基于SDN的空间信息网络自适应QoS路由算法

杨 力,李涵睿,潘成胜,戚耀文

1(大连大学 通信与网络重点实验室,辽宁 大连 116622)

2(南京理工大学 自动化学院,南京 210094)

3(大连大学 信息工程学院,辽宁 大连 116622)

4(南京信息工程大学 电子与信息工程学院,南京 210044)

1 引 言

空间信息网络将卫星与地面网络融合,有覆盖面广,按需接入,通信不受地理条件制约等特点,能够支撑多样化的通信需求,是未来网络发展的新趋势[1].但其也存在链路特性、利用率差异大,节点资源受限的问题.同时,由于空间信息网络承载业务的多样性,使得网络中服务质量的保障越发重要.为对空间信息网络业务传输进行合理规划,满足业务质量保障需求,根据数控分离思想,研究者将软件定义网络[2]引入空间信息网络.其集中管理和可编程的特点,实现了在逻辑上集中的松耦合控制平面和物理上分布的数据平面,并为实现考虑多种链路状态的路由算法提供了可能.这使得基于SDN的服务质量保障成为国内外学者们的重点研究方向[3,4],提高路由选择的质量则能够在有效的提升网络性能的同时,实现对用户服务质量的保障.

为实现SDN架构下服务质量保障的路由技术,学者们进行了大量考虑链路状态特征的路由策略研究,文献[5]提出了一种可以在SDN方案下满足QoS需求的传输方案OpenQoS,设计了SDN的多个功能模块,将丢包率和时延为权值,计算最短路径.文献[6]在SDN架构中实现了基于Openflow协议优化的ECMP(Equal Cost Multipath)[7]路由算法,通过控制器获取链路带宽,并根据链路剩余带宽确定最优路径.文献[8]提出了一种基于SDN的多路径服务质量解决方案,根据链路的时延和距离计算代价,在源和目的节点之间通过多条链路以及排队机制来保障不同类型业务的服务质量.文献[9]提出了一种基于多媒体流的分布式QoS体系结构,通过支持服务质量的控制器,根据时延、带宽、丢包率实现不同等级的服务质量,从而保证了视频流的传输质量.以上方案均在某些方面考虑了通信的服务质量要求,但未能适应于空间信息网络环境,保证其网络的整体利用率.

为了实现空间信息网络环境下的服务质量保障,文献[10]根据卫星网络大规模时延的特点,设计了一种基于存储时间聚合图的多流最大化路由方案,匹配稀有网络资源,实现QoS支持.为计算满足不同QoS需求的动态优化路径,文献[11]对数据流进行分类,提出了一种多目标决策的LEO卫星网络路由算法.文献[12]根据软件定义卫星网络可动态管理卫星网络的特性,提出了一种智能服务质量的路由方案,根据卫星的不同能级进行路由,实现了负载均衡.文献[13]提出了一种QoS单播路由机制,综合考虑QoS满意度,使用改进的Dijkstra算法找出满足多约束条件的最优路径.文献[14]在基于SDN的卫星网络架构下设计了一种采用拉格朗日松弛法的多约束QoS路由算法,近似算法能够得到相对精确的计算结果.上述算法实现了多约束QoS问题,并通过基于SDN的集中控制,从全局角度对资源统一划分.但同时,对资源进行合理的分配是一个NP难题,处理不当则会导致控制器计算复杂度过高.不适用于高速动态的空间信息网络环境,且都没有对约束条件的阈值给出计算.

为了优化多约束QoS求解的计算速度,适用于节点资源有限的空间信息网络.可以将启发式算法应用于路由协议中,让路由协议参考网络中的多种结果,以提高计算速度.文献[15]将蚁群算法应用于路由求解,提出了一种考虑卫星网络状态和信誉度的服务质量路由算法,利用蚁群算法进行路由的发现和维护,实现服务质量自适应变化.文献[16]和文献[17]结合QoS信息对蚁群算法进行了优化,实现了满足多QoS约束的路由算法.但如何针对空间信息网络特点,构建智能算法中的目标函数,以提高算法收敛速度,仍是需要重点关注的问题.

