楊耀忠 劉寶軍 段鴻杰 羅 陽 程 鵬

1(勝利油田分公司信息化管理中心 山東 東營 257000)2(中國石油大學(華東)計算機科學與技術學院 山東 青島 266580)

0 引 言

隨著分布式業(yè)務的興起，比如VM遷移、MapReduce、數(shù)據(jù)備份等，數(shù)據(jù)中心“東西向”流量大幅增加，數(shù)據(jù)中心網(wǎng)絡(DCN)流量調(diào)度壓力越來越大。為了避免擁塞，DCN通常在任意兩臺服務器之間設計有多條路徑來提高帶寬和容錯[1]，例如Fat-Tree架構。但多條路徑之間的調(diào)度問題是一個很大的挑戰(zhàn)，不合適的調(diào)度會導致?lián)砣蛿?shù)據(jù)包丟失，隨后的重傳會進一步加重擁塞，因此多路徑的合理調(diào)度是解決擁塞的關鍵。

傳統(tǒng)網(wǎng)絡具有純分布式結構，轉(zhuǎn)發(fā)和控制高度耦合在每個網(wǎng)絡設備中，導致針對性高且復雜的調(diào)度模式難以在傳統(tǒng)網(wǎng)絡中部署，數(shù)據(jù)中心也很難根據(jù)網(wǎng)絡狀態(tài)動態(tài)調(diào)整策略。

軟件定義網(wǎng)絡(SDN)是一個新型的網(wǎng)絡模型，其核心思想是數(shù)控分離，數(shù)據(jù)平面只負責高速轉(zhuǎn)發(fā)，其控制功能全部集成在控制平面，控制器是控制平面的核心，管控整個網(wǎng)絡，可以針對復雜場景制定復雜的流量調(diào)度模型，為數(shù)據(jù)中心流量調(diào)度問題提供了新思路。

1 相關工作

數(shù)據(jù)中心網(wǎng)絡中的流量調(diào)度一直是一個活躍的研究領域，這個研究領域已經(jīng)有很多成果。

等價多路徑路由(ECMP)是一個基于流的負載均衡策略，通過計算五元組的哈希值或輪詢調(diào)度這些路徑轉(zhuǎn)發(fā)數(shù)據(jù)，達到增加帶寬的目的。ECMP不區(qū)分大象流和老鼠流，因此無法為大象流均衡地分配資源。Al-Fares等[2]提出了針對Fat-Tree拓撲的集中式流調(diào)度程序。一旦流量增長到閾值以上，邊緣交換機將向控制器發(fā)送包含大象流量信息的通知，控制器負責將路徑重新分配給大流量。Hedera[3]是另一種典型的Fat-Tree拓撲下集中式流量調(diào)度系統(tǒng)，Hedera在邊緣交換機處檢測到大象流量，對大象流使用模擬退火算法進行調(diào)度，對老鼠流使用ECMP進行調(diào)度。PIAS[4]是一種DCN流調(diào)度機制，通過最短作業(yè)優(yōu)先原則和使用優(yōu)先級隊列來最小化流完成時間。這些方案忽略了存儲器占用和數(shù)據(jù)速率，它們是擁塞的重要信號和流量的特征。同時，其中一些工作著眼于當前調(diào)度流程的有效性，這可能導致流量不平衡。

流調(diào)度的另一個方向是集中在小粒度數(shù)據(jù)的傳輸上。VL2[5]利用VLB和ECMP兩種技術來提供無熱點的性能。VL2使用VLB實現(xiàn)負載均衡，ECMP實現(xiàn)多路徑傳輸。TinyFlow[6]是一種新穎的大象流調(diào)度方法，通過將大象流分割成老鼠流來改變數(shù)據(jù)中心網(wǎng)絡的流量特性，使其適合ECMP，并利用ECMP實現(xiàn)負載平衡。上述解決方案可能會導致重新排序問題，盡管有些提案指出通過某些方法進行重新排序，但會導致大量開銷。

