基于软件定义网络的多约束QoS双路径路由优化方法*

苟平章，马 琳，郭保永，原 晨

(西北师范大学计算机科学与工程学院，甘肃 兰州 730070)

1 引言

随着网络技术的飞速发展，传统的分布式网络已难以有效应对互联网发展中出现的越来越多的挑战，例如，高质量的网络服务、高效便捷的故障恢复、快速有效的网络部署等[1]。服务质量QoS (Quality of Service)以高效管理网络资源的方式为应用程序提供性能保障服务，通常定义为用来解决网络延迟和阻塞等问题的一种技术[2]。影响QoS的主要约束条件有带宽、抖动、时延、丢包率等。软件定义网络SDN (Software Defined Network)突破了传统分布式网络的扁平化架构[3]，以一种中心化的网络架构为解决QoS路由问题提供了新的可能。与传统网络不同，SDN中控制平面和数据平面的松耦合方式使得路由端到端QoS数据流可以获得全局网络状态信息[4]。这种数控分离的方式使得数据平面仅需要接收控制平面的信息和请求，并在相应的硬件中实现即可，因此SDN架构下基于QoS的路由是研究的热点问题之一。

虽然SDN架构相较于传统网络架构下QoS路由研究具有诸多优势，但仍然存在多约束QoS路由算法复杂度高、无法充分利用SDN全局化网络参数获取优势、单链路故障后数据传输无法得到保障等问题，因此如何有效地提高网络业务的QoS路由仍然是一个具有挑战性的问题。Fores等人[5]根据SDN可编程的特点，通过计算控制平面上可编程标签的方法，对数据流的应用类型进行分类，针对不同类型应用的多约束QoS需求，向其分配相应的网络资源，实现不同类型应用差异化QoS保障。Elbasheer等人[6]提出了一种基于QoS的SDN视频流路由模型，该模型通过收集网络状态来检测视频流多约束QoS的变化寻找最优路径，通过使用区分服务码点DSCP (Differentiated Services Code Point)区分网络流量类型，视频流采用多媒体流服务类的AF(Assured Forwarding)标记优先级，尽力而为流采用默认的DSCP。在物联网架构下，Sun等人[7]提出了一种在SDN网络中保障QoS的智能路由机制。结合多种机器学习算法对数据流进行识别与分类，针对多约束QoS和不同类型应用的数据流选择传输的最优路径，通过局部路由变化算法只调整拥塞链路前后的链路，解决链路拥塞问题。Henni等人[8]提出了SDN中用于QoS的一致性网络框架，通过保证优先流的QoS和最大限度地保留尽力而为流来提高网络视频的服务质量。Egilmez 等人[9]设计的OpenFlow控制器在SDN上提供端到端服务质量的多媒体传输，提供了各种接口和功能来实现QoS，区分多媒体数据流和其他数据流，优先保障多媒体数据流的QoS。Parsaei等人[10]利用二型模糊系统和杜鹃优化算法的混合模型来寻找远程手术中的最优可靠路径，在满足高质量多约束QoS的同时找到最优路径，但未考虑到链路发生故障的情形。Juttner等人[11]提出一种基于拉格朗日松弛的QoS感知算法LARAC(LAgrange Relaxation based Aggregated Cost)，解决时延约束下最小代价路径问题。Binsahaq等人[12]在LARAC算法的基础上引入SDN架构并改变该算法的搜索起点和停止条件，减少Dijkstra的重复调用次数。虽然该算法在平均运行时间方面有着显著降低，但只考虑了代价和时延的约束条件，无法满足多种多样的网络应用的传输需求。

