命名数据网络中的转发策略研究

杨若冰，马严（. 北京邮电大学网络技术研究院，北京 00876；. 北京邮电大学，北京 00876）

命名数据网络中的转发策略研究

杨若冰1，马严2
（1. 北京邮电大学网络技术研究院，北京 100876；2. 北京邮电大学，北京 100876）

以信息为中心的网络（Information Centric Networking，ICN）架构是一个面向未来的互联网体系结构，它提供了一个更加安全，高效和可扩展的服务。命名数据网络（Named Data Networking，NDN）是ICN的几种具体实现方式之一，路由和转发机制是NDN网络中的核心。本文对NDN中的几种转发策略进行了全方位的分析，通过不同的指标来评估转发策略的性能，如网络时延，报文命中距离，报文重传次数等。实验使用了ndnSIM进行模拟仿真。从仿真结果中得出，选择一个单一的最优秀的转发策略是很困难的，另外，不同的转发策略的优势和劣势也受到网络环境的较大影响，反之，不同的策略也影响了NDN架构所特有的分布式缓存机制的效果。最后，本文对不同的转发策略适用的网络情况进行了分析和总结。

计算机网络；命名数据网络；内容中心网络；转发策略

0　引言

从社交网络服务增值到查看和分享数字内容，如视频、照片、文档等，因特网不再简单的提供基本的连接性，而是变成了一个有着大量从内容提供者到内容消费者的内容流的巨大分发网络。互联网用户如今需要的是更快，更高效，更安全的内容入口，而不再关心内容的位置。因此，未来的网络需要从所关注的数据在哪儿（地址和主机）转移到数据是什么（用户和应用关心的内容）。

以内容为中心的网络[1]是一个以唯一命名的数据为核心的互联网基础设施架构。数据独立于位置、应用、存储以及各种传输方式，并且使用了网络内部的缓存功能。可以预期的是，这样的架构会带来效率的提升，关于信息与带宽需求的更好的可扩展性，以及网络在具有挑战的通信情景中的更好的鲁棒性。

目前的互联网保障的是数据容器的安全，而NDN（Named Data Networking）[2]保障的则是内容的安全。这个设计决策将对数据的信任从对主机的信任解耦[3]，使得一些从根本上可扩展的通信机制成为可能，例如利用自动的缓存机制来优化带宽消耗的方法。

作为NDN网络的核心，路由和转发平面的架构也与IP网络有着根本上的不同，有状态的转发层使得NDN的转发策略有了更强的可适应性[4]。

1　NDN基础架构

沙漏体系结构是使最初的互联网设计美观大方并且功能强大的核心原则之一，中心是一个通用的网络层（IP），这个“瘦腰”部分是推动互联网爆炸式增长的关键。NDN保持相同的沙漏形结构，如图1所示。和今天的IP架构类似，瘦腰部分也是NDN架构的中心。NDN用数据名字来发送数据而非IP地址，这个简单的变化使得IP和NDN在数据发送的操作上有着巨大的差异。

NDN设计方案中采用了层次化的内容命名机制，类似于目前的URL命名方案。例如，一个由example.com网站发布的视频的名字为“/example. com/videos/something.mpg”，“/”表示名字组件之间的分隔。而“/example.com”及“/example.com/videos”则可作为内容前缀（prefix）用于路由查找及转发。这个层级结构用来表现不同的数据片之间的关联，也保障了路由的可扩展性。

图1　Internet和NDN的沙漏架构Fig. 1 Internet and NDN Hourglass Architectures

2　NDN的路由转发

2.1NDN的路由转发模型

NDN中有两类数据报文，分别为请求报文（Interest Packet）和数据报文（Data Packet），如图2。

图2　NDN包结构Fig. 2 Packets In NDN Architecture

NDN转发模型主要有三类数据结构，分别为 转 发 信 息 库（forwarding information base，FIB）、内容存储库（content store，CS）以及未决请求表（pending interest table，PIT），如图3

所示。FIB保存了路由结点到达内容服务器的下一跳的接口，CS保存路由结点的缓存内容，PIT记录未得到响应的Interest报文的名字及其到达接口等信息，以便Data报文沿途返回。

NDN的通信是由请求方驱动并主动取回的。内容请求方（Consumer）通过网络发送一个Interest请求，Interest中含有内容的名字。通过一组路由器传播Interest，直到找到相应的Data或Interest的生存时间结束。一个Interest数据包可取回最多一个Data数据包。Interest会在传播路径上留下状态信息，Data数据包遵循反向路径找到数据请求方。

