基于粒子群優化算法的數據中心網絡流量調度策略*

馬樞清，唐 宏，李 藝，雷援杰

(重慶郵電大學 a.通信與信息工程學院；b.移動通信技術重慶市重點實驗室，重慶 400065)

0 引 言

隨著數據中心規模不斷擴展以及業務類型越來越多,豐富的業務需要大量的服務器組成集群系統協同完成工作，數據中心內部的通信變得更加頻繁，從而使得數據中心的東西向流量逐漸增多，數據中心網絡流量由“南北”為主轉為“東西”為主。

傳統數據中心網絡將網絡設備、操作系統及網絡應用緊耦合在一起，相互依賴，任一部分更新升級則要求另外兩部分做出同樣的升級，導致網絡擴展難度很高，嚴重阻礙了網絡的快速發展。軟件定義網絡(Software Defined Network,SDN)的出現為數據中心網絡的發展提供了契機[1]。SDN將數據平面和控制平面分離，底層硬件可以通用，控制平面的控制器通過南向接口對數據平面編程控制和配置管理，同時通過北向接口給應用層提供可編程能力。控制器起到了集中控制網絡的作用，很好地適應了數據中心網絡的需求。

研究表明[2]，當前數據中心流量80%的流持續時間不超過10 s，不到0.1%的流持續時間超過200 s。文獻[3]指出，90%的流攜帶不超過1 MB的數據，超過90%的字節傳輸在大于100 MB的流中。因此，根據流占用鏈路帶寬大小以及在網絡中的持續時間長短將流量分為大流和小流。但一般網絡中兩類流量是并存的，如果不考慮流特征，隨意地選擇流傳輸路徑，容易造成鏈路帶寬負載不均衡且帶寬浪費問題。因此，如何設計一種有效的流量調度策略是當前數據中心網絡中一項重要的研究內容。

針對數據中心網絡的流量調度問題，國內外研究者提出了許多方案。最早提出的等價多路徑路由算法(Equal Cost Multi Path Routing,ECMP)[4]針對同一目的地址的網絡流量，采用靜態計算路徑的哈希值的分配方式為網絡流計算傳輸路徑，能夠很好地服務小流，但可能會導致多條大流調度到同一路徑的情況，增加鏈路擁塞的可能性。Al-Fares等人[5]提出了一種動態流量調度算法(Global First Fit,GFF)，首先在邊緣交換機上監測大流，然后估計大流的自然帶寬需求，利用算法為大流計算最先適應其帶寬需求的傳輸路徑，最后將路徑方案安裝至交換機流表中。但該算法設置的流檢測時間太長，不能有效獲取網絡信息。文獻[6]提出了一種自適應多路徑負載均衡策略，通過自適應學習過程對網絡數據包進行重路由計算，有效實現較高的吞吐量，但是存在流表更新頻繁的問題。

文獻[7]表明，相較于其他群體智能算法，粒子群算法具有參數少、收斂快且精度高等特點，更適用于為網絡流量高效快速地尋找最佳調度路徑。但粒子群算法容易陷入局部最優且后期收斂速度很慢，因此，很多研究對其進行了改進[7-9]，但均存在不足。

基于以上分析，結合現有的數據中心網絡流量調度算法存在的不足，本文提出了一種基于粒子群算法的流量調度方法(Traffic Scheduling Method based on PSO,TSM_PSO),將鏈路可用帶寬和流帶寬需求作為網絡流尋找流量最優調度路徑的考慮因素，將鏈路狀態評估值和帶寬適配率的加權函數作為優化目標函數。針對粒子群算法易陷入局部最優的問題，本文利用粒子適應度函數重新定義了粒子聚合度，并引入metropolis接受準則[10]使粒子跳出局部最優。本文算法主要用于為大流計算最佳調度路徑，由于小流對時延要求高，因此采用等價多路徑算法[4]為小流計算轉發路徑。

1 系統框架

為實現網絡流量的合理調度，本文的系統框架包括拓撲發現、流量信息統計、帶寬需求估計、優化算法計算路徑及下發流表至交換機等5個模塊，如圖1所示。

圖1 系統框架圖

