Method of preserving data packet sequencing

• US 6,738,379 B1
• Filed: 03/30/2000
• Issued: 05/18/2004
• Est. Priority Date: 03/30/2000
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Balazinski, Bartosz, Racine, Yves
• Primary Examiner(s): Sam, Phirin
• Application Number:
  US09/538,195
• Time in Patent Office: 1,510 Days
• Field of Search: 370/338, 370/352, 370/353, 370/354, 370/394, 370/395.52, 370/413, 370/417, 370/473, 370/474, 370/476, 370/356, 370/386, 370/388, 370/392, 370/412, 370/422, 370/429
• US Class Current: 370/394
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method of preserving data packet sequencing between nodes in a radio telecommunications network in which the User Datagram Protocol/Internet Protocol (UDP/IP) is utilized to communicate between the nodes of the network. Sequencing numbers are added to the headers of a plurality of data packets which are transmitted over a plurality of data transmission paths. The UDP/IP protocol is adapted with a resequencing layer which is utilized at the receiving node to resequence the packets.

Claims

1. A method of preserving data packet sequencing when a plurality of data packets are transmitted over a plurality of data transmission paths between a sending node and a receiving node in a radio telecommunications network, said method comprising the steps of:

sequentially numbering the data packets at the sending node;

sequentially transmitting the packets in a sequence from the sending node over the plurality of data transmissions paths;

receiving the sequence of data packets at the receiving node;

passing the received data packets directly to a receiving application if the received data packets have sequential packet numbers; and

reconstructing the data packets into the transmitted sequence if the received data packets do not have sequential packet numbers, said reconstructing step including the steps of;

storing a first data packet received out of sequence in a reconstruction buffer having a finite storage space with a beginning and an end;

storing additional received data packets in the buffer in increasing numerical order from the beginning of the buffer;

determining whether two or more stored data packets at the beginning of the buffer have sequential packet numbers;

sending the two or more stored data packets with sequential packet numbers from the buffer to the receiving application;

starting a packet timer, T1, at the receiving node when the first out-of-sequence data packet is received, T1 timing the longest permissible transfer time of a single packet through the network, and T1 being reset each time a sequential data packet at the beginning of the buffer is received, or the buffer is filled;

determining whether or not T1 expires before a sequential data packet at the beginning of the buffer is received or the buffer is filled; and

passing any sequential data packets stored in the buffer to the receiving application if T1 expires before a sequential data packet at the beginning of the buffer is received, or if the buffer is filled.

2. A method of preserving data packet sequencing when a plurality of data packets are transmitted over a plurality of data transmission paths between a sending node and a receiving node in a radio telecommunications network, said method comprising the steps of:

labeling by the sending node, each packet being transmitted with an increasing sequence number;

transmitting the packets from the sending node over the plurality of data transmissions paths to the receiving node;

receiving a first data packet out of sequence at the receiving node;

starting a packet timer, T1, at the receiving node when the first out-of-sequence data packet is received, T1 timing the longest permissible transfer time of a single packet through the network, and T1 being reset each time a sequential data packet is received;

time-stamping the first out-of-sequence data packet and storing it in a reconstruction buffer, said buffer containing storage space to store the maximum number of data packets that can be received before T1 expires;

storing subsequently received packets in the buffer in increasing numerical order from the beginning of the buffer;

receiving a second data packet;

determining whether or not the second packet is assigned a number that is sequential to the number of the first data packet;

passing the first and second data packets from the buffer to the receiving application if the second packet is assigned a number that is sequential to the number of the first data packet, and the first and second data packets are at the beginning of the buffer;

retaining the second data packet in the buffer if the second packet is assigned a number that is not sequential to the number of the first data packet, or if the first and second packets are sequential but not at the beginning of the buffer;

determining whether or not the buffer is full;

continuing to store received packets if the buffer is not full;

if the buffer is full, determining if there are any sequences of packets that are not at the beginning of the buffer, and passing the sequence of packets that have the lowest sequential numbers to the receiving application;

determining whether or not T1 expires before a sequential data packet at the beginning of the buffer is received;

passing any sequential data packets from the buffer to a receiving application if T1 expires before a sequential data packet at the beginning of the buffer is received;

starting an inactivity timer, T2, whenever the buffer is empty, T2 timing a time period for the sequence number to repeat itself (wrap around);

determining whether or not T2 expires before another packet is received; and

starting the method over if T2 expires.

3. A method of preserving data packet sequencing when a plurality of data packets are transmitted over a plurality of data transmission paths between a sending node and a receiving node in a radio telecommunications network, said method comprising the steps of:

labeling by the sending node, each packet being transmitted with an increasing sequence number until a predetermined number of packets have formed a sequence;

repeating the sequence numbers in subsequent sequences of packets;

transmitting the packets from the sending node in a series of sequences, each sequence containing the predetermined number of data packets and repeating the sequential numbers assigned to each data packet within each sequence;

receiving the transmitted packets in the receiving node;

determining whether or not the received packets have sequential packet numbers;

passing the received data packets directly to a receiving application if the received data packets have sequential packet numbers; and

