基于名称分类的NDN路由可扩展性改进方案

张 进，江凌云

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

命名数据网络(named data networking，NDN)[1]被认为是一个能够较好地满足用户对信息传递需求的新型网络体系结构。然而，它以数据名称进行通信在路由可扩展性问题上带来了相比于传统TCP/IP网络更加严峻的挑战[2，3]：实际的网络规模很大，人们对于信息的请求也很多，会出现数量较多的生产者和消费者，那么路由器节点将需要存储很多的名称条目。相比于固定长度的IP地址，NDN不定长度的层次化数据名称会使得FIB的表项数目成倍地增长，从而造成节点的负载(例如，内存等指标)加大，存在崩溃的隐患。因此，NDN传统的路由转发方案并不可靠，需要对其进行修改，使得网络可以承载更大的规模。然而，目前提出的路由可扩展性改进方案仍然存在着缺陷，例如基于映射的方案缺乏映射细节，基于跟踪的方案集中点负载更大等等。针对以上缺陷，提出了一种基于名称分类的路由可扩展性改进方案。

1 相关工作

针对NDN中路由可扩展性的种种难点，专家和学者们提出了一些改进方案，大致可以分为基于映射与封装的路由可扩展性改进方案和基于跟踪的路由可扩展性改进方案两类。

1.1 基于映射与封装的路由可扩展性改进方案

在传统IP网络中，虽然IP地址空间是有限的，但IP转发(路由)可扩展性一直被认为是互联网部署早期以来的主要挑战之一。其中保持路由表大小受控的一个方案是引入一个间接层：通过将不在全局路由表上的地址映射到表上的地址，可以到达不在全局路由表上的地址。这是映射与封装提案背后的主要思想。这种思想同样也可以运用到NDN当中，具体如下：

Afanasyev等[4]提出SNAMP机制，它将全局路由前缀放入无默认区域(default free zone，DFZ)FIB中，不在DFZ FIB中的数据名称可以通过其与全局路由前缀的关联——链接来进行检索，链接将要检索的数据名称委托给一个全局路由前缀。而这个前缀委托需要通过NDNS[5]的迭代查询来获得。然而，这些文献并没有交代映射的具体细节，同时仅依靠映射系统来提高路由可扩展性效果并不明显。

双曲线路由具有高可扩展性，因为节点无需维护路由表或FIB，而且除了学习邻居节点的坐标外，没有动态的路由更新，因此可以将其运用到NDN网络中。Lehman等[6]在NDN网络中采取了双曲线路由的方式。Yang等[7]通过在分配双曲坐标的同时综合考虑节点之间的中心性和内容的流行程度，提出了一种基于内容的双曲线路由，称为Pop-Hyper，提高了网络的路由性能。但是，双曲线路由在NDN 中的可行性取决于基础拓扑是否是双曲线的，这是个尚未探索的问题；另外，作为域间路由，双曲线路由如何支持路由策略是另一个等待探索的问题；此外，双曲线路由中兴趣包的转发可能陷入局部最优的情况，限制了它的使用。

Ahmed等[8]提出了一种基于名称的路由方案αRoute。该方案可扩展并提供内容查找保证。并且对于使用αRoute的Internet域间路由，提出了一种分布式覆盖到底层映射方案，该方案通过保留覆盖图中的邻接关系来实现底层(AS网络)中的最短路径路由。

1.2 基于跟踪的路由可扩展性改进方案

NDN采用有状态转发平面，其保留兴趣包所采用的路径的跟踪，使数据包跟随这些“面包屑路径”以逐跳方式返回数据请求者[9]。一些文献利用NDN的这一优势来提高网络的路由可扩展性，具体如下：

Shi等[10]提出自学习路由方案，其使用有状态转发平面为生产者建立消费者发起的路径跟踪。在路由过程中，没有匹配的FIB条目的情况下，兴趣包可以以泛洪或随机单播的方式来到达数据生产者。在数据包返回消费者的路上，沿着跟踪的每个路由器为相应的数据前缀创建FIB条目，指向数据包的传入接口。这样，数据名称前缀只出现在数据包经过的节点FIB表中，FIB表项数量会有所下降。然而，兴趣包通过泛洪或随机单播的方式传播会增大网络负担，同时减小兴趣包命中数据的速度。

