孫 杰，李 莉，沈蘇彬

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003)

一種基于QoS和動(dòng)態(tài)負(fù)載均衡的路由策略

孫 杰，李 莉，沈蘇彬

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003)

為了提高SDN網(wǎng)絡(luò)負(fù)載均衡調(diào)度的針對(duì)性和準(zhǔn)確性，設(shè)計(jì)了SAS(Scheduling According to Stickiness )算法。該算法提出了鏈路粘值的概念，用鏈路粘值預(yù)估調(diào)度對(duì)流性能影響的大小，通過優(yōu)先調(diào)度粘值低的流來(lái)減小調(diào)度對(duì)流性能的影響，達(dá)到優(yōu)化調(diào)度的目的。在重路由過程中，該算法兼顧了流的QoS需求，并用近似算法進(jìn)行多QoS約束的最優(yōu)路徑選擇?；贔loodlight開源控制平臺(tái)設(shè)計(jì)和實(shí)現(xiàn)了相應(yīng)的原型系統(tǒng)，并根據(jù)負(fù)載均衡效果和負(fù)載均衡生成流的QoS兩個(gè)測(cè)試目標(biāo)，設(shè)計(jì)和實(shí)現(xiàn)了測(cè)試的方案。實(shí)驗(yàn)測(cè)試結(jié)果表明，在不同QoS需求的數(shù)據(jù)流競(jìng)爭(zhēng)網(wǎng)絡(luò)資源、導(dǎo)致網(wǎng)絡(luò)負(fù)載偏離均衡狀態(tài)的情況下，相較DLB、LABERIO機(jī)制，提出的技術(shù)方案在提高帶寬利用率的同時(shí)可以兼顧分組流的QoS需求，并且可以降低對(duì)流性能的影響。

軟件定義網(wǎng)絡(luò)；路由策略；動(dòng)態(tài)負(fù)載均衡；鏈路粘值

0 引 言

隨著大量的網(wǎng)絡(luò)設(shè)備和服務(wù)的出現(xiàn)，SDN(Software-Defined Networking)[1]網(wǎng)絡(luò)也慢慢成為一個(gè)新的研究熱點(diǎn)。與傳統(tǒng)的分布式IP網(wǎng)絡(luò)的不同之處在于它對(duì)控制平面與轉(zhuǎn)發(fā)平面的分離。SDN網(wǎng)絡(luò)是一種不需要控制邏輯和數(shù)據(jù)轉(zhuǎn)發(fā)功能緊耦合在網(wǎng)絡(luò)設(shè)備上，控制器利用控制-轉(zhuǎn)發(fā)接口[2]對(duì)數(shù)據(jù)平面的交換機(jī)進(jìn)行集中式控制的新型網(wǎng)絡(luò)體系結(jié)構(gòu)。SDN交換機(jī)以提取并解析分組頭域，逐級(jí)與流表項(xiàng)進(jìn)行匹配，按照其中指定的動(dòng)作進(jìn)行處理和轉(zhuǎn)發(fā)的通信模式，可以靈活地實(shí)現(xiàn)節(jié)點(diǎn)的數(shù)據(jù)傳輸。新型網(wǎng)絡(luò)業(yè)務(wù)被廣泛應(yīng)用，網(wǎng)絡(luò)業(yè)務(wù)類型不斷增加，網(wǎng)絡(luò)擁堵越來(lái)越嚴(yán)重。實(shí)現(xiàn)負(fù)載均衡可以優(yōu)化利用網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)資源的使用率。研究SDN網(wǎng)絡(luò)負(fù)載均衡解決方案具有很大的實(shí)用價(jià)值。

已有一些經(jīng)典的SDN網(wǎng)絡(luò)負(fù)載均衡解決方案。比如，文獻(xiàn)[3]中提出的負(fù)載均衡模型,考慮到網(wǎng)絡(luò)擁塞和服務(wù)器負(fù)載，使用平均響應(yīng)時(shí)間和網(wǎng)絡(luò)最新狀態(tài)，為網(wǎng)絡(luò)應(yīng)用的請(qǐng)求合理分配。文獻(xiàn)[4]中提出了一種支持多服務(wù)的OpenFlow負(fù)載均衡,對(duì)于不同的服務(wù)有不同的控制器用于處理，不同的控制器的負(fù)載均衡算法選擇可以是不同的。文獻(xiàn)[5]中提出了基于通配符匹配的負(fù)載均衡算法，以發(fā)起請(qǐng)求的客戶端IP地址作為通配符前綴，接著用規(guī)則集來(lái)控制交換機(jī)，從而減少控制器進(jìn)行干預(yù)的次數(shù)，降低了平均請(qǐng)求延遲。

文中認(rèn)為不同類型的流其QoS受調(diào)度的影響程度不盡相同。網(wǎng)絡(luò)中的數(shù)據(jù)流有時(shí)延敏感的小數(shù)據(jù)流和吞吐量敏感的大數(shù)據(jù)流[6]。在網(wǎng)絡(luò)負(fù)載不均衡程度超過一定值時(shí)，在同樣都能起到均衡負(fù)載的情況下，調(diào)度前一種對(duì)QoS的影響要遠(yuǎn)大于后一種，所以應(yīng)該選擇后者調(diào)度。文中提出的調(diào)度策略不僅考慮到傳統(tǒng)流的分類，而且考慮到調(diào)度可能對(duì)流的QoS性能指標(biāo)產(chǎn)生的影響大小，因此更有針對(duì)性。這里將所引入的流的適合調(diào)度值借用了一個(gè)物理學(xué)中的概念-鏈路粘值(stickness)來(lái)表述，并使用改進(jìn)的動(dòng)態(tài)負(fù)載均衡算法更新鏈路粘值。

