茍平章，馬 琳，郭保永，原 晨

(西北師范大學計算機科學與工程學院，甘肅 蘭州 730070)

1 引言

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，傳統(tǒng)的分布式網(wǎng)絡(luò)已難以有效應(yīng)對互聯(lián)網(wǎng)發(fā)展中出現(xiàn)的越來越多的挑戰(zhàn)，例如，高質(zhì)量的網(wǎng)絡(luò)服務(wù)、高效便捷的故障恢復(fù)、快速有效的網(wǎng)絡(luò)部署等[1]。服務(wù)質(zhì)量QoS (Quality of Service)以高效管理網(wǎng)絡(luò)資源的方式為應(yīng)用程序提供性能保障服務(wù)，通常定義為用來解決網(wǎng)絡(luò)延遲和阻塞等問題的一種技術(shù)[2]。影響QoS的主要約束條件有帶寬、抖動、時延、丟包率等。軟件定義網(wǎng)絡(luò)SDN (Software Defined Network)突破了傳統(tǒng)分布式網(wǎng)絡(luò)的扁平化架構(gòu)[3]，以一種中心化的網(wǎng)絡(luò)架構(gòu)為解決QoS路由問題提供了新的可能。與傳統(tǒng)網(wǎng)絡(luò)不同，SDN中控制平面和數(shù)據(jù)平面的松耦合方式使得路由端到端QoS數(shù)據(jù)流可以獲得全局網(wǎng)絡(luò)狀態(tài)信息[4]。這種數(shù)控分離的方式使得數(shù)據(jù)平面僅需要接收控制平面的信息和請求，并在相應(yīng)的硬件中實現(xiàn)即可，因此SDN架構(gòu)下基于QoS的路由是研究的熱點問題之一。

雖然SDN架構(gòu)相較于傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下QoS路由研究具有諸多優(yōu)勢，但仍然存在多約束QoS路由算法復(fù)雜度高、無法充分利用SDN全局化網(wǎng)絡(luò)參數(shù)獲取優(yōu)勢、單鏈路故障后數(shù)據(jù)傳輸無法得到保障等問題，因此如何有效地提高網(wǎng)絡(luò)業(yè)務(wù)的QoS路由仍然是一個具有挑戰(zhàn)性的問題。Fores等人[5]根據(jù)SDN可編程的特點，通過計算控制平面上可編程標簽的方法，對數(shù)據(jù)流的應(yīng)用類型進行分類，針對不同類型應(yīng)用的多約束QoS需求，向其分配相應(yīng)的網(wǎng)絡(luò)資源，實現(xiàn)不同類型應(yīng)用差異化QoS保障。Elbasheer等人[6]提出了一種基于QoS的SDN視頻流路由模型，該模型通過收集網(wǎng)絡(luò)狀態(tài)來檢測視頻流多約束QoS的變化尋找最優(yōu)路徑，通過使用區(qū)分服務(wù)碼點DSCP (Differentiated Services Code Point)區(qū)分網(wǎng)絡(luò)流量類型，視頻流采用多媒體流服務(wù)類的AF(Assured Forwarding)標記優(yōu)先級，盡力而為流采用默認的DSCP。在物聯(lián)網(wǎng)架構(gòu)下，Sun等人[7]提出了一種在SDN網(wǎng)絡(luò)中保障QoS的智能路由機制。結(jié)合多種機器學習算法對數(shù)據(jù)流進行識別與分類，針對多約束QoS和不同類型應(yīng)用的數(shù)據(jù)流選擇傳輸?shù)淖顑?yōu)路徑，通過局部路由變化算法只調(diào)整擁塞鏈路前后的鏈路，解決鏈路擁塞問題。Henni等人[8]提出了SDN中用于QoS的一致性網(wǎng)絡(luò)框架，通過保證優(yōu)先流的QoS和最大限度地保留盡力而為流來提高網(wǎng)絡(luò)視頻的服務(wù)質(zhì)量。Egilmez 等人[9]設(shè)計的OpenFlow控制器在SDN上提供端到端服務(wù)質(zhì)量的多媒體傳輸，提供了各種接口和功能來實現(xiàn)QoS，區(qū)分多媒體數(shù)據(jù)流和其他數(shù)據(jù)流，優(yōu)先保障多媒體數(shù)據(jù)流的QoS。Parsaei等人[10]利用二型模糊系統(tǒng)和杜鵑優(yōu)化算法的混合模型來尋找遠程手術(shù)中的最優(yōu)可靠路徑，在滿足高質(zhì)量多約束QoS的同時找到最優(yōu)路徑，但未考慮到鏈路發(fā)生故障的情形。Juttner等人[11]提出一種基于拉格朗日松弛的QoS感知算法LARAC(LAgrange Relaxation based Aggregated Cost)，解決時延約束下最小代價路徑問題。Binsahaq等人[12]在LARAC算法的基礎(chǔ)上引入SDN架構(gòu)并改變該算法的搜索起點和停止條件，減少Dijkstra的重復(fù)調(diào)用次數(shù)。雖然該算法在平均運行時間方面有著顯著降低，但只考慮了代價和時延的約束條件，無法滿足多種多樣的網(wǎng)絡(luò)應(yīng)用的傳輸需求。

