Method and apparatus for hashing addresses in a network switch

Claim 2

A hash system for selecting a destination network port for each of a plurality of binary address values received by a plurality of network ports, comprising: a hash memory for coupling to each of the plurality of network ports, for receiving binary hash values and for providing a corresponding port number identifying a destination network port; each of the plurality of network ports including hash logic for receiving a binary address value, for selecting a subset of bits of each received binary address value as a binary hash value, said subset of bits being determined by a bit enable value, for providing said binary hash value to said hash memory and for receiving a corresponding port number; and processor logic for coupling to each of said plurality of network ports and to said hash memory for sorting the plurality of binary address values among the plurality of network ports, for determining and periodically updating said bit enable value to optimize uniqueness of correspondingly updated binary hash values corresponding to the plurality of binary address values, for providing updated bit enable values to said hash logic of each of the plurality of network ports and for programming said hash memory according to said updated binary hash values.

Claim 3

The hash system of claim 1, further comprising: a hash bus for coupling to each of the network ports; and said hash memory comprising a random access memory device coupled to said hash bus, wherein said random access memory device receives binary hash values as addresses and provides port numbers as data on said hash bus.

Claim 4

The hash system of claim 2, wherein said hash memory comprises: first and second hash memories, wherein said processing logic enables either one of said first and second hash memories in a mutually-exclusive manner.

Claim 5

The hash system of claim 1, wherein said binary address values are media access control addresses.

Claim 6

The hash system of claim 4, wherein said bit enable value selects fifteen bits of each media access control address.

Claim 7

The hash system of claim 1, wherein said hash logic of each of the plurality of network ports comprises: an address enable register storing a bit enable value; a hash address shift register; and bit select logic coupled to said address enable register and said hash address shift register for shifting selected bits of each received binary address value into said hash address shift register.

Claim 8

The hash system of claim 1, wherein said processor logic comprises: a processor; and memory for storing an address map including received binary address values and corresponding port numbers.

Claim 9

The hash system of claim 7, wherein said processor monitors address collision workload as a relative amount of processing for handling collisions of said binary hash values.

Claim 10

The hash system of claim 7, wherein said processor periodically performs a single-bit comparison by calculating bit ratios for each bit of said received binary address values and selecting a subset of bit ratios closest to one for updating said bit enable value.

Claim 11

The hash system of claim 7, wherein said processor periodically performs a double-bit comparison for updating said bit enable value by calculating bit ratios for each bit of said received binary address values, and by selecting a subset of bits of a plurality of pairs of address bits having corresponding bit ratios closest to one and having relatively equal distribution between four groups determined by the bits of each pair of address bits.

Claim 12

The hash system of claim 7, wherein: said processor periodically performs a single-bit comparison by calculating bit ratios for each bit of said received binary address values and selecting a subset of bit ratios closest to one for updating said bit enable value; wherein said processor periodically performs a double-bit comparison for updating said bit enable value by calculating bit ratios for each bit of said received binary address values, and by selecting a subset of bits of a plurality of pairs of address bits having corresponding bit ratios closest to one and having relatively equal distribution between four groups determined by the bits of each pair of address bits; and wherein said processor selects the best bit enable value determined by said single-bit comparison and said double-bit comparison.

Claim 13

A network switch for transferring data packets between a plurality of network segments, each of the data packets including source and destination media access control (MAC) addresses, the network switch comprising: a hash memory for receiving a binary hash value and for providing a corresponding port number; a plurality of network ports coupled to said hash memory for receiving and transmitting data packets, each of said plurality of network ports including hash logic for retrieving a destination MAC address from each data packet received, for selecting a subset of bits of said destination MAC address as a binary hash value, said subset of bits being determined by a bit enable value, for providing said binary hash value to said hash memory and for receiving a corresponding port number corresponding to another one of said plurality of network ports; switch fabric coupled to said plurality of network ports for transferring data packets between said plurality of network ports; and processor logic coupled to each of said plurality of network ports and to said hash memory for sorting received MAC addresses among said plurality of network ports, for determining and periodically updating said bit enable value to optimize uniqueness of correspondingly updated binary hash values corresponding to received MAC addresses, for providing updated bit enable values to said hash logic of each of said plurality of network ports and for programming said hash memory according to said updated binary hash values.

Claim 14

A network switch for transferring data packets between a plurality of network segments, each of the data packets including source and destination media access control (MAC) addresses, the network switch comprising: a hash memory for receiving a binary hash value and for providing a corresponding port number; a plurality of network ports coupled to said hash memory for receiving and transmitting data packets, each of said plurality of network ports including hash logic for retrieving a destination MAC address from each data packet received, for selecting a subset of bits of said destination MAC address as a binary hash value, said subset of bits being determined by a bit enable value, for providing said binary hash value to said hash memory and for receiving a corresponding port number corresponding to another one of said plurality of network ports; switch fabric coupled to said plurality of network ports for transferring data packets between said plurality of network ports; and processor logic coupled to each of said plurality of network ports and to said hash memory for sorting received MAC addresses among said plurality of network ports, for determining and periodically updating said bit enable value to optimize uniqueness of correspondingly updated binary hash values corresponding to received MAC addresses, for providing updated bit enable values to said hash logic of each of said plurality of network ports and for programming said hash memory according to said updated binary hash values.

Claim 15

The network switch of claim 12, further comprising: a hash bus for coupling to each of said plurality of network ports; and said hash memory comprising a random access memory device coupled to said hash bus, wherein said random access memory device receives binary hash values as addresses and provides port numbers as data on said hash bus.

Claim 16

The network switch of claim 12, wherein said bit enable value selects fifteen bits of a media access control address.

Claim 17

The network switch of claim 12, wherein said processor logic comprises: a processor; and memory for storing an address map including received MAC addresses and corresponding port numbers.

Claim 18

The network switch of claim 15, wherein said processor periodically performs a single-bit comparison by calculating bit ratios for each bit of said received MAC addresses and selecting a subset of bit ratios closest to one for updating said bit enable value.

Claim 19

The network switch of claim 15, wherein said processor periodically performs a double-bit comparison for updating said bit enable value by calculating bit ratios for each bit of said received MAC addresses, and by selecting a subset of bits of a plurality of pairs of address bits having corresponding bit ratios closest to one and having relatively equal distribution between four groups determining by the bits of each pair of address bits.

Claim 22

The method of claim 18, further comprising the steps of: compiling a map of received binary addresses and corresponding port numbers; and said step of periodically updating the bit enable value including the step of calculating bit ratios for each bit of the received binary addresses and selecting a subset of bits closest to one as the updated bit enable value.

Claim 23

The method of claim 18, further comprising the steps of: compiling a map of received binary addresses and corresponding port numbers; and said step of periodically updating the bit enable value including the steps of: calculating bit ratios for each bit of the received binary addresses; and selecting a subset of bits of a plurality of pairs of address bits having corresponding bit ratios closest to one and having relatively equal distribution between four groups determined by the bits of each pair of address bits.