论文部分内容阅读
IP地址查找(简称IP查找)是TCP/IP网络中路由器、交换机等设备转发数据包过程中的一项核心技术。随着互联网的日益普及,网络规模持续增大,转发信息表需维护的表项也越来越多,这就加剧了IP查找方案的存储压力。大多数存储压缩方案都会牺牲一点查找性能或更新效率为代价,而拆分模型则在压缩存储的同时还能实现非常好的综合性能。但其片外存储开销大,且增长快,制约了其在实际系统中的部署应用。鉴于此,本文重点研究基于拆分模型的哈希机制,旨在保障片上存储效率和综合性能优势的前提下大幅提升片外存储效率,跨越拆分模型从理论到实践的最后一道鸿沟。首先,本文对拆分模型进行了深入研究和分析,针对拆分模型片下查找的键值取值范围固定且可预知而哈希条目易于分组的特点,提出了一种基于键值映射的分组哈希(Key-Mapping based Group Hashing,KMGH)机制。首先对哈希条目进行分组,然后在片上存储中维护一个固定大小的键值映射数组,将待检索的键值映射到一个更小的值域,以减小构建哈希表的开销。同时,为每一个哈希表维护一个高效的空位列表以提升哈希表的存储利用率。这样,在保持一次查找一次片外访存的前提下,大幅减少了片外存储开销。实验结果表明,拆分模型原有的实现相比,KMGH仅消耗额外的256K片上存储资源就能使片外存储效率提升超70%。而在整体上与现有的优秀算法相比,拆分模型配合KMGH在片上和片外的存储效率提升分别超过了80%和90%。此外,本文还进一步研究了KMGH机制在叶推、多步长前缀树场景下的应用。提出了高效的哈希组融合算法(Hash Group Fusion Algorithm,HGFA),以及三层步长择优算法(Three-level Optimal Strides Algorithm,TOSA),以综合存储评价指标为目标函数采用动态规划确定最优步长。并成功将拆分模型配合KMGH应用到了现有的优秀算法中。实验表明,在不改变算法本质和优势的前提下,基于拆分和KMGH的实现在片上和片外存储效率上都能获得显著的提升。