路由环路问题是冗余链路所面临的最为严重的问题，双路径冗余链路是保障QoS技术探索的主流方向。文献[13]在传统网络架构下提出了一种高可靠多约束双路径反向删减算法，寻找满足多约束要求并且链路不相交的高可靠双路径，其在寻找路径的过程中，对网络拓扑图中的链路进行了反转方向和删除2种操作，但在传统网络架构下不能充分发挥该算法的优势。文献[14]在传统网络架构下结合蚁群算法和双路径路由，提出了一种基于扩展Dijkstra的多约束QoS路由算法，虽然保障了链路故障后的数据传输，但是无法保障计算出的备份路径为最优路径。随着SDN理论逐渐成熟，针对多路径的路由策略也逐渐应用其中。文献[15]在现有SDN流量调度技术研究的基础上，结合强化学习在策略优化中的优势和SDN集中控制的特点，利用深度学习的神经网络拟合Q值表，提出了一种基于深度强化学习的智能多路径路由规划方法。通过判断当前路径是否满足约束条件继而生成多路径，提高链路带宽的利用率。文献[16]根据多媒体应用中对多约束QoS的不同要求，将数据流分为对时延敏感的应用流量和无特殊要求(如FTP)的流量，引入基于优先级感知的动态多路径路由算法，对不同类型的数据流使用不同的链路代价函数，灵活分配网络资源，减少了不同类别数据流之间的影响，并提高了低优先级流量的多约束QoS。文献[17]试图寻找一种基于无模型的强化学习方法，当不同的数据流分组具有相同的源、目的节点并同时进行传输时，控制器为不同的数据流分组分别下发不同的路径传输。这种保持多路径路由的方法比以前只确定单一路径路由的方法降低了时延，但不能保证多路径之间均不相交。SDN架构下许多关于多路径路由策略的研究侧重于优化链路、最大限度地利用网络资源等，当节点或链路发生拥塞或故障时，数据传输无法得到保障。因此，SDN架构下结合多约束QoS和冗余双链路是当前研究的热点问题之一。

综合以上研究，针对SDN架构下多约束QoS路由策略算法时间复杂度高和冗余双链路中环路的问题，本文提出一种基于软件定义网络的多约束QoS双路径路由优化算法SDN_MCQDP (Multi-Constrained QoS Dual-Path routing optimization algorithm based on Software-Defined Network)。首先，在SDN分级分域架构下从目的节点反向进行广度优先搜索，通过拉格朗日松弛对偶算法对多约束QoS问题进行简化，寻找节点到达目的节点的最优路径。然后，组合网络拓扑图中每一个节点到达目的节点的最优路径，生成基于目的节点可行路径的有向无环图DAG (Directed Acyclic Graph)。最后，根据反向链路删减的方法生成2条不相交的冗余链路，在链路故障时数据传输能得到保障。

2 相关技术

2.1 SDN构架

SDN是一种新型的网络架构，目前的研究大多为单个控制器，无法满足大规模网络的需求。为了更好地部署SDN并满足大规模网络的需求，在多控制器网络拓扑的设计中，使用分级分域架构[18]，如图1所示。在SDN分级分域架构中，部署多个控制器，通过分层控制器处理大量的数据。将大规模网络进一步细化为多个区域，每个区域由域内控制器单独负责。根控制器负责同步各个域控制器，以便在不同域设置路由。QoS多个约束条件取决于应用本身及随着时间增长使用该应用用户的平均数。链路时延、带宽、丢包率等信息都可以通过流量测量工具汇总给域控制器。利用这些信息，每个域控制器上的路由优化算法可以为所有多约束QoS生成基于目的节点可行路由的DAG，结合所有域控制器生成的DAG，创建全局可行路径的DAG。多域之间的路由问题简化为单域路由问题。同时，根控制器可简化为抽象后网络拓扑的域内部控制器，根据相应节点和链路信息进行最优路径选择。

Figure 1 Hierarchical domain architecture of SDN图1 SDN分级分域架构

2.2 多约束 QoS模型

基于文献[19,20]，为每个网络拓扑图生成一个至少包含一条从源节点到目的节点路径的DAG，且满足QoS约束条件，用G(N,S)表示。其中，N表示一组节点的节点集，可以是路由器、交换机或者子网；S是有向边集，表示网络链路[21]。

在QoS约束条件中，丢包率lost为乘性约束，通过对丢包率取对数的方式，将其转换为加性参数，即lg(1+lost)。由对数性质可知，当1+lost的值越小时，lg(1+lost)的值也越小。因此，本文的代价设为丢包率的对数和链路成功交付数据流所造成的开销。为解决从源节点到目的节点代价最小且满足所有约束条件的最优路径问题，建立了基于SDN的多约束QoS模型，如式(1)～式(4)所示。

源节点到目的节点的路径中，最小代价如式(1)所示：

(1)

链路时延低于约束界限,如式(2)所示：

s.t.DTxuv≤d

(2)

