Lookups by collisionless direct tables and CAMS

• US 7,349,397 B2
• Filed: 08/03/2006
• Issued: 03/25/2008
• Est. Priority Date: 05/13/2002
• Status: Expired due to Term

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Herkersdorf, Andreas Guenther, Jeffries, Clark Debs, Davis, Gordon Taylor, Rinaldi, Mark Anthony
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): Scheibel; Robert C
• Application Number:
  US11/462,071
• Publication Number:
  US 20060265372A1
• Time in Patent Office: 600 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A structure and technique for preventing collisions using a hash table in conjunction with a CAM to identify and prevent collisions of binary keys. A portion of the hash value of a binary key, which does not collide with a portion of the hash value of any other reference binary key, is used as an entry in the hash table. If two or more binary keys have identical values of the portions of the hash values, each of these binary keys are stored in their entirety, in the CAM. The key in the CAM provides a pointer to a data structure where the action associated with that binary key is stored. If the binary key is not found in the CAM, the binary key is hashed, and a specific entry in the hash table is selected using a portion of this hash value.

Claims

1. A method of preventing collisions between two or more binary keys wherein each binary key corresponds to an action to be taken, comprising the steps of:

providing a hash table having a plurality of entries, each entry associated with a binary key and indexed by a selected portion of a hash value of said associated binary key, each entry pointing to a location in a data structure for storing the non-selected portion of, or the entire hash value of, the binary key and action data corresponding to the value of the binary key, and a content addressable memory (CAM) having a plurality of entries, each configured to store a binary key, or a value unique to a binary key, and an association to a corresponding action associated therewith;

storing in said hash table a pointer to said data structure using a selected one portion of a first hash value of a first binary key as an index into the hash table when and only when a selected one portion of the first hash value is not the selected one portion of the hash value of any other binary key, and storing in the CAM the first binary key or a value unique to the first binary key, and establishing an association between the associated CAM entry location and a location of an associated data structure, when and only when the selected portion of the first hash value of the first binary key is the same as the selected portion of the hash value of one or more other binary keys;

presenting a second binary key for insertion into one of the hash table and the CAM;

creating a second hash value of the second binary key;

searching the hash table using a first portion of the second hash value;

detecting that the hash table includes an entry indexed by the first portion of the second hash value for a third binary key;

creating an entry in the CAM indexed by the second binary key;

creating an entry in the CAM indexed by the third binary key; and

deleting the entry in the hash table indexed by the first portion of the second hash value.

2. The invention as defined in claim 1 further characterized by:

presenting a binary key for action;

searching the CAM to see if the binary key is stored in said CAM;

if said binary key is found, using established association with said data structure in order to access the action data associated therewith;

hashing the binary key and accessing an entry in the hash table using a portion of resulting hashed binary key as an index into said hash table to determine if the selected entry of the hash table is valid;

if the entry is valid, then pointing to said data structure in order to access the action data associated therewith.

3. The invention as defined in claim 1 wherein said CAM and said hash table are searched simultaneously.

4. The invention as defined in claim 1 wherein said CAM is searched first, and said hash table is searched if and only if the value of the second binary key is not found in the CAM.

5. The invention as defined in claim 1 wherein said second binary key is stored unaltered in the CAM.

6. The invention as defined in claim 2 wherein said second binary key is stored unaltered in the CAM.

7. The invention as defined in claim 3 wherein said second binary key is stored unaltered in the CAM.

8. The invention as defined in claim 4 wherein said second binary key is stored unaltered in the CAM.

9. The invention as defined in claim 1 wherein said action is stored in the CAM.

10. The invention as defined in claim 1 wherein said action is directed by an offset value in said CAM location.

11. A method for preventing collisions between two or more binary keys wherein each binary key corresponds to an action to be taken, comprising:

providing a hash table having a plurality of entries, each entry associated with a binary key and indexed by a selected portion of a hash value of said associated binary key, each entry pointing to a location in a data structure for storing the non-selected portion of, or the entire hash value of, the binary key and action data corresponding to the value of the binary key;

providing a content addressable memory (CAM) having a plurality of entries, each configured to store a binary key, or a value unique to a binary key, and an association to a corresponding action associated therewith;

each entry in said hash table having an entry and a pointer to said data structure using a selected one portion of a first hash value of a first binary key as an index into the hash table when and only when a selected one portion of the first hash value is not the selected one portion of the hash value of any other binary key using said CAM and hash table to prevent collision of any binary keys;

presenting a second binary key for insertion into one of the hash table and the CAM;

creating a second hash value of the second binary key;

searching the hash table using a first portion of the second hash value;

detecting that the hash table includes an entry indexed by the first portion of the second hash value for a third binary key;

creating a first entry in the CAM indexed by the second binary key and storing a pointer to a data structure corresponding to the first entry;

creating a second entry in the CAM indexed by the third binary key and storing a pointer to a data structure corresponding to the second entry; and

deleting the entry in the hash table indexed by the first portion of the second hash value and data corresponding to the entry.

12. The invention as defined in claim 11 wherein said value stored in the CAM is the unaltered value of each key.

13. The invention as defined in claim 11 wherein said action related to each entry in said CAM is stored in said CAM.

14. The invention as defined in claim 12 wherein said action related to each entry in said CAM is stored in said CAM.

15. The invention as defined in claim 11 wherein said action related to each entry in said CAM is designated by an offset.

16. The invention as defined in claim 12 wherein said action related to each entry in said CAM is designated by an offset.