System and process for GHIH-speed pattern matching for application-level switching of data packets

• US 6,430,184 B1
• Filed: 04/10/1998
• Issued: 08/06/2002
• Est. Priority Date: 04/10/1998
• Status: Expired due to Fees

• Current Assignee: Top Layer Networks, Inc. (Corero Network Security Plc)
• Original Assignee: Top Layer Networks, Inc. (Corero Network Security Plc)
• Inventors: Robins, Cary B., Narayanaswamy, Krishna, Spinney, Barry A., Ross, Theodore L.
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Phunkulh, Bob A.
• Application Number:
  US09/058,597
• Time in Patent Office: 1,579 Days
• Field of Search: 370/389, 370/392, 370/394, 370/400, 370/411, 370/401, 370/465, 370/466, 370/467, 370/469, 370/428, 370/429, 709/230, 709/231, 709/232, 709/238
• US Class Current: 370/392
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A process and system for switching connections of data packet flows between nodes of data processing system networks operating on diverse protocols according to the application layer information on the data packets. The process retrieves and hashes the header information to from an index into memory where a flow tag pointer is stored. The flow tag points to flow switching information that directs the forwarding of the packet. The switching information is sent along with the packet data to direct the forwarding state information about the flow is updated in the flow switching information. The hash function includes a multiplication and division by polynomials forming a hash result and a signature result. Both hash and signature are used to ensure that the information retrieved is valid. If invalid, The pre hashed header information is parsed to determine the forwarding information. This forwarding information is stored for later use and the appropriate flow tag pointer is stored in the hash result index.

Claims

1. A method for creating, identifying, retrieving and storing the flow path switching information of a packet of information bytes comprising the steps of:

(a) retrieving the header of the packet,

(b) selecting a programmable subset of said header bytes,

(c) hashing said subset to form a hash result,

(d) second hashing of the header to form a signature value,

(e) selecting portions of said hash result to form an index into a memory,

(f) determining whether there is a valid flow tag at said index,

(g) if there is no valid flow tag, then

(g) (1) decoding the header of the packet to determine a forwarding flow path,

(g) (2) creating a flow tag pointer for the packet, said flow tag pointer having a destination in a flow table,

(g) (3) storing the flow tag pointer at said index,

(g) (4) storing said signature value at said index,

(g) (5) storing said forwarding flow path in said flow table at said flow tag pointer, and

(g) (6) forwarding the packet,

(h) if there is a valid flow tag, then

(h) (1) comparing said signature value to a stored signature value at said index; and

,

(h) (2) if said signature value matches said stored signature value, following a stored flow tag pointer at said index to stored flow information in said flow table and forwarding the packet according to said stored flow information.

2. A method for creating, identifying, retrieving and storing the flow path switching information of a data packet comprising the steps of:

(a) selecting a programmable subset of header bytes from the data packet,

(b) hashing said subset to form a hash result,

(c) second hashing of said subset to form a signature value,

(d) selecting portions of said hash result to form an index into a memory,

(e) determining whether there is a valid flow tag at said index,

(f) if there is no valid flow tag, then

(f) (1) decoding the header of the packet to determine a forwarding flaw path,

(f) (2) creating a flow tag pointer for the packet, said flow tag pointer having a destination in a flow table,

(f) (3) storing the flow tag pointer and said signature value at said index,

(f) (4) storing said forwarding flow path in said flow table at said flow tag pointer, and

(f) (5) forwarding the packet,

(g) if there is a valid flow tag, then

(g) (1) comparing said signature value to a stored signature value at said index;

(g) (2) if said signature value matches said stored signature value, following a stored flow tag pointer at said index to stored flow information in said flow table and forwarding the packet according to said stored flow information,

(h) receiving a second packet having similar relevant header bytes as the previous packet in the flow path, and

(i) performing steps (a) and (g) thereby determining a second forwarding path.

3. The method of claim 2 wherein step (b) further comprises the steps of:

(b) (1) forming an ordered set from said selected number of bytes,

(b) (2) multiplying said ordered set by a random polynomial to form a product polynomial,

(b) (3) choosing an irreducible and primitive polynomial, and

(b) (4) dividing said product polynomial by said irreducible and primitive polynomial forming a remainder polynomial, wherein said remainder is the hash result.

4. The method of claim 3 wherein step (d) further comprises the steps of:

(c) (1) multiplying said order set by a second random polynomial to form a second product polynomial,

(c) (2) dividing said second product polynomial by said irreducible and primitive polynomial forming a remainder polynomial to form the signature value,

(c) (3) storing the signature value,

wherein comparing said stored signature value to a signature value from a second verifies that the flow tag pointer is valid.

5. The method of claim 2 further comprising the steps of:

(j) retrieving several additional packet headers in sequence,

(k) processing the additional packet headers by

(l) pipelining the steps (a)-(g) as applied to all said headers of the packets sequentially, wherein the processing steps of the packets overlap each other but are offset in time.

