NDN 中名称查找方法对比

周炳晟，苗 笛，杨俊杰，王优祎康

（天津职业技术师范大学电子工程学院，天津 300222）

目前，互联网上大量的多媒体内容被广泛传输，并且移动应用的使用也变得越来越流行，因此高速数据传输的互联网流量正在飞速增长。在基于传统的IP网络中，IP 地址用来路由、寻址和传递数据包。用户如想访问互联网中的信息，应该基于内容提供商和信息请求者的IP 地址，在他们之间建立主机到主机的通信链路。如果多个用户向单个主机频繁请求相同的内容，则会出现传输瓶颈。为了解决这一问题，命名数据网络（name data networking，NDN）被认为是一个有前途的未来互联网技术。NDN 是一种互联网架构，用于将内容请求分发到网络中以前集中在内容源上的不同节点，其采用内容名称作为网络地址，使用前缀名称处理寻址、路由和传递的内容问题。NDN 的节点具有缓存能力，可以临时存储通过其路由的内容。如果NDN 节点接收到已经缓存在其缓存空间中的内容请求，其将立即向相应的用户提供所请求的内容。NDN 体系结构通过将内容存储在路由器等网络节点中，并重复提供不同用户请求的内容，有效地减少了网络流量。NDN 的提出有效地解决网络拥塞以及网络安全性不足等诸多问题。

本文分析NDN 内容名称的命名特点，以及现有NDN 名称查找策略的发展过程及其优缺点，对不同的查找策略进行综合对比，并提出NDN 名称查找策略下一步的研究方向。

1 NDN 的结构及名称查找

NDN[1]路由器的组件包括：①内容缓存（content store，CS），用于存储数据以响应新请求者即将到来的兴趣；②待定兴趣表（pending interest table ，PIT），它是一个用于临时存储兴趣包直至被满足的表；③转发兴趣表（forwarding information database，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 的一大挑战。

2 NDN 名称查找策略

2.1 名称查找分类

近年来，国内外众多科研小组围绕NDN 名称查找策略开展了系统的研究，研究方向大致分为FIB 名称查找、PIT 名称查找以及NDN 路由器的通用解决方案3 类。每个方案中的名称查找技术大致分为3 种：①基于前缀树查找方法。前缀树是一种有序的树形结构，已广泛应用于IP 地址查找[4-5]，在IP 领域是一种较为成熟的查找方法。在NDN 领域中前缀树将NDN 名称排成树形结构，从树根开始依次分叉开到树叶，然后根据要查找的名称，从低级别向高级别搜索，直到完全匹配。根据其结构特性的优势，前缀树可以通过聚合名称中的前缀冗余减少内存消耗，但前缀树的查找效率相对较差。②基于哈希表查找方法。哈希表也叫散列表，原理是将关键码值映射到表中的一个位置，以此来加快搜索速度。哈希表查找方法比其他方法要消耗更多内存，这是因为其需要存储整个名称字符串来处理哈希冲突并确保正确转发，还会造成假阴性的弊端。③基于布隆过滤器查找方法。布隆过滤器可以检测一个名称组件是否在一个集合当中。该方法是一种高效查找方法并且内存消耗较低，布隆过滤器从不生成假阴性，但可能会因哈希冲突而生成假阳性。据调查，目前并没有关于CS 名称查找方面的研究文献，因为CS 原理与FIB 相同。命名数据网络查找方案分类如表1 所示。

表1 命名数据网络查找方案分类

2.2 当前解决方案

2.2.1 FIB查找方法