链路抖动低于约束界限，如式(3)所示：

s.t.JTxuv≤j

(3)

约束路径瓶颈带宽大于可用带宽的最小界限,如式(4)所示：

(4)

其中，b∈R+表示网络应用对带宽约束的边界；B=(B1,B2,…,Bi)表示各边可用带宽的列向量，Bi是列向量内的元素。

2.3 拓扑发现及信息收集

在网络初始阶段，控制器需要进行拓扑发现和信息收集，OpenFlow目前没有统一规定拓扑发现的方法。本文利用传统网络中的链路状态发现协议LLDP (Link Layer Discovery Protocol) 实现网络拓扑发现。

图2为通过LLDP协议进行拓扑发现的过程。首先，控制器以泛洪的形式向网络中所有与之相连接的节点下发流条目，以请求端口信息。当控制器建立安全传输协议TLS(Transport Layer Security)会话后，向所有与之相连的节点发送 Packet-Out 消息包。当一个节点收到邻居发送的LLDP报文后，首先向自己相邻的节点发送LLDP报文，然后以Packet_In消息包的形式向控制器汇报自己和邻居的情况。当所有节点都执行完以上操作后，控制器便可以获得网络中的所有链路信息，完成拓扑发现。为了实时保障应用对多约束QoS的需求，还需要对网络状态进行监测。本文通过使用时间戳计数器，在节点之间发送数据流探测，定期轮询并存储端口发送的字节数，以此计算带宽、时延和抖动等网络状态信息。

Figure 2 Topology discovery process图2 拓扑发现过程

3 SDN_MCQDP算法

SDN_MCQDP算法需要生成基于目的节点的可行路径DAG，以确保图中每个节点均包含至少一条到达目的节点且满足多约束QoS需求的可行路径。因此，算法分为3个阶段：生成DAG阶段、多约束QoS路由选择阶段和生成双路径冗余链路阶段。生成DAG阶段，负责寻找和组合网络拓扑中所有节点到达的目的节点且满足所有QoS约束的可行路径。而寻找每一条满足约束的可行路径由多约束QoS路由选择阶段负责。反向链路删减生成双路径阶段，结合DAG生成满足多约束QoS的双路径冗余链路。

3.1 生成有向无环图

在源节点到目的节点的路径中，包含了许多中间节点到目的节点的可行路径。因此，计算源节点到目的节点可行路径的过程中，可能会遍历网络拓扑中的所有节点。本文通过基于目的节点可行路径DAG，即网络拓扑中与目的节点能够连通的所有节点，生成到达目的节点且满足多约束QoS的可行路径DAG，来达到减少重复遍历的目的。只计算少量节点可行路径就可以实现网络拓扑中所有节点可行链路的全覆盖。生成基于目的节点可行路径DAG的具体步骤如下所示：

步骤1对网络拓扑图中所有的链路进行反转，从目的节点开始进行广度优先搜索，并将节点存储到队列H中。

步骤2从队列H中依次读取节点，并计算节点到目的节点满足多约束QoS的最优路径。

步骤3按照每个节点到目的节点最优路径的跳距递减存储，并生成基于目的节点可行路径的DAG。如果已经遍历搜索网络拓扑中所有节点，则停止搜索。

假设从目的节点开始广度优先搜索所需要遍历的叶子节点数为m，网络中所有节点数为n，k为QoS约束条件的个数。生成基于目的节点的DAG，计算最优路径的时间复杂度为O(k×m×n)，而使用Dijkstra算法直接计算最优路径的时间复杂度为O(k×n2)。由此可见，上述方法可以有效降低时间复杂度，减少路由计算时间，但由于广度优先搜索内存耗费量大，会导致链路代价小幅度上升。通过上述方法能够得到所有节点到目的节点的可行路径。源节点距离目的节点越远，则可行路径包含的中间节点就越多。合并已经搜索到的可行路径，可以得到一个关于到达目的节点可行路径的DAG。迭代求解最优路径的过程中，如果已遍历存储的所有可行路径则终止算法。所有基于目的节点的广度优先搜索都可以离线完成，因为链路布局不会随着流量条件的变化而变化。只有当网络拓扑结构发生变化时，才需要重新执行广度优先搜索。在满足多约束QoS的条件下，该DAG中的可行路径也可以用于其他节点传输数据流。

图3为以R8为目的节点生成DAG的例子，每条链路均为双向传输。链路上的一对值分别表示时延(ms)和抖动(ms)，令路径QoS约束的最大值分别为40 ms和10 ms。图3中的虚线为通过SDN_MCQDP算法计算R1～R8,R2～R8和R3-R8满足多约束QoS需求的可行路径，组合这些可行路径生成DAG。从DAG中可以观察到，R1～R7中的任一节点均包含至少一条到达目的节点R8且满足多约束QoS需求的路径。

Figure 3 Generating DAG based on destination node图3 生成基于目的节点的DAG

3.2 多约束QoS路由

Dijkstra是经典的求解最短路径算法，但只适用于已满足约束条件的路径，因此具有很大的局限性。拉格朗日松弛对偶算法是求解多目标约束优化的经典算法之一，原函数约束条件多为NP-hard问题，而拉格朗日松弛对偶算法将多约束条件与目标函数聚合，使得目标函数仍保持线性，进而简化原问题[22 - 24]。本文将Dijkstra和拉格朗日松弛对偶算法结合起来，以便在更短的时间内找到满足数据流约束条件的最优传输路径。

在SDN中，对于一条链路来说，常见的QoS约束性质可分为加性、乘性和凹性，如表1所示。控制器在计算最优路径前需要对乘性约束和凹性约束分别进行预处理，对乘性约束取对数将其转化为加性约束，通过路径选择预处理的方法解决凹性约束，将多约束问题简化为一个线性规划问题。

Table 1 Common QoS constraint properties on links

通过拉格朗日松弛对偶算法将多约束QoS与代价函数聚合的具体步骤如下所示：

步骤1通过移除不满足QoS带宽约束的链路进行选路预处理。首先，应用发出报文转发的请求，当来自应用的第1个流的第1个包请求传输时，入口路由器向控制器发送该流的相关信息，开始计算该应用在一次信息更新时间间隔内传输流的数量。将该应用的瓶颈带宽乘以一次信息更新时间内流的请求数量，对链路中可用带宽不满足计算后带宽的链路进行剪枝处理。通过控制器设置链路的抖动、时延为无穷大并将丢包率设为1就可以完成剪枝处理。

例如，在线语音(VoIP)传输数据的瓶颈带宽为0.19 Mbps，信息更新周期为30 ms。在一次信息更新的时间内流的请求数量为50，控制器需要对可用带宽小于0.19×50=9.5 Mbps的链路进行剪枝。首先计算VoIP数据传输的最优路径，然后将该路径中所有已激活链路的可用带宽减去9.5 Mbps，最后用剪枝后满足可用带宽的链路寻找其他数据流的最优传输路径，这样能够尽可能满足所有应用的带宽需求。

ZL=maxλ∈R+LR(λ)

(5)

其中，λ={λ1,λ2}分别表示约束条件式(2)和式(3)聚合后的拉格朗日乘子，λ1，λ2∈R+。LR(λ)为代价函数和约束函数聚合后，在非对偶约束条件下优化的拉格朗日松弛对偶函数，具体如式(6)所示：

λ2J)xuv-(λ1d+λ2j))

(6)

当λ1，λ2为常数时，(λ1d+λ2j)的值也为常数，为了便于计算，将其舍去，式 (6)化简式(7)：

(7)

综上分析，可以将链路权重定义为C,如式(8)所示：

C=(cT+λ1D+λ2J)xuv

(8)

3.3 迭代求解最优路径

梯度下降法[25]是寻找目标函数最小化值的方法之一。本文利用梯度下降法求解多约束QoS问题得到最优路径。通过分析链路权重C可以发现，随着拉格朗日乘子λ逐渐增大，时延、抖动和丢包率在LR(λ)中的占比也会增大，因此可以认为λ是单调递增函数，需要沿负梯度迭代寻找最优路径。

通过梯度下降法迭代求解最优路径的具体步骤如下所示：

步骤1为确定时延和抖动的下降梯度，令时延和抖动的下降梯度为ΔD和ΔJ，对函数LR(λ)中λ1和λ2分别求偏导,如式(9)和式(10)所示：

(9)

(10)

为了保证梯度下降的方向为负梯度，约束ΔD和ΔJ的最大值小于0，即ΔD∈[Dxuv-d，0),ΔJ∈[Jxuv-j,0)。

