基于粒子群優(yōu)化算法的數(shù)據(jù)中心網(wǎng)絡流量調(diào)度策略*

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

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

0 引 言

隨著數(shù)據(jù)中心規(guī)模不斷擴展以及業(yè)務類型越來越多,豐富的業(yè)務需要大量的服務器組成集群系統(tǒng)協(xié)同完成工作，數(shù)據(jù)中心內(nèi)部的通信變得更加頻繁，從而使得數(shù)據(jù)中心的東西向流量逐漸增多，數(shù)據(jù)中心網(wǎng)絡流量由“南北”為主轉(zhuǎn)為“東西”為主。

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

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

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

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

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

1 系統(tǒng)框架

為實現(xiàn)網(wǎng)絡流量的合理調(diào)度，本文的系統(tǒng)框架包括拓撲發(fā)現(xiàn)、流量信息統(tǒng)計、帶寬需求估計、優(yōu)化算法計算路徑及下發(fā)流表至交換機等5個模塊，如圖1所示。

圖1 系統(tǒng)框架圖

(1)拓撲信息模塊

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

(2)信息統(tǒng)計模塊

控制器向交換機下發(fā)統(tǒng)計信息請求報文，交換收到請求報文后發(fā)送統(tǒng)計信息回復報文給控制器，控制器通過解析報文得到統(tǒng)計信息并將其保存到數(shù)據(jù)結(jié)構(gòu)中。

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

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

(4)帶寬需求估計模塊

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

(5)計算路徑模塊

根據(jù)獲取的拓撲信息及流量統(tǒng)計信息，利用優(yōu)化的粒子群算法為大流計算最佳傳輸路徑。

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

控制器通過packet-out報文向交換機下發(fā)流表信息，將流表安裝至交換機，交換機根據(jù)流表信息完成流量的轉(zhuǎn)發(fā)。

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

2 問題描述與模型建立

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

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

圖2 Fat-Tree拓撲示意圖

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

(1)

式中：byte_countt1和byte_countt2分別表示t1、t2時刻接入層交換機傳輸?shù)淖止?jié)數(shù)。

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

(2)

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

(3)

(4)

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

(5)

式中：α∈(0,1)。

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

(6)

二是流量守恒定律

(7)

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

3 改進的粒子群優(yōu)化算法

3.1 算法原理

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

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表示粒子位置，ω表示粒子速度慣性權重系數(shù)，c1和c2表示學習因子，r1和r2是0～1區(qū)間的一個隨機數(shù)，Pi(n)表示第i顆粒子迄今位置搜索到的最優(yōu)位置，Pg(n)表示整個粒子群的最優(yōu)位置。

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

(10)

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

(11)

式中：M表示種群規(guī)模，F(xiàn)itavg表示所有粒子的平均適應度值，

(12)

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

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

(13)

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

T=Tinit×Cn。

(14)

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

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

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

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

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

(15)

3.2 算法設計

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

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

具體流程如下：

Step1 定義粒子編碼方案。

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

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

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

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

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

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

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

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

4 實驗仿真與分析

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

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

4.1 仿真參數(shù)設置

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

表1 目標函數(shù)參數(shù)設置

表2 TSM_PSO算法參數(shù)設置

4.2 實驗結(jié)果分析

4.2.1 不同網(wǎng)絡負載下的網(wǎng)絡平均吞吐量

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

圖3 不同網(wǎng)絡負載下的網(wǎng)絡平均吞吐量

4.2.2 不同網(wǎng)絡負載下的鏈路丟包率

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

圖4 不同網(wǎng)絡負載下的鏈路丟包率

4.2.3 不同流量模型下的網(wǎng)絡平均吞吐量及丟包率

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

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

圖5 不同流量模式下的網(wǎng)絡平均吞吐量

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

5 結(jié)束語

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

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