综上所述,现有的基于SDN的路径优化模型中,都没能充分利用SDN优势,适应空间信息网络环境,考虑综合网络代价,保障QoS需求.

因此,本文设计了路由算法SDN-AQoS(SDN based Adaptive QoS Routing Algorithm).在基于SDN架构的空间信息网络中,定义了以最小传输代价为目标的多QoS约束问题,并基于优化蚁群算法求解.能够对空间信息网络资源进行合理分配、自适应保障多种优先级数据流不同服务需求.提升了网络服务质量和算法收敛速度.

主要工作包括以下几个方面:

1)基于SDN架构和星地链路的多元多维因素,设计了考虑链路质量、剩余带宽和节点负载的传输代价模型.定义了以最小传输代价为目标的多QoS约束问题.

2)为不同优先级的数据流,通过Adam随机梯度下降算法自适应配置不同的阈值,实现了自适应QoS约束.

3)通过优化的蚁群算法求解多约束优化问题.根据约束条件使用双禁忌表优化节点候选集.考虑带宽、丢包率改进了信息素挥发系数公式,并利用SDN可编程的特性,根据数据流的不同优先级进行取值设计.从而优化了迭代过程,加快了收敛速度.最终找到满足约束条件且具有最小传输代价的路径.实现了自适应QoS路由算法SDN-AQoS.

2 系统模型

2.1 基于SDN的网络模型

本模型由LEO(Low Earth Orbit)/GEO(Geostationary Earth Orbit)两层卫星网络和地面节点组成.为了使GEO层卫星覆盖全球区域,设置3颗GEO卫星.LEO层卫星总数为ML×NL,ML表示平面数,NL表示平面中卫星的数量.本文采用虚拟拓扑的思想解决卫星网络动态变化的特性对拓扑的影响.将卫星运行周期T划分为N={N1,N2,N3,…,Nn}个时间片,当时间片足够小时,可以假设每个时间片内的拓扑结构不变.

本文将SDN控制器部署在3颗GEO卫星和地面站.为实现服务质量支持的控制器,GEO卫星控制器通过拓扑管理功能获取每个时间片覆盖区域内的拓扑信息并存储.3个GEO控制器根据共享拓扑信息及资源管理功能接收的链路状态信息LSI(Link State Information)反馈,形成全局拓扑图.地面站控制器共享全局拓扑信息并通过路由计算功能计算每个时间片的路由表,下发流表给其他转发器.转发层的LEO节点仅负责根据流表进行转发功能.

为了在SDN控制器上提供服务质量支持,本文所提出的控制器接口、模块设计如图1所示.

图1 SDN控制器及接口模型Fig.1 SDN controller and interface model

控制器-转发器接口:该接口由Openflow[18]标准定义,并由典型的Openflow控制器实现.

控制器-控制器接口:通过该接口使多个控制器共享信息,合作管理整个网络.

拓扑管理:负责通过链路发现协议(LLDP)发现网络连接,生成聚合的网络拓扑信息,维护拓扑可视化.

资源管理:负责通过控制器-转发器接口从转发器收集最新的链路状态信息,确定其可用性和转发性能.

路由计算:与拓扑管理和资源管理功能相结合,获取最新的网络拓扑和链路状态信息,进行路由计算.

通过上述控制器设计可以为实现服务质量保证的路由提供实时的服务质量信息.同时根据SDN的可编程特性将网络协议拆包,识别数据流的不同的优先级,根据数据流对QoS的不同需求,赋予以下不同的优先级:

优先级1:实时性、抖动敏感、高交互性的数据流.

优先级2:事务办理、交互性数据流.

优先级3:仅要求低丢包率的数据流、视频流.

本文模型为确定可用链路的服务质量,计算不同优先级数据流的路由提供了保证.

