1. Field of the Invention
The present invention relates to a table management technique, and in particular to a table management method and device allowing table access using degraded data having the number of bits smaller than that of input data.
2. Description of the Related Art
Hashing is a well-known method that is used to search a table. For example, in a standard LAN (Local-Area Network), MAC (Media Access Control) addresses are uniquely assigned to respective ones of all network devices. In such a LAN system, it is known that the hashing is used to search for a 48-bit MAC address.
Referring to FIG. 1, a 48-bit MAC address is converted to 10-bit data by a hash function 10 and the degraded 10-bit data is used as address data to obtain access to an entry table 11.
Here, it is assumed that the entry table 11 contains 1024 entries, each of which is composed of a MAC address (48 bits), aport number (4 bits) of a switch accommodating such MAC address, an access bit (1 bit) indicating a history of accesses to such MAC address, and a valid bit (1 bit) indicating a validity/invalidity of registration. Here, the number of bits of a port number depends on the number of ports of the switch. In this case, since a maximum number of 16 ports is assumed, 4 bits are needed for a port number.
Therefore, one entry of the entry table 11 is decided in accordance with a 10-bit address obtained by the hash function, and a registered MAC address included therein is read and output to a comparator 12. The comparator 12 compares the registered MAC address to an input MAC address to judge match/mismatch.
However, since the 48-bit input data is degraded to 10-bit degraded data by the hash function, there is a possibility that different input MAC addresses are mapped into the same address. The frequency of occurrence of this collision depends on how a hash function is selected. In the event of occurrence of a collision, rehashing is performed to change the hash function so as to generate different hash outputs for different input MAC addresses.
The rehashing causes all of contents stored in the entry table 11 to be invalid, resulting in significant performance reduction of MAC address learning. Therefore, in consideration of the hashing mechanism, it is an important issue how the occurrence of rehashing is suppressed.
USPTO Backgrounds
USPTO Backgrounds