基于對偶分解的數(shù)據(jù)中心網(wǎng)絡(luò)流量工程方法

劉 奕，李建華，陳 玉

(1. 空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077；2. 空軍工程大學(xué)研究生院，陜西 西安 710038)

1 引言

數(shù)據(jù)中心網(wǎng)絡(luò)作為聯(lián)合裝備網(wǎng)絡(luò)的核心，對戰(zhàn)場信息進行存儲和處理，實現(xiàn)各軍種裝備信息實時共享。然而，隨著武器裝備和信息技術(shù)的發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)通信量迅速增加，對網(wǎng)絡(luò)帶寬資源的需求與日俱增，給流量工程(traffic engineering，TE)帶來新的挑戰(zhàn)，需要在保證網(wǎng)絡(luò)資源利用率基礎(chǔ)上，提高數(shù)據(jù)中心網(wǎng)絡(luò)的實時響應(yīng)能力，增強聯(lián)合裝備網(wǎng)絡(luò)系統(tǒng)效能。

軟件定義網(wǎng)絡(luò)(software defined network，SDN)作為新型的網(wǎng)絡(luò)架構(gòu)，通過OpenFlow技術(shù)將控制層面和數(shù)據(jù)層面相分離，并具有開放的可編程接口和全局化的網(wǎng)絡(luò)視圖，為網(wǎng)絡(luò)流量的精細(xì)化、智能化管理提供新的思路。

目前數(shù)據(jù)中心網(wǎng)絡(luò)中的TE方法主要分為啟發(fā)式方法和最優(yōu)化方法。文獻(xiàn)[5]提出一種基于Hash表的等價多路徑(equal cos t muti-path，ECMP)方法，該方法通過對數(shù)據(jù)流的包頭進行哈希運算，根據(jù)運算結(jié)果將負(fù)載分發(fā)到多條路徑上進行傳輸，充分利用網(wǎng)絡(luò)中大量冗余路徑，實現(xiàn)流量均衡分配和鏈路備份。該算法對于老鼠流可以實現(xiàn)有效的分配轉(zhuǎn)發(fā)，而對于多條大象流可能會造成hash路徑上的數(shù)據(jù)流碰撞，導(dǎo)致鏈路擁塞。文獻(xiàn)[7]提出一種動態(tài)路徑分區(qū)算法，利用ECMP方法將老鼠流調(diào)度在低延遲路徑上傳輸，大象流調(diào)度在高吞吐量路徑上傳輸。該算法有效降低了大小流的資源競爭，但在網(wǎng)絡(luò)數(shù)據(jù)量較大時，單條路徑很難滿足大象流的帶寬需求，導(dǎo)致傳輸延遲和鏈路擁塞。文獻(xiàn)[8]提出一種基于SDN穩(wěn)定匹配的流量調(diào)度算法，該算法通過計算大象流所需帶寬與路徑剩余帶寬的匹配度是否滿足預(yù)設(shè)閾值，來選擇大象流最佳調(diào)度路徑。算法可以有效提高網(wǎng)絡(luò)帶寬利用率，但匹配精度低，計算復(fù)雜度高，網(wǎng)絡(luò)流量分配不均。文獻(xiàn)[9]提出一種基于SDN的大象流多路徑調(diào)度算法，該算法通過設(shè)置網(wǎng)絡(luò)負(fù)載閾值來檢測大象流，然后利用控制器OpenFlow特性將大象流分解成若干老鼠流進行傳輸，并實時檢測網(wǎng)絡(luò)鏈路狀態(tài)，確保動態(tài)均衡。算法提高了網(wǎng)絡(luò)鏈路利用率，但大象流的多次分解會造成數(shù)據(jù)包接收順序錯亂，導(dǎo)致網(wǎng)絡(luò)丟包率增加。上述算法均屬于啟發(fā)式方法，當(dāng)數(shù)據(jù)中心的服務(wù)器較多時，該類算法的搜索空間規(guī)模大幅增加，為了減小計算過程中的搜索空間，只考慮了部分流(通常是大象流)，通過犧牲全局最優(yōu)解的方式來降低計算時間。文獻(xiàn)[10]結(jié)合對稱拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)特點，提出一種基于每包輪循的路由算法(digit-reverseal bouncing，DRB)，能夠在對稱多根樹拓?fù)渲杏行У胤峙涿總€數(shù)據(jù)包，提高了網(wǎng)絡(luò)利用率，降低了延遲，但在實際的軍事信息系統(tǒng)中，數(shù)據(jù)中心網(wǎng)絡(luò)由于故障或遭受敵方攻擊等因素容易導(dǎo)致拓?fù)浣Y(jié)構(gòu)并不對稱，因此該方法魯棒性較差，實際應(yīng)用受限。

