Route selection for path balancing in connection-oriented packet switching networks

• US 6,195,354 B1
• Filed: 07/16/1997
• Issued: 02/27/2001
• Est. Priority Date: 07/16/1997
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Matas, Yair, Ashwood-Smith, Peter J., Fedyk, Donald W., Skalecki, Darek Robert
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Pizarro, Ricardo M.
• Application Number:
  US08/895,589
• Time in Patent Office: 1,322 Days
• Field of Search: 370/394, 370/395, 370/396, 370/397, 370/400, 370/237, 370/468, 370/218, 370/216, 370/232
• US Class Current: 370/395.32
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• 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/22 Alternate routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

In a methodology for route selection for path balancing in a connection-oriented packet switching network, a comparison is made of the measures of utilizations of a network resource by at least two links of a link group in the network, and at least one link is identified as a candidate for carrying traffic path based on the comparison. Network traffic path on the link is then moved to the candidate link to reduce variation in the utilization of the network resource by each of the links.

Claims

1. In a connection-oriented packet switching network including a plurality of switching nodes interconnected by a plurality of link groups, each link group including a plurality of links for carrying traffic paths, a method for distributing the traffic paths among the links of a group comprising the steps of:

measuring utilization of a network resource by a first one of the links of a group currently carrying a traffic path and by a second one of the links of the group;

comparing the measures of the utilizations of the network resource by the first one of the links and the second one of the links;

identifying one of the first or second links as a candidate for carrying the traffic path based on the comparison;

moving the traffic path to a candidate link such that the move reduces variation in the utilization of the network resource by each of the links in the group.

2. The method of claim 1 wherein the step of comparing includes the substeps of determining a first difference between a current network resource utilization by the first link and a current network resource utilization by the second link;

and

determining a second difference between a projected network resource utilization by the first link and a projected network resource utilization by the second link.

3. The method of claim 2 wherein the step of comparing further includes the substeps of comparing the first and second differences;

and identifying one of the links as a candidate if the difference between the current network resource utilizations for the links exceeds the difference between the projected network resource utilizations for the links.

4. The method of claim 3 wherein the substep of determining the second difference in the projected network resource utilization by each link includes the substep of determining what the resource utilization by each link would be after a proposed redistribution of network traffic.

5. The method of claim 4 wherein the step of comparing a measure of the utilization of a network resource includes the substep of comparing at least one of bandwidths, CPU, or memory.

6. The method of claim 1 wherein the step of comparing includes the step of comparing a measure of an average utilization of a network resource by the first one of the links with a measure of an average utilization of the network resource by the second one of the links.

10. The method of claim 1 further comprising the steps of:

comparing projected network resource utilizations of all candidates when a plurality of links are identified as candidates for carrying the traffic path; and

identifying one of the candidates as a preferred link for carrying the traffic path based on the comparison of projected network resource utilizations.

11. The method of claim 6 further comprising the steps of:

comparing projected network resource utilizations of all candidates when a plurality of links are identified as candidates for carrying the traffic path; and

identifying one of the candidates as a preferred link for carrying the traffic path based on the comparison of projected network resource utilizations.

12. The method of claim 2 wherein the substep of determining the difference in current network resource utilization by each link includes the substep of dividing a total current utilization of the resource by the link by a total potential utilization of the resource by the link, and

wherein the substep of determining the difference in projected network resource utilization by each link includes the substep of dividing what the utilization of the resource by the link would be after a proposed redistribution of network traffic by the total potential utilization of the resource by the link.

14. The method of claim 1 further comprising the step of transmitting a gather packet to a switching node, the gather packet containing information identifying the candidate links.

15. The method of claim 10 further comprising the step of transmitting a gather packet to a switching node, the gather packet containing information identifying the preferred link.

7. In a connection-oriented packet switching network including a plurality of switching nodes interconnected by a plurality of link groups each including a plurality of links for carrying traffic paths, a method for distributing the traffic paths among the links comprising the steps of:

measuring utilization of a network resource by a first one of the links of a group currently carrying a traffic path and by a second one of the links of the group;

