基于Mininet的LRMC QoS路由算法仿真研究

傅妍芳，宋新美，張趙晨子，蘇一昶

(1. 西安工業(yè)大學(xué)計算機科學(xué)與工程學(xué)院，陜西西安710021；2. 中國工商銀行，陜西西安710021)

1 引言

網(wǎng)絡(luò)是一種將控制層與數(shù)據(jù)轉(zhuǎn)發(fā)平面分離的網(wǎng)絡(luò)架構(gòu)，其提供的可直接編程等特性為網(wǎng)絡(luò)控制管理技術(shù)帶來了革命性的改進。目前，SDN技術(shù)正在被廣大科研、生產(chǎn)工作者廣泛研究，并應(yīng)用在數(shù)據(jù)中心、廣域網(wǎng)等場景。然而構(gòu)建一個完整的SDN網(wǎng)絡(luò)至少需要控制器、OpenFlow 交換機、終端結(jié)點等設(shè)備，超出了大部分研究工作者具備的實驗條件。為此，OpenNet、NS3、Mininet等仿真軟件便應(yīng)運而生，其中以Mininet最為流行。

Mininet 是由虛擬主機(Host)、交換機(Switch)、控制器(Controller)、鏈路(Link)組成的開源系統(tǒng)，其采用輕量級的虛擬技術(shù)，搭建的虛擬網(wǎng)絡(luò)可以移植到真實網(wǎng)絡(luò)中。Mininet 可以簡單創(chuàng)建支持SDN的網(wǎng)絡(luò)，其主要特性包括：①支持多個用戶在同一個拓?fù)渖线M行并發(fā)操作；②方便可重復(fù)和可封裝的回歸測試；③無需物理網(wǎng)絡(luò)；④提供用于網(wǎng)絡(luò)測試的 CLI；⑤提供python API；⑥支持所有拓?fù)?。總之，Mininet因其高靈活性、高可用性、可擴展性、可共享等優(yōu)點目前被廣泛使用。

基于Mininet仿真網(wǎng)絡(luò)，本文主要關(guān)注網(wǎng)絡(luò)QoS保障技術(shù)。針對在線直播、視頻會議等多類型業(yè)務(wù)的QoS 保障需求，傳統(tǒng)網(wǎng)絡(luò)在早期提供的BE(Best Effort，盡力而為)服務(wù)之上提出了區(qū)分服務(wù)(DiffServ)模型，但受限于緊耦合的網(wǎng)絡(luò)架構(gòu)，DiffServ模型在傳統(tǒng)網(wǎng)絡(luò)中的實現(xiàn)不能快速適應(yīng)網(wǎng)絡(luò)狀態(tài)并做出實時決策，因此無法嚴(yán)格保障端到端QoS。網(wǎng)絡(luò)地址轉(zhuǎn)換(Network Address Translation，NAT)、邊界網(wǎng)關(guān)協(xié)議(Border Gateway Protocol，BGP)[1]、開放式最短路徑優(yōu)先(Open Shortest Path First，OSPF)[2]等協(xié)議功能也是為提高網(wǎng)絡(luò)傳輸QoS而實施的保障措施，但它們在傳統(tǒng)網(wǎng)絡(luò)中的配置不靈活，功能迭代速度受限，因此依然存在業(yè)務(wù)QoS不能得到有效保障的問題。鑒于此，軟件定義網(wǎng)絡(luò)(Software-Defined Networking，SDN)[3]以其中心化的控制模式解決了傳統(tǒng)網(wǎng)絡(luò)保障QoS時的諸多問題[4]。在SDN中，控制器軟件及實現(xiàn)控制功能的軟件構(gòu)成了控制平面，SDN交換機只需按照控制層面的轉(zhuǎn)發(fā)流表執(zhí)行轉(zhuǎn)發(fā)動作。這種松耦合架構(gòu)有效解決了傳統(tǒng)網(wǎng)絡(luò)中配置不便、路由不靈活等問題，從而實現(xiàn)了動態(tài)的路由策略、便捷的網(wǎng)絡(luò)配置并降低了網(wǎng)絡(luò)升級構(gòu)建成本[5]。

