Multicast – Why Use Hash Instead of Simple Compare for Filtering Frames?

ethernetipv4multicast

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.

Best Answer

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.

Related Topic