基于SDN的空间信息网络拓扑可以表示为一个无向加权拓扑图GN=(VN,EN).其中,VN={vG,vL,vT},代表每个时间片中网络所有节点的有限集合,vG,vL,vT分别表示GEO卫星、LEO卫星和地面的节点集.EN={IOL∪ISL∪UDL}代表每个时间片中网络所有链路的有限集合,由于空间信息网络的链路具有多种性质,IOL表示星际链路,ISL表示星间链路,UDL表示星地链路.不同性质的链路具有不同的传输特性.

用5个节点模拟表示SDN控制器中存储的 第N个时间片的拓扑信息,如图2所示.链路属性参数可由SDN控制器实时更新.

图2 网络拓扑模型FiG.2 Topology of network

v={v1,v2,…vn}∈VN,本文定义Elvmvn,N=(dlvmvn,blvmvn,pllvmvn)为边权值,每条边的权值都有平均时延、剩余带宽、丢包率3个属性.定义Wvn(t)来代表节点v的负载情况.xi表示在第N个时间片内节点vm和vn节点之间的连接情况.

2.2 QoS参数

空间信息网络的传输能力主要取决于链路服务质量,而QoS又受许多因素的影响.本文结合空间信息网络通信范围广但不同性质链路的传输特性差异大的特点.根据2.1节所述网络模型,利用SDN资源管理功能,实时获取链路的延迟、剩余带宽、丢包率作为QoS度量参数,用于实现QoS路由算法.

1)端到端延迟:指数据流fi从节点vm到节点vn所需要的时间,是衡量QoS的主要性能指标之一.如公式(1)所示,将传输时延和传播时延之和作为链路延迟:

(1)

2)剩余带宽:剩余带宽指链路通信中未被占用的数据传输量.在传输数据流时,链路两端的两个节点通过两个端口相连,一个端口的字节发送率等于另一个端口的字节接收率.如公式(2)所示,用节点vm的端口数据表示链路lvmvn的剩余带宽:

(2)

3)丢包率:丢包率指通信中未接收到的数据包与总发送数据包比率.通过SDN控制器在节点之间发送探测包,可以得到链路lvmvn的丢包率如公式(3)所示:

(3)

rxpacket(vm)表示节点vm收到的数据包总数,txpacket(vn)表示节点vn发送的数据包总数.

(4)

3 多约束自适应QoS路由模型

3.1 传输代价模型

(5)

(6)

2)第2项表示带宽对传输代价的影响,公式(6)Blvmvn表示链路lvmvn的带宽利用率.Bfi表示数据流fi对链路的带宽要求,要求的剩余带宽越多,选择链路lvmvn的可能性就越大.带宽利用率越高的链路,代价越大.

3)第3项表示节点负载对传输代价的影响.Wvn(t)可以有效的描述t时刻的节点容量和工作负载.节点vm和vn和之间的有效传输能力受到负载最高的节点的限制.节点负载越大,传输代价越大.

3.2 多QoS约束路由问题制定

(7)

(8)

(9)

δdelay,δband,δpacketloss分别表示链路的时延、带宽、丢包率阈值,以此制定了链路lvmvn的约束条件.

xi表示在第N个时间片内节点vm和节点vn之间是否存在可达链路.当链接存在时值为1,否则值为0.

3.3 多优先级阈值Adam求解

为了在不消耗大量计算资源的前提下更好的利用空间信息网络资源,提供个性化的服务质量,在路由计算中应考虑为不同优先级的数据流设置不同的链路约束阈值.相对于大多数算法的固定阈值设置,本文利用SDN控制器可以实时获取链路特性的特点,使用Adam(Adaptive moment estimation)[19]优化算法计算约束阈值,根据实时的链路特性为不同优先级的数据流自适应地更新阈值.

Adam算法是随机梯度下降的一阶优化算法,可以有效的求解目标函数的最大值或最小值.该算法结合了AdaGrad(自适应梯度算法)算法和RMSProp(均方根传播)算法的优点.

Adam算法首先在计算梯度的一阶矩时将当前更新梯度和最后更新梯度之间的差值保持在很小的范围内,实现平滑的梯度过渡,适应不稳定的目标函数,因此可以更好地适应网络变化.然后,设置梯度的二阶矩阵,通过计算当前梯度平方和过去梯度平方的平均值来更新学习率.本算法简单高效,根据数据流的不同优先级设定目标函数,计算阈值,提供满足不同服务质量需求的服务.