算法通過北向接口完成對(duì)流鏈路粘度的初始區(qū)分，這個(gè)過程其實(shí)是獲取業(yè)務(wù)對(duì)流鏈路粘度的需求過程。在改進(jìn)的動(dòng)態(tài)負(fù)載均衡算法更新下，多次被調(diào)度的流的鏈路粘值會(huì)不斷增大，對(duì)調(diào)度的拒絕程度越來(lái)越高。這時(shí)，即使是初始的鏈路粘值很高的流，也會(huì)被合理地調(diào)度到。在動(dòng)態(tài)重路由的過程中，算法兼顧了流的QoS需求，為流尋找一條有足夠資源、能滿足QoS要求的可行路徑。對(duì)于這種具有NP難度的多目標(biāo)選路問題，文中選擇了一種現(xiàn)有的帶多約束的最優(yōu)路徑算法-Iwata[7]，作為一個(gè)具體的計(jì)算方案。帶著這樣的目的，理論上便可以在滿足流QoS需求的同時(shí)，保證動(dòng)態(tài)負(fù)載均衡調(diào)度的針對(duì)性和準(zhǔn)確性。

1 相關(guān)技術(shù)分析

相較于傳統(tǒng)網(wǎng)絡(luò)中的負(fù)載均衡策略，在SDN網(wǎng)絡(luò)中主流的支持負(fù)載均衡機(jī)制都基于SDN控制器的全局視野。SDN控制器對(duì)網(wǎng)絡(luò)狀態(tài)進(jìn)行檢測(cè)，利用根據(jù)鏈路負(fù)載的實(shí)時(shí)狀態(tài)對(duì)影響負(fù)載均衡的最大流進(jìn)行調(diào)度的負(fù)載均衡策略。該策略的代表算法為L(zhǎng)ABERIO[8]。SDN控制器查詢鏈路負(fù)載的狀態(tài)作為動(dòng)態(tài)負(fù)載均衡的選路依據(jù)，每次都使用貪心策略選取當(dāng)前空閑帶寬最大的鏈路。該策略的代表算法為DLB[9]。

在算法LABERIO中，考慮到僅僅依靠SDN網(wǎng)絡(luò)的初始路由計(jì)算，即使在剛開始滿足負(fù)載均衡的需求，也會(huì)隨著網(wǎng)絡(luò)的變化變得不再滿足，并不能保證傳輸數(shù)據(jù)過程中的網(wǎng)絡(luò)動(dòng)態(tài)負(fù)載均衡。為此，需要對(duì)SDN網(wǎng)絡(luò)的狀態(tài)進(jìn)行周期更新，實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)負(fù)載均衡程度，對(duì)負(fù)載過重的鏈路上的流量進(jìn)行調(diào)度，以使網(wǎng)絡(luò)實(shí)現(xiàn)動(dòng)態(tài)負(fù)載均衡。對(duì)負(fù)載過重的鏈路上的流量進(jìn)行調(diào)度時(shí)，優(yōu)先對(duì)網(wǎng)絡(luò)中負(fù)載均衡影響最大的流進(jìn)行調(diào)度。但是這種算法忽略了流對(duì)QoS的要求，可能會(huì)使有些流因?yàn)檎{(diào)度而導(dǎo)致時(shí)延過大。算法對(duì)那些時(shí)延敏感的流并不合適。

在算法DLB中，將流作為更小的單元，采用了深度優(yōu)先的算法，開始從源節(jié)點(diǎn)向上傳輸?shù)礁邔哟蔚墓?jié)點(diǎn)直到第一層節(jié)點(diǎn)，然后繼續(xù)往下轉(zhuǎn)發(fā)目的節(jié)點(diǎn)。在每一跳DLB算法用貪心策略來(lái)選擇更大的空閑帶寬的鏈路。DLB算法在SDN網(wǎng)絡(luò)有著比傳統(tǒng)負(fù)載均衡算法更好的性能。但貪心路由決策沒考慮整個(gè)網(wǎng)絡(luò)的負(fù)載分布，由算法選出的源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑可能并不合適。

上述介紹的機(jī)制都是基于SDN網(wǎng)絡(luò)的動(dòng)態(tài)重路由機(jī)制[8]并已驗(yàn)證其有效性。同樣是通過動(dòng)態(tài)的重路由機(jī)制解決SDN網(wǎng)絡(luò)中的負(fù)載均衡問題,文中采用的算法更多關(guān)注了調(diào)度對(duì)流的性能所造成的影響。顯而易見，參照測(cè)算出的重路由對(duì)流產(chǎn)生的影響信息，盡量選擇影響小的流進(jìn)行重路由，比僅在初始設(shè)定流的優(yōu)先級(jí)更有針對(duì)性和準(zhǔn)確性。SAS算法中用鏈路粘值作為流拒絕重路由程度的量化的值。動(dòng)態(tài)地測(cè)算流的鏈路粘值，并按照鏈路粘值來(lái)對(duì)流進(jìn)行調(diào)度，能較好地解決SDN網(wǎng)絡(luò)中的動(dòng)態(tài)負(fù)載均衡問題。

2 問題分析與方案設(shè)計(jì)

2.1 動(dòng)態(tài)負(fù)載均衡的路由方案

