Data matching using flow based packet data storage

• US 8,755,381 B2
• Filed: 08/02/2006
• Issued: 06/17/2014
• Est. Priority Date: 08/02/2006
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silver Peak Systems Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Hughes, David Anthony, Burns, John, Yin, Zhigang
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): VU, HOANG-CHUONG Q
• Application Number:
  US11/498,473
• Publication Number:
  US 20080031240A1
• Time in Patent Office: 2,876 Days
• Field of Search: 370/395.32, 370/389, 370/392, 707/205, 711/216
• US Class Current: 370/392
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing
• 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/22 Parsing or analysis of headers

Abstract

A system for processing packets includes a communications interface and a processor. A communications interface receives a packet between a source and a destination. The processor identifies a flow between the source and the destination based on the packet. The processor determines whether some of packet data of the packet matches to storage data in storage using hashes. The processor then stores the packet data in a block of memory in the storage based on the flow and if the packet data does not match the storage data.

Claims

1. A system for processing packets, the system comprising:

a communications interface configured to receive a plurality of packets at a network device between a source and a destination, each of the packets including data and flow information; and

a processor configured to identify a flow between the source and the destination based on the flow information in each of the plurality of packets to determine whether at least a portion of the data from the received plurality of packets indicates a potential match to data in storage using hashes, to remove a header from each of the plurality of packets if no indication is found of a potential match to data in storage, to store the data from each of the plurality of packets with the removed header in a block of memory allocated for the flow, wherein the allocated block of memory comprises a page of contiguous memory and the storage includes both fast memory and slow memory used to process the flow, to retrieve a list of possible data matches, to use a computed hash index to index a hash table for the data, to determine match sizes of the most likely data match and second most likely data match, to store the data from the most likely data match and second most likely data match in the block of memory allocated for the flow if both match sizes are small, and to generate a retrieve instruction with the computed hash index of the data for the match with the larger match size if at least one match size is not small.

2. The system of claim 1 wherein the processor is configured to move the storage data between the fast memory and the slow memory.

3. The system of claim 1 wherein the flow comprises a session between the source and the destination.

4. The system of claim 1 wherein the processor is configured to retrieve a hash state of the hashes for the flow.

5. The system of claim 1 wherein the processor is configured to determine the hashes for the flow.

6. The system of claim 1 wherein the processor is configured to store a hash state of the hashes for the flow.

7. The system of claim 1 wherein the processor is configured to update the hash table with the hashes.

8. The system of claim 1 wherein the hashes are rolling.

9. The system of claim 1 wherein the processor is configured to allocate the block of the memory for the identified flow.

10. The system of claim 1 wherein the processor is configured to transmit the packet data.

11. The system of claim 1 wherein the block of memory allocated for the flow is allocated from a list of partially filled blocks of memory.

12. A method for processing packets, the method comprising:

receiving a plurality of packets at a network device between a source and a destination, each of the packets including data and flow information;

identifying a flow between the source and the destination based on the flow information in each of the plurality of packets;

determining whether at least a portion of the data from the received plurality of packets indicates a potential match to data in storage using hashes;

retrieving a list of possible data matches;

using a computed hash index to index a hash table for the data;

determining match sizes of the most likely data match and second most likely data match;

storing the data from the most likely data match and second most likely data match in a block of memory designated for the flow, if both match sizes are small;

generating a retrieve instruction with the computed hash index of the data for the match with the larger match size, if at least one match size is not small;

removing a header from each of the plurality of packets if no indication is found of a potential match to data in storage; and

storing the data from each of the plurality of packets with the removed header in a block of memory allocated for the flow, wherein the allocated block of memory comprises a page of contiguous memory and the storage includes both fast memory and slow memory used to process the flow.

13. The method of claim 12 further comprising moving the storage data between the fast memory and the slow memory.

14. The method of claim 12 wherein the flow comprises a session between the source and the destination.

15. The method of claim 12 further comprising retrieving a hash state of the hashes for the flow.

16. The method of claim 12 further comprising determining the hashes for the flow.

17. The method of claim 12 further comprising storing a hash state of the hashes for the flow.

18. The method of claim 12 further comprising updating the hash table with the hashes.

19. The method of claim 12 wherein the hashes are rolling.

20. The method of claim 12 further comprising allocating the block of the memory for the identified flow.

21. The method of claim 12 further comprising transmitting the packet data.

22. The method of claim 12 further comprising:

allocating the block of memory for the identified flow from a list of partially filled blocks of memory.

23. A software product for processing packets, the software product comprising:

software operational when executed by a processor to direct the processor to receive a plurality of packets at a network device between a source and a destination, each of the packets including data and flow information, to identify a flow between the source and the destination based on the flow information in each of the plurality of packets, to determine whether at least a portion of the data from the received plurality of packets indicates a potential match to data in storage using hashes, to retrieve a list of possible data matches, using a computed hash index to index a hash table for the data, to determine match sizes of the most likely data match and second most likely data match, to store the data from the most likely data match and second most likely data match in the block of memory allocated for the flow if both match sizes are small, to generate a retrieve instruction with the computed hash index of the data for the match with the larger match size if at least one match size is not small, to remove a header from each of the plurality of packets if no indication is found of a potential match to data in storage, and to store the data from each of the plurality of packets with the removed header in a block of memory allocated for the flow, wherein the allocated block of memory comprises a page of contiguous memory and the storage includes both fast memory and slow memory used to process the flow; and

a non-transitory computer-readable storage medium configured to store the software.

24. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to move the storage data between the fast memory and the slow memory.

25. The software product of claim 23 wherein the flow comprises a session between the source and the destination.

26. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to retrieve a hash state of the hashes for the flow.

27. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to determine the hashes for the flow.

28. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to store a hash state of the hashes for the flow.

29. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to update the hash table with the hashes.

30. The software product of claim 23 wherein the hashes are rolling.

31. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to allocate the block of the memory for the identified flow.

32. The software product of claim 23 wherein the software is operational when executed by the processor to direct the processor to transmit the packet data.

33. The software product of claim 23 wherein the block of memory allocated for the flow is allocated from a list of partially filled blocks of memory.