Pattern Matching In A Network Flow Across Multiple Packets

• US 20090028143A1
• Filed: 09/12/2007
• Published: 01/29/2009
• Est. Priority Date: 07/26/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Guntur, Ravindra, ESWARAN, Anand
• Granted Patent: US 7,873,054 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports

Abstract

Pattern matching for a network flow includes storing a representation of the pattern. The representation of the pattern includes hash values representing blocks of data in the pattern. Hash values are calculated for blocks of data in the network flow. The blocks of data are spread across multiple packets in the network flow. The calculated hash values for the blocks of data in the network flow are compared to the hash values in the representation of the pattern to detect the pattern in the network flow.

Claims

1. A method of matching a pattern in a network flow across multiple packets, the method comprising:

storing a representation of the pattern, wherein the representation includes a plurality of hash values each representing a block of data in the pattern;

receiving a network flow including a stream of packets;

calculating hash values for blocks of data in the network flow, wherein the blocks of data are spread across multiple packets in the stream of packets; and

comparing the calculated hash values for the blocks of data in the network flow to the hash values in the representation of the pattern to detect the pattern in the network flow.

2. The method of claim 1, wherein storing a representation of the pattern comprises:

storing hash values for only a subset of all the blocks of data in the pattern.

3. The method of claim 2, wherein the subset of all the blocks of data comprises a starting block of data and an ending block of data in the pattern.

4. The method of claim 1, further comprising:

storing a count of all the blocks of data in the pattern.

5. The method of claim 4, further comprising:

determining a count of the blocks of data in the network flow for which the hash values are calculated; and

comparing the determined count to the stored count of all the blocks of data in the pattern to detect the pattern.

6. The method of claim 1, wherein the blocks of data in the network flow are consecutive blocks of data spread across the multiple packets.

7. The method of claim 6, wherein the blocks of data are overlapping blocks of data.

8. The method of claim 1, further comprising:

wherein storing a representation of the pattern comprises storing the representation of the pattern in a first content addressable memory;

storing the calculated hash values in a second content addressable memory; and

detecting the pattern in the network flow at line-rate speed by retrieving data from the first and second content addressable memories for comparison.

9. A method of detecting a pattern across multiple packets in a network flow using a plurality of hash values and data block counts, the method comprising:

storing a representation of the pattern, wherein the representation includes a first hash value representing a starting block of data in the pattern and a last hash value representing an ending block of data in the pattern, and the representation includes a count of all the blocks of data in the pattern;

receiving a network flow including a stream of packets;

calculating hash values for a plurality of blocks of data in the network flow;

determining a count of the blocks of data in the network flow for which the hash values are calculated; and

detecting the pattern in the network flow if

a first calculated hash value of the calculated hash values matches the first hash value representing a starting block of data in the pattern,

a last calculated hash value of the calculated hash values matches the last hash value representing the ending block of data in the pattern, and

the determined count of the blocks of data in the network flow for which the hash values are calculated equals the count of all the blocks of data in the pattern.

10. The method of claim 9, further comprising:

receiving a packet in the network flow;

calculating the first hash value from a block of data in the packet;

determining whether the first calculated hash value matches the first hash value representing the starting block of data in the pattern;

if the first calculated hash value does not match the first hash value representing the starting block of data in the pattern, then calculating another hash value from a next consecutive block of data from the first packet or from the first and a second consecutive packet in the network flow for comparison to the first hash value representing the starting block of data in the pattern.

11. The method of claim 10, further comprising:

if the first calculated hash value matches the first hash value representing the starting block of data in the pattern, then

calculating a next hash value from a next consecutive block of data from the first packet or from the first and a second packet in the network flow, and

decrementing a counter representing a count of blocks in the pattern.

12. The method of claim 11, further comprising:

determining whether the counter equals zero;

if the counter equals zero, then determining whether the calculated next hash value equals a hash of the ending block in the pattern; and

if the next hash value equals the hash of the ending block in the pattern, then determining the pattern is detected.

13. The method of claim 12, wherein if the counter does not equal zero, then repeating calculating a next hash value from a next consecutive block of data in the network flow, and decrementing the counter representing the count of blocks in the pattern until the counter equals zero;

and

when the counter equals zero, determining whether the calculated hash value equals the hash of the ending block in the pattern to determine whether the pattern is detected.

14. The method of claim 12, wherein if the next hash value does not equal the hash of the ending block in the pattern, then determining the pattern is not detected.

15. The method of claim 9, wherein a same hash function is used to calculate the hash values for the plurality of blocks of data in the network flow and the hash values for the pattern.

16. A pattern detection system operable to detect a pattern in a network flow, the system comprising:

at least one memory storing a representation of the pattern, wherein the representation includes a plurality of hash values each representing a block of data in the pattern;

a hash unit calculating hash values for blocks of data in the network flow, wherein the blocks of data are spread across multiple packets in the stream of packets; and

a pattern detection unit comparing the calculated hash values for the blocks of data in the network flow to the hash values in the representation of the pattern to detect the pattern in the network flow.

17. The system of claim 16, wherein the at least one memory comprises at least one content addressable memory storing the representation of the pattern and the calculated hash values, and the pattern detection unit is operable to detect a pattern in the network flow by accessing the hash values stored in the at least one content addressable memory.

18. The system of claim 17, wherein the pattern detection system including the at least one content addressable memory are provided in a line card in a network switch, and the pattern detection system is operable to detect the pattern in the network flow at a line-rate speed.

19. The system of claim 18, wherein the pattern detection system receives packets in the network flow at the line-rate speed from at least one network port in the line card.

20. The system of claim 16, wherein the plurality of hash values in the representation of the pattern only include hash values for a starting block of data and an ending block of data in the pattern.