因此本文根据不同优先级数据流的QoS需求特点,如公式(10)所示,根据QoS到达曲线[20]和服务曲线[20]的水平偏差,设置目标函数.通过Adam求解曲线极值,确定阈值.

(10)

(11)

(12)

(13)

设目标函数为{f(θ)|θ∈{blvmvn,dlvmvn,pllvmvn}}={δdelay,δband,δpl}.通过Adam算法求解f(θ)曲线极值,公式(15)中,gt表示其梯度,即在时间步长t上计算ft(θ)对于θ的偏导.

t=t+1

(14)

gt=∇θft(θ)

(15)

mt=β1·mt-1+(1-β1)·gt

(16)

(17)

(18)

(19)

(20)

[vt]=

=

=

(21)

因此,通过上述算法为不同优先级的数据流得出阈值δdelay、δband、δpl,作为路由算法的约束条件.由此3类数据流可根据需求选择不同的路由线路,得到满足不同阈值约束的最佳路径.

4 蚁群优化算法在自适应QoS路由算法的应用

多约束问题的求解分为近似算法和启发式算法,近似算法能够得到相对精确的计算结果,但无法保证计算时间,启发式算法则能快速计算最优解.蚁群算法ACS(Ant Colony System)是一种启发式算法,由Dorigo于1991年提出,用于解决函数多约束优化问题[21].通过模拟蚂蚁从蚁巢出发寻找到达食物处最短的路径的过程,实现源节点与目的节点之间的端到端路径寻优.该算法计算简单,全局搜索能力好,鲁棒性强.但也存在后期收敛速度慢,且容易陷入局部最优的问题.

因此,本文为了解决上述多约束目标优化问题,对传统蚁群算法即ACS算法进行了改进.利用SDN可以实时获取链路状态信息的特性,首先通过传输代价模型和双禁忌表,对蚁群算法的转移概率公式进行了优化,加快了算法收敛速度.然后,改进了信息素挥发速度计算公式,根据数据流优先级通过SDN控制器动态设置参数,提高了路径选择质量.

4.1 转移概率优化

(22)

τlvm,vn(t)表示t时刻lvm,vn上的信息素浓度.ηlvmvn(t)表示t时刻lvm,vn上的启发度.allowedk表示蚂蚁k的下一个可选节点的集合.θ1,θ2分别为信息素和启发度的启发因子,表示其相对重要程度.

传统的蚁群算法将路径距离作为启发度进行寻优,直接应用于卫星网络会使大量数据流集中在最短路径从而造成链路拥塞.因此如公式(23)所示,根据第3节所述QoS约束模型(7),将启发度定义为公式(5)所示代价函数的倒数.

(23)

为了提前去掉不满足约束条件的链路,减少路径的计算量,以加快算法收敛速度.在借鉴禁忌搜索的基础上,加入两个禁忌表.充分利用SDN实时获取链路状态信息的优势,根据约束条件动态更新节点候选集allowedk.

allowedk={V-Tabu1-Tabu2}

(24)

4.2 信息素更新优化

每次蚂蚁走完一步或者完成n个节点的遍历之后,需要对拓扑中的残留信息素进行处理,(t+n)时刻lvm,vn上的信息素更新规则如公式(25)所示:

τlvmvn(t+n)=ρlvmvn·τlvmvn(t)+Δτlvmvn(t)

(25)

(26)

(27)

(28)

利用SDN控制器的可编程特性,根据数据流的不同优先级,针对挥发系数公式(27),自主调整a,b系数,从而动态改变对应链路的信息素挥发速度.例如优先级为2类的数据流,对带宽有更高的需求,可以将b的值设置的更高.则根据数据流的优先级设定,令b3a2>a3,a+b=1.状态好的链路信息素挥发更快,而状态差的链路信息素浓度更高,即会有更小的概率选择该链路作为转发路径.

