Scalable Multi-Hash Name Lookup Method for Named Data Networking

A Scalable Multi-Hash( SMH) name lookup method is proposed,which is based on hierarchical name decomposition to aggregate names sharing common prefixes and multiple scalable hash tables to minimize collisions among prefixes. We take the component instead of the entire name as a key in the hash functions. The SMH method achieves lookup speeds of 21. 45 and 20. 87 Mbps on prefix table with 2 million and 3. 6 million names,respectively. The proposed method is the fastest of the four methods considered and requires 61.63 and 89.17 Mb of memory on the prefix tables with 2 million and 3. 6 million names,respectively. The required memory is slightly larger than the best method. The scalability of SMH outperforms that of the other two methods.

基于混合计数布隆过滤器的高效数据名查找方法

数据名查找是信息中心网络、内容分发网络、5G核心网中基础功能组件的关键操作,需要面向大规模规则表进行最长前缀匹配,在查找速度、更新开销和存储开销等方面面临严峻挑战.首先设计了混合计数布隆过滤器(HyCBF),将数据名前缀和前缀标记维护在同一个计数布隆过滤器中同时保持二者的逻辑独立性.这样可在不增加额外存储开销和时间开销的情况下提供更丰富的指示信息.基于此,提出HyCBF辅助的二分数据名查找(HyBS)方法以实现高效查找.进一步,为缓解二分查找过程中因回溯导致的性能损失,为HyCBF中每个条目关联一个特征比特位图以降低其假阳性率.实验表明,HyBS相比现有方法在查找性能和更新速度方面具有明显优势,存储效率也有一定提升.此外,将HyBS集成到向量化数据包处理(VPP)框架中进行系统性能评估,结果表明HyBS可用于构建高通量可扩展的数据名查找引擎.

面向命名数据网的高性能内核级网络缓存方法

命名数据网(named data networking,NDN)是一种以信息为中心的新型网络架构方案,网内缓存是其核心功能之一。现有缓存模块主要以应用级缓存实现为主,存在网络操作效率低、设备兼容性差、部署位置受限等问题。相比于应用级缓存模块,内核级缓存模块可以直接且广泛地部署于通用网络设备上,有助于推动网内缓存技术的规模应用以及NDN网络方案的实际部署。然而,由于NDN网内缓存机制涉及频繁的逐包缓存操作,将网内缓存功能引入内核将会影响内核处理性能。针对这一性能问题,设计并实现了一种内核级缓存方法。该方法维护一个哈希表进行缓存的精确查找,利用NDN名称的结构性,在节点间构建字典树支撑NDN缓存模糊匹配功能。提出使用细粒度的逐槽锁保护缓存查找表,原子操作保护替换队列,将缓存操作多线程并行化。在Linux内核中实现了所提的多线程缓存模块,实验结果表明,所提出的方法可以将缓存模块查找延迟降低至现有方案的一半,并且通过多线程将吞吐量提升至6.785 Mpacket/s。

内容中心网络中名字查找技术的研究

内容中心网络作为一种新型的未来网络体系架构被提出，以满足当前互联网信息共享的需求。内容中心网络使用类似域名的层次化名字结构对内容进行标识、路由和查找。由于互联网中内容众多，使用名字前缀构建的路由表，比传统的IP路由表大2～5个数量级，且由于名字查找依旧遵循最长前缀匹配原则，使得实现高速名字查找是一个富有挑战性的难题。分析了名字查找的技术挑战、实施难点，介绍了主要技术方法以及当前在名字查找领域的主要研究成果。

NDN中快速的贪婪名称查找策略

