Method for reordering and reassembling data packets in a network

• US 20020095512A1
• Filed: 02/23/2001
• Published: 07/18/2002
• Est. Priority Date: 11/30/2000
• Status: Active Grant

• Current Assignee: AudioCodes, Inc. (Audiocodes Limited)
• Original Assignee: AudioCodes, Inc. (Audiocodes Limited)
• Inventors: Rana, Aswinkumar Vishanji, Garrow, Corey Alan
• Granted Patent: US 7,760,737 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• 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
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation

Abstract

A method is described that is operable to reorder and reassemble data packets from network traffic into unfragmented and in-order traffic flows for applications such as deep packet classification and quality of service determination. A queue engine stores incoming data packets in a packet memory that is controlled by a link list controller. A packet assembler extracts information from each data packet, particularly fields from the header information, and uses that information among other things, to determine if the data packet is fragmented or out of order, and to associate the data packet with a session id. If the packet is determined to be out of order, the queue engine includes a reordering unit, which is able to modify links with the link list controller to reorder data packets. A fragment reassembly unit is also included which is capable of taking fragments and reassembling them into complete unfragmented data packets. The reordered and reassembled data packets are then sent to an output where further operations such as deep packet classification can take place.

Claims

1. A method for reordering out of sequence data packets which are associated with a traffic flow on a data network, the data packets including header information with fields, some data packets including a sequence number that determines packet order, the method comprising:

receiving the data packets from an input;

extracting the desired fields from the data packets including the sequence number;

identifying out of sequence data packets;

reordering out of sequence data packets using a link list storing the locations of data packets in the traffic flow; and

sending the data packets to an output.

2. The method of claim 1 further comprising after reordering:

identifying fragmented data packets; and

reassembling fragmented data packets using a fragment reassembly unit and fragment memory.

3. The method of claim 1 wherein identifying out of sequence data packets includes comparing the sequence number to that of previous data packets in the same traffic flow.

4. The method of claim 1 wherein extracting includes determining a session id for the data packet the session id associating the data packet with a particular traffic flow.

5. The method of claim 1 wherein reordering includes time-out mechanism for identifying unreordered data packets after a prescribed amount of time.

6. The method of claim 2 wherein reassembling includes time-out mechanism for identifying unreassembled data packets after a prescribed amount of time.

7. The method of claim 1 further comprising after receiving, storing the data packets in a packet memory.

8. The method of claim 7 wherein the packet memory is controlled by a link list controller that keeps track of data packets in the packet memory.

9. A method for reassembling fragmented data packets which are formed by multiple fragments in a data network, the fragments including header information with fields, each fragment including a start offset and an expected offset that determines fragment order, the method comprising:

receiving the fragments from an input;

extracting the desired fields from the fragments including the start offset and the expected offset;

reassembling the fragments into the complete data packet using a link list storing the locations of the fragments making up the data packet; and

sending the reassembled data packets to an output.

10. The method of claim 9 wherein reassembling the fragments includes using a window data structure to store the start offset and expected offset of out of order fragments.

11. The method of claim 10 wherein reassembling further includes comparing the start offset of the fragment to an order offset and to the start offset and expected offset of any window entries.

12. The method of claim 9 wherein reassembling includes time-out mechanism for identifying unreassembled fragments after a prescribed amount of time.

13. The method of claim 9 further comprising after receiving, storing the fragments in a packet memory.

14. The method of claim 9 wherein the packet memory is controlled by a link list controller that keeps track of fragments and data packets in the packet memory.