Technique for adaptively load balancing connections in multi-link trunks

• US 7,787,370 B1
• Filed: 09/06/2001
• Issued: 08/31/2010
• Est. Priority Date: 09/06/2001
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Felske, Kent, Montuno, Delfin Y., Ouellette, Michel, Aweya, James
• Primary Examiner(s): Ahmed, Salman
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US09/946,736
• Time in Patent Office: 3,281 Days
• Field of Search: 370/229, 370/230, 370/230.2, 370/235, 370/236, 370/412, 370/413, 370/415, 370/468, 370/465, 370/252, 370/253, 709/105, 718/105
• US Class Current: 370/230
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A technique for adaptively load balancing connections in multi-link trunks is disclosed. The present invention provides an adaptive load balancing algorithm that utilizes relative link quality metrics to adjust traffic distribution between links. Link quality metrics may include short-term averages of an observed packet drop rate for each member link in a bundle. The present invention may dynamically adjust the number of flows on each link in proportion to available bandwidth. In addition, link quality metrics may be equalized, such that no link is more lossy than the others.

Claims

1. A method for adaptively load balancing connections in a multi-link trunk in a network having a plurality of network nodes, the method comprising the steps of:

determining at least one relative link quality metric for each link in the multi-link trunk;

detecting an arrival of a connection at a network node;

determining whether to drop an incoming packet at a link queue; and

assigning the connection to a link based on the relative link quality metric of the link;

wherein the step of determining whether to drop an incoming packet at the link queue further comprises the steps of;

computing at least one packet drop probability for each link;

generating a random number for the each link in the multi-link trunk;

comparing the random number to the at least one packet drop probability; and

computing an inter-drop interval for determining an interval at which to drop a packet.

2. The method of claim 1, further comprising the step of:

filtering the packet drop probability.

3. The method of claim 2, further comprising the step of:

computing a link weight for each link.

4. The method of claim 3, further comprising the step of:

normalizing each link weight for each link.

5. The method of claim 4, further comprising the step of:

determining a probability range for each link.

6. The method of claim 1, wherein the step of assigning the connection to the link comprises the steps of:

associating each random number to a link; and

sending the connection to the link.

7. The method of claim 1, wherein the random number is associated with one of a plurality of availability subintervals of availability values.

12. At least one non-transitory computer readable storage medium storing a computer program of instructions configured to be readable by at least one processor for instructing the at least one processor to execute a computer process for performing the method as recited in claim 1.

8. An apparatus for adaptively load balancing connections in a multi-link trunk in a network having a plurality of network nodes, the apparatus comprising:

a queue management algorithm for determining at least one relative link quality metric for each link in the multi-link trunk;

a detector for detecting an arrival of a connection at a network node and determining whether to drop an incoming packet at a link queue; and

a load balancing algorithm for assigning the connection to a link based on the relative link quality metric of the link;

wherein the detector further provides for computing at least one packet drop probability for each link;

generating a random number for the each link in the multi-link trunk; and

comparing the random number to the at least one packet drop probability; and

further computes an inter-drop interval for determining an interval at which to drop a packet.

9. The apparatus of claim 8, further comprising:

a filter for filtering the packet drop probability;

a link weight computer for computing a link weight for each link;

a normalizer for normalizing each link weight for each link; and

a probability range determinator for determining a probability range for each link.

10. The apparatus of claim 8, further comprising:

an associator for associating each random number to a link; and

a sender for sending the connection to the link.

11. The apparatus of claim 8, wherein the random number is associated with one of a plurality of availability subintervals of availability values.

13. An article of manufacture for adaptively load balancing connections in a multi-link trunk in a network having a plurality of network nodes, the article of manufacture comprising:

at least one processor readable storage medium; and

instructions stored on the at least one medium;

wherein the instructions are configured to be readable from the at least one medium by at least one processor and thereby cause the at least one processor to operate so as to;

determine at least one relative link quality metric for each link in the multi-link trunk;

detect an arrival of a connection at a network node;

determine whether to drop an incoming packet at a link queue;

compute at least one packet drop probability for each link;

generate a random number for the each link in the multi-link trunk;

compare the random number to the at least one packet drop probability;

assign the connection to a link based on the relative link quality metric of the link; and

computing an inter-drop interval for determining an interval at which to drop a packet.

14. The article of manufacture of claim 13, wherein the instructions further cause the at least one processor to operate so as to:

filter the packet drop probability;

compute a link weight for each link;

normalize each link weight for each link; and

determine a probability range for each link.

15. The article of manufacture of claim 13, wherein the random number is associated with one of a plurality of availability subintervals of availability values.