路由環(huán)路問題是冗余鏈路所面臨的最為嚴重的問題，雙路徑冗余鏈路是保障QoS技術(shù)探索的主流方向。文獻[13]在傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下提出了一種高可靠多約束雙路徑反向刪減算法，尋找滿足多約束要求并且鏈路不相交的高可靠雙路徑，其在尋找路徑的過程中，對網(wǎng)絡(luò)拓撲圖中的鏈路進行了反轉(zhuǎn)方向和刪除2種操作，但在傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下不能充分發(fā)揮該算法的優(yōu)勢。文獻[14]在傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下結(jié)合蟻群算法和雙路徑路由，提出了一種基于擴展Dijkstra的多約束QoS路由算法，雖然保障了鏈路故障后的數(shù)據(jù)傳輸，但是無法保障計算出的備份路徑為最優(yōu)路徑。隨著SDN理論逐漸成熟，針對多路徑的路由策略也逐漸應(yīng)用其中。文獻[15]在現(xiàn)有SDN流量調(diào)度技術(shù)研究的基礎(chǔ)上，結(jié)合強化學習在策略優(yōu)化中的優(yōu)勢和SDN集中控制的特點，利用深度學習的神經(jīng)網(wǎng)絡(luò)擬合Q值表，提出了一種基于深度強化學習的智能多路徑路由規(guī)劃方法。通過判斷當前路徑是否滿足約束條件繼而生成多路徑，提高鏈路帶寬的利用率。文獻[16]根據(jù)多媒體應(yīng)用中對多約束QoS的不同要求，將數(shù)據(jù)流分為對時延敏感的應(yīng)用流量和無特殊要求(如FTP)的流量，引入基于優(yōu)先級感知的動態(tài)多路徑路由算法，對不同類型的數(shù)據(jù)流使用不同的鏈路代價函數(shù)，靈活分配網(wǎng)絡(luò)資源，減少了不同類別數(shù)據(jù)流之間的影響，并提高了低優(yōu)先級流量的多約束QoS。文獻[17]試圖尋找一種基于無模型的強化學習方法，當不同的數(shù)據(jù)流分組具有相同的源、目的節(jié)點并同時進行傳輸時，控制器為不同的數(shù)據(jù)流分組分別下發(fā)不同的路徑傳輸。這種保持多路徑路由的方法比以前只確定單一路徑路由的方法降低了時延，但不能保證多路徑之間均不相交。SDN架構(gòu)下許多關(guān)于多路徑路由策略的研究側(cè)重于優(yōu)化鏈路、最大限度地利用網(wǎng)絡(luò)資源等，當節(jié)點或鏈路發(fā)生擁塞或故障時，數(shù)據(jù)傳輸無法得到保障。因此，SDN架構(gòu)下結(jié)合多約束QoS和冗余雙鏈路是當前研究的熱點問題之一。

綜合以上研究，針對SDN架構(gòu)下多約束QoS路由策略算法時間復(fù)雜度高和冗余雙鏈路中環(huán)路的問題，本文提出一種基于軟件定義網(wǎng)絡(luò)的多約束QoS雙路徑路由優(yōu)化算法SDN_MCQDP (Multi-Constrained QoS Dual-Path routing optimization algorithm based on Software-Defined Network)。首先，在SDN分級分域架構(gòu)下從目的節(jié)點反向進行廣度優(yōu)先搜索，通過拉格朗日松弛對偶算法對多約束QoS問題進行簡化，尋找節(jié)點到達目的節(jié)點的最優(yōu)路徑。然后，組合網(wǎng)絡(luò)拓撲圖中每一個節(jié)點到達目的節(jié)點的最優(yōu)路徑，生成基于目的節(jié)點可行路徑的有向無環(huán)圖DAG (Directed Acyclic Graph)。最后，根據(jù)反向鏈路刪減的方法生成2條不相交的冗余鏈路，在鏈路故障時數(shù)據(jù)傳輸能得到保障。

2 相關(guān)技術(shù)

2.1 SDN構(gòu)架

