Method and apparatus for hardware assisted TCP packet re-assembly

• US 6,963,921 B1
• Filed: 02/16/2001
• Issued: 11/08/2005
• Est. Priority Date: 02/16/2001
• Status: Expired due to Term

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Wang, Chi-Lie, Soh, Kap, Yang, Li-Jau, Mou, Chin-Li
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): BAYARD, DJENANE M
• Application Number:
  US09/785,015
• Time in Patent Office: 1,726 Days
• Field of Search: 709/230, 370/229, 370/235
• US Class Current: 709/230
• 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/12 Protocol engines
• 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/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A hardware packet accelerator parses incoming packets to retrieve header data for building a frame status and for verifying the incoming packets are part of an established connection with a host. The accelerator includes a connection database that allows retrieval of connection information based on an index constructed from a hashed TCP connection address. The frame status comprises information needed to perform packet re-assembly and is stored in a memory that is local (directly accessible) by a processing device that performs the packet re-assembly. Among other advantages, the processing device does not need to read packet header data from a packet buffer, saving large amounts of header data retrieval time.

Claims

1. A packet accelerator device, comprising:

a packet header parser configured to parse packet header fields from incoming packets directed toward a host;

a processing mechanism configured to perform packet re-assembly on packets determined to have valid connections with said host; and

an address filter configured to identify data parsed from said packet header fields needed for packet re-assembly and place that data in a local memory directly accessible by said processing mechanism;

wherein;

said address filter comprises,

a hashing mechanism configured to determine an index based on at least part of the parsed header fields,

a connection table containing connection information indexed by said hashing mechanism, and

a forward engine configured to,

retrieve connection table values from said connection table corresponding to the incoming packets and compare the retrieved connection table values with the incoming,

discard incoming packets that do not have matching connection information in said connection table,

forward the incoming packets to the processing mechanism for re-assembly if the incoming packets have matching connection information in said connection table, and

retrieve additional connection table values from said connection table when more than one connection has been stored by reference to said index; and

said connection table comprises a set of first connection address data, each first connection address data is stored at a hashed index location and includes a pointer that is either null, indicating the first connection address data is the only connection address saved at its corresponding hashed index location, or pointing to a next connection address data indicating a next connection address saved at a same hashed index.

2. The packet accelerator according to claim 1, wherein said processing mechanism is an embedded CPU within the packet accelerator.

3. The packet accelerator according to claim 1, wherein said processing mechanism is an embedded CPU within a router.

4. The packet accelerator according to claim 1, further comprising:

a frame status device configured to determine a frame status of an incoming frame of the incoming packet;

wherein said frame status comprises;

a frame pointer configured to point to a memory location of a packet buffer of the incoming frame;

at least one index/pointer field capable of being used to determine a connection address corresponding to the incoming packet;

segment data comprising information that identifies whether a full segment of packets corresponding to the incoming packet have been received;

sequence data identifying an order of the incoming frame within the segment corresponding to the incoming packet;

length of the incoming packet; and

an offset identifying a starting position of a payload of the incoming packet.

5. The packet accelerator according to claim 1, wherein:

said address filter identifies if the incoming packet is part of an established connection by performing a polynomial CRC calculation on a predetermined number of lower bits of a TCP connection address of said incoming packet, indexing into a connection table with the polynomial CRC calculation as an index, the connection table comprising a first valid connection for the index and a list of additional valid connections for the same index, and comparing the TCP connection to each of the first valid connection and each additional valid connection until a match is made.

6. The packet accelerator according to claim 5, wherein the connection table references two separate tables, the first table providing the TCP connection address for a primary connection and the second table comprising all secondary TCP connections hashed into a same index.

7. A method of accelerating packet re-assembly, comprising the steps of:

parsing a header fields of an incoming packet to determine data needed for packet re-assembly;

forwarding the packet to be re-assembled to a re-assembly mechanism;

placing the data needed for packet re-assembly in a local memory directly accessible by said re-assembly device; and

identifying if the incoming packet is part of an established connection with said host;

wherein;

said step of determining if the incoming packet is part of an established connection comprises the steps of;

hashing at least part of the parsed header fields to determine an index into a connection table;

retrieving connection information from the connection table based on said index;

comparing the connection information retrieved from the connection table to connection information from the parsed header fields;

if the connection information from the connection table matches the connection information from the parsed header fields, then, identifying the incoming packet as being part of an established connection with said host; and

if the connection information from the connection table does not match the connection information from the parsed header, then,

determining if any additional connection addresses are hashed into the connection table at said index, and

if additional connection address are hashed into the connection table at said index, then,

retrieving the additional connection addresses,

comparing the additional connection addresses to the connection information from the parsed header fields, and

if any of the additional connection addresses match the parsed header fields, identifying the incoming packet as being part of an established connection with said host.

8. The method according to claim 7, wherein:

said step of determining if any additional connection addresses are hashed into the connection table at said index comprises determining if a next pointer field at said index of the connection table is null, indicating no other connection addresses are hashed into the index, or, not null, indicating that additional connection addresses have been hashed into the connection table at the index; and

said step of retrieving the additional connection addresses comprises reading data pointed to by the next pointer field in the connection table at the index and each subsequent next pointer field of the read data.

9. The method according to claim 7, wherein said step of hashing comprises performing a polynomial CRC calculation on a predetermined number of lower bits of a TCP connection address of said incoming packet.

10. The method according to claim 9, wherein said predetermined number of lower bits comprises a number of bits needed to identify a number of connections supported by said host.