System and method for identifying data using parallel hashing

• US 7,069,268 B1
• Filed: 01/13/2003
• Issued: 06/27/2006
• Est. Priority Date: 01/13/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Burns, Barry S., Scott, Jeffery B.
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/341,971
• Time in Patent Office: 1,261 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 370/230, 370/235, 370/392, 370/401, 370/428, 711/165
• US Class Current: 707/770
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: Y10S 707/966 Distributed

Abstract

A method for identifying data is provided that includes receiving a data stream and performing a hashing operation on a portion of the data stream in order to identify a key that reflects an identity associated with the data stream. The method further includes storing a plurality of first and second hash table entries and comparing the key to the first and second hash table entries in order to evaluate if there is a match between the key and the first and second hash table entries.

Claims

1. An apparatus for identifying data, comprising:

a network element operable to receive a data stream, the network element including;

a processor; and

a memory element coupled to the processor, the memory element including a first hash table operable to store a plurality of first hash table entries and a second hash table operable to store a plurality of second hash table entries, wherein the processor performs a hashing operation on a portion of the data stream in order to identify a key that reflects an identity associated with the data stream, the key being used to generate a hash index used to correlate a match between the key and a selected one or more of the entries in the first and second hash tables, and wherein the memory element includes third, fourth, fifth, sixth, seventh, and eighth hash tables, each of which are operable to store multiple entries that may be compared to the key in order to evaluate if there is a match between the key and the entries in the hash tables.

2. The apparatus of claim 1, further comprising:

a hashed element included within the processor and operable to execute the hashing operation on the data stream in order to identify the key.

3. The apparatus of claim 2, wherein the hashed element stores a plurality of hashing operation algorithms, one or more of which correspond to each of the first and second hash tables included in the memory element.

4. The apparatus of claim 1, wherein a selected one of the hash tables is coupled to a linked list operable to provide internet protocol (IP) address information associated with the data stream when there are no matches found in the hash tables for the key.

5. The apparatus of claim 4, further comprising:

a database coupled to the linked list and operable to store IP address information associated with the data stream.

6. The apparatus of claim 1, wherein the width of each of the hash tables is one or more entries wide, each of the hash table entries in the hash tables including a key element and a data segment.

7. The apparatus of claim 1, wherein the match is used to identify one or more networking parameters for an entity associated with the data stream.

10. The method of claim 4, further comprising:

accessing a database coupled to the linked list in order to retrieve IP address information associated with the data stream when no match is found for the key.

8. A computer implemented method for identifying data, comprising:

receiving a data stream;

performing a hashing operation on a portion of the data stream in order to identify a key that reflects an identity associated with the data stream;

storing a plurality of first and second hash table entries;

comparing the key to the first and second hash table entries in order to evaluate if there is a match between the key and the first and second hash table entries; and

storing third, fourth, fifth, sixth, seventh, and eighth hash table entries, each of which are operable to be compared to the key in order to evaluate if there is a match between the key and the hash table entries.

9. The method of claim 8, wherein a selected one of the hash table entries are coupled to a linked list operable to provide internet protocol (IP) address information associated with the data stream when no match is found for the key.

11. The method of claim 8, wherein the hash table entries are stored in a plurality of hash tables, the width of each of the hash tables being one or more entries wide, each of the hash table entries in the hash tables including a key element and a data segment.

12. The method of claim 8, further comprising:

using the match to identify one or more networking parameters for an entity associated with the data stream.

13. The method of claim 8, further comprising:

invoking a selected one of a plurality of algorithms to perform the hashing operation such that the key is identified.

14. A system for identifying data, comprising:

a network element operable to receive a data stream, the network element including;

a processor;

a memory element coupled to the processor, the memory element including a first hash table operable to store a plurality of first hash table entries and a second hash table operable to store a plurality of second hash table entries, wherein the processor performs a hashing operation on a portion of the data stream in order to identify a key that reflects an identity associated with the data stream, the key being used to generate a hash index used to correlate a match between the key and one or more of the entries in the first and second hash tables, and wherein a hashed element is included within the processor and operable to execute the hashing operation on the data stream in order to identify the key, the hashed element storing a plurality of hashing operation algorithms, one or more of which correspond to each of the first and second hash tables included in the memory element; and

a database coupled to a linked list and operable to provide internet protocol (IP) address information associated with the data stream, wherein a selected one of the hash tables is coupled to the linked list that is operable to provide IP address information associated with the data stream when there are no matches found in the hash tables for the key.

15. The system of claim 14, wherein the memory element includes third, fourth, fifth, sixth, seventh, and eighth hash tables, each of which are operable to store multiple entries that may be compared to the key in order to evaluate if there is a match between the key and one or more of the entries in the hash tables.

16. The system of claim 14, wherein the width of each of the hash tables is one or more entries wide, each of the hash table entries in the hash tables including a key element and a data segment, and wherein the match is used to identify one or more networking parameters for an entity associated with the data stream.

17. A system for identifying data in an electronic processing environment, comprising:

means for receiving a data stream;

means for performing a hashing operation on a portion of the data stream in order to identify a key that reflects an identity associated with the data stream and that is used to generate a hash index;

means for storing a plurality of first and second hash table entries;

means for correlating the hash index to one or more of the first and second hash table entries in order to evaluate if there is a match between the key and the first and second hash table entries; and

means for providing storage that includes a linked list, the storage being operable to provide internet protocol (IP) address information associated with the data stream, wherein a selected one of the hash tables is coupled to the linked list that is operable to provide IP address information associated with the data stream when there are no matches found in the hash tables for the key.

18. A computer readable medium having code for identifying data, the code operable to:

receive a data stream;

perform a hashing operation on a portion of the data stream in order to identify a key that reflects an identity associated with the data stream;

store a plurality of first and second hash table entries;

compare the key to the first and second hash table entries in order to evaluate if there is a match between the key and the first and second hash table entries; and

provide storage that includes a linked list, the storage being operable to provide internet protocol (IP) address information associated with the data stream, wherein a selected one of the hash tables is coupled to the linked list that is operable to provide IP address information associated with the data stream when there are no matches found in the hash tables for the key.