在介紹基于QoS和動(dòng)態(tài)負(fù)載均衡的路由方案之前，這里先定義一個(gè)負(fù)載均衡參數(shù)ε(t)，用來(lái)描述在t時(shí)刻全網(wǎng)負(fù)載均衡的程度。ε(t)值越趨近于0表示全網(wǎng)鏈路的負(fù)載越均衡，ε(t)值越大表示全網(wǎng)的負(fù)載越不均衡。ε(t)值的計(jì)算如式(1)所示。

(1)

(2)

(3)

其中，Bt表示在t時(shí)刻鏈路l:[il,jl,CAPl]上已傳輸?shù)目俠yte。每條鏈路上的Bt值都可以通過SDN數(shù)據(jù)統(tǒng)計(jì)機(jī)制來(lái)獲取。

這里需要設(shè)置一個(gè)負(fù)載均衡閾值ε*。ε*值的設(shè)置依據(jù)是不同ε*值會(huì)導(dǎo)致不同網(wǎng)絡(luò)吞吐量，研究吞吐量與ε*的變化關(guān)系并選取使得網(wǎng)絡(luò)吞吐量最大的ε值作為ε*。當(dāng)ε(t)在t時(shí)刻大于ε*(即網(wǎng)絡(luò)負(fù)載不均衡程度超出預(yù)設(shè)值時(shí))，觸發(fā)聯(lián)合路由方案啟動(dòng)負(fù)載均衡調(diào)度?？刂破鲗⒄业秸紦?jù)在最擁堵鏈路上且鏈路粘值最小的流，將其移動(dòng)到其他可用的路徑上。這里的可用路徑需要滿足兩個(gè)條件：路徑是包含首尾節(jié)點(diǎn)的通路；路徑上的所有鏈路可以滿足流f所屬類型c的QoS需求(即滿足式(5))。在計(jì)算出所有可用路徑的集合后，選擇其中負(fù)載最小的路徑作為流f的替換路徑。如果沒有可替換的路徑表明流f對(duì)當(dāng)前鏈路的依賴程度(即粘值)高出了預(yù)期，則為流f增加一個(gè)定值s作為新的sf再重新執(zhí)行啟動(dòng)負(fù)載均衡的調(diào)度。基于QoS和動(dòng)態(tài)負(fù)載均衡的路由方案步驟的具體描述如下：

步驟1：控制器不斷檢測(cè)網(wǎng)絡(luò)的負(fù)載均衡狀態(tài)，每隔ns計(jì)算一次網(wǎng)絡(luò)的負(fù)載均衡參數(shù)ε(t)值。如果ε(t)大于閾值ε*,執(zhí)行步驟2，否則繼續(xù)執(zhí)行步驟1。

步驟2：找出負(fù)載最大的鏈路，即loadij(t)值最大的鏈路l:[il,jl,CAPl]。執(zhí)行步驟3。

步驟3：找出鏈路l:[il,jl,CAPl]承載的所有流中鏈路粘值sf最小的流f。執(zhí)行步驟4。

步驟4：找出所有流f的可用替代路徑pf集合。路徑pf的首節(jié)點(diǎn)為ni、尾節(jié)點(diǎn)為nj(即為ni→nm→nj序列)，pf滿足式(2)。如果pf集合不為空則執(zhí)行步驟5，否則執(zhí)行步驟7。

步驟5：選擇pf集合中負(fù)載最小的路徑min(pf)(如果有多個(gè)負(fù)載最小的路徑，則選擇其中剩余帶寬最大的路徑)作為流f的替代路徑。執(zhí)行步驟6。

步驟6：刪除鏈路l:[il,jl,CAPl]上f的表項(xiàng)。安裝min(pf)上f的流表項(xiàng)，建立并關(guān)聯(lián)相應(yīng)計(jì)量表項(xiàng)。執(zhí)行步驟7。

步驟7：更新流f的鏈路粘值sf。如果流f遷移成功，執(zhí)行2.3中的流f鏈路粘值更新策略，未成功則sf加上一個(gè)常數(shù)值s作為新的sf。繼續(xù)執(zhí)行步驟1。至此，聯(lián)合路由選擇的一個(gè)周期結(jié)束。

基于QoS和動(dòng)態(tài)負(fù)載均衡的路由算法依據(jù)網(wǎng)絡(luò)當(dāng)前的負(fù)載均衡狀態(tài)對(duì)過載鏈路進(jìn)行動(dòng)態(tài)的流調(diào)度，通過數(shù)據(jù)流的鏈路粘值來(lái)描述數(shù)據(jù)流對(duì)流調(diào)度的拒絕程度，進(jìn)而得到應(yīng)當(dāng)對(duì)哪條流進(jìn)行調(diào)度。因此算法的時(shí)間復(fù)雜度直接取決于鏈路個(gè)數(shù)nl和數(shù)據(jù)流的個(gè)數(shù)nf，為O(nl*nf)。

2.2 基于QoS約束的選路策略

在SDN網(wǎng)絡(luò)這種基于流的網(wǎng)絡(luò)架構(gòu)中，可以區(qū)分并保證每一個(gè)業(yè)務(wù)流的服務(wù)質(zhì)量，完成最細(xì)粒度的服務(wù)質(zhì)量保證。而SDN網(wǎng)絡(luò)擁有的網(wǎng)絡(luò)全局視野更能夠滿足業(yè)務(wù)流對(duì)鏈路的需求。邊界交換機(jī)將數(shù)據(jù)流分類后，要為數(shù)據(jù)流分配能夠滿足數(shù)據(jù)流相應(yīng)需求的路徑。數(shù)據(jù)流f可以用源節(jié)點(diǎn)sf、目的節(jié)點(diǎn)df、服務(wù)類別cf這三個(gè)屬性來(lái)表示(f:[sf,df,cf],sf∈N,df∈N,cf∈C)。其中，C代表所有服務(wù)類別的集合。服務(wù)類別包含的參數(shù)包括數(shù)據(jù)速率rc、丟包率pc、時(shí)延tc和用來(lái)為動(dòng)態(tài)負(fù)載路由算法服務(wù)的初始鏈路粘度sc(c:[rc,pc,tc,sc])。這里借用了粘值(Stickiness)的物理學(xué)概念。物理學(xué)中的粘值[10]是指流體的內(nèi)摩擦表現(xiàn)出的宏觀屬性，這里的粘值表示服務(wù)類別c的數(shù)據(jù)流f對(duì)當(dāng)前的鏈路的依賴性或者稱為數(shù)據(jù)流對(duì)重路由的排斥程度。這個(gè)變量的定義將在2.3小節(jié)加以具體描述。

(4)

路由選擇需要考慮鏈路能否滿足數(shù)據(jù)流所屬類型的QoS值。當(dāng)網(wǎng)絡(luò)中增加一個(gè)新流f(流所屬類別的屬性為rnew,pnew,tnew和snew)。流f流經(jīng)的所有鏈路l都需要滿足式(5)～(7)。

(5)

(6)

(7)

其中，fl表示在鏈路l上承載所有的流集合；nf表示流f流經(jīng)的所有的交換機(jī)集合；CAPl表示鏈路l的最大容量;pfsrc，pfdst分別表示在流f轉(zhuǎn)發(fā)路徑的起始交換機(jī)fsrc和目的交換機(jī)fdst上已接收到的流f包的總數(shù)。

常規(guī)的網(wǎng)絡(luò)時(shí)延包含處理時(shí)延、排隊(duì)時(shí)延、傳輸時(shí)延、傳播時(shí)延。這里的tl不僅僅包含鏈路時(shí)延，文獻(xiàn)[12]將傳輸時(shí)延和傳播時(shí)延合起來(lái)作為鏈路時(shí)延(例如ns2仿真器)。這里的tl不僅包含傳輸時(shí)延和傳播時(shí)延，還包含了跟控制器的交互。因此，在式(7)中大于號(hào)右邊減去了節(jié)點(diǎn)ni和控制器交互的時(shí)延dc_ni。

為了方便計(jì)算tl，文中提出了用于SDN交換機(jī)的服務(wù)質(zhì)量監(jiān)測(cè)機(jī)制，即一種基于OpenFlow協(xié)議實(shí)現(xiàn)的鏈路時(shí)延測(cè)算機(jī)制。在LLDP(LinkLayerDiscoveryProtocol[13]，鏈路層發(fā)現(xiàn)協(xié)議)分組基礎(chǔ)上進(jìn)行改進(jìn)，采用鏈路時(shí)延監(jiān)測(cè)分組(LinkDelayDiscoveryPacket,LDDP)來(lái)監(jiān)測(cè)鏈路l從鏈路源節(jié)點(diǎn)nlsrc(nlsrc∈N)接受到分組到鏈路l目的節(jié)點(diǎn)nldst(nldst∈N)接受到分組的時(shí)延。LLDP是IEEE定義的一種鏈路層協(xié)議，被大部分網(wǎng)絡(luò)設(shè)備所支持，一些OpenFlow控制器利用該協(xié)議實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞陌l(fā)現(xiàn)功能。

而LDDP分組通過控制器發(fā)出分組到鏈路l的端節(jié)點(diǎn)。LDDP分組內(nèi)容包括鏈路l的源節(jié)點(diǎn)mac地址maclsrc、鏈路l的源節(jié)點(diǎn)端口portlsrc、控制器在nlsrc處理此LDDP分組時(shí)的時(shí)刻tlsrc(LDDP:[maclsrc,portlsrc,tlsrc])。LDDP分組發(fā)出后其中的動(dòng)作字段為轉(zhuǎn)發(fā)到節(jié)點(diǎn)的指定端口。LDDP分組從節(jié)點(diǎn)nlsrc的端口轉(zhuǎn)發(fā)出去，對(duì)端節(jié)點(diǎn)nldst將會(huì)收到傳入的LDDP分組，但它并不能識(shí)別這個(gè)LDDP分組，只當(dāng)普通數(shù)據(jù)報(bào)文處理，此LDDP分組將被交換機(jī)封裝成Packet-In消息發(fā)送到控制器中?？刂破鲗DDP分組中的maclsrc和tlsrc消息記錄下來(lái)，根據(jù)maclsrc和當(dāng)前節(jié)點(diǎn)mac標(biāo)記出鏈路l，根據(jù)當(dāng)前系統(tǒng)時(shí)刻tldst、l源節(jié)點(diǎn)處理時(shí)刻tlsrc即可求出鏈路l的時(shí)延t1，其值如式(8)所示。

tl=tldst-tlsrc

(8)

文中對(duì)控制器c與節(jié)點(diǎn)ni間的時(shí)延dc_ni(包括控制器處理發(fā)送OpenFlow請(qǐng)求到控制器接收OpenFlow響應(yīng)之間的時(shí)延)的計(jì)算，這里的OpenFlow請(qǐng)求和響應(yīng)，文中使用的是特征請(qǐng)求消息和特性響應(yīng)消息。在控制器向?qū)⒐?jié)點(diǎn)ni發(fā)送特征請(qǐng)求消息時(shí)記錄下當(dāng)前時(shí)刻tc_ni，當(dāng)控制器接收到相應(yīng)節(jié)點(diǎn)的特性響應(yīng)消息時(shí)記錄下時(shí)刻tni_c。如此，dc_ni的值通過式(9)得出。將式(8)和式(9)帶入式(7)，即可完成對(duì)路徑是否滿足流時(shí)延要求的判斷。

(9)

因此，在進(jìn)行重路由之前需要先選取全網(wǎng)所有滿足式(5)～(7)的鏈路。選出的鏈路信息用來(lái)為動(dòng)態(tài)負(fù)載均衡重路由選取提供拓?fù)浣Y(jié)構(gòu)。

當(dāng)新的流需要進(jìn)行重路由時(shí)，它需要的路徑不僅要滿足2.1節(jié)的替換路徑的要求，還需要滿足式(5)～(7)對(duì)鏈路的要求。這種多目標(biāo)的選路策略是有NP難度的，因此文中采用了一種現(xiàn)有的帶多約束條件的QoS路由算法-Iwata[7]，作為一種具體的計(jì)算方案。Iwata算法先以一個(gè)QoS度量為關(guān)鍵字來(lái)計(jì)算最短路徑，然后檢測(cè)該路徑是否滿足其他QoS度量；如不滿足，則選取另一QoS度量來(lái)計(jì)算最短路徑，同樣檢測(cè)該路徑是否滿足剩余的QoS度量；如此反復(fù)直到找到一條滿足所有QoS度量的可行路徑。

2.3 分組流的鏈路粘值更新策略

為了使得網(wǎng)絡(luò)達(dá)到動(dòng)態(tài)負(fù)載均衡狀態(tài)，需要解決兩個(gè)問題：網(wǎng)絡(luò)鏈路過載發(fā)生的檢測(cè)和檢測(cè)到過載發(fā)生后的處理。這兩個(gè)問題已在2.1小節(jié)解答了。一旦鏈路發(fā)生過載，應(yīng)對(duì)鏈路上的哪個(gè)流重路由，使網(wǎng)絡(luò)狀態(tài)恢復(fù)負(fù)載均衡。需要對(duì)不同的流進(jìn)行區(qū)分，不同的流可以簡(jiǎn)單分為對(duì)吞吐量敏感的流和對(duì)延時(shí)敏感的流?？紤]到延時(shí)敏感流傳輸時(shí)間相對(duì)較短，改變其路徑很可能會(huì)增加延遲和開銷，因此應(yīng)遷移非延時(shí)敏感流[14]。利用概念粘值，鏈路粘值sf表示數(shù)據(jù)流f對(duì)遷移的拒絕程度。而前面提到的不同的流(吞吐量敏感的流和對(duì)延時(shí)敏感的流)對(duì)更改路徑的成本高低，都可以簡(jiǎn)單地用對(duì)遷移的拒絕程度高或低即鏈路粘值sf來(lái)表示。計(jì)算鏈路粘值如式(10)所示。

(10)

其中，sfl表示f最近一次sf值；ufl表示最近一次遷移對(duì)數(shù)據(jù)流的影響值。

通過式(10)可以看出，如果數(shù)據(jù)流f從未遷移過，它會(huì)有一個(gè)初始值sc。這個(gè)值路由模塊執(zhí)行時(shí)為數(shù)據(jù)流區(qū)分的服務(wù)類型c所包含的屬性sc。這個(gè)sc其實(shí)就是控制器根據(jù)分類機(jī)制為數(shù)據(jù)流f設(shè)置的初始粘值?？紤]到網(wǎng)絡(luò)的動(dòng)態(tài)性，那些被遷移的流的鏈路粘值只有根據(jù)遷移對(duì)流的影響值來(lái)動(dòng)態(tài)更新，才能保證sf的準(zhǔn)確性。并且式中sf的計(jì)算過程實(shí)際為一個(gè)迭代過程，每一次遷移的影響值都會(huì)被考慮在內(nèi)。這樣就保證了一些初始粘值較小或者每次的遷移影響值較小的流，不會(huì)被頻繁調(diào)度，保證了流調(diào)度的合理性。式(10)中影響值ufl可以通過對(duì)SDN數(shù)據(jù)統(tǒng)計(jì)信息的計(jì)算來(lái)完成。ufl的值如式(11)所示。

ufl=α*dfl+β*bfl

(11)

其中，dfl表示最近一次遷移流f丟包率的變化程度；bfl表示最近一次遷移流f傳輸帶寬的變化程度；α和β分別表示dfl、bfl在影響值ufl中所占的比例。

dfl，bfl分別通過式(12)和式(13)計(jì)算獲得。

(12)

(13)

其中，pt1表示t1時(shí)刻流f的總丟包數(shù)；bt1表示t1時(shí)刻流f的已傳輸?shù)目俠yte。

控制器在流遷移前隔ms讀取一次鏈路的統(tǒng)計(jì)信息，在流遷移后隔ns讀取一次鏈路的統(tǒng)計(jì)信息。兩次統(tǒng)計(jì)信息的比值準(zhǔn)確反映了鏈路遷移對(duì)流f的丟包率和帶寬影響。