目前，基于SDN的QoS保障技術(shù)研究已有不少成果。針對目前SDN架構(gòu)中控制器上時序優(yōu)先的流量調(diào)度算法的不足，Airton Ishimori等人提出了一種QoSFlow框架，引入HTB、SFQ、RED等隊列調(diào)度算法降低數(shù)據(jù)包轉(zhuǎn)發(fā)處理時延，有效提高了視頻等數(shù)據(jù)流的PNSR[6]。Seyhan Civanlar等人通過以時延和網(wǎng)絡(luò)丟包率的加權(quán)平均作為QoS約束代價，計算QoS視頻業(yè)務(wù)和BE業(yè)務(wù)的路徑，進而搜索滿足約束的最優(yōu)路徑，一定程度上保障了時延、丟包率QoS需求[7]-[8]。這些路由算法[11]雖然實現(xiàn)了較好的流量分布策略，一定程度上保障了高優(yōu)先級業(yè)務(wù)QoS，但對全局網(wǎng)絡(luò)業(yè)務(wù)特性考慮不全，以一種QoS性能作為優(yōu)化目標(biāo)，因此無法滿足多類型業(yè)務(wù)QoS需求，更不能達(dá)到動態(tài)自適應(yīng)保障業(yè)務(wù)QoS的目標(biāo)。

為有效保障多類型業(yè)務(wù)的QoS，本文基于Mininet仿真系統(tǒng)設(shè)計實現(xiàn)了一種基于SDN的拉格朗日松弛多約束(LRMC)QoS路由算法。在支持OpenFlow協(xié)議的交換機中，根據(jù)流表項中的TOS包頭域?qū)I(yè)務(wù)數(shù)據(jù)劃分優(yōu)先級，進而針對不同優(yōu)先級業(yè)務(wù)流建立了多約束數(shù)學(xué)模型，采用拉格朗日松弛法和梯度迭代法對約束關(guān)系進行松弛并迭代求解鏈路權(quán)重，進而利用Dijkstra算法探索出最優(yōu)路徑解。最后借助Mininet 及其CLI對LRMC QoS路由算法進行網(wǎng)絡(luò)仿真，對比其相較單約束QoS算法在網(wǎng)絡(luò)連通收斂性和網(wǎng)絡(luò)性能上的表現(xiàn)。

2 路由算法設(shè)計

面對多約束條件下的QoS路由問題時，一般采用啟發(fā)式算法或近似算法保證策略的實時可靠性[13]。啟發(fā)式算法具有時間復(fù)雜度低的優(yōu)勢，但策略質(zhì)量無法保證；近似算法雖然時間復(fù)雜度相對較高，但能更好地保證策略可靠。本文主要針對拓?fù)涔?jié)點數(shù)相對較少的網(wǎng)絡(luò)環(huán)境，所以選擇近似算法-拉格朗日松弛多約束算法求解。

2.1 QoS多約束建模

根據(jù)RFC2574標(biāo)準(zhǔn)對QoS路由的定義，QoS是基于網(wǎng)絡(luò)可用資源和業(yè)務(wù)流QoS要求來選擇路徑的路由機制或包含各種QoS參數(shù)的動態(tài)路由協(xié)議[14]。作為一種路由機制，QoS路由的預(yù)設(shè)條件是滿足一個或多個資源限制或業(yè)務(wù)流QoS要求，這些限制及要求被量化為丟包率、時延、帶寬等參數(shù)[17]。本文研究的路由算法正是針對多約束條件參數(shù)展開，這些QoS指標(biāo)被分為加法、乘法、凹性三種尺度[18]。定義如：在一個網(wǎng)絡(luò)拓?fù)渲?，記路徑P=(a，b，c，∧，e，f)，(i，j)為連接節(jié)點i和節(jié)點j的鏈路，c(i，j)為鏈路(i，j)上的某個QoS尺度值，c(p)為路徑p的某個QoS尺度值。若滿足c(p)=c(a，b)+c(b，c)+∧+c(e，f)，則這種c(i，j)尺度就屬于加法尺度，例如網(wǎng)絡(luò)時延等；若滿足c(p)=c(a，b)×c(b，c)×∧×c(e，f)，則c(i，j)這種尺度就屬于乘法尺度，例如丟包率等；若滿足c(p)=min{c(a，b)，c(b，c)，∧，c(e，f)}，則c(i，j)這種尺度就屬于凹性尺度，例如帶寬等。

針對圖G(V，E)表示的n個節(jié)點的網(wǎng)絡(luò)，其中E代表網(wǎng)絡(luò)中的鏈路集，V代表網(wǎng)絡(luò)中的節(jié)點集，設(shè)路由源節(jié)點為s，目的節(jié)點為t，Pst表示由源節(jié)點到目的節(jié)點的所有路徑集。則對于每一條路徑p∈Pst，關(guān)于其中每條鏈路e(i，j)的延遲dij、丟包率lij、帶寬bij，可根據(jù)QoS算法的性能尺度定義得到各尺度約束關(guān)系式，如式(1)、(2)、(3)所示

