Method and apparatus for performance and cost optimization in an internetwork

• US 20020078223A1
• Filed: 08/06/2001
• Published: 06/20/2002
• Est. Priority Date: 10/17/2000
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Mcguire, James G., Baldonado, Omar C., Karam, Mansour J., Finn, Sean P., Lloyd, Michael A., Madan, Herbert S., Villaverde, Jose-Miguel Pulido
• Granted Patent: US 7,406,539 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

Systems and methods are described for supporting routing intelligence for evaluating routing paths based on performance measurements. The routing intelligence may include processes executed in a self-contained device. This device may control one or more edge routers, based on performance data from end users. In other embodiments, the routing intelligence device may be used solely to monitor one or more edge routers, producing reports but not effecting any changes to routing. Routing decisions may be injected to the edge routers via BGP updates. The devices may be stationed at the premises of a multihomed organization, such as an enterprise, ISP, government organization, university, or other organization supporting a sub-network coupled to an internetwork. In other embodiments, the routing intelligence comprises processes executed on a router.

Claims

1. A method of routing a data flow traversing one or more routers in an internetwork, wherein the one or more routers are coupled to a plurality of service provider access links, the method comprising:

determining a prefix for the data flow;

calculating a plurality of performance scores for the plurality of service provider access links, each of the plurality of performance scores indicating performance of a route from a router of the one or more routers to the prefix via a distinct service provider access link from the plurality of service provider access links;

detecting a current service provider access link for the prefix, the current service provider access link corresponding to a current route to the prefix specified by a routing protocol, the current service provider access link having a performance score from the plurality of service provider access links; and

selecting a new service provider access link from the plurality of service provider access links for routing the data flow to the prefix, wherein the new server provider access link has a performance score from the plurality of performance scores superior to the performance score for the current service provider access link.

2. The method of claim 1, wherein the plurality of performance scores is at least partially dependent upon delay measurements across the plurality of service provider access links.

3. The method of claim 1, wherein the plurality of performance scores is at least partially dependent upon jitter measurements across the plurality of service provider access links.

4. The method of claim 1, wherein the plurality of performance scores is at least partially dependent upon loss measurements across the plurality of service provider access links.

5. The method of claim 1, wherein each of the plurality of performance scores comprises a scalar value.

6. The method of claim 5, wherein the plurality of performance scores is customized for HTTP traffic.

7. The method of claim 5, wherein the plurality of performance scores is customized for video traffic.

8. The method of claim 5, wherein the plurality of performance scores is customized for VoIP traffic.

9. The method of claim 1, wherein the plurality of performance scores is at least partially dependent upon interface load measurements.

10. The method of claim 1, wherein the plurality of performance scores is at least partially dependent upon user configurable weights.

11. A networking device for improving performance of one or more edge routers in communication with the networking device, the networking device comprising:

a prefix database including a plurality of network prefixes;

a priority queue, the priority queue including a plurality of entries for a subset of the plurality of network prefixes, such that the subset of the plurality of network prefixes is arranged in the priority queue in order of relative improvement in routing performance;

an asynchronous thread executing on the networking device, wherein the asynchronous thread retrieves the subset of the plurality of network prefixes from the prefix database and inserts the subset of the plurality of network prefixes in the priority queue in the order of relative improvement in routing performance; and

a synchronous thread executing on the networking device concurrently with the asynchronous thread, wherein the synchronous thread retrieves the subset of the plurality of network prefixes from the priority queue in the order of relative improvement in routing performance.

12. The networking device of claim 11, wherein the subset of the plurality of network prefixes is retrieved by the synchronous thread from the priority queue at a fixed rate.

13. The networking device of claim 12, wherein the fixed rate is user specified.

15. The routing intelligence device of claim 14, further comprising:

a plurality of blades, such that each of the plurality of service provider access links associates with one or more blades of the plurality of blades for measuring a performance of the service provider access link.

16. The routing intelligence device of claim 15, further comprising:

one or more processes for selecting a preferred service provider access link from the plurality of service provider access links, the one or more processes executed on a decision blade from the plurality of blades.

17. The routing intelligence device of claim 15, further comprising:

a communication backplane, the communication backplane coupling the plurality of blades.

18. The routing intelligence device of claim 14, further comprising:

a control protocol for communication between the routing intelligence device and the plurality of routers.

19. The routing intelligence device of claim 18, wherein the control protocol is iBGP.

14. A routing intelligence device for controlling a plurality of routers, wherein each of the plurality of routers is coupled to a plurality of service provider access links (SPALs), such that each of the plurality of routers is coupled to a distinct subset of the plurality of service provider access links, the routing intelligence device comprising:

an internal database, the internal database including a plurality of records including;

a key field storing one or more network prefixes;

a service provider access link field storing one or more identifiers for one or more current service provider access links from the plurality of service provider access links for linking the plurality of routers to the one or more network prefixes;

an update flag indicating whether the service provider access link field was recently updated; and

one or more performance scores for the one or more current service provider access links.

20. A routing intelligence device comprising:

an internal database, the internal database including a plurality of records including;

a key field storing one or more network prefixes;

a service provider access link field storing one or more identifiers for one or more current service provider access links from a plurality of service provider access links for communicating with the one or more network prefixes;

an update flag indicating whether the service provider access link field was recently updated; and

one or more performance scores for the one or more current service provider access links.

21. The routing intelligence device of claim 20, wherein the routing intelligence device is in communication with the one or more service provider access links via one or more routers.

22. The routing intelligence device of claim 20, wherein the routing intelligence device is a router coupled to the one or more service provider access links