Schmidt等[11]引入聚合点(NAC)，其包含所有的名称前缀，可通过默认路由(最短路径)到达，内容提供者需通过名称公告消息(NAM)在NAC处注册。兴趣包也沿默认路由到达NAC，再在NAC中的完整FIB的指引下到达名称提供者，如若没有，则进行泛洪。中间节点的FIB表不完整，需要使用自适应管理(基于名称流行度、附加时间戳等等)。然而，所有路由表项集中在聚合点(NAC)，虽然减小了其它节点的FIB路由表项，但在NAC处的FIB表项将成倍递增，网络规模过大时存在隐患。

Zhang等[12]提出一种名为KITE的基于跟踪的生产者移动性解决方案，同时也可用于解决FIB表项过多的问题。KITE通过在FIB中设置从固定会合服务器(RV)到移动生产者的路径，实现从移动生产者的数据检索。具体来讲，生产者首先向RV发出签名的跟踪兴趣包(TI)。RV验证TI并使用签名的跟踪数据包(TD)进行响应，然后返回给移动生产者。在接收TD时，中间路由器创建或更新指向TI输入接口的数据名称前缀的FIB条目。兴趣包会先到RV查找想要的数据名称，在RV处FIB表的指引下逐跳到达数据生产者。此时，数据名称前缀仅出现在跟踪的FIB中，从而减少了其它节点FIB表项数目。然而，此路由方案过于依赖固定会合服务器(RV)，RV中的路由表项数目远高于其它节点，存在隐患。

总的来说，这两类改进方案对网络的路由可扩展性都有一定的改善，但也存在明显的不足。基于映射与封装的方案映射细节没有给出、仅通过映射系统对FIB表项改进不明显、映射开销过大；基于跟踪的方案将表项集中在某一聚合节点会使得此处的FIB表项数目过多、负载过大。

2 基于名称分类的路由可扩展性改进方案

本节提出一种基于名称分类的路由可扩展性改进方案，解决上一节中提到的两类改进方案缺陷的同时，进一步提高网络的路由可扩展性。

2.1 总体拓扑结构以及网络的初始化过程

如图1所示的网络拓扑结构，我们假设网络中存在7个中间路由器、5个生产者、2个名称集中点，并且所有的网络中的节点已知网络拓扑结构，每个中间路由器都有自己本身的名称前缀，如路由器1的名称前缀为“/router/1”。全局名称集中点、非全局名称集中点是功能强大的存储设备，其作用与路由器相似，但其存储功能要优于中间路由器，可以存储数量较大的名称条目。接下来详细介绍网络的初始化过程。

图1 总体拓扑结构

2.1.1 生产者主动发布内容公告包

所有生产者沿着到达全局名称集中点的最短路径发送内容公告包到全局名称集中点，内容公告包中包含其可以提供的数据名称，如图2中5个生产者的内容公告所示。全局名称集中点以及内容公告包路径上的路由器节点根据内容公告包的传入接口建立FIB表，如图2中间路由器R2、R3的FIB中只包含生产者2、生产者3、生产者4的前缀条目，不包含生产者1、生产者5的前缀条目。而全局名称集中点的FIB中包含所有5个生产者的下一跳信息。

图2 生产者主动发布内容公告后网络状态

这一步骤首先在最初生产者主动发布自己可以提供的数据名称的内容，不需要兴趣包通过泛洪方式来寻找生产者，降低了网络中的流量。其次，数据名称只出现在内容公告包路径上的路由器节点的FIB表中，降低了其它网络中路由器节点的FIB表项数目以及负载。

2.1.2 不流行内容生产者发布不流行内容公告

随着网络规模的增大，网络中生产者、消费者增多，中间路由器节点以及全局名称集中点的负载和维护的FIB表项数目呈指数增长。这时，流行度较低(被请求频率较低)的数据名称的生产者主动发送不流行内容公告包(包括数据名称以及路由器名称)到全局内容名称集中点。起初不流行内容公告包的“路由器名称”字段是空的，当第一跳路由器节点收到不流行内容公告包时，将其路由器名称添加到“路由器名称”字段中。