(1)

b(p)=min[bij，bij，…，bmn]

(2)

(3)

(4)

將式(1)(2)(3)代入上式，則上述多約束問題可簡化為

(5)

該多約束最小代價路徑問題是一個NP問題，通過拉格朗日松弛法可對式(5)進行松弛處理，求得多約束問題下界，隨后在迭代探查過程中搜索滿足約束條件的路徑。

2.2 拉格朗日松弛處理

使用拉格朗日松弛法對多約束最小代價模型進行松弛時，首先需要對式(4)中丟包率約束不等式兩邊取對數(shù)，將多約束模型中的乘法約束轉(zhuǎn)換為加法約束，即：

(6)

對式(5)進行拉格朗日松弛

(7-1)

min[bij]≥B

s.t.

(i，j)∈p

(7-2)

式(7)中μ1和μ2為兩個常數(shù)級別拉格朗日乘子，因此μ1D+μ2logL也為常數(shù)，為簡化計算，可將式(7)簡化為式(8)。

(8)

根據(jù)上式，將鏈路權(quán)重Wij簡化定義為式(9)所示。

Wij=wij+μ1dij+μ2loglij

(9)

2.3 梯度迭代

欲求解權(quán)重因子，可以考慮通過梯度迭代法求解，因為通過觀察μ1、μ2與時延、丟包率的線性關(guān)系發(fā)現(xiàn)，μ1、μ2與dij、lij呈線性正相關(guān)，因此可以使用傳統(tǒng)線性表達(dá)式的求解方式梯度迭代法來求解μ1、μ2最優(yōu)解。

L(μ1，μ2)分別對μ1、μ2求偏導(dǎo)，如式(10)(11)所示

(10)

(11)

為保證Δd和Δl非負(fù)，Δd、Δl分別表示如下

(12)

(13)

令μ1←μ1+φΔd，μ2←μ2+ηΔl，保證權(quán)重因子單調(diào)遞增。使用(μ1)t、(μ2)t表示第t次梯度迭代時的鏈路權(quán)重乘子，則t+1次迭代時的乘子如式(14)、(15)：

(μ1)t+1=(μ1)t+φtΔd

(14)

(μ2)t+1=(μ2)t+ηtΔl

(15)

設(shè)不受約束時的路徑最小權(quán)重為Cmin，則步長φt和ηt如式(16)、(17)所示。

(16)

(17)

每次迭代時的標(biāo)量ωt、ρt取非負(fù)常數(shù)，即

(18)

(19)

利用梯度迭代法即可求解滿足原線性規(guī)劃問題的權(quán)重乘子μ1和μ2，即式(8)問題的權(quán)重乘子。如果所選路由上性能參數(shù)不滿足約束閾值，則調(diào)整相應(yīng)的權(quán)重乘子改變該參數(shù)在鏈路權(quán)重計算中的權(quán)重比，進而通過迭代探尋滿足式(4)約束模型的最優(yōu)可行路徑。

3 路由算法實現(xiàn)

基于對實時業(yè)務(wù)數(shù)據(jù)流的優(yōu)先級分類和多約束QoS路由算法的建模分析，本文實現(xiàn)了SDN網(wǎng)絡(luò)中實時業(yè)務(wù)多約束QoS路由算法。

圖1 LRMC多約束QoS算法流程圖

算法流程如圖1所示，主要步驟如下：

1)以拓?fù)渲墟溌積(i，j)的延遲dij為鏈路權(quán)重，通過Dijkstra算法求得最短路徑Pd。若該最短路徑的帶寬和延遲指標(biāo)滿足預(yù)設(shè)的閾值需求，則Pd為滿足約束的最短路徑，返回Pd，算法結(jié)束。否則執(zhí)行步驟2)。

2)以拓?fù)渲墟溌積(i，j)的帶寬bij為鏈路權(quán)重，通過Dijkstra算法求得最短路徑Pd。若該最短路徑的帶寬和延遲指標(biāo)滿足預(yù)設(shè)的閾值需求，則Pd為滿足約束的最短路徑，返回Pd，算法結(jié)束。否則執(zhí)行步驟3)。

3)通過步長φt和ηt迭代計算μ1和μ2，并將μ1和μ2代入式(9)得到鏈路多約束權(quán)重wij。Dijkstra算法以wij為代價求得最短路徑Pt+1，如果Pt+1滿足約束模型式(5)則選擇Pt+1為(s，t)傳輸路徑。

