Why is a hash used instead of a simple compare for filtering multicast frames?

Question

From the book Unix Network Programming,

The frame is received by the datalink on the right based on what we call imperfect filtering, which is done by the interface using the Ethernet destination address. We say this is imperfect because it is normally the case that when the interface is told to receive frames destined to one specific Ethernet multicast address, it can receive frames destined to other Ethernet multicast addresses, too.

The book further goes on to explain why is this filtering imperfect -

...many current Ethernet interface cards apply a hash function to the address, calculating a value between 0 and 511...

My question is- Ethernet address is 6 bytes, out of which top 3 bytes are constant for any multicast ethernet address. All that is remaining is 3 bytes. Why not compare them, byte by byte instead of all the hash logic. The filtering would be perfect( at least at the ethernet level I mean, at the IP layer we may as well end up detect this frame does not belong to our multicast group) and logic is much more simpler.

What performance benefits does hashing have when contrasted with a simple compare?

EDIT: I think there is some confusion here. Its not about 32 IP addresses mapping into a single ethernet address. Cos if such was the case, perfect filtering at the ethernet layer would have been impossible. But the book goes on to give examples of cards that are capable of perfect filtering

Another interface card does perfect filtering for 80 multicast addresses, but then has to enter multicast promiscuous mode. Even if the interface performs perfect filtering, perfect software filtering at the IP layer is still required because the mapping from the IP multicast address to the hardware address is not one-to-one

The bolded line clearly states that the 32-1 mapping problem exists at the IP layer and not the ethernet layer.

Answer 1

The main benefit of hashing rather than a simple compare is that you can do one lookup for any number of enabled multicast addresses. The system that has an exact match for 80 addresses will either have to build logic to fetch 80 addresses into a comparator in turn, or have 80 comparators in parallel. That's a lot of gates, even if it is simple in concept. And that's all extra cost and power.

In contrast, a hash lookup can be easily implemented with a shift register and a few XOR gates. The computation and shifts can be done as the bits arrive on the wire. Even better, the NIC is doing this already, in order to calculate the checksum.

Note also, that Stevens was writing 20-25 years ago; whilst it is still more or less the definitive work on TCP/IP, hardware has come along since then. The cost of adding a few thousand more gates won't make so much difference. Flicking through a few NIC datasheets, most opt for a hybrid approach: e.g. 16 exact addresses and a 4096 bit hashtable.

Answer 2

Multicast (IPv4) is 224/4. So it's a 28-bit layer-3 address space. That has to be put into a 23-bit layer-2 (ethernet) address space. As such, there's some overlap. But that isn't what the book is talking about.

Multicast is fundamentally broadcast, so a nic will "see" all multicast traffic. A NIC that understands multicast -- and there are NICs that don't -- implements an internal "multicast filter" to determine what to send up to the OS. For a number of reasons (mainly speed and simplicity), it was popular to use a hash function (bunch of xor's) based on a very limited number of entries in a filter table.

Several (exact numbers I've never bothered to count) linux drivers "gave up". If multicast is enabled on the interface, it sets the chip to "all_multi" mode (multicast promiscuous mode) and does filtering in the driver.

Answer 3

What the book is describing is that a layer-3 multicast IP address is 32-bits, but the multicast group part of a layer-2 multicast MAC address is only 23 bits because the first 25 bits of the layer-2 multicast MAC address are fixed. It is an imperfect match, and a layer-2 multicast MAC address maps to multiple layer-3 multicast IP addresses. Each layer-2 multicast address maps to 32 layer-3 multicast addresses.

Suppose you want to subscribe to one layer-3 multicast group, but you want to filter a different layer-3 multicast group, and those two different layer-3 multicast groups map to the same layer-2 multicast address.