黃偉，路冉，劉存才，祁思博

基于SDN分級分域架構(gòu)的QoS約束路由算法

黃偉，路冉，劉存才，祁思博

（中國電子科技集團公司第五十四研究所，河北 石家莊 050081）

傳統(tǒng)分布式的網(wǎng)絡(luò)架構(gòu)制約路由算法的創(chuàng)新，軟件定義網(wǎng)絡(luò)的出現(xiàn)為路由算法的優(yōu)化提供了新思路。已有研究中，啟發(fā)式算法廣泛應(yīng)用于服務(wù)質(zhì)量路由，但由于計算復(fù)雜度高而無法在大型網(wǎng)絡(luò)中應(yīng)用。而其他算法均存在不同程度的問題，要么復(fù)雜度較高，要么算法性能較差，如最短路徑算法?；赟DN分級分域架構(gòu)，提出了LC-LD路由算法，綜合時延條件和代價度量約束并在計算復(fù)雜度和算法性能之間保持平衡。仿真分析表明，LC-LD路由算法在有較低的計算復(fù)雜度的同時還有較高的服務(wù)質(zhì)量路由選路性能。

軟件定義網(wǎng)絡(luò)；分級分域；服務(wù)質(zhì)量；路由算法

1 引言

1.1 軟件定義網(wǎng)絡(luò)

路由算法的創(chuàng)新與發(fā)展緩慢的根源在于傳統(tǒng)分布式網(wǎng)絡(luò)架構(gòu)中的諸多缺點與限制，其中包括：所有網(wǎng)絡(luò)節(jié)點都是等價的，每個節(jié)點僅能獲取自身及周圍有限的信息；分布式網(wǎng)絡(luò)架構(gòu)由于節(jié)點對等，因此很難獲取全局實時網(wǎng)絡(luò)信息，而尋找最短路徑的Dijskra算法需要全局網(wǎng)絡(luò)的拓撲信息，必須使用分布式算法；分布式算法的結(jié)果一般只是局部最優(yōu)解，很難判斷是否為最優(yōu)路徑。大多數(shù)傳統(tǒng)網(wǎng)絡(luò)的路由算法主要以距離（跳數(shù)）或時延為參量規(guī)劃最優(yōu)路徑，優(yōu)化的目標以最短路徑為主。但由于某些算法以及分布式網(wǎng)絡(luò)架構(gòu)的特性，算法結(jié)果往往比較簡單，沒有考慮鏈路狀態(tài)參數(shù)的實時性，存在局部鏈路擁塞、整體鏈路利用率較低等比較嚴重的問題，難以發(fā)現(xiàn)諸多隱藏的錯誤[1]。例如，距離向量路由算法中存在的無窮計數(shù)問題[2]、鏈路狀態(tài)路由算法由于復(fù)雜度較高而導(dǎo)致大規(guī)模網(wǎng)絡(luò)中路由器的內(nèi)存和CPU的消耗問題[3]。盡管學(xué)術(shù)界提出許多算法來解決上述問題，但大部分僅停留在研究階段，難以應(yīng)用到產(chǎn)業(yè)界中。一部分原因是傳統(tǒng)網(wǎng)絡(luò)設(shè)備中的路由協(xié)議固化，迭代更新比較困難；另外，新設(shè)計的協(xié)議還存在某些問題，與某些現(xiàn)有網(wǎng)絡(luò)設(shè)備不兼容，兼容性與擴展性較差。

與傳統(tǒng)網(wǎng)絡(luò)的分布式策略不同，SDN通過提取網(wǎng)絡(luò)設(shè)備中的控制平面到一個邏輯上的集中控制端，實現(xiàn)了數(shù)據(jù)平面和控制平面的分離[4]，即數(shù)據(jù)平面的網(wǎng)絡(luò)交換設(shè)備不掌握任何網(wǎng)絡(luò)信息，只根據(jù)控制器下達的指令工作；控制平面的邏輯控制器運行著管理網(wǎng)絡(luò)的程序，擁有全部的網(wǎng)絡(luò)信息，與各個交換機通過控制鏈路直接或間接交換信息，并根據(jù)預(yù)先設(shè)定的協(xié)議控制交換機中的流表項[5]?，F(xiàn)有的基于OpenFlow協(xié)議[6]的SDN使用控制器下發(fā)轉(zhuǎn)發(fā)規(guī)則，每個規(guī)則包含一個字段的匹配，匹配包的動作包括丟棄、轉(zhuǎn)發(fā)、上送到控制器、優(yōu)先級和超時。通過抽象的網(wǎng)絡(luò)動作來定義數(shù)據(jù)分組行為模式，大大提高了網(wǎng)絡(luò)的靈活性和擴展性[7]，并且能夠更加便捷地對網(wǎng)絡(luò)進行管理。在集中式控制的新型網(wǎng)絡(luò)架構(gòu)下，傳統(tǒng)網(wǎng)絡(luò)中一些路由協(xié)議存在的問題得到了解決。例如，SDN集中式的控制器可實時獲取網(wǎng)絡(luò)內(nèi)所有節(jié)點的信息，形成宏觀的全局視圖，更容易運行優(yōu)化算法，部署相應(yīng)的路由策略；路由協(xié)議部署在SDN控制器[8-9]中，可方便地對路由算法進行迭代更新[10]，大大提高了網(wǎng)絡(luò)的靈活性。