分析算法流程可得，本文實現(xiàn)的基于SDN的LRMC多約束QoS路由算法的時間消耗主要包含兩部分：Dijkstra算法和調(diào)整權(quán)重因子迭代探尋最優(yōu)多約束路由。LRMC多約束QoS路由算法在搜索最優(yōu)路徑時，首先采用經(jīng)典單源最短路徑Dijkstra算法求解帶權(quán)有向網(wǎng)絡(luò)拓?fù)渲械淖疃搪窂?，而Dijkstra算法總的時間復(fù)雜度為O(n2)[20]；當(dāng)Dijkstra算法所得路徑無法滿足業(yè)務(wù)多約束需求時，使用LRMC算法迭代調(diào)整權(quán)重乘子并重新計算鏈路權(quán)重，因此設(shè)t次迭代得到最優(yōu)路徑，則算法時間復(fù)雜度為O(t·n2)。綜上，針對n個節(jié)點的稀疏網(wǎng)絡(luò)拓?fù)洌鸩降鷗次搜索最優(yōu)路徑，LRMC多約束路由算法在最壞情況下的時間復(fù)雜度為O(t·n2)，最好情況下時間復(fù)雜度為O(n2)。

4 仿真及性能評價

為評價基于SDN的LRMC多約束QoS路由算法(以下簡稱LRMC算法)的性能，本文采用mininet仿真工具分別對LRMC算法和一種SC(Single Constraint)算法對比，該算法是與LRMC算法同等算法條件下對QoS時延指標(biāo)單約束(Single Constraint)的路由算法。仿真性能包括連通時延收斂性及帶寬、傳輸速率、丟包率、時延性能的表現(xiàn)。

4.1 仿真環(huán)境設(shè)置

本文采用Ubuntu14.04操作系統(tǒng)虛擬機與mininet仿真工具模擬網(wǎng)絡(luò)環(huán)境。LRMC算法選用Python2.7開發(fā)語言和PyCharm編譯器進行開發(fā)編譯，并部署運行在虛擬機上安裝的Ryu控制器中。仿真在Mininet仿真環(huán)境下進行，為模擬真實網(wǎng)絡(luò)環(huán)境中的鏈路負(fù)載情況，實驗中為每條鏈路Hi→Hj設(shè)定固定帶寬值(bw)，網(wǎng)絡(luò)拓?fù)淠_本如圖2所示。

圖2 拓?fù)錁?gòu)建腳本

4.2 仿真及分析

1)實驗一：算法收斂性實驗

建設(shè)全域旅游示范區(qū)，首要的是抓好高等級的優(yōu)質(zhì)景區(qū)[13]，這些景區(qū)是引領(lǐng)區(qū)域旅游發(fā)展的增長極，可以依托這些景區(qū)打造沿黃精品旅游線路。目前山西沿黃縣市還沒有5A級景區(qū)，未來仍需加緊二次深度開發(fā)沿黃核心景區(qū)，提升景區(qū)質(zhì)量等級與接待服務(wù)水平，創(chuàng)新旅游項目，延伸景區(qū)景觀以擴大景區(qū)規(guī)模。同時，要摸清沿黃旅游資源家底，對尚未開發(fā)到位的旅游資源，尤其是特色旅游資源，要按照國際旅游標(biāo)準(zhǔn)開發(fā)規(guī)劃，爭取一次到位，避免破壞性建設(shè)。

為對比SC算法與LRMC算法在路由發(fā)現(xiàn)時間上的收斂性，本次實驗擬在實驗拓?fù)渲蟹謩e運行SC和LRMC算法，利用ICMP協(xié)議中的icmp＿seq字段測試連通性，執(zhí)行操作如下： H1、H3、H5分別向H4、H6、H8發(fā)送30次ICMP請求報文，監(jiān)測ICMP＿seq發(fā)送次數(shù)與連通響應(yīng)時間。

圖3、圖4、圖5分別為H1→H4、H3→H6、H5→H8節(jié)點之間鏈路的30次連通時間折線圖，圖中剔除了SC算法的超時數(shù)據(jù)。由圖可知，SC算法在ICMP＿seq次數(shù)少于21次時均連接超時，無法收斂，在21至25次之間時才不超時，但是連通時延均大于等于0.28ms，H1→H4連接過程中當(dāng)ICMP＿seq次數(shù)為25、26時，H1和H4的時延測試結(jié)果甚至達(dá)到2046ms和1047ms，此后時延才急劇下降，實現(xiàn)收斂。而LRMC算法在ICMP＿seq次數(shù)僅為1時就達(dá)到連通目標(biāo)，且除第一次連通外，連通時延均小于0.1ms。