FIB 也称转发信息库，维护NDN 路由转发表的转发信息。目前，在FIB 方向基于前缀树的NDN 名称查找的相关工作有很多，代表性的有：2014 年，湖南大学Li 等[6]研究了基于FPGA 的加速名称查找方法（hierarchical aligned transition array，HATA） 来 代 替GPU 名称查找方法（multi-ATA，MATA）。虽然多对齐转换数组MATA 有效地提高了查找速度，并且在一定程度上压缩了储存空间，但其查找延迟较严重。为了解决这一问题，该研究组提出分层对齐过渡数组HATA 来表示名称树，在FPGA 平台上实现了流水线加速NDN 名称查找。实验结果表明，内存占比为63.45%，与现有的GPU 解决方案相比，该方法的内存成本降低了90%以上，延迟降低了3 个数量级，吞吐量达到125 MLPS。2016 年，Lee 等[7]提出了一种名为路径压缩名称前缀树（path-compressed name prefix tree，PC-NPT）来降低内存需求，提高搜索性能。这种新的用于FIB 表查找的结构将路径压缩应用于名称前缀树中，进行单个子空节点的压缩。仿真结果表明，空节点数减少了97%以上。2016 年，Li 等[8]提出了一种基于多对齐转换数组（MATA）的P-tire 结构，该结构可以加快名称查找过程并且解决了转发的可扩展性问题。Ptire 结构的LPM 算法能够提前获取结束端口，且在不匹配时立刻返回端口。实验结果表明，P-tire 结构的吞吐量是MATA 的3 倍。

同样也有一部分FIB 方向基于哈希表的NDN 名称查找方法，如2014 年，Wang 等[9]提出了一种自适应贪婪策略来搜索最长的匹配前缀（greedy-SPHT）。其优点是通过动态调整搜索路径来进行应变。该方法不仅可以加快名称查找速度，还能够防御名称的攻击。该团队还开发出一种新型哈希表数据结构，将许多小的稀疏完美哈希表组合成一个更大哈希表，提高了查找速度并且减少了内存的压力。实验表明，在3 M 与10 M 条目下greedy-SPHT 的吞吐量达到57.14 MLPS，并且分别将内存消耗显著降低到72.95 MB 和247.20 MB，内存占比为45.11%。

2013 年，Wang 等[10]提出了单独使用基于布隆过滤器的FIB 查找方法，该查找方法分为2 个阶段。在第一阶段，将名称前缀的长度发送到布隆过滤器中，并且通过查询布隆过滤器来确定名称的最长前缀。在第二阶段，根据第一阶段的结果，在多个布隆过滤器的简化组中查找名称。在本文中使用布隆过滤器进行查找，可以有效减少内存消耗，加速名称查找。实验结果表明，NameFilter 在仅使用了237.27 MB 内存的情况下，实现了37 MLPS 的吞吐量，比经典的字符前缀树查找法快约12 倍，节省了4 倍内存，内存占比为30.1%。NameFilter 在平均工作负载和繁重工作负载下分别达到37 MSPS 和32.59 MSPS。与其他方法相比，内存消耗占比提高不大，并且NameFilter 的性能取决于前缀长度和路由器接口的数量，只能在特定环境发挥优势。