1.2 SDN分級分域架構(gòu)

由于目前SDN主要以試驗性的網(wǎng)絡(luò)為主，因此其控制平面多為單控制器，僅負責(zé)小規(guī)模的試驗性網(wǎng)絡(luò)。對于大規(guī)模網(wǎng)絡(luò)部署來說，單控制器的性能和可靠性等指標難以滿足要求。此外，根據(jù)不同網(wǎng)絡(luò)場景之間的差異，其需求有很大不同。因此為了適應(yīng)SDN未來的發(fā)展與演進，需要大規(guī)模網(wǎng)絡(luò)再細化為一些子區(qū)域，每個區(qū)域由區(qū)域內(nèi)的單控制器單獨負責(zé)。為了更好地部署SDN并滿足大規(guī)模網(wǎng)絡(luò)的需求，學(xué)術(shù)界提出了SDN分級分域架構(gòu)[11]。在SDN分級分域架構(gòu)中，網(wǎng)絡(luò)由多個子區(qū)域構(gòu)成，每個子區(qū)域總負責(zé)的控制平面稱為DCP（domain control plane)，DCP可以由單個域內(nèi)控制器（DC，domain controller）組成，也可由分布式的控制器集群組成。DCP負責(zé)管理子區(qū)域網(wǎng)絡(luò)內(nèi)部，子區(qū)域之間的通信以及全局網(wǎng)絡(luò)的宏觀信息由更上層SCP（super control plane)負責(zé)。SCP收集各個子區(qū)域的域內(nèi)信息和區(qū)域間的鏈路狀態(tài)信息，完成對網(wǎng)絡(luò)全局性的管理，可由域間總控制器（SC，super controller）組成。SDN分級分域體系架構(gòu)信息交互流程如圖1所示。

圖1 SDN分級分域架構(gòu)示意

SDN分級分域架構(gòu)在邏輯上對大規(guī)模網(wǎng)絡(luò)進行了再次分層，簡化了大規(guī)模網(wǎng)絡(luò)的管理難度，并且提高了網(wǎng)絡(luò)的可擴展性，使骨干網(wǎng)的SDN化成為可能。例如，在大型運營商網(wǎng)絡(luò)中，存在接入網(wǎng)、匯聚網(wǎng)、核心網(wǎng)等不同規(guī)模的網(wǎng)絡(luò)。每種網(wǎng)絡(luò)的規(guī)模、業(yè)務(wù)形態(tài)、網(wǎng)絡(luò)狀況及其抽象模型均有所不同，對于網(wǎng)絡(luò)功能的要求也有所不同。不同的網(wǎng)絡(luò)根據(jù)相應(yīng)的網(wǎng)絡(luò)功能需求運行特定的網(wǎng)絡(luò)應(yīng)用程序來管理。對于諸如運營商級的大型網(wǎng)絡(luò)來說，分級分域架構(gòu)可以提高其可擴展性與易操作性，是SDN大規(guī)模應(yīng)用的必然條件。在分級分域架構(gòu)下，子區(qū)域內(nèi)控制器與底層網(wǎng)絡(luò)設(shè)備實時交互獲取信息，靈活實現(xiàn)區(qū)域內(nèi)不同的路由策略；區(qū)域內(nèi)控制器上報各自區(qū)域路由信息給頂層域間控制器從而實現(xiàn)對于全局性網(wǎng)絡(luò)管理。綜上所述，分級分域網(wǎng)絡(luò)架構(gòu)可以在降低路由算法復(fù)雜度的同時提高其路由性能，可以實現(xiàn)域內(nèi)、域間不同的路由策略，進而大大提高網(wǎng)絡(luò)的靈活性。

1.3 QoS約束路由算法