步骤2设时延和抖动的步长为αt和βt，其计算分别如式(11)和式(12)所示：

(11)

(12)

其中，t表示当前迭代计算的次数，Cmin是不受QoS约束的最小路径权重，μt和ξt为确定合适步长而持续更新的非负常数。

(13)

(14)

(15)

(16)

生成DAG阶段和多约束QoS路由选择阶段的伪代码如算法1所示。

算法1多约束QoS路由DAG算法

输入:网络拓扑图G(N,S)，源节点u，目的节点v,数据传输多约束QoS的需求。

输出:源节点到目的节点(u,v)的最优路径。

1V(Maximum number of iterations),t(Number of iterations)；//初始化参数

2S′=Backward(S);//反转链路

3H=BFS(N,S′,v);/*广度优先搜索网络拓扑图中的节点*/

4M=∅;//初始化M，存放从P中出栈的节点

5G_DAG= {};/*初始化G_DAG，存放u→v的最优路径*/

6while(M!=N)do

7P′=P.pop();

8fort=1 toVdo

9XZL=Dijkstra(P′,C);

10 get shortest pathutor,xuv, fromXZL;

11if(Dxuv≤d&&Jxuv≤j)

13break;

14else

15 通过式(9)和式(10)更新时延和抖动的下降梯度ΔD、ΔJ；

16 通过式(11)和式(12)更新时延和抖动的步长αt、βt；

20endif

21endif

22endfor

23M=M∪nodes(xuv)；

24G_DAG.add(xuv)；//生成基于目的节点的DAG

25endwhile

26return基于目的节点的有向无环图G_DAG

3.4 生成双路径冗余链路

当控制器下发的路由出现故障时，需要快速重新计算并下发路由，但是在此期间，分组数据有可能会丢失。传统的双路径路由在计算时，首先检查并计算源节点到目的节点的最短路径，然后从网络拓扑中删除该路径后重新搜索最短路径。假设存在2条可行路径，不一定能找到2条不相交的路径，搜索到的备用路径的长度可能会比预期的长许多，不能同时满足QoS多个约束条件的需求。为解决传统的双路径路由问题，本文在SDN分级分域的架构下，控制器利用资源集中管理的特点，根据每个节点和链路的状态信息及多约束QoS的需求，使用反向链路删减生成备份路径的方法[13]，在源节点和目的节点之间寻找2条不相交且满足多约束QoS的最优路径。当链路或节点发生故障时，控制器能够快速切换到备用路径以保障数据正常传输，同时在一定程度上能够减轻网络的负载。具体步骤如下所示：

步骤1通过算法1得到基于目的节点的有向无环图G_DAG，在G_DAG中找到满足多约束QoS需求且成本值最小的第1条路径P1。如果P1不存在，则查找失败，算法结束。否则，转到步骤2。

步骤2将找到的第1条路径P1中所有的链路反转反向，设置该路径上所有加性约束为0，DTxuv=0,JTxuv=0,∀(u,v)∈P1，并重新生成一个基于目的节点的有向无环拓扑网络图G′。

在步骤2中设置反转链路上所有路径的加性约束为0而不是负值的目的在于避免由负值引起的环路。

图4的示例中，寻找R1和R6之间2条不相交且满足多约束QoS的路径。在已经生成DAG的前提下，每个链路上的一对值分别表示时延(ms)和抖动(ms)，并假设QoS约束的最大值分别为40 ms和10 ms。图4a～图4d分别对应步骤1～步骤4。在图4a中计算得到满足多约束QoS的第1条路径P1为R1-R4-R6-R5-R8。在图4b中将P1中所有的链路反转，并令加性约束的权值为0，生成新的有向无环网络拓扑图G′。图4c中，在新拓扑图中计算得到的最优路径P2为R1-R5-R6-R8。将路径P1和P2求并操作，删除路径集中的反向链路，即删除R5-R6。其余链路根据链路方向重新组合为最终的2条最优路径，即P′1为R1-R4-R6-R8，P′2为R1-R5-R8，如图4d所示。

Figure 4 Multi constrained QoS dual path routing图4 多约束QoS双路径路由

双路径冗余链路的反向链路删减算法如算法2所示。

