Lookups by collisionless direct tables and CAMs

• US 7,116,664 B2
• Filed: 05/13/2002
• Issued: 10/03/2006
• Est. Priority Date: 05/13/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark Debs, Davis, Gordon Taylor, Rinaldi, Mark Anthony, Herkersdorf, Andreas Guenther
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): SCHEIBEL, ROBERT C
• Application Number:
  US10/144,610
• Publication Number:
  US 20030210689A1
• Time in Patent Office: 1,604 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 indexed by a selected portion of hash values of said binary keys, each entry pointing to a location in a data structure for storing the non-selected portions of, or the entire hash value of, the binary key and action data corresponding to the value of the binary key, and a contact 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 the hash values of binary keys as an index into the hash table when and only when said selected one portion of the hash value is not the selected one portion of the hash value of any other binary key, and storing in the CAM binary keys or values unique to said binary keys, and establishing an association between said CAM entry locations and locations of said data structures, when and only when the selected portion of the hash value of any such binary key is the same as the selected portion of the hash value of one or more other binary keys, and wherein deletion of an entry from the hash table or CAM is accomplished by;

seeking the binary key in the CAM and, if found, then deleting this key and ending the program;

if the key is not found, then seek the selected portion of the hash value in the hash table, if a match is not found, end program;

if a match is found, compare the remainder of hash value,

if a match is found, delete portion of hash value from hash table;

if a match is not found, end program.

2. 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 indexed by a selected portion of hash values of said binary keys, each entry pointing to a location in a data structure for storing the non-selected portions of, or the entire hash value of, the binary key and action data corresponding to the value of the binary key, and a contact 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 the hash values of binary keys as an index into the hash table when and only when said selected one portion of the hash value is not the selected one portion of the hash value of any other binary key, and storing in the CAM binary keys or values unique to said binary keys, and establishing an association between said CAM entry locations and locations of said data structures, when and only when the selected portion of the hash value of any such binary key is the same as the selected portion of the hash value of one or more other binary keys, and wherein an insertion of a new value in the CAM or hash table is accomplished by;

seeking the value of the binary key in the cam;

if the value is found, overwriting the key and associated action and the program ended;

if the key is not found in the CAM, the key is hashed, the selected hash value is sought in the hash table, if the selected value is not found in the hash table, the selected value is written in the hash table with a pointer to the action and the remainder of the hash value, and the program is ended;

if the selected portion of hash value is stored in the hash table with a pointer to the remainder of the hash value, the action is updated and the program ended;

if the remainder of the hash value is different corresponding to a different action, then enter the key of the selected portion of the hash value being compared into the CAM with the associated activity, recreate the key from the hash value stored in the hash table and action, and enter the recreated key in the CAM and associated action and end the program.