In sequence packet delivery without retransmission
A method of re-ordering packets receives packets having packet sequence numbers. The method then determines if a packet is an out of window packet and buffers out-of-window packets having a sequence number more than a first number. The method delivers a packet when the packet sequence number matches a first number. It delivers all buffered packets when a timeout occurs. A communication system having at least one network device that performs this method is also disclosed.
1. A method of re-ordering packets, the method comprising:
establishing tunnel parameters between a transmitting station and a receiving station, the tunnel parameters comprising an expected sequence number, a window size parameter, and a timeout value;
receiving a plurality of packets of a data stream at a receiving station, each of the packets having a packet sequence number indicating a position of the packet in the data stream;
determining if the packet sequence number of a first packet is equal to the expected sequence number;
delivering the first packet when the packet sequence number is equal to the expected sequence number;
determining if the packet sequence number of the first packet is out-of-window when the packet sequence number is not equal to the expected sequence number, wherein determining if the packet sequence number is out-of-window includes comparing the packet sequence number of the first packet to a window check parameter comprising the expected sequence number added to the window size parameter, the window size parameter having a predetermined and fixed value;
buffering the first packet if the first packet is in-window, wherein the tunnel allocates enough space in the buffer to store all in-window packets;
checking the buffer when the first packet is in-window and the packet sequence number is less than the window check parameter, wherein checking the buffer comprises starting a timer with the timeout value, the timeout value comprising a maximum delay the tunnel will wait on an arrival of a next in-sequence packet for in-sequence delivery;
buffering the first packet if the first packet is out-of-window;
checking the buffer when the first packet is out-of-window and the packet sequence number is greater than the window check parameter, wherein checking the buffer includes:
determining if the buffer is full;
buffering the first packet when the buffer is not full; and
when the buffer is full:
determining a lowest sequence number in the buffer;
delivering only a packet having the lowest sequence number; and
advancing the expected sequence number to an updated number comprising the lowest sequence number plus one; and
discarding the first packet when the first packet is out-of-window and the packet sequence number is less than the expected sequence number.
2. The method of claim 1 , the method further comprising:
delivering all packets in the buffer upon expiration of the timer;
advancing the expected sequence number to a second number; and
resetting the timer.
3. The method of claim 2 , wherein the second number is equal to a highest sequence number in the buffer before delivering all packets plus one.
4. An apparatus for re-ordering packets, the apparatus comprising:
means for establishing tunnel parameters between a transmitting station and a receiving station, the tunnel parameters comprising an expected sequence number, a window size parameter, and a timeout value;
means for receiving a plurality of packets of a data stream at a receiving station, each of the packets having a packet sequence number indicating a position of the packet in the data stream;
means for determining if the packet sequence number of a first packet is equal to the expected sequence number;
means for delivering the first packet when the packet sequence number is equal to the expected sequence number;
means for determining if the packet sequence number of the first packet is out-of-window when the packet sequence number is not equal to the expected sequence number, wherein determining if the packet sequence number is out-of-window includes comparing the packet sequence number of the first packet to a window check parameter comprising the expected sequence number added to the window size parameter, the window size parameter having a predetermined and fixed value;
means for buffering the first packet if the first packet is in-window, wherein the tunnel allocates enough space in the buffer to store all in-window packets;
means for checking the buffer when the first packet is in-window and the packet sequence number is less than the window check parameter, wherein checking the buffer comprises starting a timer with the timeout value, the timeout value comprising a maximum delay the tunnel will wait on an arrival of a next in-sequence packet for in-sequence delivery;
means for buffering the first packet if the first packet is out-of-window;
means for checking the buffer when the first packet is out-of-window and the packet sequence number is greater than the window check parameter, wherein checking the buffer includes:
determining if the buffer is full;
buffering the first packet when the buffer is not full; and
when the buffer is full:
determining a lowest sequence number in the buffer;
delivering only a packet having the lowest sequence number; and
advancing the expected sequence number to an updated number comprising the lowest sequence number plus one; and
means for discarding the first packet when the first packet is out-of-window and the packet sequence number is less than the expected sequence number.
5. The apparatus of claim 4 , the apparatus further comprising:
means for delivering all packets in the buffer upon expiration of the timer;
means for advancing the expected sequence number to a second number; and
means for resetting the timer.
6. The apparatus of claim 5 , wherein the second number is equal to a highest sequence number in the buffer before delivering all packets plus one.