基于SDN的數據中心流量負載均衡

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

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

0 引 言

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

傳統網絡具有純分布式結構，轉發和控制高度耦合在每個網絡設備中，導致針對性高且復雜的調度模式難以在傳統網絡中部署，數據中心也很難根據網絡狀態動態調整策略。

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

1 相關工作

數據中心網絡中的流量調度一直是一個活躍的研究領域，這個研究領域已經有很多成果。

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

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

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

2 系統分析與建模

2.1 系統總覽

如圖1所示，K-pod Fat-Tree網絡分為三個層次：自下而上分別為邊緣層(edge)、匯聚層(aggregate)和核心層(core)，拓撲含有(k/2)2個核心交換機，其中匯聚層交換機與邊緣層交換機構成一個pod，每個pod有k個匯聚層交換機。在此網絡拓撲中，定義三種流量調度模式：pod間流調度、pod內流調度和機柜流量調度。pod間流調度指不同pod間任何主機對之間的通信，由拓撲結構可知，pod間流必須經過其中核心交換機，所以當pod間流到達時，只需要為其選擇合適的核心交換機，就能確定此流量的最短路徑[8]。機柜流量調度指連接在同一交換機上的任意兩臺主機間的通信，因此只有一條傳輸路徑。pod內流調度指同一pod內任意兩個不連接在同一交換機上的主機間的通信，同pod間流調度類似，只需為流分配匯聚交換機。例如，主機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網絡架構

如上述所示，當數據中心在進行流量調度時，我們的關注對象由路徑和流變為交換機和流。

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

圖2 共享內存式交換機原理

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

2) 流：數據中心的流量可以分為大象流和老鼠流兩類，根據以往的研究表明，數據中心的流量服從長尾概率分布，大象流數量只占流總數的20%，但卻占據了90%的網絡流量[9]，本文的重點關注數據中心中服務器之間傳輸的大象流集合。如沒有特殊說明，以下提及的流皆指大象流。

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

2.2 流-交換機匹配模型

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

(1)

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

(2)

定義1流的交換機優先級列表順序由交換機內存大小決定。

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

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

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

定義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 匹配沖突問題

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

圖3 匹配沖突示例

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

3 系統方案與實現

3.1 TPLM算法

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

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

輸出：最優解集合M。

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

2.初始化M為空

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

4.sj=優先級最高且未拒絕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.根據當前匹配結果M更新C

15.endif

16.endWhile

17.ReturnM

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

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

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

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

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

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

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

3.2 系統方案

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

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

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

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

定理2TPLM所得的匹配一定穩定。

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

3.3 負載均衡架構

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

圖4 負載均衡架構

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

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

Schedule：該模塊主要的工作是執行TPLM算法，得到最優匹配后把匹配結果轉化為流表規則的形式下發到數據平面。

4 仿真與評估

4.1 仿真環境

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

表1 仿真參數

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

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

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

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

4.2 仿真結果與分析

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

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

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

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

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

圖7 大象流的吞吐量隨網絡負載變化

圖8 老鼠流的吞吐量隨網絡負載變化

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

圖9 網絡時延隨網絡負載變化

由于將穩定匹配應用于大象流調度，這將為數據傳輸和網絡容量均獲得最佳結果，因此，網絡吞吐量、FCT、時延的性能均顯示了TPLM的有效性。

ECMP通過哈希的手段得到流的轉發路徑，由于哈希沖突的存在，哈希在同一路徑上的多個流會發生擁塞，從而增加時延，減少了網絡吞吐量。Hedera專注于將一個流分配到當前最佳路徑，卻忽略了該路徑承載多個流時的沖突問題，從而使多個流的傳輸都無法獲得最佳性能。TPLM使用穩定匹配理論將所有流分配給適當的路徑，其匹配機制有效地避免了擁塞，從全局的角度調度流量，為整個網絡流調度找到全局最優解。因此，與ECMP和Hedera相比，TPLM具有更好的性能。

5 結 語

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