QoS約束路由問題可以概括為，在滿足一個或多個條件約束下，尋找一條或多條最優(yōu)路徑，其中“最優(yōu)”可以有不同的度量方式?；赒oS的路由算法就是要找到一條從源點到終點滿足QoS參數(shù)約束的最優(yōu)路徑。幾種常用QoS參數(shù)包括可用帶寬、端到端延遲、分組丟失率、抖動和開銷，這些參數(shù)代表了網(wǎng)絡(luò)的質(zhì)量，且具有不同的數(shù)學(xué)特性。根據(jù)這些數(shù)學(xué)特性，QoS 參數(shù)可以歸類為以下3類：加性參數(shù)、乘性參數(shù)和瓶頸性參數(shù)，其中，加性參數(shù)包括時延、抖動、成本和跳數(shù)，乘性參數(shù)包括傳輸成功率，瓶頸性參數(shù)包括帶寬。如果對乘性參數(shù)取對數(shù)，就可以將其轉(zhuǎn)換為加性參數(shù)，最終QoS參數(shù)可歸類為兩類參數(shù)：瓶頸性參數(shù)和加性參數(shù)。如果一個路由算法被多個QoS參數(shù)約束，則這樣的算法屬于NP 完全問題[12]，在多項式時間內(nèi)無法取得精確結(jié)果。學(xué)術(shù)界提出了多種啟發(fā)式算法來解決這個問題，根據(jù)待解決的問題類型和求解方法，可將這些算法分成如下幾類：多項式非啟發(fā)類、非多項式非啟發(fā)類、探測類、限定QoS參數(shù)類、動態(tài)規(guī)劃類和代價函數(shù)類[13]。多QoS參數(shù)約束條件下的路由算法中，啟發(fā)式算法和近似算法均存在某些缺陷：首先，這兩類算法計算復(fù)雜度較高，在大規(guī)模網(wǎng)絡(luò)中無法實際應(yīng)用；其次，算法性能較低，無法計算出有效的最優(yōu)路徑；另外還存在一部分算法僅針對特殊需求而無法滿足通用的需求[14]。

綜上，已提出的路由算法中大部分是以鏈路狀態(tài)[15]或以特定需求為主導(dǎo)來設(shè)計路由算法的，如多路徑路由算法[16]，一次計算得到多個最優(yōu)路徑以實現(xiàn)負載均衡；動態(tài)路由算法，實時調(diào)整路由算法參數(shù)來最大限度計算出最優(yōu)路徑等。本文以包含大規(guī)模節(jié)點的SDN出發(fā)，應(yīng)用分級分域的新型網(wǎng)絡(luò)架構(gòu)[17]，基于時延和代價參數(shù)約束，設(shè)計可應(yīng)用于大規(guī)模網(wǎng)絡(luò)的高效路由算法，并保證了相應(yīng)的高性能以及低復(fù)雜度。

2 基于QoS約束SDN分級分域路由算法

本文在SDN 分級分域體系架構(gòu)下，考慮時延敏感的條件，計算當時延受限時，最小化代價的路由算法，即Delay-Constrained Least Cost 路由問題，簡稱DCLC問題[18]。本文中選取2個QoS參數(shù)：代價和時延。時延通指鏈路的傳輸時延和網(wǎng)絡(luò)設(shè)備內(nèi)的排隊時延等。代價通常為網(wǎng)絡(luò)傳輸?shù)拈_銷。在分級分域架構(gòu)下，域內(nèi)控制器可實時獲取域內(nèi)節(jié)點之間的時延和代價，域間控制器獲取部分域內(nèi)網(wǎng)絡(luò)節(jié)點鏈路信息，尋找時延受限而代價最小化的路由路徑，即LC-LD（least cost-least delay）路由算法。

2.1 問題描述

首先，本文提出域內(nèi)和域間兩種不同的LC-LD路由算法的簡單版本；之后，本文分析了出現(xiàn)環(huán)路的原因，以及如何檢測和消除環(huán)路；最后證明了經(jīng)過環(huán)路消除算法之后已經(jīng)不存在環(huán)路。同時，下文中LC路徑表示節(jié)點之間的最小代價路徑，LD路徑表示節(jié)點之間的最短時延路徑。

2.2 LC-LD路由算法描述

在SDN 分級分域架構(gòu)下，本文首先介紹域內(nèi)的LC-LD路由算法的簡單版本，然后介紹域間路由算法。該算法的目標是尋找一條在時延受限的條件下從源節(jié)點到目的節(jié)點的最優(yōu)路徑。在構(gòu)建最優(yōu)路徑時，每個節(jié)點有兩個可選的輸出鏈路。其中，一個是當前節(jié)點到目的節(jié)點的LC路徑，另一個是當前節(jié)點到目的節(jié)點的LD路徑。在大量約束條件的限制下，該算法計算得到的路徑可能不是嚴格意義上的最優(yōu)路徑，但大大減少了各個節(jié)點的計算量。

