Optimized algorithm for stream re-assembly

• US 20050286526A1
• Filed: 06/25/2004
• Published: 12/29/2005
• Est. Priority Date: 06/25/2004
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Li, Yunhong, Khobare, Abhijit S., Sood, Sanjeev H.
• Application Number:
  US10/877,465
• Publication Number:
  US 20050286526A1
• Time in Patent Office: Days
• 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 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

A mechanism is provided to receive out-of-order packets and to use a table to place the out-of-order packets in a queue so that the packets are queued in order of a sequence in which the packets were sent.

Claims

1. A method comprising:

receiving packets delivered out-of-order by a network; and

using a table to place each packet received in a queue so that the packets are queued in order according to a sequence in which the packets were provided to the network by a sender.

2. The method of claim 1 wherein the packets include order information, associated with the packets by the sender, usable to determine the sequence.

3. The method of claim 2 wherein the order information in each packet comprises a sequence number.

4. The method of claim 3 wherein the queue comprises a linked list and the table divides the linked list into sublists at points in the linked list corresponding to gaps in the sequence.

5. The method of claim 4 wherein each sublist is represented by an entry in the table.

6. The method of claim 5 wherein each entry includes a head pointer to point to a first packet in the sublist and a tail pointer to point to a last packet in the sublist.

7. The method of claim 6 wherein the entry further includes a start sequence number associated with the first packet in the sublist and an end sequence number associated with the last packet in the sublist.

8. The method of claim 5 wherein using the table comprises:

searching the table for each packet after such packet is received, the searching beginning with a first entry and continuing with each successive entry until a matching one of the entries, one usable to determine a location at which such packet is to be inserted into the queue linked list, is found.

9. The method of claim 8 wherein searching comprises, for each entry searched, examining the entry to determine if the packet should be included in the sublist represented by the entry.

10. The method of claim 9 wherein searching further comprises updating the entry to reflect the inclusion of the packet in the sublist.

11. The method of claim 9 wherein searching further comprises examining the entry to determine if the packet is to be added to the queue linked list as a new sublist that is adjacent to the sublist in the queue linked list.

12. The method of claim 11 wherein searching further comprises updating the table to include a new entry to represent the new sublist.

13. The method of claim 1 wherein each packet comprises a TCP segment.

14. The method of claim 1 wherein each packet comprises an IP fragment.

15. The method of claim 2 wherein each packet comprises an IP fragment and the order information comprises an offset value.

16. An article comprising:

a storage medium having stored thereon instructions that when executed by a machine result in the following;

using a table to place packets, delivered out-of-order by a network, in a queue so that the packets are queued in order according to a sequence in which the packets were provided to the network by a sender.

17. The article of claim 16 wherein the packets include order information, associated with the packets by the sender, usable to determine the sequence.

18. The article of claim 17 wherein the order information in each packet comprises a sequence number.

19. The article of claim 18 wherein the queue comprises a linked list and the table divides the linked list into sublists at points in the linked list corresponding to gaps in the sequence.

20. The article of claim 19 wherein each sublist is represented by an entry in the table.

21. The article of claim 20 wherein each entry includes a head pointer to point to a first packet in the sublist and a tail pointer to point to a last packet in the sublist.

22. The article of claim 21 wherein the entry further includes a start sequence number associated with the first packet in the sublist and an end sequence number associated with the last packet in the sublist.

23. The article of claim 21 wherein using the table comprises:

searching the table for each packet after such packet is received, the searching beginning with a first entry and continuing with each successive entry until a matching one of the entries, one usable to determine a location at which such packet is to be inserted into the queue linked list, is found.

24. The article of claim 23 wherein searching comprises, for each entry searched, examining the entry to determine if the packet should be included in the sublist represented by the entry.

25. The article of claim 24 wherein searching further comprises updating the entry to reflect the inclusion of the packet in the sublist.

26. The article of claim 24 wherein searching further comprises examining the entry to determine if the packet is to be added to the queue linked list as a new sublist that is adjacent to the sublist in the queue linked list.

27. The article of claim 26 wherein searching further comprises updating the table to include a new entry to represent the new sublist.

28. The article of claim 16 wherein each packet comprises a TCP segment.

29. The article of claim 16 wherein each packet comprises an IP fragment.

30. The article of claim 17 wherein each packet comprises an IP fragment and the order information comprises an offset value.

31. An apparatus comprising:

a memory system including a buffer memory to store packets delivered out-of-order by a network;

a processor, coupled to the memory system, to execute software to process the packets according to a protocol;

wherein the processor, when executing the software, maintains in the memory system data structures including a queue and a corresponding table;

wherein the processor, when executing the software, uses the table to place packets in the queue so that the packets are queued in order according to a sequence in which the packets were provided to the network by a sender.

32. The apparatus of claim 31 wherein the packets include sequence numbers, associated with the packets by the sender, usable to determine the sequence.

33. The apparatus of claim 32 wherein the queue comprises a linked list and the table divides the linked list into sublists at points in the linked list corresponding to gaps in the sequence.

34. The apparatus of claim 33 wherein each sublist is represented by an entry in the table.

35. The apparatus of claim 34 wherein the processor, when using the table, searches the table for each packet after such packet is received, the searching beginning with a first entry and continuing with each successive entry until a matching one of the entries, one usable to determine a location at which such packet is to be inserted into the queue linked list, is found.

36. The apparatus of claim 35 wherein the searching comprises, for each entry searched, examining the entry to determine if the packet should be included in the sublist represented by the entry.

37. The apparatus of claim 34 wherein the searching further comprises updating the entry to reflect the inclusion of the packet in the sublist.

38. The apparatus of claim 36 wherein the searching further comprises examining the entry to determine if the packet is to be added to the queue linked list as a new sublist that is adjacent to the sublist in the queue linked list.

39. The apparatus of claim 38 wherein searching further comprises updating the table to include a new entry to represent the new sublist.

40. The apparatus of claim 31 wherein each packet comprises a TCP segment.

41. The apparatus of claim 31 wherein the processor comprises a host CPU and the software comprises host operating system software.

42. The apparatus of claim 41 wherein the software comprises a TCP/IP stack.

43. The apparatus of claim 31 wherein the processor is a network processor having multiple threads of execution configurable to enable at least one of the threads of execution to execute the software.

44. An offload engine comprising:

a network device to interface to a network;

a memory system including a buffer memory to store packets delivered out-of-order by the network; and

a network processor comprising

a first interface connected to the network device to receive packets from the network;

a second interface to enable connection to a host system;

at least one processor, coupled to the memory system, to execute software to process the packets according to TCP;

wherein the at least one processor, when executing the software, maintains in the memory system data structures including a queue and a corresponding table; and

wherein the at least one processor, when executing the software, uses the table to place packets in the queue so that the packets are queued in order according to a sequence in which the packets were provided to the network by a sender.

45. The offload engine of claim 44 wherein the at least one processor comprises a first, general purpose processor to handle a control plane component of the TCP and a second processor to handle a data plane component of the TCP.

46. The offload engine of claim 45 where the software resides in the data plane component of the TCP.

47. The offload engine of claim 45 wherein the second processor comprises microengines each having threads of execution, and the software comprises microcode to execute on at least one thread of at least one microengine.