High-Speed MAC Address Search Engine
6 Assignments
0 Petitions
Accused Products
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.
85 Citations
38 Claims
-
1-17. -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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
-
-
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. - View Dependent Claims (27, 28, 29, 30)
-
-
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. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38)
-
Specification