Addressing mechanism for multiple look-up tables

Claim 2

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 Q addition, the second X-bit index being associated with a particular one of the multiple overlaid look-up tables.

Claim 3

The system of claim 1 wherein the V bits that are combined with the first X-bit index are the remaining V bits of the Y+V-bit identifier.

Claim 4

The system of claim 1 wherein 2 Q is the number of overlaid look-up tables.

Claim 5

The system of claim 1 wherein the Q of the modulo 2 Q addition is equal to X.

Claim 8

The system of claim 5 wherein the means for producing the second X-bit index adds the V-bit identifier to the first X-bit index using modulo 2 Q addition.

Claim 9

The system of claim 6 wherein 2 Q is the number of overlaid look-up tables.

Claim 10

The system of claim 6 wherein the Q of the modulo 2 Q addition is equal to X.

Claim 11

The system of claim 5 wherein the means for producing the second X-bit index subtracts the V bits from the first X-bit index using modulo 2 Q subtraction, where 2 Q is the number of overlaid look-up tables.

Claim 12

The system of claim 5 wherein the means for producing the second X-bit index subtracts the V bits from the first X-bit index using modulo 2 x subtraction.

Claim 13

The system of claim 6 wherein the V bits that are combined with the first X-bit index are the remaining V bits of the Y+V-bit identifier.

Claim 14

The system of claim 5 wherein the means for producing the second X-bit index XORs the V bits and the first X-bit index.

Claim 15

The system of claim 5 wherein: the table address selects a hash bin that is associated with stored Y-bit values that map to the first index; and the system selects the appropriate one of the stored Y-bit values by comparing the stored values with the Y-bit value used to produce the first index.

Claim 16

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.

Claim 17

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.

Claim 18

The network switch of claim 14, wherein the information used by the hash processor is a 48-bit media access control address.

Claim 19

The network switch of claim 15, wherein the hash processor includes: a. means for segmenting the 48 bits into four 12 bit words; b. combination means for combining corresponding bits of each of the words to produce a first 12-bit index, said means combining corresponding bits of the words ______________________________________ 35 34 33 32 47 46 45 44 43 42 41 40 31 30 29 28 27 26 25 24 39 38 37 36 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ______________________________________ where the numerals indicate bit positions.

Claim 20

The network switch of claim 14, wherein the means for producing the second X-bit index combines the first 12-bit index with a 10-bit VLAN identifier to produce a second 12-bit index.

Claim 21

The network switch of claim 17, wherein the means for producing second X-bit index further combines the index and the identifier by modulo 2 12 addition.

Claim 22

The network switch of claim 14, wherein the means for producing the second X-bit index combines the first X-bit index and the V bits by modulo 2 Q addition.

Claim 23

The network switch of claim 14, wherein the means for producing the second X-bit index combines the first X-bit index and the V bits by modulo 2 x addition.

Claim 24

The network switch of claim 14, wherein the means for producing the second X-bit index combines the first X-bit index and the V bits by modulo 2 n addition.

Claim 25

The network switch of claim 14, wherein the means for producing the second X-bit index combines the V bits and the first X-bit index by modulo 2 x subtraction.

Claim 26

The network switch of claim 14, wherein the means for producing the second X-bit index combines the V bits and the first X-bit index by modulo 2 n subtraction.

Claim 27

The network switch of claim 14, wherein the means for producing the second x-bit index XORs the V bits and the first X-bit index.

Claim 28

The network switch of claim 14, wherein the means for producing the second X-bit index manipulates the V bits of the VLAN identifier and combines the result with the first X-bit index.