Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – Addressing cache memories
Reexamination Certificate
1998-03-19
2001-05-08
Yoo, Do (Department: 2185)
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
Addressing cache memories
C711S200000, C711S216000
Reexamination Certificate
active
06230231
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
The present invention relates generally to network switches, and more particularly to storage and recovery of address information in an address cache of a network switch.
Network switches commonly employ an address cache to facilitate the flow of data units from a source device to a destination device in a communications network. The address cache contains entries that indicate address information for various devices in the network such as computers and printers. In a technique known as “forwarding,” the switch employs the address information to determine which port or ports to employ for transmission of a received data unit toward the destination device. Without the benefit of the address information the switch needs to transmit the data unit via every port in the switch in accordance with a technique known as “flooding” in order to assure that the data unit may be received by the destination device.
Caching requires a hash function that maps a search key to a cache line index. The cache line index is used to access the cache to perform a comparison of the search key to the cache tag. If a match is found, the cache data associated with the cache entry is returned. In a network switch, the search key is commonly a Media Access Control (“MAC”) address. The cache tag is compared against the appropriate fields of the MAC address and if a match is found, the associated cache data is used to forward the data frame. The combination of cache line index and cache tag limit the amount of storage required for the data structure because the full 48 bit MAC address does not need to be stored in every cache entry.
Bit selection is one of the simplest forms of hash function. With bit selection, some number of bits (e.g., low order 16 bits of MAC address) are used as the cache line index and the remaining bits (e.g., high order 32 bits) are stored in the cache entry as the cache tag. A matching cache entry is found when the cache tag is equal to the corresponding bits of the MAC address for which the search is being performed.
In network switch applications the key space is the set of all MAC addresses and the search key space is the subset of MAC addresses that a given network switch will find encapsulated in the header of frames that it receives. An important aspect of any hash function is the degree to which it uniformly distributes the values from the search key space in the hash key space. The hash key space is the set of all cache line indices generated from the hash function. If the search key space included all possible MAC addresses, then a simple bit select function would likely suffice because the values in the search key space would uniformly alias in the hash key space.
In practical application, however, the search key space has been demonstrated to contain more information in the low order 28 bits of each value than in the high order 20 bits. This property is developed in the paper “A Comparison of Hashing Schemes for Address Lookup in Computer Networks,” Raj Jain, IEEE Transactions on Communication, Vol. 40, Number 3, October 1992. It is reasonable to expect some variation in this bit position information content among different network switches since the search key space may be different for each switch. However, the conclusion reached by Jain remains applicable. A desirable hash is one that uniformly distributes search keys in the hash space, permits storage of less than the full MAC address in each cache entry, and can be adapted to variations in the search key space.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, a cache line index for an address cache entry is calculated by organizing an address such as a Media Access Control (“MAC”) address into a plurality of intermediate elements, manipulating the bits of at least one of the intermediate elements in accordance with predetermined criteria, and folding the intermediate elements together with an exclusive-OR function. The predetermined manipulation criteria may include programmable bitwise shifting and concatenation of intermediate elements with other address information such as a Virtual Local Area Network (“VLAN”) index. In the case where a MAC address is employed, the 28 lower order bits of the MAC address are distributed across every bit of the exclusive-OR computation, thereby attributing greater “weight” to the bits that contain the greatest amount of information.
A 48 bit MAC address can be mapped to a 14 bit cache line index. In one of the disclosed embodiments, bits
13
:
0
of the MAC address are right shifted by a number of bits designated by a first variable using a barrel shifter and the result is employed as a first 14 bit intermediate element. Bits
27
:
14
of the MAC address are right shifted by a number of bits designated by a second variable using a barrel shifter and the result is employed as a second 14 bit intermediate element. Bits
47
:
46
of the MAC address are concatenated with bits
39
:
28
of the MAC address and the result is employed as a third 14 bit intermediate element. Bits
45
:
40
of the MAC address are concatenated with a logic value “0” and either the value “0000000” or the VLAN index, depending upon predetermined criteria, and the result is employed as the fourth 14 bit intermediate element. For example, the VLAN index may be employed only when the VLAN index field contains meaningful information. The four 14 bit intermediate elements are then entered into a bitwise exclusive-OR function, and the output may be employed as the cache line index.
A 7 bit VLAN index enables segmentation of the 2
14
cache into 128 virtual tables, i.e., one table per index value, with dynamic size up to 2
14
locations. The VLAN Index bits are distributed across 7 bits of the hash result if the VLAN index is employed in the hash calculation. Hence, the VLAN Index bits are “weighted” with respect to the upper MAC Address bits.
Calculations performed in accordance with the described technique are advantageously reversible. Because the cache line index is calculated through exclusive-OR folding of the do intermediate address elements, a subset of the intermediate address elements can be employed in conjunction with the cache line index to recover each element of the original address. In particular, any three of the intermediate elements can be employed in conjunction with the cache line index to recover the original MAC address. During an address cache search for an address specified in a data unit received by the switch, the address information in the header of the received data unit is employed as a search key into the address cache. If a match occurs then the original MAC address can be recovered by reversing the computations on the stored segments and the cache line index. Hence, the size of the tag portion that is maintained in the address cache entry is reduced relative to the full MAC address without a reduction in the information content of the entry.
Programmable bitwise shifting of intermediate address elements facilitates adaptation of the hash operation to different conditions. The variables that designate the number of bits by which the first and second elements are shifted can be dynamically adjusted to provide improved hash calculation results if the MAC address values being hashed produce uneven distribution. The two variably shifted 14 bit elements yield 196 distinct programmable variations for producing the hash result. Variable selection can be automated with software to provide more uniform distribution of the address information in the address cache.
REFERENCES:
patent: 4215402 (1980-07-01), Mitchell et al.
patent: 5633858 (1997-05-01), Chang et al.
patent: 5923660 (1999-07-01), Shemla et al.
Kilchenmann, S. Re: Bytearray to integer. [Online] news://de.comp.lang.java, Dec. 17, 1997.*
DEC-TR593, A Comparison of Hashing Schemes for Address Lookup in Computer Networks,by: Raj Jain, Digital E
DeLong Kenneth J.
Miller David S.
3Com Corporation
Encarnacion Yamir
Weingarten, Schurgin Gagnebin & Hayes LLP
Yoo Do
LandOfFree
Hash equation for MAC addresses that supports cache entry... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hash equation for MAC addresses that supports cache entry..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash equation for MAC addresses that supports cache entry... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2512207