US 7,613,110 B1Granted

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

AssigneeCisco Technology, Inc.

InventorDana Blair

Life of this patent

Estimating the term…

Loading patent…

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.

Claims40

Dependent claims

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.

11 more elements

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.

12 more elements

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.

12 more elements

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.

12 more elements

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.

12 more elements

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.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/892,608Filed 15 Jul 2004 · continuation
Priority: 17 May 2000
Granted: 3 Nov 2009
Term ends: Not estimatedThe source records don’t support an estimate.

Classification14 codes

H04L 47/2416
Traffic characterised by specific attributes, e.g. priority or QoS: real-time traffic
H04L 45/245
Multipath: link aggregation, e.g. trunking
H04L 45/302
Routing or path finding of packets in data switching networks: route determination based on requested QoS
H04L 45/306
Route determination based on requested QoS: route determination based on the nature of the carried application

Family

Application09/574,684Parent of this continuation · filed 17 May 2000
US 6,778,495 B1Parent of this continuation
US 7,613,110 B1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key