控制器記錄并更新每條流的最新的鏈路粘值。當(dāng)SDN網(wǎng)絡(luò)發(fā)生過載時(shí)，控制器對(duì)比過載鏈路上所承載的流的鏈路粘值并決定對(duì)哪條流進(jìn)行流調(diào)度。關(guān)于根據(jù)鏈路粘值進(jìn)行流調(diào)度以及調(diào)度后的路由策略已在2.1小節(jié)說明了。

由上可知，SAS是一種基于QoS和動(dòng)態(tài)負(fù)載均衡的路由策略，所以在實(shí)驗(yàn)部分需要使用不同類別流傳輸對(duì)動(dòng)態(tài)負(fù)載均衡的實(shí)現(xiàn)進(jìn)行功能測(cè)試，使用不同的傳輸速率對(duì)使用SAS機(jī)制后的帶寬、丟包率、抖動(dòng)變化進(jìn)行性能分析。

3 實(shí)驗(yàn)搭建及性能分析

實(shí)驗(yàn)對(duì)SAS算法系統(tǒng)軟件進(jìn)行測(cè)試，測(cè)試環(huán)境如圖1所示。在源末主機(jī)上部署iperf發(fā)包工具，模擬端到端的不同業(yè)務(wù)流的傳輸環(huán)境。在兩種業(yè)務(wù)流傳輸情況下分別執(zhí)行LABERIO、DLB以及文中的SAS系統(tǒng)，統(tǒng)計(jì)各機(jī)制運(yùn)行過程中帶寬、丟包率、抖動(dòng)等性能指標(biāo)來(lái)進(jìn)行比較。

3.1 實(shí)驗(yàn)環(huán)境搭建

搭建SDN實(shí)驗(yàn)網(wǎng)絡(luò)。首先在一臺(tái)DELL服務(wù)器上部署最新版本floodlight控制器，作為控制層設(shè)備。其次，由于目前OpenFlow物理交換機(jī)價(jià)格昂貴，文中選用一款開源的OpenFlow軟件交換機(jī)OVS安裝在三臺(tái)DELL臺(tái)式機(jī)上作為數(shù)據(jù)層轉(zhuǎn)發(fā)設(shè)備。交換機(jī)和控制器的主機(jī)系統(tǒng)均為32位Ubuntu 12.04，而通信的主機(jī)節(jié)點(diǎn)均為Windows7系統(tǒng)。

圖1 測(cè)試網(wǎng)絡(luò)拓?fù)鋱D

實(shí)驗(yàn)中，三臺(tái)OVS軟件換機(jī)分別與控制器相連受控制器控制。文中將控制器IP地址設(shè)置為192.168.0.150，交換器控制端口IP地址分別設(shè)置為192.168.0.151，192.168.0.152和192.168.0.153。將通信主機(jī)與三臺(tái)交換機(jī)中的任意一臺(tái)相連，通信主機(jī)分別運(yùn)行數(shù)據(jù)傳輸?shù)目蛻舳撕头?wù)器端(文中是用iperf發(fā)包工具)用于發(fā)送和請(qǐng)求數(shù)據(jù)分組。設(shè)置負(fù)載均衡閾值ε*為1%，粘值增量常數(shù)s為1。

3.2 實(shí)驗(yàn)性能評(píng)估指標(biāo)

文中使用平均帶寬利用率、平均丟包率和平均抖動(dòng)等性能指標(biāo)對(duì)負(fù)載均衡算法的性能進(jìn)行評(píng)估。

(1)平均帶寬利用率。

指定帶寬arf是指由客戶機(jī)發(fā)送流的帶寬，而實(shí)際帶寬rrf是指服務(wù)器實(shí)際獲取的流帶寬。由于傳輸期間可能發(fā)生網(wǎng)絡(luò)擁塞將導(dǎo)致分組丟失，從而服務(wù)器接收的實(shí)際帶寬小于或等于由客戶機(jī)發(fā)送的指定帶寬。平均帶寬利用率α是指每條流實(shí)際獲得的帶寬與其所指定帶寬的比值的平均值。

(14)

平均帶寬利用率反映了網(wǎng)絡(luò)的均衡程度，利用率越高說明網(wǎng)絡(luò)的負(fù)載越均衡。

(2)平均丟包率百分比。

由SDN統(tǒng)計(jì)機(jī)制獲得每條流的丟包信息，丟包數(shù)與傳輸指定的數(shù)目的比值就是這條流的丟包率。平均丟包率百分比β是指所有流的丟包率的平均值，如式(7)所示。平均丟包率百分比越大說明網(wǎng)絡(luò)擁塞程度越高，流的QoS傳輸效果越差。

(15)

(3)平均抖動(dòng)。

根據(jù)iperf客戶端工具輸出的測(cè)試報(bào)告，得到每個(gè)流的抖動(dòng)jf。平均丟包率百分比γ是指所有流的抖動(dòng)的平均值。平均抖動(dòng)越大則說明流的QoS傳輸效果越差。

(16)

3.3 實(shí)驗(yàn)結(jié)果分析

圖2是在不同業(yè)務(wù)流傳輸時(shí)，三項(xiàng)機(jī)制的平均帶寬利用率比較。

圖2 多業(yè)務(wù)流時(shí)不同機(jī)制對(duì)平均帶寬利用率的影響