针对当前基于Trie的变长层次化且可以无限长度的命名的数据网络(Named Data Networking,NDN)内容名称的最长前缀匹配查找策略存在复杂性高、查找速率低且树型数据结构的更新开销高等问题,导致算法效率低,提出一种快速的贪婪名称查找机制(FGNL)来实现数据包的快速转发。快速的贪婪的组件代码分配机制复杂性较低,容易实现,支持快速更新;组件编码树本质上是一个二维状态转移表,进一步转换成快速的哈希表查找;多哈希表结构创建速度快,且压缩存储空间,能够极大地加快名称查找的速度。实验结果证明,与字符查找树相比FGNL方案减少大约48.71%的内存,与NCE相比节省26.98%的存储空间,且查找速度获得了2倍的加速。评估结果也表明,该方案可以向上扩展来适应名称集潜在的未来增长。

命名数据网络中基于多级计数Bloom过滤器的名字查找方法研究

针对目前NDN中大多数基于Bloom过滤器的名字查找方法仅考虑速率而忽略冲突概率的局限,提出了一种考虑名字冲突概率并基于多级计数Bloom过滤器的名字查找方法.该方法的实验结果表明:相对于目前广泛研究的计数Bloom过滤器、哈希函数和d-left计数Bloom过滤器,所提方法能有效降低冲突概率.

基于深度布隆过滤器的NDN网络三级名字查找方法

为提高命名数据网络(Name Data Networking,NDN)路由过程中内容名字查找的效率,该文提出一种基于深度布隆过滤器的3级名字查找方法。该方法使用长短记忆神经网络(Long Short Term Memory,LSTM)与标准布隆过滤器相结合的方法优化名字查找过程;采用3级结构优化内容名字在内容存储器(Content Store,CS)、待定请求表(Pending Interest Table,PIT)中的精确查找过程,提高查找精度并降低内存消耗。从理论上分析了3级名字查找方法的假阳性率,并通过实验验证了该方法能够有效节省内存、降低查找过程的假阳性。

一种支持动态名字查找的NDN网络路由转发表设计

路由转发表是命名数据网络转发模块中重要的组成部分,转发表不仅要能被快速构建,还要支持高速的动态名字查找.所谓动态查找,是指当进行名字查找时,转发表还需同时支持表项的插入、更新和删除操作.设计二者兼顾的转发表仍是一大挑战,当前的研究成果主要是通过先构建路由表,再新建一个路由表索引来实现快速的名字查找,但对于高速动态名字查找效果仍然不佳.在本文中,我们将改进后的自适应基数树融合到转发表中,使转发表能利用基数树的特点,实现快速构建和动态名字查找,这种新的转发表称为自索引转发表.实验评估表明,自索引转发表有效提升了转发表的构建速度,保证了动态名字查找的效率,并在一定程度上节省了新建额外索引的内存开销.

基于神经网络的命名数据网学习型FIB研究

针对命名数据网转发信息库快速检索差异化名称数据、高效存储转发信息和有效支持最长名称前缀匹配机制的需求和挑战,提出了基于神经网络的命名数据网学习型FIB整体方案,称L-FIB.首先,介绍了L-FIB的索引结构LearningTree,通过使用塔式两级神经网络模型学习索引内容在存储器中的分布情况,实现更均匀的数据映射,降低映射冲突,提高存储效率.其次,研究了L-FIB的存储结构和名称数据检索算法,片内高速存储器部署多个与不同名称前缀组件数相对应的索引结构Learning Tree,片外低速存储器部署多个与索引结构Learning Tree对应的FIB存储池,并通过相应的名称数据检索算法实现对兴趣包的转发信息检索和转发信息更新操作,有效支持了命名数据网的最长名称前缀匹配机制,提高了名称数据检索速度.实验结果表明,L-FIB在误判概率、存储消耗和吞吐量方面的综合性能明显优于其他对比方案.在误判概率低于1%的条件下,L-FIB的索引结构存储消耗仅为58.258 MB,能够部署于高速存储器SRAM上.L-FIB的实际吞吐量约为11.64×10^6数据包/s,可以满足当前命名数据网对数据包快速处理的要求.

基于改进型MBF的命名数据网PIT存储结构研究

