Distribution of communication load over multiple paths based upon link utilization

• US 6,084,858 A
• Filed: 01/29/1997
• Issued: 07/04/2000
• Est. Priority Date: 01/29/1997
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Raj, Alex Edward, Matthews, Wallace E., Dev, Roger
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US08/790,467
• Time in Patent Office: 1,252 Days
• Field of Search: 370/238, 370/252, 370/254, 370/255, 370/256, 370/351, 370/389, 370/400, 370/408, 370/237, 395/200, 709/232, 709/234, 709/233, 709/235, 709/238, 709/241, 709/243, 709/244
• US Class Current: 370/238
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth

Abstract

A method for selecting a communication path over which to send a communication load between a first station and a second station in a communication network, in which the communication network has a plurality of possible communication paths between the first and second stations. The method comprises identifying at least one of the possible communication paths between the first and second stations, determining a first path metric for each identified path, the first path metric having a value that may vary as distribution of the load across the network varies and selecting one of the at least one identified paths based on the value of the first path metric for each identified path.

Claims

1. A method of selecting a communication path over which to send a communication load between a first and a second station in a communication network, the communication network having a plurality of possible communication paths between the first and second stations, the method comprising the steps of:

identifying at least one of the possible communication paths between the first and second stations, wherein each of the at least one identified communication paths includes at least one link in the communication network;

determining a first path metric for each identified path, including;

determining a first link metric for each link of each identified path based on usage, an administrative cost, and an intrinsic bandwidth of the respective link; and

combining the first link metrics for each link of the respective identified path; and

selecting one of the at least one identified paths based on the value of the first path metric for each identified path.

2. The method of claim 1, wherein the first link metric for each link of each identified path is proportional to the administrative cost and the usage of the respective link and inversely proportional to the intrinsic bandwidth of the respective link.

3. The method of claim 1, wherein the first link metric for a link e having an administrative cost, cost(e), a usage, usage(e), and an intrinsic bandwidth, intrinsic_-- bandwidth(e), is a function of ##EQU9## .

4. The method of claim 1, wherein the first link metric for a link e having an administrative cost, cost(e), a usage, usage(e), and an intrinsic bandwidth, intrinsic_-- bandwidth(e), is a function of ##EQU10## where K is a constant.

5. The method of claim 1, wherein the first link metric for a link e having an administrative cost, cost(e) and a residual bandwidth, residual_-- bandwidth(e), is a function of ##EQU11## .

6. The method of claim 1, wherein the first link metric for a link e having an administrative cost, cost(e), a used bandwidth, used_-- bandwidth(e), and an intrinsic bandwidth, intrinsic_-- bandwidth(e), is a function of ##EQU12## .

7. The method of claim 1, further comprising a step of determining a second path metric for each identified path, and wherein the step of selecting comprises the step of selecting one of the at least one identified paths based on the value of the first path metric and the second path metric for each identified path.

8. The method of claim 7, wherein the second path metric is not dynamic.

9. The method of claim 7, wherein the step of selecting includes the steps of selecting all of the identified paths having an optimal first path metric and, if more than one optimal path is identified, selecting the identified optimal path having the best value for the second path metric.

10. The method of claim 9, wherein each of the at least one identified communication paths includes at least one link in the communication network and wherein:

the first path metric is based on a first link metric for each link in the respective path; and

the second path metric is based on a second link metric for each link in the respective path.

11. The method of claim 10 wherein:

the first link metric is based upon a usage of the respective link and on a bandwidth for the respective link; and

the second link metric is based on a bandwidth of the respective link.

12. A method of transmitting a communication load between a first and a second station in a connection-oriented communication network, the communication network having a plurality of possible communication paths between the first and second stations, the method comprising the steps of:

(a) defining a connection between the first and the second stations, including;

identifying at least one of the possible communication paths between the first and second stations;

calculating a dynamic first path metric for each identified path, the first path metric having a value responsive to changes of the distribution of communication loads across the network; and

selecting one of the at least one identified paths based on the value of the first path metric for each identified path;

(b) transmitting at least a portion of the communication load on the defined connection;

(c) repeating steps (a) and (b) until the transmission of the communications load is complete or the transmission is terminated.

13. The method of claim 12, wherein the step of calculating includes:

determining a first link metric for each link of each identified path; and

combining the first link metrics for each link of the respective identified path.

14. The method of claim 13, wherein the first link metric for each link of each identified path is based on a total number of connections that are currently defined on the network that include the respective link.

