In a computer network, a networking switch receives data packets from a number of ingress ports connected to the switch and forwards the data packets to a number of egress ports connected to the switch. The switch determines the egress port to which the data packets are forwarded dependent on a destination address included in the data packet received at one of the ingress ports.
The egress ports to which data packets are to be forwarded based on a destination address are stored in a forwarding entry in a forwarding table in the networking switch. The forwarding table is searched for the forwarding entry associated with a particular destination address.
In general, it is not feasible to provide an entry in the forwarding table for each possible destination address accessible through the switch. For example, for a 48 bit Ethernet destination address, that is, a Media Access Control (xe2x80x9cMACxe2x80x9d) address, 248 forwarding entries are required in the forwarding table to store forwarding information for all the possible MAC addresses. Instead, only a portion of the MAC addresses are stored in a hash table. A hash function is performed on the destination address to provide a smaller number which is then used to index the hash table.
As a result of performing a hash function on the destination address, multiple destination addresses may map to the same index, that is, aliasing may occur. Thus, an insert of an entry into a location in the hash table may be blocked if the location is already storing a forwarding entry for another destination.
One approach to the problem of aliasing is to generate a second hash function for the destination address in order to provide a second index if the forwarding entry is not found at the first index. However, multiple levels of hashing results in a non-deterministic search by adding delay to the search for the forwarding entry.
One well-known technique for reducing aliasing and providing a deterministic search is to provide more than one location at each index. This is also called the multiple bucket technique. In a hash table implementing multiple buckets, a predetermined number of locations or buckets are provided at each index.
FIG. 1A illustrates a block diagram of a prior art multi-bucket hash table 136. The hash table 136 includes 215 indices (through index bits 14:0) 134. There are four buckets 138A-D at each index 134. Each of the buckets 138A-D stores one forwarding entry. The size of the hash table 136 is determined by the size of the location 138A-D and the total number of indices 134. For example, if each bucket 138A-D is one byte wide, a 128 Kilobytes (32 Kilobytesxc3x974) hash table is required.
However, the multi-bucket hash table results in inefficient use of memory and an insert of a forwarding entry may be blocked if all the locations at an index are used. Thus, no further forwarding entries for destination addresses mapping to the index can be stored at that index in the hash table even though unused locations may be available at other indices in the hash table.
A network switch includes a plurality of hash tables, each of which is accessed concurrently with a different computed index. The indices are computed by hash function logic from a key dependent on a destination address. A forwarding entry for a key is inserted in one of the locations identified by the computed indices for the key. When a packet is received, the indices are computed to access the four hash tables, and the located forwarding entries are searched for one having a matching key. By appropriate storage of forwarding entries during the insert process, the match search can be completed in one search cycle.
The forwarding entry is preferably inserted in an unused location identified by the computed indices by an insert selection logic after detecting the unused location. However, if the insert selection logic determines that all the locations identified by the computed indices for the key are used, the insert selection logic may overwrite one of the used locations.
In a preferred embodiment, having determined that all the locations identified by the computed indices for the key are used, the insert selection logic moves one of the forwarding entries having another key to another location available to the other key and then inserts the new forwarding entry. Since the movement of that entry may result in movement of yet another entry, the forwarding entries may be recursively reordered.
When a packet is received, a key match logic searches the hash tables for a search key stored in a forwarding entry in one of the locations specified by the computed indices and provides the matching forwarding entry. Because of the reordering in the insert process, the proper forwarding entry in one of the indexed locations can be assured.
The hash function logic preferably computes the index for each hash table by generating a CRC for the key and selecting a portion of the CRC as the index. The number of hash tables and corresponding indices is preferably four.
USPTO Backgrounds
USPTO Backgrounds