时间戳

首页 > 解决方案 > 用于 tcp 哈希表的 5 个 turple（src ip、src 端口、dst ip、dst 端口、协议）的高效哈希

network-programming - 用于 tcp 哈希表的 5 个 turple（src ip、src 端口、dst ip、dst 端口、协议）的高效哈希

问题描述

我发现了一些函数示例，可以快速散列一个 5 元组，以识别 tcp 连接表中双向流以进行 tcp 流重组（sha/md5 太慢..）

例如

((size_t)(key.src.s_addr) * 59) ^
((size_t)(key.dst.s_addr)) ^
((size_t)(key.sport) << 16) ^
((size_t)(key.dport)) ^
((size_t)(key.proto));

或者这个，其中 K 是一个哈希表大小为 n 的键，并使用异或运算符，其中异或运算可以表示为

H(X) = k1⊕k2⊕...kn

或者以下 97 位 (32+32+16+16+1) 的 ips/ports/proto 是否会提供足够的随机性而不会发生冲突

src ip 80.229.161.151 = 1357226391
dst ip 80.229.161.159 = 1357226399
src port 35555 
dst port 80
tcp 6

H(X) = 1357226391 * 97 ⊕ 1357226399 * 97 ⊕ 35555 * 97 ⊕ 80 * 97 ⊕ 6 * 97

hash key = 131654394123 ???

https://www.researchgate.net/publication/281571413_COMPARISON_OF_HASH_STRATEGIES_FOR_FLOW-BASED_LOAD_BALANCING

如果我这样做对，有人可以解释一下吗？

或者向我指出一些解释如何做到这一点的好论文？

标签： network-programming

解决方案

底线是：这取决于。如果您的流量中的源 IP 和目标 IP 分布良好，并且端口分布良好，则可能其中任何一个都适用于哈希表。但是，如果您碰巧正在查看在一小部分 IP 地址之间具有许多连接或具有很少不同端口的网络流量，事情就会变得更加复杂。

通常，对于散列表，散列的结果不需要是完美的。这并不是说您需要完全消除冲突，您只是不希望它们频繁出现，或者导致许多条目共享一小组哈希桶而许多其他哈希桶未使用。但这在很大程度上取决于您的应用程序以及您的网络流量来自何处。在最坏的情况下，最好尽量减少对输入和设计的依赖。

一种经常用来最小化这种冲突的方法是找到一个快速、有效、非加密的通用哈希，然后将元组中的所有地址和端口布置在一个连续的缓冲区中，在缓冲区上运行哈希函数并折叠将结果放入哈希表索引中。

下面的第一个链接是这个定义：

非加密哈希函数将字符串作为输入并计算整数输出。散列函数的理想特性是输出均匀分布在可能输出的域中，尤其是对于相似的输入。与密码散列函数不同，这些函数并非旨在承受攻击者寻找冲突的努力。

（为了澄清最后一句话，这些散列函数确实最大限度地减少了冲突；只是没有努力使它们抵抗可能导致构造冲突的密码分析。）

看看这些页面，其中包含有关“最近”发展的大量信息：

一般来说，这些散列会比 ad-hoc XOR 实现慢，但比 SHA 和 MD5 等加密散列快得多。当然，散列函数的速度是你必须做出判断的东西——但根据我的经验，获取 TCP/IP 5 元组的散列以用作散列表的索引很少会成为显着的性能瓶颈。通常处理的其他部分在性能方面要昂贵得多 - 特别是如果您将进行 TCP 流重组：这将需要大量的缓冲区和内存管理、数据复制等。

使用通用哈希函数的另一个优点：当您准备好添加 IPv6 支持时，不需要新算法。您只需布置一个更大的缓冲区，将您的 16 字节 IPv6 地址复制到其中，然后运行相同的散列函数。

另请参阅 Software Engineering SE 中的相关问题，该问题具有“现场”的优势： https ://softwareengineering.stackexchange.com/q/49550/261672

推荐阅读