命名数据网络中基于蚁群优化的视频业务路径优化

侯睿，郑勇*，周烁，张成俊

(1 中南民族大学 计算机科学学院，武汉 430074；2 武汉纺织大学 机械工程与自动化学院，武汉 430073)

目前的TCP/IP网络体系存在地址数量有限、移动性、安全性等局限而发展受限.作为下一代互联网体系的典型解决方案之一,命名数据网络[1](NDN，Named Data Networking)允许用户根据所需数据信息对象的名称而非位置来请求和获取数据，通过分层结构化命名方式分离位置和标识，使目前主机-主机通信方式转变为请求内容-获取内容的通信方式，因此较TCP/IP体系在安全性、移动性、数据重用性等方面具有更明显的优势.

同时，随着多媒体业务的快速发展，视频业务流量在因特网中的比重越来越大，据思科可视化网络指数(VNI)报告预测，全球各业务总量逐年攀升，其中视频业务流量占比最高，而视频业务因其数据量较大、带宽占用较高的特点，对网络资源有较高的要求，如何保证视频业务在NDN中的可靠传输就成为信息中心网络(ICN，Information Centric Networking)研究领域的重要课题.

为了提升视频业务在NDN中的传输可靠性并保证服务质量QoS，文献[2]提出一种QoE驱动的动态视频流算法(fair-DAS，fair Dynamic Adaptive video Streaming)，该算法能对多客户端的视频流进行动态自适应带宽优化分配，但在客户端增多时仍可能出现因总带宽不足产生的客户端视频体验不佳等问题；文献[3]提出一种基于网络编码的自适应视频流架构，在一定程度上能提高视频质量，但是网络编码过程可能会导致编码时间开销增大而影响路由；文献[4]提出一种基于视频请求比例不同来划分视频热度的缓存替换算法(PCSD)，PCSD根据请求比例将视频热度高的视频块放到靠近视频接收端的边缘路由器中来减少路由跳数，增加视频传输性能，但对于热度较低的视频数据不能达到相同效果；文献[5]提出一种基于视频分发的网络编码和速率分配算法，该算法测算出客户端和中间节点发送数据包(Data Packet)的最优速率，根据各data包流的速率分配提高各客户端视频平均质量，但并不能根据各客户端视频业务的不同针对性地保证视频质量.文献[6]提出基于路径上缓存的多径路由MRBRC，通过发送探路兴趣包，根据缓存内容的流行度与转发端口的历史信息来收集热度信息，并通过周期性统计缓存流行内容来更新路由表实现内容与转发接口的对应，其路由表维护成本及内容统计成本会随着缓存信息的增大而急剧增大，极大降低了传输性能.

有别于以上仅以带宽、缓存、热度作为优化对象的视频业务优化方法，本文从视频业务数据量大、适宜多路径传输的特点进行考虑，提出了一种适用于NDN网络中，基于改进的蚁群优化算法的视频业务路径优化方法 (ACO-MpR，Ant Colony Optimization-based Multipath Routing).该方法通过NDN中信息转发表 (FIB，Forwarding Information Base)能转发兴趣包(Interest Packet)到多个接口的特性，使用多条路径[7]并行传输，并通过最优化模型计算和分析得到针对不同视频业务传输的多条路径,以达到增加网络聚合带宽、减少时延、增加吞吐量的目的.

1 ACO-MpR算法及多路径模型

1.1 视频业务分类

NDN中订阅者(Subscriber)发送带有请求信息的interest包来获取数据，返回的data包包含相应的内容，data包的传输方式会因视频业务特性的不同而不同，从而给出相应的传输方案.

视频业务因具体路由要求不同，其QoS服务要求也不同，QoS要求分为：尽力而为型(BE，Best-effort)，快速转发型(EF，Expedited Forwarding)及保证转发型(AF，Assured Forwarding).视频业务在业务需求上具有数据传输量较大、实时性要求高及所需带宽较大等特点，本文针对视频业务的特点从拥塞、带宽及时延等方面进行视频业务分类，根据不同视频业务对应的拥塞、带宽及时延要求组成约束三元组进行路由限制，通过约束三元组中约束条件重要性的不同进行加权，以找到最能满足其服务要求的路由.

本文将视频业务通信类型分为视频传输及下载、视频通话、视频分发及群会议等几个具有代表性的业务类型，不同通信类型根据其具体服务要求进行细化，提供针对不同视频业务的优化传输方案，如表1所示，表1中视频传输及下载业务对带宽要求较高，对时延要求一般，属于尽力传输型业务，因此带宽要求占有更大的权重.