SDN是一種新型的網(wǎng)絡(luò)架構(gòu)，目前的研究大多為單個控制器，無法滿足大規(guī)模網(wǎng)絡(luò)的需求。為了更好地部署SDN并滿足大規(guī)模網(wǎng)絡(luò)的需求，在多控制器網(wǎng)絡(luò)拓撲的設(shè)計中，使用分級分域架構(gòu)[18]，如圖1所示。在SDN分級分域架構(gòu)中，部署多個控制器，通過分層控制器處理大量的數(shù)據(jù)。將大規(guī)模網(wǎng)絡(luò)進一步細化為多個區(qū)域，每個區(qū)域由域內(nèi)控制器單獨負責。根控制器負責同步各個域控制器，以便在不同域設(shè)置路由。QoS多個約束條件取決于應(yīng)用本身及隨著時間增長使用該應(yīng)用用戶的平均數(shù)。鏈路時延、帶寬、丟包率等信息都可以通過流量測量工具匯總給域控制器。利用這些信息，每個域控制器上的路由優(yōu)化算法可以為所有多約束QoS生成基于目的節(jié)點可行路由的DAG，結(jié)合所有域控制器生成的DAG，創(chuàng)建全局可行路徑的DAG。多域之間的路由問題簡化為單域路由問題。同時，根控制器可簡化為抽象后網(wǎng)絡(luò)拓撲的域內(nèi)部控制器，根據(jù)相應(yīng)節(jié)點和鏈路信息進行最優(yōu)路徑選擇。

Figure 1 Hierarchical domain architecture of SDN圖1 SDN分級分域架構(gòu)

2.2 多約束 QoS模型

基于文獻[19,20]，為每個網(wǎng)絡(luò)拓撲圖生成一個至少包含一條從源節(jié)點到目的節(jié)點路徑的DAG，且滿足QoS約束條件，用G(N,S)表示。其中，N表示一組節(jié)點的節(jié)點集，可以是路由器、交換機或者子網(wǎng)；S是有向邊集，表示網(wǎng)絡(luò)鏈路[21]。

在QoS約束條件中，丟包率lost為乘性約束，通過對丟包率取對數(shù)的方式，將其轉(zhuǎn)換為加性參數(shù)，即lg(1+lost)。由對數(shù)性質(zhì)可知，當1+lost的值越小時，lg(1+lost)的值也越小。因此，本文的代價設(shè)為丟包率的對數(shù)和鏈路成功交付數(shù)據(jù)流所造成的開銷。為解決從源節(jié)點到目的節(jié)點代價最小且滿足所有約束條件的最優(yōu)路徑問題，建立了基于SDN的多約束QoS模型，如式(1)～式(4)所示。

源節(jié)點到目的節(jié)點的路徑中，最小代價如式(1)所示：

(1)

鏈路時延低于約束界限,如式(2)所示：

s.t.DTxuv≤d

(2)

鏈路抖動低于約束界限，如式(3)所示：

s.t.JTxuv≤j

(3)

約束路徑瓶頸帶寬大于可用帶寬的最小界限,如式(4)所示：

(4)

其中，b∈R+表示網(wǎng)絡(luò)應(yīng)用對帶寬約束的邊界；B=(B1,B2,…,Bi)表示各邊可用帶寬的列向量，Bi是列向量內(nèi)的元素。

2.3 拓撲發(fā)現(xiàn)及信息收集

在網(wǎng)絡(luò)初始階段，控制器需要進行拓撲發(fā)現(xiàn)和信息收集，OpenFlow目前沒有統(tǒng)一規(guī)定拓撲發(fā)現(xiàn)的方法。本文利用傳統(tǒng)網(wǎng)絡(luò)中的鏈路狀態(tài)發(fā)現(xiàn)協(xié)議LLDP (Link Layer Discovery Protocol) 實現(xiàn)網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。

圖2為通過LLDP協(xié)議進行拓撲發(fā)現(xiàn)的過程。首先，控制器以泛洪的形式向網(wǎng)絡(luò)中所有與之相連接的節(jié)點下發(fā)流條目，以請求端口信息。當控制器建立安全傳輸協(xié)議TLS(Transport Layer Security)會話后，向所有與之相連的節(jié)點發(fā)送 Packet-Out 消息包。當一個節(jié)點收到鄰居發(fā)送的LLDP報文后，首先向自己相鄰的節(jié)點發(fā)送LLDP報文，然后以Packet_In消息包的形式向控制器匯報自己和鄰居的情況。當所有節(jié)點都執(zhí)行完以上操作后，控制器便可以獲得網(wǎng)絡(luò)中的所有鏈路信息，完成拓撲發(fā)現(xiàn)。為了實時保障應(yīng)用對多約束QoS的需求，還需要對網(wǎng)絡(luò)狀態(tài)進行監(jiān)測。本文通過使用時間戳計數(shù)器，在節(jié)點之間發(fā)送數(shù)據(jù)流探測，定期輪詢并存儲端口發(fā)送的字節(jié)數(shù)，以此計算帶寬、時延和抖動等網(wǎng)絡(luò)狀態(tài)信息。