命名数据网(named data networking,NDN)是一种新型的未来网络架构,以解决当今TCP/IP(transmission control protocol/internet protocol)网络面临的问题。NDN路由器的转发平面采用了一个新的数据结构待定Interest表(pending interest table,PIT),用于记录所有待定兴趣包的转发信息,并根据此信息正确地转发返回的数据包。因此,设计一个高效的PIT存储结构对提高转发性能具有重要的作用。结合Bitmap提出一种改进的数据结构BMBF(bitmap-mapping bloom filter),该结构采用一个哈希函数实现多次哈希映射以提高检索速度,并利用Bitmap实现元素内存单元的地址偏移量的动态分配。同时,在此基础上提出PIT存储结构B-Ma PIT,通过管理多个动态存储空间实现片外存储消耗随元素数量改变而改变。通过仿真实验与现有PIT结构进行了性能对比,结果表明BMa PIT在存储消耗、数据表构建速度、吞吐量方面具有更优秀的性能表现。

基于流行度和CDT的NDN名称查找方案

针对命名数据网络在网络规模增大时造成的转发信息表(Forwarding Information Base,FIB)中的名称条目呈指数级爆炸性增长、内存占用大、名称查找速度慢等问题,提出了一种基于流行度和CDT的名称查找方案。该方案将FIB划分为计数布隆过滤器(Counting Bloom Filter,CBF)、流行FIB、Conflict-split Degraded Trie(“冲突拆分”Degraded Trie,CDT)以及辅助FIB。CBF用于快速筛选掉不在FIB中的名称前缀,流行FIB用于高流行度的名称前缀的快速转发,CDT用于减少树的深度以及节点的数目,辅助FIB用于辅助流行FIB的更新以及CDT中节点的快速定位。实验结果表明,该方案在创建时间、查找时间、内存占用上存在优化效果,从而提升了NDN中FIB的存储和名称查找性能。

NDN中名称查找方法对比

概述了命名数据网络(NDN)名称查找所面临的挑战以及实施难点。针对现有的22种名称查找方法,以查找吞吐率、内存开销占比和名称路由表3个因素作为衡量指标,分别采用基于前缀树、哈希表、布隆过滤器3种查找方案进行比对分析。结果表明:使用2种及以上的混合查找方案能够有效提高名称查找效率,为未来NDN的设计提供了新的思路。

面向NDN中名字查找的哈希布鲁姆过滤器

该文设计了一种面向NDN中名字查找的哈希布鲁姆过滤器(HBF)。HBF由位于片内存储器中的g个计数器布鲁姆过滤器(CBF)、g个计数器和位于片外存储器中的g个哈希表组成,每个哈希表与1个CBF和1个计数器关联。为了避免因部分CBF存入名字过多而导致HBF的高误判率,HBF通过二次哈希选择算法将NDN路由器中FIB/CS/PIT表项完整信息均匀分散保存于g个CBF和g个哈希表中,同时也利于数据包转发的并行处理。理论分析和实验结果表明在名字查找过程中,HBF利用片内存储器中CBF的定位与过滤作用,大幅度减少片外存储器的访问开销,提高数据包转发速率,有效避免泛洪攻击。

信息中心网络中的内容命名粒度研究

【目的】在信息中心网络中,内容命名粒度是影响网络效率特别是路由查表效率中的重要因素,然而具体关系尚待研究。【方法】本文从内容命名粒度对网络名字数量的影响出发,探究不同命名方式下内容命名粒度对内容请求数量以及不同命名方式下路由表规模的影响,进而得到内容命名粒度对路由查表效率的影响。【结果】探究发现内容命名粒度越小,名字数量和请求数量越多,(依命名方式不同)路由表规模可能变大、查表效率会降低。【局限】本研究的结果主要是基于论文调研、数据分析和本地测试,暂时缺乏真实网络测试的支撑。【结论】本文阐明了内容命名粒度对信息中心网络产生影响的各个因素以及这些因素间的相互关系,为相关领域进一步的研究工作打下理论基础。

