Method of maintaining packet order in multipath transmission systems having non-uniform traffic splitting

• US 6,788,686 B1
• Filed: 11/30/1999
• Issued: 09/07/2004
• Est. Priority Date: 11/30/1999
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Krishnan, Santosh, Khotimsky, Denis Andreyevich
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): Volper, Thomas E.
• Application Number:
  US09/451,587
• Time in Patent Office: 1,743 Days
• Field of Search: 370/389, 370/392, 370/393, 370/394, 370/411, 370/437, 370/465, 370/470, 370/471, 370/473, 370/474, 370/475, 370/535, 370/536, 370/537, 370/542, 370/412, 370/415, 370/416
• US Class Current: 370/394
• 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/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method to restore the original order of packets in an end-to-end data flow after the flow has been multiplexed over a set of communication or switching paths whose available bandwidth varies significantly over time. To convey the relative path ordering, the method considers all possible path pairs. For each such path pair it enumerates the packet block transmissions, i.e., the sequences of packets transmitted on a selected path of the given path pair which are not interleaved by the packets transmitted on the other path of the same pair. Packet block enumeration for each path pair is performed independently and does not take into account any packets transmitted on the other paths. A packet transmitted on a given path carries a set of packet block identifications for each path pair the given path belongs to. Increasing the range of the packet block enumeration, the robustness of the method can be adjusted to an arbitrary level of packet loss tolerance.

Claims

1. A method of transmitting a packet in a multipath network comprising the steps of:

determining a number of available paths through the network;

selecting a path i from the number of available paths over which to transmit the packet;

determining a set of available paths that have been used for packet transmission since path i was last used;

generating a sequence control header representing the determined set of used available paths; and

transmitting the packet including the generated sequence control header over the selected path i.

2. A method of maintaining packet order between a source and a destination in a multipath network comprising the steps of:

determining a number of available paths through the network;

at the source;

selecting a path i from the number of available paths over which to transmit the packet;

determining a set of available paths that have been used for packet transmission since path i was last used;

generating a sequence control header representing the determined set of used available paths; and

transmitting the packet including the generated sequence control header over the selected path i, at the destination;

enqueuing received packets into separate reassembly queues, one for each available path; and

determining a proper order of the received packets from the sequence control header of the packets contained at the head of the reassembly queues.

3. A method of maintaining packet order in a split flow transmission between a source and a destination in a multipath network comprising the steps of:

determining a number of available paths through the network;

at the source;

selecting a path i from the number of available paths over which to transmit the packet;

determining a set of available paths that have been used for packet transmission since path i was last used;

generating a sequence control header representing the determined set of used available paths; and

transmitting the packet including the generated sequence control header over the selected path i;

at the destination;

enqueuing received packets into separate reassembly queues, one for each available path and each split flow; and

determining a proper order of the received packets pertaining to the same split flow from the sequence control header of the packets contained at the head of the reassembly queues.

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

updating local state information pertaining to each split flow.

5. A method of transmitting a packet in a multipath network comprising the steps of:

determining a number of available paths k through the network;

selecting a path i from the number of available paths k over which to transmit the packet;

determining a set of available paths that have been used for packet transmission since path i was last used;

generating a sequence control header comprising rank components respectively related to each path other than path i; and

transmitting the packet including the generated sequence control header over the selected path i.

6. The method of claim 5, wherein said selecting comprises:

identifying path pairs among the available paths k; and

creating a sequence control state for each flow split and each path pair.

7. The method of claim 6, further comprising establishing a priority path between each path pair.

8. The method of claim 7, wherein said establishing is performed between a transmitter and a receiver.

9. The method of claim 7, wherein a path having a lower ordinal index is a priority path of said path pair.

10. The method of claim 9, wherein the respective rank components comprise:

a respective packet block sequence number; and

said packet block sequence numbers wrap-around in modulo 2^m, wherein m is an integer greater than 1.

11. The method of claim 10, wherein said packet block sequence number is transmitted with each packet.

12. The method of claim 11, wherein a least significant bit of said packet block sequence number is dropped during transmission of a packet.

13. The method of claim 10, wherein the respective rank components comprise k−

1 bits.