Exact match lookup with variable key sizes

1. A method for performing an exact match lookup in a network device, the method comprising:

receiving a network packet at the network device;

determining a lookup key for the network packet at least based on data included in a header of the received network packet;

performing two or more hash operations on the lookup key using two or more hash functions to compute two or more hashed lookup key segments; and

querying, using the two or more hashed lookup key segments, a database distributed among two or more memory banks to extract a value exactly corresponding to the lookup key, wherein querying the database includes

accessing the two or more memory banks using the two or more hashed lookup key segments to retrieve two or more matching segments, including a first matching segment and a second matching segment, from the two or more memory banks,

retrieving a pointer corresponding to the first matching segment, wherein the pointer points to the second matching segment,

determining, using the pointer, that the first matching segment and the second matching segment are to be combined, and

combining at least the first matching segment and the second matching segment that were retrieved from the two or more memory banks to identify a matching entry in the database, the value exactly corresponding to the lookup key being a value associated with the matching entry.

2. The method of claim 1 , wherein:

performing two or more hash operations includes performing N hash operations on the lookup key using N hash functions to compute N hashed lookup key segments, N being an integer greater than one; and

querying a database includes querying a database distributed among N memory banks, each of the N memory banks corresponding to a different one of the N hash functions.

3. The method of claim 1 , wherein:

querying the database further includes retrieving a key size indicator associated with at least one of the two or more matching segments; and

determining that at least the first matching segment and the second matching segment are to be combined at least using (i) the pointer and (ii) the key size indicator.

4. The method of claim 1 , wherein:

the pointer indicates a location, in the two or more memory banks, of the second matching segment.

5. The method of claim 1 , wherein determining that the first matching segment and the second matching segment are to be combined comprises:

determining that the first matching segment and the second matching segment are to be combined when the pointer corresponding to the first matching segment, stored in one of the two or more memory banks, points to the second matching segment, stored in another one of the two or more memory banks.

6. A network device comprising:

a plurality of interfaces;

a lookup memory storing a database distributed among two or more memory banks; and

a packet processor coupled to the plurality of interfaces, the packet processor being configured to process network packets received via at least some of the plurality of interfaces, wherein the packet processor comprises

a key generation unit configured to determine a lookup key for a network packet received via one of the plurality of interfaces at least based on data included in a header of the received network packet, and

a key search unit configured to

perform two or more hash operations on the lookup key using two or more hash functions to compute two or more hashed lookup key segments,

query the database, using the two or more hashed lookup key segments, to extract a value exactly corresponding to the lookup key, wherein the key search unit is configured to query the database at least by

accessing the two or more memory banks using the two or more hashed lookup key segments to retrieve two or more matching segments, including a first matching segment and a second matching segment, from the two or more memory banks,

retrieving a pointer corresponding to the first matching segment, wherein the pointer points to the second matching segment,

determining, using the pointer, that the first matching segment and the second matching segment are to be combined, and

combining at least the first matching segment and the second matching segment that were retrieved from the two or more memory banks to identify a matching entry in the database, the value exactly corresponding to the lookup key being a value associated with the matching entry.

7. The network device of claim 6 , wherein:

the lookup memory stores a database distributed among N memory banks, N being an integer greater than one; and

the key search unit is configured to perform the two or more hash operations at least by performing N hash operations on the lookup key using N hash functions to compute N hashed lookup key segments, each of the N hash functions corresponding to a different one of the N memory banks.

8. The network device of claim 6 , wherein the key search unit is configured to:

query the database further by retrieving a key size indicator associated with at least one of the two or more matching segments; and

determine that the at least the first matching segment and the second matching segment are to be combined at least using (i) the pointer and (ii) the key size indicator.

9. The network device of claim 6 , wherein:

the pointer indicates a location, in the two or more memory banks, of the second matching segment.

10. The network device of claim 6 , wherein the lookup memory is a static random access memory (SRAM).

11. The network device of claim 6 , wherein the key search unit is configured to:

determine that the first matching segment and the second matching segment are to be combined when the pointer corresponding to the first matching segment, stored in one of the two or more memory banks, points to the second matching segment, stored in another one of the two or more memory banks.