System and method for optimally configuring border gateway selection for transit traffic flows in a computer network

• US 7,197,040 B2
• Filed: 07/01/2002
• Issued: 03/27/2007
• Est. Priority Date: 07/01/2002
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Smith, Mark A., Rastogi, Rajeev, Bressoud, Thomas C.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Rose, Kerri M.
• Application Number:
  US10/186,761
• Publication Number:
  US 20030142682A1
• Time in Patent Office: 1,730 Days
• Field of Search: 370/389, 370/392, 370400-402, 370/238, 370/351, 718/102, 718/104, 718/105, 709/238, 709/241
• US Class Current: 370/401
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A system for, and method of, configuring border gateway selection for transit traffic flows in a computer network. In one embodiment, the system includes: (1) a border gateway modeler that builds a model of cooperating border gateways, the model including capacities of the border gateways and (2) a traffic flow optimizer, associated with the border gateway modeler, that initially assigns traffic to the border gateways in accordance with a generalized assignment problem and subsequently reassigns the traffic to the border gateways based on cost until the capacities are respected.

Claims

1. A system for configuring border gateway selection for transit traffic flows in a computer network, comprising:

a border gateway modeler that builds a model of cooperating border gateways, said model including capacities of said border gateways; and

a traffic flow optimizer, associated with said border gateway modeler, that initially assigns traffic to said border gateways in accordance with a generalized assignment problem and subsequently reassigns said traffic to said border gateways based on cost until said capacities are respected, wherein said cost is associated with route advertisement information comprising a network prefix, an Internet Protocol address of a next-hop, a multi-exit discriminator, and a list of autonomous systems along a path to a specified destination network prefix.

2. The system as recited in claim 1 wherein said cooperating border gateways are associated with an autonomous system.

3. The system as recited in claim 1 wherein said traffic flow optimizer assumes a single egress point for traffic intended for a given address.

4. The system as recited in claim 1 wherein said traffic flow optimizer assumes multiple egress points for traffic intended for a given address.

5. The system as recited in claim 1 wherein said traffic flow optimizer reassigns said traffic to said border gateways by solving a linear programming relaxation of an integer programming formulation for said generalized assignment problem.

6. The system as recited in claim 1 wherein said capacities are selected from the group consisting of:

ingress capacities, and

egress capacities.

7. The system of claim 1, wherein said traffic flow optimizer is further configured to:

a) accept an advertisement among a plurality of advertisements with the highest local preference;

b) if a tie occurs in (a), break the tie among the plurality of advertisements that are tied in the highest local preference by accepting an advertisement of the plurality of advertisements with a shortest associated system path;

c) if a tie occurs in (b), break the tie among the plurality of advertisements that are tied in their shortest associated system path by accepting an advertisement of the plurality of advertisements with a smallest multi-exit discriminator;

d) if a tie occurs in (c), break the tie among the plurality of advertisements that are tied in their smallest multi-exit discriminator by accepting an advertisement with the smallest intra-domain cost to an egress border router; and

e) if a tie occurs in (d), break the tie among the plurality of advertisement that are tied in their smallest intra-domain cost to an egress border router by accepting an advertisement with the smallest next-hop address.

8. A system for configuring border gateway selection for transit traffic flows in a computer network, comprising:

a border gateway modeler that builds a model of cooperating border gateways including capacities thereof; and

a traffic flow optimizer, associated with said border gateway modeler, that initially assigns traffic to said border gateways in accordance with a generalized assignment problem and subseguenily reassigns said traffic to said border gateways based on cost until said capacities are respected, wherein said traffic flow optimizer holds certain of said capacities constant while reassigning said traffic to said border gateways.

9. The system as recited in claim 8, wherein said traffic flow optimizer selects a single egress of said traffic for reassignment to said border gateways.

10. The system as recited in claim 8, wherein said traffic flow optimizer selects multiple egresses of said traffic for reassignment to said border gateways.

11. The system as recited in claim 8, wherein said traffic flow optimizer reassigns said traffic to said border gateways based on cost until proximity constraints and said capacities are respected.

12. A method of configuring border gateway selection for transit traffic flows in a computer network, comprising:

building a model of cooperating border gateways, said model including capacities of said border gateways;

initially assigning traffic to said border gateways in accordance with a generalized assignment problem; and

subsequently reassigning said traffic to said border gateways based on cost until said capacities are respected, wherein said cost is associated with route advertisement information comprising a prefix, an Internet protocol address of a next-hop, a multi-exit discriminator, and a list of autonomous systems along a path to a specified network destination prefix.

13. The method as recited in claim 12 wherein said cooperating border gateways are associated with an autonomous system.

14. The method as recited in claim 12 wherein said initially assigning comprises assuming a single egress point for traffic intended for a given address.

15. The method as recited in claim 12 wherein said initially assigning comprises assuming multiple egress points for traffic intended for a given address.

16. The method as recited in claim 12 wherein said subsequently reassigning comprises reassigning said traffic to said border gateways by solving a linear programming relaxation of an integer programming formulation for said generalized assignment problem.

17. The method as recited in claim 12 wherein said capacities are selected from the group consisting of:

ingress capacities, and

egress capacities.

18. A method of configuring border gateway selection for transit traffic flows in a computer network, comprising:

building a model of cooperating border gateways including capacities thereof;

initially assigning traffic to said border gateways in accordance with a generalized assignment problem; and

subsequently reassigning said traffic to said border gateways based on cost until said capacities are respected, wherein said subsequently reassigning comprises holding certain of said capacities constant.

19. The method as recited in claim 18 wherein said subsequently reassigning comprises selecting a single egress of said traffic for reassignment to said border gateways.

20. The method as recited in claim 18 wherein said subsequently reassigning comprises selecting multiple egresses of said traffic for reassignment to said border gateways.

21. The method as recited in claim 18 wherein said subsequently reassigning said traffic to said border gateways based on cost until proximity constraints and said capacities are respected.

22. A method of managing a computer network, comprising:

collecting route advertisement information from border routers in said computer network, wherein said route advertisement information comprises a network prefix, an Internet Protocol address of a next-hop, a multi-exit discriminator, and a list of autonomous systems along a path to a specified destination network prefix;

retrieving existing policy information regarding each of said border routers;

collecting traffic information regarding each of said border routers;

employing said route advertisement information, said existing policy information and said traffic information to compute updated policy information; and

replacing said existing policy information with said updated policy information to decrease traffic through said computer network.

23. The method as recited in claim 22 wherein said method is carried out repeatedly during an operation of said computer network.

24. The method as recited in claim 22 wherein said method is repeated at user-defined intervals during an operation of said computer network.

25. The method as recited in claim 22 wherein said computer network is an autonomous system.

26. The method as recited in claim 22 wherein said employing comprises assuming a single egress point for traffic intended for a given address.

27. The method as recited in claim 22 wherein said employing comprises assuming multiple egress points for traffic intended for a given address.