Figure 2 Topology discovery process圖2 拓撲發(fā)現(xiàn)過程

3 SDN_MCQDP算法

SDN_MCQDP算法需要生成基于目的節(jié)點的可行路徑DAG，以確保圖中每個節(jié)點均包含至少一條到達目的節(jié)點且滿足多約束QoS需求的可行路徑。因此，算法分為3個階段：生成DAG階段、多約束QoS路由選擇階段和生成雙路徑冗余鏈路階段。生成DAG階段，負責尋找和組合網(wǎng)絡(luò)拓撲中所有節(jié)點到達的目的節(jié)點且滿足所有QoS約束的可行路徑。而尋找每一條滿足約束的可行路徑由多約束QoS路由選擇階段負責。反向鏈路刪減生成雙路徑階段，結(jié)合DAG生成滿足多約束QoS的雙路徑冗余鏈路。

3.1 生成有向無環(huán)圖

在源節(jié)點到目的節(jié)點的路徑中，包含了許多中間節(jié)點到目的節(jié)點的可行路徑。因此，計算源節(jié)點到目的節(jié)點可行路徑的過程中，可能會遍歷網(wǎng)絡(luò)拓撲中的所有節(jié)點。本文通過基于目的節(jié)點可行路徑DAG，即網(wǎng)絡(luò)拓撲中與目的節(jié)點能夠連通的所有節(jié)點，生成到達目的節(jié)點且滿足多約束QoS的可行路徑DAG，來達到減少重復(fù)遍歷的目的。只計算少量節(jié)點可行路徑就可以實現(xiàn)網(wǎng)絡(luò)拓撲中所有節(jié)點可行鏈路的全覆蓋。生成基于目的節(jié)點可行路徑DAG的具體步驟如下所示：

步驟1對網(wǎng)絡(luò)拓撲圖中所有的鏈路進行反轉(zhuǎn)，從目的節(jié)點開始進行廣度優(yōu)先搜索，并將節(jié)點存儲到隊列H中。

步驟2從隊列H中依次讀取節(jié)點，并計算節(jié)點到目的節(jié)點滿足多約束QoS的最優(yōu)路徑。

步驟3按照每個節(jié)點到目的節(jié)點最優(yōu)路徑的跳距遞減存儲，并生成基于目的節(jié)點可行路徑的DAG。如果已經(jīng)遍歷搜索網(wǎng)絡(luò)拓撲中所有節(jié)點，則停止搜索。

假設(shè)從目的節(jié)點開始廣度優(yōu)先搜索所需要遍歷的葉子節(jié)點數(shù)為m，網(wǎng)絡(luò)中所有節(jié)點數(shù)為n，k為QoS約束條件的個數(shù)。生成基于目的節(jié)點的DAG，計算最優(yōu)路徑的時間復(fù)雜度為O(k×m×n)，而使用Dijkstra算法直接計算最優(yōu)路徑的時間復(fù)雜度為O(k×n2)。由此可見，上述方法可以有效降低時間復(fù)雜度，減少路由計算時間，但由于廣度優(yōu)先搜索內(nèi)存耗費量大，會導(dǎo)致鏈路代價小幅度上升。通過上述方法能夠得到所有節(jié)點到目的節(jié)點的可行路徑。源節(jié)點距離目的節(jié)點越遠，則可行路徑包含的中間節(jié)點就越多。合并已經(jīng)搜索到的可行路徑，可以得到一個關(guān)于到達目的節(jié)點可行路徑的DAG。迭代求解最優(yōu)路徑的過程中，如果已遍歷存儲的所有可行路徑則終止算法。所有基于目的節(jié)點的廣度優(yōu)先搜索都可以離線完成，因為鏈路布局不會隨著流量條件的變化而變化。只有當網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生變化時，才需要重新執(zhí)行廣度優(yōu)先搜索。在滿足多約束QoS的條件下，該DAG中的可行路徑也可以用于其他節(jié)點傳輸數(shù)據(jù)流。

圖3為以R8為目的節(jié)點生成DAG的例子，每條鏈路均為雙向傳輸。鏈路上的一對值分別表示時延(ms)和抖動(ms)，令路徑QoS約束的最大值分別為40 ms和10 ms。圖3中的虛線為通過SDN_MCQDP算法計算R1～R8,R2～R8和R3-R8滿足多約束QoS需求的可行路徑，組合這些可行路徑生成DAG。從DAG中可以觀察到，R1～R7中的任一節(jié)點均包含至少一條到達目的節(jié)點R8且滿足多約束QoS需求的路徑。