定義路徑

目的節(jié)點ID，。

目的節(jié)點ID，。

假設(shè)所有節(jié)點的代價向量和時延向量都持續(xù)更新。在執(zhí)行算法的過程中，代價及其向量、時延及其向量均保持不變。

對于跨域路由，本文算法對網(wǎng)絡(luò)視圖做了如下所述的抽象簡化。總控制器需要獲取的路由信息如下。

各個區(qū)域出口之間鏈路的時延和代價。

區(qū)域內(nèi)源節(jié)點和目的節(jié)點到該域出口的鏈路的時延和代價。

各個區(qū)域不同出口之間LC，LD路徑的時延和代價。

區(qū)域內(nèi)部控制器除了需要獲取區(qū)域內(nèi)部的信息，還需要上報總控制器SD源節(jié)點，目的節(jié)點到該區(qū)域出口的LC、LD路徑的時延和代價，以及各個區(qū)域出口之間的LC、LD路徑的時延和代價。

經(jīng)過上述邏輯抽象與簡化，原來復(fù)雜的、大規(guī)模的網(wǎng)絡(luò)拓撲被抽象為邏輯分層的新網(wǎng)絡(luò)拓撲。對于新的網(wǎng)絡(luò)拓撲，部分節(jié)點之間會有兩條鏈路路徑，即源節(jié)點、目的節(jié)點到該域的出口，以及各個域的出口之間存在的兩條直連的LC、LD路徑。簡化過后，網(wǎng)絡(luò)拓撲中的節(jié)點包括如下信息：所有域的出口節(jié)點信息；源節(jié)點目的節(jié)點信息。

鏈路包括如下信息：源節(jié)點到該節(jié)點所屬區(qū)域出口的LC/LD路徑信息；目的節(jié)點到所屬區(qū)域出口的LC/LD路徑信息；所有區(qū)域的出口之間的LC/LD路徑信息。

經(jīng)過上述抽象之后，多區(qū)域之間的選路問題可以簡化為區(qū)域內(nèi)部的選路問題，同時總控制器可以簡化為抽象后網(wǎng)絡(luò)拓撲的區(qū)域內(nèi)部控制器，根據(jù)相應(yīng)路由信息，進行路徑選擇。

如果以上不等式成立，即從活躍節(jié)點到目的節(jié)點存在經(jīng)過鏈路（活躍節(jié)點，ic_nhop）延約束的路徑，此時選擇活躍節(jié)點到目的節(jié)點的最小代價路徑。反之，選擇活躍節(jié)點到目的節(jié)點的最小時延路徑。這條從活躍節(jié)點到目的節(jié)點的LD路徑必然是從源節(jié)點到目的節(jié)點的時延受限的一條路徑中的一部分。否則，算法不會選取之前的活躍節(jié)點。經(jīng)由以上分析，控制器會選擇活躍節(jié)點的上述任意一種方向，此時，活躍節(jié)點中有如下路由信息：

起始節(jié)點,；

目的節(jié)點,；

Previous_node=ID of the Previous_active_node；

Previous_delay=delay_so_far, and

2.3 環(huán)路消除算法

2.2節(jié)提出的路由算法中，算法計算路徑上的每個節(jié)點都會選擇最小代價或最小時延的相應(yīng)路徑。如果所有節(jié)點全部選擇最小代價路徑或最小時延路徑時，最終得到的路由結(jié)果不會產(chǎn)生環(huán)路現(xiàn)象，因為生成的路徑分別為最小代價路徑或最小時延路徑。然而，若某些節(jié)點選擇最小代價路徑，其他節(jié)點選擇最小時延路徑時，則可能產(chǎn)生路由環(huán)路現(xiàn)象。下面集中分析討論檢測環(huán)路的方法和環(huán)路消除算法。

圖2中各個子圖代表了產(chǎn)生環(huán)路的場景。計算起始節(jié)點到目的節(jié)點的路徑，時延約束不超過8個單位。如圖2(a)、圖2(b)和圖2(c)所示，環(huán)路形成共經(jīng)歷圖2所示幾個階段。起始節(jié)點到目的節(jié)點是一條最小時延路徑，鏈路(,)是其中的第一部分。節(jié)點到目的節(jié)點是一條最小代價路徑，鏈路(,)是其中的第二部分。節(jié)點到目的節(jié)點是一條最小時延路徑，鏈路(,)是其中的第三部分。環(huán)路→→→，具體如圖2(c)所示。

