SDN架構下的鏈路分離路徑算法的研究

池亞平 高 聰 陳 穎 范曉紅

1(北京電子科技學院通信工程系 北京 100070)2(西安電子科技大學通信工程學院 陜西 西安 710071)3(中國科學院信息工程研究所網絡測評技術重點實驗室 北京 100093)

0 引 言

近些年，隨著互聯網規模的不斷擴大，互聯網用戶數量呈現巨大的增長。人們對互聯網的需求越來越多，對網絡的質量要求也日益增高，所以人們要求網絡的傳輸能夠更加可靠。傳統網絡具有非常分散的控制機制，特定的路由協議和算法在每個獨立的節點上運行。在現如今網絡設備多種多樣的現實網絡中，這種分布式網絡架構，使得網絡管理和監控成為一項艱巨的任務。SDN的出現給復雜的網絡管理者們帶來了曙光。SDN擺脫了硬件對于網絡的限制，使網絡可編程化，通過軟件可以對網絡進行管理和修改。

SDN是一個具有三層架構的新型網絡架構(如圖1所示)，包括數據層、控制層、應用層。其中控制層是SDN的一個核心層，在控制層實現路徑的計算。在SDN架構中，控制層與數據層分離，對網絡的控制集中在可編程控制器中。數據層與控制層分離的靈活架構，使QoS傳輸和流量工程可以集中式處理網絡的拓撲信息，網絡可以高效地運行。傳統網絡的體系結構是過于靜態、不夠靈活，無法獲得網絡全局拓撲信息。SDN中網絡設備的流量可以由軟件集中動態控制，可以確保網絡資源的優化分配，避免擁塞。SDN的一個重要的特點是可以獲取到網絡拓撲的全局信息，SDN的出現使得流量工程有了更進一步的發展。該網絡架構通過使用新型網絡協議(如OpenFlow[1])降低傳統網絡設備獲取網絡資源信息的通信開銷，降低對網絡資源的占用。SDN另一個重要的特點是能夠靈活地控制網絡流量，使用不同的路由算法來改變網絡的傳輸路徑。路由算法僅運行在控制器中，SDN通過對路由設備的集中控制，提供更加精確的路徑，獲得更小的延遲、更加高質量的路徑。

圖1 SDN架構圖

SDN網絡的出現，使現有網絡有了集中控制的思想，對傳統網絡中的路由算法有了較大的影響。由于SDN的創新特性的出現，不得不對傳統的路由算法進行重新研究。本文對多路徑算法進行了改進及應用，多路徑算法對流量工程也具有很大幫助。流量工程用于優化網絡流量的控制和監控，有助于滿足特定的服務質量并提供高效的網絡資源利用率。傳統的流量工程增加網絡的通信開銷，并且復雜的算法對有限的計算資源來說是一個巨大的挑戰，SDN的出現有效應對了流量工程的這一挑戰。

多路徑路由算法能夠計算出網絡中多條可行路徑，可以應用到流量工程中，啟用多路徑，便于分流，從而利用現有利用率比較低的路徑，有利于網絡流量在不同鏈路上進行均衡。當前在多路徑算法中，對于鏈路分離路徑算法的應用研究很少。鏈路分離路徑可以增加數據的可靠傳遞，為尋路失敗提供彈性，縮減網絡的擁堵，有助于在網絡中提供高速率的數據傳輸和負載均衡。對于在QoS需求較高的網絡中，SDN具有較高的優勢。通過為不同的流量提供多個鏈路分離路徑，從而有效地優化網絡資源的利用，即實現接納控制、流量分類和負載均衡等，還能夠增強路徑的可靠性。對于流量感知網絡，解決接入控制和多路徑的失敗等問題需要耗費很多時間，這些工作的耗時不僅體現在網絡的核心設備或路由器的接入時間，更體現在路徑的計算上。

SDN通過使用OpenFlow協議能夠細粒度地對流量進行調控，使得網絡可以更加精確地對流量進行控制。現有的許多算法僅僅是增強鏈路的約束條件，或者是在SDN中應用十分復雜的算法來取得更優的鏈路。本文將SDN的靈活特性、細粒度控制特性與鏈路分離路徑相結合，利用二者的特點，為網絡提供多條可靠路徑，從而提高網絡的魯棒性，并且可以使用多分離路徑進行負載均衡。由于使用了分離路徑算法，更能提高網絡的利用率。

1 研究現狀

