Hash collision resolution with key compression in a MAC forwarding data structure

• US 8,312,066 B2
• Filed: 11/30/2010
• Issued: 11/13/2012
• Est. Priority Date: 11/30/2010
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Alleyne, Brian, Lakshmikanthan, Ramanathan, Jagannathan, Rajesh
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US12/957,301
• Publication Number:
  US 20120136889A1
• Time in Patent Office: 714 Days
• Field of Search: 707/899, 709/242, 726/13
• US Class Current: 707/899
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

Embodiments of the invention include a method performed in a media access control (MAC) forwarding control module within a network element for looking up a MAC address and interface (I/F) identifier pair (MAC-I/F pair) from a MAC forwarding data structure that comprises a first tier data structure and a plurality of second tier data structures. The MAC forwarding data structure utilizes compressed keys to index each of the plurality second tier data structures. The compressed key is generated with a desired MAC address and a mask bit list that corresponds with enough bit positions such that all MAC addresses in second tier data structure can be uniquely addressed with just the values of each MAC address in the bit positions listed. As such, the MAC forwarding data structure is constructed so that the total cost of a lookup with the compressed key technique is deterministic and, therefore, O(1).

Claims

1. A method performed by a network element including a media access control (MAC) forwarding control module that looks up MAC address and interface (I/F) identifier pairs (MAC-I/F pairs) stored in a MAC forwarding data structure, the method comprising the steps of:

receiving at a physical port of the network element a packet that was sent by another network element and that includes a MAC address to lookup in the MAC forwarding data structure;

generating a first tier hash index from the received MAC address with a first hash function;

accessing a first tier bucket in a first tier data structure at the first tier hash index;

determining the first tier bucket'"'"'s contents;

in the case that the first tier bucket contains a null, returning a null;

in the case that the first tier bucket contains one of the MAC-I/F pairs, retrieving the MAC-I/F pair from the first tier bucket, comparing the received MAC address to the retrieved MAC-I/F pair'"'"'s MAC address and;

in the case that the received MAC address matches the MAC-I/F pair'"'"'s MAC address, returning the retrieved MAC-I/F pair'"'"'s interface identifier, wherein the interface identifier identifies an interface within the network element to which the packet should be forwarded, and

in the case that the received MAC address does not match the retrieved MAC-I/F pair'"'"'s MAC address, returning null; and

in the case that the first tier bucket contains a second tier data structure address and a mask bit list;

generating a second tier hash index from the received MAC address and the mask bit list, accessing a second tier bucket in a second tier data structure, wherein the second tier data structure is stored at the second tier data structure address and the second tier bucket stored at the second tier hash index, determining contents of the second tier bucket, in the case that the second tier bucket contains a null, returning a null, in the case that the second tier bucket contains one of the stored MAC-I/F pairs, retrieving the MAC-I/F pair from the second tier bucket, comparing the received MAC address to the retrieved M AC-I/F pair'"'"'s MAC address and;

in the case that the received MAC address matches the retrieved MAC-I/F pair'"'"'s MAC address, returning the retrieved MAC-I/F pair'"'"'s interface identifier, wherein the interface identifier identifies an interface within the network element to which the packet should be forwarded, and

in the case that the received MAC address does not match the retrieved MAC-I/F pair'"'"'s MAC address, returning null;

whereby each MAC-I/F pair lookup requires, at most, two memory accesses because the second tier lookup is a deterministic lookup with only a single memory access.

2. The method of claim 1, wherein the generation of the second tier hash index from the MAC address and the mask bit list comprises the steps of:

initializing the second tier hash index to an empty value; and

for each mask bit location in the mask bit list;

retrieving a bit value from the MAC address corresponding to a bit specified by the current mask bit location, and

appending the bit value to the second tier hash index.

3. The method of claim 1, wherein the first hash function is selected from one of:

a modified cyclic redundancy check (CRC) function, a cryptographic hash function, and a checksum hash function.

4. A method performed by a network element including a media access control (MAC) forwarding control module that inserts MAC address and interface (I/F) identifier pairs (MAC-I/F pairs) into a MAC forwarding data structure utilizing compressed keys to index second tier data structures, the method comprising the steps of:

receiving, at the MAC forwarding control module, a first MAC-I/F pair to insert into the MAC forwarding data structure, the MAC forwarding data structure comprising a first tier data structure and a second tier data structure, the second tier data structure containing a plurality of MAC-I/F pairs;

determining a destination location for the first MAC-I/F pair, the destination location in the second tier data structure;

determining contents of the destination location in the second tier data structure;

in the case that the destination location contains null, inserting the first MAC-I/F pair into the destination location;

in the case that the destination location contains one of the plurality of MAC-I/F pairs;

generating a new mask bit list from the first MAC-I/F pair and the plurality of MAC-I/F pairs,

generating a new second tier data structure comprising the first MAC-I/F pair and the plurality of MAC-I/F pairs, and

updating the first tier data structure with an address to the new second tier data structure and the new mask bit list;

whereby a MAC forwarding data structure is constructed such that subsequent lookups will deterministically require, at most, two memory accesses to retrieve a value of a desired MAC-I/F pair or a null value.