Figure 3 Generating DAG based on destination node圖3 生成基于目的節(jié)點的DAG

3.2 多約束QoS路由

Dijkstra是經(jīng)典的求解最短路徑算法，但只適用于已滿足約束條件的路徑，因此具有很大的局限性。拉格朗日松弛對偶算法是求解多目標約束優(yōu)化的經(jīng)典算法之一，原函數(shù)約束條件多為NP-hard問題，而拉格朗日松弛對偶算法將多約束條件與目標函數(shù)聚合，使得目標函數(shù)仍保持線性，進而簡化原問題[22 - 24]。本文將Dijkstra和拉格朗日松弛對偶算法結(jié)合起來，以便在更短的時間內(nèi)找到滿足數(shù)據(jù)流約束條件的最優(yōu)傳輸路徑。

在SDN中，對于一條鏈路來說，常見的QoS約束性質(zhì)可分為加性、乘性和凹性，如表1所示?？刂破髟谟嬎阕顑?yōu)路徑前需要對乘性約束和凹性約束分別進行預(yù)處理，對乘性約束取對數(shù)將其轉(zhuǎn)化為加性約束，通過路徑選擇預(yù)處理的方法解決凹性約束，將多約束問題簡化為一個線性規(guī)劃問題。

Table 1 Common QoS constraint properties on links

通過拉格朗日松弛對偶算法將多約束QoS與代價函數(shù)聚合的具體步驟如下所示：

步驟1通過移除不滿足QoS帶寬約束的鏈路進行選路預(yù)處理。首先，應(yīng)用發(fā)出報文轉(zhuǎn)發(fā)的請求，當來自應(yīng)用的第1個流的第1個包請求傳輸時，入口路由器向控制器發(fā)送該流的相關(guān)信息，開始計算該應(yīng)用在一次信息更新時間間隔內(nèi)傳輸流的數(shù)量。將該應(yīng)用的瓶頸帶寬乘以一次信息更新時間內(nèi)流的請求數(shù)量，對鏈路中可用帶寬不滿足計算后帶寬的鏈路進行剪枝處理。通過控制器設(shè)置鏈路的抖動、時延為無窮大并將丟包率設(shè)為1就可以完成剪枝處理。

例如，在線語音(VoIP)傳輸數(shù)據(jù)的瓶頸帶寬為0.19 Mbps，信息更新周期為30 ms。在一次信息更新的時間內(nèi)流的請求數(shù)量為50，控制器需要對可用帶寬小于0.19×50=9.5 Mbps的鏈路進行剪枝。首先計算VoIP數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑，然后將該路徑中所有已激活鏈路的可用帶寬減去9.5 Mbps，最后用剪枝后滿足可用帶寬的鏈路尋找其他數(shù)據(jù)流的最優(yōu)傳輸路徑，這樣能夠盡可能滿足所有應(yīng)用的帶寬需求。

ZL=maxλ∈R+LR(λ)

(5)

其中，λ={λ1,λ2}分別表示約束條件式(2)和式(3)聚合后的拉格朗日乘子，λ1，λ2∈R+。LR(λ)為代價函數(shù)和約束函數(shù)聚合后，在非對偶約束條件下優(yōu)化的拉格朗日松弛對偶函數(shù)，具體如式(6)所示：

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

(6)

當λ1，λ2為常數(shù)時，(λ1d+λ2j)的值也為常數(shù)，為了便于計算，將其舍去，式 (6)化簡式(7)：

(7)

綜上分析，可以將鏈路權(quán)重定義為C,如式(8)所示：

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

(8)

3.3 迭代求解最優(yōu)路徑

梯度下降法[25]是尋找目標函數(shù)最小化值的方法之一。本文利用梯度下降法求解多約束QoS問題得到最優(yōu)路徑。通過分析鏈路權(quán)重C可以發(fā)現(xiàn)，隨著拉格朗日乘子λ逐漸增大，時延、抖動和丟包率在LR(λ)中的占比也會增大，因此可以認為λ是單調(diào)遞增函數(shù)，需要沿負梯度迭代尋找最優(yōu)路徑。

通過梯度下降法迭代求解最優(yōu)路徑的具體步驟如下所示：

步驟1為確定時延和抖動的下降梯度，令時延和抖動的下降梯度為ΔD和ΔJ，對函數(shù)LR(λ)中λ1和λ2分別求偏導(dǎo),如式(9)和式(10)所示：

(9)

(10)

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

