# US 7,613,110 B1 · Combining multilink and IP per-destination load balancing over a multilink bundle

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,613,110 B1
- Document ID: US7613110B1
- Status: Granted
- Kind: B1
- Application number: 10/892,608
- Filed: 2004-07-15
- Granted: 2009-11-03
- Earliest claimed: 2000-05-17
- Assignees: Cisco Technology, Inc.
- Inventors: Dana Blair
- Web page: https://patentgrep.com/patent/US7613110B1

## CPC

- H04L 47/2416: Real-time traffic
- H04L 45/245: {Link aggregation, e.g. trunking}
- H04L 45/302: Route determination based on requested QoS
- H04L 45/306: {Route determination based on the nature of the carried application}
- H04L 45/38: {Flow based routing}
- H04L 47/10: Flow control; Congestion control
- H04L 47/125: by balancing the load, e.g. traffic engineering
- H04L 47/17: Interaction among intermediate nodes, e.g. hop by hop
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/283: in response to processing delays, e.g. caused by jitter or round trip time [RTT]
- H04L 47/36: by determining packet size, e.g. maximum transfer unit [MTU]
- Y02D 30/50: in wire-line communication networks, e.g. low power modes or reduced link rate
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## 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

### Claim 1

A storage device or memory storing one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform steps comprising:
at a first network device, segregating received packets of best efforts traffic from received packets of one or more delay-sensitive flows;
performing multilink processing for the best efforts traffic;
wherein performing the multilink processing comprises:
fragmenting a plurality of the packets of the best efforts traffic into fragments;
encapsulating the fragments for transmission and adding fragment sequence numbers to headers of the encapsulated fragments; and
transmitting the encapsulated fragments from the packets of the best efforts traffic over multiple communication links of a bundle of data communication links;
wherein the bundle of data communication links is operable to connect the first network device to a second network device;
performing per-flow load balancing for the one or more delay-sensitive flows;
wherein performing the per-flow load balancing includes:
encapsulating the packets of the one or more delay-sensitive flows for transmission without adding fragment sequence numbers to headers of the encapsulated packets;
assigning each packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, to a single communication link of the bundle of data communication links, wherein the single communication link for the particular delay-sensitive flow is determined at least in part by hashing header information from the packet; and
transmitting the encapsulated packets of the particular delay-sensitive flow over the single communication link by interleaving the encapsulated packets between those encapsulated fragments from the packets of the best efforts traffic that are transmitted on the single communication link.

### Claim 2 (depends on 1)

The storage device or memory as in claim 1, wherein the one or more sequences of instructions further comprise instructions, wherein execution of the instructions by the one or more processors causes the one or more processors to perform:
prior to the segregating, a classifier receiving a stream of data packets intended for transport.

### Claim 3 (depends on 1)

The storage device or memory as in claim 1, wherein the instructions that cause the one or more processors to perform per-flow load balancing further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
for each packet of at least one of the delay-sensitive flows, calculating a hash value from predetermined packet header data.

### Claim 4 (depends on 1)

The storage device or memory as in claim 1, wherein the instructions that cause the one or more processors to perform per-flow load balancing further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
for each packet of a first one of the delay-sensitive flows, calculating a first hash value from predetermined packet header data; and
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.

### Claim 5 (depends on 1)

The storage device or memory as in claim 1, wherein the instructions that cause the one or more processors to perform per-flow load balancing further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
for each packet of at least one of the delay-sensitive flows, calculating a hash value from predetermined packet header data; and
assigning each packet for the at least one of the delay-sensitive flows to one of the bundle of data communication links as a function of the hash value.

### Claim 6 (depends on 1)

The storage device or memory as in claim 1, wherein the instructions that cause the one or more processors to perform per-flow load balancing further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
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 one of the delay-sensitive flows to a first one of the bundle of data communication links as a function of the first hash value; and
assigning each packet for the second delay-sensitive flow to a second one of the bundle of data communication links as a function of the second hash value.

