Method and apparatus for performance and cost optimization in an internetwork

• US 20090006647A1
• Filed: 06/11/2008
• Published: 01/01/2009
• Est. Priority Date: 10/17/2000
• Status: Active Grant

• Current Assignee: Herbert S. Madan, James G. Mcguire, Jose-Miguel Pulido Villaverde, Mansour J. Karam, Michael A. Lloyd, Omar C. Balonado, Sean P. Finn
• Original Assignee: Herbert S. Madan, James G. Mcguire, Jose-Miguel Pulido Villaverde, Mansour J. Karam, Michael A. Lloyd, Omar C. Balonado, Sean P. Finn
• Inventors: Karam, Mansour J., Finn, Sean P., Lloyd, Michael A., McGuire, James G., Madan, Herbert S., Balonado, Omar C., Villaverde, Jose-Miguel Pulido
• Granted Patent: US 7,840,704 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/0811 by checking connectivity
• 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 43/55 Testing of service level quality, e.g. simulating service usage
• 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/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• 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-10. -10. (canceled)

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.

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.

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.

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.