内容中心网络中基于可用带宽的多接口路由策略

黄 胜，张宏宇，吴 震，滕明埝，郑丹玲

（重庆邮电大学 光纤通信技术重点实验室，重庆400065）

0 引 言

CCN［1］中基本的路由机制是洪泛路由［2］（flooding routing，FR）和最优路由［3］（best routing，BR）。基于蚁群优化［4］（ant colony optimization，ACO）的分布式路由策略和贪婪路由算法［5］是基于BR 提出的，容易导致网络中链路带宽资源的浪费并加重最优路径和相应服务器的负载。CCN本身具有多路径路由的特点，文献［6］提出实现CCN多路径传输的拥塞控制机制，基于窗口的兴趣包控制机制［7，8］来调控接收端请求包的速率，减少链路中的拥塞的发生。为了减少数据冗余［9］，根据不同参数提出基于层次分析法［10］的CCN 多路径兴趣包路由机制。基于兴趣包窗口的拥塞控制机制仅通过反馈的拥塞信息调节请求速率，不能及时减缓拥塞的发生，因此，本文提出一种MRSAB 算法。该算法依据链路带宽占用情况及时选择链路转发兴趣包，减少网络中链路拥塞的发生。

1 CCN 的基本描述

1.1 CCN 的基本模型

CCN 采用七层结构，保持了TCP／IP 体系结构的沙漏模型［2］，在中间层采用命名数据取代IP。CCN 是一个由接收者驱动的通信模型，在CCN 的通信过程中存在两种类型的包：兴趣包和数据包，请求者发送的兴趣包由名字唯一的标识，兴趣包通过CCN 的节点转发给能够提供请求内容的邻近节点，与之相匹配的数据包沿着兴趣包的反向路径传送给请求者，完成信息的传输过程。CCN 节点主要包括3部分：内容存储库 （content store，CS），未决请求表（pending interest table，PIT）和 转 发 信 息 库 （forwarding information base，FIB）。CS通常采用LRU 或LFU 替换策略存储数据包，PIT 被用来记录未被满足兴趣包的进入接口，以便请求的内容顺利地传回请求节点，FIB 的处理机制类似于TCP／IP结构中的路由转发表，但FIB 支持向多个接口转发请求。

在CCN 转发模型中，请求者发出兴趣包请求相匹配的数据，包的转发过程如图1 所示。当兴趣包到达节点时，节点根据该兴趣包中包含的内容名依次在CS，PIT，FIB中利用最长前缀匹配进行查找。首先查找CS，如果CS中包含该兴趣包匹配的数据包，节点将数据包按照请求接口发送到请求者；如果CS中未存储匹配的数据，则在PIT 中继续查找，如果PIT 中包含该兴趣包的内容条目，则将请求接口添加到PIT 的请求接口列表中，否则将在FIB 中继续查找；如果FIB 中包含与该兴趣包内容名相关的条目，则按照FIB中记录的信息将兴趣包转发到下一跳节点，同时将请求信息添加到PIT 条目中。如果以上3种情况都不符合，说明不存在相关的匹配路由，则丢弃该兴趣包。

图1 CCN 中包的转发过程

当节点收到返回的数据包时，节点根据数据包中包含的内容名查找PIT 条目，将该数据通过与内容名相匹配的接口转发，CCN 节点采用缓存策略将数据包存储到CS中，同时删除相应的PIT 条目。如果查找不到相应的PIT 条目则丢弃该数据。

1.2 两种对比路由算法介绍

本文的对比算法采用CCN 中常用的两种路由机制，FR 将兴趣包转发到节点的各个接口请求相应数据，即将节点上兴趣包的副本以广播的形式转发到下一跳节点，兴趣包通过洪泛方式请求数据会提高缓存命中率，但是每个兴趣包仅返回一个数据包，这样将造成网络资源浪费，增加路由开销。BR 从FIB的多个接口中选择一个能获得相匹配数据的最优接口，使得该接口到服务器的性能最好 （如跳数最少或整体负载最低等），然后将节点上到达的兴趣包通过该条最优路径进行转发。由于BR 将大部分兴趣包通过一条路径转发，过多的兴趣包请求将造成该链路拥塞的发生，而且会造成链路负载不均衡问题。

FR 和BR 的路由转发过程如图2所示。图中虚线表示兴趣包请求的最优路径，最优路径根据该路由算法中选取的参数确定。洪泛将请求者发出的兴趣包按照图中黑色箭头向下游节点进行转发。由于CCN 网络中过多的兴趣包请求会导致网络中链路拥塞的发生，FR 和BR 路由算法不能有效地减少链路拥塞的发生，从而增加请求数据的时延，BR 路由算法也造成网络中链路负载不均衡问题。为了将兴趣包通过合理的接口转发，本文在BR 算法的基础上提出了MRSAB算法。

图2 FR 和BR 转发过程

2 MRSAB算法

目前大部分的设备都具有多路径传输的能力，研究结果表明TCP／IP网络中多路径路由可以获得负载均衡，减少拥塞，低功率消耗和较高吞吐量等好的性能。CCN 本身具有支持多路径传输的能力，因此，CCN 的多路径路由采取一定的路由机制合理地分配兴趣包到多条路径上请求数据，可以充分利用网络带宽资源，并且使CCN 网络获得较好的性能。