步驟2設(shè)時延和抖動的步長為αt和βt，其計算分別如式(11)和式(12)所示：

(11)

(12)

其中，t表示當前迭代計算的次數(shù)，Cmin是不受QoS約束的最小路徑權(quán)重，μt和ξt為確定合適步長而持續(xù)更新的非負常數(shù)。

(13)

(14)

(15)

(16)

生成DAG階段和多約束QoS路由選擇階段的偽代碼如算法1所示。

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

輸入:網(wǎng)絡(luò)拓撲圖G(N,S)，源節(jié)點u，目的節(jié)點v,數(shù)據(jù)傳輸多約束QoS的需求。

輸出:源節(jié)點到目的節(jié)點(u,v)的最優(yōu)路徑。

1V(Maximum number of iterations),t(Number of iterations)；//初始化參數(shù)

2S′=Backward(S);//反轉(zhuǎn)鏈路

3H=BFS(N,S′,v);/*廣度優(yōu)先搜索網(wǎng)絡(luò)拓撲圖中的節(jié)點*/

4M=?;//初始化M，存放從P中出棧的節(jié)點

5G_DAG= {};/*初始化G_DAG，存放u→v的最優(yōu)路徑*/

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)；//生成基于目的節(jié)點的DAG

25endwhile

26return基于目的節(jié)點的有向無環(huán)圖G_DAG

3.4 生成雙路徑冗余鏈路

當控制器下發(fā)的路由出現(xiàn)故障時，需要快速重新計算并下發(fā)路由，但是在此期間，分組數(shù)據(jù)有可能會丟失。傳統(tǒng)的雙路徑路由在計算時，首先檢查并計算源節(jié)點到目的節(jié)點的最短路徑，然后從網(wǎng)絡(luò)拓撲中刪除該路徑后重新搜索最短路徑。假設(shè)存在2條可行路徑，不一定能找到2條不相交的路徑，搜索到的備用路徑的長度可能會比預(yù)期的長許多，不能同時滿足QoS多個約束條件的需求。為解決傳統(tǒng)的雙路徑路由問題，本文在SDN分級分域的架構(gòu)下，控制器利用資源集中管理的特點，根據(jù)每個節(jié)點和鏈路的狀態(tài)信息及多約束QoS的需求，使用反向鏈路刪減生成備份路徑的方法[13]，在源節(jié)點和目的節(jié)點之間尋找2條不相交且滿足多約束QoS的最優(yōu)路徑。當鏈路或節(jié)點發(fā)生故障時，控制器能夠快速切換到備用路徑以保障數(shù)據(jù)正常傳輸，同時在一定程度上能夠減輕網(wǎng)絡(luò)的負載。具體步驟如下所示：

步驟1通過算法1得到基于目的節(jié)點的有向無環(huán)圖G_DAG，在G_DAG中找到滿足多約束QoS需求且成本值最小的第1條路徑P1。如果P1不存在，則查找失敗，算法結(jié)束。否則，轉(zhuǎn)到步驟2。

步驟2將找到的第1條路徑P1中所有的鏈路反轉(zhuǎn)反向，設(shè)置該路徑上所有加性約束為0，DTxuv=0,JTxuv=0,?(u,v)∈P1，并重新生成一個基于目的節(jié)點的有向無環(huán)拓撲網(wǎng)絡(luò)圖G′。

在步驟2中設(shè)置反轉(zhuǎn)鏈路上所有路徑的加性約束為0而不是負值的目的在于避免由負值引起的環(huán)路。

圖4的示例中，尋找R1和R6之間2條不相交且滿足多約束QoS的路徑。在已經(jīng)生成DAG的前提下，每個鏈路上的一對值分別表示時延(ms)和抖動(ms)，并假設(shè)QoS約束的最大值分別為40 ms和10 ms。圖4a～圖4d分別對應(yīng)步驟1～步驟4。在圖4a中計算得到滿足多約束QoS的第1條路徑P1為R1-R4-R6-R5-R8。在圖4b中將P1中所有的鏈路反轉(zhuǎn)，并令加性約束的權(quán)值為0，生成新的有向無環(huán)網(wǎng)絡(luò)拓撲圖G′。圖4c中，在新拓撲圖中計算得到的最優(yōu)路徑P2為R1-R5-R6-R8。將路徑P1和P2求并操作，刪除路徑集中的反向鏈路，即刪除R5-R6。其余鏈路根據(jù)鏈路方向重新組合為最終的2條最優(yōu)路徑，即P′1為R1-R4-R6-R8，P′2為R1-R5-R8，如圖4d所示。

Figure 4 Multi constrained QoS dual path routing圖4 多約束QoS雙路徑路由

雙路徑冗余鏈路的反向鏈路刪減算法如算法2所示。