算法2反向链路删减算法

输入:基于目的节点的有向无环图G_DAG,源节点u，目的节点v，数据传输多约束QoS的需求。

输出:满足多约束QoS需求的2条不相交路径P1和P2。

1P1=Dijkstra(G_DAG，u，v)；

2if(P1=∅)then

3returnfailure;

4else

5 get the pathP1;

6endif

7foreach link (u，v) in pathP1/*反转P1中所有链路，并令链路权值为0*/

8modify(u，v) to (v，u);

9 setDTxuv=0,JTxuv=0;

10endfor

11P2=Dijkstra(G′，u，v);

12if(P2=∅)then

13returnfailure;

14else

15 get the pathP2;

16endif

17RA=take the union ofP1andP2;

18PALL=delete the reverse link fromRAand combine it intoP＇1andP＇2;

19foreach linkQinPALL

20if(DTxuv≥d&&JTxuv≥j)then/*判断P1和P2是否满足多约束QoS需求*/

21CML=Q∩P1;

22Remain_links=deleteCMLfromQ;

23 deleteRemain_linksinG′;

24 go to line 11;

25else

26 returnPALLand get the two paths;

27endif

28endfor

4 仿真实验及结果分析

通过对不同的网络数据流进行测试[26]，网络中超过80%的数据流持续时间不超过10 s，仅有低于0.1%的数据流持续时长超过200 s，数据流中超过50%的字节持续时间低于25 s。本文设置控制器每25 s更新一次网络状态，并且向节点下发新的流表。

为精确评估算法的性能，本文在VMware上使用网络仿真工具Mininet构建网络拓扑，用Ryu作为控制器设备实现功能模块，用Iperf流生成工具模拟真实网络流量。仿真拓扑图使用Internet Topology Zoo dataset[27]的8个真实网络拓扑案例，其中ATT North America拓扑中共25个节点，57条链路；BT Europe拓扑中共24个节点，27条链路；BT North American拓扑共36个节点，17条链路；Interroute拓扑共27个节点，36条链路；Colt拓扑共153个节点，191条链路；TaTa拓扑共145个节点，194条链路；Cogent拓扑共197个节点，245条链路；Global Center拓扑共9个节点，36条链路。通过对不同网络拓扑类型的路由计算时间、链路利用率和QoS流满意度，验证SDN_MCQDP算法性能，与基于SDN架构的QT(Quality of service-Technology of network resource allocation)[2]、MODLARAC(MODified LAgrange Relaxation based Aggregated Cost)算法[12]和基于传统网络架构的RMCDP_RD(Reliable Multi-Constrained Dual-Path Reverse Deletion)[13]、H_MCOP(Heuristic for Multi-Constrained Optimal Path)算法[28]进行仿真对比实验。

4.1 路由计算时间

路由计算时间包括：生成DAG的时间，控制器向计算DAG中生成双路径冗余链路的时间和下发流表的时间，以及源节点传输数据流到达目的节点的时间总和。将SDN_MCQDP与MODLARAC、QT、RMCDP_RD、H_MCOP算法进行比较，在不同拓扑图下的路由计算时间如图5所示。

Figure 5 Routing calculation time图5 路由计算时间

如图5所示，Global Center为全连接网络，尽管节点个数较少，但是H_MCOP在多约束QoS最优路径选择中存在产生累积误差、搜索范围不全面等缺点，因此路由计算时间最长。SDN_MCQDP算法在基于SDN架构的全局网络视图中，利用广度优先搜索降低了算法的时间复杂度，并通过生成基于目的节点的DAG，避免了节点的重复调用，有效降低了路由计算时间。针对8种拓扑图，SDN_MCQDP算法的平均路由计算时间在3～6 s，相比H_MCOP、QT、RMCDP_RD和MODLARAC分别降低了65.6%，57.7%，52.0%和7.1%。

4.2 链路利用率比较

将SDN_MCQDP与MODLARAC、QT、RMCDP_RD和H_MCOP算法进行比较，在不同拓扑图下的链路利用率如图6所示。从图6可以看出，SDN_MCQDP、QT、MODLARAC、RMCDP_RD和H_MCOP的平均链路利用率为75.8%，75.3%，75.0%，71.2%和58.9%。SDN_MCQD、MODLARAC、RMCDP_RD和QT的平均链路利用率要远高于H_MCOP的。H_MCOP存在无法返回最优路径和计算最优路径存在误差的情况，因此链路利用率较低。SDN_MCQDP通过对无用带宽链路做剪枝处理，减少了可用带宽的资源浪费，并且双路径路由在一定程度上能够减轻链路负载，因此，在满足网络应用带宽需求的同时，有效提高了链路利用率。