5. The method of claim 4, wherein the generating a new mask bit list step comprises the steps of:

adding the first MAC-I/F pair to the plurality of MAC-I/F pairs;

for each MAC-I/F pair in the plurality of MAC-I/F pairs;

comparing a first MAC address of the current MAC-I/F pair to each MAC address of each of the other MAC-I/F pairs in the plurality of MAC-I/F pairs to determine the left most bits that are different between the first MAC address and each of the other MAC addresses in the plurality of MAC-I/F pairs,

compiling the new mask bit list with all of the bit positions that differ between each of the MAC addresses in the MAC-I/F pairs and each of the other MAC addresses in the plurality of MAC-I/F pairs, and

removing all duplicates from the mask bit list.

6. The method of claim 5, wherein the step of generating a new second tier data structure comprises the steps of:

creating a new array structure to store the plurality of MAC-I/F pairs; and

for each MAC-I/F pair in the plurality of MAC-I/F pairs;

generating a second tier hash index for the current MAC-I/F pair using the mask bit list and the MAC addresses of the current MAC-I/F pair, and

inserting the current MAC-I/F pair into the array at the second tier hash index for the current MAC-I/F pair.

7. The method of claim 6, wherein the step of generating a second tier hash index for the current MAC-I/F pair comprises the steps of:

initializing the second tier hash index to an empty value; and

for each bit location in the mask bit list;

retrieving a bit value for from a corresponding bit location in the MAC address of the current MAC-I/F pair, and

appending the bit value to the second tier hash index.

8. A network element, to be coupled to a network, configured to receive packets from other network elements of the network, process those packets, and maintain a media access control (MAC) address and interface (I/F) (MAC-I/F) forwarding data structure for determining the destination I/F of received packets, the network element comprising:

a plurality of I/Fs configured to receive packets from other network elements of the network, each packet comprising a destination media access control (MAC) address;

a processor coupled to the plurality of I/Fs and configured to;

process the received packets, and

transmit the processed packets through different ones of the plurality of I/Fs to the processed packets destinations;

a MAC forwarding control module coupled to the processor and configured to maintain a MAC forwarding data structure that includes a first tier data structure, to store a plurality of second tier data structure addresses, and to associate MAC addresses with corresponding forwarding I/Fs, the MAC forwarding control module comprising;

a compressed key lookup module configured to;

receive a first MAC address to lookup a MAC-I/F pair from the MAC forwarding data structure,

generate a first tier hash index from the first MAC address with a first hash function,

retrieve contents of a first tier bucket from a location in the first tier data structure corresponding with the first tier hash index,

determine the contents of the first tier bucket,

return a null value when the first tier bucket'"'"'s contents are null,

return the retrieved MAC-I/F pair'"'"'s interface identifier when the first tier bucket'"'"'s contents are a MAC-I/F pair corresponding to the first MAC address, wherein the interface identifier identifies an interface within the network element to which the packet should be forwarded,

lookup the MAC-I/F pair from one of the plurality of second tier data structures using a second tier hash index generated from the MAC address and a mask bit list associated with the one of the plurality of second tier data structures when the first tier bucket'"'"'s contents are an address to the one of the plurality of second tier data structures and the mask bit list,

a MAC-I/F association module configured to learn which of the plurality of I/Fs is associated with each of the received packets'"'"' destination MAC address, and

a compressed key insert module configured to;

receive a first MAC-I/F pair to insert into the MAC forwarding data structure,

generate a first tier hash index from the MAC address of the first MAC-I/F pair,

determine the contents of a first tier bucket at a location in the first tier data structure corresponding with the first tier hash index,

when the contents of the first tier bucket are null, insert the first MAC-I/F pair in the first tier bucket, and

when the contents of the first tier bucket are a second MAC-I/F pair;

generate a mask bit list from the first MAC-I/F pair and the second MAC-I/F,

generate a second tier data structure,

insert the first MAC-I/F pair and the second MAC-I/F pair in the second tier data structure, and

insert an address to the second tier data structure and the mask bit list in the first tier bucker; and

a memory coupled to the processor and the MAC forwarding data structure control module, the memory configured to store the MAC forwarding data structure;

whereby a MAC forwarding data structure is constructed such that subsequent lookups will deterministically require, at most, two memory accesses to retrieve a value of a desired MAC-I/F pair or a null value.

9. The network element of claim 8, wherein the compressed key insert module is configured to:

generate the mask bit list by comparing a first MAC address of the first MAC-I/F pair to with a second MAC address of the second MAC-I/F pair and storing first bit of difference between the first MAC address and the second MAC address; and

insert the first MAC-I/F pair and the second MAC-I/F pair in the second tier data structure by generating second tier hash indexes from the mask bit list and the MAC addresses of the MAC-I/F pairs, wherein the second tier hash indexes correspond to the value of the bits of the MAC addresses at the bit positions listed in the mask bit list.

10. The network element of claim 8, wherein the MAC forwarding control module further comprises a compressed key delete module configured to remove MAC-I/F pairs from the MAC forwarding data structure.