Method and system for optimizing routing through multiple available internet route providers
First Claim
1. A method for routing traffic from a source to a routing destination in a network where a plurality of routes arm available, comprising:
- assigning a cost to each of said routes and selecting the route with the lowest cost as defined by a cost function, wherein said cost is a function of a path characteristic over the route to which said cost is assigned;
for at least one route, determining the location of said routing destination and inferring said path characteristic based on measurement of said path characteristic associated with sending tic from said source to another destination over said available routes, wherein the location of said routing destination is determined by circular intersection by;
measuring the time it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles.
16 Assignments
0 Petitions
Accused Products
Abstract
A method and system for optimizing routing traffic to a destination when multiple routes are available. A performance monitoring and inference component measures the performance of the available paths to a large set of subnetworks, and uses those measurements to infer the performance of all available paths to an even larger set of subnetworks. A routing optimization component uses a cost function that assigns a cost to a routing table based on information from the performance monitoring and inference component, as well as other path characteristics, and further uses a minimization methodology to find a routing table with a very low cost, as defined by the cost function. A BGP bridge takes the routing table generated by the routing optimization component and communicates that information to the routers using BGP, thereby ensuring that the routers will route traffic in accordance with the routing table.
208 Citations
63 Claims
-
1. A method for routing traffic from a source to a routing destination in a network where a plurality of routes arm available, comprising:
-
assigning a cost to each of said routes and selecting the route with the lowest cost as defined by a cost function, wherein said cost is a function of a path characteristic over the route to which said cost is assigned;
for at least one route, determining the location of said routing destination and inferring said path characteristic based on measurement of said path characteristic associated with sending tic from said source to another destination over said available routes, wherein the location of said routing destination is determined by circular intersection by;
measuring the time it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for routing traffic from a source to a routing destination in a network where a plurality of routes are available, comprising:
-
obtaining a measurement of a path characteristic associated with routing traffic from said source to said routing destination for a first route; and
determining the location of said routing destination and inferring said path characteristic for a second route based on measurement of said path characteristic associated with sending traffic from said source to another destination, wherein the location of said routing destination is determined by circular intersection by;
measuring the time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents; and
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center;
using a cost function, assigning a cost to each available route as a function of the path characteristic associated with said route;
minimizing said cost function over said available routes; and
routing said traffic according to the lowest cost route determined by minimizing said cost function. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A method for routing traffic from a source to a routing destination in a network where a plurality of routes are available, comprising:
-
obtaining a measurement of a path characteristic associated with routing traffic from said source to said routing destination for a first route; and
determining the location of said routing destination and inferring said path characteristic for a second route based on measurement of said path characteristic associated with sending traffic from said source to another destination, wherein the location of said routing destination is determined by circular intersection by;
measuring the time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents; and
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles;
using a cost function, assigning a cost to each available route as a function of the path characteristic associated with said route;
selecting the route with the lowest cost as defined by said cost function; and
routing said traffic according to the lowest cost route. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. A method for routing traffic from a source to a routing destination in a network where a plurality of routes are available, comprising:
-
obtaining a measurement of a path characteristic associated with routing traffic from said source to said routing destination for a first route; and
inferring said path characteristic for a second route based on measurement of said path characteristic associated with sending traffic from said source to another destination, wherein the location of said routing destination is determined by circular intersection by;
measuring th time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles;
using a cost function, assigning a cost to each available route as a function of the path characteristic associated with said route;
minimizing said cost function over said routes and identifying a route with the lowest cost of routing said traffic as defined by said cost function; and
generating a routing table containing said lowest cost route. - View Dependent Claims (20, 21, 22, 23, 24)
-
-
25. A computer-readable medium comprising commuter-executable instructions for:
-
assigning a cost to each routes from a source to a routing destination in a network where a plurality of routes are available, wherein said cost is a function of a path characteristic over the route, and selecting the route with the lowest cost as defined by a cost function, wherein assigning a cost to each of said routes comprises;
determining, the location of said routing destination and inferring said path characteristic based on measurement of said path characteristic associated with sending traffic from said source to another destination over said available routes, wherein determining the location of said routing destination comprises;
measuring the time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles. - View Dependent Claims (26, 27, 28, 29, 30)
-
-
31. A computer-readable medium including computer executable instructions for routing traffic source to a routine destination in a network where a plurality of routes are available, wherein the instructions comprise:
-
obtaining a measurement of a path characteristic associated with routing traffic from said source to said routing destination for a first route; and
determining the location of said routing destination and inferring said path characteristic for a second route based on measurement of said path characteristic associated with sending traffic from said source to another destination by;
measuring the time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles;
using a cost function, assigning a cost to each available route as a function of the path characteristic associated with said route;
minimizing said cost function over said available routes; and
routing said traffic according to the lowest cost route determined by minimizing said cost function. - View Dependent Claims (32, 33, 34, 35, 36)
-
-
37. A computer-readable medium including computer-executable instructions fort routing traffic from a source to a routing destination in a network wherein a plurality of routes are available, wherein the instructions comprise:
-
obtaining a measurement of a path characteristic associated with routing traffic from said source to said routing destination for a first path; and
determining the location of said routing destination and inferring said path characteristic for a second route based on measurement of said path characteristic associated with sending traffic from said source to another destination by;
measuring the time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles;
using a cost function, assigning a cost to each available route as a function of the path characteristic associated with said route;
selecting the route with the lowest cost as defined by said cost function; and
routing said traffic according to the lowest cost route. - View Dependent Claims (38, 39, 40, 41, 42)
-
-
43. A computer-readable medium including computer-executable instructions for routing traffic from a source to a routing destination in a network where a plurality of routes are available, wherein the instructions comprise:
-
obtaining a measurement of a path characteristic associated with routing traffic from said source to said routing destination for a first path; and
determining the location of said routing destination and inferring said path characteristic for a second route based on measurement of said path characteristic associated with sending tic from said source to another destination by;
measuring the time that it takes for traffic to move from a plurality of source locations to said routing destination;
converting said times to distance equivalents;
forming a plurality of intersecting circles using said distance equivalents as the radius of circles with said source locations as the center; and
determining the physical location of said routing destination from the intersection of said circles;
using a cost function, assigning a cost to each available route as a function of the path characteristic associated with said route;
minimizing said cost function over said routes and identifying a route with the lowest cost of routing said traffic as defined by said cost function; and
generating a routing table containing said lowest cost route. - View Dependent Claims (44, 45, 46, 47, 48)
-
-
49. A method for determining a route based on measured and inferred path characteristics, comprising:
-
measuring a path characteristic associated with a first path between a first subnet source and a first subnet destination;
measuring a path characterstics associated with a second path between the first subnet source and a second subnet destination;
inferring a path characteristic associated with a third path between the first subnet source and a third subnet destination using a weighted average of the measured path characteristic associated with the first path and the measured path characteristic associated with the second path; and
determining a next hop subnet for each of the paths using a cost function based on the path characteristic and at least one additional path characteristic, wherein the cost function uses a coefficient to weight the path characteristic and the at least one additional path characteristic. - View Dependent Claims (50, 51, 52, 53, 54, 55, 56)
-
-
57. A method for identifying optimized routes between a plurality of subnet sources and a plurality of subnet destinations, comprising:
-
for each subnet source, obtaining performance data for a plurality of possible routes between the subnet source and the subnet destinations;
selecting an initial route based on the performance data; and
optimizing the routes by;
for each subnet source, optimizing the routes from the subnet source to the subnet destinations by selecting the routes having a lowest cost using a cost function that is based on weighted path characteristics; and
for each subnet destination, optimizing the routes from the subnet sources to the subnet destination by selecting the routes having a lowest cost based on the cost function. - View Dependent Claims (58, 59, 60, 61, 62)
-
-
63. A method for propagating routes to a plurality of routers within an autonomous System (AS), comprising:
-
receiving route information from within the AS for a plurality of routes between the AS and a plurality of prefix destinations;
receiving route information from a plurality of neighboring ASs via Border Gateway Protocol (BGP);
based on the routing information from the AS and the neighboring ASs, determining a next hop AS for each of the routes between the AS and the prefix destinations; and
propagating the next hop donation to a plurality of routes within the AS.
-
Specification