2

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.

4

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.

| improve this answer | |
  • +1. You are right. I think the key thing here, as you mention, is that a single host can be subscribed to multiple multicast addresses. In this case a hash surely makes better sense than software compares. – Pavan Manjunath Dec 8 '15 at 19:59
1

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.

| improve this answer | |
0

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.

| improve this answer | |
  • I think I have to disagree here. I know there are 32 IP addresses that can map to a single Eth address. But the books says "it can receive frames destined to other Ethernet multicast addresses" and NOT other IP addresses.The book also discusses hashing, indicating that 2 different MAC addresses can map to the same hash – Pavan Manjunath Dec 8 '15 at 0:19
  • The layer-3 multicast address is hashed to get the layer-2 multicast address. Perhaps the book worded it poorly, but this is a subject which is thoroughly understood. The hash is from layer-3 to layer-2 addresses for multicast. – Ron Maupin Dec 8 '15 at 0:21
  • Kindly see my latest edit. I've added more details from the book – Pavan Manjunath Dec 8 '15 at 0:28
  • You can believe me or not, but the multicast hash is from the 32-bit layer-3 multicast address to the 23-bit layer-2 multicast group. The 32-bit layer-3 multicast addresses don't have the problem because you can do perfect filtering of multicast groups since there is a 1:1 relationship between the layer-3 multicast address and the multicast group. The problem is with the layer-2 multicast addressing because it can't do perfect filtering since each layer-2 multicast address really represents 32 different multicast groups. – Ron Maupin Dec 8 '15 at 0:35
  • Your explanation seems very intuitive and logical. But your argument implies perfect filtering is impossible in layer-2 but the books quotes specific examples of interface cards that are capable of perfect filtering. How would you explain that? – Pavan Manjunath Dec 8 '15 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.