Method and apparatus for performance and cost optimization in an internetwork

• US 7,406,539 B2
• Filed: 08/06/2001
• Issued: 07/29/2008
• Est. Priority Date: 10/17/2000
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Finn, Sean P., Baldonado, Omar C., Villaverde, Jose-Miguel Pulido, McGuire, James G., Madan, Herbert S., Lloyd, Michael A., Karam, Mansour J.
• Primary Examiner(s): Nguyen, Dustin
• Application Number:
  US09/923,924
• Publication Number:
  US 20020078223A1
• Time in Patent Office: 2,549 Days
• Field of Search: 709/232, 709/224, 709/238, 709/226, 709/229, 709/241, 370/15, 370/238, 370/395, 370/401, 370/431, 370/404, 370/443, 370/412, 370/392, 370/395.32, 370/254, 370/351, 379/88, 398/42
• US Class Current: 709/240
• 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, wherein the prefix corresponds to an application selectable from a plurality of applications;

calculating a plurality of application-specific performance scores for the plurality of service provider access links, each of the plurality of application-specific performance scores indicating performance for an application 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 an application-specific performance score from the plurality of service provider access links;

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 superior performance score from the plurality of application-specific performance scores superior to the performance score for the current service provider access link; and

implementing a route update request according to a priority queue, wherein the route update request corresponds to the superior performance score.

2. The method of claim 1, wherein the plurality of application-specific performance scores are 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 application-specific performance scores are 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 application-specific performance scores are 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 application-specific performance scores comprises a scalar value.

6. The method of claim 5, wherein the plurality of application-specific performance scores are customized for HTTP traffic.

7. The method of claim 5, wherein the plurality of application-specific performance scores are customized for video traffic.

8. The method of claim 5, wherein the plurality of application-specific performance scores are customized for VoIP traffic.

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

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

11. The method of claim 1, further comprising transmitting the selected new service provider access link to the one or more routers.

12. The method of claim 11, wherein the selected new service provider access link is transmitted using a Border Gateway Protocol update message.

13. The method of claim 1, wherein selecting a new service provider access link comprises comparing a best route to a default BGP route.

14. The method of claim 5, wherein each performance score from the plurality of performance scores is customized for any one of a plurality of customer-selectable applications selected from the group consisting of a Web-based application, a voice application, and a video application.

18. The method of claim 1, wherein selecting a new service provider access link depends on a difference between a performance score of the new service provider access link and a performance score of the current service provider access link.

19. The method of claim 1, further comprising assessing a penalty to a performance score for at least one of the current service provider access link and the new service provider access link.

15. A method of routing from a source node to a group of destination nodes having a common prefix comprising:

a. generating a plurality of performance scores for a plurality of routes from the source node to the group of destination nodes, each performance score corresponding to an access link from one or more access links;

b. determining a superior performance score from the plurality of performance scores;

c. implementing a route update request according to a priority queue, wherein the route update request corresponds to the superior performance score, the priority queue prioritizes received route update requests according to urgency, and a rank of the update request for a prefix in the priority queue is dependent on a percent improvement of a performance score resulting from moving the prefix from its current route to a pending winner route; and

d. configuring a router to select an access link corresponding to the route update request.

16. The method of claim 15, further comprising transmitting data related to a route containing the selected access link to the one or more access links.

17. The method of claim 16, wherein the data comprises network layer reachability information.

20. A method of routing from a source node to a group of destination nodes having a common prefix comprising:

a. generating a plurality of performance scores for a plurality of routes from the source node to the group of destination nodes, each performance score corresponding to an access link from one or more access links, wherein a performance score from the plurality of performance scores is determined by unpacking the group into component prefixes in the event a change in a performance score for the group above a threshold level is determined and generating performance scores for each of the component prefixes;

b. determining a superior performance score from the plurality of performance scores;

c. implementing a route update request according to a priority queue, wherein the route update request corresponds to the superior performance score; and

d. transmitting a routing change corresponding to the route update request to one or more routers along the routes to route data along an access link.