DHash: A Cache-Friendly TCP Lookup Algorithm for Fast Network Processing 陈旻宇 PB14011074 王超逸 PB14207080

01 所做工作

01 所做工作 Dhash：新颖的哈希表数据结构和算法，为快速TCB设计 对缓存友好的 用于快速网络处理的 TCP查找算法 高效的算法，旨在支持在高速网络中的巨大数量的会话 使用Dhash增强构建在多核系统上的并行TCP/IP栈 可以以16.3Mpps的速率处理百万级别的TCP对话，超过了10Gbps网络连接的最大吞吐量:14.88Mpps

02 工作背景 相关工作

02 工作背景 传统TCP实现的瓶颈 TCP中，TCB用哈希表实现，但只有在负载系数比较低的时候才能快速查找， 如果限制哈希表大小，会增加哈希冲突(时间瓶颈） 对于TCB查找，很难实现空间-时间的平衡，但它又是重要的瓶颈 如图，TCB查找一直是最重要的瓶颈，在会话数量达到131，072时，TCB查找所占时间达到了恐怖的98.6%

02 相关工作 随着TCP会话数量的增加，TCB工作集会成比例增加 单纯地增加缓存大小只能起到有限的好处 存在一些改善哈希表查找的最坏情况的算法优化， 但是没有设计出适应现代电脑架构的算法，尤其是对于缓存的有效利用 HashCache:固定大小的非链表的哈希表 一系列硬件优化方案：仅处理少量对话，拓展昂贵，需要修改现有网络栈

03 解决方案

03 解决方案：主要思路/关键措施 数据结构 TCB工作集的线性增长源于TCB查找和访问的紧密耦合，是低性能的根源 链表的空间局部性较差，尤其在最后一级缓存不足的系统中 更换链表，用连续存储空间—固定大小(64bytes)的哈希桶，中间划分固定大小的slot 查找表应该尽可能紧凑 尽可能压缩信息，用32bit签名代替96bit的会话标识符，查找表不保存TCB位置，而是计算出来 Dhash数据结构：第i个哈希桶中的第j个slot,映射到TCB数组中， A[i*每个桶的元素个数+j]表示的TCB 如图：包含16个32位长的slot，预分配TCB阵列，前N个元素具有 一一映射查找表，其余作为TCB保留池

03 解决方案：主要思路/关键措施 签名算法 使用较短的签名，减少哈希表的大小 --可能会引入伪阳性(不同的会话标识符正好有相同的签名) ----每一次会话的签名都在查找表中匹配相应的TCB，由4元组确认匹配 每个TCP数据包都会被签名，所以需要低计算开销 --我们有四元组SrcIP DestIP SrcPort DestPort，下面给出4种算法 （1） 对四元组取异或 SrcIP⊕DestIP⊕SrcPort⊕DestPort （2） 计算SrcIP⊕DestIP和SrcPort⊕DestPort，并用他们计算CRC值 （3） 计算CRC（SrcIP | DestIP | SrcPort | DestPort和CRC（DestIP | SrcIP | DestPort | SrcPort） 再进行异或 （4） 计算CRC（SrcIP | DestIP | SrcPort | DestPort和CRC（DestIP | SrcIP | DestPort | SrcPort） 再将两个16位CRC值链接为32位，这是不对称的，第一次不匹配时，交换高低16位再比较

03 解决方案：主要思路/关键措施 用Major Location方法减少比较时间 当Hash桶为hit状态时，签名会一个个去寻找匹配，我们不应该从头开始匹配(期望为8次)，我们用类似于Major Location的机制来进行签名存储。 (图：Major Location的匹配机制) 当一个会话标识符被放入一个Hash桶时，我们计算它的Major Location作为匹配搜索起点，因为需要向两个方向搜索，Major Location应该是对称的。任何的4位签名算法都可以用于取得Major Location，比如：

03 解决方案：主要思路/关键措施 详细算法描述 1. 查找会话 1. 查找会话 收到TCP数据包后，会话标识符用于计算Hash索引和绘画签名，然后计算Major Location,从Major Location所指的slot开始移动到桶的末端，并在到达桶末端时重新启动以匹配TCB，匹配完成 后， 对应TCB被访问，进一步比较4元组确认是否为伪阳性，如果没有找到匹配，相应的冲突列表被检 查，最终返回一个TCB索引或者NOT FOUND 2. 添加会话 找到一个空slot，以及找到一个会话，将其存放在其中，返回对应的TCB，如果没有空slot，TCB 池包含的空TCB以及一个包含会话标识符的新元素，以及TCB位置被链接到冲突链表 删除会话 当会话关闭时，释放TCB，如果Hash中发现签名桶，清除slot为0，如果会话标识符在冲突列表中 被找到，Dhash将TCB放回TCB池中，并删除链表元素

04 其他内容 评论

04 其他内容&评论 文中剩余内容对于Dhash的负载因子，伪阳性率、系统矫正等内容做了分析，并且测试了Dhash的并行表现。 从图中我们可以看到，Dhash的性能比原始的TCB查询算法 的性能，在单核到多核的各个核心数量的表现是更加优秀的 并且，在7核的情况下，Dhash的处理速率超越了14.88Mpps 的速率线。 这说明Dhash的确是一个确实可行，并且是更优化的算法 除此之外，还对比了四种不同的签名算法的优劣性， 发现最后一种非对称算法速率最高，并且伪阳性率接近0 (不附图） 以及研究了运用Major Location方法的对性能的增强， 同样做出了非常有意义的工作

04 其他内容&评论 总体来说，这篇论文是一份非常有意义的论文，主要表现在从数据结构以及算法上，对现有TCP查询算法进行了改进，而不需要改变协议栈，并且切合了当前计算机体系结构的特点，针对Cache瓶颈做出了特别的优化(Cache-friendly) 最可贵的是，它能够满足特别大数量的TCP对话的要求，并且在并行系统上有非常优秀的表现，这表明了它距离应用到工业生产当中的距离已经非常小了，极有可能在应用中提升TCP查找的速度，解决实际的问题！