MB86960 Datasheet, PDF (33/65 Pages) Fujitsu Component Limited. – NETWORK INTERFACE CONTROLLER with ENCODER/DECODER (NICE)

MB86960
HASH TABLE
The Hash Table provides a means for filtering incoming
multicast packets so that the host processor does not have
to process ones that are not of interest. The principle
employed in this filtering scheme was originally
developed by computer science to arrange a large number
of elements of an array or database in such a way that
facilitates searching for elements associated with a given
key or datum. The ‘hash function’ is a mathematical or
logical function which maps all possible elements in a
domain onto a smaller domain called the ‘hash table’.
As an example, suppose the following hashing function
is used: “Treating the multicast address as a non-negative
48-bit integer, divide this number by 64 and take the
remainder.” This function will map all multicast
addresses into a 64-element hash table since the
remainder can be only the integer values 0 through 63.
Applying this hashing function results in taking the
least-significant 6 bits of the multicast address as an
integer. In the hash table, for each element, 0 through 63,
a single bit is stored which indicates whether the address
is to be accepted (1) or rejected (0). If, for example, the
node belongs to three multicast groups, only three or
fewer of the hash table elements will store 1’s, the rest
0’s. The scheme allows the acceptance of any number of
the addresses, including all of them. The limitation is that
there may be addresses not of interest used on the network
which also fall into the ‘accept’ elements, so in this case
the filtering is imperfect. But in any case, most of the
nonapplying addresses can be filtered out in this way.
The actual hashing function used in the NICE chip is this:
“Calculate the CRC on the multicast address and take the
high-order 6 bits of this calculation”. The six bits are used
to address the elements of the hash table. If a 1 is stored in
an element of the table, associated packets are accepted.
The hash filter criterium is only used on multicast
addresses, which all start with a 1. Node ID’s, which start
with a 0, are not filtered by the hash filter. The broadcast
address, a special case of the multicast set wherein all the
bits are 1’s, will be accepted anyway unless the “Reject all
packets” mode is selected.
Figure 12 shows the register core, a modified shift-right
register, used in generating and checking CRC’s.
Whereas some controllers share a single such core
between transmitter and receiver, NICE has two of these,
one for the generator and one for the checker, allowing
both to operate concurrently for self-receive. To begin
the calculation, the register is first set to all 1’s. For the
generator case, as the packet is transmitted, the data is
clocked serially into the left-hand end of the register
starting with the 48 bits of the destination address (the
preamble is skipped). After the last bit of the ‘data’ field is
clocked into the register, the CRC calculation is finished.
The feedback line is then forced low and the register
becomes a simple shift-right register. Its contents are then
shifted out serially and transmitted, appending the CRC
to the end of the packet. For the CRC checker, the
calculation starts out the same way as for CRC generation
feeding the incoming data into the register. But in this
case, the CRC field of the packet is also fed into the
calculation. The result is a fixed constant in the register if
no CRC error has occurred.
For the Hash Filter, after the last bit of the destination
address has been clocked into the register, the left-hand
six register bits are stored in another register used to
address the Hash Table elements. The left-most bit is most
significant. The left-most three bits are used as the Hash
Table register address and the right-most three as the bit
address within a register byte. Having selected a Hash
Table element in this way, a 1 in the table will indicate the
packet is to be accepted, provided it is a multicast packet
(first bit of destination address must be 1), and passes the
error filters.
The hash filter is only employed when the address filter
mode select bits, AF1, AF0 are 0, 1, selecting the “NODE
ID, Broadcast, Multicast + Hash Table” mode. Like the
NODE ID registers, the Hash Table registers should only
be accessed when the receiver is disabled, i.e. when DLC
EN is high, to avoid interaction with the receiver. There
are eight bytes of registers in the Hash Table containing
the 64 1-bit elements (refer to Table 1 for location).
Source code software examples showing how to calculate
entries for the Hash Table are available from Fujitsu
Microelectronics, Semiconductor Division, in C and
assembly language.