圖2 環(huán)路消除算法示意

在圖2中運行環(huán)路消除算法的過程如下：在節(jié)點處檢測到環(huán)路，則立即沿著環(huán)路回退，由于節(jié)點處路由信息的flag標志位為LDPATH ，故繼續(xù)回退到節(jié)點，同時刪除（,）鏈路的路由表項（圖2(d)）。若節(jié)點處路由信息的flag標志位為LCPATH，則節(jié)點調(diào)整到沿著最小時延路徑的方向并修改相應(yīng)的路由表項信息，即刪除鏈路(,)，增加鏈路(,)。節(jié)點沿著相應(yīng)路徑到目的節(jié)點，算法結(jié)束。最終路由算法得到的結(jié)果如圖2(e)所示。

考慮以下情況：如果活躍節(jié)點路由信息的flag設(shè)置為LCPATH，回退過程中active_node將刪除LC方向鏈路，增加LD方向鏈路，此時LC方向和LD方向鏈路相同，則環(huán)路第二次出現(xiàn)。因此如果下一跳節(jié)點同時屬于活躍節(jié)點到目的節(jié)點的最小代價路徑和最小時延路徑中的一部分，且滿足least_cost_nhop (active_node, d) = least_ dealy_nhop (active_node,d) ，則設(shè)置活躍節(jié)點中路由表的flag標志位為LDPATH。

對于不同區(qū)域之間的路由問題，經(jīng)過抽象簡化的網(wǎng)絡(luò)拓撲中可能在一對節(jié)點之間包含兩條鏈路，分別為最小代價路徑和最小時延路徑。由于回退過程中活躍節(jié)點將刪除最小代價方向鏈路，增加最小時延方向鏈路，同時這兩條鏈路并不相同，那么如果出現(xiàn)上述下一跳節(jié)點相同的情況，此時選擇最小代價方向，則標記為LCPATH；后續(xù)如果選擇最小時延方向，則標記為LDPATH。

2.4 算法證明

假設(shè)不等式(4)成立

下面證明本文提出的算法計算得到的路徑不包含環(huán)路。在活躍節(jié)點查找路由表獲取下一跳節(jié)點信息之前，檢查其他路由表信息，如果已經(jīng)有源節(jié)點和目的節(jié)點的表項信息，表明環(huán)路出現(xiàn)，此時運行環(huán)路消除算法，因此最終算法得到的路徑無環(huán)。

2.5 復(fù)雜度分析

圖3中的(,)，(,)，(,)，(,)和(,)是樹鏈路。

圖3 鏈路示例圖

經(jīng)過上述分析，每條反向鏈路最多產(chǎn)生+個上行鏈路，最壞情況下會有(+)個環(huán)路，考慮到約束條件，復(fù)雜度大概為(||2)。每個環(huán)路最長為2(||1)，因而本算法在最差情況下的復(fù)雜度不超過(||3)。事實上，本算法在平均情況下性能遠超最壞情況。

在分級分域架構(gòu)中，假設(shè)有個節(jié)點，個域，平均每個域有個節(jié)點，即=，平均每個域有個出口，且<。經(jīng)過前幾節(jié)抽象之后的網(wǎng)絡(luò)拓撲的節(jié)點數(shù)變?yōu)?2。相對于原始拓撲，節(jié)點個數(shù)減少，從而大大降低了路由算法的復(fù)雜度。

3 仿真結(jié)果分析

由上述原理分析，相對于傳統(tǒng)分布式的網(wǎng)絡(luò)架構(gòu)，經(jīng)過抽象之后的分級分域的網(wǎng)絡(luò)結(jié)構(gòu)中網(wǎng)絡(luò)拓撲規(guī)模下降，使算法復(fù)雜度有所下降。下面選取兩個算法復(fù)雜度較低的服務(wù)質(zhì)量路由方案進行仿真對比分析，另外引入一種基于啟發(fā)式多約束最優(yōu)路徑的路由算法（S-MQOS）[19]進行對比，確保4種方案網(wǎng)絡(luò)拓撲內(nèi)個數(shù)相同。具體分析如下。

