Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
1999-11-26
2004-10-12
Nguyen, Steven H. D. (Department: 2739)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S217000, C711S220000
Reexamination Certificate
active
06804767
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the efficient construction and access of address tables within network mutliplexers and, in particular, to a method and system for efficiently adding addresses to an address table of limited size until the address table is nearly full and for efficiently locating entries within the address table.
BACKGROUND OF THE INVENTION
Bridges, switches, and routers are networking devices that interconnect two or more distinct physical communication network media, such as ethernets, token rings, and optical fibre media. Network multiplexers forward communications packets received from a first network medium via a first network multiplexer port to one or more destination communications network media via one or more destination network multiplexer ports. In forwarding a communications packet, the network multiplexer accesses an address table that contains a set of associations between network addresses and network multiplexer ports. The network multiplexer compiles the address table over time, monitoring incoming communications packets for newly recognized source addresses that do not yet exist in the address table. Those newly recognized addresses are entered into the address table in association with an indication of the port through which the communications packet was received. Subsequently, when a communications packet is received with a destination address matching an address already entered into the address table, the network multiplexer can determine to which port to forward the communications packet.
The memory resources within a network multiplexer are limited, for practical, technical, and economic reasons. Even in the case where a network multiplexer serves only to link multiple ethernets, an address table could potentially contain many trillions of entries. For this reason, and because network devices may be relocated from one network medium to another, it is technically impractical to hardwire an address table within a network multiplexer. Instead, the network multiplexer dynamically constructs an address table. In order to dynamically construct the address table, the network multiplexer requires a method for storing associations between discovered network addresses and ports quickly and economically within an address table of finite size so that the network multiplexer can quickly determine whether an incoming destination address occurs within the address table and, if so, determine the port associated with that destination address. Content addressable memories may be used for storing the address table. These are memories combined with a huge amount of hardware logic that allows memory locations to be addressed by the contents of the memory locations. However, content addressable memories are currently too expensive and too large for use in mass-produced network multiplexers. Alternatively, software or firmware routines, or logic circuits, that implement a hash table within random access memory (“RAM”) can provide functionality similar to content addressable memories. A discrete mathematical function is applied to an address to produce an index into a memory region in which the entry for that address is stored. However, because the discrete mathematical function maps a relatively large number of different possible addresses into a much smaller number of memory locations, collisions invariably occur between different addresses. Currently-available hash table implementations address the collision problem in order to attempt to maximize the capacity of a finite-sized address table, but characteristically do so at the expense of increased computational complexity and decreased computational efficiency. Network multiplexer designers, architects, and manufacturers have therefore recognized a need for an efficient and economical address table implementation that avoids the use of content addressable memories and avoids the complexity and inefficiency of currently-available hash table implementations.
SUMMARY OF THE INVENTION
The present invention provides a computationally and memory-efficient implementation of an address table for use in a network multiplexer. This implementation employs multiple hash functions as well as hash table reshuffling. However, the implementation is markedly more efficient and more computationally straightforward than currently-available implementations because hash table reshuffling is largely deferred to future address entry operations. The computational efficiency provided by the present invention is important in network multiplexers that store and forward hundreds or thousands of communications packets per second and the computational straightforwardness is necessary for designing integrated circuits that implement the address table in logic circuits.
REFERENCES:
patent: 5414704 (1995-05-01), Spinney
patent: 5920900 (1999-07-01), Poole et al.
patent: 6115802 (2000-09-01), Tock et al.
patent: 6173384 (2001-01-01), Weaver
patent: 6266705 (2001-07-01), Ullum et al.
patent: 6308218 (2001-10-01), Vasa
patent: 6310876 (2001-10-01), Egbert
Duong Duc
Hewlett--Packard Development Company, L.P.
Nguyen Steven H. D.
LandOfFree
Method and system for automatic address table reshuffling in... 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 system for automatic address table reshuffling in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for automatic address table reshuffling in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3315521