4.3 SDN-AQoS路由算法步骤

本文SDN控制器上实现的路由算法SDN-AQoS流程如图3所示.

图3 算法流程图Fig.3 Algorithm process

具体实现如算法1所示.

算法1.SDN-AQoS路由算法

输入:当前时间片下的拓扑图GN,s,d

1.初始化：t=0;循环最大次数Nmax,;蚂蚁个数m;δdelay;δband;δpacketloss;Tabu1k(s);Tabu2k(s);α;β

2.for(k=1,k

3.初始化Tabu2k(s)和Tabu1k(s)

4.for(i=1,i

5.ifdlvmvn≥δdelayorblvmvn≤δbandorpllvmvn≥δpl

6.将vn节点加入Tabu2k(s)

7.重新从allowedk选择节点vn

8.else

10.确定转移节点vn

11.if节点vn是目的节点d

12.则清空所有Taub列表,进行下一只蚂蚁的遍历

13. 将此路径放到路径集P中

14.else

15.将蚂蚁k移动到节点vn

16.将节点vn插入Tabu1k(s)

17.通过SDN控制器设置a,b值

18.根据公式(25)计算τlvmvn(t+n)

19.更新信息素浓度

20.end if

21. end if

22. end for

23. end for

5 仿真实验结果与分析

5.1 实验参数设置

本文使用STK与MATLAB进行联合仿真,STK软件可模拟动态卫星网络场景,使用3颗可覆盖全球的高轨卫星和66颗铱星星座作为低轨卫星,同时选取20个非均匀分布的地面节点作为地面站.为了模拟真实的空间信息网络应用,卫星坐标每1s更新一次,根据卫星位置计算出坐标,输出位置及轨道参数信息,生成动态拓扑矩阵,将生成的动态拓扑导入MATLAB.

仿真卫星参数和网络参数设置如表1、表2所示.

表1 卫星参数设置Table 1 Satellite parameter settings

表2 网络参数设置Table 2 Network parameter setting

根据本证向量设置QoS属性在不同优先级下的服务速率δdelay,δband,δpl,如表3所示.

表3 QoS服务速率参数设置Table 3 QoS service rate parameter setting

结合文献[19]的结论,在Adam算法中的良好参数设置,本文令α=0.001,β1=0.9,β2=0.999,=10-8.

结合文献[17]给出的参数范围,为使算法达到最佳收敛次数,在验证本文算法性能时的蚁群算法参数设置如下:

θ1=1,θ2=3.一般认为节点数量的三分之二是最优蚂蚁数,故令蚂蚁数m=60.

图4 a和b对迭代次数的影响Fig.4 Influence of a and b on the number of iterations

5.2 实验结果及分析

5.2.1 SDN-AQoS算法收敛性能测试

多约束问题的启发式算法求解较难从理论角度证明其优化性能,进而采用测试函数的优化效果来验证算法性能.选取1对源-目的节点,生成100个不同优先级的数据流,平均数据包大小设置为10Mbit并随机分布在三层网络中,数据包传输速率从每秒1Mbps～4.5Mbps不等.在保持其他条件一致的情况下,将本文算法、使用本文中为代价的基于原始蚁群ACS[20]的路由算法、基于蚁群算法的QoS优化路由OQR-ACA[17]进行收敛比较.

根据图5收敛曲线图可以看出,本文算法在寻路阶段添加了约束判断,相对于ACS、OQR-ACA在早期收敛速度稍慢,但随着迭代次数的增加,由于候选节点集的优化,在搜索后期收敛速度加快.并通过SDN为不同优先级的数据流设置不同的参数,进行信息素更新,减少了迭代次数.最终,本文算法在迭代到第7次时已经收敛到最优解,完成7次迭代的时间为1.5s.ACS算法和OQR-ACA算法则需要更多的迭代次数才能达到收敛,完成迭代需要更长的运行时间.使得本文算法的收敛性优于ACS算法和OQR-ACA算法.

图5 算法收敛曲线Fig.5 Algorithm convergence curve

5.2.2 不同QoS优先级数据流路由性能测试

将3种优先级的数据流,共计1000个,以相同速率注入网络中,在源节点和目的节点相同的情况下,使用本文所述阈值设置方法和文献[17]中所述阈值设置方法进行比较,其时延、带宽、丢包率情况如图6所示.

图6 QoS性能Fig.6 QoS performance

1类优先级的数据流,要求时延更低,可以允许丢包率相对较高;2类优先级的数据流,要求更高的带宽;3类优先级的数据流,要求丢包率更低,可以允许时延相对较高.

由图6可以看出,3种数据流会根据不同的需求选择不同的路由路径.本文所述阈值方案能够实现在1优先级下更低的时延,2优先级下更高的带宽,3优先级下更低的丢包率.针对不同优先级的需求,实现了更佳的服务质量保证.

5.2.3 SDN-AQoS路由算法性能测试

为了评估本文提出的SDN-AQoS路由算法性能,本文实现了以下3个相关算法:经典的ECMP算法[7]、基于卫星网络下多约束QoS的MSRA算法[11]以及OQR-ACA[17]算法,并与其进行了比较.

1)网络平均吞吐量

图7显示了数据流量从1Mbps到4.5Mbps时吞吐量的变化状况,当流量小于2Mbps时,每个算法对网络吞吐量的负载能力基本相同.随着流量的增加,SDN-AQoS吞吐量的增加更为迅速并且始终拥有更高的吞吐量.当网络吞吐量达到30MBPS时,OQR-ACA和MSRA算法接近饱和,而SDN-AQoS路由算法在最小传输代价的路径优化目标中,考虑了星间链路和地面链路之间的差异、链路可用带宽及路径上节点的工作负载,从而使网络吞吐量更晚接近饱和.可以看出,SDN-AQoS算法平均吞吐量与OQR-ACA相比增加了11.1%,与MSRA相比增加了13.7%,与ECMP 算法相比提升了22.4%.

图7 网络平均吞吐量Fig.7 Average network throughput

2)负载分布指数

