Method and system for maintaining partial order of packets

• US 20040240473A1
• Filed: 05/28/2003
• Published: 12/02/2004
• Est. Priority Date: 05/28/2003
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Kumar, Alok, Yavatkar, Raj, Hardekopf, Benjamin C.
• Granted Patent: US 7,411,902 B2
• Time in Patent Office: Days
• US Class Current: 370/474
• CPC Class Codes: H04L 2012/565 Sequence integrity
• 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/25 Routing or path finding in a switch fabric

Abstract

A method and system for maintaining partial order of packets in packet processing modules is described. The system includes a memory and a plurality of packet processing modules to process packets that are part of a sequence in order. The memory stores a plurality of indicators, each indicator associated with one of the plurality of packet processing modules to identify which packets in the sequence are to be processed by the packet processing module and which packets in the sequence are to be skipped. The next packet in the sequence to be processed by the packet processing module is determined based on the stored indicators. A packet received at the packet processing module is processed if the packet is the next packet in the sequence to be processed.

Claims

1. A method comprising:

storing for one of a plurality of packet processing modules a plurality of indicators to identify which packets in a sequence of packets will be processed by the packet processing module;

determining a next packet in the sequence to be processed by the packet processing module based on the stored indicators; and

processing a packet received at the packet processing module if the received packet is the next packet in the sequence to be processed.

2. The method of claim 1, wherein storing for one of a plurality of packet processing modules a plurality of indicators to identify which packets in a sequence of packets will be processed by the packet processing module comprises storing an indicator for each packet in the sequence of packets to indicate whether the packet will be processed or skipped by the packet processing module.

3. The method of claim 2, wherein determining the next packet in the sequence to be processed by the packet processing module based on the stored indicators comprises determining the last packet in the sequence that has been processed by the packet processing module and checking the indicator associated with the next packet in the sequence to determine whether the next packet in the sequence should be skipped.

4. The method of claim 1, further comprising storing the packet received at the packet processing module if the received packet is not the next packet in the sequence to be processed.

5. The method of claim 4, wherein storing the received packet if the received packet is not the next packet in the sequence to be processed comprises storing the received packet in an Asynchronous Insert, Synchronous Remove (AISR) array if the received packet is not the next packet in the sequence to be processed.

6. The method of claim 5, further comprising retrieving the stored packet from the AISR array and processing the packet when the packet is determined to be the next packet in the sequence to be processed.

7. The method of claim 1, further comprising storing a plurality of indicators to specify which packets in the sequence of packets are ready to be processed by the packet processing module.

8. The method of claim 1, further comprising storing an indicator to identify whether the packet processing module has at least one packet waiting to be processed.

9. The method of claim 1, further comprising storing an indicator to identify whether the packet processing module has a number of packets waiting to be processed that exceeds a predetermined threshold number.

10. An apparatus comprising:

a plurality of packet processing modules to process packets that are part of a sequence in order; and

a memory coupled to the plurality of packet processing modules, the memory to store the packets of the sequence in order and to store a plurality of indicators, each indicator associated with one of the plurality of packet processing modules to identify which packets in the sequence are to be processed by the packet processing module.

11. The apparatus of claim 10, wherein the memory is a Static Random Access Memory (SRAM).

12. The apparatus of claim 10, wherein the memory to store the packets of the sequence in order comprises the memory store the packets in an Asynchronous Insert, Synchronous Remove (AISR) array.

13. The apparatus of claim 10, wherein the memory to store a plurality of indicators comprises the memory to store a plurality of bit vectors, each bit vector associated with one of the plurality of packet processing modules to identify which packets in the sequence are to be processed by the packet processing module.

14. The apparatus of claim 13, wherein the memory further stores a plurality of bit vectors associated with the plurality of packet processing modules to identify which packets in the ordered sequence of packets are ready to be processed by each of the packet processing modules.

15. The apparatus of claim 13, wherein the memory further stores a bit vector to indicate which packet processing modules have at least one packet waiting to be processed.

16. The apparatus of claim 13, wherein the memory further stores a bit vector to indicate which packet processing modules have a number of packets waiting to be processed that exceeds a predetermined threshold.

17. The apparatus of claim 13, wherein the memory further stores a bit vector to indicate which packet processing modules have a packet in the right order that is waiting to be processed.

18. An article of manufacture comprising:

a machine accessible medium including content that when accessed by a machine causes the machine to;

store for one of a plurality of packet processing modules a plurality of indicators to identify which packets in a sequence of packets will be processed by the packet processing module;

determine a next packet in the sequence to be processed by the packet processing module based on the stored indicators; and

process a packet received at the packet processing module if the packet is the next packet in the sequence to be processed.

19. The article of manufacture of claim 18, wherein the machine accessible medium including content that when accessed by the machine causes the machine to store for one of a plurality of packet processing modules a plurality of indicators to identify which packets in a sequence of packets will be processed by the packet processing module comprises machine accessible medium including content that when accessed by the machine causes the machine to store an indicator for each packet in the sequence of packets to indicate whether the packet will be processed or skipped by the packet processing module.

20. The article of manufacture of claim 19, wherein the machine accessible medium including content that when accessed by the machine causes the machine to determine the next packet in the sequence to be processed by the packet processing module based on the stored indicators comprises machine accessible medium including content that when accessed by the machine causes the machine to determine the last packet in the sequence processed by the packet processing module and to check the indicator associated with the next packet in the sequence to determine whether the next packet in the sequence should be skipped.

21. The article of manufacture of claim 18, wherein the machine-accessible medium further includes content that causes the machine to store the packet received at the packet processing module in an Asynchronous Insert, Synchronous Remove (AISR) array if the received packet is not the next packet in the sequence to be processed.

22. The article of manufacture of claim 21, wherein the machine-accessible medium further includes content that causes the machine to retrieve the stored packet from the AISR array and process the packet when the packet is determined to be the next packet in the sequence to be processed.

23. A system comprising:

a switch fabric;

a network processor coupled to the switch fabric via a switch fabric interface, the network processor including;

a plurality of packet processing modules to process packets that are part of a sequence in order; and

a Static Random Access Memory (SRAM) coupled to the network processor, the SRAM to store the packets of the sequence in order in an array and to store a plurality of indicators, each indicator associated with one of the plurality of packet processing modules to identify which packets in the sequence are to be processed by the packet processing module.

24. The system of claim 23, wherein the SRAM to store the packets of the sequence in order in an array comprises the SRAM to store the packets in an Asynchronous Insert, Synchronous Remove (AISR) array.

25. The system of claim 23, wherein the SRAM to store a plurality of indicators comprises the SRAM to store a plurality of bit vectors, each bit vector associated with one of the plurality of packet processing modules to identify which packets in the sequence are to be processed by the packet processing module.

26. The system of claim 25, wherein the SRAM further stores a plurality of bit vectors associated with the plurality of packet processing modules to identify which packets in the sequence are ready to be processed by the packet processing modules.