Method and apparatus for performance and cost optimization in an internetwork
View Patent ↗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.
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.
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.
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.
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.