### Claim 7 (depends on 1)

The storage device or memory as in claim 1, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
transmitting the encapsulated packets of a first one of the delay sensitive flows and of a second one of delay-sensitive flows over assigned first and second data communication links interleaved together with those encapsulated fragments of the packets of the best efforts traffic that are transmitted on the first and second data communication links.

### Claim 8 (depends on 1)

The storage device or memory as in claim 1, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
transmitting the best efforts traffic and the one or more delay-sensitive flows including at least interleaving the best efforts traffic with the one or more delay-sensitive flows.

### Claim 9

An apparatus comprising:
means for segregating received packets of best efforts traffic from received packets of one or more delay-sensitive flows;
means for performing multilink processing for the best efforts traffic;
wherein the means for performing multilink processing comprise:
means for fragmenting a plurality of the packets of the best efforts traffic into fragments;
means for encapsulating the fragments for transmission and adding fragment sequence numbers to headers of the encapsulated fragments; and
means for transmitting the encapsulated fragments from the packets of the best efforts traffic over multiple communication links of a bundle of data communication links;
wherein the bundle of data communication links is operable to connect the apparatus to a network device;
means for performing per-flow load balancing for the one or more delay-sensitive flows;
wherein the means for performing per-flow load balancing include:
means for encapsulating the packets of the one or more delay-sensitive flows for transmission without adding fragment sequence numbers to headers of the encapsulated packets;
means for assigning each packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, to a single communication link of the bundle of data communication links, wherein the single communication link for the particular delay-sensitive flow is determined at least in part by hashing header information from the packet; and
means for transmitting the encapsulated packets of the particular delay-sensitive flow over the single communication link by interleaving the encapsulated packets between those encapsulated fragments from the packets of the best efforts traffic that are transmitted on the single communication link.

### Claim 10

A system comprising a set of components that is configured to:
distinguish received packets of best efforts traffic from received packets of one or more delay-sensitive flows;
segregate the received packets of the best efforts traffic from the received packets of the one or more delay-sensitive flows;
perform multilink processing for the best efforts traffic;
wherein a first component that is configured to perform the multilink processing is further configured to:
fragment a plurality of the packets of the best efforts traffic into fragments;
encapsulate the fragments for transmission and add fragment sequence numbers to headers of the encapsulated fragments; and
transmit the encapsulated fragments from the packets of the best efforts traffic over multiple communication links of a bundle of data communication links;
wherein the bundle of data communication links is operable to connect the system to a network device;
perform per-flow load balancing for the one or more delay-sensitive flows;
wherein a second component that is configured to perform the per-flow load balancing is further configured to:
encapsulate the packets of the one or more delay-sensitive flows for transmission without adding fragment sequence numbers to headers of the encapsulated packets;
assign each packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, to a single communication link of the bundle of data communication links, wherein the single communication link for the particular delay-sensitive flow is determined at least in part by hashing header information from the packet; and
transmit the encapsulated packets of the particular delay-sensitive flow over the single communication link by interleaving the encapsulated packets between those encapsulated fragments from the packets of the best efforts traffic that are transmitted on the single communication link.

### Claim 11 (depends on 10)

The system as in claim 10, wherein the set of components includes at least
a classifier configured to receive a stream of data packets intended for transport.

### Claim 12 (depends on 10)

The system as in claim 10, wherein the second component is further configured to:
for each packet of at least one of the delay-sensitive flows, calculate a hash value from predetermined packet header data.

### Claim 13 (depends on 10)

The system as in claim 10, wherein the second component is further configured to:
for each packet of a first one of the delay-sensitive flows, calculate a first hash value from predetermined packet header data; and
for each packet of a second one of the delay-sensitive flows, calculate a second hash value from predetermined packet header data, the second hash value differing from the first hash value.

### Claim 14 (depends on 10)

