基于SDN的云數(shù)據(jù)App-RS路由算法

文杰斌，廖海洲

(湖南郵電職業(yè)技術(shù)學(xué)院， 長(zhǎng)沙 410015)

基于SDN的云數(shù)據(jù)App-RS路由算法

文杰斌，廖海洲

(湖南郵電職業(yè)技術(shù)學(xué)院， 長(zhǎng)沙 410015)

當(dāng)前,隨著云數(shù)據(jù)服務(wù)應(yīng)用的普及,因不同類型的云業(yè)務(wù)應(yīng)用的網(wǎng)絡(luò)需求不同，故不能平等地對(duì)待所有類型的云業(yè)務(wù)應(yīng)用。為此，提出了一種App-RS(application-aware routing scheme)路由算法。對(duì)于calss 1業(yè)務(wù)應(yīng)用，該算法考慮端對(duì)端的時(shí)延及鏈路負(fù)載；對(duì)于calss 2業(yè)務(wù)應(yīng)用，考慮延遲偏差及鏈路負(fù)載；對(duì)于其他業(yè)務(wù)應(yīng)用，只考慮鏈路負(fù)載。仿真結(jié)果表明：APP-RS路由算法比CORouting路由算法在3類業(yè)務(wù)應(yīng)用中的平均吞吐量分別高出9.86%、4.53%和4.07%，相比CORouting路由算法中的calss 1業(yè)務(wù)應(yīng)用平均點(diǎn)對(duì)點(diǎn)延遲少25.47%，相比CORouting路由算法中的class 2業(yè)務(wù)應(yīng)用平均時(shí)延偏差少49.65%。因此，APP-RS路由算法比CORouting路由算法更能滿足SDN云數(shù)據(jù)中心所有class業(yè)務(wù)應(yīng)用對(duì)網(wǎng)絡(luò)的需求。

SDN；云數(shù)據(jù)；App-RS；路由算法

在云數(shù)據(jù)應(yīng)用中，因不同類型的業(yè)務(wù)應(yīng)用對(duì)網(wǎng)絡(luò)資源的要求不同，所以對(duì)不同類型的業(yè)務(wù)應(yīng)用進(jìn)行平等對(duì)待并不合適?，F(xiàn)已提出的在云數(shù)據(jù)中心業(yè)務(wù)應(yīng)用的感知資源(如CPU、GPU、內(nèi)存、磁盤I/O)管理方法用于預(yù)測(cè)應(yīng)用資源需求及盡力滿足這些業(yè)務(wù)應(yīng)用需求,但是這些方法沒(méi)有考慮網(wǎng)絡(luò)應(yīng)用需求。

應(yīng)用感知路由是一種很多前途的網(wǎng)絡(luò)資源云數(shù)據(jù)中心方案，可滿足不同類型業(yè)務(wù)應(yīng)用的網(wǎng)絡(luò)需求。針對(duì)不同網(wǎng)絡(luò)需求可分配切實(shí)可行的路由來(lái)滿足不同業(yè)務(wù)應(yīng)用。例如：流媒體視訊業(yè)務(wù)應(yīng)用較Web業(yè)務(wù)應(yīng)用就需要更多的帶寬；VoIP業(yè)務(wù)應(yīng)用相對(duì)P2P文件共享業(yè)務(wù)應(yīng)用則需要較低的網(wǎng)絡(luò)時(shí)遲。然而，通過(guò)傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這些目標(biāo)并不容易，但在SDN網(wǎng)絡(luò)中讓網(wǎng)管通過(guò)外部控制器來(lái)管理自身網(wǎng)絡(luò)變得很有前途，即通過(guò)SDN基于網(wǎng)絡(luò)應(yīng)用需求來(lái)實(shí)現(xiàn)應(yīng)用感知路由成為可能。

1 SDN網(wǎng)絡(luò)中OpenFlow結(jié)構(gòu)

在SDN網(wǎng)絡(luò)結(jié)構(gòu)中，因控制面和數(shù)據(jù)面獨(dú)立，所以網(wǎng)絡(luò)控制變得直接可程序化。另外，SDN網(wǎng)絡(luò)中需通過(guò)控制面協(xié)議來(lái)保證數(shù)據(jù)面通信。當(dāng)前較高級(jí)的協(xié)議是OpenFlow，圖1為OpenFlow結(jié)構(gòu)。圖1中：OpenFlow交換機(jī)及控制器通過(guò)SSL(secure sockets layer)通信，當(dāng)OpenFlow交換機(jī)接收一個(gè)在流表中不匹配的封包時(shí)，它會(huì)通過(guò)安全信道轉(zhuǎn)發(fā)此封包到控制器，然后由控制器決定怎么處理此封包并修改OpenFlow交換機(jī)中的流表。通過(guò)此方式，能以當(dāng)前網(wǎng)絡(luò)信息(如鏈路負(fù)載、時(shí)延及時(shí)延偏差)來(lái)直接控制OpenFlow控制器以確定其路由。

2 App-RS算法

App-RS算法是一種基于SDN云數(shù)據(jù)中心業(yè)務(wù)應(yīng)用的感知路由算法。該算法考慮所有class類業(yè)務(wù)應(yīng)用并把這些應(yīng)用根據(jù)它們對(duì)網(wǎng)絡(luò)的需求分成3種主要類型。每種類型業(yè)務(wù)應(yīng)用通過(guò)考慮不同參數(shù)(如鏈路負(fù)載、時(shí)延或時(shí)延偏差)用不同的路由方案來(lái)進(jìn)行處理。

2.1 業(yè)務(wù)應(yīng)用分類

在App-RS算法中，把所需傳輸?shù)臉I(yè)務(wù)應(yīng)用數(shù)據(jù)根據(jù)各自所容忍的時(shí)遲、時(shí)延偏差及包丟失率分為3類，業(yè)務(wù)應(yīng)用分類及對(duì)傳輸?shù)囊笕绫?所示。

表1 業(yè)務(wù)應(yīng)用分類

2.2 App-RS路由方案

在App-RS路由方案中,對(duì)于不同類型的業(yè)務(wù)應(yīng)用使用不同的路由算法。對(duì)于class 1類業(yè)務(wù)應(yīng)用，需找到一條低時(shí)延路徑，同時(shí)要通過(guò)路徑負(fù)載平衡實(shí)現(xiàn)低丟包率，只要時(shí)延不超過(guò)一定值，給用戶的感覺(jué)效果如同實(shí)時(shí)應(yīng)用。對(duì)于class 2類業(yè)務(wù)應(yīng)用，需找到一條低時(shí)延偏差路徑，同時(shí)也要通過(guò)路徑負(fù)載平衡實(shí)現(xiàn)低丟包率，只要時(shí)延偏差不超過(guò)某值，流類業(yè)務(wù)應(yīng)用能被大家接受。對(duì)于class 3類業(yè)務(wù)應(yīng)用，只需找到一條最小擁擠路徑以確保低丟包率。

對(duì)于class 1和class 2業(yè)務(wù)應(yīng)用，目標(biāo)是找到一條最小鏈路負(fù)載及滿足時(shí)延上限的剩余路徑。其解決思路與已通過(guò)使用LARAC(拉格朗日松弛)算法解決的時(shí)延約束下的最小代價(jià)路徑問(wèn)題類似。LARAC算法流程如下：

procedure LARAC(G,s,t,c,d,Dmax)

rC← Dijkstra(G,s,t,c)

if fD(rC) ≦ Dmaxthen return rC

else rD← Dijkstra(G,s,t,d)

if fD(rD) > Dmaxthen return“no feasible solution”

else

while true do

r ← Dijkstra(G,s,t,Cλ)

if fλ(r)= fλ(rC)then return rD

else if fD(r)≦ Dmaxthen rD←r

else rC← r

end if

end while

end if

end if

end procedure

本文采用LARAC算法來(lái)為class 1和class 2業(yè)務(wù)應(yīng)用找到合適的路徑，表2為L(zhǎng)ARAC路由算法所用的符號(hào)定義。

表2 LARAC路由算法所用的符號(hào)定義

App-RS路由算法流程如圖2所示。服務(wù)器通過(guò)檢查某業(yè)務(wù)應(yīng)用的App-ID確定其業(yè)務(wù)應(yīng)用所屬的class。獲取網(wǎng)絡(luò)最新信息并針對(duì)不同業(yè)務(wù)應(yīng)用使用不同路由算法。例如：對(duì)于class 1業(yè)務(wù)應(yīng)用(即實(shí)時(shí)業(yè)務(wù)應(yīng)用)，使用LARAC(G,s,t,c,d,Dmax)算法來(lái)找到一條d是時(shí)延代價(jià)矩陣中的系數(shù)且Dmax是點(diǎn)對(duì)點(diǎn)時(shí)延上限值的路徑；對(duì)于class 2業(yè)務(wù)應(yīng)用(即視頻流業(yè)務(wù)應(yīng)用)，也是使用LARAC(G,s,t,c,d,Dmax)算法來(lái)找到一條d是時(shí)延偏差代價(jià)矩陣中的系數(shù)且Dmax是點(diǎn)對(duì)點(diǎn)時(shí)延偏差上限值的路徑；對(duì)于class 3業(yè)務(wù)應(yīng)用(即其他業(yè)務(wù)應(yīng)用)，則使用Dijkstra(G,s,t,c)算法來(lái)找到一條最小擁擠路徑。在以上3類業(yè)務(wù)應(yīng)用中，c都是其鏈路負(fù)載矩陣系數(shù)。一旦確定了應(yīng)用業(yè)務(wù)路徑，則對(duì)應(yīng)的流記錄就會(huì)被沿著這條路徑添加到每個(gè)交換機(jī)。

圖2 App-RS算法流程

2.3 App-RS算法應(yīng)用舉例

以圖3的App-RS路由算法中class 1業(yè)務(wù)應(yīng)用舉例,而對(duì)于class 2業(yè)務(wù)應(yīng)用則與此類似，只是將class 1中的時(shí)延約束條件改為時(shí)延偏差。而對(duì)于class 3業(yè)務(wù)應(yīng)用，則采用著名的Dijkstra’s算法。因此，以下僅以class 1業(yè)務(wù)應(yīng)用舉例介紹。

圖3 App-RS算法舉例

圖3中關(guān)鍵是找到從節(jié)點(diǎn)1到節(jié)點(diǎn)6不超過(guò)時(shí)延上限1.4的最小負(fù)載路徑。在表3中，隨著λ的增加，時(shí)延fD(r)在fC(r)+λfD(r)合計(jì)代價(jià)中的權(quán)重將提高。當(dāng)λ=0時(shí)，最小鏈路負(fù)載是1—2—4—6，但是其時(shí)延大于1.4，不滿足要求。而路徑1—3—2—5—6和1—3—5—6雖然都滿足時(shí)延約束條件，但是1—3—2—5—6路徑具有更小的鏈路負(fù)載fC(r)，所以LARAC路由算法將選擇1—3—2—5—6作為節(jié)點(diǎn)1到節(jié)點(diǎn)6的數(shù)據(jù)路徑。

LARAC路由算法的目標(biāo)是找到一個(gè)最好λ值，對(duì)應(yīng)此λ值的鏈路具有最小負(fù)載，且滿足時(shí)延偏差條件。

表3 拉格朗日乘子分析表

3 算法仿真比較

3.1 仿真條件及仿真建立

選擇SDN模擬器EstiNet，使用Floodlight作為SDN OpenFlow主流控制器。具體仿真參數(shù)設(shè)置如表4所示。

表4 仿真條件設(shè)置

為比較App-RS算法、CORouting算法及Floodlight OpenFlow算法的性能差異，選擇1個(gè)4層級(jí)胖樹(shù)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)，如圖4所示。實(shí)驗(yàn)中取平均帶寬率、平均包丟失率、平均點(diǎn)到點(diǎn)時(shí)延及平均時(shí)延偏差作為性能指標(biāo)。

圖4 胖樹(shù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(k=4)

仿真時(shí)某些鏈路傾向于擁塞，且整個(gè)流量的80%從胖樹(shù)的單一層級(jí)出發(fā)。表5為由許多使用者日常行為統(tǒng)計(jì)到的不同class業(yè)務(wù)應(yīng)用負(fù)載所占比率情況。

表5 不同class業(yè)務(wù)應(yīng)用負(fù)載所占比率情況

3.2 仿真結(jié)果

圖5～7為class 1業(yè)務(wù)應(yīng)用分別采用Floodlight、CORouting、App-RS三種不同路由算法時(shí)的平均帶寬率、平均包丟失率、平均點(diǎn)到點(diǎn)時(shí)延仿真比較情況。

圖5 class 1類業(yè)務(wù)應(yīng)用平均帶寬率仿真比較

圖6 class 1類業(yè)務(wù)應(yīng)用平均包丟失率仿真比較

圖7 class 1類業(yè)務(wù)應(yīng)用平均點(diǎn)到點(diǎn)時(shí)延仿真比較

由于CORouting算法和Floodlight算法總是為class 1類業(yè)務(wù)應(yīng)用選擇跳躍點(diǎn)數(shù)最少的路徑，所以兩類控制器將指示所有class 1類業(yè)務(wù)應(yīng)用流向相同路徑。因此，當(dāng)網(wǎng)絡(luò)中存在太多的class 1類業(yè)務(wù)應(yīng)用流經(jīng)過(guò)同一路徑時(shí)，兩種算法都可能導(dǎo)致網(wǎng)絡(luò)的擁塞。而App-RS算法既考慮了鏈路負(fù)載，又考慮到了端到端的時(shí)延，所以其對(duì)于class 1類業(yè)務(wù)應(yīng)用的平均帶寬率、平均包丟失率、平均端到端時(shí)延要分別比CORouting算法高9.86%、9.76%、25.47%。

圖8～10為class 2類業(yè)務(wù)應(yīng)用分別采用Floodlight、CORouting、App-RS三種不同路由算法時(shí)的平均帶寬率、平均包丟失率、平均時(shí)延偏差仿真比較情況。雖然App-RS和CORouting兩種算法都考慮了鏈路負(fù)載，但是App-RS算法比CORouting算法多考慮了時(shí)延偏差，所以App-RS算法對(duì)class 2類業(yè)務(wù)應(yīng)用的時(shí)延偏差要比 CORouting算法的低。因class 1類業(yè)務(wù)應(yīng)用導(dǎo)致的擁塞可能會(huì)影響到class 2類業(yè)務(wù)應(yīng)用的平均帶寬率、平均包丟失率，所以對(duì)class 2類業(yè)務(wù)應(yīng)用采用App-RS算法時(shí)的平均帶寬率、包丟失率及時(shí)延偏差要比采用CORouting算法時(shí)相應(yīng)提升4.53%、4.1%及4.95%。

圖8 class2類業(yè)務(wù)應(yīng)用平均帶寬率仿真比較

圖9 class 2類業(yè)務(wù)應(yīng)用平均包丟失率仿真比較

圖10 class 2類業(yè)務(wù)應(yīng)用平均時(shí)延偏差仿真比較

圖11～12為class 3類業(yè)務(wù)應(yīng)用分別采用Floodlight、CORouting、App-RS三種不同路由算法時(shí)的平均帶寬率、平均包丟失率仿真比較情況。盡管App-RS和CORouting兩種算法都只考慮了鏈路負(fù)載，但因class 1類業(yè)務(wù)應(yīng)用導(dǎo)致的擁塞也可能影響到class 3類業(yè)務(wù)應(yīng)用時(shí)的平均帶寬率、平均包丟失率，所以對(duì)class 3類業(yè)務(wù)應(yīng)用采用App-RS算法時(shí)的平均帶寬率、平均包丟失率要比采用CORouting算法時(shí)提升4.07%、3.97%。

圖11 class 3類業(yè)務(wù)應(yīng)用平均帶寬率仿真比較

圖12 class 3類業(yè)務(wù)應(yīng)用平均包丟失率仿真比較

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

本文提出了基于SDN云數(shù)據(jù)服務(wù)的應(yīng)用感知路由算法(App-RS)。該算法根據(jù)各自業(yè)務(wù)應(yīng)用特性及網(wǎng)絡(luò)需求把應(yīng)用分成3類，每類業(yè)務(wù)應(yīng)用通過(guò)不同路由算法進(jìn)行處理，這些路由算法考慮到了不同的參數(shù)以滿足其網(wǎng)絡(luò)需求。仿真結(jié)果顯示：在class 1、class 2、class 3三類業(yè)務(wù)應(yīng)用中使用App-RSS算法時(shí)，其對(duì)應(yīng)的平均帶寬率要比使用CORouting算法分別高出9.86%、4.53%及4.07%；在class l業(yè)務(wù)應(yīng)用中使用App-RSS算法時(shí)的平均端到端時(shí)延要比使用CORouting算法時(shí)低25.47%；在class 2業(yè)務(wù)應(yīng)用中使用App-RSS算法時(shí)的平均時(shí)延偏差要比使用CORouting算法時(shí)低49.65%。

[1] 黃韜,劉江,魏亮.軟件定義網(wǎng)絡(luò)核心原理與應(yīng)用實(shí)踐[J].通信學(xué)報(bào),2015(3):12-15.

[2] 左青云,陳鳴,趙廣松.基于OpenFlow的SDN技術(shù)研究[J].軟件學(xué)報(bào),2013(5):1079-1097.

[3] 吳宇文.軟件定義網(wǎng)絡(luò)控制平面可擴(kuò)展性研究進(jìn)展[J].軟件學(xué)報(bào),2017(7)：1-16.

[4] 侯長(zhǎng)逸.OpenFlow網(wǎng)絡(luò)軟件路由研究[J].蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版),2013(2):260-263.

[5] 劉中金,李勇,蘇厲.TCAM存儲(chǔ)高效的OpenFlow多級(jí)流表映射機(jī)制[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2014(4):437-442.

[6] 李龍,付斌章,陳明宇.Nimble:一種適用于OpenFlow網(wǎng)絡(luò)的快速流調(diào)度策略[J].計(jì)算機(jī)學(xué)報(bào),2015(5):1056-1068.

[7] 楊思錦,莊雷,胡穎.一種動(dòng)態(tài)自調(diào)節(jié)的SDN控制器負(fù)載均衡算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016(12):71-74.

[8] 賈濡,郜帥,羅洪斌.智慧協(xié)同網(wǎng)絡(luò)中基于流量矩陣的負(fù)載均衡路由機(jī)制[J].通信學(xué)報(bào),2016(4):128-138.

[9] 周環(huán),劉慧.基于Floodlight的SDN控制器研究[J].計(jì)算機(jī)工程與應(yīng)用,2016(24):137-147.

[10] 蔡岳平,王昌平.軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)混合路由機(jī)制[J].通信學(xué)報(bào),2016(4):44-52.

(責(zé)任編輯劉 舸)

CloudDataApp-RSRoutingAlgorithmBasedonSDN

WEN Jiebin, LIAO Haizhou

(Hunan Post And Telecommunication College, Changsha 410015, China)

At present, the application of cloud data services is popular. Because of different network requirements of different types of cloud applications, all types of cloud applications cannot be treated equally. It proposes a App-RS(application-aware routing scheme)routing algorithm. For calss1 business applications, the algorithm considers end-to-end delay and link load, and for calss2 business applications, considering delay bias and link load for other business applications, and only consider the link load. The simulation results show that the average throughput of App-RS routing algorithm is 9.86%, 4.53% and 4.07% higher than CORouting routing algorithm in three kinds of business applications, and the average delay is less 25.47% than CORouting routing algorithm, and the average delay deviation is 49.65% compared with the class 2 services in CORouting routing algorithm. Therefore, the App-RS routing algorithm can meet the requirements of all the class service application of SDN more than CORouting routing algorithm.

SDN; cloud data; App-RS; routing algorithm

2017-08-18

湖南省教育廳科學(xué)研究項(xiàng)目“基于SDN的集客專線業(yè)務(wù)傳送承載解決方案研究”(15C1018)

文杰斌(1982—)，男，湖南桃江人，碩士，講師，主要從事通訊技術(shù)研究，E-mail:32383101@qq.com ; 廖海洲(1965—)，男，湖南桃源人，副教授，主要從事通訊技術(shù)研究。

文杰斌，廖海洲.基于SDN的云數(shù)據(jù)App-RS路由算法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2017(11):172-178.

formatWEN Jiebin, LIAO Haizhou.Cloud Data App-RS Routing Algorithm Based on SDN[J].Journal of Chongqing University of Technology(Natural Science)，2017(11):172-178.

10.3969/j.issn.1674-8425(z).2017.11.026

TP393

A

1674-8425(2017)11-0172-07