Hash Collision Resolution with Key Compression in a MAC Forwarding Data Structure
First Claim
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, andin 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, retuning 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 MAC-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, andin 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.
1 Assignment
0 Petitions
Accused Products
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).
-
Citations
10 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, retuning 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 MAC-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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (5, 6, 7)
-
-
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. - View Dependent Claims (9, 10)
-
Specification