Method and apparatus for communications traffic engineering

• US 7,230,924 B2
• Filed: 03/28/2001
• Issued: 06/12/2007
• Est. Priority Date: 03/28/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Chiu, Angela L., Tang, Zhuangbo, Civanlar, Seyhan, Lu, Leonard L.
• Primary Examiner(s): Patel; Ajit
• Assistant Examiner(s): Shew; John
• Application Number:
  US09/819,555
• Publication Number:
  US 20020186658A1
• Time in Patent Office: 2,267 Days
• Field of Search: 370229-230, 370/230.1, 370231-235, 3702351-236, 370/236.1, 3702362-238, 3702381-240, 370/242, 370/328, 370351-352, 370/395.4, 370/401, 370/522, 379/219, 379/221.03, 379/221.04, 709239-242
• US Class Current: 370/237
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

This invention provides for a technique for selectively off-loading traffic from congested sub-regions of a network to more lightly-loaded regions by making use of Multiprotocol Label Switching (MPLS). For each network element, an Interior Gateway Protocol (IGP) routing is employed to provide re-routing and to identify congested links caused by re-routed trunks for each single failure. The re-routed traffic is then analyzed and alternate Label Switched Paths (LSPs) are identified for such traffic trunks so that the traffic is directed to the alternate LSPs during the single failure event.

Claims

1. A method for routing traffic in a network comprised of a plurality of links to selectively off-load traffic from congested portions of the network to portions that are less congested, comprising:

identifying which of said links are congested determining, for each of said links, that a utilization for the link exceeds a predetermined parameter associated with the link, said predetermined parameter a maximum link utilization, the maximum link utilization associated with all of the links and associated with a bandwidth that is below a maximum capacity of the link;

identifying traffic trunks that contribute to traffic of the identified congested network links;

selecting rerouting traffic trunks where each of the rerouting traffic trunks are traffic trunks that contribute to the traffic of the identified congested network links;

ordering the rerouting traffic bunks in congestion contribution order; and

rerouting portions of the traffic in the rerouting traffic trunks that contribute to the identified congested network links sufficient to reduce said link utilization to a value equal to or below said predetermined parameter.

2. The method of claim 1, wherein the predetermined parameter is a traffic load parameter, the selecting rerouting traffic trunks comprising:

generating a minimum traffic off-load volume Vl, for each of the identified congested network links l=1, 2, 3, . . . L, where L is the total number of congested network links, that brings a traffic load of network link l to below the traffic load parameter.

3. The method of claim 2, wherein the selected rerouting traffic trunk is selected from the identified traffic trunks, starting with a traffic trunk having a greatest volume of traffic contribution to the traffic of the corresponding congested network link.

4. The method of claim 2, further comprising:

a) generating a residue capacity for all the network links of the network after the traffic contribution of the selected rerouting traffic trunk is removed from the corresponding congested network link;

b) generating a modified residue capacity for all the network links based on the residue capacity and traffic contribution of the selected rerouting traffic trunk; and

c) generating a label switching path (LSP) having an LSP residue capacity for the traffic portion of the selected rerouting traffic trunk.

5. The method of claim 4, further comprising:

d) adding the LSP of step c to route the traffic portion of the selected rerouting traffic trunk;

e) adding the LSP residue capacity as added traffic to the network;

f) generating a new residue capacity for all the network links based on the residue capacity and the added traffic;

g) generating another LSP having another LSP residue capacity for another traffic portion of the selected rerouting traffic trunk if the LSP residue capacity is less than the traffic portion of the selected rerouting traffic trunk;

h) repeating steps d-g until either new traffic of the identified congested traffic link is approximately less than or equal to the predetermined parameter, or until a predetermined maximum number of LSPs has been reached;

i) selecting a next traffic trunk from the list and removing a traffic portion contribution of the next traffic trunk that contributes to the corresponding identified congested network link from the network, if the maximum number of LSPs has not been reached; and

j) repeating steps a-i until all traffic of the rerouting traffic trunks have been routed with LSPs or until the maximum number of LPSs has been reached.

6. The method as in claim 5, wherein the LSPs are selected in greatest residue capacity order, the method further comprising:

k) generating a Path node list and a Tent node list for building a path from an ingress node of the selected rerouting traffic trunk to an egressing node of the selected rerouting traffic trunk, wherein the Path comprises;

l) starting a first node set path from the ingress node of the selected ingressing rerouting traffic trunk;