Figure 6 Comparison of link utilization图6 链路利用率比较

4.3 QoS流满意度

针对不同网络应用的QoS需求，7种常见的真实网络应用的QoS需求如表2所示。本文依据表2对QoS流满意度进行测试。

Table 2 QoS requirements of different applications

在不计入设备故障时，使用SDN_MCQDP满足QoS需求流的百分比的实验结果如图7所示。从图7可以看出，不同网络应用需求的QoS流满意度在95%～100%。SDN_MCQDP算法综合考虑了时延、抖动、带宽和丢包率等4种QoS约束条件，在满足全部约束条件的情况下寻找最优路径，能够满足大部分网络应用的流的满意度。

Figure 7 QoS satisfaction of different applications图7 不同应用下流的QoS满意度

链路发生故障时使用SDN_MCQDP满足QoS流需求的百分比的实验结果如图8所示。从图8可以看出，当链路发生故障的数量分别为2，4，6和8时，大部分网络应用仍能满足其QoS需求，因为SDN_MCQDP利用反向链路删减算法得到2条不相交且满足多约束QoS的最优路径，控制器能够快速响应并下发备用路径。

Figure 8 Satisfaction of QoS flow after link failure图8 链路故障后QoS流的满意度

4.4 平均代价

SDN_MCQDP与MODLARAC、QT、RMCDP_RD和H_MCOP算法的链路平均代价如图9所示。假设存在最优路径，H_MCOP能够在满足所有约束条件的情况下搜索最优路径，但是存在无法返回最优路径的隐患。SDN_MCQDP不存在这种情况，本文算法需要控制器根据网络规模发送大量数据流，生成基于目的节点的DAG，提高链路开销来降低算法的时间复杂度，导致平均代价消耗大。如果供应商需要在多约束QoS条件下快速选择数据转发的最优路径，但不介意链路平均代价的小幅提升，SDN_MCQDP是最优的选择。

Figure 9 Average cost图9 平均代价

4.5 时延相对差异百分比

根据(时延约束-路径时延)/时延约束*100%计算链路中时延的相对差异百分比，在不同网络规模下对比SDN_MCQDP与MODLARAC、QT、RMCDP_RD 算法在时延方面的性能，结果如图10所示。 H_MCOP算法存在无法返回最优路径的情况，因此在该性能测试中无法对其进行对比。

Figure 10 Percentage of relative delay difference 图10 时延相对差异百分比

从图10可以看出，SDN_MCQDP算法的时延相对差异百分比相较于MODLARAC、RMCDP_RD和QT算法的分别提高了4.9%，2.4%和1.1%。MODLARAC的时延相对百分比最低，因为该算法不会直接返回最优路径，仍需进一步计算以免遗漏满足多约束QoS的最优路径。SDN_MCQDP算法在生成基于目的节点DAG的过程中，已经计算出中间节点到目的节点的所有可行路径，减少了节点的重复调用，降低了链路时延。

5 结束语

针对SDN架构下多约束QoS路由算法复杂度高、链路故障后数据传输无法保障等问题，设计并实现了一种基于SDN的多约束QoS双路径路由优化算法SDN_MCQDP。通过拉格朗日松弛对偶算法将多种约束性能指标整合到代价函数；生成基于目的节点DAG的方法，来降低算法复杂度并减少路由计算时间；利用多约束双路径反向删减算法得到2条不相交的最优路径，保障数据在链路或节点发生故障时正常传输。仿真结果表明，SDN_MCQDP能够有效降低路由计算时间，提升链路利用率，且适应多种网络拓扑类型，满足大部分网络应用的QoS需求。SDN_MCQDP虽然在仿真中有较好的表现，但是目前仅考虑SDN架构下的网络，在实际应用中，由于相关设备价格昂贵，商业化并未完全普及，因此，下一步将考虑混合网络的使用情况，并进一步优化算法以降低平均代价。