綜上所述，為了實現(xiàn)數(shù)據(jù)中心網(wǎng)絡(luò)流量的快速均衡調(diào)度，本文將最小化最大鏈路利用率作為目標(biāo)函數(shù)，利用對偶分解技術(shù)，將原問題分解為若干獨立的子問題，通過獨立求解和并行計算的方式，得到每個鏈路利用率的最優(yōu)上界，最大程度減少鏈路擁塞和運算時間，提高數(shù)據(jù)中心網(wǎng)絡(luò)的實時響應(yīng)能力，確保數(shù)據(jù)中心網(wǎng)絡(luò)中的應(yīng)用程序滿足服務(wù)質(zhì)量(quality of service，QoS)需求。

2 算法原理

本文采用線性規(guī)劃方法來解決數(shù)據(jù)中心的資源分配問題，其目標(biāo)函數(shù)是最小化網(wǎng)絡(luò)中最大鏈路利用率，為了減少搜索空間，將原問題分解成若干子問題，然后結(jié)合OpenMp方法在多個計算核心上并行求解子問題，最后通過整合子問題解得到原問題的最終解。

2.1 數(shù)學(xué)模型

假設(shè)一k元Fat-tree網(wǎng)絡(luò)結(jié)構(gòu)

G

(

V

，

E

)，其中核心層有(

k/

2)個交換機，主機總數(shù)為

k

/

4，

V

表示所有通信節(jié)點的集合，

E

表示兩通信節(jié)點的鏈路集合。對于每個interpod的通信需求，在網(wǎng)絡(luò)中任意給定的源節(jié)點和目標(biāo)節(jié)點對之間均有(

k/

2)條可能的路徑，并且這些路徑中的每一條對應(yīng)于一個核心交換機。本文目的是將通信需求分配到可用路徑，從而最小化各路徑的最大鏈路利用率，其最優(yōu)化數(shù)學(xué)模型可表示為

(1)

∑∈

f

(

p

)=

d

，?

i

(2)

約束式(1)保證了通過包含鏈路(

u

，

v

)的所有路徑的流量之和應(yīng)低于該鏈路的容量，約束式(2)確保了通過與某個需求相關(guān)聯(lián)的所有路徑的流量始終等于該需求的總量。通過最小化最大鏈路利用率

m

，實現(xiàn)數(shù)據(jù)中心網(wǎng)絡(luò)的負(fù)載均衡，同時將過載鏈路上的流量轉(zhuǎn)移到空閑鏈路上，防止個別鏈路的擁塞，導(dǎo)致網(wǎng)絡(luò)長時間延遲和數(shù)據(jù)包丟失，從而提高數(shù)據(jù)中心網(wǎng)絡(luò)的QoS。

2.2 模型分解

為了減少計算時間，本文結(jié)合Lagrange 對偶原理，將主問題分解為若干獨立子問題，則1

.

1節(jié)最優(yōu)化模型的對偶表達(dá)式為

(3)

X

(

u

，

v

)≤0

(4)

其中

D

是需求集，

X

(

u

，

v

)和

y

分別是對應(yīng)約束式(1)和(2)的對偶變量。對于每個(

u

，

v

)∈

E

，

X

(

u

，

v

)為約束(1)的對偶變量，對每個

i

∈

D

，

y

為約束式(2)的對偶變量。根據(jù)約束式(1)和(2)，

y

為任意，

X

(

u

，

v

)≤0，約束式(3)和(4)分別對應(yīng)于約束式(1)和(2)中每個

i

∈

D

、

p

∈

P

和

m

的變量

f

(

p

)。約束式(3)中對應(yīng)于變量

f

(

p

)的系數(shù)

X

