NDN中名称查找方法对比

NDN中名称查找方法对比

周炳晟，苗笛，杨俊杰，王优祎康（天津职业技术师范大学电子工程学院，天津300222）目前，互联网上大量的多媒体内容被广泛传输，并且移动应用的使用也变得越来越流行，因此高速数据传输的互联网流量正在飞速增长。在基于传统的IP网络中，IP地址用来路由、寻址和传递数据包。用户如想访问互联网中的信息，应该基于内容提供商和信息请求者的IP地址，在他们之间建立主机到主机的通信链路。如果多个用户向单个主机频繁请求相同的内容，则会出现传输瓶颈。为了解决这一问题，命名数据网络（namedatanetworking，NDN）被认为是一个有前途的未来互联网技术。NDN是一种互联网架构，用于将内容请求分发到网络中以前集中在内容源上的不同节点，其采用内容名称作为网络地址，使用前缀名称处理寻址、路由和传递的内容问题。NDN的节点具有缓存能力，可以临时存储通过其路由的内容。如果NDN节点接收到已经缓存在其缓存空间中的内容请求，其将立即向相应的用户提供所请求的内容。NDN体系结构通过将内容存储在路由器等网络节点中，并重复提供不同用户请求的内容，有效地减少了网络流量。NDN的提出有效地解决网络拥塞以及网络安全性不足等诸多问题。本文分析NDN内容名称的命名特点，以及现有NDN名称查找策略的发展过程及其优缺点，对不同的查找策略进行综合对比，并提出NDN名称查找策略下一步的研究方向。1NDN的结构及名称查找NDN[1]路由器的组件包括：①内容缓存（contentstore，CS），用于存储数据以响应新请求者即将到来的兴趣；②待定兴趣表（pendinginteresttable，PIT），它是一个用于临时存储兴趣包直至被满足的表；③转发兴趣表（forwardinginformationdatabase，FIB），通过最长前缀匹配（LPM）将兴趣包转发给下一个路由器。NDN使用2种类型的包，分别为兴趣包和数据包。NDN通信由消费者驱动，消费者发送兴趣包以请求内容，内容提供商将数据包作为对兴趣包的响应转发给消费者，如果从消费者到内容提供商的路径上的任何中间节点具有满足兴趣包的数据包，则该节点可以提供该数据包。在通信时，数据包与兴趣包没有任何接口或主机地址[2]。兴趣包由消费者发送，而数据包由兴趣包建立的信息传递回来。在传统IP网络的传输架构下，随着数据的大量增加，数据传输效率变得低效。而NDN的结构区别于传统的IP结构，它把内容作为网络处理的基本对象，用名称作为数据查找的依据，为数据的高质量传输提供了更多的可能性。NDN的每个数据包的名称都是独一无二的，每个NDN名称由多个可变长度的名称组成。NDN名称采用分层的方式来组合构成，如名称为/a/b/c/有3个a/、b/、c/，名称组件被“/”分隔开；其名称前缀为/a/、/a/b/、和/a/b/c/。采用分层结构能够聚合名称，降低规范命名的工作量，减轻路由的压力并在一定程度上加快名称的查找速度。由于网络内容的庞大，路由会承受越来越大的压力，造成工作效率的降低，所以名称的结构也会影响名称的查找。尽管NDN重新构建了以数据为核心的网络架构，但其转发机制与传统网络类似，并且名称前缀依赖于最长前缀匹配（LPM），所以还不足以实现高质量快速查找。使用高速数据包转发，NDN的名称查找面临以下挑战：①长度不固定的名称。与固定长度的IP地址不同，NDN名称类似于统一资源定位符（URL）[3]，它有一个分层结构，由一系列带任何类型字符的分隔组件组成。另外，名称的长度不固定，理论上没有上限。因此，传统网络中的查找算法很难延续到NDN。②大型转发表。在NDN中每个传入的名称都会搜索一个带有一组名称前缀的前缀数据库。从这个意义上说，大规模的名称前缀数据库会极大降低性能。事实上，NDN命名前缀数据库的规模至少比传统网络大一个数量级。因此，迫切需要专用的名称查找算法来实现高吞吐量。③频繁更新。随着物联网、云计算和网络功能虚拟化的发展，网络应用必须在极短的时间内响应不同的用户需求，所请求的数据、拓扑和策略将频繁改变，使得数万个新的名称前缀被动态地插入名称前缀数据库，并且许多旧的名称前缀将同时被删除。因此，快速前缀更新是NDN的一大挑战。2NDN名称查找策略2.1名称查找分类近年来，国内外众多科研小组围绕NDN名称查找策略开展了系统的研究，研究方向大致分为FIB名称查找、PIT名称查找以及NDN路由器的通用解决方案3类。每个方案中的名称查找技术大致分为3种：①基于前缀树查找方法。前缀树是一种有序的树形结构，已广泛应用于IP地址查找[4-5]，在IP领域是一种较为成熟的查找方法。在NDN领域中前缀树将NDN名称排成树形结构，从树根开始依次分叉开到树叶，然后根据要查找的名称，从低级别向高级别搜索，直到完全匹配。根据其结构特性的优势，前缀树可以通过聚合名称中的前缀冗余减少内存消耗，但前缀树的查找效率相对较差。②基于哈希表查找方法。哈希表也叫散列表，原理是将关键码值映射到表中的一个位置，以此来加快搜索速度。哈希表查找方法比其他方法要消耗更多内存，这是因为其需要存储整个名称字符串来处理哈希冲突并确保正确转发，还会造成假阴性的弊端。③基于布隆过滤器查找方法。布隆过滤器可以检测一个名称组件是否在一个集合当中。该方法是一种高效查找方法并且内存消耗较低，布隆过滤器从不生成假阴性，但可能会因哈希冲突而生成假阳性。据调查，目前并没有关于CS名称查找方面的研究文献，因为CS原理与FIB相同。命名数据网络查找方案分类如表1所示。表1命名数据网络查找方案分类2.2当前解决方案2.2.1FIB查找方法FIB也称转发信息库，维护NDN路由转发表的转发信息。目前，在FIB方向基于前缀树的NDN名称查找的相关工作有很多，代表性的有：2014年，湖南大学Li等[6]研究了基于FPGA的加速名称查找方法（hierarchicalalignedtransitionarray，HATA）来代替GPU名称查找方法（multi-ATA，MATA）。虽然多对齐转换数组MATA有效地提高了查找速度，并且在一定程度上压缩了储存空间，但其查找延迟较严重。为了解决这一问题，该研究组提出分层对齐过渡数组HATA来表示名称树，在FPGA平台上实现了流水线加速NDN名称查找。实验结果表明，内存占比为63.45%，与现有的GPU解决方案相比，该方法的内存成本降低了90%以上，延迟降低了3个数量级，吞吐量达到125MLPS。2016年，Lee等[7]提出了一种名为路径压缩名称前缀树（path-compressednameprefixtree，PC-NPT）来降低内存需求，提高搜索性能。这种新的用于FIB表查找的结构将路径压缩应用于名称前缀树中，进行单个子空节点的压缩。仿真结果表明，空节点数减少了97%以上。2016年，Li等[8]提出了一种基于多对齐转换数组（MATA）的P-tire结构，该结构可以加快名称查找过程并且解决了转发的可扩展性问题。Ptire结构的LPM算法能够提前获取结束端口，且在不匹配时立刻返回端口。实验结果表明，P-tire结构的吞吐量是MATA的3倍。同样也有一部分FIB方向基于哈希表的NDN名称查找方法，如2014年，Wang等[9]提出了一种自适应贪婪策略来搜索最长的匹配前缀（greedy-SPHT）。其优点是通过动态调整搜索路径来进行应变。该方法不仅可以加快名称查找速度，还能够防御名称的攻击。该团队还开发出一种新型哈希表数据结构，将许多小的稀疏完美哈希表组合成一个更大哈希表，提高了查找速度并且减少了内存的压力。实验表明，在3M与10M条目下greedy-SPHT的吞吐量达到57.14MLPS，并且分别将内存消耗显著降低到72.95MB和247.20MB，内存占比为45.11%。2013年，Wang等[10]提出了单独使用基于布隆过滤器的FIB查找方法，该查找方法分为2个阶段。在第一阶段，将名称前缀的长度发送到布隆过滤器中，并且通过查询布隆过滤器来确定名称的最长前缀。在第二阶段，根据第一阶段的结果，在多个布隆过滤器的简化组中查找名称。在本文中使用布隆过滤器进行查找，可以有效减少内存消耗，加速名称查找。实验结果表明，NameFilter在仅使用了237.27MB内存的情况下，实现了37MLPS的吞吐量，比经典的字符前缀树查找法快约12倍，节省了4倍内存，内存占比为30.1%。NameFilter在平均工作负载和繁重工作负载下分别达到37MSPS和32.59MSPS。与其他方法相比，内存消耗占比提高不大，并且NameFilter的性能取决于前缀长度和路由器接口的数量，只能在特定环境发挥优势。也有很多混合方法，将各个查找方法相融合，取其所长，代表性的有：2015年，Tan等[11]为解决内存效率问题，提出了一种名为名称分裂字符树法（splitnamecharactertree，SNT）。该方法首先将名称分解成多个组件，然后对这些组件分别进行哈希运算后构建成一个前缀树，再将该前缀树分成2部分，分别对这2部分进行查找。实验结果表明，SNT通过哈希计算可以减少约30%的内存开销，通过分解前缀树可以进一步减少约30%内存消耗。虽然维护哈希表需要额外的内存成本，但该方法仍将内存效率提高了23%～49%。2015年，华盛顿大学的Yuan等[12]提出了一种基于哈希表与二分搜索法的最长名称前缀匹配（longestnameprefixmatching，LNPM）设计。在每个节点，如果在相应的哈希表中找到匹配的前缀，则前进到右子树来搜索更长的匹配前缀；如果没有搜索到，那么最长的匹配前缀必须在左子树中。当到达叶FIB条目时，则查找过程结束。实验结果表明，在7个组件名称表中使用10亿个最长名称前缀可以达到6MLPS的吞吐量。2017年，He等[13]对二分搜索法进行了深入的研究，团队提出了一种新的算法以确保快速搜索路径，并且无需额外的回溯代价和多余的内存消耗。该算法是一种布隆过滤器辅助的二分搜索法（BBS）算法，二分搜索法的散列查找次数比LNPM少得多，但是在NDN直接应用可能会占据大量内存，因此BBS使用布隆过滤器在保持快速查找的同时，还可以减少内存消耗。实验表明，在查找速度方面，随着名称前缀数量的增加，BBS的速度会比LNPM的速度有较慢的衰减，BBS仅比LNPM增加了4%的内存消耗。2019年，Wu等[14]提出名为SNBS（splitthenameintobasisandsuffix）的名称查找方法，将名称拆分为2部分，前半部分的组件存储在计数布隆过滤器CBF中进行并行查找，降低假阳性发生的概率，后半部分使用树形图来减少树的长度，这样随着前缀名称数量的增加，其也可以保持相对稳定高效的查找性能。实验表明，SNBS的吞吐量可以达到10MLPS。2019年，Byun等[15]提出了一种用于FIB查找的阶级优先树算法（LPT）和实现LPT的2阶段布隆过滤器结构。当搜索LPT时，如果遇到普通节点，则记住该级别，然后搜索下一个级别；当没有后续节点时，访问最后一个匹配级别的哈希表。如果哈希表所返回级别的名称前缀与输入的匹配，则可以完成对给定输入的搜索。2阶段布隆过滤器的前半部分为级别布隆过滤器I-BF和端口布隆过滤器p-BF。储存在LPT的级别信息被编程为I-BF，储存在FIB的输出信息被编程为p-BF。由于所提出的架构足够小，可以存储在片内存储器中，因此仅通过查询片内布隆过滤器而不访问片外散列表，FIB查找性能得到了极大的提高。2020年，Lee等[16]提出了一种新的布隆过滤器，名为双负载布隆过滤器（DLBF），其能够在单个布隆过滤器中保存成员信息与返回值。本文将PC-NPT存储在DLBF中，用来加速名称的查找。DLBF在FIB的片内，PC-NPT在片外。且PC-NPT的每个节点都被编程到片内DLBF并存储在片外FIB中。仿真结果表明，在使用内存更少的情况下，吞吐量为48.5MLPS。2020年，Kim等[17]提出一种方法，该方法将分层哈希表与帕特里夏前缀树相结合，在每个组件上分层构建多个哈希表，每个哈希表可以动态变化。在产生哈希冲突时，可以使用帕特里夏前缀树解决。实验结果表明，该方法吞吐量可达到14.2MLPS。2.2.2PIT查找方法PIT也称待定信息表，通过上游接受兴趣信息与下游接受数据信息的方式参与转发过程。在PIT中，基于前缀树的查找方法最典型的是在2016年Saxena等[18]提出的Radient。其将所有传入的名称请求分为多个组件，给每个组件分配一个令牌，使所有相同的组件都接受相同的令牌。当名称的所有组成部分都分配到令牌后，编码的名称就存储到前缀树中，以便更加快速查找。实验结果表明，在2900×104个真实数据中编码的存储名称比不编码存储名称减少了87.63%的内存消耗，比ENPT方案减少了35.45%的内存消耗，吞吐量为0.051MLPS。虽然该方法比其他方法减少了更多的内存消耗，但在查找速率以及数据传输稳定性方面略有不足。2013年，So等[19]提出了基于哈希表的PIT查找方法SipHash，解决了恶意生成兴趣包导致哈希冲突的问题，并发挥了更好的性能。在FIB的名称查找，使用了2阶段LPM算法。结果表明，在20GbpsNDN流量的吞吐量为8.8MLPS。然而该方法使用哈希表导致了较高的内存成本，内存开销占比过高。2014年，Yuan等[20]提出了一种新型PIT，将网络路由器分为核心路由器与边缘路由器。核心路由器存储16bit的指纹而不是名称字符串，边缘过滤器用来过滤。兴趣聚合功能解放了核心路由器，因此即使在指纹冲突发生时，也能保证数据包得到传递。实验结果表明，该吞吐量为0.83MLPS，内存消耗为64.49MB。同样有一部分基于布隆过滤器的PIT查找方法。如在2015年，Carofiglio等[21]提出了一种新的实现PIT的方法，该方法开发了一个PIT动力学作为相关系统参数函数的分析模型，构建了高速内容路由器实现的实验平台研究PIT动态，并确认分析结果的准确性，提供最优PIT尺寸的指导方针，并分析具有跟踪驱动数据包延迟分布的ISP聚合网络的情况。实验结果表明，该方法的内存消耗为70.35MB，实现了更高的吞吐量。2014年，Li等[22]提出了PIT的增强版MaPIT，提出一种新的数据结构MappingBloomfilter（MBF）来满足PIT缩减其大小和快速操作的需求，在MBF的基础上提出了MaPIT。实验结果表明，在片内存储中减少了99.34%的内存消耗。2.2.3NDN路由器查找方法目前，NDN路由器的查找方法一般为哈希查找以及布隆过滤器查找。2015年，Feng等[23]提出了一种新的编码机制，将NDN名称用拆分运算符分层，在每一层使用哈希增量函数获得哈希序列，并且通过状态转移数组将哈希函数简化并且更新，使对名称的搜索、修改、删除更加快速。但是，该方法容易使NDN路由器背负相当大的负载压力。同样在2015年，Dai等[24]提出一种名为BFAST的数据索引结构，该结构采用计数布隆过滤器平衡哈希表之间的负载，使每个非空哈希表的前缀数量接近1，这样减少了查找时间并且提高了查找性能。实验结果表明，BFAST的吞吐量可以达到36.41MLPS，速度分别是NameFilter、NCE和CCNx的1.27倍、4.49倍和12.4倍，该方法在高负载下查找时间以及查找性能有所减弱。2017年，Hsu等[25]采用了一种基于循环冗余校验的CRC-32编码方案，将所有名称前缀的长度都适当缩短，并将其部分合并减少名称前缀识别的次数，从而提高名称搜索的效率。实验结果表明，该查找方法将存储空间减少到26.29%，查找速度比原来的NDN方法提高了21.63%。然而，该方法与其他查找方法在查找速度与内存开销占比方面相比仍不占优势。同在2017年，北京理工大学的Liu等[26]提出一种新的名为CTrie方法，CTrie将原来的帕特里夏前缀树扩展为基于组件和基于字节的分层名称前缀树。实验结果表明，该结构比基于哈希表的解决方案快3.2倍，只耗费了38%的内存。该结构适用于为物联网提供较为弹性的NDN数据平面。2018年，Shen等[27]提出了一种名为CoDE的高效查找方法，由哈希表和新的数据结构多级二元查找树EBST（multilevelbinarysearchtree）构成。该方法也拥有防冲突驱动的编码机制，使其能够用最少的编码数量获得最快的名称查找与前缀更新。实验表明，CoDE的查找速度是NCE和NameFilter的12.67倍与7.36倍，占用的内存节省了90.94%和69.79%。3综合对比分析12种基于FIB的查找方法测试结果对比如表2所示，5种基于PIT和NDN路由器的查找方法测试对比分别如表3和表4所示。表212种基于FIB的查找方法测试结果对比表35种基于PIT的查找方法测试结果对比表45种基于NDN路由器的查找方法测试结果对比从表2可知，对NDN中的名称查找方法性能比较以吞吐量与内存占比为主要基准，由于每个方法所比较的对象不同，对于内存消耗，可根据数据集的原始大小来评估内存消耗，吞吐量以MLPS每秒百万次搜索为基准来