2.1 三颜色标识机制

CCN 中的FIB不同于IP中的FIB，IP的FIB中通常仅记录最优下一跳信息，NDN 的FIB 中包含排列的多个接口，用来记录路由过程的信息并且提供一定的路由转发策略，CCN 中FIB包含的信息如图3所示。CCN 中的FIB条目为每个接口记录一个检索数据的状态，本文使用三颜色机制［11］来标识各个接口的状态：绿色表示接口处于可用状态；黄色表示接口处于可用或不可用状态；红色表示接口处于不可用状态。当节点创建一个新的FIB 条目时，该条目对应接口的状态被标记为黄色，当有相应的数据包从该接口返回时则标记该接口状态为绿色，当该接口的待发兴趣包超时或者一段时间后未被使用，其状态被标记成黄色，如果一个接口失效或从上游接收到NACK 则该接口状态被标记为红色。

图3 CCN 中的FIB信息

2.2 数学模型描述

在CCN 网络链路上，数据包占用大部分的链路带宽，兴趣包占用的带宽可以忽略不计，因此本文利用数据包个数反映链路带宽占用情况，节点上到达的兴趣包根据预测的链路带宽占用情况选择接口进行转发。

在一个短时间段Δt内链路上转发的数据包个数变化很小，因此可以利用时间t前面时间段内数据包个数的测量值来预t～t＋Δt内数据包个数的估计值，根据该估计值评估t～t＋Δt内每条可用接口链路带宽占用情况。EWMA［12］数学模型根据实际的测量值cij（t）预测下一个时刻的估计值EWMA（t＋Δt），λ表示对测量值的权重系数，其公式如式 （1）所示

由于EWMA 模型对估计值进行预测的精确度不高，为了提高预测精确度将其变形为WMA 数学模型来预测t～t＋Δt内数据包的个数，WMA 模型根据不同时间段内测量值对估计值的影响程度给予不同的权值。由于每个匹配兴趣包的数据包大小相同，且占用带宽相同，因此一个时间段内数据包的个数可以反映链路带宽占用情况。利用WMA 模型预测t～t＋Δt时间段内数据包个数的估计值，需要利用t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt这3个时间段内数据包个数的测量值对其进行预测。例如预测t～t＋Δt内数据包个数Bt＋1，则需要记录之前3个时间段内对应数据包个数的测量值Bt、Bt－1、Bt－2，每个时间段之间的间隔为Δt＜＜T（T 表示仿真时间）。WMA 模型预测Bt＋1的公式如式 （2）所示

其中，参数α、β、γ 分别对应t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt这3个时间段内数据包个数测量值的权值，α＋β＋γ＝1。在该模型中，越是接近需要预测的时间段，测量值对估计值的影响越大，即Bt对Bt＋1的预测影响最大，因此α的设置应该明显大于其它两个参数 （本文α取0.7，β取0.2，γ取0.1）。

2.3 MRSAB具体描述

MRSAB首先通过三颜色路由机制为节点判断可用接口，然后为可用接口对应链路预测t～t＋Δt内的估计值Bt＋1，从而判断每个接口对应链路的带宽占用情况，最后对可用接口对应链路的可用带宽进行比较排序，选取可用带宽大的接口进行兴趣包的转发。文中MRSAB 算法具体步骤如下：

步骤1 设网络拓扑中每条链路的负载容量为Rij，Bij表示一条链路上当前时刻带宽占用情况。

步骤2 节点收到兴趣包后按照CCN 的基本转发过程查找，需要在FIB中查找下一跳节点时根据该兴趣包名进行最长前缀匹配查找，找出节点上标记为绿色的可用状态接口。

步骤3 判断可用状态接口对应链路上占用带宽是否超过该链路的负载容量Rij，如果所有可用链路上带宽占用都超过总的负载容量，即都处于链路拥塞状态则执行步骤4，否则执行步骤5。

步骤4 丢弃该兴趣包，在一定程度上减少网络拓扑中兴趣包的数量，并标记该接口为黄色。

步骤5 利用WMA 模型预测可用链路上数据包的估计值，从而计算链路上带宽占用情况。

步骤6 比较可用链路中数据包的估计值，选择两条可用带宽较大的链路，使用可用带宽最大的链路转发兴趣包，另一条作为备选链路从而保证数据请求的可靠性。

本文提出的MRSAB 算法根据链路带宽占用情况选择转发接口，这样可以充分利用网络中带宽资源，通过一定的链路限制减少该机制中链路拥塞的发生，减少请求数据的时延。三颜色机制标识可用接口使兴趣包向具有匹配数据的链路转发，增加缓存的命中率，减少服务器的负载，该机制最大的优点是多接口路由的引入使CCN 网络中链路到达更好的负载均衡。

3 仿真分析

本文在Linux环境下采用基于NS3 的ndnSim 仿真平台。本文的数据请求服从Zipf分布，仿真结果与CCN 中常用的FR 和BR 进行比较。本实验采用LCE 缓存策略和LRU 替换策略，仿真时间200s。

