Combining multilink and IP per-destination load balancing over a multilink bundle

• US 6,778,495 B1
• Filed: 05/17/2000
• Issued: 08/17/2004
• Est. Priority Date: 05/17/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Blair, Dana
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US09/574,684
• Time in Patent Office: 1,553 Days
• Field of Search: 370/230, 370/231, 370/235, 370/395.32, 370/395.4, 370/395.41, 370/395.42, 370/395.21, 370/471, 370/474
• US Class Current: 370/230
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• 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
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/36 by determining packet size, e.g. maximum transfer unit [MTU]
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Load balanced transport of best efforts traffic together with delay-bounded traffic over a multilink bundle combines fragmentation and fragment distribution for best efforts packets with per-flow balancing for delay-bounded traffic. In the preferred embodiments, the best efforts packets receive Multilink Protocol treatment, including fragmentation and addition of sequence headers. Fragments of packets for one such communication go over the various links within the bundle, as appropriate for load balancing on the links. For each delay-bounded flow, such as for a VOIP service, the sending node hashes the packet header data and applies all packets for the flow to one of the links, assigned as a function of the hash value. Different flow headers produce different hash results; therefore the node sends different flows over the different links in a substantially balanced manner.

Claims

1. A method of load balanced transmission of packets through a bundle of data communication links, the method comprising the steps of:

distinguishing packets for best-efforts service from packets forming a plurality of delay-sensitive flows;

fragmenting a plurality of the packets for best-efforts service;

for each fragmented packet, transmitting the fragments over a plurality of the data communication links of the bundle;

for each packet of a first one of the delay-sensitive flows, calculating a first hash value from predetermined packet header data;

for each packet of a second one of the delay-sensitive flows, calculating a second hash value from predetermined packet header data, the second hash value differing from the first hash value;

assigning each packet for the first delay-sensitive flow to a first one of the data communication links as a function of the first hash value;

assigning each packet for the second delay-sensitive flow to a second one of the data communication links as a function of the second hash value; and

transmitting packets of the first and second delay-sensitive flows over the assigned first and second data communication links interleaved together with the fragments transmitted on the first and second data communication links.

2. A method as in claim 1, wherein the assigning steps directly identify the first and second data communication links from one or more bits of the first and second hash values.

3. A method as in claim 1, wherein the assigning steps associate the first and second hash values with the first and second data communication links, respectively as a function of usage of the first and second data communication links.

4. A method as in claim 3, wherein the function of usage of the first and second data communication links comprises relative levels of existing assignments to the first and second data communication links.

5. A method as in claim 1, wherein the steps of fragmenting and transmitting of fragments conform to the Multilink Protocol.

6. A method as in claim 5, wherein the step of transmitting packets of the first and second delay-sensitive flows conforms to the Point-to-Point Protocol.

7. A method as in claim 1, further comprising assigning the fragments for transmission over the plurality of data communication links in a round-robin fashion.

8. A method as in claim 1, further comprising adding a sequence number to each of the fragments for transmission.

9. A method as in claim 8, wherein the step of transmitting of the packets of the first and second delay-sensitive flows comprises transmitting packets of the first and second delay-sensitive flows without adding any sequence numbers.

10. A transmitting device, for load balanced transmission of packets through a bundle of data communication links, comprising:

a classifier receiving a stream of data packets intended for transport through the bundle for segregating received packets for best-efforts service from received packets forming a plurality of delay-sensitive flows;

a fragmentor coupled to the classifier for fragmenting a plurality of the packets for best-efforts service;

means for calculating a hash value from predetermined data from a header contained in each packet of the plurality of delay-sensitive flows;

link interfaces, each link interface being coupled for transmission of fragments and packets over a data communication link of the bundle; and

a load balancing element for;

1) evenly distributing the fragments of each of the plurality of the packets for best-efforts service to a plurality of the link interfaces for transmission; and

2) distributing the packets of different ones of the delay-sensitive flows to a plurality of the link interfaces for transmission while distributing all packets of each one of the delay-sensitive flows to a single one of the link interfaces for transmission, as a function of the hash values.

11. A device as in claim 10 comprising a packet router.

12. A device as in claim 10, further comprising:

a Multilink Protocol encapsulator for encapsulating the fragments; and

a Point-to-Point Protocol encapsulator for encapsulating the packets of the delay-sensitive flows.

13. A device as in claim 12, wherein:

the Multilink Protocol encapsulator adds a header to each fragment, each header containing a sequence number, and

the Point-to-Point Protocol encapsulator adds no sequence numbers to the packets of the delay-sensitive flows.

14. A device as in claim 10, wherein at least two of the link interfaces provide an equal data rate transmission over respective links coupled thereto.

15. A device for reception of load balanced packet transmissions through a bundle of data communication links carrying fragments of packets of best efforts traffic distributed throughout the links and carrying packets of a plurality of delay-sensitive flows, the packets of each delay-sensitive flow traversing a single one of the data communication links, the device comprising:

a plurality of link interfaces, each link interface being coupled for reception of fragments and packets over one data communication link of the bundle;

a decoder coupled to the link interfaces for segregating received fragments of packets of best efforts traffic from received packets of one or more individual delay-sensitive flows;

a fragment reassembler for reordering fragments received over different links as necessary and reassembling fragments into packets for best-efforts service; and

a packet router, coupled to receive packets from the fragment reassembler, and coupled to receive packets from delay-sensitive flows carried on a plurality of the data communication links from the decoder without any reordering.