reconstructing the data packets into the transmitted sequence if the received data packets do not have sequential packet numbers by;

storing the received data packets in a reconstruction buffer having a storage space with a beginning and an end, said received packets being stored in the buffer in increasing numerical order from the beginning of the buffer;

determining whether two or more packets have sequential numbers and are stored at the beginning of the buffer;

passing the two or more packets to the receiving application if they have sequential numbers and are stored at the beginning of the buffer;

retaining the two or more packets in the buffer if they have sequential numbers and are not stored at the beginning of the buffer;

determining whether subsequently received packets fill a gap between the beginning of the buffer and the two or more sequential packets; and

passing the two or more sequential packets and the subsequently received packets to the receiving application if the subsequently received packets fill the gap between the beginning of the buffer and the two or more packets.

4. A method of preserving data packet sequencing when a plurality of data packets are transmitted over a plurality of data transmission paths between a sending node and a receiving node in a radio telecommunications network, said method comprising the steps of:

labeling by the sending node, each packet being transmitted with an increasing sequence number;

transmitting the packets from the sending node over the plurality of data transmissions paths to the receiving node;

receiving the data packets at the receiving node;

determining whether the received data packets have sequential packet numbers;

passing the received data packets directly to a receiving application if the received data packets have sequential packet numbers;

storing the received data packets in a reconstruction buffer if the received data packets do not have sequential packet numbers;

starting a packet timer, T1, at the receiving node when the first out-of-sequence data packet is received, T1 timing the longest permissible transfer time of a single packet through the network, and T1 being reset each time a sequential data packet at the beginning of the buffer is received, or the buffer is filled;

determining whether or not T1 expires before a sequential data packet at the beginning of the buffer is received or the buffer is filled; and

passing any sequential data packets stored in the buffer to the receiving application if T1 expires before a sequential data packet at the beginning of the buffer is received, or if the buffer is filled.

5. In a data network in which a plurality of data packets are transmitted over a plurality of data transmission paths between a sending node and a receiving node, the data packets being numbered with increasing sequence numbers, a method of resequencing the data packets in a reconstruction buffer in the receiving node prior to passing the data packets to a receiving application, said method comprising the steps of:

(A) entering a Start-up state when a transmission begins, said startup state performing the steps of;

(1) starting a packet timer, T1, when a first data packet is received, T1 timing the longest permissible transfer time of a single packet through the network;

(2) placing additional packets in the buffer in increasing sequence number;

(3) determining whether T1 expires or the buffer is full;

(4) passing a first group of sequential data packets at the beginning of the buffer to the receiving application;

(5) determining whether the buffer is empty;

(6) proceeding to step (B) upon determining that the buffer is empty; and

(7) proceeding to step (C) upon determining that the buffer is not empty;

(B) entering an Empty Buffer state, said Empty Buffer state performing the steps of;

(1) starting an inactivity timer, T2, that measures a time period for the sequence number to repeat itself (wrap around);

(2) if T2 expires before receiving a packet, returning to the Start-up state;

(3) if a subsequent data packet is received having a sequence number that equals the expected value of the sequence number for the next data packet to be received;

(a) passing the subsequent data packet having a sequence number that equals the expected value to the receiving application;

(b) incrementing the expected value; and

(c) restarting T2;

(4) if a subsequent data packet is received having a sequence number that does not equal the expected value and is out of the range of the buffer space, the sequence number is in the T2 space, and T2 has not expired;

(a) stopping T2; and

(b) returning to the Start-up state;

(5) if a subsequent data packet is received having a sequence number that does not equal the expected value and is out of the range of the buffer space, and out of T2 space;

(a) rejecting the subsequent data packet;

(b) incrementing a rejection counter; and

(c) determining whether the rejection counter equals a rejection counter threshold;

(d) remaining in the Empty Buffer state if the rejection counter does not equal the rejection counter threshold; and

(e) returning to step (A) if the rejection counter equals the rejection counter threshold; and

(6) proceeding to step (C) upon determining that a subsequent data packet is received having a sequence number that does not equal the expected value and is within the range of the buffer; and

(C) entering a Buffer Not Empty state, said Buffer Not Empty state performing the steps of;

(1) if a subsequent data packet is received having a sequence number that does not equal the expected value;

(a) time stamping the subsequent packet; and

(b) storing the subsequent packet in the buffer;

(2) if T1 has expired, the buffer is full, or if a subsequent data packet is received having a sequence number that equals the expected value;

(a) passing sequential data packets at the beginning of the buffer to the receiving application;

(b) incrementing the expected value; and

(c) returning to the Empty Buffer state if the buffer is empty;

(3) if a subsequent data packet is received having a sequence number that does not equal the expected value and the sequence number is out of the range of the buffer;

(a) rejecting the subsequent data packet;

(b) incrementing a rejection counter; and

(c) determining whether the rejection counter equals a rejection counter threshold;

(d) remaining in the Buffer Not Empty state if the rejection counter does not equal the rejection counter threshold; and

(e) returning to the Start-up state if the rejection counter equals the rejection counter threshold.