Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-05-12
2004-05-11
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S216000, C365S049130
Reexamination Certificate
active
06735670
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data communications networks and more particularly relates to a forwarding table constructed using a combination of HASH table and contents addressable memory (CAM).
BACKGROUND OF THE INVENTION
Currently, the number of data networks and the volume of traffic these networks carry are increasing at an ever increasing rate. The network devices that make up these networks generally consist of specialized hardware designed to move data at very high speeds. Typical networks, such as Ethernet based networks, are comprised mainly of end stations, Ethernet hubs, switches, routers, bridges and gateways. ATM networks are constructed with similar network devices adapted to carry ATM traffic, e.g., ATM capable end stations, edge devices and ATM switches.
With the ever increasing user demand for faster and faster data communications, network devices must perform at higher and higher speeds. A primary function of a typical network devices is to receive frames (packets, cells, etc.) at one or more ingress ports, and forward the frame to the appropriate egress port. Accomplishing this requires that the network device make a forwarding decision about the received frame. This requires processing resources and typically utilizes a memory lookup operation in making the forwarding decision.
For example, consider a network device with 64 output ports. For each frame received, a forwarding decision must be made to determine which of the output ports to forward the frame to or whether to drop the frame altogether. The decision to forward to one or more ports is indicated in a 64 bit output port vector whereby a bit is set corresponding to each port the frame is to be output to. Assuming that the forwarding decision is made after receipt of the header, than the 64 bit output port vector is stored in a memory queue until the entire frame has been received. Once received, the output port vector is retrieved from memory and the frame is directed to the output ports indicated in the corresponding output port vector.
The memory used to store the output port vector, i.e. the forwarding information, typically utilizes some form of hash table. Hashing techniques are widely used in computer hardware and software systems, such as operating systems, compilers, etc., to store large numbers of elements. Hashing involves calculating an index from a key and using the index to look for matches in a hash table. The function that calculates the index is known as a hash function. The use of hashing permits a plurality of elements to be stored in very large spaces, thus they impose little restriction on the size of the collection of elements stored.
The hash table is well suited for fast storage and retrieval of information elements. The efficiency of a hash table implementation is largely dependent on the hash function used. The keys used by a hash table may be simple or complex, which in the latter case may be made up of several attributes of an element. Alternatively, the complete element may be used as the input to the hash function.
A block diagram illustrating an example hash table implementation some of the entries of which have one or more collisions associated therewith is shown in FIG.
1
. The hash table, generally referenced
10
, comprises a table
19
having a plurality of entries
12
. In this example, the table
19
comprises 10 entries. The input (known as the key) is applied to the hash function
18
. The function takes the key and ‘hashes’ it wherein it returns an index (possibly a large integer) obtained by manipulating the key. The index generated by the hash function is then applied to the hash table
19
.
With a good hash function, all the bits in the key affect the value of the index generated. In addition, the dependence of the index on the value of the key is preferably non-obvious.
The principle of a hash table is that a possibly infinite set of elements is partitioned into a finite number of hash values. The hash function is performed using the key as input to yield a resulting hash value (i.e. index). A hash collision occurs, however, if for two different keys the hash function returns the same hash value. In such cases, a collision list is generated whereby all the keys that return the same hash value are linked.
For example, with reference to
FIG. 1
, the hash function
18
calculates the index from the key by (1) transforming the key into an integer according to its position in the alphabet, (2) the resulting integers are added together and (3) the result is divided by the size of the hash table (i.e.
10
) and the remainder is the hash result or index.
Thus, the key ‘cdf’ is hashed to the value
3
. The key ‘no’ is hashed to the value
9
. A first collision occurs when hashing the key ‘efh’. As a result, both keys are placed in a collision linked list that is associated with table entry
9
. A second collision occurs on the key ‘ccc’ and as a result, this key is added to the collision linked list associated with hash table entry
9
. Note that each entry and associated linked list is commonly called a bucket. Upon retrieval, the linked list associated with a hash result is searched element by element for a match with the key. If the indexes obtained by hashing are uniformingly distributed across the array of buckets, then the buckets are not likely to be long.
Thus, in the ideal case, a hash function returns a different hash value for each unique key. If there are collisions, it is preferable that the collision linked list remains small in order to maintain fast access time. This means that hash values should be evenly distributed across all the hash table entries. In addition, the hash function preferably always returns the same hash value for a given key.
Note that in many applications, a hash table is better at retrieving information that an array or a linked list since the correct bucket is away determined very quickly using hashing. Then, if there were one or more collisions, only the few keys that collided at the index of the bucket must be searched.
Thus, choosing a good peforming hashing function h(k) is the tricky part of implementing a hash table based search and retrieval system. The function h should ideally distribute the input elements as uniformly as possible over the buckets (or slots) of the hash table. The major criterion is that the hash function should generate a minimum number of collisions.
If the probability that a key k occurs in the set of input value is P(k), and there are m slots in the hash table, then a uniform hashing function h(k) satisfies:
∑
k
|
h
(
k
)
=
0
P
(
k
)
=
∑
k
|
h
(
k
)
=
1
P
(
k
)
=
…
=
∑
k
|
h
(
k
)
=
m
-
2
P
(
k
)
=
∑
k
|
h
(
k
)
=
m
-
1
P
(
k
)
=
1
m
(
1
)
Most of the time it is not possible to ensure this. Thus, a uniform hashing function is difficult to achieve in practice.
A hash table is realized using a large enough memory to store the hashed index values in a one way organization. The hashing function hashes the key to a smaller index. In a network device application, the key comprises a MAC address, for example. The index is used to access a linear table called the hash table. The MAC address is stored at a location corresponding to the index along with the forwarding information. In the event of a collision, a sequential search is performed of the collision linked list associated with that location. A hit occurs when the index matches the stored data.
The advantage of using a hash table is its relatively low cost in terms of size required to store a given number of entries. A disadvantage of a hash table with a collision linked list is the multiple cycles required for finding a hit. Limiting the number of addresses per hash entry is likely to result in one or more addresses not being able to be stored, resulting in a less than 100% hit ratio.
SUMMARY OF THE INVENTION
The present invention solves the problems associated with the prior art
Bronstein Zvika
Schzukin Golan
Shimony Ilan
Yaron Opher
3Com Corporation
Moazzami Nasser
Zaretsky Howard
Zaretsky & Associates PC
LandOfFree
Forwarding table incorporating hash table and content... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Forwarding table incorporating hash table and content..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forwarding table incorporating hash table and content... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3250548