Method and system for reassembling and parsing packets in a network environment

• US 7,298,746 B1
• Filed: 04/22/2002
• Issued: 11/20/2007
• Est. Priority Date: 02/11/2002
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: TRAN, KIET, Chou, Chien C., Puri, Rahoul, Gomez, Miguel, de la Iglesia, Erik
• Primary Examiner(s): Levitan, Dmitry
• Application Number:
  US10/127,372
• Time in Patent Office: 2,038 Days
• Field of Search: 370/389, 370/392, 370/397, 370/394, 709227-229
• US Class Current: 370/394
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• 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 packet reassembly system includes a buffer for storing information elements included in one or more incoming packets, a memory for storing validity indicators corresponding to the information elements, a first logic circuit capable of setting the validity indicators based on the information elements stored in the buffer, and a second logic circuit capable of determining the contiguity of the information elements stored in the buffer based on the settings of the validity indicators.

Claims

1. A method of reassembling a plurality of information elements included in one or more packets that may be received in any order, comprising:

providing a buffer having a plurality of locations, each location capable of storing an information element;

providing a plurality of flags, in a memory, in one-to-one correspondence with the plurality of locations in the buffer, each flag to indicate whether an information element is stored or not at the corresponding location in the buffer;

storing a plurality of information elements in the buffer according to one or more sequence numbers, associated with the one or more packets, that determine a correct order, wherein the sequence number for a packet determines the location in the buffer where any information element included in the packet is stored, so that the information elements, if received in a different order, are placed in the correct order;

for each information element stored in the buffer, setting the flag corresponding to the location in the buffer where the data element is stored to indicate storage of an information element at the location; and

scanning information derived from the plurality of flags in the memory to determine whether reassembly is complete.

2. The method of claim 1, wherein each of the information elements is a byte.

3. The method of claim 1, wherein each of the flags is a bit.

4. The method of claim 1, wherein the step of scanning includes:

determining a contiguity of the plurality of information elements stored in the buffer based on the corresponding plurality of flags in the memory.

5. The method of claim 1, further comprising:

setting an encoded value as a function of at least one of the flags; and

determining whether a token, comprising one or more of the information elements, is stored in the buffer based on the encoded value.

6. The method of claim 5, wherein the encoded value is a single or multibit value stored in memory.

7. The method of claim 5, wherein the encoded value corresponds to a plurality of flags stored in the memory.

8. A system for handling packet traffic, comprising:

a buffer for storing a plurality of information elements included in one or more packets that may be received in any order, the buffer having a plurality of locations, the plurality of information elements being stored according to one or more sequence numbers, associated with the one or more packets, that determine a correct order, wherein the sequence number for a packet determines the location in the buffer where any information element included in the packet is stored, so that the information elements, if received in a different order are placed in the correct order;

a memory for storing a plurality of validity indicators in-one-to-one correspondence with the plurality of locations of the buffer, each such validity indicator to indicate whether an information element is stored or not at the corresponding location of the buffer;

a first logic circuit capable of setting the validity indicators based on storage of the information elements at the corresponding locations of the buffer; and

a second logic circuit capable of determining a contiguity of the information elements stored in the buffer based on the settings of the validity indicators.

9. The system of claim 8, wherein the information elements are bytes.

10. The system of claim 8, wherein the validity indicators are bits.

11. The system of claim 8, further comprising:

a second memory for storing a summary value;

a third logic circuit for setting the summary value as a function of one or more of the validity indicators; and

a fourth logic circuit for determining whether a token, comprising one or more of the information elements, is stored in the buffer based on the summary value.

12. The system of claim 11, wherein the summary value is a single or multibit value stored in the second memory.

13. The system of claim 8, wherein the buffer includes a circular buffer.

14. A system for handling packet traffic, comprising:

means for storing a plurality of information elements included in one or more packets, which may be received in any order, at a plurality of locations according to one or more sequence numbers, associated with the one or more packets, that determine a correct order, a sequence number for a packet determining the location where any information element included in the packet is stored, so that the information elements, if received in a different order, are placed in the correct order;

means for storing a plurality of validity indicators that are in one-to-one correspondence with the plurality of locations, wherein each of the validity indicators is to indicate whether an information element is stored or not at the corresponding location;

means for setting the validity indicators based on storage of the information elements in the corresponding locations; and

means for determining a contiguity of the stored information elements based on the settings of the validity indicators.

15. The system of claim 14, further comprising:

means for setting a summary value as a function of one or more of the validity indicators; and

means for determining whether a token, comprising one or more of the information elements, is present among the stored information elements based on the summary value.

16. A method of reassembling a plurality of information elements that may be received in any order comprising:

providing a memory having a plurality of locations, each for storing an information element;

providing a plurality of indicators in one-to-one correspondence with the plurality of locations, each such indicator to indicate whether an information element is stored or not at the corresponding location in the memory;

storing a plurality of information elements in the memory according to sequence numbers, associated with the information elements, that determine a correct order wherein the sequence number for an information element determines the location in the memory where the information element is stored, so that the information elements, if received in a different order, are placed in the correct order;

for each information element stored in the memory, setting the indicator for the corresponding location to indicate storage of the information element at that location; and

determining if reassembly is complete by examining contiguity of one or more of the locations in the memory based on settings of the corresponding indicators.

17. The method of claim 16 wherein the determining step comprises:

deriving encoded information for each of one or more groups of locations in the memory; and

determining contiguity of one or more groups of locations in the memory based on settings of the encoded information for the corresponding one or more groups of locations in the memory.

18. The method of claim 17 further comprising determining whether an end of message is present in a group of locations based on settings of the encoded information corresponding to that group of locations.

19. The method of claim 18 further comprising determining contiguity for all locations in the group preceding the end of message based on settings of the encoded information corresponding to that group of locations.

20. The method of claim 16 wherein each of the plurality of information elements has an order in a message, the method further comprising storing the plurality of information elements in the memory in the same order as in the message.