從圖中可以看到，隨著流量負(fù)荷增加，三種算法的平均帶寬利用率在逐步下降。SAS算法在平均帶寬利用率上表現(xiàn)一般。甚至在高流量負(fù)荷時(shí)，比LABERIO表現(xiàn)要差。尤其在客戶端發(fā)送速率增加至6 Mbps后，利用率平均低了3%左右。因?yàn)樵谥刎?fù)荷之下，LABERIO算法這種優(yōu)先對(duì)網(wǎng)絡(luò)中占用帶寬最多的流進(jìn)行調(diào)度的機(jī)制，雖然忽略了流對(duì)QoS的要求，但負(fù)載均衡效果更好。在重負(fù)荷之下DBL算法的單跳最優(yōu)策略更容易引發(fā)網(wǎng)絡(luò)的局部擁塞，增大了報(bào)文的丟包率，降低了數(shù)據(jù)流的帶寬利用率，而SAS算法在考慮全局路徑負(fù)載情況后做出的選路降低了發(fā)生擁塞的概率，相比于DBL有更高的帶寬利用率。

隨著數(shù)據(jù)傳輸速率的增加，網(wǎng)絡(luò)動(dòng)態(tài)的調(diào)整，重新尋找滿足流QoS要求的可行路徑。相較于DLB、LABERIO機(jī)制，SAS算法使用了測(cè)算流QoS變化的負(fù)載均衡改進(jìn)策略，優(yōu)勢(shì)在于提高了流的負(fù)載均衡調(diào)度的針對(duì)性和準(zhǔn)確性。

SAS通過改進(jìn)的動(dòng)態(tài)負(fù)載均衡算法，按鏈路粘值為流進(jìn)行調(diào)度。鏈路粘值考慮到了丟包率的影響，優(yōu)先調(diào)度對(duì)丟包率影響較小的流。由于SAS是多目標(biāo)的計(jì)算綜合最優(yōu)結(jié)果的算法，SAS相比LABERIO這種單純考慮負(fù)載均衡效果的算法，SAS會(huì)在負(fù)載均衡調(diào)度時(shí)考慮到調(diào)度對(duì)流丟包率的影響，優(yōu)先調(diào)度丟包率影響較小的流而不是對(duì)負(fù)載均衡影響最大的流，因此會(huì)產(chǎn)生更低的網(wǎng)絡(luò)丟包率。作為代價(jià)，SAS算法在平均帶寬利用率上表現(xiàn)一般，甚至在高流量負(fù)荷時(shí)，比LABERIO表現(xiàn)要差。

圖3給出了3種算法的平均丟包率的實(shí)驗(yàn)結(jié)果。

圖3 多業(yè)務(wù)流時(shí)不同機(jī)制對(duì)平均丟包率的影響

從平均丟包率隨流量負(fù)荷變化而變化的情況看，SAS平均丟包率最低，LABERIO平均丟包率低于DLB。整體上LABERIO好于DLB，這歸功于全局選路降低了擁塞出現(xiàn)的概率，減少了需經(jīng)過擁塞路徑才能遞交的報(bào)文。SAS丟包率的變化趨勢(shì)跟其他算法一致，在具體數(shù)值上小了幾個(gè)百分點(diǎn)。當(dāng)客戶端發(fā)送速率達(dá)到9 Mbps時(shí)，三種算法的平均丟包率都超過了50%，這也說明當(dāng)網(wǎng)絡(luò)流量負(fù)荷較高時(shí)，網(wǎng)絡(luò)中各鏈路都較為擁堵，報(bào)文在交換機(jī)中丟包率會(huì)更高。SAS算法在平均丟包率上表現(xiàn)相對(duì)較好，但在高流量負(fù)荷時(shí)丟包率同樣很高。跟現(xiàn)有方案相比，SAS在丟包率表現(xiàn)上有一定程度的改進(jìn)。

圖4給出了三種算法平均抖動(dòng)的實(shí)驗(yàn)結(jié)果。

圖4 多業(yè)務(wù)流時(shí)不同機(jī)制對(duì)平均抖動(dòng)的影響

從整個(gè)曲線上看,SAS處在最下方，LABERIO處在DLB的下方。SAS在平均抖動(dòng)上性能要優(yōu)于LABERIO和DLB。曲線開始的一段時(shí)間內(nèi)，抖動(dòng)呈上升趨勢(shì)，這是因?yàn)閿?shù)據(jù)流剛剛開始產(chǎn)生，網(wǎng)絡(luò)中同時(shí)傳輸?shù)臄?shù)據(jù)流還未達(dá)到最大值，只有部分鏈路上有流量經(jīng)過。當(dāng)傳輸?shù)臄?shù)據(jù)流達(dá)到4 Mpbs時(shí)，抖動(dòng)也基本達(dá)到峰值，這之后的變化幅度相對(duì)更小。

從圖4中的抖動(dòng)變化能夠看出LABERIO平均抖動(dòng)性能優(yōu)于DLB，相對(duì)于DLB流量分布更為均勻，網(wǎng)絡(luò)中的流量分配更為均衡。而LABERIO是對(duì)網(wǎng)絡(luò)中影響負(fù)載均衡的最大流進(jìn)行調(diào)度，當(dāng)調(diào)度到時(shí)延敏感的數(shù)據(jù)流時(shí)，肯定會(huì)出現(xiàn)流的抖動(dòng)波動(dòng)較大的現(xiàn)象。SAS按流調(diào)度對(duì)流受調(diào)度影響的歷史信息進(jìn)行流調(diào)度，優(yōu)先對(duì)受調(diào)度影響較小的流。因此，會(huì)產(chǎn)生更低的平均抖動(dòng)。在具體數(shù)值上，LABERIO和DLB雖然比文中方案在數(shù)值上高了零點(diǎn)幾毫秒，但數(shù)據(jù)的變化趨勢(shì)相似，SAS的表現(xiàn)相對(duì)較好。跟現(xiàn)有方案相比，SAS在抖動(dòng)表現(xiàn)上有一定程度的改進(jìn)。