(

u

，

v

)和

y

，與約束式(1)和(2)中每個(

u

，

v

)和

i

的系數(shù)

f

(

p

)相等。另一方面，目標(biāo)函數(shù)中的系數(shù)

f

(

p

)為零，則對應(yīng)于對偶式中的變量

f

(

p

)的約束將是約束(3)。類似地，對于每個(

u

，

v

)和

i

，約束(1)和(2)中的系數(shù)

m

分別為-

c

(

u

，

v

)和0，其目標(biāo)函數(shù)中的系數(shù)為1。因此，其對偶約束為∑(，)∈-

X

(

u

，

v

)×

C

(

u

，

v

)≤-1，等價于約束式(4)。

(5)

X

(

u

，

v

)≤0

(6)

(7)

其中，

?

i

∈

D

，

p

∈

P

X

(

u

，

v

)≤0

(8)

?

i

∈

I

，

p

∈

P

(9)

X

(

u

，

v

)≤0

(10)

其中

I

={

i

∈

D

：?

p

∈

P

，

p

∩

A

≠?}。對于每個

sub

，變量的數(shù)量是|

A

|+|

I

|，為了方便求解主問題的次梯度，求得

sub

的對偶表達(dá)式為

Minimize

Π

z

?(

u

，

v

)∈

A

(11)

(12)

其中

Π

是對應(yīng)于約束式(10)的對偶變量，

f

(

p

)是對應(yīng)于

sub

中約束式(9)的對偶變量。

2.3 主問題求解

(13)

可得

(14)

將不等式(17)與

φ

(

z

)=

Π

z

相加，可得

(15)

由式(15)可知，

Π

是在點

z

處的函數(shù)

φ

(

z

)的次梯度。因此，可在計算

sub

的最優(yōu)解之后，由式(16)求得主問題次梯度

ξ

=(

Π

，…，

Π

)

(16)

設(shè)

ξ

為第

r

次迭代時

Z

點上主問題的次梯度，

I

(

Z

)={

j

：

z

=0}，則次梯度投影可由式(17)計算

(17)

根據(jù)投影的次梯度，即可計算直線搜索步長

α

，如式(18)所示

(18)

根據(jù)搜索步長α，可計算出第r+1次迭代的Z值，如式(19)所示

(19)

則主問題求解算法具體流程如下：

Step

1：初始化 ε∈(0，1)，r=1，Z=(1/2，…，1)；

Step3：根據(jù)式(16)計算主問題的次梯度；

Step4：根據(jù)式(17)計算主問題中每個

j

=1，…，

n

的次梯度投影；Step5：如果‖

ξ

‖≤

ε

，停止迭代，否則轉(zhuǎn)向

Step

6。

Step6：利用式(18)計算直線搜索步長α，利用式(19)計算新的點，設(shè)置r=r+1，返回Step2。

3 仿真結(jié)果和分析

3.1 實驗環(huán)境

為了有效檢驗本文所提算法對數(shù)據(jù)中心流量的快速均衡調(diào)度性能，構(gòu)建k=16的Fat-tree模擬網(wǎng)絡(luò)，其中每個主機有20個請求隨機發(fā)送到其它pods的5個主機。模擬網(wǎng)絡(luò)中有1024個主機和20480個流，網(wǎng)絡(luò)交換機之間共有4096個鏈路。根據(jù)文獻(xiàn)[12]設(shè)置流量需求分布，網(wǎng)絡(luò)流量由查詢流量(2至20 kB)、延遲敏感短信息(100 kB至1 MB)和大象流(1至100 MB)組成，主問題中的子問題數(shù)為32。

算法運行平臺的操作系統(tǒng)版本：Windows 2012 R2，CPU：Quad 3.47 GHz Intel Xeon?X5690，內(nèi)存：16GB，有8個可用的計算核心，每個核心運行一個進程線程。

3.2 實驗分析

1)鏈路利用率分析

對比分析本文算法與文獻(xiàn)[5，9，10]三種算法的鏈路利用率情況，如圖1所示，實驗中Fat-tree網(wǎng)絡(luò)k=16。

圖1 四種算法的鏈路利用率