路由转发过程总结如下：Interest进入，被cache所满足，直接匹配Content Store中的内容；Interest进入，没有被cache所满足，但已存在PIT表中，为抑制Interest在网络中的重复出现，不进行转发；Interest进入，没有被cache所满足，同时也不在PIT表中，因此在PIT表中增加一个记录，同时在FIB中进行查询，通过转发策略转发；返回Data数据包，和PIT表中内容匹配，消除表中相应行，存储在Content Store中，遵循对应Interest的反向路径转发。

图3　NDN路由节点Fig.3 NDN Node

2.2NDN的转发策略

在NDN的数据层，PIT纪录了所有未被满足的Interests和各自进入的接口，当接收到匹配的数据或者发生超时后，相应的PIT项将从表中删除。保存每一个数据报的状态这一点和IP无状态的数据层有着根本上的区别。这些状态信息使NDN的数据层在处理网络问题上有着可适应性，同时也能够更加有效的利用网络资源。

NDN和传统的IP网络不同，传统的IP网络的路由层负责各种功能，转发层只需要根据FIB进行转发。而NDN中路由层只需要建立最初的FIB表，并且负责网络和拓扑的长期变化，确保路径无环、拥塞控制等均由转发层完成[5]。

NDN的转发策略是路由器中的决策者，决定是否转发，在什么时间转发，以及向哪里转发某个Interest。目前NDN中核心的两种转发策略为洪泛转发策略（Flooding Strategy）和最优路径转发策略（Best Route Strategy），根据网络的负载和取回数据的延迟之间的权衡选择不同策略。本文的主要目的为通过两种主要策略的性能优势，找到不同策略的适用环境。

洪泛转发策略中，接收一个Interest请求报文，路由器向FIB表中对应前缀的所有接口转发该报文。FIB表中的多路径选项由相应的路由策略在网络初始建立和网络拓扑发生变化时写入[6-8]。

最优路径转发策略将Interest转发给开销最小的上游节点。之后，如果consumer重发这个Interest，或者相同的Interest从其他下游节点到达，如果在最小转发间隔的时间内，则新的Interest不会被转发，否则会被再次转发。一个再次转发的Interest被转发给除了之前使用过的接口之外的开销最小的下一跳节点。

图4　GEANT拓扑Fig.4 GEANT Topology

3　实验及分析

实验使用ndnSIM[9-10]仿真环境对不同算法进行评估，ndnSIM是基于ns-3的NDN模拟器。我们在实验中对洪泛，最优路径策略进行比较，同时分析了网络内缓存的影响。

拓扑结构采用GEANT（http://www.geant.net/）网络，如图4所示。拓扑结构有22个节点，36条链路，链路间的带宽设为1Mbps，时延为10ms。为了增加网络链路通信压力，以体现转发策略的优劣，实验设置13个消费者节点，2个生产者节点。Interest的生存时间为2s，重传时间为50ms。缓存的替换算法为LRU（Least Recently Used）。在模拟中，使用路由策略预先计算了路由路径，并将结果设置在每一个router上。

实验所评估的内容为：最优路径转发策略（Best Route），启用网络缓存的最优路径转发策略（Best Route with Caching），洪泛转发策略（Flooding），启用网络缓存的洪泛转发策略（Flooding with Caching）。

3.1理想状态下的网络

设置拓扑中每个consumer每秒发送固定的Interest数量，此时网络中无拥塞。在不造成超时的情况下，第10s增加了Interest请求。由于没有请求的超时和重发，consumer发送请求的行为在第10秒停止。

从图5中可以看出，在网络无拥塞的情况下，四种情况下的表现基本相同。缓存在此时并没有明显起到作用，因为所有的consumers都是同时对同一个数据进行请求的，所以一般情况下对应的数据都是直接从producers返回的。因此每个转发策略在网络中启用缓存和不启用缓存的性能相同。

图5　理想状态下的网络性能Fig. 5 Network under Ideal Conditions

唯一的不同在于Best Route（ Best Route with Caching）在第10s的Interest发送速率增大之后，接收数据的速率低于Flooding（ Flooding with Caching），平均时延高于Flooding（ Flooding with Caching），这说明在网络无拥塞的情况下，洪泛策略总能找到更好的路径，这也在命中距离中有体现。因为每两个邻接的routers的链路开销都一样，在不考虑链路交通状况的情况下，跳数就代表了所走路径的总开销。此时由于发送了大量数据包，跳数最短路径不再是最快的路径，此时洪泛策略能够更快地找到跳数多但时延短的路径。

