Method and apparatus for hardware packets reassembly in constrained networks

• US 7,991,007 B2
• Filed: 07/05/2005
• Issued: 08/02/2011
• Est. Priority Date: 10/29/2004
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Cheok, Yook Khai, Agarwal, Puneet
• Primary Examiner(s): Ferris; Derrick W
• Assistant Examiner(s): Cheng; Peter
• Application Number:
  US11/172,799
• Publication Number:
  US 20060106946A1
• Time in Patent Office: 2,219 Days
• Field of Search: 370/474, 370/394, 370/353, 370/392, 370/238, 370/395.1, 370/341, 370/400, 710/30
• US Class Current: 370/474
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• 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/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation

Abstract

A hardware packets reassembly apparatus and method includes an ingress unit receiving and parsing a data packet, recognizing fragments corresponding to the data packet, and outputting control information of the fragments. An en-queue unit stores the control information of each fragment, links each related fragment based on the control information, and enqueues the data packet when all fragments are available corresponding to the data packet, wherein the data packet is enqueued only when all of the fragments corresponding to the data packet are available in a sequential order. A dequeue unit dequeues the data packet from a packet descriptor, and scheduling the data packet based on a corresponding class of service. An egress unit assembles all fragments corresponding to the data packet into a full packet and outputting the assembled data packet from an output port.

Claims

1. A hardware packets reassembly apparatus, comprising:

an ingress unit configured to receive a plurality of fragments corresponding to a data packet, and configured to output forwarding control information associated with the plurality of fragments;

an en-queue unit configured to store the forwarding control information of each fragment from the plurality of fragments, and link related fragments from the plurality of fragments based on the forwarding control information,

the en-queue unit configured to store a descriptor of the data packet in a packet descriptor buffer in response to all fragments from the data packet being received in a sequential order, the en-queue unit configured to drop out-of-order fragments that are received in an order different from the sequential order until all fragments from the data packet are received in the sequential order;

a de-queue unit configured to schedule transmission of the plurality of fragments as a single unit based on the stored descriptor and based on a class of service, and configured to retrieve each fragment from the plurality of fragments based on the stored descriptor of the data packet, the descriptor including a pointer for each fragment from the plurality of fragments and the forwarding control information; and

an egress unit configured to assemble the plurality of fragments corresponding to the data packet into a full data packet.

2. The hardware packets reassembly apparatus as recited in claim 1, wherein the forwarding control information comprises at least one of a source address and a destination address, a fragment payload size, a fragment identity, a fragment payload offset, a source port and a destination port, an indicator of a class of service of the data packet, and a tunnel key.

3. The hardware packets reassembly apparatus as recited in claim 1, wherein the ingress unit is configured to identify whether a fragment from the plurality of fragments is received at the ingress unit based on the forwarding control information.

4. The hardware packets reassembly apparatus as recited in claim 1, wherein the ingress unit is configured to detect, in a hardware platform, whether a fragment from the plurality of fragments is received in the sequential order with respect to other fragments from the plurality of fragments, based on a fragment identifier and an offset associated with the fragment from the plurality of fragments.

5. The hardware packets reassembly apparatus as recited in claim 1, wherein the ingress unit is configured to process the forwarding control information related to a forwarding decision for the data packet and the en-queue unit.

6. The hardware packets reassembly apparatus as recited in claim 1, wherein the en-queue unit further comprises a fragment link buffer, the en-queue unit and the de-queue unit share a packet memory buffer and a packet descriptor, each forwarding control information of each fragment from the plurality of fragments is stored in the fragment link buffer, while a payload of the data packet defined by at least a portion of the plurality of fragments is stored in the packet memory buffer.

7. The hardware packets reassembly apparatus as recited in claim 6, wherein the fragment link buffer is configured to determine whether the plurality of fragments are received in the sequential order, check for fragments missing from the plurality of fragments, and an age of each of the fragments from the plurality of fragments when the plurality of fragments are stored in the fragment link buffer.

8. The hardware packets reassembly apparatus as recited in claim 7, wherein the fragment link buffer comprises a link buffer content-addressable memory (CAM) and link buffer random-access memory (RAM), and the fragment link buffer is configured to compare a field of an incoming fragment from the plurality of fragments with existing content inside the link buffer CAM.