m) finding all nearest neighbor nodes not in the first node set;

n) placing all nearest node neighbors in a second node set ordered based on their maximum modified residue capacity;

o) removing a lead node in the second node set;

p) updating the first node set with the lead node if the lead node is not an egressing node and deleting all nodes with a same node id as the lead node from the second node set;

q) repeating steps m-p until the lead node is an egressing node; and

r) constructing a best path primary LSP from the nodes listed in the first node set.

30. The method according to claim 6, wherein the steps are stored in a memory.

7. A method for routing network traffic of a network, comprising:

generating, in the event of a single network link failure case n=1, 2, . . . k, where k is a number of all the links in the network, a plurality of link utilizations generated based on a first routing technique;

identifying one or more network links as congested by determining that, for each link, a utilization of the link exceeds, a predetermined parameter, wherein the predetermined parameter is a maximum link utilization, the maximum link utilization associated with all of the links and associated with a bandwidth that is below a maximum capacity of the link; and

rerouting portions of the traffic that contribute to the identified congested links sufficient to reduce, for each of the congested links, the link utilization to a value equivalent to or below said predetermined parameter.

8. The method of claim 7, further comprising:

identifying traffic trunks that contribute to traffic of the identified congested network links; and

selecting rerouting traffic trunks where each of the rerouting traffic trunks are traffic trunks that contribute to a non-original traffic of the identified single failure congested network links.

9. The method of claim 8, wherein the predetermined parameter is a traffic load parameter, the selecting rerouting traffic trunks comprising:

generating a minimum non-original traffic off-load volume Vl(n) for each of the identified congested network links l=1, 2, 3, . . . L, where L is the total number of congested network links, that brings the non-original traffic load of network link l to below the traffic load parameter;

generating a list of traffic trunks corresponding to each of the identified congested network links, where each of the traffic in the traffic trunks in the list contributes to the non-original traffic of a corresponding identified congested network link;

selecting a traffic trunk as a rerouting traffic trunk from the list based on its non-original traffic contribution to the traffic of the corresponding congested network; and

rerouting a traffic portion of the selected rerouting traffic trunk that contributes non-original traffic to the corresponding identified congested network link from the network to reduce the congestion of the network.

10. The method of claim 9, wherein the selected rerouting traffic trunk is selected from the list of traffic trunks, starting with a traffic trunk having a greatest volume of non-original traffic contribution to the traffic of the corresponding congested network link.

11. The method of claim 9, further comprising:

a) generating a residue capacity for all the network links of the network after the non-original traffic contribution of the selected rerouting traffic trunk is removed from the corresponding congested network link;

b) generating a modified residue capacity for all the network links based on the residue capacity and non-original traffic contribution of the selected rerouting traffic trunk; and

c) generating a label switching path (LSP) having an LSP residue capacity for the non-original traffic portion of the selected rerouting traffic trunk.

12. The method of claim 11, further comprising:

d) adding the LSP of step c to route the non-original traffic portion of the selected rerouting traffic trunk;

e) adding the LSP residue capacity as added traffic to the network;

f). generating a new residue capacity for all the network links based on the network links'"'"' residue capacity and the added traffic;

g) generating another LSP having another LSP residue capacity for another non-original traffic portion of the selected rerouting traffic trunk if the added LSP residue capacity is less than the non-original traffic portion of the selected rerouting traffic trunk;

h) repeating steps d-g until either traffic of the identified congested traffic link is approximately less than or equal to the predetermined parameter, or until a predetermined maximum number of LSPs has been reached;

i) selecting a next traffic trunk from the list and removing a non-original traffic portion contribution of the next traffic trunk that contributes to the corresponding identified congested network link from the network, if the maximum number of LSPs has not been reached; and

j) repeating steps a-i until all non-original traffic of the rerouting traffic trunks have been routed with LSPs or until the maximum number of LSPs has been reached.

13. The method as in claim 12, wherein the LSPs are selected in greatest residue capacity order, the method further comprising:

k) generating a PATH node list and a TENT node list for building a path from an ingress node of the selected rerouting traffic trunk to an egressing node of the selected rerouting traffic trunk, wherein the PATH comprises;

l) starting a first node set best path from the ingress node of the selected ingressing rerouting traffic trunk;

m) finding all nearest neighbor nodes not in the first node set;

n) placing all nearest node neighbors in a second node set ordered based on their maximum modified residue capacity;

o) removing a lead node in the second node set;

p) updating the first node set with the lead node if the lead node is not an egressing node and deleting all nodes with a same node id as the lead node from the second node set;

q) repeating steps m-p until the lead node is an egressing node; and

r) constructing a best path alternate LSP from the nodes listed in the first node set.

31. The method according to claim 13, wherein the steps are stored in a memory.

14. A multi-protocol label switching (MPLS) device in a network comprising:

a congestion identifying device, wherein the congestion identifying device identifies a congestion of network links by determining that link utilization exceeds a predetermined traffic load parameter, wherein the predetermined traffic load parameter is a maximum link utilization, the maximum link utilization associated with all of the links and associated with a bandwidth that is below a maximum capacity of the link;

a contributing traffic trunk identifying device, wherein the contributing traffic trunk identifying device identifies traffic trunks that contribute to the congestion of the congested network links; and

a LSP selector device, wherein the LSP selector device selects rerouting LSP traffic paths for the identified traffic trunks to reduce the traffic of the congested network links sufficient to reduce link utilization below the predetermined traffic load parameter.

15. The device according to claim 14, wherein the contributing traffic trunk identifying device:

generates a minimum traffic off-load volume V_l, for each of the congested network links l=1, 2, . . . L, where L is the total number of congested network links, that brings a traffic load of a network link l to below the traffic load parameter;

generates a list of traffic trunks corresponding to each of the identified congested network links where each of the traffic trunks in the list contributes to traffic of a corresponding identified congested network link;

selects a traffic trunk from the list based on contribution of the selected traffic trunk to the traffic of the corresponding congested network link as a rerouting traffic trunk; and

removes a traffic portion of the selected rerouting traffic trunk that contributes to the corresponding identified congested network link from the network.

16. The device of claim 15, wherein the contributing traffic trunk identifying device selects a rerouting traffic trunk from the list of traffic trunks, starting with a traffic trunk having a greatest volume of traffic contribution to the traffic of the corresponding congested network link.

17. The device of claim 16, wherein the LSP selector device:

a) generates a residue capacity for all the network links of the network after the traffic contribution of the selected rerouting traffic trunk is removed from the corresponding congested network link;

b) generates a modified residue capacity for all the network links based on the residue capacity and traffic contribution of the selected rerouting traffic trunk; and

c) generates a label switching path (LSP) having an LSP residue capacity or the traffic portion of the selected rerouting traffic trunk.

18. The device of claim 17, wherein the LSP selector device:

d). adds the LSP of step c to route the traffic portion of the selected rerouting traffic trunk;

e) adds the LSP residue capacity as added traffic to the network;

f) generates a new residue capacity for all the network links based on the residue capacity and the added traffic;

g) generates another LSP having another LSP residue capacity for another traffic portion of the selected rerouting traffic trunk if the LSP residue capacity is less than the traffic portion of the selected rerouting traffic trunk;

h) repeats steps d-g until either new traffic of the identified congested traffic link is approximately less than or equal to the predetermined parameter, or until a predetermined maximum number of LSPs has been reached;

i) selects a next traffic trunk from the list and removes a traffic portion contribution of the next traffic trunk that contributes to the corresponding identified congested network link from the network, if the maximum number of LSPs has not been reached; and

j) repeats steps a-i until all traffic of the rerouting traffic trunks have been routed with LSPs or until the maximum number of LSPs has been reached.

19. The device as in claim 18, wherein the LSP selector device selects LSPs in greatest residue capacity order, wherein the LSP selector:

k) generates a PATH node list and a TENT node list for building a path from an ingress node of the selected rerouting traffic trunk to an egressing node of the selected rerouting traffic trunk;

l) starts a first node set path from the ingress node of the selected ingressing rerouting traffic trunk;

m) finds all nearest neighbor nodes not in the first node set;

n) places all nearest node neighbors in a second node set ordered based on their maximum modified residue capacity;

o) removes a lead node in the second node set;

p) updates the first node set with the lead node if the lead node is not an egressing node and deletes all nodes with a same node id as the lead node from the second node set;

q) repeats steps m-p until the lead node is an egressing node; and

r) constructs a best path primary LSP from the nodes listed in the first node set.

28. The device according to claim 19, further comprising:

a configuration template generator that generates a configuration template for building path circuits corresponding to the paths selected by the LSP selector device.