圖3 H1、H4連通收斂圖

圖4 H3、H6連通收斂圖

圖5 H5、H8連通收斂圖

因此由該算法收斂性實驗可見，LRMC算法的連通速度明顯快于SC算法，快速實現(xiàn)收斂性。

2)實驗二：算法性能實驗

為驗證LRMC算法在網(wǎng)絡(luò)傳輸性能上的表現(xiàn)，本次實驗分別計算SC算法與LRMC多約束路由算法運行時的鏈路帶寬、傳輸速率、延遲及丟包率性能，并統(tǒng)計分析其方差。實驗中，將H1-H7共7 臺主機作為客戶端，H8作為服務(wù)端，當(dāng)SC算法與LRMC算法運行時，客戶端分別向服務(wù)端發(fā)送6M的TCP數(shù)據(jù)包，計算每條鏈路在兩種算法運行時的傳輸性能。

表1 LRMC算法與SC算法運行時網(wǎng)絡(luò)性能

LRMC算法與SC算法運行時網(wǎng)絡(luò)性能統(tǒng)計如表1所示，由表可知，LRMC算法運行時，鏈路帶寬、傳輸速率、丟包率性能與SC算法運行時基本一致，部分鏈路略高于SC；而對于傳輸速率，除路徑H1→H8、H6→H8、H7→H8在兩種算法運行時的差值小于0.1%之外，LRMC路由算法在其余H2→H8、H3→H8、H4→H8、H5→H8路徑上運行時的傳輸速率比SC算法運行時高39～99.3倍。

為進一步對比LRMC算法、SC算法在鏈路帶寬、傳輸速率、鏈路時延、丟包率性能上的穩(wěn)定性，本實驗計算并統(tǒng)計了表2對應(yīng)各性能數(shù)據(jù)方差值，性能方差數(shù)據(jù)直方如圖6所示。

圖6 算法傳輸性能方差對比

如圖7所示，對于鏈路帶寬性能，SC算法與LRMC算法運行時性能方差基本一致，LRMC算法比SC算法帶寬方差小9.27%，而其它傳輸速率、時延、丟包率3個性能指標(biāo)在兩種算法運行時的性能方差差距較明顯，LRMC算法方差比SC算法分別小38.2%、45.2%、11.9%。由此可知，相較于SC算法，LRMC算法運行時的網(wǎng)絡(luò)性能穩(wěn)定性更優(yōu)。

綜上實驗結(jié)果及分析可得，本文設(shè)計實現(xiàn)的LRMC多約束路由算法在鏈路帶寬、傳輸速率、時延、丟包率性能上的表現(xiàn)優(yōu)于SC算法，并且相較于SC算法運行時對業(yè)務(wù)QoS的保障，LRMC算法在QoS保障方面性能更穩(wěn)定。

5 總結(jié)

本文借助Mininet仿真系統(tǒng)，搭建、運行仿真SDN網(wǎng)絡(luò)，最后基于對傳統(tǒng)網(wǎng)絡(luò)QoS保障算法的研究，針對多類型業(yè)務(wù)QoS無法得到有效保障的問題，設(shè)計實現(xiàn)了一種基于SDN的LRMC多約束QoS路由算法。根據(jù)業(yè)務(wù)QoS需求建立了關(guān)于帶寬、延時、丟包率性能指標(biāo)的多約束數(shù)學(xué)模型，在Dijkstra算法基礎(chǔ)上結(jié)合拉格朗日松弛法和梯度迭代法迭代求解得到滿足約束條件的最優(yōu)路徑解。最后將LRMC多約束QoS路由算法算法實現(xiàn)部署運行在Mininet仿真網(wǎng)絡(luò)控制器中，在仿真網(wǎng)絡(luò)中對比其與單約束算法在連通時間收斂性和網(wǎng)絡(luò)性能上的表現(xiàn)。Mininet仿真結(jié)果表明，本LRMC路由算法運行時的連通時間較同等條件下的時延單約束算法連通時間更短、性能更優(yōu)更穩(wěn)定，結(jié)合SDN網(wǎng)絡(luò)架構(gòu)的可直接編程特性和集中控制特性可有效保障多類型業(yè)務(wù)QoS。