之后的路由器节点收到此包后首先删除FIB表中包中携带的不流行内容名称的条目，然后检索FIB表中有无不流行内容公告包中“路由器名称”中存储的路由器名称的条目，如果有则不做操作，没有则将包中的路由器名称与不流行内容公告包到达接口的对应关系添加到FIB表中。全局名称集中点收到此包后执行相同操作，并将此包转发给非全局名称集中点。非全局名称集中点根据收到的不流行内容公告包，建立一张映射关系表，此表包括不流行数据名称(非全局路由名称)与路由器名称(全局路由名称)的一一对应关系。

例如，我们假设生产者2、生产者3、生产者4提供的数据内容是不流行的，这3个生产者发送不流行内容公告包到全局名称集中点。出于简单直观的考虑，图3中只画出了生产者2、生产者3的不流行内容公告以及它们在网络中的变化。实际上生产者4也具有不流行内容公告，同样在网络中变化，与生产者2、生产者3类似。起初不流行内容公告包的“路由器名称”是空的，如图3中生产者2、生产者3旁的不流行内容公告所示。当他们到达第一跳路由器R3时，将R3的路由器名称“/router/3”添加到包中的“路由器名称”字段中，并在FIB表中删除包中的不流行内容名称条目，再将修改过的不流行内容公告发送给R2，R2收到包后，在其FIB表中删除这3个不流行内容名称条目，并将R3的路由器名称“/router/3”和包的到达接口“face3”添加到FIB表中，之后将此包发送给全局名称集中点，全局名称集中点收到此包后执行与R2相同的操作，之后将此包转发给非全局名称集中点，非全局名称集中点根据此包建立映射关系表。

图3 不流行内容生产者发布不流行内容公告后网络状态

这一步骤首先不流行的数据名称被访问较少，因此不必在中间路由器节点存储这些数据名称和接口的对应关系，特别是在网络规模增大时。其次，上一步全局路由名称节点需要维护所有生产者可提供的数据名称与下一跳接口的对应关系，导致集中点的负载过大，存在隐患。而加入非全局路由名称集中点可以缓解全局集中点的压力，使得网络可以承载更大的规模。

2.2 兴趣包处理过程

基于名称分类的路由可扩展性改进方案的兴趣包处理过程也与传统的兴趣包处理过程不同，如图4所示，具体如下：

图4 兴趣包处理过程

(1)兴趣包到达某一路由器节点，首先检查内容存储(CS)中有无数据，有则返回数据，没有则检查待定兴趣表(PIT)中有无兴趣包中携带的名称条目，有则添加来源接口，没有则检查转发信息表(FIB)中有无兴趣包中携带的名称条目，有则从相应的接口转发到下一跳节点；

(2)如果FIB表中没有兴趣包中携带的名称条目，则将此兴趣包转发到全局名称集中点。兴趣包到达全局名称集中点后，检查全局名称集中点的FIB表中有无兴趣包中携带的名称条目，有则从相应的接口转发到下一跳节点，没有则检查兴趣包中是否携带转发提示；

(3)如果兴趣包中携带转发提示，则重新检索FIB表，在其指引下将兴趣包转发到下一跳节点。如果兴趣包中不携带转发提示，则将兴趣包转发到非全局名称集中点；

(4)兴趣包到达非全局名称集中点后，会检索映射关系表中是否存在其携带的名称条目，如果存在，则将其非全局路由名称所对应的全局路由名称作为转发提示添加到兴趣包中，修改过的兴趣包重新回到全局名称集中点，在其FIB表的指引下转发到下一跳节点；如果不存在，则丢弃此兴趣包。

2.3 兴趣包处理场景

2.3.1 全局路由名称兴趣包处理

我们考虑两个请求全局名称的兴趣包，它们分别请求“/tencent/movie”以及“/baidu/picture”数据，如图5所示。