SDN使網絡軟件化、扁平化。在SDN中，關于路由算法的研究有很多。一方面，有些研究人員使用簡單的路由算法，如最短路徑優先算法和帶寬最寬的路徑算法來優化SDN網絡中的路由問題。文獻[2]使用帶寬最寬的路徑來查找數據中心的交換機和服務器之間路徑，帶寬最寬的路徑搜索算法會對帶寬資源造成過度的浪費，過度消耗網絡帶寬還能造成網絡擁堵。文獻[3]在Floodlight控制器中使用廣度優先搜索算法代替了最短路徑優先算法。在這些文獻中，研究人員沒有使用SDN的特性來對算法進行優化。另一方面，SDN中大部分的路由算法的研究主要集中在復雜的路由算法上，這些算法的主要目標就是滿足服務需求的QoS約束，約束越多算法越復雜。文獻[4-5]使用復雜的算法來優化多媒體和視頻流量通信，從而提高網絡服務的通信質量。同樣的，文獻[6]使用多約束最短路徑來增強視頻流的服務。SDN架構下的流量調度算法是當下研究的熱點，文獻[7-8]在混合SDN架構下對網絡進行建模，研究使用貪婪策略對SDN交換機進行增量部署，計算出混合SDN網絡中合理的SDN交換機配置數量比例。文獻[9]研究了在SDN網絡中，快速計算出帶寬受限的路徑。在傳統的算法中，最小跳數算法MHA(Minimum-hopalgorithm)是使用比較廣泛的算法，它可以在滿足帶寬需求的路徑中選擇鏈路跳數最少的一個路徑。該算法維護每條鏈路上的可用帶寬信息，只有那些有足夠資源且滿足用戶需求的路由才會被考慮進路由中。MHA法非常簡單，但是很快就會造成網絡的瓶頸鏈路，導致資源利用率低下。文獻[9]中提及的最短最寬路徑SWP(Shortest Widest Path)和最寬最短路徑WSP(Widest Shortest Path)算法都是MHA的增強的算法。其中WSP算法在最短可行路徑集合中，選擇具有最高可用帶寬的路徑即最寬路徑，在負載均衡和資源消耗兩個沖突的需求之間權衡。

上述算法最終都是考慮一條路徑作為最佳傳輸路徑，多路徑算法在流量工程領域有很多優勢。等價路由ECMP[10](Equal Cost Multipath Routing)就是多路徑算法一個很好的應用，可以同時使用多條路徑進行傳輸，增加了網絡的傳輸帶寬。Yen算法和MPS算法是都是多路徑算法，屬于K最短路徑算法，可找出前K條最短路徑。其中Yen算法在流量工程中有應用。以上的多路徑算法在是尋找到多條發生重疊的路徑，如果在公共鏈路上出現了故障，對兩點之間的連通性有很大影響。文獻[11]提出了最大K條不相交路徑算法來實現路由。該算法未找到最短的一對不相交路徑，并且沒有使用SDN能夠細粒度控制流量的特性來改進算法。

在通信的源節點和目的節點之間尋找多條分離路徑，可以將多條路徑互相當做主備路徑，在一條路徑失效時，將流量切換到其他路徑上，以提高網絡的可靠性，還有利于網絡流量工程、負載均衡和擁塞避免的發生。關于分離路徑算法，RF(Remove-Find)方法是在一對源節點和目的節點之間建立兩條鏈路分離路徑的一種簡單方法。這種方法簡單但是有以下缺點：1) 在網絡中刪除源節點和目的節點之間的鏈路，會導致剩余網絡拓撲圖不連通，從而導致求解不出更多的路徑。2) 即使求出第二條路徑，第二條路徑過長，或者僅僅是問題的可行解而不是最優解。Suurballe提出通過路徑增益方法，并使用最短路徑方法構建以總長度最小為目標，尋找出兩條節點分離路徑。之后Suurballe和Tarjan對算法進行了改進。Bhandari通過在原始的Dijkstra算法基礎上，提出在有向圖中求取路徑的鏈路分離路徑算法。以上提到的多數算法都是對原有算法的條件進行改進和增強，沒有利用到SDN能夠細粒度控制流量的新特性。為了獲得更好的路由性能，文獻[12-13]已經開始嘗試利用SDN架構的優勢，但是沒有考慮到分離路徑算法的優勢。

