Method and apparatus for re-ordering data packets in a network environment

• US 6,246,684 B1
• Filed: 12/24/1997
• Issued: 06/12/2001
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation), Hyundai Electronics Industries Co. Ltd. (SK Hynix Inc.)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Kung, Hsiang-Tsung, Chapman, Alan Stanley John
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US08/998,347
• Time in Patent Office: 1,266 Days
• Field of Search: 370/394, 370/428, 370/252, 370/362, 370/363, 370/412
• US Class Current: 370/394
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The invention provides a method and apparatus for re-ordering data traffic units, such as IP data packets, that may have been miss-ordered during a transmission over a multi-pathway link between a source node and a destination node in a network. The re-ordering apparatus includes a storage medium for intercepting the IP data packets and holding the IP data packets to allow IP data packets delayed on slower pathways to catch-up. The IP data packets in the storage medium are re-ordered based on their sequence number in an attempt to restore the original order of the IP data packets. A maximal time delay variable determines how long a certain IP data packet can be held in the storage medium. The TP data packet is released prior to the maximal time delay variable or as the maximal time delay variable is exceeded.

Claims

1. An apparatus for manipulating data traffic units transmitted in a network to reduce a level of miss-ordering of the data traffic units, said apparatus comprising:

a) an input for receiving a stream of data traffic units in a potentially miss-ordered condition, each data traffic unit being associated to a respective sequence number;

b) a re-ordering queue for receiving the data traffic units;

c) a processing unit in an operative relationship with said re-ordering queue, said processing unit is operative for;

i) reordering the data traffic units in the re-ordering queue on a basis of the sequence number of each data traffic Unit for reducing a level of miss-ordering of the data traffic units;

ii) applying to the data traffic units in the re-ordering queue a first selection operation, the first selection operation being characterized by a minimal time delay variable that defines a minimal residence time of a data traffic unit prior to release of the data traffic unit from said re-ordering queue, the first selection operation being applied to locate a potential data traffic unit having a sequence number indicating that the data traffic unit precedes all the other data traffic units in said re-ordering queue and having a residence time exceeding the minimal time delay variable;

iii) applying to the data traffic units in the re-ordering queue a second selection operation, the second selection operation being characterized by a maximal time delay variable that defines a maximal residence time of a data traffic unit prior to release of the data traffic unit from said re-ordering queue, the second selection operation being applied to locate a potential data traffic unit having a residence time exceeding the maximal time delay variable irrespective of the sequence number of the data traffic unit;

d) an output for releasing data traffic units located by the either one of the first and the second selection operations.

2. An apparatus as defined in claim 1, wherein said processing unit is further operative for increasing the value of the maximal time delay variable.

3. An apparatus as defined in claim 2, wherein said processing unit is further operative for:

a) identifying a missed opportunity in a re-ordering operation of said re-ordering queue to reduce a level of miss-ordering between data traffic units;

b) increasing said maximal time delay variable when a missed opportunity is identified in a).

4. An apparatus as defined in claim 2, wherein said processing unit is further operative for decreasing the value of the maximal time delay variable.

5. An apparatus as defined in claim 4, wherein said processing unit decreases the value of the maximal time delay variable when no missed opportunity of re-ordering is identified during a certain number of data traffic units re-ordering events.

6. An apparatus as defined in claim 1, wherein said processing unit is operative for assessing a variation in delays for propagating data traffic units traveling toward said apparatus over different pathways.

7. An apparatus as defined in claim 6, wherein each data traffic unit is associated to a respective timestamp, each timestamp being indicative of a time data element assigned by a traffic splitting source in a network, said processing unit being operative for:

a) recording for each data traffic unit a time of arrival;

b) reading the timestamp in each data traffic unit;

c) processing for each data traffic unit the time stamp and the recorded time of arrival to compute the variation in delays for propagating data traffic units traveling over different pathways.

8. An apparatus as defined in claim 1, wherein each data traffic unit is associated to a respective address data element, each address data element being indicative of a traffic splitting source in a network through which the data traffic unit has traveled, said apparatus further comprising a set of maximal time delay variables, each maximal time delay variable being associated to a respective address data element thereby allowing a given maximal time delay variable to be associated to a data traffic unit on the basis of said address data element.

9. An apparatus as defined in claim 1, wherein each data traffic unit constitutes an IP data packet.

10. An apparatus as defined in claim 9, wherein each data traffic unit is associated to a respective address data element, each address data element being indicative of a traffic splitting source in a network through which the data traffic unit has traveled.

11. An apparatus as defined in claim 1, wherein said re-ordering queue includes a buffer.

12. A method for manipulating data traffic units transmitted in a network to reduce a level of miss-ordering of the data traffic units, said method comprising:

a) receiving a stream of data traffic units in a potentially miss-ordered condition, each data traffic unit being associated to a respective sequence number;

b) placing the data traffic units in a re-ordering queue;

c) re-ordering the data traffic units in the re-ordering queue on a basis of the sequence number of each data traffic unit for reducing a level of miss-ordering of the data traffic units;