我们先来处理兴趣包1，兴趣包1到达中间路由器R4后，查询CS、PIT、FIB后，都没有其请求的数据名称条目，那么中间路由器R4会将其转发到距离全局名称集中点最近的中间路由器R1。兴趣包1到达中间路由器R1后，同样检查其CS、PIT、FIB。在其FIB中找到了其请求的“/tencent/movie”名称前缀，则在其FIB指引下，从face5接口转发到达生产者1，如图5中实线箭头所示。

图5 全局路由名称兴趣包的处理

兴趣包2同样到达中间路由器R4后，查询CS、PIT、FIB后，都没有其请求的数据名称条目，那么中间路由器R4会将其转发到距离全局名称集中点最近的中间路由器R1，R1的FIB中也没有其请求的数据名称条目，R1就将此兴趣包转发至全局名称集中点，全局名称集中点的FIB中存在其请求的数据名称条目，则在其指引下到达R6，再在R6的FIB指引下到达R7，在R7的FIB指引下到达生产者5，如图5中虚线箭头所示。

从兴趣包1、兴趣包2的处理过程可以看到，生产者主动宣告自己可以提供的数据名称的内容可以有效降低中间路由器的FIB表项数目和负载，同时兴趣包找到生产者的时间相比之前通过洪泛等方式建立的网络来讲不会增加甚至更少。

2.3.2 非全局路由名称兴趣包处理

请求非全局路由名称“/sina/news”的兴趣包3到达R4后，查询R4的CS、PIT、FIB中都无“/sina/news”前缀条目，则R4将其转发给距离全局名称集中点最近的R1，R1中同样没有此名称前缀，R1将其转发给全局名称集中点，全局名称集中点查询后同样没有此名称前缀，则将其转发给非全局名称集中点，在非全局名称集中点的映射关系表中找到了此非全局名称前缀所对应的全局名称前缀“/router/3”，将其封装到兴趣包3中作为转发提示，再将封装后的兴趣包3转发给全局名称集中点，全局名称集中点检索兴趣包3中的转发提示，找到了“/router/3”所对应的下一跳接口“face3”，通过此接口将兴趣包转发给R2，R2同样检索转发提示通过接口“face3”将兴趣包3转发给R3，R3的FIB中存在其请求的数据名称前缀“/sina/news”，通过接口“face3”转发到达生产者3，如图6中箭头所示。

图6 非全局路由名称兴趣包的处理

从兴趣包3的处理过程可以看到，请求非全局路由名称的兴趣包相对于请求全局路由名称的兴趣包只是多了一步去非全局名称集中点查询的过程，对于兴趣包找到生产者的时间几乎没有影响，但可以大大减少这中间的路由器以及全局名称集中点的表项数目和负载，使得网络可以承载更大的规模，网络的路由可扩展性得到了改善。

3 实验和结果

在本节中，我们将对所提出的路由可扩展性方案进行仿真实验，实验平台为ndnSIM[13]，这是NDN团队开发的针对NDN实验的开源仿真平台，它是ns-3的扩展。

3.1 实验设置

为了得出我们提出的基于名称分类的路由可扩展性改进方案相对于基于跟踪的路由可扩展性改进方案[12](只有一个集中点，没有所谓的非全局路由名称集中点)在路由可扩展性上的优势，我们设计了两个简易拓扑，如图7、图8 所示。每个拓扑都有4个消费者、2个生产者，网络中的每个链路都具有1 Mbps带宽和10 ms的RTT。在所有情况下，兴趣包的大小为40字节，而数据包的大小为1024字节。在拓扑1中，选择一个中间路由器作为名称集中点。在拓扑2中，选择两个中间路由器，一个作为全局名称集中点，另一个作为非全局名称集中点。

图7 拓扑1

图8 拓扑2

同时，为了区分流行的内容生产者和不流行的内容生产者，我们规定Dst1为不流行内容生产者、Dst2为流行内容生产者。Src1为请求不流行内容的消费者，Src2、Src3、Src4为请求流行内容的消费者。4个消费者都是每秒发送100个兴趣包，转发策略采用最佳路由策略。由于我们专注于网络的路由性能，因此我们在仿真实验中不考虑缓存的影响。

