基于軟件定義網絡的多約束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架構下的網絡，在實際應用中，由于相關設備價格昂貴，商業化并未完全普及，因此，下一步將考慮混合網絡的使用情況，并進一步優化算法以降低平均代價。