The system as in claim 10, wherein the second component is further configured to:
for each packet of at least one of the delay-sensitive flows, calculate a hash value from predetermined packet header data; and
assign each packet for the at least one of the delay-sensitive flows to one of the bundle of data communication links as a function of the first hash value.

### Claim 15 (depends on 10)

The system as in claim 10, wherein the second component is further configured to:
for each packet of a first one of the delay-sensitive flows, calculate a first hash value from predetermined packet header data;
for each packet of a second one of the delay-sensitive flows, calculate a second hash value from predetermined packet header data, the second hash value differing from the first hash value;
assign each packet for the first one of the delay-sensitive flows to a first one of the bundle of data communication links as a function of the first hash value; and
assign each packet for the second delay-sensitive flow to a second one of the bundle of data communication links as a function of the second hash value.

### Claim 16 (depends on 10)

The system as in claim 10, wherein the set of components is further configured to:
transmit the encapsulated packets of a first one of the delay sensitive flows and of a second one of the delay-sensitive flows over assigned first and second data communication links interleaved together with those fragments of the packets of the best efforts traffic that are transmitted on the first and second data communication links.

### Claim 17 (depends on 10)

The system as in claim 10, wherein the set of components is further configured to:
transmit the best efforts traffic and the one or more delay-sensitive flows by interleaving the best efforts traffic with the one or more delay-sensitive flows.

### Claim 18

A method comprising:
at a first network device, distinguishing received packets of best efforts traffic from received packets of one or more delay-sensitive flows;
at the first network device, segregating the received packets of the best efforts traffic from the received packets of the one or more delay-sensitive flows;
at the first network device, performing multilink processing for the best efforts traffic;
wherein performing the multilink processing comprises:
fragmenting a plurality of the packets of the best efforts traffic into fragments;
encapsulating the fragments for transmission and adding fragment sequence numbers to headers of the encapsulated fragments; and
transmitting the encapsulated fragments from the packets of the best efforts traffic over multiple communication links of a bundle of data communication links;
wherein the bundle of data communication links connects the first network device to a second network device;
at the first network device, performing per-flow load balancing for the one or more delay-sensitive flows;
wherein performing the per-flow load balancing includes:
encapsulating the packets of the one or more delay-sensitive flows for transmission without adding fragment sequence numbers to headers of the encapsulated packets;
assigning each packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, to a single communication link of the bundle of data communication links, wherein the single communication link for the particular delay-sensitive flow is determined at least in part by hashing header information from the packet; and
transmitting the encapsulated packets of the particular delay-sensitive flow over the single communication link by interleaving the encapsulated packets between those encapsulated fragments from the packets of the best efforts traffic that are transmitted on the single communication link.

### Claim 19 (depends on 18)

The method as in claim 18, wherein the distinguishing includes at least
a classifier receiving a stream of data packets intended for transport.

### Claim 20 (depends on 18)

The method as in claim 18, wherein performing the per-flow load balancing further comprises:
for each packet of at least one of the delay-sensitive flows, calculating a hash value from predetermined packet header data.

### Claim 21 (depends on 18)

The method as in claim 18, wherein performing the per-flow load balancing further comprises:
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.

### Claim 22 (depends on 18)

The method as in claim 18, wherein performing the per-flow load balancing further comprises:
for each packet of at least one of the delay-sensitive flows, calculating a hash value from predetermined packet header data; and
assigning each packet for the at least one of the delay-sensitive flows to one of the bundle of data communication links as a function of the hash value.

### Claim 23 (depends on 18)

The method as in claim 18, wherein performing the per-flow load balancing further comprises:
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 one of the delay-sensitive flows to a first one of the bundle of data communication links as a function of the first hash value; and
assigning each packet for the second delay-sensitive flow to a second one of the bundle of data communication links as a function of the second hash value.

### Claim 24 (depends on 18)

The method as in claim 18, further comprising:
transmitting the encapsulated packets of a first one of the delay sensitive flows and of a second one of the delay-sensitive flows over assigned first and second data communication links interleaved together with those fragments of the packets of the best efforts traffic that are transmitted on the first and second data communication links.

### Claim 25 (depends on 18)

The method as in claim 18, further comprising:
transmitting the best efforts traffic and the one or more delay-sensitive flows including at least interleaving the best efforts traffic with the one or more delay-sensitive flows.

### Claim 26

A method comprising:
at a first network device, receiving over a bundle of data communication links encapsulated fragments of packets of best efforts traffic and encapsulated packets of one or more delay-sensitive flows;
wherein the bundle of data communication links connects the first network device to a second network device;
wherein each encapsulated packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, is received on a single communication link of the bundle of data communication links, wherein said each encapsulated packet is interleaved between those encapsulated fragments of the packets of the best efforts traffic that are transmitted on the single communication link;
at the first network device, de-interleaving the received encapsulated fragments of the packets of the best efforts traffic from the received encapsulated packets of the one or more delay-sensitive flows;
at the first network device, performing multilink processing for the best efforts traffic;
wherein performing the multilink processing comprises:
de-encapsulating the encapsulated fragments of the packets of the best efforts traffic; and
performing a reassembly operation to reconstruct the packets of the best efforts traffic from the fragments of the packets based at least in part on fragment sequence numbers that are included in headers of the encapsulated fragments; and
at the first network device, performing point-to-point processing for the one or more delay-sensitive flows;
wherein performing the point-to-point processing includes:
de-encapsulating the encapsulated packets of the particular delay-sensitive flow that are received over the single communication link, wherein headers of the encapsulated packets do not include fragment sequence numbers; and
recovering the packets of the particular delay-sensitive flow without reordering the encapsulated packets of the particular delay-sensitive flow.

### Claim 27 (depends on 26)

The method as in claim 26, further comprising:
distinguishing between the received encapsulated fragments of the packets of the best efforts traffic from the received encapsulated packets of the one or more delay-sensitive flows, wherein the received encapsulated fragments of the packets of the best efforts traffic and the received encapsulated packets of the one or more delay-sensitive flows are interleaved.

### Claim 28 (depends on 26)

The method as in claim 26, wherein:
performing the multilink processing comprises supplying the packets of the best efforts traffic to a routing element.

### Claim 29 (depends on 26)

The method as in claim 26, wherein performing the multilink processing includes reordering the received fragments of the packets of the best efforts traffic.

### Claim 30 (depends on 26)

The method as in claim 26, further comprising:
supplying the packets from the one or more delay-sensitive flows and the packets from the best efforts traffic to a routing element of the first network device; and
the routing element routing the packets from the one or more delay-sensitive flows and the packets from the best efforts traffic to a third network device.

### Claim 31

A system including at least a set of components that is configured to:
receive over a bundle of data communication links encapsulated fragments of packets of best efforts traffic and encapsulated packets of one or more delay-sensitive flows;
wherein the bundle of data communication links is operable to connect the system to a network device;
wherein each encapsulated packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, is received on a single communication link of the bundle of data communication links, wherein said each encapsulated packet is interleaved between those encapsulated fragments of the packets of the best efforts traffic that are transmitted on the single communication link;
de-interleave the received encapsulated fragments of the packets of the best efforts traffic from the received encapsulated packets of the one or more individual delay-sensitive flows;
perform multilink processing for the best efforts traffic;
wherein a first component that is configured to perform the multilink processing is further configured to:
de-encapsulate the encapsulated fragments of the packets of the best efforts traffic; and
perform a reassembly operation to reconstruct the packets of the best efforts traffic from the fragments of the packets based at least in part on fragment sequence numbers that are included in headers of the encapsulated fragments; and
perform point-to-point processing for the one or more delay-sensitive flows;
wherein a second component that is configured to perform the point-to-point processing is further configured to:
de-encapsulate the encapsulated packets of the particular delay-sensitive flow that are received over the single communication link, wherein headers of the encapsulated packets do not include fragment sequence numbers; and
recover the packets of the particular delay-sensitive flow without reordering the encapsulated packets the particular delay-sensitive flow.