也有很多混合方法，将各个查找方法相融合，取其所长，代表性的有：2015 年，Tan 等[11]为解决内存效率问题，提出了一种名为名称分裂字符树法（split name character tree，SNT）。该方法首先将名称分解成多个组件，然后对这些组件分别进行哈希运算后构建成一个前缀树，再将该前缀树分成2 部分，分别对这2部分进行查找。实验结果表明，SNT 通过哈希计算可以减少约30%的内存开销，通过分解前缀树可以进一步减少约30%内存消耗。虽然维护哈希表需要额外的内存成本，但该方法仍将内存效率提高了23%～49%。2015 年，华盛顿大学的Yuan 等[12]提出了一种基于哈希表与二分搜索法的最长名称前缀匹配（longest name prefix matching，LNPM）设计。在每个节点，如果在相应的哈希表中找到匹配的前缀，则前进到右子树来搜索更长的匹配前缀；如果没有搜索到，那么最长的匹配前缀必须在左子树中。当到达叶FIB 条目时，则查找过程结束。实验结果表明，在7 个组件名称表中使用10 亿个最长名称前缀可以达到6 MLPS 的吞吐量。2017 年，He 等[13]对二分搜索法进行了深入的研究，团队提出了一种新的算法以确保快速搜索路径，并且无需额外的回溯代价和多余的内存消耗。该算法是一种布隆过滤器辅助的二分搜索法（BBS）算法，二分搜索法的散列查找次数比LNPM 少得多，但是在NDN 直接应用可能会占据大量内存，因此BBS 使用布隆过滤器在保持快速查找的同时，还可以减少内存消耗。实验表明，在查找速度方面，随着名称前缀数量的增加，BBS 的速度会比LNPM 的速度有较慢的衰减，BBS 仅比LNPM 增加了4%的内存消耗。2019 年，Wu 等[14]提出名为SNBS（split the name into basis and suffix）的名称查找方法，将名称拆分为2 部分，前半部分的组件存储在计数布隆过滤器CBF 中进行并行查找，降低假阳性发生的概率，后半部分使用树形图来减少树的长度，这样随着前缀名称数量的增加，其也可以保持相对稳定高效的查找性能。实验表明，SNBS 的吞吐量可以达到10 MLPS。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.5 MLPS。2020年，Kim 等[17]提出一种方法，该方法将分层哈希表与帕特里夏前缀树相结合，在每个组件上分层构建多个哈希表，每个哈希表可以动态变化。在产生哈希冲突时，可以使用帕特里夏前缀树解决。实验结果表明，该方法吞吐量可达到14.2 MLPS。

2.2.2 PIT查找方法

PIT 也称待定信息表，通过上游接受兴趣信息与下游接受数据信息的方式参与转发过程。在PIT 中，基于前缀树的查找方法最典型的是在2016 年Saxena等[18]提出的Radient。其将所有传入的名称请求分为多个组件，给每个组件分配一个令牌，使所有相同的组件都接受相同的令牌。当名称的所有组成部分都分配到令牌后，编码的名称就存储到前缀树中，以便更加快速查找。实验结果表明，在2 900×104个真实数据中编码的存储名称比不编码存储名称减少了87.63%的内存消耗，比ENPT 方案减少了35.45%的内存消耗，吞吐量为0.051 MLPS。虽然该方法比其他方法减少了更多的内存消耗，但在查找速率以及数据传输稳定性方面略有不足。

2013 年，So 等[19]提出了基于哈希表的PIT 查找方法SipHash，解决了恶意生成兴趣包导致哈希冲突的问题，并发挥了更好的性能。在FIB 的名称查找，使用了2 阶段LPM 算法。结果表明，在20 GbpsNDN 流量的吞吐量为8.8 MLPS。然而该方法使用哈希表导致了较高的内存成本，内存开销占比过高。2014 年，Yuan等[20]提出了一种新型PIT，将网络路由器分为核心路由器与边缘路由器。核心路由器存储16 bit 的指纹而不是名称字符串，边缘过滤器用来过滤。兴趣聚合功能解放了核心路由器，因此即使在指纹冲突发生时，也能保证数据包得到传递。实验结果表明，该吞吐量为0.83 MLPS，内存消耗为64.49 MB。

同样有一部分基于布隆过滤器的PIT 查找方法。如在2015 年，Carofiglio 等[21]提出了一种新的实现PIT的方法，该方法开发了一个PIT 动力学作为相关系统参数函数的分析模型，构建了高速内容路由器实现的实验平台研究PIT 动态，并确认分析结果的准确性，提供最优PIT 尺寸的指导方针，并分析具有跟踪驱动数据包延迟分布的ISP 聚合网络的情况。实验结果表明，该方法的内存消耗为70.35 MB，实现了更高的吞吐量。2014 年，Li 等[22]提出了PIT 的增强版MaPIT，提出一种新的数据结构MappingBloomfilter（MBF）来满足PIT 缩减其大小和快速操作的需求，在MBF 的基础上提出了MaPIT。实验结果表明，在片内存储中减少了99.34%的内存消耗。