由圖1可知，本文算法優(yōu)化的流量負(fù)載較為均衡，沒有鏈路是擁塞的，所有鏈路的利用率約為0.37～0.67。文獻(xiàn)[5]ECMP算法的鏈路利用率約為0.34～0.98，隨著鏈路數(shù)量的增加，導(dǎo)致ECMP算法的負(fù)載分配不均衡更加顯著，當(dāng)鏈路數(shù)量較多時，會發(fā)生鏈路飽和情況，主要是由于ECMP算法將大象流映射到同一條路徑，從而導(dǎo)致明顯的負(fù)載失衡。文獻(xiàn)[9]算法的鏈路利用率約為0.38～0.85，該算法的鏈路利用率的最大值大于本文算法，主要是由于文獻(xiàn)[9]算法只關(guān)注大象流，分別利用啟發(fā)式方法和ECMP方法分配大象流和老鼠流，而本文算法對網(wǎng)絡(luò)中所有流的路徑進行了優(yōu)化配置。文獻(xiàn)[10]算法的鏈路利用率約為0.41～0.81，該算法的最大鏈路利用率較高，主要是由于其分配決策中并沒有考慮網(wǎng)絡(luò)的當(dāng)前狀態(tài)，導(dǎo)致當(dāng)網(wǎng)絡(luò)流量負(fù)載增多時，鏈路利用率增加明顯，而本文算法結(jié)合當(dāng)前網(wǎng)絡(luò)狀態(tài)，并對網(wǎng)絡(luò)中所有流的路徑進行了優(yōu)化配置，有效避免了路徑擁塞。

2)計算復(fù)雜度分析

對比分析k=4、k=8和 k=16三種Fat-tree網(wǎng)絡(luò)結(jié)構(gòu)下，文獻(xiàn)[9，10]和本文三種算法的計算時間，如圖2所示。

圖2 三種算法的計算時間

由圖2中可知，三種算法的計算時間均隨著網(wǎng)絡(luò)節(jié)點的增加而增加，文獻(xiàn)[10]的最優(yōu)化求解算法復(fù)雜度較高，隨著網(wǎng)絡(luò)節(jié)點的增加，計算時間增加明顯。本文算法經(jīng)過對偶分解，實現(xiàn)多線程并行運算，有效降低了計算時間，可以得到一個具有可容忍計算復(fù)雜度的最優(yōu)解，幾乎與文獻(xiàn)[9]啟發(fā)式算法的計算復(fù)雜度相同。

3)運算線程數(shù)分析

對比分析不同線程數(shù)量下，本文算法的計算時間，如圖3所示，實驗中Fat-tree網(wǎng)絡(luò)k=16。

圖3 不同線程數(shù)條件下的計算時間

本文經(jīng)過對偶分解，將多個子問題并行求解來減少計算時間。由圖3可知，當(dāng)并行求解的線程數(shù)量較小時，計算時間較長，隨著線程數(shù)增加，計算時間逐漸減少，當(dāng)線程數(shù)超過8時，計算時間略有增加，主要是由于增加線程的數(shù)量也會增加并行度，但是考慮到實驗平臺只有8個計算核心，每個核心一次運行1個線程，超過8個線程后就都會導(dǎo)致線程爭奪緩存資源，容易產(chǎn)生錯誤共享和計算時間增加，因此，在實際應(yīng)用過程中，應(yīng)根據(jù)硬件自身條件和需求，合理控制線程數(shù)量，已達(dá)到最佳流量均衡調(diào)度效果。

4 結(jié)語

針對數(shù)據(jù)中心網(wǎng)絡(luò)鏈路擁塞問題，提出一種基于對偶分解的數(shù)據(jù)中心網(wǎng)絡(luò)流量工程算法。利用對偶分解技術(shù)，將原問題分解為若干獨立的子問題，通過獨立求解和并行計算的方式，最大程度減少鏈路擁塞和運算時間，確保數(shù)據(jù)中心網(wǎng)絡(luò)中的應(yīng)用程序滿足QoS需求。通過仿真表明：本文算法通過對網(wǎng)絡(luò)中所有流的路徑進行優(yōu)化配置，相比啟發(fā)式算法，降低了鏈路利用率，同時減少了計算時間，但在實際應(yīng)用過程中，應(yīng)合理控制線程數(shù)量。