论文部分内容阅读
命名数据网络（Named Data Networking,NDN）是一种以数据内容为中心的新型网络架构,能有效解决传统TCP/IP网络在移动性、安全性和可扩展性等方面遇到的瓶颈,在工业互联网、智能家居、边缘计算、区块链等新型业务场景和领域已实现部署应用并获广泛关注。数据包交换理论是现代网络架构的基石,NDN也不例外。依据包交换理论,数据包查找转发是网络承载信息传输的关键核心操作,也是重要的性能瓶颈。在NDN中,转发平面数据包查找转发需解决的关键问题是数据名查找（Name Lookup）。不同于传统TCP/IP网络采用IP地址进行编址和寻址,NDN采用数据名来标识数据和网络报文,用于查找转发。相比于IP地址,数据名具有更强、更灵活的表达能力,但同时也加剧了包查找转发面临的性能挑战。首先,数据名的长度不定且没有上界,查找开销更大。其次,数据名的组成更加复杂,转发表的规模也更大,进而导致查找结构的存储开销也越大。此外,NDN中转发规则表地更新更加频繁,查找结构和算法的设计中必须综合考虑更新性能。大量研究表明,基于哈希的数据名查找机制具有较好的综合性能,也是NDN官方发布的转发引擎中采用的方案。然而,现有方案在查找性能和存储效率方面还存在一定的扩展性问题,难以应对链路速度和转发规则数目地持续增长。本文面向命名数据网络的转发平面,以哈希机制为基础,针对查找速度和存储效率的挑战研究高性能数据名查找算法。主要贡献如下:首先,针对现有方案在网络异常或遭受拒绝服务（Denial of Service,Do S）攻击等极端情况下查找性能急剧下降的问题,提出了一种基于特征前缀的数据名过滤算法（Feature Prefix based Name Filtering,FPNF）以保障极端情况下的查找性能,保障网络稳定性。核心思想是通过分析转发规则中数据名前缀的组成与分布特点,提取特征前缀构建布鲁姆过滤器,以快速过滤掉最终无法匹配有效规则的兴趣包,大幅提升数据名查找在大量不匹配场景下的性能。该方法可与现有多种数据名查找算法结合,协同完成高效数据名查找并保障极端情况的查找性能。为充分验证FPNF与不同算法的适配效果,本文选用多种数据名查找算法与FPNF结合进行性能评估。实验结果表明:FPNF算法虽然在常规场景下查找性能有所下降（8%左右）,但是在极端场景下性能可获得超过80%地显著提升,且随着不匹配数据名占比地增加,其性能提升效果越明显。FPNF算法与多种现有数据名查找算法相结合,能提高它们在极端情形下60%以上的查找性能。由此可见,FPNF有助于提高网络稳定性,提高网络适应更加复杂场景的能力。其次,针对主流多级哈希查找算法探测次数高导致的性能瓶颈,提出了一种全新的探测思路以提升查找性能。其核心思想是为不定长的数据名组件构建定长的字符索引,再用字符索引构建布鲁姆过滤器将哈希探测转化为布鲁姆过滤器探测。因为字符索引结构、长度确定且字符数目可控,方便一次读入进行高效处理。此外,连续多次地布鲁姆过滤器探测比连续多次哈希探测的缓存利用率更高,也可有效减少探测过程的访存开销,从而加快数据名查找。实验结果表明:本方法在常规场景和极端场景下分别能带来超过30%和80%地性能提升。此外,基于字符索引的数据名查找算法也可以与现有多级哈希数据名查找算法结合,适用性广泛,加快链路传输速度,更好地应对大规模转发规则集。此外,针对NDN转发引擎中的二分哈希查找算法BSH存储开销高的问题,提出了一种布鲁姆过滤器辅助的二分搜索算法（Bloom-filter assisted Binary Search,BBS）。其核心思想是将BSH算法中每个哈希表需要维护的数据名前缀细分为真实前缀（即真实存在的数据名转发规则）和虚拟前缀（即原始转发规则表中不存在、仅用于保障二分查找正确性的前缀）。因为虚拟前缀的特殊性,可采用布鲁姆过滤器进行维护以减少空间开销。在查找过程中,首先在虚拟前缀对应的布鲁姆过滤器中进行探测,然后再在相应的真实前缀哈希表中进行探测,综合两者探测的结果来共同决定二分查找的下一步。实验结果表明:BBS算法在实现高效二分查找的同时,相比BSH可压缩超过60%的存储开销。可见,BBS能在查找性能和存储效率之间获得更好地折衷,综合性能更优。该算法在保证提高网络快速信息传输的同时,能够更好地应对规则集数目增长的挑战。最后,针对现有方案难以兼顾长数据名查找性能和大规则表存储效率的问题,提出了一种基于分组分治策略的数据名查找机制。核心思想是根据规则长度在N个连续且不相交区间(0,L1],(L1,L2],,(Ln-1,Ln],（Ln,+∞）,中的分布情况对规则集进行分组。由于长度较长的数据名在规则集出现的频率非常低,这样选择合适的分组方案后每一个规则组要么只需维护少量的无长度上界的规则,要么只需维护大量有长度上界的规则。因此,可针对每一个规则组的特点采用不同的数据结构和算法,充分发挥不同查找算法的优势并规避其劣势,进而提升整体性能。初步实验结果表明:采用上述分组分治策略的数据名查找算法在查找速度和存储效率两方面均有显著提升,如采用分组分治策略的树形结构数据名查找算法比不采用分组策略的算法在查找速度上提升了2倍,而存储开销减少了超过70%。由此可见,基于分组分治策略的数据名查找算法能够更加灵活地处理大规模规则集带来的挑战,而未来更进一步地设计和优化会提升网络应对复杂场景的能力,使得NDN能够更好地满足各种新型技术、领域的需求。