US 7,480,308 B1Granted

Distributing packets and packets fragments possibly received out of sequence into an expandable set of queues of particular use in packet resequencing and reassembly

AssigneeCisco Technology, Inc.

InventorsEarl T. Cohen, John Andrew Fingerhut, John J. Williams, Jr.

Life of this patent

Estimating the term…

Loading patent…

Abstract

Packets and packets fragments possibly received out of sequence are distributed into an expandable set of queues. For each particular packet or fragment, a queue within a set of queues is identified that does not contain a packet or packet fragment that is subsequent to the particular packet or fragment, and the particular packet or fragment is enqueued therein. If there is not such a queue available, a new queue is added to the set of queues. A data structure is typically updated for packet fragments to identify when all fragments have been received and the order of queues containing the packet fragments in order of their position within the reassembled packet. This ordered list of the queues is communicated to a reassembly mechanism to retrieve the packet fragments and to reassemble the packet. Resequencing of packets is similarly performed, and may be part of the reassembly process. The list of queues is not always used by the reassembly/resequencing mechanism as the enqueued fragments/packets typically contain sequence numbers.

Claims24

Dependent claims

A method for reassembling a packet, the packet when reassembled includes a plurality of packet fragments with each packet fragment identified with a position within the packet, the method comprising:

maintaining a plurality of queues;
enqueuing the plurality of packet fragments in a plurality of the plurality of queues, and
retrieving the plurality of packet fragments from the plurality of packet queues based on indications added to a data structure identifying the order of the plurality of packet fragments to produce the packet;
wherein said operation of enqueuing the plurality of packet fragments in the plurality of the plurality of queues includes, for each particular packet fragment of the plurality of packet fragments:
identifying a particular queue of the plurality of queues such that no already queued packet fragment of the packet in the particular queue comes after the particular packet fragment in the packet, wherein said identifying the particular queue for the particular packet fragment includes checking, at least when the particular queue is not empty, that the particular queue does not include a packet fragment which comes after the particular packet fragment in the packet;
enqueuing the particular packet fragment at the end of the particular queue;
and updating the data structure to include an indication of the particular queue in relation to the position of the particular packet fragment in the packet.

4 more elements

An apparatus for reassembly of a packet, the packet when reassembled includes a plurality of packet fragments with each packet fragment identified with a position within the packet, the apparatus comprising:

a plurality of reassembly queues;
a reassembly mechanism;
and
a distributor configured for each particular packet fragment of the plurality of packet fragments:
to acquire the particular packet fragment of the plurality of packet fragments, to identify a particular queue of the plurality of reassembly queues such that no already queued packet fragment in the particular queue comes after said particular packet fragment in the packet;
to cause said particular packet fragment to be enqueued at the end of the particular queue;
and to update a data structure to include an indication of the particular queue in relation to the position of said particular packet fragment in the packet;
wherein said identifying the particular queue includes checking, at least when the particular queue is not empty, that the particular queue does not include a packet fragment which comes after said particular packet fragment in the packet;
and wherein at least a plurality of said reassembly queues contains one or more of the plurality of packet fragments;
and wherein the distributor is configured to identify when all packet fragments of the packet have been received and in response, to provide the reassembly mechanism with indications of the queues of the plurality of reassembly queues containing packet fragments of the packet and their order corresponding to that of the order of the plurality of packet fragments in the packet;
and
wherein the reassembly mechanism is configured to retrieve the plurality of packet fragments from the plurality of resequencing queues based on the indications added to the data structure and reassemble the plurality of packet fragments to produce the packet.

9 more elements

A method for resequencing and reassembling of packets, the method comprising:

maintaining a plurality of queues;
acquiring a packet fragment of a plurality of packet fragments of a packet, wherein a stream of a plurality of packets includes the packet;
identifying a particular queue of the plurality of queues for the particular packet fragment such that no already queued packet fragment in the particular queue comes after the particular packet fragment in the packet and the particular queue includes no already queued packet fragment of a packet subsequent to the particular packet in the stream of packets;
wherein said identifying the particular queue includes checking, at least when the particular queue is not empty, that the particular queue does not include a packet fragment which comes after the particular packet fragment in the packet or the stream of packets;
enqueuing the particular packet fragment at the end of the particular queue;
and updating a data structure to include an indication of the particular queue in relation to the position of the particular packet fragment in the packet and the stream of packets;
and
retrieving the plurality of packet fragments from the plurality of packet queues based on the data structure to produce the packet.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/812,207Filed 29 Mar 2004
Granted: 20 Jan 2009
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 47/34
Flow control; Congestion control: ensuring sequence integrity, e.g. using sequence numbers
H04L 47/43
Flow control; Congestion control: assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
H04L 49/90
Packet switching elements: buffering arrangements
H04L 49/9094
Replacing packets in a storage arrangement, e.g. pushout: arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing…