为什么使用散列而不是简单的比较来过滤多播帧?

网络工程 以太网 ipv4 多播
2021-08-03 03:42:51

来自Unix Network Programming一书

该帧由右侧的数据链路根据我们所说的不完善过滤接收,这是由接口使用以太网目标地址完成的。我们说这是不完美的,因为通常情况下,当接口被告知接收目的地为一个特定以太网组播地址的帧时,它也可以接收目的地为其他以太网组播地址的帧。

这本书进一步解释了为什么这种过滤不完美——

...许多当前的以太网接口卡对地址应用哈希函数,计算 0 到 511 之间的值...

我的问题是 - 以太网地址是 6 个字节,其中前 3 个字节对于任何多播以太网地址都是恒定的。剩下的就是 3 个字节。为什么不逐字节比较它们,而不是所有的哈希逻辑。过滤将是完美的(至少在以太网级别我的意思是,在 IP 层我们也可能最终检测到这个帧不属于我们的多播组)并且逻辑要简单得多。

与简单比较相比,散列有哪些性能优势?

编辑:我认为这里有些混乱。它不是将 32 个 IP 地址映射到单个以太网地址。因为如果是这样的话,以太网层的完美过滤将是不可能的。但是这本书接着给出了能够完美过滤的卡片的例子

另一个接口卡对 80 个多播地址做了完美的过滤,但随后必须进入多播混杂模式。即使接口进行了完美的过滤,IP层仍然需要完善的软件过滤,因为IP组播地址到硬件地址的映射不是一一对应的

粗线清楚地表明 32-1 映射问题存在于 IP 层而不是以太网层。

3个回答

散列而不是简单比较的主要好处是您可以对任意数量的已启用多播地址进行一次查找。具有 80 个地址的精确匹配的系统要么必须构建逻辑以依次将 80 个地址提取到比较器中,要么并行使用 80 个比较器。这是很多门,即使它在概念上很简单。这都是额外的成本和电力。

相比之下,哈希查找可以通过移位寄存器和几个异或门轻松实现。当位到达线路时,可以完成计算和移位。更好的是,NIC 已经这样做了,以计算校验和。

另请注意,史蒂文斯是在 20-25 年前写作的;虽然它或多或少是关于 TCP/IP 的决定性工作,但从那时起硬件就出现了。再增加几千个门的成本不会有太大的不同。浏览一些 NIC 数据表,大多数人选择混合方法:例如 16 个精确地址和 4096 位哈希表。

多播 (IPv4) 是 224/4。所以它是一个 28 位的第 3 层地址空间。必须将其放入 23 位第 2 层(以太网)地址空间。因此,存在一些重叠。但这不是本书要讨论的内容。

多播从根本上说是广播,因此网卡将“看到”所有多播流量。理解多播NIC——也有不理解多播NIC——实施内部“多播过滤器”来确定向操作系统发送什么。出于多种原因(主要是速度和简单性),基于过滤表中非常有限数量的条目使用散列函数(一堆异或)是很流行的。

几个(我从来没有费心去计算的确切数字)Linux 驱动程序“放弃了”。如果在接口上启用了多播,它会将芯片设置为“all_multi”模式(多播混杂模式)并在驱动程序中进行过滤。

书中描述的是三层组播IP地址是32位,但是二层组播MAC地址的组播组部分只有23位,因为二层组播MAC地址的前25位是固定的。这是一个不完美的匹配,一个二层组播MAC地址映射到多个三层组播IP地址。每个二层组播地址映射到32个三层组播地址。

假设您要订阅一个三层组播组,但要过滤不同的三层组播组,并且这两个不同的三层组播组映射到同一个二层组播地址。