3.2突发拥塞的网络

设置拓扑中每个consumer节点在理想网络状态的基础上，首先按照恒定速率发送Interest数据包，在第10s突然增大发送数量，此时网络中发生了Interest的超时。

3.2.1发送Interest报文的数量

图6　Consumers每秒发送Interests的总数量Fig. 6 Number of Transmitted Interests

由于Consumer每秒发送Interests的总数量中，包括那些因为超时而重发的Interest包，因此可以看到发送趋势整体上是在第10s突然增大并且维持到第12s之后开始下降。从发送数量可以看出，Flooding with Caching首先结束Interest的发送，接下来是Flooding，Best Route with Caching，最后是Best Route。

3.2.2接收Data报文的数量

图7　Consumers每秒接收Data packets的总数量Fig. 7 Number of Received Data Packets

从图中可以看出，完成总共1000个Interest的发送和数据的接收，Consumer接收Data packets的结束顺序与发送Interest的结束顺序相同。并且对于同一个转发策略而言，启用缓存比不启用缓存能够在每秒接收到更多的数据。

3.2.3平均时延

图8　平均时延Fig. 8 Average Time Delay

时延基本上呈线性增长趋势，从理想状态下的网络中得出，相互之间应该为差异较小的状态。

3.2.4平均命中距离

以时间为维度来比较每秒的平均命中距离的变化时，由于到后期网络中每秒发送的Interest较少，样本不足，因此平均命中距离有较大波动。因为在此例中选择了计算总的平均命中距离。

通过比较所有Interest的平均命中距离，我们可以得出，网络内缓存在此时有了很大的作用。Flooding with Caching和 Best Route with Caching都分别优于Flooding和Best Route。这说明有缓存的情况下，Interest可以在离自己更近的节点找到匹配的数据。而Best Route的平均命中距离又小于Flooding，这是因为Best Route总是优先选择线路开销最小的路径，在实验中即经过的跳数最少的路径。

3.2.5超时Interest报文的数量

图9　平均命中距离Fig. 9 Average Hit Distance

图10　每秒超时Interests的总数量Fig. 10 Timeout Interests

由于洪泛策略会在网络中创造更多的流量，因此在拥塞刚开始的时候，洪泛策略的拥塞状况更为严重，超时数量远远高于最优路径转发策略。但由于突发拥塞非常短暂，洪泛策略的超时数量也迅速下降。基本和最优路径转发策略持平。而由于洪泛策略的数据可以通过所有可用路径返回，从3.2.2可用看出，在最初的拥塞情况得到缓解后，能够到达consumer的Data packet也更多。

同时，在网络启用缓存的情况下，超时的数量也相应下降，这是因为consumer可以从相对于producer而言，离自己更近的节点处获得数据，进而降低了拥塞程度。

3.3连续拥塞的网络

从3.1和3.2节中可以看出，洪泛策略在网络负载不过重的情况下，性能都较好，为了对现实中可能发生的持续拥塞的网络中不同策略的性能进行比较，在这个实验中，设置拓扑中每个consumer在前两节的基础上，从第10s开始发送大量Interest请求并持续一段时间，结果如下。

3.3.1发送Interest报文的数量

从图11中可以看到consumers从10s开始至12s连续发送500个Interest之后，最优路径转发策略的发送数量立刻下降，而洪泛策略由于严重的拥塞和超时，接下来仍然保持着较高的发送数量。Best Route首先结束Interest的发送，接下来是Best Route with Caching，Flooding with Caching，最后是Flooding。

图11 Consumers每秒发送Interests的总数量Fig. 11 Number of Transmitted Interests

3.3.2接收Data报文的数量

在本次试验中，首先完成所有包发送和接收的是Best Route，接下来是Best Route with Caching，Flooding with Caching，最后是Flooding，与3.3.1中的结束顺序相同。从拥塞初始发生的时间点可以看出，Best Route和Best Route with Caching的成功接收数据数量最高，Flooding with Caching次之，Flooding最后。

图12　Consumers每秒接收Data Packets的总数量Fig. 12 Number of Received Data Packets

Best Route和Best Route with Caching在连续拥塞的网络中表现差异不大，一方面是由于缓存的过程造成了一定的资源消耗，再者是因为实验中所有节点对相同数据的请求都是在按同样顺序发送的（除了超时重传），在最优路径上的缓存效果并不十分明显。