算法2反向鏈路刪減算法

輸入:基于目的節(jié)點的有向無環(huán)圖G_DAG,源節(jié)點u，目的節(jié)點v，數(shù)據(jù)傳輸多約束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/*反轉(zhuǎn)P1中所有鏈路，并令鏈路權(quán)值為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 仿真實驗及結(jié)果分析

通過對不同的網(wǎng)絡(luò)數(shù)據(jù)流進行測試[26]，網(wǎng)絡(luò)中超過80%的數(shù)據(jù)流持續(xù)時間不超過10 s，僅有低于0.1%的數(shù)據(jù)流持續(xù)時長超過200 s，數(shù)據(jù)流中超過50%的字節(jié)持續(xù)時間低于25 s。本文設(shè)置控制器每25 s更新一次網(wǎng)絡(luò)狀態(tài)，并且向節(jié)點下發(fā)新的流表。

為精確評估算法的性能，本文在VMware上使用網(wǎng)絡(luò)仿真工具Mininet構(gòu)建網(wǎng)絡(luò)拓撲，用Ryu作為控制器設(shè)備實現(xiàn)功能模塊，用Iperf流生成工具模擬真實網(wǎng)絡(luò)流量。仿真拓撲圖使用Internet Topology Zoo dataset[27]的8個真實網(wǎng)絡(luò)拓撲案例，其中ATT North America拓撲中共25個節(jié)點，57條鏈路；BT Europe拓撲中共24個節(jié)點，27條鏈路；BT North American拓撲共36個節(jié)點，17條鏈路；Interroute拓撲共27個節(jié)點，36條鏈路；Colt拓撲共153個節(jié)點，191條鏈路；TaTa拓撲共145個節(jié)點，194條鏈路；Cogent拓撲共197個節(jié)點，245條鏈路；Global Center拓撲共9個節(jié)點，36條鏈路。通過對不同網(wǎng)絡(luò)拓撲類型的路由計算時間、鏈路利用率和QoS流滿意度，驗證SDN_MCQDP算法性能，與基于SDN架構(gòu)的QT(Quality of service-Technology of network resource allocation)[2]、MODLARAC(MODified LAgrange Relaxation based Aggregated Cost)算法[12]和基于傳統(tǒng)網(wǎng)絡(luò)架構(gòu)的RMCDP_RD(Reliable Multi-Constrained Dual-Path Reverse Deletion)[13]、H_MCOP(Heuristic for Multi-Constrained Optimal Path)算法[28]進行仿真對比實驗。

4.1 路由計算時間

路由計算時間包括：生成DAG的時間，控制器向計算DAG中生成雙路徑冗余鏈路的時間和下發(fā)流表的時間，以及源節(jié)點傳輸數(shù)據(jù)流到達目的節(jié)點的時間總和。將SDN_MCQDP與MODLARAC、QT、RMCDP_RD、H_MCOP算法進行比較，在不同拓撲圖下的路由計算時間如圖5所示。

Figure 5 Routing calculation time圖5 路由計算時間

如圖5所示，Global Center為全連接網(wǎng)絡(luò)，盡管節(jié)點個數(shù)較少，但是H_MCOP在多約束QoS最優(yōu)路徑選擇中存在產(chǎn)生累積誤差、搜索范圍不全面等缺點，因此路由計算時間最長。SDN_MCQDP算法在基于SDN架構(gòu)的全局網(wǎng)絡(luò)視圖中，利用廣度優(yōu)先搜索降低了算法的時間復(fù)雜度，并通過生成基于目的節(jié)點的DAG，避免了節(jié)點的重復(fù)調(diào)用，有效降低了路由計算時間。針對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存在無法返回最優(yōu)路徑和計算最優(yōu)路徑存在誤差的情況，因此鏈路利用率較低。SDN_MCQDP通過對無用帶寬鏈路做剪枝處理，減少了可用帶寬的資源浪費，并且雙路徑路由在一定程度上能夠減輕鏈路負載，因此，在滿足網(wǎng)絡(luò)應(yīng)用帶寬需求的同時，有效提高了鏈路利用率。

Figure 6 Comparison of link utilization圖6 鏈路利用率比較

4.3 QoS流滿意度

針對不同網(wǎng)絡(luò)應(yīng)用的QoS需求，7種常見的真實網(wǎng)絡(luò)應(yīng)用的QoS需求如表2所示。本文依據(jù)表2對QoS流滿意度進行測試。

Table 2 QoS requirements of different applications

在不計入設(shè)備故障時，使用SDN_MCQDP滿足QoS需求流的百分比的實驗結(jié)果如圖7所示。從圖7可以看出，不同網(wǎng)絡(luò)應(yīng)用需求的QoS流滿意度在95%～100%。SDN_MCQDP算法綜合考慮了時延、抖動、帶寬和丟包率等4種QoS約束條件，在滿足全部約束條件的情況下尋找最優(yōu)路徑，能夠滿足大部分網(wǎng)絡(luò)應(yīng)用的流的滿意度。

Figure 7 QoS satisfaction of different applications圖7 不同應(yīng)用下流的QoS滿意度

鏈路發(fā)生故障時使用SDN_MCQDP滿足QoS流需求的百分比的實驗結(jié)果如圖8所示。從圖8可以看出，當鏈路發(fā)生故障的數(shù)量分別為2，4，6和8時，大部分網(wǎng)絡(luò)應(yīng)用仍能滿足其QoS需求，因為SDN_MCQDP利用反向鏈路刪減算法得到2條不相交且滿足多約束QoS的最優(yōu)路徑，控制器能夠快速響應(yīng)并下發(fā)備用路徑。

Figure 8 Satisfaction of QoS flow after link failure圖8 鏈路故障后QoS流的滿意度

4.4 平均代價

SDN_MCQDP與MODLARAC、QT、RMCDP_RD和H_MCOP算法的鏈路平均代價如圖9所示。假設(shè)存在最優(yōu)路徑，H_MCOP能夠在滿足所有約束條件的情況下搜索最優(yōu)路徑，但是存在無法返回最優(yōu)路徑的隱患。SDN_MCQDP不存在這種情況，本文算法需要控制器根據(jù)網(wǎng)絡(luò)規(guī)模發(fā)送大量數(shù)據(jù)流，生成基于目的節(jié)點的DAG，提高鏈路開銷來降低算法的時間復(fù)雜度，導(dǎo)致平均代價消耗大。如果供應(yīng)商需要在多約束QoS條件下快速選擇數(shù)據(jù)轉(zhuǎn)發(fā)的最優(yōu)路徑，但不介意鏈路平均代價的小幅提升，SDN_MCQDP是最優(yōu)的選擇。

Figure 9 Average cost圖9 平均代價

4.5 時延相對差異百分比

根據(jù)(時延約束-路徑時延)/時延約束*100%計算鏈路中時延的相對差異百分比，在不同網(wǎng)絡(luò)規(guī)模下對比SDN_MCQDP與MODLARAC、QT、RMCDP_RD 算法在時延方面的性能，結(jié)果如圖10所示。 H_MCOP算法存在無法返回最優(yōu)路徑的情況，因此在該性能測試中無法對其進行對比。

Figure 10 Percentage of relative delay difference 圖10 時延相對差異百分比

從圖10可以看出，SDN_MCQDP算法的時延相對差異百分比相較于MODLARAC、RMCDP_RD和QT算法的分別提高了4.9%，2.4%和1.1%。MODLARAC的時延相對百分比最低，因為該算法不會直接返回最優(yōu)路徑，仍需進一步計算以免遺漏滿足多約束QoS的最優(yōu)路徑。SDN_MCQDP算法在生成基于目的節(jié)點DAG的過程中，已經(jīng)計算出中間節(jié)點到目的節(jié)點的所有可行路徑，減少了節(jié)點的重復(fù)調(diào)用，降低了鏈路時延。

5 結(jié)束語

針對SDN架構(gòu)下多約束QoS路由算法復(fù)雜度高、鏈路故障后數(shù)據(jù)傳輸無法保障等問題，設(shè)計并實現(xiàn)了一種基于SDN的多約束QoS雙路徑路由優(yōu)化算法SDN_MCQDP。通過拉格朗日松弛對偶算法將多種約束性能指標整合到代價函數(shù)；生成基于目的節(jié)點DAG的方法，來降低算法復(fù)雜度并減少路由計算時間；利用多約束雙路徑反向刪減算法得到2條不相交的最優(yōu)路徑，保障數(shù)據(jù)在鏈路或節(jié)點發(fā)生故障時正常傳輸。仿真結(jié)果表明，SDN_MCQDP能夠有效降低路由計算時間，提升鏈路利用率，且適應(yīng)多種網(wǎng)絡(luò)拓撲類型，滿足大部分網(wǎng)絡(luò)應(yīng)用的QoS需求。SDN_MCQDP雖然在仿真中有較好的表現(xiàn)，但是目前僅考慮SDN架構(gòu)下的網(wǎng)絡(luò)，在實際應(yīng)用中，由于相關(guān)設(shè)備價格昂貴，商業(yè)化并未完全普及，因此，下一步將考慮混合網(wǎng)絡(luò)的使用情況，并進一步優(yōu)化算法以降低平均代價。