在SDN分級分域結(jié)構(gòu)的條件下，最小時延路由算法簡稱LD，網(wǎng)絡(luò)內(nèi)總控制器獲取路由信息的過程如下所示：① 區(qū)域各個出口之間鏈路的時延和代價；② 區(qū)域內(nèi)部源節(jié)點、目的節(jié)點到該域出口的最小時延路徑的時延和代價；③ 各個域的不同出口之間最小時延路徑的時延和代價。區(qū)域內(nèi)部控制器有如下任務(wù)：① 獲取區(qū)域內(nèi)部網(wǎng)絡(luò)路由信息；②上報總控制器源節(jié)點、目的節(jié)點到該區(qū)域出口的最小時延路徑的時延和代價，以及各個區(qū)域出口之間的最小時延路徑的時延和代價。經(jīng)過以上分析簡化之后形成新的網(wǎng)絡(luò)拓撲，給定源節(jié)點和目的節(jié)點，算法計算得到最小時延路徑。

另一個簡化版本的路由算法是最小代價路由算法，簡稱LC，網(wǎng)絡(luò)內(nèi)總控制器獲取路由信息與上述最小時延算法完全相同。區(qū)域內(nèi)部控制器任務(wù)如下：①獲取區(qū)域內(nèi)部路由信息；②上報源節(jié)點、目的節(jié)點到該區(qū)域出口的最小代價路徑的時延和代價到總控制器，另外還有各個區(qū)域出口之間的最小代價路徑的時延和代價。經(jīng)過以上分析簡化之后形成新的網(wǎng)絡(luò)拓撲，給定源節(jié)點和目的節(jié)點，算法計算得到的是最小時延路徑。與LD算法不同的是，如果最小代價路徑不符合時延參數(shù)的約束要求，則算法失敗。

綜上，LC-LD算法的算法復(fù)雜度為(3)，LC算法和S-MQOS與算法方案復(fù)雜度為(2)，是網(wǎng)路拓撲內(nèi)節(jié)點的個數(shù)。由2.5節(jié)可知，經(jīng)過SDN分級分域架構(gòu)抽象后的節(jié)點個數(shù)大幅減少，計算復(fù)雜度相對傳統(tǒng)的情況也大幅降低，因此，LC-LD算法擁有較低的算法復(fù)雜度。

其次，仿真網(wǎng)絡(luò)拓撲各部分參數(shù)的生成方式都是隨機的，但基本符合現(xiàn)實網(wǎng)絡(luò)的情況。這些參數(shù)包括：區(qū)域數(shù)、區(qū)域內(nèi)的節(jié)點數(shù)、各鏈路的代價和時延參數(shù)。其中，區(qū)域數(shù)服從 5~10 的均勻分布，區(qū)域內(nèi)的節(jié)點數(shù)服從 10~20 的均勻分布。各鏈路的時延和代價參數(shù)呈負相關(guān)，大致符合方程0.01.+ 0.1.= 1，式中時延和代價僅代表數(shù)量關(guān)系，并大致符合現(xiàn)實網(wǎng)絡(luò)的情況。在上述參數(shù)條件下隨機生成100個網(wǎng)絡(luò)，并在不同時延參數(shù)條件的限制下對4種算法分別進行了100次實驗。另外，如果算法計算得到的路由路徑不符合時延參數(shù)的約束，則不記入最后的統(tǒng)計平均結(jié)果。最終統(tǒng)計結(jié)果如圖4所示。

圖4 不同時延參數(shù)約束下的路由平均代價

不同時延參數(shù)約束下的路由平均代價情況如圖4所示。本文提出的LC-LD算法相對于簡化之后的LD算法平均代價有明顯降低，LC-LD算法隨著時延參數(shù)約束的增加，有更大概率選擇最小代價路徑，最終平均代價降低；另外，LC-LD算法的代價逼近最優(yōu)情況下LC算法的平均代價。S-MQOS由于其最優(yōu)性，在平均代價方面是最低的，但其算法復(fù)雜度較高。

在4種算法計算得到的路由滿足時延約束的路徑的比例即成功率，LC-LD算法與LD算法基本一致，這是因為當有時延約束時，LC-LD算法更傾向于選擇最小時延路徑。同時LC-LD算法顯著高于LC算法，當時延參數(shù)約束大于300時，計算得到的所有路徑幾乎滿足時延約束。當時延約束不超過300時，LC算法成功率低于50%。但隨著時延約束的提高，選路成功率有提升。而S-MQOS由于其復(fù)雜性，在時延約束上限超過500時，成功率才有所提高（如圖5所示）。

圖5 不同時延限制下選路成功率

綜上，對于時延受限、代價盡可能降低的選路問題，本文提出的LC-LD算法的選路成功率比LC和S-MQOS算法大大提高，同時隨著時延約束條件的放寬，LC-LD算法計算得到的結(jié)果的平均代價的最優(yōu)情況與LC算法的平均代價十分接近。相對LD算法在滿足時延約束條件的情況下，LC-LD算法的選路成功率與LD算法幾乎相近，但平均代價有明顯降低。本文提出的LC-LD算法相比其他3個算法在總控制器與區(qū)域內(nèi)控制器之間交互信息較多，但算法的性能影響不是很大。