考慮到以上解決方案的局限性，我們使用穩(wěn)定匹配理論[7]為數(shù)據(jù)中心中大象流調(diào)度問題建模。然后本文提出一種基于穩(wěn)定匹配的大象流調(diào)度算法TPLM，它可以在數(shù)據(jù)中心中提高設備資源利用率和網(wǎng)絡吞吐量。

2 系統(tǒng)分析與建模

2.1 系統(tǒng)總覽

如圖1所示，K-pod Fat-Tree網(wǎng)絡分為三個層次：自下而上分別為邊緣層(edge)、匯聚層(aggregate)和核心層(core)，拓撲含有(k/2)2個核心交換機，其中匯聚層交換機與邊緣層交換機構成一個pod，每個pod有k個匯聚層交換機。在此網(wǎng)絡拓撲中，定義三種流量調(diào)度模式：pod間流調(diào)度、pod內(nèi)流調(diào)度和機柜流量調(diào)度。pod間流調(diào)度指不同pod間任何主機對之間的通信，由拓撲結構可知，pod間流必須經(jīng)過其中核心交換機，所以當pod間流到達時，只需要為其選擇合適的核心交換機，就能確定此流量的最短路徑[8]。機柜流量調(diào)度指連接在同一交換機上的任意兩臺主機間的通信，因此只有一條傳輸路徑。pod內(nèi)流調(diào)度指同一pod內(nèi)任意兩個不連接在同一交換機上的主機間的通信，同pod間流調(diào)度類似，只需為流分配匯聚交換機。例如，主機h1到h2的路徑只有h1-e1-h2；h1到h3的路徑有h1-e1-g1-e2-h3和h1-e1-g2-e2-h3;h1到h5的路徑有四條，分別是h1-e1-g1-c1-g3-e3-h5，h1-e1-g1-c3-g3-e3-h5，h1-e1-g2-c2-g4-e3-h5，h1-e1-g2-c4-g4-e3-h5。

圖1 4-pod Fat-Tree網(wǎng)絡架構

如上述所示，當數(shù)據(jù)中心在進行流量調(diào)度時，我們的關注對象由路徑和流變?yōu)榻粨Q機和流。

1) 交換機：數(shù)據(jù)中心中的所有交換機，同大多數(shù)商用交換機一樣，數(shù)據(jù)中心的交換機通常是共享內(nèi)存式的交換機，即所有交換機端口共享數(shù)據(jù)包緩沖區(qū)來提高內(nèi)存利用率[9]。以下提到的交換機均認為是共享內(nèi)存式交換機。圖2為共享內(nèi)存式交換機的示例。

圖2 共享內(nèi)存式交換機原理

這組交換機由S={s1,s2,…,sj}表示，|S|表示交換機的總數(shù)，cj表示交換機sj的容量。交換容量代表交換機各接口之間所能進行的數(shù)據(jù)交換的最大能力。一定程度上來說，交換機的容量是一個單位時間內(nèi)能接收的數(shù)據(jù)包個數(shù)，因此交換機的容量與流的傳輸速率有關。

2) 流：數(shù)據(jù)中心的流量可以分為大象流和老鼠流兩類，根據(jù)以往的研究表明，數(shù)據(jù)中心的流量服從長尾概率分布，大象流數(shù)量只占流總數(shù)的20%，但卻占據(jù)了90%的網(wǎng)絡流量[9]，本文的重點關注數(shù)據(jù)中心中服務器之間傳輸?shù)拇笙罅骷稀Ｈ鐩]有特殊說明，以下提及的流皆指大象流。

該組流被定義為F={f1,f2,…,fi}，|F|表示流的數(shù)量。流具有許多特征，例如生存時間、數(shù)據(jù)大小和數(shù)據(jù)速率。如上所述，交換機的容量與流的傳輸速率有關，因此我們注意流的速率特性，并用ri表示流量的速率。這里，ri可以是特定時間間隔內(nèi)的平均配對流量速率，并且可以適當?shù)卦O置間隔長度以匹配環(huán)境的動態(tài)，同時不響應瞬時流量突發(fā)。這是合理的，許多現(xiàn)有的數(shù)據(jù)中心流量測量的研究表明，流量隨著時間的推移呈現(xiàn)緩慢變化的現(xiàn)象[10]。

2.2 流-交換機匹配模型

μ(sn)?sn?fmfm∈[F-μ(sn)]

(1)

μ(fm)?fm?snsn∈[S-μ(fm)]

(2)

定義1流的交換機優(yōu)先級列表順序由交換機內(nèi)存大小決定。

流將占用路徑上的交換機內(nèi)存資源，在一個時間單位內(nèi)，交換機接收的總流量速率不能超過交換機的容量，即cj≥∑ri。為了避免擁塞，流更喜歡具有更大容量的交換機。所以定義流的交換機優(yōu)先級列表P(fi)={s1,s2,…,sj}中交換機的順序是由交換機內(nèi)存大小決定的，pod間流優(yōu)先級列表對應核心交換機，pod內(nèi)流對應匯聚層交換機。

定義2交換機的流優(yōu)先級列表順序由流的傳輸速率決定。

每個交換機sj也會有一個流優(yōu)先級列表：P(sj)={f1,f2,…,fi}，交換機優(yōu)先考慮傳輸速率低的流，所以列表中流的順序由通過他們的速率決定。由于每個交換機可以接受多個流，并且為了不超過交換機的容量，交換機需要檢測內(nèi)存狀態(tài)。

定義3給定S和F，流-交換機匹配問題要找的是最佳匹配集合M={(fi,sj)|fi∈P(sj),sj∈P(fi)}。

max |M|

(3)

E(fi,μ(fi))=0

(5)

|μ(fi)|≤1

(6)

式中：j=1,2,…,|S|；i=1,2,…,|F|。

式(4)確保所有交換機的容量不會溢出，式(6)確保每個流最多與一個交換機匹配。

2.3 匹配沖突問題

由于交換機的內(nèi)存限制、流的交換機偏好的存在，可能會導致pod間流量和pod內(nèi)流量在匹配交換機的過程中發(fā)生沖突。如圖3所示，在Fat-Tree網(wǎng)絡中，一個容量為9的核心交換機A，匯聚層交換機B、C的容量分別是10和7，B和C在一個pod內(nèi)。兩個大象流a和b，假設流a是一個pod間流，其數(shù)據(jù)速率是8；流b是一個pod內(nèi)流，其數(shù)據(jù)速率是6。流a選擇A作為合適的核心交換機，并途經(jīng)交換機B轉(zhuǎn)發(fā)到交換機A。同時，如果同一個pod內(nèi)的流b選擇交換機B作為合適的匯聚層交換機，這就導致了交換機B內(nèi)存溢出。原因在于pod內(nèi)流調(diào)度選擇匯聚層交換機時忽略了該匯聚層交換機是否有足夠的內(nèi)存來傳輸該流，這可能導致交換機的擁塞或流的重傳。我們稱此為匯聚層交換機上的pod內(nèi)流和間流沖突。

圖3 匹配沖突示例

為了解決此問題我們需要分別執(zhí)行pod內(nèi)流調(diào)度和pod間流調(diào)度，此外由于沖突的原因是匯聚層交換機的資源有限，所以在執(zhí)行pod間流調(diào)度時，為流匹配合適的核心交換機，之后根據(jù)資源消耗修改路徑上的匯聚層交換機的內(nèi)存狀態(tài)。

3 系統(tǒng)方案與實現(xiàn)

3.1 TPLM算法

以上定義了一個穩(wěn)定匹配問題，G-S算法[11]是求解穩(wěn)定匹配問題的常用算法，但是G-S算法是一對一的匹配，流-交換機匹配問題是多對一的關系，而且由于交換機優(yōu)先選擇傳輸速率低的流，流優(yōu)先考慮選擇容量大的交換機，導致網(wǎng)絡中的很多流或交換機會具有相同的優(yōu)先級列表，會使得容量大的交換機非常繁忙，容量小的交換機非?？臻e。因此不能直接應用G-S算法到流-交換機匹配問題中。TPLM算法如算法1所示。

算法1TPLM算入：F，S，C，R。

輸出：最優(yōu)解集合M。

1.計算得到P(F)、P(S)

2.初始化M為空

3.While(F中存在任意一個未匹配的流fi)do

4.sj=優(yōu)先級最高且未拒絕sj的交換機inP(fi)

5.ifsjis未匹配then

6.M=M∪(fi,sj)

7.elseiffi?sjfksjthen

8.M=M-(fi,sk)

9.M=M∪(fi,sj)

10.else

11.sj拒絕fi

12.endif

13.ifM不在變化&&存在fi未匹配then

14.根據(jù)當前匹配結果M更新C

15.endif

16.endWhile

17.ReturnM

針對上述問題，本文改進G-S算法，提出一種流優(yōu)先層次匹配算法TPLM，流優(yōu)先指流-交換機匹配的過程中，由流主動匹配交換機，交換機是被匹配方，這樣做的目的是保證交換機內(nèi)存資源不溢出。層次匹配指，將匹配分為pod間流調(diào)度匹配和pod內(nèi)流調(diào)度匹配兩層，先匹配pod間流，pod間流匹配完成后，更新交換機剩余內(nèi)存信息再匹配pod內(nèi)流，目的是解決2.3節(jié)描述的匹配沖突問題。

TPLM的算法流程如表1所示，TPLM通過多次迭代匹配得到交換機和流的一對多最優(yōu)匹配。定義流選定交換機的狀態(tài)稱為“延遲接受”。迭代過程如下：

步驟1選擇流集合F中的任意一個不是“延遲接受”狀態(tài)的流fi，并且請求P(fi)中優(yōu)先級最高且沒有拒絕過它的交換機sj作為匹配對象。

步驟2若交換機sj已經(jīng)匹配了流fk，則比較P(sj)中fi和fk的優(yōu)先級，若fi的優(yōu)先級高于fk，則sj拒絕fk接受fi。否則sj拒絕流fi，然后fi按步驟1選擇下一個交換機作為匹配對象，直到匹配成功。

步驟3多次迭代直到“延遲接受”匹配對,sj沒有改變。如果每個流已經(jīng)處于“延遲接受”狀態(tài)，則迭代結束，并且當前流和交換機匹配結果是最佳匹配。否則，記錄當前匹配結果，并將當前匹配結果的存儲容量C與其匹配流量的數(shù)據(jù)速率R之間的差值作為新的交換容量C′，轉(zhuǎn)到步驟1。

通過多次迭代，交換機和流的匹配結果將呈現(xiàn)“小而多，大而少”的狀態(tài)。即具有大容量的交換機匹配較多的具有相對小的數(shù)據(jù)速率的流，小容量的交換機接收較少的具有數(shù)據(jù)速率相對大的流，這避免了貪婪的出現(xiàn)并提高了交換機的利用率。

一般來說，流量負載均衡專注于將一個流分配給當前的最優(yōu)路徑，但是卻忽略了該路徑繼續(xù)承載其他流時會發(fā)生流量碰撞，使得兩個流的傳輸都受阻。TPLM的思想是為每個流匹配一條合適的路徑，而不是單個流轉(zhuǎn)發(fā)的最優(yōu)路徑，這就意味著TPLM為整個網(wǎng)絡流調(diào)度找到了全局最優(yōu)解，從而提高了整個網(wǎng)絡的性能。

3.2 系統(tǒng)方案

首先執(zhí)行pod間流調(diào)度，得到核心層最優(yōu)匹配。根據(jù)Fat-Tree網(wǎng)絡架構的特點，我們根據(jù)源主機和核心交換機可以唯一確定一組路徑，從而確定一組匯聚層交換機，通過減去其流經(jīng)的pod間流的傳輸速率來更新匯聚層交換機的剩余容量，得到最新的剩余內(nèi)存。然后通過算法1進行pod內(nèi)流量調(diào)度，最終得到匯聚層最優(yōu)匹配。

考慮到老鼠流對時延敏感的特性，對于老鼠流我們使用時延最小調(diào)度策略，即老鼠流到達時，控制器選取當前時延最小的路徑為其路由。

定理1TPLM算法中，所有的流都能匹配到交換機。

證明隨著迭代次數(shù)的增加，總有一個時候所有流都有交換機與之匹配。因為流會根據(jù)自己的交換機優(yōu)先級列表排名依次進行匹配。假如存在一個流沒有匹配到交換機，那么這個流必定是向所有交換機進行請求匹配了。但是交換機只要被請求一次就一定會進入“延遲接受”狀態(tài)，這與存在一個流沒有匹配到交換機假設相悖，所以假設不成立。該算法一定會使得所有流都能夠配對成功。

定理2TPLM所得的匹配一定穩(wěn)定。

證明假設匹配結果M中有兩個匹配對(f1,s1)、(f2,s2)，f1認為s2好于s1，s2認為f1好于f2。這兩個匹配的形成是有先后順序的，假設f1先和s1先匹配，由于f1認為s2好于s1，那么f1已經(jīng)向s2請求過了，請求的結果有兩種：1)s2當時接受了f1。我們可以發(fā)現(xiàn)，算法中交換機一旦接受了某個流的請求，就一定會一直處于“延時接受”狀態(tài)，且從交換機的視角而言，匹配的流只會越來越好。這與結果中f2和s2匹配是矛盾的。2) 如果s2當時沒有接受f1的請求，那么s2當時一定有比f1更好的流與之匹配，最后也不會選擇f2。所以TPLM返回結果中不存在不穩(wěn)定配對。

3.3 負載均衡架構

負載均衡架構如圖4所示，主要共包含三個模塊：Monitor、Statistics Collector、Schedule。

圖4 負載均衡架構

Monitor：該模塊主要負責收集流量信息和交換機信息。流的傳輸速率和交換機的內(nèi)存信息是匹配過程中最重要的兩部分，這些數(shù)據(jù)必須在數(shù)據(jù)平面獲取。

Statistics Collector：主要負責統(tǒng)計獲取底層網(wǎng)絡的數(shù)據(jù)信息。統(tǒng)計收集模塊在控制器中完成，與底層Monitor通信，獲取Monitor收集的流量和交換機信息，并向Schedule模塊提供接口。

Schedule：該模塊主要的工作是執(zhí)行TPLM算法，得到最優(yōu)匹配后把匹配結果轉(zhuǎn)化為流表規(guī)則的形式下發(fā)到數(shù)據(jù)平面。

4 仿真與評估

4.1 仿真環(huán)境

我們在Floodlight控制器上實現(xiàn)了TPLM，在Mininet上搭建6-pod Fat-Tree網(wǎng)絡拓撲，仿真中的其他參數(shù)如表1所示。Floodlight控制器和Mininet都運行在一臺裝有Ubuntu 18.04系統(tǒng)的服務器上。

表1 仿真參數(shù)

本文采用如下三種流量模式：

1) Stride(i)：拓撲中主機從左向右依次編號，編號為m的主機向編號為(i+m)/n的主機發(fā)送數(shù)據(jù)。

2) Random(i)：拓撲中主機從左向右依次編號，每臺主機等概率地向任意i臺主機發(fā)送數(shù)據(jù)。

3) Staggered Prob(EdgeP,PodP)：主機以概率EdgeP發(fā)送到同一邊緣交換機中的另一個主機，并以概率PodP發(fā)送到其相同的pod，并以概率1-EdgeP-PodP發(fā)送到網(wǎng)絡的其余部分。

4.2 仿真結果與分析

我們從平均流完成時間(FCT)、大象流吞吐量、平均網(wǎng)絡吞吐量和平均網(wǎng)絡延遲中比較了TPLM，Hedera和ECMP的三種策略，以證明性能的實際提高。

圖5顯示了三種調(diào)度策略下不同模式老鼠流的FCT。可以看出，由于老鼠流在機柜流量的調(diào)度幾乎沒有優(yōu)化空間，因此這三種調(diào)度算法在Stride(1)模式下的區(qū)別并不明顯。隨著系數(shù)i的增加，pod間流傳輸增多，TPLM表現(xiàn)出優(yōu)勢。在Random(i)模式下，隨著參數(shù)的增加，TPLM的優(yōu)勢越來越明顯。圖6顯示了三種調(diào)度策略在不同調(diào)度模式下大象流的FCT?？傮w而言，TPLM性能最好，而ECMP性能最差。在Stride(i)模式下，TPLM調(diào)度大象流相比調(diào)度老鼠流時效果更好。在Random(i)模式下，隨著系數(shù)i的增加，TPLM的優(yōu)勢變得越來越明顯。

圖5 老鼠流的平均流完成時間

圖6 大象流的平均流完成時間

圖7是在Staggered Prob(0.2,0.3)模式下的三種調(diào)度策略的圖示。網(wǎng)絡負載的增大，意味著網(wǎng)絡中發(fā)生流量碰撞的概率的增大，使得無法做到負載均衡的調(diào)度策略性能較低?？梢钥闯?，隨著網(wǎng)絡負載的增加，三種調(diào)度策略下的大象流吞吐量逐漸增加，而增量逐漸減小。與ECMP相比，Hedera和TPLM在高負載條件下具有顯著提高的吞吐量。由于ECMP是基于五元組來計算哈希選擇路徑的，因此它不會考慮可能導致鏈接或交換機擁塞的負載情況，從而導致數(shù)據(jù)包丟失。與Hedera相比，TPLM具有優(yōu)勢，由于TPLM預先匹配了收集到的大象流量，因此不會由于新大象流量的統(tǒng)計而導致資源分配不均。圖8顯示了在Staggered Prob(0.2,0.3)模式下，三種負載均衡策略的全網(wǎng)吞吐量隨網(wǎng)絡負載變化的曲線。由于網(wǎng)絡中的大部分流量都是由大象流貢獻的，因此全網(wǎng)吞吐量曲線和大象流吞吐量變化曲線基本相同。

圖7 大象流的吞吐量隨網(wǎng)絡負載變化

圖8 老鼠流的吞吐量隨網(wǎng)絡負載變化

圖9是在Staggered Prob(0.2,0.3)模式下平均網(wǎng)絡時延隨網(wǎng)絡負載變化的曲線，隨著網(wǎng)絡負載的增大，TPLM的優(yōu)勢越來越明顯，可以看出，TPLM有效地改善了整個網(wǎng)絡的平均延遲。

圖9 網(wǎng)絡時延隨網(wǎng)絡負載變化

由于將穩(wěn)定匹配應用于大象流調(diào)度，這將為數(shù)據(jù)傳輸和網(wǎng)絡容量均獲得最佳結果，因此，網(wǎng)絡吞吐量、FCT、時延的性能均顯示了TPLM的有效性。

ECMP通過哈希的手段得到流的轉(zhuǎn)發(fā)路徑，由于哈希沖突的存在，哈希在同一路徑上的多個流會發(fā)生擁塞，從而增加時延，減少了網(wǎng)絡吞吐量。Hedera專注于將一個流分配到當前最佳路徑，卻忽略了該路徑承載多個流時的沖突問題，從而使多個流的傳輸都無法獲得最佳性能。TPLM使用穩(wěn)定匹配理論將所有流分配給適當?shù)穆窂剑淦ヅ錂C制有效地避免了擁塞，從全局的角度調(diào)度流量，為整個網(wǎng)絡流調(diào)度找到全局最優(yōu)解。因此，與ECMP和Hedera相比，TPLM具有更好的性能。

5 結 語

本文研究了數(shù)據(jù)中心大象流調(diào)度問題，發(fā)現(xiàn)數(shù)據(jù)中心內(nèi)“東西向”大象流的合理調(diào)度是數(shù)據(jù)中心流量負載均衡的關鍵點，并應用穩(wěn)定匹配理論提出解決方案TPLM，TPLM主要考慮了交換機和大象流之間的關系，建立大象流和交換機的層次匹配模型，TPLM可以有效地避免網(wǎng)絡擁塞?；贔loodlight和Mininet的實驗結果表明，大象流的吞吐量和全網(wǎng)吞吐量得到顯著提升，老鼠流的平均流完成時間在顯著降低。