本文借鑒了Bhandari算法的優勢，將其與SDN相結合，利用了SDN的靈活特性，為網絡傳輸提供多個路徑，增加數據的可靠傳遞，為尋路失敗提供彈性，縮減網絡的擁堵，有助于在新型網絡中提供高速率的數據傳輸和負載均衡。

2 OpenFlow

OpenFlow協議可以實現SDN，基于OpenFlow使得網絡可編程，從而進一步推出了SDN的概念。OpenFlow支持基于流量的路由決策，OpenFlow交換機根據控制器發出的指令區分流量進行處理，一個流可以被廣泛地定義為具有相似特征的一系列分組。控制器可以根據圖2中的9個二層網絡到四層網絡之間的分組報文頭字段以及該分組到達接口的標識符來定義一個網絡流量。這種控制選項可以實現高精度控制的動態多路徑路由，顯著增加網絡容量。

圖2 OpenFlow報頭字段

使用OpenFlow接口的統計特性來計算的最佳路徑，可以使用基于OpenFlow協議的OpenMT[14]和OpenNetMon[15]等高效的開源軟件提取路由算法所需要的信息。其中OpenMT是一種用于OpenFlow網絡的流量矩陣估計系統，OpenMT使用OpenFlow交換機中提供的內置功能，既降低了開銷，又準確地測量了流量矩陣。OpenMT使用從OpenFlow控制器中學到的路由來智能地獲取流量統計信息。OpenNetMon也是一種開源的軟件，用于監控OpenFlow網絡中的每個流量指標，特別是吞吐量、延遲和數據包丟失。在OpenFlow提供接口來實現細粒度的流量工程的情況下，OpenNetMon提供必要的監視來確定是否實際滿足端到端QoS參數，并為TE方法提供輸入來計算適當的路徑。

OpenFlow協議為數據層和控制層之間提供網絡連接，為控制層提供全局的網絡視圖。當網絡連接發生任何變化時，OpenFlow交換機會向控制層發送一個端口狀態消息來更新這個變化。另外，OpenFlow交換機有各個端口、各個流和各個隊列的流量計數器。這些計數器使用兩種類型的消息來維護控制器數據庫的網絡狀態。流量越大，消息越頻繁。Read-State消息由控制器發送，用于手機交換機統計信息。消息包含每個交換機的流量持續時間和字節數，從而識別每個鏈路的網路吞吐量。

算法的實現需要從OpenFlow協議中提取出有效的QoS信息來進行計算。此外，還可以根據OpenFlow報頭的不同識別流量的類型、源端口和目的端口等有效信息。

3 算法介紹

SDN控制層的一個主要功能是路徑的計算，對于求解分離路徑來說，就是找出從源點到目的節點之間一組鏈路利用率低的鏈路。在給定的源節點和目的節點之間計算出一對分離路徑，將第一可用路徑視為主路徑，第二可用路徑視為恢復路徑，其他可用路徑進行負載均衡。在主要路徑故障發生時，將路徑上的流量迅速切換至備用路徑，這種方法可以有效地提高網絡的可靠性和QoS保障。多路徑算法能夠更好地提供網絡生存能力和恢復能力，非常有利于流量工程、負載均衡和擁塞避免等情況。

3.1 網絡模型及假設

有關算法的實現，從關鍵的假設開始介紹，然后建立模型解決分離路徑問題。假設網絡的初始狀態是具有非負性QoS鏈路權重的網絡，其中QoS權重可以使用加性的，也可以是凸性或凹性的。加性約束有時延、抖動等；凸性或凹性的約束有如帶寬、策略標志等。使用修改后的Dijkstra算法之后，網絡中的鏈路將被置為相反方向或者QoS將被賦予負值。如圖3所示，邊AC在執行完一次算法之后將被置于反向，并將權QoS權重值設置為負值。

圖3 修改的Dijkstra算法演示拓撲

將網絡抽象為加權無向圖，記為G(V,E)。網絡中的路由設備和通信鏈路分別用圖3中的節點和邊表示。V表示節點的集合，E表示G(V,E)中邊的集合。(u，v)表示從節點u到節點v的一條邊。G中每條邊(u，v)都具有特定的帶寬。

用s和t分別代表通信的源和目的節點，P為從s到t的一條路徑，用E(P)={(u,v)|(u,v)∈P}代表路徑P上的邊的集合，給出如下定義：

定義1假設路徑P1和路徑P2是網絡G(V,E)中的兩條路徑，若E(P1)∩E(P2)=φ，則P1和P2為鏈路分離路徑。