3.3.3平均时延

平均时延仍然是近似线性增长，由于平均时延计算的是最终成功返回匹配数据的请求，并且是从第一次发送某Interest开始计时，最优路径策略略高于洪泛策略。

图13　平均时延Fig. 13 Average Time Delay

3.3.4平均命中距离

类似于3.2节中的结果，启用网络缓存时的平均命中距离均小于不启用缓存时的对应数据。Flooding with Caching由于使用洪泛的方式发送请求，一个返回的数据可以缓存在多个节点上，因此优于Best Route with Caching。

而关于Flooding和 Best Route，通过实验中的观测，随着实验的进行，Flooding策略的平均命中距离变化并不明显，而Best Route每秒的平均命中距离在不断上升后保持了一个较高的平均跳数，这是由于原本在FIB中优先性高的路径由于发生了超时而被标记为不可用的，而经过的跳数高因而优先级低的路径被Best Route启用并且保持使用。

图14　平均命中距离Fig. 14 Average Hit Distance

3.3.5超时Interest报文的数量

每秒的超时数量印证了通过每秒发送Interest和接收Data的数量得出的结论。在连续的拥塞网络中，洪泛策略会造成更加严重的请求超时。Flooding超时最为严重，Flooding with Caching次之，而Best Route和Best Route with Caching的请求超时数量类似。

图15　每秒超时Interests的总数量Fig. 15 Timeout Interests

4　结论

在相同的网络状况下，洪泛策略总是能找到最优的路径来取回数据，从实验一也可以看出这一点，在网络无压力的情况下，洪泛策略的时延最小。但与此同时，洪泛策略在网络中同时发出的多个Interest报文将导致网络产生大量的冗余流量，当 NDN 网络连接度较高时，这种冗余现象会更加明显。

最优路径转发策略是由路由算法预先在FIB设置了多条路径以及每条路径对应的优先级。由于网络状况的变化，在一个Interest的转发过程中，节点所选择的FIB表中的最优路径并不一定是此时网络中的最优路径，因而对于网络变化会有一定的反应延迟。但与洪泛策略相比，最优路径转发策略大大的降低了网络中的负载，对于拥塞的网络，不会造成更大的网络负担。

在普遍启用了网络内缓存的情况下，最优路径转发策略虽然在一定程度上能够减少网络的冗余流量，但未考虑周围节点可能存在的缓存内容，因此当周围节点有对应的缓存内容时，最优路径转发策略也不一定是最好的。而洪泛策略总是能匹配到离请求节点最近的数据。

实验表明一个单独的固定协议并不适用于所有的网络状况。在网络没有拥塞，并且洪泛策略也不会产生拥塞的情况下，洪泛策略是最优的，它总能找到所有可用的路径，并且从最优的路径中返回数据给请求节点。而在有突发拥塞的网络中，洪泛策略也能在拥塞程度迅速下降后，保持相对更高的收发数据速率。但在持续拥塞的网络中，由于洪泛策略使拥塞的网络更加拥塞，导致网络负载急剧增长，更加容易造成网络的瘫痪。而此时最优路径策略的性能更优，因为最优路径策略在一条路径发生问题时，会自动的使用下一条可用路径。在不造成网络负担的情况下，对网络进行了自动的适应，这种由多路带来的可适应性转发的能力在严重拥塞的网络情况下工作的更好。

实验中，网络内缓存的启用也对算法性能有一定的影响，缓存功能一方面能够提供更小的命中距离，更低的时延，另一方面也会造成资源的消耗。实验中采取LRU算法对缓存内容进行更替，这就使得网络节点需要对每一个接收到的Data packet进行保存和替换。但同时也要考虑到，网络内缓存不仅可以在网络拥塞的情况下起作用，对于其他一些应用场景也有着重要意义。根据小世界路由法则，一定范围的节点在某在一段时间内可能会请求同样的数据，而缓存能够加速这一内容分发过程。

由于并没有一个最优的转发策略，因此，router也可以在不同的场景上应用不同的策略，例如某个Interest的第一次转发只转发给最优的路径；而当发生重传时，将Interest同步转发给多个可用的接口；当接收到NACK时，将Interest转发给除了接收到NACK的上游router以外的其他router，将数据流分散到其他可用的接口；同时，也可以定期的将Interest同时转发给目前不可用的接口，对接口进行主动探测，得到接口对应的链路情况。