2.2.3 NDN路由器查找方法

目前，NDN 路由器的查找方法一般为哈希查找以及布隆过滤器查找。2015 年，Feng 等[23]提出了一种新的编码机制，将NDN 名称用拆分运算符分层，在每一层使用哈希增量函数获得哈希序列，并且通过状态转移数组将哈希函数简化并且更新，使对名称的搜索、修改、删除更加快速。但是，该方法容易使NDN 路由器背负相当大的负载压力。同样在2015 年，Dai 等[24]提出一种名为BFAST 的数据索引结构，该结构采用计数布隆过滤器平衡哈希表之间的负载，使每个非空哈希表的前缀数量接近1，这样减少了查找时间并且提高了查找性能。实验结果表明，BFAST 的吞吐量可以达到36.41 MLPS，速度分别是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（multilevel binary search tree）构成。该方法也拥有防冲突驱动的编码机制，使其能够用最少的编码数量获得最快的名称查找与前缀更新。实验表明，CoDE 的查找速度是NCE 和NameFilter 的12.67 倍与7.36 倍，占用的内存节省了90.94%和69.79%。

3 综合对比分析

12 种基于FIB 的查找方法测试结果对比如表2所示，5 种基于PIT 和NDN 路由器的查找方法测试对比分别如表3 和表4 所示。

表2 12 种基于FIB 的查找方法测试结果对比

表3 5 种基于PIT 的查找方法测试结果对比

表4 5 种基于NDN 路由器的查找方法测试结果对比

从表2 可知，对NDN 中的名称查找方法性能比较以吞吐量与内存占比为主要基准，由于每个方法所比较的对象不同，对于内存消耗，可根据数据集的原始大小来评估内存消耗，吞吐量以MLPS 每秒百万次搜索为基准来进行对比。

从表3 可知，尽管搜索速度有所提高，但大多数随机搜索方法依赖于FIB 的重建，可能会导致所谓的回溯问题，从而导致假阴性，以及由于许多无用条目不能及时删除而造成的内存浪费。

从表4 可知，虽然名称搜索速度没有FIB 高，但内存开销占比明显减少，可以发现单纯使用某一个方案的查找方法，优点和缺点都很明显。内存消耗少的会产生误报，内存消耗高，误报率则随之降低。综合查找方案吞吐率和内存开销虽然没有明显的优势，但在查找速度与内存消耗方面非常稳定。

FIB 名称查找是基于LPM 最长前缀匹配算法，PIT 和CS 名称查找是基于EM 最大期望算法。因为3种组件的原理不同，所以寻找一种合适的处理方案来适应3 种不同组件是比较困难的，因此要分别讨论在不同组件上的查找方法，从而最大程度地提高查找效率。

4 结 语

本文整合了FIB、PIT、NDN 路由器的名称查找方法。分析得出，不同的名称搜索方案都有比较好的应对未来NDN 网络挑战的方法，这些优秀的方案共有的特点就是使用2 种及以上的混合查找方法，虽然查找速率不是最快，内存开销占比不是最佳，但在稳定性、有效性、延迟、误报率等方面有良好表现。本文所研究的NDN 名称查找方法大多数是在百万个名称前缀的基础上进行实验，所以不一定完全具有代表性，在未来研究中要多使用更大规模数据集，实现高速更新。此外，对名称可扩展性以及低延迟方面还需进一步研究，实现更高质量名称查找。在未来，NDN 的许多功能特性，如多路径转发、网络内缓存、安全、可伸缩转发以及网络内缓存等，可以用于网络应用，如车载通信、军事通信网络、会议教育系统、娱乐以及多媒体系统。NDN 在安全性方面也是未来探索研究的一个领域。其中，当用户节点和内容提供者之间的所有中间节点都可以使用内容请求时，攻击者可以通过监视内容请求来跟踪用户信息，目前还没有一个永久性的解决办法。总之，安全、信任管理和隐私仍然是NDN中一个开放的研究领域。