3.2 实验指标

我们根据ndnSIM仿真平台可以实验出来的数据指标，选择以下3个指标进行仿真实验。

(1)路由器处理的兴趣包的数量：记录随着时间的推移，两套方案的中间路由器处理的兴趣包的数量的平均值。处理的兴趣包的数量越多代表网络可以承载更大规模的兴趣包的请求，也就意味着网络的路由可扩展性越强；

(2)时延：兴趣包的处理所需要的时间。兴趣包处理的越快，网络就可以处理更多的兴趣包，从某种意义上讲也是路由可扩展性性能的提升；

(3)丢包率：路由器丢弃的兴趣包数目与总的兴趣包数目的比值。每个路由器不可能处理完所有的兴趣包，一些处理不了的兴趣包会将其丢弃，例如全局集中点与非全局集中点都没有所请求的数据名称条目。丢包率越低，代表网络初始化的更加合理。

3.3 实验结果

3.3.1 路由器处理的兴趣包的数量

图9显示了我们的方案与基于跟踪的方案随着时间的推移路由器处理的兴趣包数目的实验结果。从图中可以看出，起初两种方案处理的兴趣包数目都很少，在0.5 s-1 s中都急剧增加，后面大体处于稳定的趋势。从二者的对比情况来看，我们的方案一直比基于跟踪的方案处理的兴趣包的数目更多。这是因为我们的方案将流行内容的兴趣包与不流行内容的兴趣包分开处理，与之前统一处理的方式相比路由器的负担会减少，相应的处理的兴趣包数量也会增多。

图9 路由器处理的兴趣包数随时间的变化曲线

3.3.2 时延

在时延方面，ndnSIM可以仿真出消费者兴趣包的两种处理时延：LastDelay、FullDelay。其中，LastDelay表示最后发送的兴趣包和接收到的数据包之间的延迟。FullDelay代表发送的第一个兴趣包和接收到的数据包之间的延迟(即，包括兴趣包重传的时间)。在图10中，我们仿真了FullDelay随着时间的变化，可以看到，基于跟踪的方案FullDelay随着时间的增加呈现波动上升趋势，而我们的方案FullDelay一直处在一个较低的值并保持平稳。在图11中，我们仿真了LastDelay随着时间的变化，可以看到，两种方案的实验值虽有波动但都保持平稳，我们的方案相对来讲时延更低一些。综上两个图可以得到，我们的方案的兴趣包需要重传的次数相对基于跟踪的方案会少很多，才会导致LastDelay二者相差不大，FullDelay相差悬殊。由此可见，我们的方案更能很好地处理兴趣包。

图10 FullDelay随时间的变化曲线

图11 LastDelay随时间的变化曲线

3.3.3 丢包率

图12显示了随着时间的推移路由器的丢包率的变化趋势。从图12中可以看到，两种方案都呈现上升后平稳的趋势，在丢包率这一指标来讲，二者差别不大，说明两种方案网络初始化都很合理，路由器丢包率处在一个正常水平。

图12 丢包率随时间的变化曲线

4 结束语

命名数据网络中的路由可扩展性是一个急需解决的问题，它直接影响到此网络结构能否运用到实际的大规模环境中。本文从基于映射与封装的方案以及基于跟踪的方案的基础上，针对它们的缺点，提出了一种基于名称分类的路由可扩展性改进方案。该方案首先让生产者主动宣告自己可以提供的数据名称内容到全局名称集中点，相比于洪泛会降低网络中兴趣包的流量，同时减轻中间路由器的负载；其次引入非全局路由名称集中点，分担了全局名称集中点的压力，进一步降低其它路由器的负载。实验结果表明，该方案相比基于跟踪的方案在路由器可以处理的兴趣包的数量、时延等指标上存在优化效果，验证该方案相比基于跟踪的方案进一步提升了路由可扩展性性能。下一步，准备从查表结构以及算法出发，提升查表速度，进一步提升网络的路由可扩展性。