Addressing mechanism for multiple look-up tables
AssigneeCisco Technology, Inc.
InventorHon Wah Chin
Life of this patent
Estimating the term…
Abstract
A hash table addressing mechanism enters multiple, overlaid look-up tables with a hash table address that corresponds to an X-bit index J that includes both bits associated with a V-bit identifier that selects the appropriate overlaid table, and a Y-bit identifier that hashes to an X-bit index I that selects the appropriate location within the selected table. The table includes hash bins with locations that contain Y-bit identifiers that map under the hash function to the same index I. For each addressed location the system compares the stored identifier with only the Y-bit identifier used to produce the index I, to determine which of the table locations is associated with both the Y-bit identifier and the V-bit identifier that were used to produce the hash table address.
Claims25
In a system that includes multiple overlaid look-up tables, a table addressing system including:
- A. a processor for producing a first X-bit index based on Y bits of a Y+V-bit identifier, the X-bit index being associated with the selection of a table entry;
- B. means for producing a second X-bit index by combining the first X-bit index with V bits that are associated with the remaining V-bits of the Y+V-bit identifier, said means adding the V bits using modulo 2.sup.Q addition, the second X-bit index being associated with a particular one of the multiple overlaid look-up tables.
A system including:
- A. multiple look-up tables, each of the respective tables being associated with a V-bit identifier and including information that relates to Y+V-bit identifiers;
- B. a hash processor for producing a first X-bit index that is a hash of the Y-bits of the Y+V-bit identifier which are not part of the V-bit identifier,
- C. means for producing a second X-bit index by combining V bits that are associated with the V-bit identifier with the first X-bit index;
- and
- D. table control circuitry that uses the second X-bit index to (i) enter the table that is associated with the V-bit identifier, and (ii) select therefrom a table location that is associated with the Y bits of the Y+V-bit identifier.
A network switch that transfers data packets between ports, some of which are members of one or more virtual local area networks, or VLANs, the switch including:
- A. n multiple look-up tables that contain information related to the routing of the data packets, the individual tables being associated, respectively, with one of the VLANs;
- B. means for producing an address for the look-up tables, said means including:
- i. a hash processor for producing a first X-bit index from a hash of information in the destination address field of the data packet;
- and
- ii. means for producing a second X-bit index, the means combining the first X-bit index with V bits that are associated with a V-bit VLAN identifier that is included in a VLAN identifier field of the data packet;
- and
- iii. means for producing a table address from the second X-bit index;
- and
- C. table control circuitry for using the table address to enter the look-up table that is associated with the VLAN identifier and select therefrom a table location that is associated with the destination address.
Dependencies are inferred from the claim text.