4 結(jié)束語(yǔ)

文中從調(diào)度會(huì)對(duì)流QoS產(chǎn)生影響的角度，盡可能利用流的調(diào)度受影響的歷史信息，提出了一種基于QoS和動(dòng)態(tài)負(fù)載均衡的路由策略SAS。在floodlight控制器平臺(tái)上編寫實(shí)現(xiàn)SAS算法并與DLB、LABERIO進(jìn)行對(duì)比。統(tǒng)計(jì)各項(xiàng)性能指標(biāo)可以看出，SAS算法按照流的鏈路粘值進(jìn)行調(diào)度，可以保證在滿足不同業(yè)務(wù)流QoS需求的同時(shí)，有效提高帶寬利用率，產(chǎn)生較低的抖動(dòng)和丟包率，提高SDN網(wǎng)絡(luò)路由轉(zhuǎn)發(fā)的效率。

[1] Open Networking Foundation.Software-defined networking:the new norm for networks[EB/OL].2012.https://www.opennetworking.org/sdn-resources/sdn-library/whitepapers.

[2] 沈蘇彬.軟件定義聯(lián)網(wǎng)的建模與分析[J].南京郵電大學(xué)學(xué)報(bào):自然科學(xué)版,2014,34(3):1-9.

[3] 張園園.利用openflow技術(shù)實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡[D/OL].[2010-12-09].http://www.paper.edu.cn/releasepaper/content/201012-258.

[4] Handigol N,Seetharaman S,Flajslik M,et al.Plug-n-Serve:load-balancing web traffic using OpenFlow[J].ACM Sigcomm Demo,2009,4(5):6.

[5] Koerner M, Kao O. Multiple service load-balancing with OpenFlow[C]//IEEE international conference on high performance switching & routing.[s.l.]:IEEE,2012:210-214.

[6] Benson T,Akella A,Maltz D A.Network traffic characteristics of data centers in the wild[C]//Proceedings of the 10th ACM SIGCOMM conference on Internet measurement.[s.l.]:ACM,2010:267-280.

[7] Fujita N,Iwata A.Adaptive and efficient multiple path pre-computation for QoS routing protocols[C]//Global telecommunications conference.[s.l.]:IEEE,2001:2215-2219.

[8] Long H,Shen Y,Guo M,et al.LABERIO:dynamic load-balanced routing in OpenFlow-enabled networks[C]//IEEE 27th international conference on advanced information networking and applications.[s.l.]:IEEE,2013:290-297.

[9] Li Y,Pan D.OpenFlow based load balancing for Fat-Tree networks with multipath support[C]//Proceedings of 12th IEEE international conference on communications.Budapest,Hungary:IEEE,2013:1-5.

[10] Kovtun P K,Son D T,Starinets A O.Viscosity in strongly interacting quantum field theories from black hole physics[J].Physical Review Letters,2005,94(11):111601.

[11] Open Networking Foundation.OpenFlow switch specification,version1.3[EB/OL].2012.https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.0.pdf.

[12] Issariyakul T, Hossain E. Introduction to network simulator NS2[M].[s.l.]:Springer-Verlag,2012.

[13] Surhone L M,Tennoe M T,Henssonow S F,et al.Link layer discovery protocol[M].[s.l.]:Betascript Publishing,2010.

[14] 樊自甫,伍春玲,王金紅.基于SDN架構(gòu)的數(shù)據(jù)中心網(wǎng)絡(luò)路由算法需求分析[J].電信科學(xué),2015,31(2):36-45.

A Routing Strategy Based on QoS and Dynamic Load Balancing

SUN Jie，LI Li，SHEN Su-bin

(School of Computer Science & Technology,School of Software，Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In order to improve pertinence and accuracy of network load balancing scheduling for SDN (Software-Defined Networking),a SAS algorithm is designed.This algorithm puts forward the concept of link stickiness,and applies link stickiness to estimate the impacts of scheduling on flow performance,by preferentially scheduling flow with low stickiness to reduce the impacts of scheduling on flow performance,so as to achieve the purpose of optimized scheduling.In the process of re-routing,it takes QoS needs of flow into consideration,and applies approximation algorithm to calculate the optimal route under multi-QoS constraints.Then a prototype system is designed and implemented based on Floodlight,an open control platform.Aiming at two test targets,including the load_balancing effect and its generated flows’ QoS,the test approach is designed and implemented.Experimental test results show that in case of different QoS requirement flows competing for limited network resources and resulting in network load deviations from the balance state,compared with DLB and LABERIO,the technology approach proposed can improve the bandwidth utilization while fulfilling the requirements of QoS on flow,and reduce the influence on flow’s performance.

Software-Defined Networking;routing strategy;dynamic load balancing;link stickness

2016-01-18

2016-05-10

時(shí)間：2016-10-24

江蘇省未來(lái)網(wǎng)絡(luò)前瞻性研究資助項(xiàng)目(BY2013095-1-08)

孫 杰(1990-),男，碩士研究生，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)；沈蘇彬，博士生導(dǎo)師，研究方向?yàn)橛?jì)算網(wǎng)絡(luò)、下一代電信網(wǎng)及網(wǎng)絡(luò)安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1113.028.html

TP392

A

1673-629X(2016)11-0188-07

10.3969/j.issn.1673-629X.2016.11.041