图8显示了数据流量从1Mbps～4.5Mbps时负载分布指数的变化状况.在全局流量较小时,各类算法都能得到较好的发挥,本文SDN-AQoS算法优势不明显.随着网络负载的增大,其它算法开始出现拥塞.SDN-AQoS算法在考虑多种因素的最小代价传输的同时对业务进行了分类,从而能够将更多的链路纳入路径选择中,不会始终在某些节点上聚集.因此在后期,负载分布指数相对另外3种算法始终保持在一个较高的水平.可以看出,SDN-AQoS算法平均负载指数与OQR-ACA相比增加了13.4%,与MSRA相比增加了16.7%,与ECMP 算法相比提升了24.1%.

图8 负载分布指数Fig.8 Load distribution index

6 结束语

本文提出了一种基于SDN的空间信息网络自适应QoS路由策略.在该算法中:1)基于SDN架构和星地链路的多元多维因素,设计了考虑链路质量、剩余带宽和节点负载的传输代价模型.定义了以最小传输代价为目标的多QoS约束问题;2)为不同优先级的数据流,通过Adam随机梯度下降算法自适应配置不同的阈值,实现QoS约束自适应;3)通过优化的蚁群算法求解多约束优化问题.根据约束条件使用双禁忌表优化节点候选集.考虑带宽、丢包率改进了信息素挥发系数公式,并利用SDN可编程的特性,根据数据流的不同优先级进行取值设计.从而优化了迭代过程,加快了收敛速度.最终找到满足约束条件且具有最小传输代价的路径.实现了自适应QoS路由算法SDN-AQoS;4)使用STK和MATLAB模拟卫星网络环境及SDN架构联合仿真.仿真结果表明,该路由策略与ACS、OQR-ACA相比具有更好的收敛性能和针对不同优先级数据流的QoS保障.与ECMP、OQR-ACA、MSRA算法相比,网络平均吞吐量提升了22.4%.实现了在保证服务质量的同时最大化网络吞吐量.从而解决了基于SDN的QoS在空间信息网络环境下应用的路由问题.