Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-09-30
2004-08-10
Nguyen, Brian (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395320, C370S401000
Reexamination Certificate
active
06775281
ABSTRACT:
BACKGROUND OF THE INVENTION
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 (“MAC”) address, 2
48
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 2
15
indices (through index bits 14:0)
134
. There are four buckets
138
A-D at each index
134
. Each of the buckets
138
A-D stores one forwarding entry. The size of the hash table
136
is determined by the size of the location
138
A-D and the total number of indices
134
. For example, if each bucket
138
A-D is one byte wide, a 128 Kilobytes (32 Kilobytes×4) 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.
SUMMARY OF THE INVENTION
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.
REFERENCES:
patent: 5032987 (1991-07-01), Broder et al.
patent: 5129074 (1992-07-01), Kikuchi et al.
patent: 5371499 (1994-12-01), Graybill et al.
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5802054 (1998-09-01), Bellenger
patent: 5914938 (1999-06-01), Brady et al.
patent: 5949786 (1999-09-01), Bellenger
patent: 6034958 (2000-03-01), Wicklund
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 0 365 337 (1990-04-01), None
Hamilton Brook Smith & Reynolds P.C.
Mosaid Technologies Inc.
Nguyen Brian
LandOfFree
Method and apparatus for a four-way hash table does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for a four-way hash table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a four-way hash table will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3336612