從OpenFlow統計的信息中提取出網絡中各鏈路的QoS信息，QoS信息可以從上文中介紹的開源軟件中提取，該軟件使用上文中所述的細粒度OpenFlow統計量。在多路徑算法運行之前，先對網絡拓撲進行處理。首先對QoS信息做處理，由于QoS權重可以是加性的也可是凸性或凹性的，對于凸性和凹性信息(如帶寬和策略標志)使用OpenFlow統計的流量類型和數據，根據不同種類的流量給出QoS值。如果是對帶寬需求較高的流量請求，我們可以將剩余帶寬值較低的鏈路進行刪除，保留合理的鏈路。對于加性QoS參數，例如延時和抖動，根據網絡的特征來尋找更加合理的路徑，而不是一味地尋求最短路徑，容易造成網絡擁堵，并產生資源的浪費。本文給出鏈路QoS信息的參考值，假設buv是流量的最低需求的帶寬，duv表示鏈路延遲，puv表示丟包率，對低于有效帶寬buv的鏈路進行刪除，用Cuv來表示在(u,v)邊上消耗的費用，將QoSuv定義為：

QoSuv=aduv+βpuv?(u,v)∈E

3.2 改進的Dijkstra

Dijkstra算法適用于QoS路由，并在實際中網絡中，具有可擴展性的優勢，它被互聯網路由的逐跳協議所使用。大型網絡和SDN控制網絡是可擴展的，使用改進的Dijkstra算法有助于減少源到目的路由的最壞計算時間。Dijkstra算法用一種貪婪的方法來計算源、目的地對之間或從源到任何其他目的地之間的最短路徑。

對于傳統的Dijkstra算法，不能直接應用到權值為負的拓撲中。Bhandari改進的算法之中，路徑中存在負的邊，必須保證已經標記的節點再次被評估，這就意味著任何已經被評估的節點在下一次計算中也要被再次評估。這對存在負弧的網絡拓撲構造鏈路分離路徑特別有效。

當拓撲存在權值為負的邊時候，原始Dijkstra算法會失效，如圖3所示。利用原始Dijkstra算法，求得的路徑為P1=ABZ，權重大小為13，此路徑并非最短路徑，利用改進的Dijkstra算法之后，可以得到最短路徑為P2=ADECBZ，權重大小為12，P2權重小于P1，是權重最小的鏈路。

3.3 鏈路分離路徑算法

使用OpenFlow協議從網絡中獲取QoS信息作為算法的輸入。最后輸出需要的k條分離路徑。鏈路分離路徑算法的偽代碼如下：

Input:(Graph G(V, E), QoS and Request R(s,d,k))

Output: kMDP

1 Run(MDA_Path_Pi);

2 E(Pir) <-E(Pi)

教師也可以根據學生回答問題的情況進行追問，追問的問題可以是學生以往的典型錯誤，可以是問題的進一步拓展，也可以是知識之間的聯系和運用。在不斷的設問和追問中，師生和生生不斷產生思維碰撞。

3 K<-1,2,…,k;

4 Update Path;

5 while(negative_BMDA_Path_(Pi)=true) do

6 G<-G′;

7 Run(MDA_Path_Pi);

8 If (MDA_Path_Pi over) do

9 return kMDP;

10 else if(E(Pir)∩E(Pi)=?) do

11 E(Pir)<-E(Pi)

12 Update Path;

13 else

14 E(Pir)<-{E(Pi)-E(Pir)∩E(Pi)}

15 Update Path;

16 end if

17 then if(Path < k) do

18 go to step 5;

19 else

20 Return kMDP;

21 end if

22 end if

在上述偽代碼中，當第一次尋找路徑時，在沒有負邊的情況下，算法第1行是按照最短路徑算法來尋路的。第5～6行改變了原始的拓撲圖，第7行在改變后的拓撲中尋找新的最短路徑。第9～15行是將計算出的最短路徑所在的邊重新組合成最短路徑。

3.4 算例分析