4 結(jié)束語

本文提出了基于SDN分級分域架構(gòu)，時延與代價參數(shù)最優(yōu)的服務(wù)質(zhì)量路由算法——LC-LD路由算法。已有研究中，基于QoS的路由算法基本是啟發(fā)式算法，這類算法由于復(fù)雜度過高，無法在實際的大規(guī)模網(wǎng)絡(luò)中應(yīng)用。而其他一類算法復(fù)雜度較低，如最短路徑算法[20-21]，但其算法性能較差。本文算法基于SDN分級分域架構(gòu)，在算法復(fù)雜度和算法性能間保持平衡，既保證了較低的算法復(fù)雜度使其能應(yīng)用于現(xiàn)實中的網(wǎng)絡(luò)，又保證了算法的高效性從而能夠計算得到有效的路由路徑。LC-LD算法基于SDN分級分域的網(wǎng)絡(luò)架構(gòu)，經(jīng)過抽象之后形成新的網(wǎng)絡(luò)拓撲，網(wǎng)絡(luò)節(jié)點大幅減少，相對于啟發(fā)式服務(wù)質(zhì)量路由算法復(fù)雜度大大降低。同時仿真結(jié)果表明，相對于最小代價路由算法和啟發(fā)式多約束最優(yōu)路由算法，LC-LD算法能保證找到滿足時延約束條件的有效路徑，并隨著時延約束上限的提高，LC-LD算法計算得到的路徑的平均代價與最優(yōu)情況下最小代價路由算法接近。與最小時延路由算法相比，本算法在滿足時延約束條件的情況下，選路成功率與最小時延路由算法相似，但顯著降低了鏈路的平均代價。因此，與復(fù)雜度較低的路由算法相比，LC-LD算法的性能有較大的提升。在后續(xù)工作中，LC-LD算法可以針對組播以及任播等其他網(wǎng)絡(luò)場景進一步優(yōu)化。

[1] WANG Z, CROWCROFT J. QoS routing for supporting resource reservation [J]. IEEE Journal on Selected Areas in Communications, 1996,14(7): 1228-1234.

[2] HEDRICKCL. Routing information protocol 1988[S].

[3] MOY J. OSPF Version 2[S]. 1997.

[4] BIANCO, ANDREA, et al. OpenFlow switching: data plane performance [C]//IEEE International Conference on ICC. 2010: 1-5.

[5] MCKEOWN N. Software defined mobile networks[C]//Tenth ACM International Symposium on Mobile Ad Hoc Networking & Computing. 2009.

[6] PFAFF B. OpenFlow switch specification version 1.1.0 implemented (Wire Protocol 0x02) [S]. 2011.

[7] Open Networking Foundation (ONF). SND Architecture Overview[S]. 2013.

[8] GUDE N,KOPONEN T'PETTIT J, et a1.Nox:towards an operating system for networks[J]. ACM SIGCOMM Computer Communication Review,2008, 38(3): 105-110.

[9] KOPONEN T, CASADO M, GUDE N, et a1. Onix: a distributed control platform for large-scale production networks[C]//Usenix Symposium on Operating Systems Design & Implementation, 2010(10): 1-6.

[10] ROTHENBERG C E,NASCIMENTO M K SALVADORM R et a1. Revisiting routing control platforms with the eyes and muscles of software-defined networking[C]//The First Workshop on Hot Topics in Software Defined Networks. 2012: 13-18.

[11] LIN P, BI J, WANG Y. East-west bridge for SDN network peering [M]//Frontiers in Internet Technologies. Berlin: Springer. 2013: 170-181.

[12] GAREY M S, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness. Oxford: Freeman[M]. W.H., 1979.

[13] 崔勇, 吳建平, 徐恪,等. 互聯(lián)網(wǎng)絡(luò)服務(wù)質(zhì)量路由算法研究綜述[J].軟件學(xué)報, 2002, 13(11):2065-2075.

CUI Y, WU J P, XU L. A survey on research of quality of service routing algorithms in internet[J]//Journal of Software, 2002, 13(11): 2065-2075.

[14] 董占麗. 基于SDN的農(nóng)墾EDRP路由協(xié)議研究[J].信息技術(shù), 2014, 38(3): 198-202.

DONG Z L. Discussion on Nongken EDRP protocol based on SDN[J]//Information Technology, 2014, 38(3): 198-202.

