劉 奕，李建華，陳 玉

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

1 引言

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

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

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

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

2 算法原理

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

2.1 數學模型

假設一k元Fat-tree網絡結構

G

(

V

，

E

)，其中核心層有(

k/

2)個交換機，主機總數為

k

/

4，

V

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

E

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

k/

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

(1)

∑∈

f

(

p

)=

d

，?

i

(2)

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

u

，

v

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

m

，實現數據中心網絡的負載均衡，同時將過載鏈路上的流量轉移到空閑鏈路上，防止個別鏈路的擁塞，導致網絡長時間延遲和數據包丟失，從而提高數據中心網絡的QoS。

2.2 模型分解

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

.

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

(3)

X

(

u

，

v

)≤0

(4)

其中

D

是需求集，

X

(

u

，

v

)和

y

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

u

，

v

)∈

E

，

X

(

u

，

v

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

i

∈

D

，

y

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

y

為任意，

X

(

u

，

v

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

i

∈

D

、

p

∈

P

和

m

的變量

f

(

p

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

f

(

p

)的系數

X

(

u

，

v

)和

y

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

u

，

v

)和

i

的系數

f

(

p

)相等。另一方面，目標函數中的系數

f

(

p

)為零，則對應于對偶式中的變量

f

(

p

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

u

，

v

)和

i

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

m

分別為-

c

(

u

，

v

)和0，其目標函數中的系數為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

，變量的數量是|

A

|+|

I

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

sub

的對偶表達式為

Minimize

Π

z

?(

u

，

v

)∈

A

(11)

(12)

其中

Π

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

f

(

p

)是對應于

sub

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

2.3 主問題求解

(13)

可得

(14)

將不等式(17)與

φ

(

z

)=

Π

z

相加，可得

(15)

由式(15)可知，

Π

是在點

z

處的函數

φ

(

z

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

sub

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

ξ

=(

Π

，…，

Π

)

(16)

設

ξ

為第

r

次迭代時

Z

點上主問題的次梯度，

I

(

Z

)={

j

：

z

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

(17)

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

α

，如式(18)所示

(18)

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

(19)

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

Step

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

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

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

j

=1，…，

n

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

ξ

‖≤

ε

，停止迭代，否則轉向

Step

6。

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

3 仿真結果和分析

3.1 實驗環(huán)境

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

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

3.2 實驗分析

1)鏈路利用率分析

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

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

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

2)計算復雜度分析

對比分析k=4、k=8和 k=16三種Fat-tree網絡結構下，文獻[9，10]和本文三種算法的計算時間，如圖2所示。

圖2 三種算法的計算時間

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

3)運算線程數分析

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

圖3 不同線程數條件下的計算時間

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

4 結語

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