表1 视频业务分类

数据对象是根据Subscriber在网络拓扑中与之通信的数据发布者(Publisher)的数量进行划分的，一般情况下，Subscriber只能与一个或多个Publisher进行数据通信.图1 是一个一对一双向数据传输过程，为简化模型可看成两个独立的单向数据传输过程，同样，一对多的通信过程也可以简化为多个一对一的多路径通信过程.

图1 数据生产消费关系

1.2 多路径设计原理

根据业务类型来初始化包括满足其相应 QoS的时延、带宽及拥塞值在内的所有参数，并在找到一条路径后更新NHN (Next Hop Node)表，重复该过程直到找到满足其约束条件的多条路径，最后将得到的多条路径通过最优化模型筛选出最满足 QoS 要求的多条路径.

在ACO-MpR算法中加入NHN表记录网络拓扑中每个节点的相邻节点.对于一个通信过程，对同一业务数据而言，设置TSR(Travel Second Route)值用于记录下一跳接口的转发状态，通过改变信息转发表FIB中TSR值来避免链路段相交，从而达到同一业务的不同数据块能在没有重复链路段的路径上传输的目的.

算法1：

while(not satisfy the feasibility test of route)

initialize all parameters and NHN table

while (not satisfy the end condition)

fori=1 to num_ant do

randomly choose an initial node

forj=1 to nodes do

choose next node

add path[i,j] into taboo table

end for

end for

for link inGdo

update the pheromone concentration

end for

print route

end while

update the NHN by the output route

end while

for route in routes do

filter routes by the optimization model

end for

算法1中，ACO-MpR设立路由可行性条件，并结合最优化模型，引入NHN表以得出最满足相应视频业务类型QoS要求且链路不相交的多路径.

几条不同路径存在重复链路段时会导致拥塞，而路由节点重复则不会，因此对于不同路径中某个相交路由节点，通过判断其下一跳节点是否重复即可避免重复链路段的出现，因此避免路径重复机制也是能顺利得出多条无重复链路段路径的必要条件，对于数据量较大的视频业务而言，视频业务的不同数据块在不同路径的相同链路段传输可能导致拥塞，因此在ACO-MpR中根据链路不相交原则，通过在蚁群优化算法中加入NHN表来解决这种拥塞问题.

1.3 包格式设计

NDN中把data包粒度较高且数据量较大的数据对象以一定的比例分配在多条路径中传输.如图2所示，在包格式[8]的设计中加入separator，if_separate用于区分是否按照多路径方式传输；separate section用以区分数据块中的不同data包在哪条路径上传输.

图2 包格式设计

1.4 避免路径重复机制

图3表示interest包转发到下一接口的避免路径重复过程.

图3 避免路径重复流程

通过在ACO-MpR中加入NHN表，对输出的路由节点进行判断使TSR状态发生变化，由此确保多条路径没有相同路由链路[9].ACO-MpR算法中NHN表用于记录网络拓扑中每个路由节点的相邻节点，通过区分同一业务的不同数据块决定不同传输路径中该节点通往相邻节点的接口的状态，产生TSR状态转换，使得信息转发表FIB禁止同一个视频业务的不同数据块在相交节点的同一个接口转发，对于一个通信过程，设置TSR值用于记录下一跳接口的转发状态，通过改变信息转发表FIB中TSR值来避免链路相交.

路由转发机制如图4所示，TSR值为1表示对该interest包而言该接口为可转发状态，为0则表示不可转发状态.若interest包block1从接口A转发到路由节点A，则TSR值变为0，对于同一视频业务的block2则只能从TSR值为1的接口转发.这种机制能有效避免路径重复，且能解决返回的data包在相同链路中传输带来的拥塞问题.

图4 路由转发机制

1.5 最优化模型

ACO-MpR算法将链路上三元组数据(Congestion,Delay,Bandwidth)作为约束条件，通过有约束非线性最优化模型[10]进行路径筛选以满足相应视频业务的QoS，将n条路径筛选为m(n≥m≥1)条满足相应业务QoS的路径进行数据传输.

本文对三元组数据进行无量纲化处理得到预处理数据(Conge,Delay,Band)，并做约束处理[11]，每段链路需满足相应视频业务的QoS要求的带宽、时延及拥塞值，如下式(1)、(2)、(3)分别表示第N条路径满足相应视频业务的尽力而为型、快速转发型及保证转发型的QoS要求,其中最优化模型可行域中必须以式(1)、(2)、(3)这3个值与被筛选路径相应数据的比较关系来确定筛选条件.