(1)拓撲信息模塊

控制器將攜帶了LLDP數據包的packet-out報文發送到交換機的指定端口，收到LLDP數據包的交換機將數據包發送給鄰接交換機。鄰接交換機收到LLDP數據包后，通過packet-in報文將數據包發送給控制器，控制器收到數據包后結合packet-in信息和LLDP數據包的包頭信息，最終獲取網絡拓撲信息。

(2)信息統計模塊

控制器向交換機下發統計信息請求報文，交換收到請求報文后發送統計信息回復報文給控制器，控制器通過解析報文得到統計信息并將其保存到數據結構中。

(3)K最短路徑算法模塊

該模塊利用python的一個軟件包networkx中內置的KSP算法，通過該算法找出流的源主機和目的主機之間包含K條最短路徑的集合。本文為了縮減算法的無效搜索范圍，先利用KSP算法找出一個最短路徑集作為初始路徑集。

(4)帶寬需求估計模塊

由于流占用的帶寬通常受到源主機和目的主機的網絡接口設備限制，當前占用帶寬情況不能完全代表流的真實帶寬需求[11]。因此，需要通過該模塊在網絡傳輸無限制的理想情況下獲取網絡流量的自然帶寬需求。

(5)計算路徑模塊

根據獲取的拓撲信息及流量統計信息，利用優化的粒子群算法為大流計算最佳傳輸路徑。

(6)安裝流表至交換機模塊

控制器通過packet-out報文向交換機下發流表信息，將流表安裝至交換機，交換機根據流表信息完成流量的轉發。

流量調度算法的整體流程為：網絡流量到達邊緣交換機，邊緣交換機根據流的源主機地址和目的主機地址判斷它們是否直連，如果是則直接轉發；如果不是，則根據設定的網絡流量閾值將網絡流分為大流和小流。本文采用ECMP算法[4]為小流計算轉發路徑，控制器結合大流的統計信息和拓撲信息，利用優化的粒子群算法為大流計算最佳傳輸路徑，將包含路徑信息的流表安裝至交換機，最后交換機完成大流的轉發。

2 問題描述與模型建立

針對當前數據中心網絡流量調度算法存在鏈路帶寬負載不均衡及帶寬資源浪費的問題，綜合考慮當前網絡可用帶寬資源狀況以及待調度網絡流量的實際帶寬需求，建立如下模型。

由于Fat-Tree結構簡單且易于擴展，主機之間有多條可達路徑，因此本文采用Fat-Tree[12]作為實驗拓撲，如圖2所示。

圖2 Fat-Tree拓撲示意圖

邊緣層交換機根據網絡流的傳輸速率將網絡流量分為大流和小流。網絡流到達接入層交換機時，根據網絡流量的傳輸速率將其分類，本文將傳輸速率超過鏈路帶寬的10%的網絡流量判定為大流，小于鏈路帶寬的10%的網絡流量則判定為小流。網絡流量的傳輸速率計算公式如下：

(1)

式中：byte_countt1和byte_countt2分別表示t1、t2時刻接入層交換機傳輸的字節數。

將本文拓撲記為圖G(V,E)，其中V表示所有交換機節點的集合，E表示鏈路的集合。將n條大象流記為f={f1,f2,…,fs,…,fn}，鏈路容量為C，第s條網絡流的帶寬需求為bs。由KSP算法找出初始路徑集P={P1,P2,…,Pk}，第i條路徑Pi={li1,li2,…,liq}。設路徑i上第j鏈路的可用帶寬為Bij，則路徑可用帶寬Bi=min(Bi1,Bi2,…,Biq)。因此，第i條路徑的鏈路平均可用帶寬Baverage可表示為

(2)

為網絡流計算調度路徑時，如果鏈路可用帶寬與鏈路帶寬平均值的偏差程度越小，則在一定程度上網絡的負載均衡效果越好，因此提出鏈路評估函數efi:

(3)

(4)

由公式(4)可知，為網絡流計算調度路徑時，如果只考慮是否造成帶寬浪費問題，則可能會出現部分鏈路過載而其余鏈路空閑的情況。因此，綜合考慮鏈路帶寬偏差及流帶寬需求與實際鏈路帶寬的適配程度，建立的目標函數F如下所示：

