Routing system for internet traffic
First Claim
1. A method of routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has capacity associated therewith, said method comprising:
- determining a first, second, and third traffic flow demand for a first, second, and third prefix, respectively, in a network prefix set;
gathering performance data for each of said first, second, and third prefixes along each of said plurality of routes;
making first, second, and third routing decisions in a computer for routing each of said first, second, and third prefixes, respectively, along one of said plurality of routes,said computer using a linear programming technique to make said first, second, and third routing decisions, said linear programming technique including solving an objective function subject to a plurality of constraints, wherein said plurality of constraints includes said capacity, as well as prices associated with said routes;
wherein;
said first routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes;
said second routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes;
said third routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; and
forwarding Internet Protocol (IP) packets along said plurality of routes in accordance with said first, second, and third routing decisions.
10 Assignments
0 Petitions
Accused Products
Abstract
A deterministic approach for route selection in the Internet and other multi-homed networks is presented that is based upon a mathematical model that takes into consideration performance and costs while satisfying commitment constraints. The approach is expressed with a linear programming formulation that can be solved with conventional linear programming solver software. Performance metrics can be defined and combined in order to achieve the best route selection depending on requirements. Some of the potential benefits of the approach include: a global optimal solution for routing traffic (using metrics such as performance, cost, and other constraints), a dynamic weight assignment for performance metrics, and a flexible problem definition to add routing rules (e.g. static and restricted routes) to the model.
154 Citations
10 Claims
-
1. A method of routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has capacity associated therewith, said method comprising:
-
determining a first, second, and third traffic flow demand for a first, second, and third prefix, respectively, in a network prefix set; gathering performance data for each of said first, second, and third prefixes along each of said plurality of routes; making first, second, and third routing decisions in a computer for routing each of said first, second, and third prefixes, respectively, along one of said plurality of routes, said computer using a linear programming technique to make said first, second, and third routing decisions, said linear programming technique including solving an objective function subject to a plurality of constraints, wherein said plurality of constraints includes said capacity, as well as prices associated with said routes;
wherein;said first routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; said second routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; said third routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; and forwarding Internet Protocol (IP) packets along said plurality of routes in accordance with said first, second, and third routing decisions. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system for routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has a capacity associated therewith, said system comprising:
-
memory; a processor configured to execute instructions in the memory to carry out the following functions; a traffic estimator adapted to determine a traffic flow demand for a first, second, and third prefix in a network prefix set; a performance evaluator adapted to gather performance data for each of said first, second, and third prefixes along each of said plurality of routes; a routing engine adapted to make first, second, and third routing decisions for routing each of said first, second, and third prefixes, respectively, along one of said plurality of routes, wherein; said first routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; said second routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; said third routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; and wherein said routing engine performs the following; (a) determines a performance value for each of said first, second, and third prefixes based upon said performance data, said performance values including a weighted sum of a latency metric and a loss metric; (b) receives from a user a plurality of weights to be used in computing said weighted sum; (c) determines a set of said first, second, and third routing decisions that maximizes a sum of said performance values; (d) forwards Internet Protocol (IP) packets along said plurality of routes in accordance with said set of first, second, and third routing decisions; and (e) uses a linear programming technique to make said first, second, and third routing decisions, wherein said linear programming technique includes solving an objective function subject to a plurality of constraints including said capacity of said plurality of routes, as well as prices associated with said routes. - View Dependent Claims (7, 8, 9, 10)
-
Specification