Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-04-25
2004-05-04
Nguyen, Chau (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06731633
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to network units for use in a packet-based communication system wherein network units such as switches and routers respond to address data in address data packets to direct packets towards their intended destinations. The invention particularly though not exclusively concerns the hashing of media access control addresses to facilitate the establishment and use of a forwarding database.
BACKGROUND TO THE INVENTION
It is well known in for example network units which are otherwise termed switches, bridges and routers to provide a forwarding database which is accessed employing address data within a receive packet and yields forwarding data such as a port number enabling a switching engine to direct the packet to an appropriate port from which the packet may be dispatched. Neither the particular nature of the address data, which is typically layer
2
or media access control data, nor the particular forwarding data, typically port numbers, is of direct importance to the invention. Nevertheless the invention will be described in relation to the employment of media access control data.
Although the establishment of a forwarding database is not of particular importance to the invention, it may be noted that it is customary to establish a forwarding database by the reading of a source address from an incoming packet and to determine whether that source address corresponds to an address which is already established as an entry in the forwarding database. If the source address is not matched in this way, a new entry is made in the database.
It is also well known to employ the destination address, in a manner to be described, to access the database in order to obtain the forwarding data. If the destination address is not in the database then it may be necessary to broadcast the packet and to detect a response from the intended recipient, in order to establish, for example, from which port it is necessary to forward the packet in order to direct the packet to the correct destination.
In order to make the establishment of a forwarding database and also look-ups in the database more efficient, for example in terms of memory space to be occupied, it is known, for example from U.S. Pat. No. 5,708,659 and GB patent application No. 2337674 to employ a hashing algorithm. The main purpose of hashing is to reduce a very wide address into a much less wide address. For example, it may be employed to reduce a 48-bit wide media access control address into a 16-bit wide address. The result of hashing may be a pointer to an associated data table which includes the original MAC address and other data such as the forwarding data.
Since the hashing of address data into a pointer does not necessarily produce a unique result, it is customary to organise the associated data table so that if a second MAC address hashes to the same result the entry relating to the first MAC address is caused to contain a link pointer to a new entry for the second MAC address. During a look-up process, if the stored MAC address which is returned from the associated data table does not match the input MAC address then the link pointer will direct a search engine to the next linked entry in the associated data table which might have a MAC address that matches the input MAC address and so on. The phenomenon of the same hash result from different original addresses is called ‘convergence’.
Although the use of linked lists is a necessary feature of look-up tables which are accessed by hashing, it is not desirable that linked lists be produced, since they significantly retard the look-up process.
SUMMARY OF THE INVENTION
The present invention relates to the improvement of the hashing process so as to reduce the incidence of convergence and the consequent occurrence of linked lists.
In a preferred form of the present invention, a seed for a hashing algorithm is provided by a combination, such as an exclusive-OR combination, of part of an input address word and a selected adjustable auxiliary word. Hashing is preferably performed in at least two stages, wherein in one cycle a hash function is applied to a portion of the input address not including the part which is combined with the selected word to constitute a hash seed and another (preceding) cycle in which a further part of the address and the aforementioned hash seed are subject to hashing. The selected word may be a software programmable mask and it is possible thereby to ensure a high degree of randomness in the hash seed. With appropriate adjustment of the mask, convergence can readily be reduced. More particularly the invention allows up to 2
n
−1 permutations of the hash algorithm. With such a range of permutations it should always be possible to find an optimal hash algorithm for a given database.
REFERENCES:
patent: 5475826 (1995-12-01), Fischer
patent: 5914938 (1999-06-01), Brady et al.
patent: 6173384 (2001-01-01), Weaver
patent: 6233242 (2001-05-01), Mayer et al.
patent: 6292483 (2001-09-01), Kerstein
patent: 6424650 (2002-07-01), Yang et al.
patent: 6473424 (2002-10-01), DeJager et al.
patent: 6504843 (2003-01-01), Cremin et al.
patent: 6553029 (2003-04-01), Alexander
patent: 483424 (1992-05-01), None
patent: 953919 (1999-11-01), None
Jain, Raj. “A Comparison of Hashing Schemes for Address Lookup in Computer Networks”. IEEE Transactions on Communications. Oct. 1992. vol. 40. No. 10. pp. 1570-1573.*
Tung-Shou, Chen et al. “Hash-Semijoin: a New Technique for Minimizing Distributed Query Time”. Proceedings of the Third Workshop on Future Trends ofDistributed Computing Systems. Apr. 1992. pp. 325-330.
Clifford Neil J
O'Brien Eoin
O'Donoghue Derry M
Sohor Annette E
3Com Corporation
Mills Donald L
Nguyen Chau
Nixon & Vanderhye PC
LandOfFree
Network unit including address hashing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network unit including address hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network unit including address hashing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3235448