Method and system for maintaining partial order of packets

• US 7,411,902 B2
• Filed: 05/28/2003
• Issued: 08/12/2008
• 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.
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US10/447,500
• Publication Number:
  US 20040240473A1
• Time in Patent Office: 1,903 Days
• Field of Search: 370/474, 370/230
• US Class Current: 370/230
• 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 a first packet processing module and a second packet processing module a plurality of indicators to identify which packets in a sequence of packets will be processed by the first packet processing module or the second packet processing module;

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

processing a packet received at the first packet processing module if the received packet is the next packet in the sequence to be processed; and

storing a plurality of indicators to specify which packets in the sequence of packets are ready to be processed by the first packet processing module.

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

3. The method of claim 2, wherein determining the next packet in the sequence to be processed by the first packet processing module based on the stored indicators comprises determining the last packet in the sequence that has been processed by the first 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 by the first packet processing module.

4. The method of claim 1, further comprising storing the packet received at the first 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 an indicator to identify whether the first packet processing module has at least one packet waiting to be processed.

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

9. An article of manufacture comprising:

a computer readable medium encoded with computer executable instructions that when accessed by a computer causes the computer to;

store a first packet processing module and a second packet processing module a plurality of indicators to identify which packets in a sequence of packets will be processed by the first packet processing module or the second packet processing module;

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

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

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.

10. The article of manufacture of claim 9, wherein the computer readable medium encoded with computer executable instructions that when accessed by the computer causes the computer to store for the first packet processing module and the second packet processing module a plurality of indicators to identify which packets in a sequence of packets will be processed by the first 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 by the first packet processing module and skipped by the second packet processing module.

11. The article of manufacture of claim 10, wherein the computer readable medium encoded with computer executable instructions that when accessed by the computer causes the computer to be processed by the first 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 first 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 by the first packet processing module.

12. The article of manufacture of claim 9, wherein the computer readable medium encoded with computer executable instructions that when accessed by the computer causes the computer to retrieve the stored packet from the AISR away and process the packet when the packet is determined to be the next packet in the sequence to be processed.