文杰斌，廖海洲

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

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

文杰斌，廖海洲

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

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

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

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

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

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

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

2 App-RS算法

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

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

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

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

2.2 App-RS路由方案

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

對于class 1和class 2業(yè)務(wù)應(yīng)用，目標是找到一條最小鏈路負載及滿足時延上限的剩余路徑。其解決思路與已通過使用LARAC(拉格朗日松弛)算法解決的時延約束下的最小代價路徑問題類似。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算法來為class 1和class 2業(yè)務(wù)應(yīng)用找到合適的路徑，表2為LARAC路由算法所用的符號定義。

表2 LARAC路由算法所用的符號定義

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

圖2 App-RS算法流程

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

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

圖3 App-RS算法舉例

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

LARAC路由算法的目標是找到一個最好λ值，對應(yīng)此λ值的鏈路具有最小負載，且滿足時延偏差條件。

表3 拉格朗日乘子分析表

3 算法仿真比較

3.1 仿真條件及仿真建立

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

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

為比較App-RS算法、CORouting算法及Floodlight OpenFlow算法的性能差異，選擇1個4層級胖樹拓撲結(jié)構(gòu)網(wǎng)絡(luò)，如圖4所示。實驗中取平均帶寬率、平均包丟失率、平均點到點時延及平均時延偏差作為性能指標。

圖4 胖樹網(wǎng)絡(luò)拓撲結(jié)構(gòu)(k=4)

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

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

3.2 仿真結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

(責任編輯劉 舸)

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

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

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

文杰斌，廖海洲.基于SDN的云數(shù)據(jù)App-RS路由算法[J].重慶理工大學學報(自然科學)，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