基于改进哈希编码的路由查询匹配算法

路由查找算法是网络路由器关键技术之一,为了提高数据查询性能,提出一种基于改进哈希编码的路由查询匹配算法。利用哈希函数压缩数据名字,采用状态转换阵列实现名称最长前缀的快速匹配,将路由节点缓存因素引入路由决策,采用仿真对比实验对算法的性能进行测试。结果表明,与其它路由查询匹配算法相比,本文算法不仅降低了数据内存开销,大幅度减少平均查询时间,而且提高了数据路由查询的效率。

可编程虚拟化路由器的转发表查找技术综述

可编程虚拟化路由器是未来互联网的核心网络设备,即在一个物理路由器平台上并行实现多个相互独立的虚拟路由器。综述了可编程虚拟化路由器的转发表(forwarding table,FIB)查找技术。分析了FIB查找技术的性能与可伸缩性挑战,即查找吞吐量、存储空间和增量更新问题。讨论了多FIB融合的IP查找算法和基于NDN(named data networking)命名的非IP查找算法的研究进展。指出了OpenFlow的多域FIB查找和基于硬件的NDN线速转发是未来研究亟需解决的重点问题。

NDN名字查找算法的性能测试平台的设计和实现

在内容标记网络（NDN）中，越来越多的名字查找算法被提出。这些算法的性能包括速度、可扩展性以及更新性能等亟需评估。但是，NDN目前还处在研究阶段，没有大规模NDN网络部署，缺少真实的大规模名字查找表以及相应的流量。该文设计并实现了一个用于评测名字查找算法性能的软件测试平台——NDNBench。NDNBench包含4个部分：种子表分析器、名字表产生器、名字流量产生器以及更新流量产生器。实验发现名字表和流量的特征会在很大程度上影响NDN名字查找的性能。NDNBench平台将这些特征进行提取，形成可以量化的参数并提供给用户。用户通过调整NDNBench的不同参数，可以得到具有不同结构特征以及表项数目的名字查找表和相应测试流量，从而对名字查找算法性能进行测试评估。该文还对现有的一些名字查找算法进行评估。NDNBench已经在最近的一些工作中得到应用。

支持泛洪攻击检测的命名数据网PIT

针对命名数据网待定兴趣转发表中高效的变长名称数据索引、硬件可支持的存储消耗以及兴趣包泛洪攻击检测等问题,提出了基于字符卷积神经网络的认知索引模型(C&I),该模型能够支持路由名称数据的分类、聚合,降低名称数据的存储消耗.同时,基于C&I提出了支持兴趣包泛洪攻击检测的待定兴趣转发表(PIT)存储结构C&IPIT及其数据检索算法,通过多级存储器部署方式,分别在片上和片下的存储器中部署索引结构及存储空间.实验结果表明,C&I-PIT在名称数据聚合、存储消耗、泛洪攻击检测等方面具有良好的性能.

基于双向跳表的命名数据网内容存储池

针对命名数据网中内容存储池须要快速检索差异化名称数据、高效存储数据信息和有效支持缓存替换策略的设计需求,提出了一种基于双向跳表的命名数据网内容存储池的存储结构学习树-双向跳表(LT-DSL).该存储结构由部署于片上的学习树和部署于片下的双向跳表(DSL)两种数据结构组成.LT-DSL通过重新设计索引数据结构来学习索引内容在存储器中的分布情况,实现了数据的均匀映射,提升了存储效率,降低了存储开销;同时,通过采用全新的名称数据检索算法来快速检索名称数据,LT-DSL有效支持了缓存替换策略,加速了数据处理过程.实验结果表明:相比其他基于跳表的内容存储池方案,LT-DSL在有效支持缓存替换策略和满足网络丢包率低于1%的前提下,进一步提升了数据检索速度,降低了整体存储开销.