Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

High-speed mac address search engine

High-speed mac address search engine description/claims

This application is a continuation of U.S. application Ser. No. 10/750,445 filed Dec. 31, 2003, which is a Continuation-In-Part of U.S. Ser. No. 09/643,567, filed Aug. 22, 2000 and issued as U.S. Pat. No. 6,697,873 on Feb. 24, 2004, all of which are incorporated herein by reference as if set forth in their entireties.

The present invention relates to computer network technology. More particularly, the present invention relates to searching and forwarding of frames and computer addresses in a computer network. Description Of Related Art

A computer network generally comprises a set of conjoined computer devices that are communicatively linked so as to share resources such as storage devices, peripherals, applications, output devices, etc. The computing devices in a local area network (LAN) are typically connected to each other directly by cable connections. For organizational reasons, several devices in a network may be connected at a central connection point referred to herein as a hub. A hub typically has a plurality of ports that are each communicatively linked to one or more devices, such as a node, a switch, or a repeater. As used herein, the term “node” refers to any device that can communicated with other computers in a network. The hub receives an incoming signal from a source node through one port and sends the incoming signal out to a destination node through one or more other ports.

A repeater is a very simple form of a hub. Repeaters extend the size of a network by joining multiple segments into a larger segment. Repeaters increase a network signal's strength so the signal can be transmitted and received over a greater distance without a loss in quality. For example, the signal may have become degraded due to the distance traveled from the source to the repeater over the cable. The repeater regenerates the weak signal internally and forwards the signal out through all ports. This means that a repeater does not process data at all, but rather merely receives incoming signals and reconditions them for immediate transmission on all ports (except the originating port). That is, the repeater does not perform any analysis as to the destination address of the signal, but rather blindly sends the signal out through all ports.

A repeater can significantly increase the traffic level of a network because the repeater outputs all incoming signals through every port. This may not present a problem in networks where communication traffic is relatively low. However, in networks where traffic volume is relatively high, small increases in communication traffic may significantly degrade the performance of the network.

Switches and bridges are more complex types of hubs that overcome the aforementioned drawbacks associated with repeaters. Unlike repeaters, switches and bridges include frame forwarding logic and perform basic signal filtering functions before transmitting an incoming signal. Whereas repeaters forward all signals through every port, switches and bridges only forward signals that are necessary and only forward the signals to the appropriate port based upon the destination address of the signal.

In relation to the Ethernet network standard, signals are transmitted through the network as frames of data that travel from the source node to the destination node. A frame is generally comprised of several fields of information, including two fields that denote the destination Media Access Control (MAC) address and the source MAC address for the frame. The source MAC address specifies the source node of the frame and the destination MAC address specifies the destination node of the frame. Each node in the network is identified by a unique MAC address, which comprises a 48 bit (6 byte) string. Six bytes of device ID allows for approximately 32 trillion (248) possible unique MAC addresses;

When a switch or a bridge receives an incoming frame, the switch or bridge examines the frame's destination address. The switch maintains in internal memory a database of past frames. Through use of the database, referred to herein as an address table, the switch can keep track of which MAC addresses correspond to which ports on the switch. Upon receipt of a frame, the switch references the database and determines the port that is associated with the particular MAC address. The switch then forwards the frame to the correct port. Essentially, the switch checks its internal memory of past frames and determines whether to forward the frame to another port i or to filter out the frame.

The speed at which a switch can forward a frame to the correct port is dependent on several factors, including the amount of time that it takes for the frame to search its address table, find the frame's destination address and output the frame through the correct port(s). Ideally, an address table would contain enough data space to store each and every possible 6 byte MAC address. In such a case, the address table could contain an array of entries comprised of a complete listing of every single possible address and the port corresponding to each address. Upon receipt of a MAC address, the switch could then quickly search through the table and identify the appropriate port to which the MAC address should be forwarded.

However, as mentioned, there are approximately 32 trillion (248) possible MAC addresses that would have to be stored in such a table. In the real world, it would not be practical from a cost standpoint to maintain sufficient memory to store a table that contains each and every possible six byte MAC address. One way of reducing the amount of memory required for an address table would be to store a compressed or hashed version of the address in the table. However, this could result in collisions during searching as one or more different addresses could map to the same hash value.

Consequently, there is a need for a fast and efficient method of maintaining computer address forwarding tables.