29. The device according to claim 14, wherein the actions of the congestion identifying device, the contributing traffic trunk identifying device and the LSP selector device, are performed by a computer.

20. A device for routing network traffic of a network, comprising:

a congestion identifying device, wherein the congestion identifying device;

generates, in the event of a single network link failure case n=1, 2, . . . k, where k is a number of all the links in the network, a traffic road map generated based on a first routing technique; and

identifies one or more network links as congested, by determining that link utilization exceeds a predetermined traffic load parameter, wherein the predetermined traffic load parameter is a maximum link utilization, the maximum link utilization associated with all of the links and associated with a bandwidth that is below a maximum capacity of the link; and

a LSP selector device, wherein the LSP selector device reroutes portions of the traffic that contribute to the identified congested links sufficient to reduce link utilization below said predetermined traffic load parameter.

21. The device of claim 20, wherein the congestion identifying device:

identifies traffic trunks that contribute to traffic of the identified congested network links; and

the LSP selector device selects rerouting traffic trunks where each of the rerouting traffic trunks contributes to a non-original traffic of the identified congested network links.

22. The device of claim 21, wherein the predetermined parameter is a traffic load parameter, and wherein the congestion identifying device:

generates a minimum non-original traffic off-load volume Vl(n) for each of the identified congested network links l=1, 2, 3, . . . L, where L is the total number of congested network links, that brings the non-original traffic load of network link l to below the traffic load parameter;

generates a list of traffic trunks corresponding to each of the identified congested network links, where each of the traffic trunks in the list contributes to the non-original traffic of a corresponding identified congested network link;

selects a traffic trunk from the list based on its non-original traffic contribution to the traffic of the corresponding congested network link as a rerouting traffic trunk; and

removes a traffic portion of the selected rerouting traffic trunk that contributes non-original traffic to the corresponding identified congested network link from the network.

23. The device of claim 22, wherein the selected rerouting traffic trunk is selected from the list of traffic trunks, starting with a traffic trunk having a greatest volume of non-original traffic contribution to the traffic of the corresponding congested network link.

24. The device of claim 22, wherein the LSP selector device:

a) generates a residue capacity for all the network links of the network after the non-original traffic contribution of the selected rerouting traffic trunk is removed from the corresponding congested network link;

b) generates a modified residue capacity for all the network links based on the residue capacity and non-original traffic contribution of the selected rerouting traffic trunk; and

c) generates a label switching path (LSP) having an LSP residue capacity for the non-original traffic portion of the selected rerouting traffic trunk.

25. The device of claim 24 wherein the LSP selector device:

d) adds the LSP of step c to route the non-original traffic portion of the selected rerouting traffic trunk;

e) adds the LSP residue capacity as added traffic to the network;

f) generates a new residue capacity for all the network links based on the network links'"'"' residue capacity and the added traffic;

g) generates another LSP having another LSP residue capacity for another non-original traffic portion of the selected rerouting traffic trunk if the added LSP residue capacity is less than the non-original traffic portion of the selected rerouting traffic trunk;

h) repeats steps d-g until either traffic of the identified congested traffic link is approximately less than or equal to the predetermined parameter, or until a predetermined maximum number of LSPs has been reached;

i) selects a next traffic trunk from the list and removes a non-original traffic portion contribution of the next traffic trunk that contributes to the corresponding identified congested network link from the network, if the maximum number of LSPs has not been reached; and

j) repeats steps a-i until all non-original traffic of the rerouting traffic trunks have been routed with LSPs or until the maximum number of LPSs has been reached.

26. The device as in claim 25, wherein LSP selector device selects the LSPs in greatest residue capacity order and:

k) generates a PATH node list and a TENT node list for building a path from an ingress node of the selected rerouting traffic trunk to an egressing node of the selected rerouting traffic;

l) starts a first node set path from the ingress node of the selected ingressing rerouting traffic trunk;

m) finds all nearest neighbor nodes not in the first node set;

n) places all nearest node neighbors in a second node set ordered based on their maximum modified residue capacity;

o) removes a lead node in the second node set;

p) updates the first node set with the lead node if the lead node is not an egressing node and deletes all nodes with a same node id as the lead node from the second node set;

q) repeats steps m-p until the lead node is an egressing node; and

r) constructs a best path alternate LSP from the nodes listed in the first node set.

27. The device according to claim 26, wherein the LSP selector device generates alternate LSPs, wherein the alternate LSPs do not include a path in a primary LSP.