更进一步的想法是，NDN router可以对不同的前缀采用不同的转发策略。例如在网络负载较轻的情况下，对于一段时间内请求较多的前缀，采取洪泛策略，可以更多的在缓存中命中匹配的数据。此外，网络中不同的节点也可能采用不同的转发策略。例如根据网络中节点的不同联通度，节点周围的缓存能力状况，来制定相应的转发策略。

关于转发策略的实验研究对于未来NDN路由转发的研究方向，以及评估标准有着一定的指导意义。对于研究一个综合洪泛策略和最优路径转发策略优势的新的转发策略，提供了一定的理论支持。例如更低的网络负载，更高的缓存命中率等更加适用于NDN网络的路由转发策略。

[1] Ahlgren B，Dannewitz C，Imbrenda C，et al. A survey of information-centric networking[J]. Communications Magazine，IEEE，2012，50 （7）: 26-36.

[2] Zhang L，Afanasyev A，Burke J，et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review，2014，44（3）: 66-73.

[3] Wendlandt D，Avramopoulos I，Andersen D G，et al. Don’t secure routing protocols，secure data delivery[J]. Computer Science Department，CMU，2006，40（3）: 61-66.

[4] Yi C，Afanasyev A，Wang L，et al. Adaptive forwarding in named data networking[J]. ACM SIGCOMM computer communication review，2012，42（3）: 62-67.

[5] Yi C，Afanasyev A，Moiseenko I，et al. A case for stateful forwarding plane[J]. Computer Communications，2013，36（7）: 779-791.

[6] 屈鸿.一种基于神经网络的最短路径树生成算法[J].新型工业化，2012，2（2）：62-66.

Qu Hong.A neural network method for the computing of the shortest path tree[J].The Journal of New Industrialization，2012，2（2）：62-66.

[7] 张灿，林昭文，马严. OpenFlow网络环境中的路由技术研究[J].新型工业化，2014，4（2）：57-61，66.

ZHANG Can，LIN Zhao-wen，MA Yan. Research On Routing Technology In Openflow Environment[J].The Journal of New Industrialization，2014，4（2）：57-61，66.

[8] Hoque A K M，Amin S O，Alyyan A，et al. Nlsr: Named-data link state routing protocol[C]//Proceedings of the 3rd ACM SIGCOMM Workshop on Information-centric Networking. ACM，2013: 15-20.

[9] S. Mastorakis，A. Afanasyev，I. Moiseenko，and L. Zhang. ndnSIM 2.0: A new version of the NDN simulator for NS-3[R]. NDN，Technical Report NDN-0028，2015.

[10] A. Afanasyev，I. Moiseenko，and L. Zhang. ndnSIM: NDN simulator for NS-3[R]. NDN，Technical Report NDN-0005，2012.

Research on Forwarding Strategies in Named Data Networking

YANG Ruo-bing1, MA Yan2
(1.Beijing University of Posts and Telecommunications Institute of Network Technology, Beijing 100876, China; 2. Beijing University of Posts and Telecommunications, Beijing 100876, China)

Information centric networks(ICN) architecture is an architecture for the future use of the Internet, it provides a more secure, efficient and scalable service. Naming data network(NDN) is one of several concrete implementations of ICN. Routing and forwarding mechanism is the core of NDN. In this paper, we focus on analyzing the performance of several forwarding strategies of NDN through different indicators, such as network delay, packet hit distance, and the number of packet retransmissions. A ns-3 based NDN simulator, namely ndnSIM simulator was used to evaluate the performance of considered algorithms. Simulation results show that there is not a single best strategy, every strategy has its pros and cons, and which is severely affected by the network environment. In turn, the strategies affect the effectiveness of the distributed caching mechanisms typically used in the NDN architecture. In the end, we summarize the network situation that suitable for each forwarding strategy.

Computer network; NDN; ICN; Forwarding strategies

10.3969/j.issn.2095-6649.2015.10.009

YANG Ruo-bing, MA Yan. Research on Forwarding Strategies in Named Data Networking[J]. The Journal of New Industrialization，2015，5（10）: 59-67.

杨若冰（1991-），女，硕士研究生，计算机网络技术与应用

通信联系人：马严，教授，主要研究方向：下一代互联网技术

本文引用格式：杨若冰，马严.命名数据网络中的转发策略研究[J]. 新型工业化，2015，5（10）：59-67.