High-Speed MAC Address Search Engine

Abstract

Disclosed is an apparatus and method for storing and searching computer node addresses in a computer network system. In one embodiment, the apparatus comprises a frame forwarding device such as a switch. The switch includes two MAC address tables including a primary MAC address table and secondary MAC address table both for storing and searching MAC addresses. The primary table stores records that contain compressed values of MAC addresses. The records are contained in storage locations that are referenced using the compressed value of the MAC address as a search index. In order to account for searching collisions that may result from different MAC addresses compressing to the same value, each record in the primary address table is linked to a chain of records in the secondary table. The records in the secondary table store the full value of the MAC address. Each chain of records in the secondary address table contains MAC addresses the present invention.

1 - 17 . (canceled) 
     
     
         18 . A method of searching for a computer address in an address table, the steps comprising:
 partitioning the computer address into an upper set and a lower set;   generating a search index by compressing the computer address, wherein the search index comprises a number of bits equal to the number of bits of the lower set;   accessing a primary address record corresponding to the computer address in a primary address table, the primary address record being accessed by using the search index to locate the primary address record, wherein the primary address record includes the computer address, a port number associated with the computer address, and a link that specifies the location of an initial secondary address record in a secondary address table; and   comparing the search index to the primary address record.   
     
     
         19 . The method of  claim 18 , wherein comparing the search index to the primary address record includes at least the following:
 selecting at least one low order bit of the combination of the search index and the lower set, wherein a first value is determined;   decompressing the compressed value of the address contained in the primary address record to obtain a second value; and   comparing the first value to the second value.   
     
     
         20 . The method of  claim 18 , further comprising, if the first value does not equal the second value, accessing the initial secondary address record, wherein the initial secondary address record includes a respective address entry, a port number associated with the computer address, and a link to a subsequent secondary address record of the same hash family. 
     
     
         21 . The method of  claim 18 , wherein the primary address table is stored in a memory external to the switch and wherein the secondary address table is stored in content addressable memory. 
     
     
         22 . The method of  claim 18 , wherein the step of generating a search index by compressing the computer address further comprises at least one of the following: compressing the computer address from a width of 48 bits to a width of less than 48 bits and compressing the computer address from a width of 48 bits to a width of 16 bits. 
     
     
         23 . The method of  claim 18 , further comprising the step of comparing the first value to the computer address in a secondary record. 
     
     
         24 . The method of  claim 23 , further comprising, if the subsequent secondary record is empty, populating the initial secondary address record with the location of the subsequent secondary address record. 
     
     
         25 . The method of  claim 18 , wherein the computer address comprises 60 bits, the upper set comprises 48 bits and the lower set comprises 12 bits. 
     
     
         26 . A storage and search unit for computer addresses each having a fixed bit size n, the unit comprising:
 a primary address table stored within a first memory the primary address table configured to store a plurality of primary address records, each primary address record including a respective address entry a port number associated with the compressed address entry and a first link that links at least one primary address record to a corresponding chain of secondary address records in a secondary address table;   a secondary address table stored within a second memory separate from the first memory, the secondary address table configured to store a plurality of secondary address records, each secondary address record including a respective address entry a port number associated with the computer address, and a link that links at least one secondary address record to a corresponding secondary address record in the secondary address table to thereby form one or more linked chains of secondary address records;   a software search module configured to store and access the primary address records and secondary address records.   
     
     
         27 . The storage and search unit of  claim 26 , wherein the second memory comprises a content addressable memory. 
     
     
         28 . The storage and search unit of  claim 26 , wherein the bus width of the first memory is 16 bits. 
     
     
         29 . The storage and search unit of  claim 26 , wherein the bit size of the compressed address entry is equal to the bus width of the first memory. 
     
     
         30 . The storage and search unit of  claim 29 , wherein the storage and search unit comprises a switch on an Ethernet network. 
     
     
         31 . A computer-readable medium that includes computer-readable software, the computer-readable software including a set of instructions for causing the device to perform at least the following:
 search for a computer address in an address table;   partition the computer address into an upper set and a lower set;   generate a search index by compressing the upper set to obtain a compressed value of the computer address;   access a primary address record corresponding to the computer address in a primary address table, the primary address record being accessed by using the search index to locate the primary address record; and   compare the search index to the primary address.   
     
     
         32 . The computer-readable medium of  claim 31 , wherein comparing the search index to the primary address includes at least the following:
 select the order bits of the combination of the search index and the lower set, wherein a first value is determined,   decompress the compressed value of the address contained in the primary address record to obtain a second value; and   comparing the first value to the second value.   
     
     
         33 . The computer-readable medium of  claim 31 , the set of instructions further configured to cause the device to perform at least the following:
 if the first value does not equal the second value, then access the initial secondary address record using the link, wherein the initial secondary address record includes a respective address entry of the first bit size less than the fixed bit size n, a port number associated with the computer address, and a link to a subsequent secondary address record of the same hash family.   
     
     
         34 . The computer-readable medium of  claim 31 , wherein the set of instructions is further configured to perform at least the following: compress the computer address from a width of 48 bits to a width of less than 48 bits. 
     
     
         35 . The computer-readable medium of  claim 31 , wherein the set of instructions is further configured to perform at least the following: compress the computer address from a width of 48 bits to a width of 16 bits. 
     
     
         36 . The computer-readable medium of  claim 31 , wherein the set of instructions is further configured to perform at least the following: compare the first value to the full computer address in the secondary record. 
     
     
         37 . The computer-readable medium of  claim 36 , wherein the set of instructions is further configured to perform at least the following: if the subsequent secondary record is empty to populate the subsequent secondary record with the computer address and with a port associated with the computer address. 
     
     
         38 . The computer-readable medium of  claim 37  wherein the set of instructions is further configured to perform at least the following: if the subsequent secondary record is empty, populate the initial secondary address record with the location of the subsequent secondary address record.