comparing the measures of the utilizations of the network resource by the first one of the links and the second one of the links, including determining a first difference between a current network resource utilization by the first link and a current network resource utilization by the second link and determining a second difference between a projected network resource utilization by the first link and a projected network resource utilization by the second link;

determining whether the difference between the current network resource utilizations for the links exceeds the difference between the projected network resource utilizations for the links;

comparing a measure of an average utilization of a network resource by a first link of a group with a measure of an average utilization of the network resource by a second link of the group if the difference of current utilizations does not exceed the difference in projected utilizations;

identifying candidate links for carrying the traffic path, links for which the difference between the current network resource utilizations exceeds the difference between the projected network resource utilizations; and

moving the traffic path to one of the candidate links.

8. The method of claim 7 wherein the step of comparing the measures of the average utilizations includes the substeps of determining a difference between a current average network resource utilization by the first link and a current average network resource utilization by the second link;

and determining a difference between a projected average network resource utilization by the first link and a projected average network resource utilization by the second link.

9. The method of claim 8 including the step of identifying a link as a candidate if both the difference between the current network resource utilizations for the links equals the difference between the projected network resource utilizations by the links and the difference between the current average network resource utilizations by the links exceeds the difference between the projected average network resource utilizations by the links.

13. The method of claim 7 wherein the substep of comparing a measure of average utilization of the network resource by each link includes the substep of dividing a total current utilization of the resource by the link by the number of traffic paths on the link.

16. In a connection-oriented packet switching network including a plurality of switching nodes interconnected by a plurality of link groups, each group including a plurality of links for carrying traffic paths, a method for distributing the traffic paths among the links comprising the steps of:

measuring utilization of a network resource by the link currently carrying the traffic path and by all other links in the group;

comparing the measures of the utilizations of the network resource by the link currently carrying a traffic path the other links in the group;

identifying one link as a candidate for carrying the traffic path based on the comparison; and

moving the network traffic path from the link currently carrying the path to the link identified as the candidate link thereby reducing variation in the utilization of the network resource between the links in the group.

17. In a connection-oriented packet switching network including a plurality of switching nodes interconnected by a plurality of link groups, each including a plurality of links for carrying traffic paths, an apparatus for distributing the traffic paths among the links, comprising:

means for comparing measures of utilizations of a network resource by a first one of the links of a group currently carrying a traffic path and by a second one of the links of the group; and

means for identifying one of the first or second links as a candidate for carrying the traffic path based on the comparison of the measures of the utilizations.

18. The apparatus of claim 17 wherein

the means for identifying includes means for identifying all candidate links for carrying the traffic path,

and wherein the apparatus comprises means for moving the traffic path to a candidate link.

19. The apparatus of claim 18 wherein the means for comparing includes means for determining a first difference between a current network resource utilization by the first link and a current network resource utilization by the second link;

and

means for determining a second difference between a projected network resource utilization by the first link and a projected network resource utilization by the second link.

20. The apparatus of claim 19 wherein the means for comparing further includes means for comparing the first and second differences;

and means for identifying one of the links being identified as a candidate if the difference between the current network utilizations for the links exceeds the difference between the projected network resource utilizations for the links.

21. The apparatus of claim 20 wherein the means for determining a second difference in the projected network resource utilization by each link includes means for determining what the utilization by each link would be after a proposed redistribution of network traffic.

22. The apparatus of claim 21 wherein the means for comparing includes means for comparing at least one of bandwidths, CPU, or memory.

23. The apparatus of claim 18 wherein the means for comparing includes means for comparing a measure of an average utilization of a network resource by a first link of a group with a measure of an average utilization of the network resource by a second link of the group.

24. The apparatus of claim 20 wherein the means for comparing the differences includes means for determining whether the current network resource utilizations for the links exceeds the difference between the projected network resource utilizations for the links;

and means for comparing a measure of an average utilization of a network resource by a first link of a group with a measure of an average utilization of the network resource by a second link of the group if the difference of current utilizations does not exceed the difference in projected utilizations.

25. The apparatus of claim 24 wherein the means for comparing the measures of the average utilizations includes means for determining a difference between a current average network resource utilization by the first link and a current average network resource utilization by the second link;