In view of the aforementioned needs, the invention contemplates an apparatus and method for storing and searching computer node addresses in a computer network system. The system is described in the exemplary context of storing and searching MAC addresses in an Ethernet system. The system 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 MAC address table is preferably stored in a memory that is external to the switch and the secondary MAC address table is preferably stored in a memory that is internal to the switch. The primary table is preferably sensitive in data entry size according to the bus width of the external memory and may have a slower access speed and larger size than the secondary table. In order to increase the searching speed of the secondary address table, a search module is configured to perform on a bandwidth that is optimized to the memory in which the secondary address table is stored.

In one aspect of the invention, the primary address table stores records that contain MAC addresses. The records are contained in storage locations that are referenced using a compressed or hashed value of the MAC address as a search index. In order to account for searching collisions that may result from different MAC addresses hashing to the same value, each record in the primary address table may be linked to a hash family of chain of records in the secondary table. Each hash family chain of records in the secondary address table contains MAC addresses that belong to the same hash family, or MAC addresses that compress to the same value.

In accordance with the present invention, there is provided a method of searching for a computer address in an address table where the computer address having a bit size n. The bit size n computer address is partitioned into an upper set of n-m bits and a lower set of m bits, with m being a value less than bit size n. A search index is then generated by compressing the upper set of n-m bits to obtain a compressed value of the computer address, resulting in the search index having a number of bits equal to the number of bits of the lower set of m bits. A primary address record corresponding to the computer address is accessed via a primary address table. The primary address record is 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 that specifies the location of an initial secondary address record in a secondary address table. The search index is then compared to the primary address record by selecting the m low order bits of the combination of the search index and the lower set of m bits resulting in a first value. The compressed value of the address contained in the primary address record is decompressed to obtain a second value. The first and second values are compared and if the first value does not equal the second value, then the initial secondary address record is accessed using the link. The initial secondary address record includes a respective address entry of the bit size n-m, a port number associated with the computer address, and a link to a subsequent secondary address record of the same hash family.

Further in accordance with the present invention, there is provided a storage and search unit for computer addresses with each having a fixed bit size n. The unit includes a primary address table stored within a first memory of a first bus width, the primary address table configured to store a plurality of primary address records, each primary address record including a respective address entry of a first bit size less than the fixed bit size n, a port number associated with the compressed address entry and a first link that links each primary address record to a corresponding chain of secondary address records in a second address table. Also included in the unit is a secondary address table stored within a second memory separate from the first memory, the second address table configured to store a plurality of secondary address records, each secondary address record including 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 that links each secondary address record to a corresponding secondary address record in the second address table to thereby form one or more linked chains of secondary address records, wherein each chain of secondary address records contains full address entries of the same hash family. The unit further comprises a software search module configured to store and access the primary address records and secondary address records, wherein the software module stores each primary address record in a location defined by the value of the respective compressed address entry.

Still in accordance with the present invention, there is provided a computer readable software stored within a frame forwarding device of a computer network. The computer readable software code includes a set of instructions, which cause the device to search for a computer address of bit size n in an address table. The software then partitions the bit size n computer address into an upper set of n-m bits and a lower set of m bits, with m being less than n. The instructions then generate a search index by compressing the upper set of n-m bits to obtain a compressed value of the computer address. The search index having the same number of bits as the lower set of bits. The software then accesses a primary address record corresponding to the computer address in a primary address table by using the search index. The primary address record includes the computer address, a port number associated with the computer address, and a link that that specifies the location of an initial secondary address record in a secondary address table. The software then instructs the comparison of the search index to the primary address record. The instructions further include selecting the m low order bits of the combination of the search index and the lower set of m bits to determine a first value. The compressed value of the address contained in the primary address record is then decompressed to obtain a second value. The instructions then compare the first value and the second value and if the first value does not equal the second value, the instructions provide for an initial secondary address record to access via the link. The initial secondary address record includes a respective address entry of the bit size n-m, a port number associated with the computer address, and a link to a subsequent secondary address record of the same hash family.

Still further in accordance with the present invention, there is provided there is provided a method of searching for a computer address in an address table where the computer address having a bit size n. The bit size n computer address is partitioned into an upper set of n-m bits and a lower set of m bits, with m being a value less than bit size n. A search index is then generated by compressing the upper set of n-m bits to obtain a compressed value of the computer address, resulting in the search index having a number of bits equal to the number of bits of the lower set of m bits. An address record corresponding to the computer address is accessed via an address table. The address record is accessed by using the search index to locate the address record, wherein the address record includes the computer address, and a port number associated with the computer address. The search index is then compared to the address record by selecting the m low order bits of the combination of the search index and the lower set of m bits resulting in a first value. The compressed value of the address contained in the address record is decompressed to obtain a second value. The first and second values are compared to determine if a match has occurred.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws