基于SDN的數(shù)據(jù)中心動態(tài)優(yōu)先級多路徑調(diào)度算法

肖軍弼，程 鵬，譚立狀，孟祥澤

(1.中國石油大學(華東)計算機科學與技術(shù)學院，山東 青島 266580；2.北京交通大學下一代互聯(lián)網(wǎng)互聯(lián)設(shè)備國家工程實驗室，北京 100044)

0 引 言

云計算的發(fā)展使得越來越多的服務(wù)選擇部署在大型的數(shù)據(jù)中心，而不是部署在本地服務(wù)器上。傳統(tǒng)的數(shù)據(jù)中心流量主要是來自數(shù)據(jù)中外部客戶端請求訪問數(shù)據(jù)中心內(nèi)部服務(wù)器的流量，近年來隨著分布式業(yè)務(wù)的發(fā)展，數(shù)據(jù)中心內(nèi)部服務(wù)器之間的流量大幅增加，例如主從備份、設(shè)備動態(tài)遷移等。這些流量稱為“東西向”流量，現(xiàn)在數(shù)據(jù)中心中“東西向”流量占總流量的80%[1-2]，即數(shù)據(jù)中心內(nèi)部服務(wù)器之間的通信流量占絕大多數(shù)。數(shù)據(jù)中心網(wǎng)絡(luò)的特點是服務(wù)器之間的流量大、突發(fā)流量大等，通常數(shù)據(jù)中心是通過增加冗余鏈路來達到增加帶寬的目的[1]，如何調(diào)度多個鏈路成為提高網(wǎng)絡(luò)性能的關(guān)鍵，所以需要為數(shù)據(jù)中心制定高效可行的流量調(diào)度方法，來緩解網(wǎng)絡(luò)流量壓力。

傳統(tǒng)網(wǎng)絡(luò)模式下的數(shù)據(jù)中心網(wǎng)絡(luò)具有純分布式控制、控制與轉(zhuǎn)發(fā)高度耦合的特點，以及盡力而為的轉(zhuǎn)發(fā)模式，導致針對性強且復雜的調(diào)度策略很難在傳統(tǒng)網(wǎng)絡(luò)的結(jié)構(gòu)下實施。傳統(tǒng)網(wǎng)絡(luò)中每個節(jié)點獨立工作，若網(wǎng)絡(luò)環(huán)境改變，使得網(wǎng)絡(luò)整體不能動態(tài)地調(diào)整，所以越來越多的人會考慮使用軟件定義網(wǎng)絡(luò)(SDN)這種松耦合且擴展性強的網(wǎng)絡(luò)架構(gòu)[3]。

SDN作為新型的網(wǎng)絡(luò)體系結(jié)構(gòu)，其核心思想是數(shù)控分離[4]。交換機只負責簡單的數(shù)據(jù)轉(zhuǎn)發(fā)工作，決策功能全部集中在控制器中?？刂破髯鳛镾DN的核心能夠管控整個網(wǎng)絡(luò)，并通過OpenFlow[5]消息與交換機交互，可以針對復雜多變的業(yè)務(wù)場景制定靈活的網(wǎng)絡(luò)轉(zhuǎn)發(fā)策略，為數(shù)據(jù)中心流量負載均衡問題提供了新思路。

1 相關(guān)工作

為了避免擁塞，數(shù)據(jù)中心網(wǎng)絡(luò)(DCN)通常在任意2臺服務(wù)器之間設(shè)計有多條路徑來提高帶寬和容錯，例如Fat-tree架構(gòu)[6]，但是如何合理地調(diào)度多個路徑是一個很大的挑戰(zhàn)。

等價多路徑路由(ECMP)是目前應(yīng)用最廣泛的流量調(diào)度策略。ECMP是一個基于流的流量調(diào)度策略，它根據(jù)流的五元組信息通過哈希、輪詢或者隨機的方式將流分配到某一個路徑中，達到增加帶寬的目的[7]。然而ECMP有2個明顯的缺點，首先是ECMP沒有擁塞感知機制，給已經(jīng)擁塞的鏈路繼續(xù)分配轉(zhuǎn)發(fā)任務(wù)，導致加重擁塞；另外ECMP并不區(qū)分大象流和老鼠流，這種無差別的轉(zhuǎn)發(fā)策略顯然已經(jīng)不再適用于當今的數(shù)據(jù)中心網(wǎng)絡(luò)。

Hedera[8]是一種集中式的動態(tài)流量調(diào)度策略，結(jié)合OpenFlow[9]動態(tài)地求得大象流帶寬閾值，老鼠流使用ECMP策略轉(zhuǎn)發(fā)，大象流通過模擬退火算法求得轉(zhuǎn)發(fā)路徑，轉(zhuǎn)發(fā)效率相對于ECMP有了顯著提升。雖然Hedera從理論上可行，但由于流量的龐大，大象流的調(diào)度策略難以很好地擴展到DCN。Curtis等人[10]已經(jīng)證明Hedera的說法過于樂觀，并且控制器無法快速提取流量統(tǒng)計數(shù)據(jù)以做出路由決策。此外，Hedera的大象流量檢測機制也會增加網(wǎng)絡(luò)負擔。

Zhang等人[11]針對將數(shù)據(jù)中心流量和交換機內(nèi)存轉(zhuǎn)化為一個穩(wěn)定匹配問題，設(shè)計了一種名叫Fincher的算法，并證明了這一問題是一個NP難問題。Fincher尋找流與交換機之間的穩(wěn)定匹配，考慮到了交換機內(nèi)存對于流完成時間的影響，但是只考慮了共享內(nèi)存式交換機內(nèi)存對大象流轉(zhuǎn)發(fā)的影響，并未考慮鏈路，且缺乏實時性。

針對以上現(xiàn)有流量調(diào)度策略的局限性，本文提出一種動態(tài)優(yōu)先級多路徑調(diào)度算法(DPMS)。DPMS結(jié)合數(shù)據(jù)中心流量重尾分布[12-13]的特性降低了大象流檢測所消耗的額外負載，并且能根據(jù)鏈路實時狀態(tài)動態(tài)改變多路徑的優(yōu)先級，達到提高網(wǎng)絡(luò)吞吐量的目的。

2 多路徑調(diào)度算法設(shè)計

2.1 算法思想

多路徑調(diào)度算法是一種SDN架構(gòu)下適用于數(shù)據(jù)中心Fat-Tree網(wǎng)絡(luò)的多路徑流量調(diào)度策略。該策略中主要工作包括數(shù)據(jù)包采集、大象流檢測、鏈路代價計算和可行路徑計算。流量調(diào)度流程如圖1所示。

圖1 流量調(diào)度流程圖

詳細步驟如下：當流到達邊緣交換機時，首先檢測該交換機流表項中是否已經(jīng)有相匹配的流表，若有，則說明之前已經(jīng)為該流做出了轉(zhuǎn)發(fā)策略且策略未過期，交換機直接按照流表規(guī)則轉(zhuǎn)發(fā)；若沒有，則把首個數(shù)據(jù)包通過Packet_In消息發(fā)送給控制器，由控制器做決策?？刂破鹘邮盏絇acket_In消息后首先判斷該流是大象流還是老鼠流，若為大象流，交換機計算K條最短路徑，并根據(jù)鏈路代價計算各個鏈路的優(yōu)先級，控制器根據(jù)K條路徑及其優(yōu)先級通過Flow_Mod消息下發(fā)組表和流表，交換機根據(jù)組表和流表規(guī)則轉(zhuǎn)發(fā)大象流；若為老鼠流，則控制器計算時延最短的路徑，通過Packet_Out消息下發(fā)流表，交換機根據(jù)流表規(guī)則轉(zhuǎn)發(fā)老鼠流。

2.2 大象流檢測模型

本文使用sFlow agent統(tǒng)計交換機中的流量，使用sFlow-rt作為收集器[14]。整個過程中sFlow agent過濾掉已經(jīng)被認定為大象流的流量不必全量采樣，且對數(shù)據(jù)包的處理過程發(fā)生在數(shù)據(jù)平面，這樣有效地減少了控制平面的額外負擔。采樣率設(shè)置為1/z，表示每z個數(shù)據(jù)包采樣一個數(shù)據(jù)包，采樣率必須設(shè)置合理，過大會導致大象流的丟失，影響準確性，過小會增加內(nèi)存和計算負擔[17]。整個過程中，采樣的數(shù)據(jù)包需要實時計算自適應(yīng)閾值σ來判斷是否是大象流。

數(shù)據(jù)中心的流量服從重尾分布，大象流的數(shù)量很少，但卻占據(jù)了大部分的網(wǎng)絡(luò)流量，老鼠流的數(shù)量很多，卻只占有很少的流量，數(shù)據(jù)中心經(jīng)常使用這一特性改善網(wǎng)絡(luò)鏈路。本文使用Pareto[15-16]重尾模型來計算動態(tài)閾值，其概率密度函數(shù)是P(βi=x)=αkx-a-1(x≥k)，其累積分布函數(shù)用公式(1)表示，公式(2)表示互補累計分布，其中α=1.2，k=2。

(1)

(2)

(3)

公式(4)表示采樣數(shù)據(jù)包大于閾值x的條件下，總數(shù)據(jù)包數(shù)量超過閾值X的概率[18]。

P(mi≥X|ki≥x)=

(4)

2.3 鏈路代價計算

大象流的鏈路代價計算需要考慮鏈路帶寬和時延這2個因素，定義p(s,d)表示從源s到目的地d的k條路徑，p(s,d)k表示第k條路徑。

每條鏈路包含多個子鏈路，而鏈路的剩余帶寬類似于木桶原理，鏈路的剩余帶寬等于子鏈路剩余帶寬的最小值，定義p(s,d)k上鏈路剩余帶寬(remaining bandwidth， rb)為：

rb(s,d)k=min(bwki),i∈p(s,d)k

(5)

其中，bwki是第k條路徑上第i段鏈路的剩余帶寬，i是p(s,d)k路徑上的第i段路徑。

那么可以定義路徑p(s,d)k上各鏈路利用率(Link Resource Utilization， LRU)為：

(6)

其中，tb(s,d)k表示p(s,d)k的鏈路總帶寬，鏈路總帶寬等于該鏈路包含的子鏈路的帶寬最小值。

定義路徑p(s,d)k上大象流的鏈路代價(link cost of elephant flow， lce)為：

lce(s,d)k=m×NRUp(s,d)k+n×d(s,d)k

(7)

其中,d(s,d)k表示路徑p(s,d)k的平均時延，m、n分別是剩余帶寬和時延的鏈路代價系數(shù)，且m+n=1。由于大象流是帶寬敏感型[19]，與大象流相關(guān)的業(yè)務(wù)一般對鏈路資源要求較高，對時延要求較少，所以m的取值要比n大一些。在本文中，通過仿真實驗分析，鏈路代價系數(shù)m、n的取值分別為0.8、0.2。

由于老鼠流是時延敏感性流[20]，數(shù)量較多，但攜帶數(shù)據(jù)很少，所以交換機沒必要為每個老鼠流配置永久流表。當收到老鼠流時控制器只需要計算得到當前時延最小的路徑，然后下發(fā)流表并設(shè)置軟超時時間，使得轉(zhuǎn)發(fā)完成后交換機自動刪除該流表。所以老鼠流的鏈路代價(link cost of mouse flow， lcm)表示為：

lcm(s,d)k=m×d(s,d)k

(8)

2.4 可行路徑計算

K-pod Fat-tree網(wǎng)絡(luò)分為3個層次：自上而下分別為邊緣層、匯聚層和核心層，圖2給出了一個4-pod Fat-tree網(wǎng)絡(luò)架構(gòu)的示例。拓撲含有(k/2)2個核心交換機，其中匯聚層交換機與邊緣層交換機構(gòu)成一個pod，每個pod有k/2個匯聚層交換機。在此網(wǎng)絡(luò)拓撲中，pod間任何主機對之間都存在(k/2)2條相同的最短路徑。pod內(nèi)流分為2種情況：如果2個主機連接在一個交換機上，那么就只有一條最短路徑可選，如果不在同一個交換機上則有k/2條最短路徑[22]。

圖2 4-pod Fat-tree網(wǎng)絡(luò)架構(gòu)圖

本文采用K短路徑算法(KSP)[21]來得到跳數(shù)最少的k條路徑，并計算鏈路代價作為每條路徑的優(yōu)先級，最后下發(fā)組表和流表。本文將此算法稱為動態(tài)優(yōu)先級多路徑調(diào)度算法(DPMS)。DPMS的偽代碼如算法1所示。

算法1DPMS

輸入：當前要處理的流flow，網(wǎng)絡(luò)拓撲

輸出：最優(yōu)路徑path

1 if (flow是大象流)

2 if (flow是pod間流)

3w=跳數(shù);

4 path[]=KSP((k/2)2,w,s,d);

5 else if (flow是pod內(nèi)流)

6 if (s和d在同一交換機上)

7 path[]=KSP(1,w,s,d);

8 else

9 path[]=KSP(k/2,w,s,d);

10 for (p: path)

11p.priority=priority(s,d)p

12 else

13 weight=時延;

14 path[]=KSP(1,weight,s,d);

15 return path;

其中第4行是調(diào)用Floodlight控制器的內(nèi)置KSP算法，4個參數(shù)分別是要求得路徑個數(shù)、計算參數(shù)、源地址和目的地址，算法第11行是計算每條鏈路的優(yōu)先級，如公式(9)所示，p(s,d)中k個鏈路的優(yōu)先級定義為k條鏈路代價的總和與當前鏈路的鏈路代價的比。

(9)

OpenFlow1.3支持組表，組表[23]是一種復雜的轉(zhuǎn)發(fā)模式，用在多路徑、快速重路由等場景下。通過算法求得的大象流最優(yōu)路徑是一組k個鏈路及其優(yōu)先級的集合，組表中可以含有多個group_buckets，即粗略對應(yīng)多條路徑，每個group_buckets里的bucket_weight對應(yīng)其優(yōu)先級。研究表明，SDN網(wǎng)絡(luò)中主要時延來自于交換機發(fā)送Packet_In消息時，交換機緩存數(shù)據(jù)包等待控制器命令的下發(fā)這部分時間，在本方案中，交換機下發(fā)組表后該組表會一直存儲在交換機中，只需要根據(jù)網(wǎng)絡(luò)狀態(tài)定時更新每個bucket_weight，并不需要中斷當前通信去請求控制器，在縮短時延方面有明顯的優(yōu)勢。

2.5 系統(tǒng)總體架構(gòu)

該流量調(diào)度系統(tǒng)架構(gòu)如圖3所示，主要包含3個部分：最底層的是數(shù)據(jù)平面，數(shù)據(jù)平面除了包含OpenFlow交換機外還有sFlow agent，負責流量采樣；負責流量監(jiān)測的是sFlow收集器，該部分接受數(shù)據(jù)平面中sFlow agent采樣的數(shù)據(jù)，并進行大象流檢測，最后把檢測結(jié)果發(fā)送給SDN控制器；最后一部分是SDN控制器，SDN控制器負責獲取全網(wǎng)信息，并計算轉(zhuǎn)發(fā)路徑下發(fā)流表。

圖3 流量調(diào)度系統(tǒng)架構(gòu)圖

3 仿真與分析

3.1 仿真環(huán)境

本文在Linux系統(tǒng)上使用Floodlight控制器實現(xiàn)了DPMS算法，并使用mininet[24]模擬數(shù)據(jù)平面拓撲，構(gòu)建了一個如圖2所示的4-pod Fat-Tree網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行仿真。本實驗通過Iperf性能工具產(chǎn)生流量，且大象流和老鼠流的比例是9:1，鏈路帶寬設(shè)置為100 Mbit/s。

仿真使用2種數(shù)據(jù)中心常用的流量模式：

1)Random：每臺主機等概率地向其他主機發(fā)送數(shù)據(jù)。

2)Staggered Prob(EdgeP,PodP)：主機以概率EdgeP發(fā)送到同一邊緣交換機中的另一個主機，稱為機柜流量。以概率PodP發(fā)送到其相同的pod且不在同一邊緣交換機的主機，即pod內(nèi)流量。以概率1-EdgeP-PodP發(fā)送到網(wǎng)絡(luò)的其余部分，即pod間流量。