15. The method of claim 14, wherein the first link metric for each link of each identified path is further based on an administrative cost and an intrinsic bandwidth of the respective link.

16. The method of claim 14, wherein step (a) further comprises the step of calculating a second path metric for each identified path, and wherein the step of selecting includes the step of selecting all of the identified paths having an optimal first path metric and, if more than one optimal path is identified, selecting the identified optimal path having the best value for the second path metric.

17. An apparatus for transmitting a communication load between a first and a second station in a connection-oriented communication network, the communication network having a plurality of possible communication paths between the first and second stations, the apparatus comprising:

means for defining a connection between the first and second stations, including;

means for identifying at least one of the possible communication paths between the first and second stations;

means for calculating a dynamic first path metric for each identified path, including means for determining a first link metric for each link of each identified path and means for combining the first link metrics for each link of the respective identified path, wherein the first link metric is based on a total number of connections that are currently defined on the network that include the respective link; and

means for selecting one of the at least one identified paths based on the value of the first path metric for each identified path; and

means for transmitting the communication load on the defined connection.

18. The means of claim 17, wherein the first link metric for each link of each identified path is further based on an administrative cost and an intrinsic bandwidth of the respective link.

19. A method of selecting a communication path over which to send a communication load between a first and a second station in a communication network, the communication network having a plurality of possible communication paths between the first and second stations, the method comprising:

identifying at least one of the possible communication paths between the first and second stations;

calculating a dynamic first path metric for each identified path, the first path metric having a value responsive to changes of the distribution of communication loads across the network; and

selecting one of the at least one identified paths based on the value of the first path metric for each identified path.

20. The method of claim 19, wherein each of the at least one identified communication paths includes at least one link in the communication network and the step of calculating includes:

determining a first link metric for each link of each identified path; and

determining the first path metric for each identified path based on the first link metric for each link of the respective identified path.

21. The method of claim 20, wherein the first link metric is based upon a usage of the respective link.

22. The method of claim 21, wherein the first link metric is proportional to the usage of the respective link.

23. The method of claim 21, wherein the first link metric is further based on a bandwidth for the respective link.

24. The method of claim 23, wherein the first link metric is based on a combination of the usage of the respective link and the bandwidth for the respective link.

25. The method of claim 24, wherein the first link metric is proportional to the usage of the respective link and inversely proportional to the bandwidth of the respective link.

26. The method of claim 21, wherein the first link metric is further based on a cost of the respective link.

27. The method of claim 26, wherein the first link metric is based on a combination of the usage and the cost of the respective link.

28. The method of claim 27, wherein the first link metric is proportional to the usage and the cost of the respective link.

29. The method of claim 19, wherein the communications network is connection oriented.

30. An apparatus for selecting a communication path over which to send a communication load between a first and a second station in a communication network, the communication network having a plurality of possible communication paths between the first and second stations, the apparatus comprising:

means for identifying at least one of the possible communication paths between the first and second stations;

means for calculating a dynamic first path metric for each identified path, the first path metric having a value responsive to changes of the distribution of communication loads across the network; and

means for selecting one of the at least one identified paths based on the value of the first path metric for each identified path.

31. The apparatus of claim 30, wherein each of the at least one identified communication paths includes at least one link in the communication network and the means for calculating includes:

means for determining a first link metric for each link of each identified path; and

means for determining the first path metric for each identified path based on the first link metric for each link of the respective identified path.

32. The apparatus of claim 31, wherein the first link metric is based upon a usage of the respective link.

33. The apparatus of claim 32, wherein the first link metric is proportional to the usage of the respective link.

34. The apparatus of claim 32, wherein the first link metric is further based on a bandwidth for the respective link.

35. The apparatus of claim 34, wherein the first link metric is based on a combination of the usage of the respective link and the bandwidth for the respective link.

36. The apparatus of claim 35, wherein the first link metric is proportional to the usage of the respective link and inversely proportional to the bandwidth of the respective link.

37. The apparatus of claim 32, wherein the first link metric is further based on a cost of the respective link.

38. The apparatus of claim 37, wherein the first link metric is based on a combination of the usage and the assigned cost of the respective link.

39. The apparatus of claim 38, wherein the first link metric is proportional to the usage and the assigned cost of the respective link.

40. The apparatus of claim 30, wherein the communications network is connection oriented.

41. The apparatus of claim 30, wherein the apparatus is a network management server.