(5)

式中：α∈(0,1)。

約束條件有兩個，一是鏈路帶寬約束條件

(6)

二是流量守恒定律

(7)

其中公式(6)考慮了鏈路帶寬利用率約束，μi,j表示第i條路徑上第j條鏈路的鏈路帶寬利用率；公式(7)表示流調度過程中必須滿足的流量守恒定律，中間節點流入與流出的流量必須相等。

3 改進的粒子群優化算法

3.1 算法原理

粒子群優化算法由美國社會心理學家Kenney和電氣工程師Eberhart首次提出。他們受到鳥群覓食過程的規律性啟發，進而利用群體智能建立的一個簡化模型。將鳥群中的鳥簡化為粒子，每個粒子的都有一個飛行速度和位置，通過更新粒子的飛行速度和位置，為鳥群尋找最佳位置:

vi(n+1)=ωvi(n)+c1r1(Pi(n)-xi(n))+

c2r2(Pg(n)-xi(n))，

(8)

xi(n+1)=xi(n)+vi(n+1) 。

(9)

式中：vi表示粒子速度，xi表示粒子位置，ω表示粒子速度慣性權重系數，c1和c2表示學習因子，r1和r2是0～1區間的一個隨機數，Pi(n)表示第i顆粒子迄今位置搜索到的最優位置，Pg(n)表示整個粒子群的最優位置。

相較于其他群體智能算法，粒子群算法實現簡單、收斂速度快且求解精度高，更適用于為網絡流量尋找最佳調度路徑。但粒子群算法易陷入局部最優情形，區別于文獻[7]中的種群聚集度和文獻[8]中的粒子相似度，它們主要采用粒子之間的空間距離確定粒子相似程度，而本文算法基于粒子適應度函數定義了粒子聚合度。適應度函數是評價粒子位置好壞的重要依據，本文用目標函數構造適應度函數,如公式(10)所示:

(10)

定義2：粒子聚合度是衡量粒子的聚散程度，如果粒子聚合度值越高則粒子越易陷入局部最優，公式如下：

(11)

式中：M表示種群規模，Fitavg表示所有粒子的平均適應度值，

(12)

當粒子聚合度δ小于設定的閾值時，則將當前粒子的適應度值和上一代粒子的適應度值比較，如果當代粒子適應度值小于上一代粒子適應度值，則更新粒子最優位置；反之，粒子位置不更新。

粒子聚合度δ很大時，說明群體中部分粒子的適應度值遠遠超過群體的平均適應值，使得這些粒子很快在種群中占絕對比例，種群的群體進化能力弱化，易陷入局部最優。因此，當粒子聚合度δ大于設定的閾值時，本文借鑒metropolis接受準則[10]，使粒子在更新過程中能以一定概率接受當前狀態下的較差解，增加解的多樣性，一定程度上避免算法陷入局部最優。計算公式如下：

(13)

Fit函數表示適應度函數，T為當前溫度，更新公式如式(14)所示:

T=Tinit×Cn。

(14)

式中：C為溫度變化率，為模擬徐徐降溫的過程，一般取值0.95～0.99。

(1)如果當前粒子的適用度函數F(xi(n+1))小于F(Pi(n))，則Pi(n+1)=xi(n+1)；

(2)如果當前粒子的適用度函數F(xi(n+1))大于F(Pi(n))，求得粒子最優位置更新的概率為p，當p大于random(0,1)時，Pi(n+1)=xi(n+1)，其中random(0,1)表示0～1之間的均勻分布隨機數；

(3)如果當p小于random(0,1)時，Pi(n+1)=Pi(n)。

由粒子速度更新公式可知，慣性權重ω作為速度的系數，在很大程度上決定了粒子的搜索空間范圍。為了使算法初期在全局范圍內快速搜索，當搜索空間快速收斂于某一區域后，后期在這一區域內進行局部精細搜索。因此，提出一個慣性權重優化方法，如公式(15)所示:

(15)

3.2 算法設計