16. A device as in claim 15, further comprising:

a Multilink Protocol de-encapsulator for stripping off Multilink Protocol encapsulation data from the fragments; and

a Point-to-Point Protocol de-encapsulator for stripping off Point-to-Point Protocol encapsulation data from the packets of the delay-sensitive flows.

17. A device as in claim 15, wherein at least two of the link interfaces provide an equal data rate reception from respective links coupled thereto.

18. A device as in claim 15, wherein the router comprises an Internet Protocol packet router.

29. The device of claim 15, wherein the packet router is configured to

calculate a first hash value from predetermined packet header data for each packet of a first one of the delay-sensitive flows;

calculate a second hash value from predetermined packet header data for each packet of a second one of the delay-sensitive flows, the second hash value differing from the first hash value;

assign each packet for the first delay-sensitive flow to a first one of the data communication links as a function of the first hash value;

assign each packet for the second delay-sensitive flow to a second one of the data communication links as a function of the second hash value; and

transmit packets of the first and second delay-sensitive flows over the assigned first and second data communication links interleaved together with the fragments transmitted on the first and second data communication links.

19. An apparatus for load balanced transmission of packets through a bundle of data communication links of a packet communication network, comprising:

means for distinguishing packets for best-efforts service from packets forming a plurality of delay-sensitive flows;

means for fragmenting a plurality of the packets for best-efforts service;

means for evenly transmitting the fragments of each fragmented packet over a plurality of the links of the bundle;

means for calculating a first hash value from predetermined packet header data of each packet of a first one of the delay-sensitive flows and calculating a second hash value from predetermined packet header data of each packet of a second one of the delay-sensitive flows, the second hash value differing from the first hash value;

means for assigning each packet for the first and second delay-sensitive flows to respective first and second ones of the links as a function of the first and second hash values; and

link interfaces coupled to the first and second links for transmitting packets of the first and second delay-sensitive flows over the assigned first and second links interleaved together with the fragments transmitted on the first and second links.

20. A computer-readable medium carrying one or more sequences of instructions for load balanced transmission of packets through a bundle of data communication links, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

distinguishing packets for best-efforts service from packets forming a plurality of delay-sensitive flows;

fragmenting a plurality of the packets for best-efforts service;

for each fragmented packet, transmitting the fragments over a plurality of the data communication links of the bundle;

for each packet of a first one of the delay-sensitive flows, calculating a first hash value from predetermined packet header data;

for each packet of a second one of the delay-sensitive flows, calculating a second hash value from predetermined packet header data, the second hash value differing from the first hash value;

assigning each packet for the first delay-sensitive flow to a first one of the data communication links as a function of the first hash value;

assigning each packet for the second delay-sensitive flow to a second one of the data communication links as a function of the second hash value; and

transmitting packets of the first and second delay-sensitive flows over the assigned first and second data communication links interleaved together with the fragments transmitted on the first and second data communication links.

21. A computer-readable medium as in claim 20, wherein the assigning steps directly identify the first and second data communication links from one or more bits of the first and second hash values.

22. A computer-readable medium as in claim 20, wherein the assigning steps associate the first and second hash values with the first and second data communication links, respectively as a function of usage of the first and second data communication links.

23. A computer-readable medium as in claim 22, wherein the function of usage of the first and second data communication links comprises relative levels of existing assignments to the first and second data communication links.

24. A computer-readable medium as in claim 20, wherein the steps of fragmenting and transmitting of fragments conform to the Multilink Protocol.

25. A computer-readable medium as in claim 24, wherein the step of transmitting packets of the first and second delay-sensitive flows conforms to the Point-to-Point Protocol.

26. A computer-readable medium as in claim 20, further comprising assigning the fragments for transmission over the plurality of data communication links in a round-robin fashion.

27. A computer-readable medium as in claim 20, further comprising adding a sequence number to each of the fragments for transmission.

28. A computer-readable medium as in claim 27, wherein the step of transmitting of the packets of the first and second delay-sensitive flows comprises transmitting packets of the first and second delay-sensitive flows without adding any sequence numbers.

30. A system comprising:

a device for reception of load balanced packet transmissions through a bundle of data communication links carrying fragments of packets of best efforts traffic distributed throughout the links and carrying packets of a plurality of delay-sensitive flows, the packets of each delay-sensitive flow traversing a single one of the data communication links, the device including at least

a plurality of link interfaces, each link interface being coupled for reception of fragments and packets over one data communication link of the bundle;

a decoder coupled to the link interfaces for segregating received fragments of packets of best efforts traffic from received packets of one or more individual delay-sensitive flows;

a fragment reassembler for reordering fragments received over different links as necessary and reassembling fragments into packets for best-efforts service; and

a packet router, coupled to receive packets from the fragment reassembler, and coupled to receive packets from delay-sensitive flows carried on a plurality of the data communication links from the decoder without any reordering.

31. A system comprising:

a set of components that is configured to perform

segregating received fragments of packets of best efforts traffic from received packets of one or more individual delay-sensitive flows;

multilink processing for delay sensitive flows; and

per-flow load balancing for best efforts traffic.

32. A method comprising:

segregating received fragments of packets of best efforts traffic from received packets of one or more individual delay-sensitive flows;

performing multilink processing for the delay-sensitive flows; and

performing per-flow load balancing for the best efforts traffic.