[15] 王歆平, 王茜, 劉恩慧, 等. 基于SDN的按需智能路由系統(tǒng)研究與驗證[J]. 電信科學(xué), 2014, 30(4): 8-14.

WANG X P, WANG Q, LIU E H. Research and Verification on SDN-Based On-Demand Smart Routing System[J]// Telecommunications Science, 2014, 30(4): 8-14.

[16] DOSHI M, KAMDAR A. Multi-constraint QoS disjoint multipath routing in SDN[C]//2018 Moscow Workshop on Electronic and Networking Technologies (MWENT). 2018: 1-5.

[17] HATA M, SOYLU M, IZUMI S, et al. Design of SDN based end-to-end routing over multiple domains for mobility management[C]//Network and Service Management (CNSM), 2017 13th International Conference on. IEEE, 2017: 1-4.

[18] SALAMA H F, REEVES D S, VINIOTIS Y A. Distributed algorithm for delay-constrained unicast routing[J]. IEEE/ACM Transactions on Networking, 2000, 8(2): 239-250.

[19] 楊建華. 基于啟發(fā)式多約束最優(yōu)路徑的軟件定義網(wǎng)絡(luò)服務(wù)質(zhì)量路由算法研究[D]. 陜西: 西安電子科技大學(xué), 2015.

YANG J H. Research on quality-of-service routing algorithm in software defined network based on heuristic multi-constraint optimal path[D]. Shaanxi: Xidian University,2015.

[20] 陳章迎,朱尚明.基于重疊網(wǎng)絡(luò)的多路徑路由設(shè)計和實現(xiàn)[J].通信學(xué)報,2018,39(S1):200-205.

CHEN Y Z, ZHU S M. Designing and implementation of multi-path QoS routing algorithm based on overlay network[J]//Journal on Communications,2018,39(S1):200-205.

[21] 孔德慧. 基于SDN的多限制多路徑QoS路由算法研究[D].北京:北京郵電大學(xué),2018.

KONG D H. Routing algorithm for qos with multi constraints and multipath based on SDN[D].Beijing: Beijing University of Posts and Telecommunications,2018.

QoS routing algorithm based on multiple domain architecture of SDN

HUANG Wei, LU Ran, LIU Cuncai, QI Sibo

The 54th Research Institute of China Electronic Technology Group Corporation, Shijiazhuang 050081,China

Traditional distributed network architecture constraints the innovation of routing algorithm. Software-defined network (SDN) provides a new solution for the optimization of routing algorithm. Previous researches show that the quality of service (QoS) routing issues are based on heuristic algorithm mostly, but these methods cannot be applied in large networks due to their high computing complexity. However, other algorithms have a lot of problems, which are high complexity or poor QoS performance, such as shortest path algorithm. This paper proposes A new QoS routing algorithm: LC-LD routing algorithm was proposed. LC-LD was based on SDN west-east interface and binds both delay constraint and cost constraint. keeping a good balance between computational complexity and algorithm performance. Finally, the simulation results show that LC-LD can possess both low computational complexity and high QoS routing performance.

software defined network (SDN), SDN west-east interface, quality-of-service (QoS), routing algorithm

黃偉（1978? ），男，河北保定人，中國電子科技集團公司第五十四研究所高級工程師，主要研究方向為通信系統(tǒng)總體技術(shù)、通信系統(tǒng)與網(wǎng)絡(luò)仿真。

路冉（1979? ），女，河北石家莊人，中國電子科技集團公司第五十四研究所高級工程師，主要研究方向為通信網(wǎng)絡(luò)仿真技術(shù)和軟件定義網(wǎng)絡(luò)。

劉存才（1965? ），男，河北石家莊人，中國電子科技集團公司第五十四研究所高級工程師，主要研究方向為通信網(wǎng)仿真和通信網(wǎng)的可靠性。

祁思博（1991? ），男，河北石家莊人，中國電子科技集團公司第五十四研究所工程師，主要研究方向為通信網(wǎng)仿真和軟件定義網(wǎng)絡(luò)。

TP393

A

10.11959/j.issn.2096?109x.2019047

2019?01?19；

2019?03?18

祁思博，773624104@qq.com

國防科技重點實驗室基金資助項目（No.614210401050217）

The National Defence Science and Technology Key Laboratories Foundation of China (No.614210401050217)

黃偉, 路冉, 劉存才, 等. 基于SDN分級分域架構(gòu)的QoS約束路由算法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 2019, 5(5): 21-31.

HUANG W, LU R, LIU C C, et al. QoS routing algorithm based on multiple domain architecture of SDN[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 21-31.