在Fat-Tree拓撲結構中，任意兩臺主機之間存在多條可達路徑。本文通過KSP算法計算出k條最短路徑的集合，并將該最短路徑集作為粒子群優化算法的初始輸入。

將n條大象流記為f={f1,f2,…,fs,…,fn}，第s條網絡流的帶寬需求為bs，記n條大流對應的一種路徑方案為D={d1,d2,…,dn}，其中di表示第i條網絡流的路徑編號。在粒子群中，M顆粒子組成的集合表示為X=[X1,X2,…,XM]，其中，Xi={xi1,xi2,…,xin}表示維度為n的第i顆粒子位置。基于以上分析，本文將粒子的編碼方案定義為每一個粒子位置Xi對應一種流調度方案D，第i顆粒子的第i維位置xii對應了D中第i條網絡流的調度路徑，即網絡流的最佳調度路徑就是粒子群優化算法中的最優解。

具體流程如下：

Step1 定義粒子編碼方案。

Step2 初始化粒子群算法參數，包括種群規模、粒子維度、迭代次數和慣性權重等，設置初始溫度及退火系數。

Step3 初始化粒子速度和位置，從最短路徑集中隨機選擇一條路徑作為粒子的初始位置。

Step4 通過鏈路的統計信息計算粒子對應路徑的適應度函數值，由適應度值算出當前粒子的聚合度。如果粒子聚合度小于設定的閾值，轉至Step 5；如果粒子聚合度值大于設定的閾值，則轉至Step 6。

Step5 將當代粒子適應度值和上一代粒子個體最優適應度值比較，如果當代適應度值小于上一代粒子個體最優適應度值，則更新粒子個體最優解，反之則不更新。

Step6 引入metropolis準則判斷是否更新個體最優解，然后通過比較種群中全部粒子的個體最優解求得全局最優解。

Step7 迭代次數加1，粒子進入下一代，更新慣性權重，通過位置和速度更新公式更新粒子位置和速度。

Step8 判斷是否達到收斂條件或者最大迭代次數，如果沒有，則更新退火溫度，重復Step 4；反之算法停止，輸出結果，得到大流的最優調度路徑。

下面對本文算法的時間復雜度作簡要分析。假設網絡中有大流n條，小流有m條，流的源主機和目的主機之間共有(k/2)2條可達路徑，本文算法迭代次數為F，種群規模為M，則算法的時間復雜度為O(nMF(k/2)2)+O(m)。

4 實驗仿真與分析

本文實驗在輕量級仿真工具Mininet和Ryu控制器上完成仿真。Mininet為實驗搭建網絡拓撲，使用Iperf產生流量，交換機之間的最大鏈路帶寬設置為1 Gb/s，間隔1 s使用bwm-ng工具檢測端口傳輸數據的統計信息，每20 s重新加載一次拓撲結構。

本文實驗仿真包括不同網絡負載以及不同流量模式下的算法性能比較。其中，不同網絡負載的含義為網絡中發送大流的主機數占比,不同流量模式主要包括random和stag_pEdge_pPodIn兩類,random流量模式表示源主機以隨機方式向目的主機發送大流,而stag_pEdge_pPodIn表示在源主機發送的流量中，有pEdge占比的流量發送到同一接入層交換機的主機，發送到同一pod內主機的流量占比為pPodIn，剩余占比為1-pPodIn-pEdge的流量發送給不同pod的主機。

4.1 仿真參數設置

本文所提算法目標函數的權重由仿真實驗確定。由表1可看出，當α取值0.6時，本文所提算法的整體性能最佳。其他參數在本實驗中的具體設置如表2所示，經驗取值表示該算法參數在多數研究中的一般取值范圍。

表1 目標函數參數設置

表2 TSM_PSO算法參數設置

4.2 實驗結果分析

4.2.1 不同網絡負載下的網絡平均吞吐量

