MAC address table search unit

• US 5,914,938 A
• Filed: 11/19/1996
• Issued: 06/22/1999
• Est. Priority Date: 11/19/1996
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Esmaeili, Ahmad, Ramamurthy, Suryanarayan, Head, David A., Brady, David M.
• Primary Examiner(s): TON, DANG T
• Application Number:
  US08/746,963
• Time in Patent Office: 945 Days
• Field of Search: 370/254, 370/400, 370/401, 370/398, 370/474, 370/472, 370/471, 370/470, 370/351, 370/352, 707/10, 707/7, 707/8, 707/9, 707/100, 707/205, 707/103, 707/3, 701/110, 701/118, 701/120, 701/122, 701/143
• US Class Current: 370/254
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming

Abstract

A search key having a first length is presented to a universal hashing process. The search key is hashed using a universal hash function to generate a bucket ID having a second length, smaller than the first length. The bucket ID is used to address a table stored in a computer readable medium and a pointer is retrieved from an associated storage location. The pointer is used to index a hash bucket containing one or more entries, each of which can be compared to the search key to determine whether any of the entries match the search key. For the case where the method is used in a Ethernet switch, the search key may comprise a virtual LAN identification and media access control address. The table is made up of number of hash buckets, each of which may have one or more entries. New entries are stored in one of the hash buckets according to the universal hash function so long as no overflows of any hash bucket would be created. If a bucket overflow would result from the storing operation, a new hash function is automatically selected so that no hash bucket overflows will result when the new entry is stored in a new table.

Claims

1. A computer assisted method of locating an entry in a table stored in a computer readable medium, comprising the steps of:

(a) generating a search key having a first number of bits, wherein said search key comprises a virtual LAN identification (VLAN ID) and a media access control (MAC) address;

(b) applying a universal hash function to said search key to generate a bucket ID having a second number of bits less than said first number of bits, by

(i) segmenting said search key into a plurality of segments, each of said segments having an equal number of bits;

(ii) multiplying each of said segments by a corresponding segment of a hash coefficient to create a series of products;

(iii) summing said series of products to create a sum; and

(iv) performing a MOD operation with said sum and a prime number to generate said bucket ID;

(c) addressing a table stored in said computer readable medium using said bucket ID to obtain a pointer;

(d) indexing a hash bucket using said pointer; and

(e) comparing a first entry in said hash bucket to said search key to determine whether said first entry matches said search key.

2. A computer assisted method of locating an entry in a table as in claim 1 wherein said search key has 64 bits.

3. A computer assisted method of locating an entry in a table as in claim 1 wherein said bucket ID has 17 bits.

4. A computer assisted method of locating an entry in a table as in claim 1 wherein said prime number has the form 2^P -1, where P is an integer and 2^P -1 equals the number of hash buckets comprising said table.

5. A computer assisted method of locating an entry in a table as in claim 1 wherein said hash bucket comprises a maximum of four entries.

6. A computer assisted method for configuring a media access control (MAC) address table for a node of a communication network, comprising the steps of:

receiving at said node a frame of information, said frame including a MAC address;

generating a first value including said MAC address;

applying a universal hash function to said first value to generate a second value by (i) segmenting said first value into a plurality of segments, each of said segments having an equal number of bits, (ii) multiplying each of said segments by a corresponding segment of a hash coefficient to create a series of products, (iii) summing said series of products to create a sum, and (iv) performing a MOD operation with said sum and a prime number to generate said second value, and addressing a table using said second value to obtain a pointer; and

storing said MAC address in a MAC address table at a storage location indicated by said pointer.

7. A computer assisted method of configuring a MAC address table as in claim 6 wherein said first value further includes a virtual LAN identifier (VLAN ID).

8. A computer assisted method of configuring a MAC address table as in claim 7 wherein said VLAN ID is obtained from said frame.

9. A computer assisted method of configuring a media access control (MAC) address table for a node of a communication network, said MAC address table having a number of hash buckets, each of said hash buckets having one or more entries, the method comprising the steps of:

receiving at said node a frame of information including a MAC address, said MAC address being different from each of said entries; and

storing said MAC address as an entry in one of said hash buckets according to a universal hash function so long as a hash bucket overflow is not created by;

(i) applying said universal hash function to said MAC address to generate a bucket value,

(ii) addressing a table using said bucket value,

(iii) retrieving a pointer from said table at a storage location determined by said step of addressing,

(iv) indexing a corresponding one of said hash buckets using said pointer and determining the number of entries in said corresponding hash bucket, and

(v) storing said MAC address as a new entry in said corresponding hash bucket if said number of entries is less than a threshold value;

otherwise generating a new MAC address table based on a new hash function, selected so that no hash bucket overflows will result when said MAC address is stored in said new MAC address table.

10. A computer assisted method of configuring a MAC address table as in claim 9 wherein said threshold value is four.

11. A computer assisted method of configuring a MAC address table as in claim 9 wherein generating said new MAC address table comprises the steps of:

selecting a new hash multiplier value;

generating a new hash function based on said hash multiplier value;

testing said new hash function by computing new bucket identifiers for each entry in said MAC address table using said new hash function and determining whether said new hash function will create any new hash buckets with a number of entries greater than said threshold; and

generating said new MAC address table based on said new hash function so long as no new hash buckets will have a number of entries greater than said threshold, otherwise repeating said steps of selecting, generating and testing until an appropriate hash function is found.

12. A table search unit, comprising:

means for generating a search key having a first number of bits;

means for applying a universal hash function to said search key to generate a bucket ID having a second number of bits less than said first number of bits, said means for applying a universal hash function including;

(i) means for segmenting said search key into a plurality of segments, (ii) means for multiplying each of said segments by a corresponding segment of a hash coefficient to create a series of products, (iii) means for summing said products to create a sum, and (iv) means for performing a MOD operation with said sum and a prime number to generate said bucket ID;

means for addressing a table stored in a computer readable medium using said bucket ID to obtain a pointer;

means for indexing a hash bucket using said pointer; and

means for comparing a first entry in said hash bucket to said search key to determine whether said first entry matches said search key.

13. A communication node, comprising:

means for receiving a frame of information including a MAC address;

means for generating a first value including a MAC address;

means for applying a universal hash function to said first value to generate a search value;

means for storing said MAC address at a storage location corresponding to said search value, said means for storing including means for addressing a table using said search value to obtain a pointer, and means for storing said MAC address in a MAC address table at said storage location, said storage location being indicated by said pointer.