3.1 缓存命中率

MRSAB与FR 和BR 在缓存命中率的比较如图4所示。由图可知随着参数α的增加，缓存命中率逐渐增加，因为α越大缓存中存储的内容越集中，缓存命中的概率越大。相对于FR 和BR，MRSAB 在α＞0.6 时缓存命中率相对较高，FR 的缓存命中率越来越低是因为缓存中存储的内容越来越集中，通过广播兴趣包副本请求数据使网络中兴趣包增多，而每个兴趣包仅返回一个数据包。MRSAB 在α＜0.6时缓存命中率低于FR 是因为缓存中存储的内容不太集中，FR 通过多条路径请求数据能够提高命中数据的可能性。

图4 缓存命率的比较

3.2 平均时延

MRSAB与FR 和BR 在平均时延上的比较如图5所示。由图可知MRSAB的平均时延相对较低，随着参数α的增加平均时延越来越低，因为α越大，对存储比较集中的内容请求所需要的时延较小。

图5 平均时延的比较

3.3 负载均衡

本文选取一个度数最大且具有3个输入数据接口和一个输出数据接口的节点进行负载均衡的测量，MRSAB 与FR 和BR 负载均衡的比较如图6所示。由图可知MRSAB的负载均衡明显优于FR 和BR。图中BR 的负载均衡最差是因为该机制仅选取一个最优路径进行兴趣包的转发，这样容易造成该链路负载过大，从而使网络中整体的负载均衡较差。FR的负载均衡不稳定是因为向一个节点的所有接口转发兴趣包的副本，而并非所有接口都是可用状态，所以其负载均衡随着路径上兴趣包请求速率的增加有较大的波动。度数为n的节点负载均衡度Ln的计算公式如式（3）所示

式中：L——一个节点上返回数据包接口的个数，αk——L个接口对应每条链路上带宽占用情况。

图6 负载均衡的比较

3.4 服务器负载

3种路由机制服务器负载 （服务器中数据包请求次数）的比较如图7所示。由图可知MRSAB的服务器负载低于其它两种路由机制，FR 向节点的各个接口转发兴趣包，当相应链路的中间节点没有相匹配的数据时，兴趣包被转发到服务器进行数据包的请求，因此使服务器的负载明显增加。

图7 服务器负载的比较

4 结束语

针对CCN路由过程中链路拥塞和负载不均衡等问题，本文提出了一种MRSAB算法，该算法在WMA数学模型下利用t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt内数据包个数的测量值预测t～t＋Δt内数据包个数的估计值，从而评估链路带宽的占用情况，通过比较节点可用链路带宽占用情况选择t～t＋Δt内兴趣包的转发接口。仿真结果表明，本文提出算法充分利用网络中的带宽资源，在α＞0.6的条件下提高缓存命中率，在整个α的变化范围内减少平均请求时延，该算法最明显的优点是提高链路的负载均衡，减少服务器的负载。

［1］Jacobson V，Smetters DK，Thornton JD，et al.Networking named content［C］／／Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.ACM，2009：1－12.

［2］Zhang L，Estrin D，Burke J，et al.Named data networking（ndn）project［R］.Relatório Técnico NDN－0001，Xerox Palo Alto Research Center－PARC，2010：1－24.

［3］Detti A，Blefari－Melazzi N.Network layer solutions for a content－centric internet ［M］／／Trustworthy Internet.Springer Milan，2011：359－369.

［4］Shanbhag S，Schwan N，Rimac I，et al.SoCCeR：Services over content－centric routing ［C］／／Proceedings of the ACM SIGCOMM Workshop on Information－Centric Networking.ACM，2011：62－67.

［5］Wang L，Waltari O，Kangasharju J.MobiCCN Mobility support with greedy routing in content－centric networks ［C］／／GLOBECOM IEEE Global Communications Conference：NGNNext Generation Network，2013.

［6］Carofiglio G，Gallo M，Muscariello L，et al.Multipath congestion control in content－centric networks ［J］.IEEE NOMEN，2013，13：1－6.

［7］Carofiglio G，Gallo M， Muscariello L.ICP：Design and evaluation of an interest control protocol for content－centric networking ［C］／／IEEE Conference on Computer Communications Workshops.IEEE，2012：304－309.

［8］Fu T，Li Y，Lin T，et al.An effective congestion control scheme in content－centric networking ［C］／／13th International Conference on Parallel and Distributed Computing，Applications and Technologies.IEEE，2012：245－248.

［9］Rossini G，Rossi D.Evaluating CCN multi－path interest forwarding strategies［J］.Computer Communications，2013，36（7）：771－778.

［10］Zhang Y，Liu J，Huang T，et al.Multi－path interests routing scheme for multi－path data transfer in content centric networking ［C］／／National Doctoral Academic Forum on Information and Communications Technology，2013：1－6.

［11］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.

［12］Qian H，Ravindran R，Wang GQ，et al.Probability－based adaptive forwarding strategy in named data networking ［C］／／IFIP／IEEE International Symposium on Integrated Network Management.IEEE，2013：1094－1101.