(1)

(2)

(3)

最优化模型通过对带宽与时延拥塞积的商做平均化处理，表示当Band,Delay，Conge满足视频业务相应QoS要求时m条路径的带宽与时延拥塞积的商的平均数最大，当再增加或者减少一条路径时使得该商的平均数变小都不可取，以其最大值确定、筛选出m条路径，将其作为最优化模型中的目标函数，如下：

(4)

如表2所示，基于IETF提出的区分服务模型[12]DiffServ(Differentiated Services)，对于不同业务类型的QoS要求都有对应于带宽、时延以及拥塞值的系数α,β,λ,且α+β+λ=1.

设置Datam为最优化模型的决策变量，它表示数据源节点到数据请求节点第m条路径传输总量，再设置最优化模型相应的可行域.然后根据式(1)、(2)、(3)的筛选条件建立最优化模型可行域约束条件[13]为：

(5)

2 仿真结果与分析

针对视频业务数据量大、QoS要求较高的特点，当前关于命名数据网络中视频业务优化的研究多以带宽、缓存及内容热度为研究方向，本文选取命名数据网络中经典的路由方式蚁群优化算法ACOIR(ACO-inspired ICN Routing)[14]和多路径路由方法MRBRC为对比对象.本文以蚁群优化算法对路由选择具有收敛快及鲁棒性强的特点，结合命名数据网络支持多网址的特征，做出针对视频业务区分及多路径传输的改进，在以蚁群优化算法为主的传统路由方法基础上，针对不同视频业务提出基于改进蚁群优化算法的多路径传输方案.在实验阶段，设置ACO-MpR及ACOIR的实验参数见表3.

表3 参数表

如图5所示，本文基于改进萨拉玛算法[15]来随机生成一个包含30个结点的网络拓扑图.在多路径视频数据传输过程中，路径条数越多，算法时间复杂度越高，划分以及组合数据块的时间开销越大，当路径条数达到一定值时，ACO-MpR算法优越性会达到最高，故本实验中路径条数设为两条来代表多路径中的一种情况，进行实验对比.

图5 拓扑图

ACO-MpR算法在找到多条路径后，将视频对象分配到各路径传输，分配原则是使最终到达数据请求端的时间开销差最小.如图6所示，实验表明：在包含30个结点的拓扑图中约有54.7%的数据报文由第一条路径传输，第二条路径则传输了45.3%，这样分配使得时间开销一致，即达到数据同时接收完毕的平衡状态，使得数据的总传输时间降到最低.

图6 多路径数据分配图

如图7所示，ACO-MpR中聚合带宽的优势使得数据对象并行发送，降低了传输时间，且对数据量较大的数据给出相应约束条件，使得路由更能满足其QoS，有效满足EF及AF可靠性的视频业务需求.而MRBRC由于需查询数据包与端口的关系，导致传输时间受查询结果影响.ACO-MpR和MRBRC由于节点缓存在每次路由后会趋向请求节点，因此平均传输时间都有一定程度的降低.

图7 传输时间

如图8所示，ACOIR与ACO-MpR的时延几乎一致，而MRBRC中时延较高且时延抖动较大，这是由于MRBRC中匹配数据包与端口存在不稳定性以及周期性更新缓存内容使得开销增大导致的，且拓扑图中节点数量有限使得ACO-MpR算法产生后续的路径时会增大时延，在实际路由中，时延会随着拓扑节点总数量的增多而降低.

图8 各路径总时延

图9给出了网络吞吐量情况，由于多路径聚合并行带宽更大，因此ACO-MpR算法能得到更大的数据吞吐量，有效保证数据的可靠性，使BE类型业务传输时间降低，而MRBRC未考虑多路径数据传输中的拥塞，使得路由受拥塞的影响比ACO-MpR大.

图9 吞吐量

3 结论

本文针对视频业务服务质量优化问题提出了视频数据的多路径传输方案，针对其不同的传输需求给出相应的满足其QoS的传输方式，仿真实验结果表明基于蚁群优化的视频业务路径优化方法能为视频业务提供更好的服务质量保障.该方法能通过更大的聚合带宽，在不同数据传输场景中根据不同视频业务类型的特点对数据传输方式进行优化，尤其对于传输带宽资源占用较大的视频业务以及数据量较大的数据对象，ACO-MpR算法在网络聚合带宽、路由时间及数据吞吐量等方面有更好的表现.