and means for determining a difference between a projected average network resource utilization by the first link and a projected average network resource utilization by the second link.

26. The apparatus of claim 25 including means for identifying a link as a candidate if both the difference between the current network resource utilizations for the links equals the difference between the projected network resource utilizations by the links and the difference between the current average network resource utilizations by the links exceeds the difference between the projected average network resource utilizations by the links.

27. The apparatus of claim 18 further comprising:

means for comparing projected network resource utilizations of all candidates when a plurality of links are identified as candidates for carrying the traffic path; and

means for identifying one of the candidates as a preferred link for carrying the traffic path based on the comparison of projected network resource utilizations.

28. The apparatus of claim 23 further comprising:

means for comparing projected network resource utilizations of all candidates when a plurality of links are identified as candidates for carrying the traffic path; and

means for identifying one of the candidates as a preferred link for carrying the traffic path based on the comparison of projected network resource utilizations.

29. The apparatus of claim 19 wherein the means for determining the difference in current network resource utilization by each link includes means for dividing a total current utilization of the resource by the link by a total potential utilization of the resource by the link, and

wherein the means for determining the difference in projected network resource utilization by each link includes means for dividing what the utilization of the resource by the link would be after a proposed redistribution of network traffic by the total potential utilization of the resource by the link.

30. The apparatus of claim 24 wherein the means for comparing a measure of average utilization of the network resource by each link includes means for dividing a total current utilization of the resource by the link by the number of traffic paths on the link.

31. The apparatus of claim 17 further comprising means for transmitting a gather packet to a switching node, the gather packet containing information identifying the candidate links.

32. The apparatus of claim 27 further comprising means for transmitting a gather packet to a switching node, the gather packet containing information identifying the preferred link.

33. In a connection-oriented packet switching network including a plurality of switching nodes interconnected by a plurality of link groups, each group including a plurality of links for carrying traffic paths, an apparatus for distributing the traffic paths among the links comprising:

means for comparing measures of utilizations of a network resource by the link currently carrying a traffic path and by all other links in the group;

means for identifying one link as a candidate for carrying the traffic path based on the comparison; and

means for moving the network traffic path from the link currently carrying the path to the link identified as the candidate link thereby reducing variation in the utilization of the network resource between the links in the group.

34. A connection-oriented packet switching network comprising:

a plurality of link groups, each group including a plurality of links for carrying traffic paths; and

a plurality of switching nodes interconnected by the link groups, each switching node including;

means for comparing measures of utilizations of a network resource by a first link of a group currently carrying a traffic path and by a second link of the group, and

means for identifying one of the first or second links as a candidate for carrying the traffic path based on the comparison.

35. The network of claim 34 wherein the means for identifying includes means for identifying all candidate links for carrying the traffic path, the switching node further comprising

means for moving the traffic path to a candidate link such that the move reduces variation in the utilization of the network resource by each of the links in the group.

36. The network of claim 34 wherein the means for comparing further includes means for determining a first difference between a current network resource utilization by the first link and a current network resource utilization by the second link;

and means for determining a second difference between a projected network resource utilization by the first link and a projected network resource utilization by the second link.

37. The network of claim 36, each switching node further including means for comparing the first and second differences;

and means for identifying one of the links as a candidate if the difference between the current network utilizations for the links exceeds the difference between the projected network resource utilizations for the links.

38. The network of claim 34 wherein the means for comparing further includes means for comparing a measure of an average utilization of a network resource by a first link of a group with a measure of the average utilization of the network resource by a second link of the group.

39. A connection-oriented packet switching network comprising:

a plurality of link groups, each group including a plurality of links for carrying traffic paths;

a plurality of switching nodes interconnected by the link groups, each switching node including;

means for comparing measures of utilizations of a network resource by the link currently carrying the traffic path and by all other links in the group,

means for identifying one as a candidate for carrying the traffic path based on the comparison, and

means for moving the network the traffic path from the link currently carrying the traffic path to the link identified as the candidate thereby reducing variation in the utilization of the network resource between the links in the group.