Data network controller

• US 7,668,966 B2
• Filed: 11/01/2002
• Issued: 02/23/2010
• Est. Priority Date: 11/02/2001
• Status: Active Grant

• Current Assignee: Internap Holding LLC
• Original Assignee: Internap Network Services Corporation
• Inventors: Johnson, Jeremy, Chaffee, Gordon, Klinker, Eric, Fraleigh, Charles J., McCanne, Steven, McKernan, Daniel S.
• Primary Examiner(s): Follansbee; John
• Assistant Examiner(s): Chou; Alan S
• Application Number:
  US10/286,576
• Publication Number:
  US 20030088529A1
• Time in Patent Office: 2,671 Days
• Field of Search: 709/232
• US Class Current: 709/232
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/028 by filtering
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/38 : Flow based routing
• CPC Class Codes: H04L 47/20 : Traffic policing
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/9023 : for implementing a jitter-buffer
• CPC Class Codes: H04L 65/1101 : Session protocols
• CPC Class Codes: H04L 65/80 : Responding to QoS
• CPC Class Codes: H04L 69/14 : Multichannel or multilink protocols
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers

Abstract

The present invention provides for a system and method for data network control. Using a flow control system, embodiments of the present invention can analyze traffic flow volume and performance, incorporate usage, billing, and cost control data to yield an improved data network controller. Efficiency in data routing is improved while costs are decreased by enabling the selection of the optimal performance data route. Cost constraints and costs are minimized for an overall data load. Given a diverse set of cost structures for available transit providers, the overall system cost can be minimized by distributing traffic in a manner that takes advantage of the diverse billing structures and yet maintains acceptable performance levels. Systems and methods in accordance with embodiments of the present invention determine projected flow performance and projected flow volume in relation to the available bandwidth and marginal cost to a destination provider.

Claims

1. A method for controlling a data flow on a network, wherein the network includes a plurality of network service providers (NSPs), the method comprising:

comparing a candidate loss for a candidate NSP to a current loss for the current NSP, wherein the current NSP is currently used for routing the data flow and the candidate NSP is selected from the remaining ones of the plurality of NSPs;

comparing a candidate latency for the candidate NSP to a current latency for the current NSP;

if the candidate loss and the candidate latency for the candidate NSP are better than the current loss and the current latency for the current NSP, then comparing the candidate NSP to the other of the remaining ones of the plurality of NSPs by;

determining a best latency of the remaining ones of the NSPs;

determining a best loss of the remaining ones of the NSPs;

for those remaining ones of the NSPs that have the best latency and the best loss, determining a greatest available bandwidth of the remaining ones of the NSPs;

for those remaining ones of the NSPs that have the greatest available bandwidth, determining a least next cost tier;

for those remaining ones of the NSPs that have the least next cost tier, determining a lowest identifier; and

assigning a change value so that the data flow is moved from the current NSP to the remaining one of the NSPs that has the lowest identifier.

2. An apparatus for controlling a data flow on a network, wherein the network includes a plurality of network service providers (NSPs) and the data flow is currently routed through a current NSP, the apparatus comprising at least one computing device configured to:

evaluate a candidate latency for a candidate NSP, wherein the candidate NSP is selected from remaining ones of the plurality of NSPs;

evaluate a candidate loss for the candidate NSP;

evaluate a candidate bandwidth for the candidate NSP to a bandwidth allocation for the candidate NSP;

determine a loss value for the remaining ones of the plurality of NSPs;

determine a cost for the remaining ones of the plurality of NSPs;

evaluate an identifier for the remaining ones of the plurality of NSPs; and

determine a change value.

3. The apparatus of claim 2, wherein the at least one computing device is further configured to:

determine a lowest latency for the remaining ones of the plurality of NSPs if said candidate bandwidth is less than said bandwidth allocation;

determine a lowest loss for the remaining ones of the plurality of NSPs;

determine a greatest available bandwidth based on a cost and a usage variable for the remaining ones of the plurality of NSPs;

determine a cost tier for the remaining ones of the plurality of NSPs;

determine a lowest identifier for the remaining ones of the plurality of NSPs; and

assign a change value.

4. An apparatus for controlling a data flow on a network, wherein the network includes a plurality of network service providers (NSPs) and the data flow is currently routed through a current NSP, the apparatus comprising at least one computing device configured to:

compare a candidate loss for a candidate NSP to a current loss for the current NSP, wherein the candidate NSP is selected from the remaining ones of the plurality of NSPs;

compare a candidate latency for the candidate NSP to a current latency for the current NSP;

determine a best latency of the remaining ones of the plurality of NSPs;

determine a best loss of the remaining ones of the plurality of NSPs;

evaluate a candidate bandwidth for the candidate NSP;

determine a maximum candidate bandwidth value for the candidate NSP;

determine a cost tier for the remaining ones of the plurality of NSPs;

determine a lowest identifier of the remaining ones of the plurality of NSPs; and

assign a change value to control routing of the data flow.

5. A computer-readable medium storing instructions for controlling data flow on a network, wherein the network includes a plurality of network service providers (NSPs) and the data flow is currently routed through a current NSP, by performing the steps of:

evaluating a candidate latency for a candidate NSP, wherein the candidate NSP is selected from remaining ones of the plurality of NSPs;

evaluating a candidate loss for a candidate NSP;

comparing a candidate bandwidth for a candidate NSP to a bandwidth allocation for a candidate NSP;

determining a loss value for at least some of the remaining ones of the plurality of NSPs;

determining a cost for at least some of the remaining ones of the plurality of NSPs;

evaluating an identifier for at least some of the remaining ones of the plurality of NSPs; and

determining a change value.

6. The computer-readable medium of claim 5, further comprising the steps of:

determining a lowest latency for at least some of the remaining ones of the plurality of NSPs if said candidate bandwidth for the candidate NSP is less than said bandwidth allocation for the candidate NSP;

determining a lowest loss for at least some of the remaining ones of the plurality of NSPs;

determining a greatest available bandwidth for at least some of the remaining ones of the plurality of NSPs based on a cost and a usage variable;

determining a cost tier for at least some of the remaining ones of the plurality of NSPs;

determining a lowest identifier for at least some of the remaining ones of the plurality of NSPs;

and assigning a change value.

7. A computer-readable medium storing instructions for controlling a data flow on a network, wherein the network includes a plurality of network service providers (NSPs) and the data flow is currently routed through a current NSP, by performing the steps of:

comparing a candidate loss for a candidate NSP to a current loss for the current NSP, wherein the candidate NSP is selected from remaining ones of the plurality of NSPs;

comparing a candidate latency for the candidate NSP to a current latency for the current NSP;

determining a best latency for the remaining ones of the plurality of NSPs;

determining a best loss for the remaining ones of the plurality of NSPs;

evaluating a candidate bandwidth values for the candidate NSP;

determining a maximum candidate bandwidth value for the candidate NSP;

determining a cost tier for the remaining ones of the plurality of NSPs;

determining a lowest identifier for the remaining ones of the plurality of NSPs; and

assigning a change value to control the data flow.

8. A method for distributing data flows between a plurality of network system providers (NSPs), wherein each NSP has a multi-tier cost structure and a minimum commitment level, the method comprising:

providing a data flow on a current NSP;

for a candidate NSP, wherein the candidate NSP is one of the remaining NSPs;

comparing performance data for the current NSP with performance data for the candidate NSP;

if the performance data for the candidate NSP is better than the performance data for the current NSP, then determining whether current bandwidth for the candidate NSP is below bandwidth allocation for the candidate NSP;

if the current bandwidth for the candidate NSP is below the bandwidth allocation for the candidate NSP, then

comparing performance data for the candidate NSP with other ones of the remaining NSPs; and

comparing cost data for the candidate NSP with other ones of the remaining NSPs; and

based on the performance data and cost data comparisons, changing the data flow from the first NSP to one of the remaining NSPs.

9. The method of claim 8, wherein comparing performance data for the current NSP with performance data for the candidate NSP comprises comparing latency data or loss data.

10. The method of claim 8, wherein comparing performance data for the candidate NSP with other ones of the remaining NSPs, comprises comparing latency data or loss data.

11. The method of claim 8, wherein comparing cost data for the candidate NSP with other ones of the remaining NSPs, comprises comparing a cost for the minimum commitment level for the candidate NSP with a cost for the minimum commitment levels for the other ones of the remaining NSPs.

12. The method of claim 8, wherein comparing cost data for the candidate NSP with other ones of the remaining NSPs, comprises comparing a cost for a next cost tier for the candidate NSP with a cost for the next cost tier for the other ones of the remaining NSPs.