網絡負載指的是發送大流的主機所占比例，網絡平均吞吐量指的是在當前網絡負載狀況下傳輸數據量的平均值，是衡量網絡傳輸性能的關鍵因素。圖3給出了本文算法TSM_PSO與DLB_PSO、ECMP、GFF和EFLB不同網絡負載狀況的網絡平均吞吐量，可以看出，網絡負載較低時，網絡流很少，ECMP和GFF算法較為簡單，DLB_PSO也只需采用簡單的流量調度算法為網絡流計算傳輸路徑，因此表現出相對較好的性能。隨著網絡負載的增加，ECMP不考慮鏈路狀態，等價分配路徑給網絡流，容易將多條網絡流調度到同一路徑上。GFF總是為網絡流找到最先滿足網絡需求的傳輸路徑，導致網絡帶寬的浪費。EFLB只考慮了為網絡流尋找負載最小的鏈路，后續的流到達時可能無法找到適合轉發的路徑。DLB_PSO僅考慮通過選擇核心層交換機為大流計算轉發路徑，忽略了大流在匯聚層交換機的轉發，增加了大流在核心層交換機沖突的可能性。而本文算法同時考慮鏈路狀態與網絡流的需求，減輕了鏈路帶寬資源浪費問題，且為流計算轉發路徑時，不局限于選擇合適核心層交換機確定調度路徑，尋優的范圍更廣，流量碰撞的可能性更小。因此，本文算法獲取的平均吞吐量相對更高。

圖3 不同網絡負載下的網絡平均吞吐量

4.2.2 不同網絡負載下的鏈路丟包率

丟包率表明網絡流在網絡中的擁塞狀況，是衡量網絡傳輸性能的另一個重要因素。從圖4可以看出，在網絡負載較低時，網絡流較少，鏈路中存在很多的空閑鏈路，5種算法的丟包率幾乎為0。但隨著負載增加，網絡擁塞的可能性加大，5種算法的丟包率也更明顯。相比于其余3種算法，TSM_PSO與DLB_PSO獲得較低的丟包率，但由于DLB_PSO為網絡流計算調度路徑的范圍較窄，導致網絡流無法快速找到路徑，其算法性能不穩定。

圖4 不同網絡負載下的鏈路丟包率

4.2.3 不同流量模型下的網絡平均吞吐量及丟包率

由圖5可得，pod內網絡流量較多時，5種算法的性能差別較小，網絡平均吞吐量較高。但隨著pod間流量的增加，網絡流碰撞的可能性加大，相比于其他對比算法，TSM_PSO與DLB_PSO測得的平均吞吐量更高，說明這兩種算法更適用于pod間網絡流量較多的情況。

圖5 不同流量模式下的鏈路丟包率

圖5 不同流量模式下的網絡平均吞吐量

圖6給出了5種算法在不同流量模式下的丟包率。當pod內和pod間的網絡流量較為均衡時，5種算法的網絡丟包率達到最小。當pod間網絡流量增多時，5種算法的丟包率都呈上升趨勢。其中，ECMP、GFF和EFLB導致網絡流量沖突的可能性很大，其丟包率急劇增加。DLB_PSO在pod間流量較多時，算法性能較好。Tsm_pso考慮了鏈路狀態，能夠快速合理地將網絡流量調度至合適的路徑上，減少了網絡流量碰撞的情況，從而丟包率最低，網絡的負載均衡性能更佳。

5 結束語

針對數據中心網絡中存在鏈路帶寬負載不均衡及帶寬資源浪費問題，綜合考慮鏈路狀態和流需求，本文提出了一種基于粒子群優化算法的數據中心網絡流量調度策略。通過粒子尋找最佳位置的過程為網絡流量計算最佳傳輸路徑，結合適應度函數定義粒子聚合度，進而判斷粒子是否有陷入局部最優的趨勢，并引入metropolis準則對有陷入局部最優趨勢的粒子進行引導，最后得出粒子的最佳位置即為一種網絡流量調度路徑方案。

仿真結果表明，在不同流量模式和不同網絡負載的情況下，本文所提算法能夠在一定程度上提高網絡吞吐量，同時降低網絡丟包率。相比于對比算法，在網絡負載較大時，本文算法表現出更佳的性能。但本文算法僅在Fat-tree拓撲架構下進行了仿真實驗分析，對于其他拓撲結構的性能效果需要進一步驗證。