Method for reordering sequenced packets

1. A method for receiving, reordering, and transmitting data packets, wherein each data packet contains a sequence identifier, the method comprising:

receiving data packets

for each received data packet:

extracting a sequence number from the data packet

associating a receive time indicator with the data packet

calculating an expiration time for the received data packet based on the associated receive time indicator

recording the sequence number and the calculated expiration time in a table in sequence number order

for each data packet to be transmitted:

reading the table to determine a next data packet to be transmitted

transmitting the next data packet if the next data packet is available

if the next data packet is unavailable

determining a true expiration time for the unavailable next data packet

waiting for the unavailable next data packet to become available if a current time is less than the true expiration time for the unavailable next data packet

defining the unavailable data packet as lost if the current time is greater than the true expiration time for the unavailable data packet.

2. The method of claim 1 , further comprising:

obtaining a memory pointer from an address FIFO for each received data packet

storing each received data packet in a memory based on the associated memory pointer

recording the memory pointer in the table entry for the received data packet.

3. The method of claim 2 , further comprising returning the memory pointer associated with each data packet in the output stream to the address FIFO.

4. The method of claim 1 , wherein the next data packet to be transmitted is determined based on the sequence numbers stored in the table.

5. The method of claim 1 , wherein the next data packet to be transmitted is determined based on the sequence numbers stored in the table and a priority level associated with at least some of the received data packets.

6. The method of claim 1 , wherein the calculated expiration time of a received data packet is determined by adding a predetermined time-out period to the receive time indicator.

7. The method of claim 1 , wherein the true expiration time of an unavailable data packet is determined to be the lowest expiration time of all received data packets having a higher sequence number than the sequence number of the unavailable data packet.

8. A system for reordering data packets at a destination processor in a packet switching network, wherein a sequence identifier is associated with each data packet, the system comprising:

time stamp logic that operates to associate a receive time indicator with each received data packet

enqueue logic that operates to

extract a sequence number from each received data packet

compute an expiration time for each received data packet based on the receive time indicator

store the extracted sequence number and computed expiration time into a table based on the sequence identifiers associated with the received data packets

dequeue logic that operates to

read the table to determine a next data packet to be transmitted

output the next data packet if the next data packet is available

if the next data packet is unavailable

determine a true expiration time for the unavailable next data packet

wait for the unavailable next data packet to become available if a current time is less than the true expiration time for the unavailable data packet

define the unavailable data packet as lost if the current time is greater than the true expiration time for the unavailable data packet.

9. The system of claim 8 , further comprising:

a memory coupled to the enqueue logic

a pointer FIFO coupled to the enqueue logic

wherein the enqueue logic operates to obtain a pointer to the memory from the pointer FIFO for each received data packet and stores the received data packets in the memory based on the pointers.

10. The system of claim 9 , wherein the memory and the pointer FIFO are coupled to the dequeue logic.

11. The system of claim 10 , further comprising a read pointer register that is used to read selected entries from the table.

12. The system of claim 11 , further comprising a delay store register that is used to store the pointers into the table.

13. The system of claim 12 , further comprising a current value register that is used to determine the true expiration time.

14. The system of claim 13 , further comprising a largest value register that is used to maintain a largest sequence identifier value.

15. The system of claim 8 , wherein the dequeue logic determines the next data packet to be transmitted based on the sequence numbers stored in the table.

16. The system of claim 8 , wherein the dequeue logic determines the next data packet to be transmitted based on the sequence numbers stored in the table and a priority level associated with at least some of the received data packets.

17. The system of claim 8 , wherein the enqueue logic determines the computed expiration time of a received data packet by adding a predetermined time-out period to the receive time indicator.

18. The system of claim 8 , wherein the dequeue logic determines the true expiration time of an unavailable data packet to be the lowest expiration time of all received data packets having a higher sequence number than the sequence number of the unavailable data packet.