3.2 仿真結(jié)果分析

本文從平均吞吐率、平均流完成時間(FCT)和鏈路利用率這3個角度比較了DPMS、Hedera和ECMP這3種策略，以驗證性能的實際提高。

平均吞吐率是衡量網(wǎng)絡(luò)性能的重要指標，本文在6組網(wǎng)絡(luò)模式下比較3個調(diào)度策略的性能。如圖4所示，在EdgeP較低時，即網(wǎng)絡(luò)內(nèi)有較多的pod內(nèi)流和pod間流時，DPMS、Hedera和ECMP這3種策略的吞吐率差距較大。因為在pod內(nèi)流和pod間流多的情境下，ECMP無法根據(jù)鏈路擁塞狀態(tài)動態(tài)地分配鏈路資源，大象流的碰撞率增大。Hedera區(qū)分大象流和老鼠流，動態(tài)對大象流進行調(diào)度，所以效果比ECMP要好。DPMS除了為大象流提供動態(tài)調(diào)度，還針對pod內(nèi)流和間流進行路徑優(yōu)化，并且改善了交換機同控制器的通信，減少了流等待時間。

圖4 網(wǎng)絡(luò)平均吞吐率

數(shù)據(jù)中心的老鼠流通常是時延敏感性，通常與對時延敏感的應(yīng)用相關(guān)聯(lián)，所以平均流完成時間(Avg FCT)是此類流量的關(guān)鍵性能指標。本文在5組流量模式下比較了3個流量調(diào)度策略的Avg FCT，如圖5所示，當機柜流量占比為多數(shù)時3種調(diào)度策略的差異不大，隨著跨交換機和跨pod的流量的增多，DPMS逐漸展現(xiàn)出優(yōu)勢。這是因為數(shù)據(jù)中的老鼠流是以沒有擁塞感知的ECMP策略調(diào)度的，當大象流量發(fā)生碰撞時會阻塞鏈路，如果此時老鼠流被調(diào)度到此鏈路便會發(fā)生擁塞。DPMS更加合理地調(diào)度了大象流，均衡地利用了網(wǎng)絡(luò)資源，間接地保證了老鼠流的傳輸環(huán)境。

圖5 網(wǎng)絡(luò)平均流完成時間

通過DPMS進行多路徑的調(diào)度最直觀的表現(xiàn)就是鏈路利用率，它反映了算法是否合理地利用了冗余鏈路。選取6組流量模式進行試驗，如圖6所示，同樣ECMP和Hedera在pod間流量占比較大時大象流碰撞較多，容易造成鏈路擁塞，鏈路帶寬利用不均衡。DPMS算法更好地利用了鏈路，并對pod內(nèi)流和pod間流作出優(yōu)化，其鏈路利用率更高。在stag(0.8,0.1)的流量模式下，由于機柜流量較多，即表示沒有太多的冗余鏈路可以利用，所以3種調(diào)度策略的鏈路利用率差異不明顯。

圖6 鏈路利用率

4 結(jié)束語

本文研究了數(shù)據(jù)中心大象流調(diào)度問題，發(fā)現(xiàn)數(shù)據(jù)中心內(nèi)“東西向”流量的合理調(diào)度是數(shù)據(jù)中心流量負載均衡的關(guān)鍵點。然后在SDN的架構(gòu)下提出了一種動態(tài)優(yōu)先級多路徑調(diào)度算法DPMS，該算法根據(jù)鏈路實時狀態(tài)以及大象流和老鼠流的特性動態(tài)地改變路由策略，減少了交換機中數(shù)據(jù)包隊列的等待時間。通過對比實驗表明，與ECMP和Hedera相比，部署DPMS的網(wǎng)絡(luò)具有更高的鏈路利用率和吞吐量、更低的時延。通過模擬仿真的形式驗證了算法的可行性，并在真實環(huán)境下部署測試，因此真實環(huán)境下該算法對控制器的負載問題還需要進一步研究。