6. A method for identifying, and retrieving the flow path switching information of a packet of information comprising the steps of:

retrieving the header of the packet,

selecting one or more header bytes from the header,

forming an ordered set of said selected header bytes,

multiplying the header with a polynomial to form a first result,

dividing the first result by another polynomial to form the hash result,

multiplying said ordered set by a second random polynomial forming a second product polynomial,

dividing said second product polynomial by an irreducible and primitive polynomial forming a remainder polynomial to form the signature value,

comparing stored signature values with presently calculated signatures values to determine that said flow tag pointer is valid,

selecting portions of the hash result to form an index into memory,

retrieving a valid flow tag pointer from the memory contents at the index,

verifying the validity of the flow tag pointer by comparing the calculated signature value with a previously stored signature value,

retrieving switching information stored in a flow table at the selected flow tag pointer destination, and,

forwarding the packet according to said retrieved switching information.

7. A method for forming an index into an information field from an incoming byte stream comprising the steps of:

selecting a programmable never of said bytes at programmable byte positions,

forming an ordered set from said number of bytes;

multiplying said ordered set by a random polynomial forming a product polynomial,

forming an irreducible and primitive polynomial,

dividing said product polynomial by said irreducible and primitive polynomial forming a remainder polynomial, referred to as a hash result, and

forming said index by selecting portions of said hash result.

8. The method as defined in claim 7 for forming an index further comprising the steps of:

multiplying said ordered set by a second random polynomial forming a second product polynomial,

dividing said second product polynomial by said irreducible and primitive polynomial forming a remainder polynomial to form a signature value,

comparing said signature value to a signature value previously stored in the index to determine that said index is valid.

9. The method as defined in claim 8 wherein the step of forming the signature value includes calculations involving lossy compressions including CRC'"'"'s and checksums, and

storing the signature value as part of the hash result.

10. The method of claim 8 further comprising the step of using the signature value as a hash key directly to increase the confidence of a non-aliased hash result.

11. Apparatus for determining whether a presently received data packet is part of a flow initiated by a previously received data packet, said apparatus comprising:

(a) a trash preprocessor having an input of a portion of said presently received data packet and an output of a hash result, said hash preprocessor to (i) select a programmable number of bytes of said portion of said data packet at programmable byte positions, (ii) form an ordered set from said number of bytes, (iii) multiply said ordered set by a random polynomial to form a product polynomial, (iv) form an irreducible and primitive polynomial, (v) divide said product polynomial by said irreducible and primitive polynomial to form a remainder polynomial to produce said hash result; and

(b) a comparator having inputs of said hash result and a corresponding hash result of said previously received data packet, and having an output tagging said presently received data packet as part of said flow if and only if there is a match.

12. The apparatus of claim 11 further comprising a second hash preprocessor having an input of a larger portion of said presently received data packet and an output of a signature value, which is compared to the corresponding signature value of a corresponding portion of said presently received data packet wherein said second hash preprocessor (vi) multiplies said ordered set by a second random polynomial to form a second product polynomial and (vii) divides said second product polynomial by said irreducible and primitive polynomial to form a remainder polynomial to produce said signature value.

13. The apparatus of claim 12 wherein said comparator comprises:

(a1) a memory with a plurality of indexed locations exactly one of which includes said signature value of said previously received data packet, (a2) a pointer to said indexed locations set by a portion of said hash result, and (a3) a comparator with inputs including (i) said signature value of said presently received data packet and (ii) corresponding information contained in that of said memory locations pointed to by said pointer; and

an output determining said tagging only if there is a match of said inputs.

14. Apparatus for determining whether a presently received data packet is part of a flow initiated by a previously received data packet, said apparatus comprising:

(a) a hash preprocessor having an input of a portion of said presently received data packet and an output of a hash result;

said hash preprocessor to (i) select a programmable number of bytes of said portion of said data packet at programmable byte positions, (ii) form an ordered set from said number of bytes, (iii) multiply said ordered set by a random polynomial to form a product polynomial, (iv) forms an irreducible and primitive polynomial, (v) divide said product polynomial by said irreducible and primitive polynomial to form a remainder polynomial to produce said hash result;

(b) a comparator having inputs of said hash result and a corresponding hash result of said previously received data packet, and having an output tagging said presently received data packet as part of said flow if and only if there is a match; and

(c) a second hash processor having an input of a larger portion of sand presently received data packet and an output of a signature value, which is compared to the corresponding signature value of a corresponding portion of said presently received data packet, said second hash preprocessor to (i) select a programmable number of bytes of a portion of said data packet at programmable byte positions, (ii) form an ordered set from said number of bytes, (iii) multiply said ordered set by a random polynomial to form a product polynomial, (iv) form an irreducible and primitive polynomial, and (v) divide said product polynomial by said irreducible and primitive polynomial to to form a remainder polynomial to produce said signature value.