# US 2015/0103662 A1 · Routing system for internet traffic

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0103662 A1
- Document ID: US20150103662A1
- Status: Published application
- Kind: A1
- Application number: 14/081,601
- Filed: 2013-11-15
- Published: 2015-04-16
- Earliest claimed: 2013-10-15
- Assignees: Internap Corporation
- Applicants: Internap Network Services Corporation
- Inventors: Marco A. Valero; Charles Victor Bancroft, II; William Brian Hammond; Adam S. Rothschild; Charles R. Gwyn, IV; Christopher B. Freas; Gilbert L. Shillcutt; Michael William Palladino
- Web page: https://patentgrep.com/patent/US20150103662A1

## CPC

- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 43/0829: Packet loss
- H04L 43/0852: Delays
- H04L 45/70: {Routing based on monitoring results}
- H04L 45/04: {Interdomain routing, e.g. hierarchical routing}
- H04L 45/124: {using a combination of metrics}
- H04L 45/125: based on throughput or bandwidth
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 1

A method of routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has a capacity associated therewith, said method comprising:
determining a traffic flow demand for each prefix in a network prefix set;
gathering performance data for each prefix along each route;
determining a performance value to each said prefix based upon said performance data;
determining in a computer a routing decision for each said prefix, each said routing decision assigning one of said plurality of routes to each one of said prefixes; wherein each said routing decision is based upon said traffic flow demand, said performance values, and the capacity associated with each route.

### Claim 2 (depends on 1)

The method of claim 1 wherein said routing decisions maximize a total sum of said performance values for said network prefix set.

### Claim 3 (depends on 1)

The method of claim 1 wherein a totality of said routing decisions represents a deterministic solution to routing all said prefixes in said network prefix set in a manner that maximizes the total sum of said performance values.

### Claim 4 (depends on 1)

The method of claim 1 further including:
making a first routing decision for a first prefix; and
making a second routing decision for a second prefix wherein said second routing decision takes into account an effect of said first routing decision on capacity.

### Claim 5 (depends on 1)

The method of claim 1 further including:
solving an objective function using a linear programming technique wherein said objective function is subject to a plurality of constraints, and said plurality of constraints includes said capacity, as well as prices associated with said routes.

### Claim 6 (depends on 1)

The method of claim 1 further including:
normalizing said performance data;
receiving user-defined weight values; and
using said user-defined weight values and said normalized performance data to determine said performance values.

### Claim 7 (depends on 1)

The method of claim 1 further including:
forwarding Internet Protocol (IP) packets along said plurality of routes in accordance with said routing decisions.

### Claim 8 (depends on 1)

The method of claim 1 further including;
inputting a route-specific constraint into said computer for a specific prefix, said route-specific constraint identifying at least one route to be avoided or used for the specific prefix; and
using said route-specific constraint when determining the routing decisions for each prefix in said network prefix set.

### Claim 9 (depends on 1)

The method of claim 1 further including:
inputting a minimum commitment level into said computer for each of said plurality of routes, said minimum commitment level identifying a level of traffic for each route above which additional charges are incurred;
inputting a price weighting into said computer, said price weighting being indicative of an importance of routing traffic in a manner that reduces price; and
using said minimum commitment level and said price weighting when making each of said routing decisions.

### Claim 10 (depends on 9)

The method of claim 9 further including:
inputting a capacity relaxation value into said computer for a selected one of said routes, said capacity relaxation variable identifying an acceptable degree to which traffic routed to said selected one of said routes may exceed the minimum commitment level for said selected one of said routes; and
using an increased capacity for said selected one of said routes when determining routing decisions for each said prefix, said increased capacity corresponding to said capacity relaxation value.

### Claim 11 (depends on 1)

The method of claim 1 further including:
using a first linear programming iteration to determine a first subset of said routing decisions corresponding to a first subset of said prefixes; and
subsequently using a second linear programming iteration to determine a second subset of said routing decisions corresponding to a second subset of said prefixes, wherein said second linear programming iteration is based on a reduced capacity, said reduced capacity accounting for an amount of capacity consumed by the traffic flow demand of said first subset of prefixes.

### Claim 12 (depends on 1)

The method of claim 1 further including:
(a) updating said traffic flow demand for each prefix in said network prefix set;
(b) gathering updated performance data for each prefix along each route; and
(c) determining in the computer a revised routing decision for each said prefix, wherein each of said revised routing decisions is based upon said updated traffic flow demand, said updated performance data, and the capacity associated with each route.