圖4是使其運行改進后的Dijkstra算法演示。由于第一次運行，拓撲中沒有負邊緣的存在，嚴格按照Dijkstra算法來運行，計算出路徑為P1=ABCZ。之后改變路徑的方向為反向，將成本大小改變為負值，此時已經計算出的路徑的鏈路成本改為-QoS，再次運行改進的Dijkstra算法，得到路徑P2=ADCEZ。如果得到的路徑與已知路徑發生重疊，則刪除兩條鏈路的并集，剩余的鏈路組成分離路徑。在計算出P2之后再次修改拓撲，將兩條路徑的方向取反，鏈路成本改為負值，得到圖4中帶有負權值的網絡拓撲。在新的拓撲中使用改進的Dijkstra算法找到從A到Z的最短路徑P3=AFECBHZ，再刪除與之前求得的鏈路的并集，得到三條鏈路分離路徑。重復上述步驟直到路徑計算結束或已達到路徑數量請求。

圖4 相交路徑算法演示

算法的主要流程就是在修改后的拓撲上求出最短路徑，將計算出的最短路徑和此前的最短分離路徑作比較，刪除重疊的邊，將剩余的邊組合成最短的鏈路分離路徑。上述例子中路徑P3=AFECBHZ遍歷P2、P3的EC和BC兩條邊，刪除EC和BC之后我們會得到三條鏈路分離的路徑(AFEZ,ADCZ,ABHZ)，權重的總和為15，即三條鏈路權重之和。

如果FE權值變為5，在第二次轉變后的拓撲中最短路徑P3=AFDBHZ，三條分離路徑即變成ABCZ、ADCEZ和AFDBHZ，他們的總長度為3+4+10=17。

4 仿 真

分別使用擁有20個節點的網絡和40個節點的網絡的拓撲，對于n個點之間我們建立n(n-1)條邊的完全拓撲，并在拓撲中求解不同數量的路徑個數，并統計算法的執行時間。如圖5所示，算法在較短時間內可以求得所需要的路徑數量。

圖5 求解路徑的平均計時間

仿真網絡采用具有14個節點21條鏈路的NSFNET骨干網絡進行實驗仿真。如圖6所示，使用延遲作為實驗仿真的QoS值，對每個滿足帶寬需求的鏈路上設置不同的延時。在圖中使用1節點為源節點，13節點為目的節點，使用SDN控制器獲取分離鏈路。設置各個鏈路帶寬1 Gbit/s，鏈路帶寬滿足網絡鏈路的傳輸質量需求。當鏈路數量為1時，算法就是最短路徑算法，所以求得的路徑數目k須大于1，才能體現算法的特點，所以我們取k=2為例，實現仿真。

圖6 NSFNET網絡

使用Mininet[16]模擬骨干網絡，使用Pox控制器進行控制。建立數據平面的方法有三種：1) Hop-by-Hop方式，即交換機之間的數據面直接進行物理連接的方式。2) 覆蓋方式，即采用IP通道的等技術構建用于數面的覆蓋網絡。3) 混合方式，即上述兩種方式的組合稱為混合方式。本文采用Hop-by-Hop方式組建數據平面，其優點是OpenFlow交換機的數據平面直接互相連接，與其他覆蓋方式相比，具有能夠高速處理，判斷何處出現故障時的考慮因素較少等優點。

利用網絡中的延遲作為仿真的參考QoS，求出合適路徑，計算出QoS最低的兩條分離路徑。在每條鏈路上取不同的延時參數，分別計算路徑作對比。其中：MHA算法得到的延時較高；使用Yen算法得到兩個鏈路的平均延時較高，求出的路徑條數較多；Dijkstra算法得到最優路徑；Path1和Path2是使用本文的算法求出的兩條分離路徑。由此可見，本文的算法比Yen算法更加有優勢，在延時相對接近的情況下，本文的算法能夠得到鏈路分離路徑，而Yen算法得到的是一組發生重疊的路徑。

如圖7所示，多路徑分離算法也可以取得良好的通信鏈路，但是路徑分離算法使用到了更多的鏈路，計算出兩條分離路徑，可以提供更好的負載均衡，大大提高了鏈路的魯棒性。

圖7 不同算法之間延遲的比較

5 結 語

鏈路分離路徑算法可以計算出多條沒有共用鏈路的路徑，將其與SDN的靈活性和細粒度控制特性相結合，可以為不同服務質量的流量請求提供不同的路徑，也可以為同一類型的服務提供多條路徑以供選擇。根據網絡的擁擠程度調整路徑的使用，提供網絡傳輸質量的同時，還能夠提高網絡利用率。鏈路分離路徑能夠提高網絡的可靠性，為尋路失敗提供韌性，縮減網絡的擁堵，在網絡中為高速率的數據傳輸提供很大的幫助，實現網絡的負載均衡。