### Claim 32 (depends on 31)

The system as in claim 31, wherein the set of components is further configured to:
distinguish between the received encapsulated fragments of the packets of the best efforts traffic from the received encapsulated packets of the one or more delay-sensitive flows, wherein the received encapsulated fragments of the packets of the best efforts traffic and the received encapsulated packets of the one or more delay-sensitive flows are interleaved.

### Claim 33 (depends on 31)

The system as in claim 31, wherein the first component is further configured to supply the packets of the best efforts traffic to a routing element.

### Claim 34 (depends on 31)

The system as in claim 31, wherein the first component is further operable to reorder the received fragments of the packets of the best efforts traffic.

### Claim 35 (depends on 31)

The system as in claim 31, wherein the set of components is further configured to:
supply the packets from the one or more delay-sensitive flows and the packets from the best efforts traffic to a routing element of the system;
wherein the routing element is configured to route the packets from the one or more delay-sensitive flows and the packets from the best efforts traffic to a network device.

### Claim 36

A storage device or memory storing one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform steps comprising:
at a first network device, receiving over a bundle of data communication links encapsulated fragments of packets of best efforts traffic and encapsulated packets of one or more delay-sensitive flows;
wherein the bundle of data communication links is operable to connect the first network device to a second network device;
wherein each encapsulated packet of a particular delay-sensitive flow, of the one or more delay-sensitive flows, is received on a single communication link of the bundle of data communication links, wherein said each encapsulated packet is interleaved between those encapsulated fragments of the packets of the best efforts traffic that are transmitted on the single communication link;
de-interleaving the received encapsulated fragments of the packets of the best efforts traffic from the received encapsulated packets of the one or more delay-sensitive flows;
performing multilink processing for the best efforts traffic;
wherein performing the multilink processing comprises:
de-encapsulating the encapsulated fragments of the packets of the best efforts traffic; and
performing a reassembly operation to reconstruct the packets of the best efforts traffic from the fragments of the packets based at least in part on fragment sequence numbers that are included in headers of the encapsulated fragments; and
performing point-to-point processing for the one or more delay-sensitive flows;
wherein performing the point-to-point processing includes:
de-encapsulating the encapsulated packets of the particular delay-sensitive flow that are received over the single communication link, wherein headers of the encapsulated packets do not include fragment sequence numbers; and
recovering the packets of the particular delay-sensitive flow without reordering the encapsulated packets of the particular delay-sensitive flow.

### Claim 37 (depends on 36)

The storage device or memory as in claim 36, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
distinguishing between the received encapsulated fragments the of packets of the best efforts traffic from the received encapsulated packets of the one or more delay-sensitive flows, wherein the received encapsulated fragments of the packets of the best efforts traffic and the received encapsulated packets of the one or more delay-sensitive flows are interleaved.

### Claim 38 (depends on 36)

The storage device or memory as in claim 36, wherein the instructions that cause the one or more processors to perform the multilink processing further comprise instructions which, when executed by the one or more processors cause the one or more processors to perform:
supplying the packets of the best efforts traffic to a routing element.

### Claim 39 (depends on 36)

The storage device or memory as in claim 36, wherein the instructions that cause the one or more processors to perform the multilink processing further comprise instructions which, when executed by the one or more processors cause the one or more processors to perform reordering the received fragments of the packets of the best efforts traffic.

### Claim 40 (depends on 36)

The storage device or memory as in claim 36, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:
supplying the packets from the one or more delay-sensitive flows and the packets from the best efforts traffic to a routing element of the first network device; and
the routing element routing the packets from the one or more delay-sensitive flows and the packets from the best efforts traffic to a third network device.