### Claim 13 (depends on 12)

The method of claim 12 wherein steps (a), (b), and (c) are performed more than ten times an hour.

### Claim 14

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, 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.

### Claim 15 (depends on 14)

The method of claim 14 further including:
determining a plurality of additional traffic flow demand for a plurality of additional prefixes in the network prefix set;
gathering performance data for each of said plurality of additional prefixes along each of said plurality of routes;
making a plurality of additional routing decisions in the computer for routing each of the plurality of additional prefixes along one of said plurality of routes, wherein:
said first routing decision also takes into account said plurality of additional traffic flow demand;
said second routing decision also takes into account said plurality of additional traffic flow demand
said third routing decision also takes into account said plurality of additional traffic flow demand; and
said plurality of additional routing decisions each take into account said first, second, and third flow demands, as well as said capacity of said plurality of routes.

### Claim 16 (depends on 14)

The method of any of claim 14 further including:
using a linear programming technique to make all of said 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.

### Claim 17 (depends on 14)

The method of claim 14 29 further including:
normalizing said performance data;
receiving user-defined weight values; and
using said user-defined weight values and said normalized performance data to determine said performance values.

### Claim 18 (depends on 16)

The method of claim 16 further including;
inputting a route-specific constraint into said computer for a specific prefix, said route specific constraint identifying at least one route to be avoided or used for the specific prefix; and
using said route-specific constraint when determining the routing decisions for each prefix in said network prefix set.

### Claim 19 (depends on 18)

The method of claim 18 further including:
inputting a minimum commitment level into said computer for each of said plurality of routes, said minimum commitment level identifying a level of traffic for each route above which additional charges are incurred;
inputting a price weighting into said computer, said price weighting being indicative of an importance of routing traffic in a manner that reduces price;
inputting a capacity relaxation value into said computer for a first one of said routes, said capacity relaxation variable identifying an acceptable degree to which traffic routed to said first one of said routes may exceed the minimum commitment level for said first one of said routes; and
using said minimum commitment level and said price weighting when making each of said routing decisions; and
using an increased capacity for said first one of said routes when determining routing decisions for said first, second, and third prefixes, said increased capacity corresponding to said capacity relaxation value.

### Claim 20 (depends on 19)

The method of claim 19 further including:
using a first linear programming iteration to determine said first routing decision;
subsequently using a second linear programming iteration to determine said second routing decision, wherein said second linear programming iteration is based on a first reduced capacity, said first reduced capacity accounting for an amount of the capacity consumed by the traffic flow demand of said first prefix; and
subsequently using a third linear programming iteration to determine said third routing decision, wherein said third linear programming iteration is based on a second reduced capacity, said second reduced capacity accounting for an amount of the capacity consumed by the traffic flow demand of said first and second prefixes.

### Claim 21

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 including:
a traffic estimator adapted to determine a traffic flow demand for each prefix in a network prefix set;
a performance evaluator adapted to gather performance data for each prefix along each route; and
a routing engine adapted to determine a routing decision for each said prefix wherein each said routing decision assigns one of said plurality of routes to each one of said prefixes; and wherein each said routing decision is based upon said traffic flow demand, said performance data, and the capacity associated with each route.

### Claim 22 (depends on 21)

The system of claim 21 wherein said routing engine is further adapted to determine a performance value for each said prefix based upon said performance data, and said routing decisions maximize a total sum of said performance values for said network prefix set.

### Claim 23 (depends on 21)

The system of claim 21 wherein said performance evaluator is implemented in a first computer, said routing engine is implemented in a second computer different from said first computer, and said traffic estimator is implemented in a third computer different from said first and second computers.

### Claim 24 (depends on 22)

The system of claim 22 wherein said routing engine uses a linear programming technique to determine said routing decisions, wherein said linear programming technique includes solving an objective function subject to a plurality of constraints including said capacity, as well as prices associated with said routes.

### Claim 25 (depends on 21)

The system of claim 21 wherein said performance values include a weighted sum of a latency and loss metrics, and said routing engine is adapted to receive from a user a plurality of weights to be used in computing said weighted sum.

### Claim 26 (depends on 21)

The system of claim 21 wherein said routing engine is adapted to receive a route-specific constraint for a specific prefix and use said route-specific constraint when determining the routing decisions for each prefix in said network prefix set, wherein said route-specific constraint identifies a specific route to either be used or avoided for the specific prefix.

### Claim 27 (depends on 21)

The system of claim 21 wherein said routing engine is adapted to receive from a user a minimum commitment level for each of said plurality of routes, wherein said minimum commitment level identifies a level of traffic for each route above which additional charges are incurred, and said routing engine is further adapted to receive a capacity relaxation value for a selected one of said routes, said capacity relaxation variable identifying an acceptable degree to which traffic routed to said selected one of said routes may exceed the minimum commitment level for said selected one of said routes, and wherein said routing engine uses an increased capacity for said selected one of said routes when determining routing decisions for each said prefix, said increased capacity corresponding to said capacity relaxation value.

### Claim 28 (depends on 21)

The system of claim 21 wherein said routing engine uses a first linear programming iteration to determine a first subset of said routing decisions corresponding to a first subset of said prefixes; and
said routing engine subsequently uses a second linear programming iteration to determine a second subset of said routing decisions corresponding to a second subset of said prefixes, said second linear programming iteration being based on a reduced capacity that accounts for an amount of capacity consumed by the traffic flow demand of said first subset of prefixes.

### Claim 29 (depends on 21)

The system of claim 21 wherein:
(a) said traffic estimator updates said traffic flow demand for each prefix in said network prefix set;
(b) said performance evaluator gathers updated performance data for each prefix along each route; and
(c) said routing engine determines a revised routing decision for each said prefix, wherein each of said revised routing decisions is based upon said updated traffic flow demand, said updated performance data, and the capacity associated with each route.

### Claim 30

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 including
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; and
said third routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes.

### Claim 31 (depends on 30)

The system of claim 30 wherein:
said traffic estimator determines a plurality of additional traffic flow demand for a plurality of additional prefixes in the network prefix set;
said performance evaluator gathers performance data for each of said plurality of additional prefixes along each of said plurality of routes; and
said routing engine makes a plurality of additional routing decisions for routing each of the plurality of additional prefixes along one of said plurality of routes; wherein:
said first routing decision also takes into account said plurality of additional traffic flow demand;
said second routing decision also takes into account said plurality of additional traffic flow demand
said third routing decision also takes into account said plurality of additional traffic flow demand; and
said plurality of additional routing decisions each take into account said first, second, and third flow demands, as well as said capacity of said plurality of routes.

### Claim 32 (depends on 30)

The system of claim 30 wherein said routing engine determines a performance value for each of said first, second, and third prefixes based upon said performance data; determines a set of said first, second, and third routing decisions that maximizes a sum of said performance values; and forwards Internet Protocol (IP) packets along said plurality of routes in accordance with said set of first, second, and third routing decisions.

### Claim 33 (depends on 32)

The system of claim 32 wherein said routing engine is configured to use a linear programming technique to make all of said routing decisions, said linear programming technique including solving an objective function subject to a plurality of constraints including said capacity, as well as prices associated with said routes; and
wherein said performance values include a weighted sum of a latency and loss metrics, and said routing engine is adapted to receive from a user a plurality of weights to be used in computing said weighted sum.

### Claim 34 (depends on 33)

The system of claim 33 wherein said routing engine is adapted to receive a route-specific constraint for a specific prefix and use said route-specific constraint when determining the routing decisions for each prefix in said network prefix set, wherein said route-specific constraint identifies a specific route either be used or avoided for the specific prefix.

### Claim 35 (depends on 33)

The system of claim 33 wherein said routing engine is configured to receive from a user a minimum commitment level for each of said plurality of routes, said minimum commitment level identifying a level of traffic for each route above which additional charges are incurred; and said routing engine is further adapted to receive a capacity relaxation value for a selected one of said routes, said capacity relaxation variable identifying an acceptable degree to which traffic routed to said selected one of said routes may exceed the minimum commitment level for said selected one of said routes; and said routing engine being is further configured to use an increased capacity for said selected one of said routes when determining routing decisions for said first, second, and third prefixes, said increased capacity corresponding to said capacity relaxation value.

### Claim 36 (depends on 35)

The system of claim 35 wherein:
said traffic estimator updates said traffic flow demand for said first, second, and third prefixes;
said performance evaluator updates performance data for said first, second, and third prefixes along each route; and
said routing engine determines a revised routing decision for each of said first, second, and third prefixes, wherein each of said revised routing decisions is based upon said updated traffic flow demand, said updated performance data, and the capacity associated with each route.