9. The hardware packets reassembly apparatus as recited in claim 8, wherein when the comparison is a miss, a fragment offset is zero, and the link buffer CAM is not full, the fragment link buffer is configured to create a new entry insertion of the incoming fragment, the new entry insertion includes the source port/address and fragment identifier of the data packet, a valid bit representing that the entry is valid, and an age counter value.

10. The hardware packets reassembly apparatus as recited in claim 8, wherein when the comparison is a miss, a fragment offset is non-zero, the incoming fragment is dropped, the payload corresponding with the incoming fragment is not stored, and the link buffer RAM is not updated.

11. The hardware packets reassembly apparatus as recited in claim 8, wherein when the comparison is a hit and a fragment offset is zero, the fragment link buffer sends an indicator representing that an older first fragment is stored in the link buffer CAM.

12. The hardware packets reassembly apparatus as recited in claim 8, wherein when the comparison is a hit and a fragment offset is non-zero, the incoming fragment is dropped, the payload corresponding with the incoming fragment is stored as an additional fragment, and the link buffer RAM is not updated.

13. The hardware packets reassembly apparatus as recited in claim 8, wherein when the comparison is a hit and the incoming fragment offset is non-zero, the plurality of fragments are determined to be received in the sequential order and configured to be reassembled.

14. The hardware packets reassembly apparatus as recited in claim 8, further comprising:

an aging counter counting a time period from when the incoming fragment is received to a threshold level where the link buffer entry corresponding to the incoming fragment is aged and invalidated and the aging counter resets itself for a next insertion of the link buffer entry.

15. The hardware packets reassembly apparatus as recited in claim 1, wherein the de-queue unit comprises a scheduler configured to select and schedule output of linked shim headers and the plurality of fragments to the egress unit.

16. The hardware packets reassembly apparatus as recited in claim 1, wherein the egress unit is configured to assemble the plurality of fragments by adding additional fields to a Packet Link RAM to store context for more than one of the plurality of fragments.

17. The hardware packets reassembly apparatus as recited in claim 1, wherein the en-queue unit includes a plurality of fragment link buffers, each fragment link buffer from the plurality of fragment link buffers is associated with a different class of service.

18. The hardware packets reassembly apparatus as recited in claim 1, wherein the descriptor includes a packet header field, a packet control field, a fragment field, and a destination port field, at least a portion of the descriptor is defined based on the forwarding control information.

19. A hardware packets reassembly method, comprising:

receiving a plurality of fragments corresponding to a data packet, and outputting forwarding control information associated with the plurality of fragments;

storing the forwarding control information of each fragment from the plurality of fragments;

linking related fragments from the plurality of fragments based on the forwarding control information;

storing a descriptor of the data packet in a packet descriptor buffer in response to all fragments from the data packet being received in a sequential order;

dropping out-of-order fragments received in an order different from the sequential order until all fragments from the data packet are received in the sequential order;

scheduling transmission of the plurality of fragments as a single unit based on the stored descriptor and based on a class of service;

retrieving each of the plurality of fragments based on the stored descriptor of the data packet, the descriptor including a pointer for each fragment from the plurality of fragments and the forwarding control information; and

assembling the plurality of fragments corresponding to the data packet into a full packet.

20. A hardware packets reassembly apparatus, comprising:

means for receiving a plurality of fragments corresponding to a data packet, and outputting forwarding control information associated with the plurality of fragments;

means for storing the forwarding control information of each fragment from the plurality of fragments, linking related fragments from the plurality of fragments based on the forwarding control information, for storing a descriptor of the data packet in a packet descriptor buffer in response to all fragments from the data packet, being received in a sequential order, and for dropping out-of-order fragments received in an order different from the sequential order until all fragments from the data packet are received in the sequential order;

means for scheduling transmission of the plurality of fragments as a single unit based on the stored descriptor and based on a class of service, and for retrieving each of the plurality of fragments based on the stored descriptor of the data packet, the descriptor including a pointer for each fragment from the plurality of fragments and the forwarding control information; and

means for assembling the plurality of fragments corresponding to the data packet into a full packet.