d) applying to the data traffic units in the re-ordering queue a first selection operation, the first selection operation being characterized by a minimal time delay variable that defines a minimal residence time of a data traffic unit prior to release of the data traffic unit from said re-ordering queue, the first selection operation being applied to locate a potential data traffic unit having a sequence number indicating that the data traffic unit precedes all the other data traffic units in said re-ordering queue and having a residence time exceeding the minimal time delay variable;

e) applying to the data traffic units in the re-ordering queue a second selection operation, the second selection operation being characterized by a maximal time delay variable that defines a maximal residence time of a data traffic unit prior to release of the data traffic unit from said re-ordering queue, the second selection operation being applied to locate a potential data traffic unit having a residence time exceeding the maximal time delay variable irrespective of the sequence number of the data traffic unit;

f) releasing data traffic units located by the either one of the first and the second selection operations.

13. A method as defined in claim 12, said method further comprising:

a) identifying a missed opportunity in a re-ordering operation of said re-ordering queue to reduce a level of miss-ordering between data traffic units;

b) increasing said maximal time delay variable when a missed opportunity is identified in a).

14. A method as defined in claim 13, said method further comprising decreasing the value of the maximal time delay variable when no missed opportunity of re-ordering is identified during a certain number of data traffic units re-ordering operations.

15. A method as defined in claim 12, said method further comprising assessing a variation in delays for propagating data traffic units traveling over different pathways.

16. A method as defined in claim 15, wherein each data traffic unit is associated to a respective timestamp, each timestamp being indicative of a time data element assigned by a traffic splitting source in a network, said method further comprising:

a) recording for each data traffic unit a time of arrival;

b) reading the timestamp in each data traffic unit;

c) processing for each data traffic unit the time stamp and the recorded time of arrival to compute the variation in delays for propagating data traffic units traveling over different pathways.

17. A method as defined in claim 12, wherein each data traffic unit is associated to a respective address data element, each address data element being indicative of a traffic splitting source in a network through which the data traffic unit has traveled, said method further comprising providing a set of maximal time delay variables, each maximal time delay variable being associated to a respecti e address data element thereby allowing a given maximal time delay variable to be associated to a data traffic unit on the basis of said address data element.

18. A method as defined in claim 12, wherein each data traffic unit is associated to a respective address data element, each address data element being indicative of a traffic splitting source in a network through which the data traffic unit has traveled.

19. A computer readable storage medium including a program element suitable for execution by a computing apparatus for manipulating data traffic units transmitted in a network to reduce a level of miss-ordering of the data traffic units, said computing apparatus comprising:

a) a memory unit for storing a re-ordering queue for receiving the data traffic units;

b) a processor operatively connected to said memory unit, said program element when executing on said processor being operative for implementing;

i) an input for receiving a stream of data traffic units in a potentially miss-ordered condition, each data traffic unit being associated to a respective sequence number;

ii) a re-ordering module for re-ordering the data traffic units in the re-ordering queue on a basis of the sequence number of each data traffic unit for reducing a level of miss-ordering of the data traffic units;

iii) a selector module for;

(i) applying to the data traffic units in the re-ordering queue a first selection operation, the first selection operation being characterized by a minimal time delay variable that defines a minimal residence time of a data traffic unit prior to release of the data traffic unit from said re-ordering queue, the first selection operation being applied to locate a potential data traffic unit having a sequence number indicating that the data traffic unit precedes all the other data traffic units in said re-ordering queue and having a residence time exceeding the minimal time delay variable;

(ii) applying to the data traffic units in the re-ordering queue a second selection operation, the second selection operation being characterized by a maximal time delay variable that defines a maximal residence time of a data traffic unit prior to release of the data traffic unit from said re-ordering queue, the second selection operation being applied to locate a potential data traffic unit having a residence time exceeding the maximal time delay variable irrespective of the sequence number of the data traffic unit;

iv) an output for releasing data traffic units located by the selector module.

20. An apparatus for manipulating data traffic units transmitted in a network to reduce a level of miss-ordering of the data traffic units, said apparatus comprising:

a) means for receiving a stream of data traffic units in a potentially miss-ordered condition, each data traffic unit being associated to a respective sequence number;

b) means for storing the data traffic units;

c) means for re-ordering the data traffic units in the storing means on a basis of the sequence number of each data traffic unit for reducing a level of miss-ordering of the data traffic units;

d) means for applying to the data traffic units in the storing means a first selection operation, the first selection operation being characterized by a minimal time delay variable that defines a minimal residence time of a data traffic unit prior to release of the data traffic unit from said storing means, the first selection operation being applied to locate a potential data traffic unit having a sequence number indicating that the data traffic unit precedes all the other data traffic units in said string means and having a residence time exceeding the minimal time delay variable;

e) means for applying to the data traffic units in the storing means a second selection operation, the second selection operation being characterized by a maximal time delay variable that defines a maximal residence time of a data traffic unit prior to release of the data traffic unit from said storing means, the second selection operation being applied to locate a potential data traffic unit having a residence time exceeding the maximal time delay variable irrespective of the sequence number of the data traffic unit;

f) means for releasing data traffic units located by the either one of the first and the second selection operations.