基于軟件定義網絡的數據中心自適應多路徑負載均衡算法

許紅亮，楊桂芹，蔣占軍

（蘭州交通大學電子與信息工程學院，蘭州 730070）

0 引言

軟件定義網絡（Software Defined Network，SDN）［1-2］是網絡領域提出的一種新型架構，其核心理念是將網絡的控制平面與數據轉發平面分離解耦，實現網絡的集中控制和面向業務層可編程，網絡的可編程幫助控制底層網絡數據的轉發行為，有助于感知底層網絡的運行狀態。但隨著計算機和網絡產業的不斷推進，新型網絡應用的出現使得網絡通信量呈現爆發式增長，給數據中心網絡提出了考驗［3］。傳統網絡設備運行在封閉系統中，應用層不能感知底層網絡運行狀態，在有限的鏈路上處理海量的數據請求，給數據中心帶來極大流量壓力，出現負載不均衡、吞吐量低等問題。為解決該問題，國內外學者針對數據中心多路徑負載均衡［4］做了一些研究，采取靜態或動態的負載均衡算法來處理，這些算法雖然取得了效果，但缺少一定的自適應性，面對網絡中實時變化的動態流量，無法快速感知網絡運行狀態和鏈路的實時傳輸狀態，或者只是局限于實現局部的最優轉發，因此不能保證在全局最優的網絡狀態下，最大限度實現基于數據中心網絡的多路徑負載均衡。

傳統的負載均衡采用等價多路徑（Equal Cost Multi-Path，ECMP）路由算法［5-6］，其核心是將數據進行哈希計算，均衡在所有等價的路徑上，把流量負載平均分配在每條鏈路，來實現網絡數據轉發；但該算法缺少擁塞感知機制，未考慮網絡實時狀態。針對數據中心胖樹拓撲的網絡，目前也有一些其他的解決方案：AL-Fares 等［7］提出了全局首次匹配（Global First Fit，GFF）算法和模擬退火法。GFF算法獲取網絡中所有的鏈路信息，選取首次滿足匹配條件的路徑，雖然實現方法簡單但不能實現全局最優；模擬退火法用概率性搜索的方法，雖然選擇了全網最優的路徑轉發，但網絡收斂性變差。Li 等［8］通過局部動態的路由策略，實現了動態負載均衡（Dynamic Load Balancing，DLB），但該算法未從全局層面研究，導致局部鏈路負載太重，出現網絡擁塞現象。Lu 等［9］提出了基于SDN 的流量控制策略，在網絡利用率方面作了改進，但在路徑選擇時有排除更優路徑的可能。孫三山等［10］針對數據中心擁塞問題，提出基于流調度代價的擁塞控制路由算法（Flow Scheduling Cost based Congestion Control Routing Algorithm，FSC-CCRA），對數據流量區分大小流，根據定義流調度代價選取路徑，但該算法自適應動態選擇路徑的能力不足。

針對急劇增長的數據量給數據中心帶來的壓力、傳統封閉的網絡運行系統和有限鏈路傳輸的限制，使得網絡出現負載不均衡、吞吐量低等問題，本文選用新型架構軟件定義網絡（SDN），在此網絡背景下，利用SDN 能充分感知網絡實時運行狀態和集中管控的特點，結合蜘蛛猴優化（Spider Monkey Optimization，SMO）算法良好的自適應全局探索能力，提出了一種基于蜘蛛猴優化的SDN 自適應多路徑負載均衡算法（Load Balancing Algorithm based on SMO，SMO-LBA）。首先，建立SMO-LBA 的實現框架，通過各模塊的協調配合，實時獲取計算數據中心網絡中各路徑的鏈路空閑率；然后，計算評估各路徑相應的適應度值，在蜘蛛猴的本地領導者階段和全局領導者階段進行自適應評估更新；最后，動態選擇出數據中心網絡中鏈路占用率最小的路徑，且此路徑為全局最優路徑，作為數據最終選定的轉發路徑，根據選路結果，下發新的流表按此流表規則進行轉發，能有效解決在數據中心網絡環境下的負載不均衡的問題。

通過仿真實驗表明，SMO-LBA 發揮了SDN 感知底層網絡細節特征的優點，能獲取鏈路的實時狀態信息，同時利用蜘蛛猴優化算法的全局探索能力，從局部到全局地動態開采，自適應地調整數據流的選路，實現了數據中心網絡的負載均衡，有效地解決了傳統網絡缺乏感知和負載均衡算法缺少自適應性的問題。

1 算法設計與實現

1.1 算法實現架構

根據SDN 體系架構，其數據平面通過南向接口收到控制器的指令，按照指令要求處理網絡數據，南向接口反饋網絡配置和運行狀態信息給控制器，應用層通過北向應用程序接口（Application Programming Interface，API）對網絡進行控制。為實現本文提出的基于蜘蛛猴優化的自適應多路徑負載均衡算法（SMO-LBA），在算法實現框架內設計了信息收集模塊、網絡管理模塊、自適應路由模塊和流表下發模塊，總體框架如圖1 所示，這些模塊作為數據中心的核心功能模塊，完成網絡流量從收集到下發的所有流程，實現自適應多路徑負載均衡。

圖1 SMO-LBA實現框架Fig.1 SMO-LBA implementation framework

1.1.1 信息收集模塊

信息收集模塊作為基礎模塊，以信息收集代理模塊作為輔助，主要用來收集數據中心網絡中的實時狀態信息，探測感知網絡中各節點狀態信息和各路徑上的鏈路狀態信息，獲取數據中心完整網絡拓撲結構，建立相關路徑信息監測表，為后續自適應路由模塊提供全網拓撲結構和流量信息。信息收集模塊通過鏈路層發現協議（Link Layer Discovery Protocol，LLDP）［11］將相關信息封裝在Packet_in/Packet_out 消息中，在控制器和交換機之間通信，對反饋信息解析整理得到全網拓撲。

1.1.2 網絡管理模塊

為實現自適應動態負載均衡，需要對網絡內的參數實時動態監控，用網絡管理模塊周期性監測網內各參數信息。網絡管理模塊通過南向OpenFlow 協議［12］獲取端口統計信息，周期性獲得網絡流量和各轉發路徑負載情況，不斷更新管理路徑信息監測表，包括流管理、節點管理和鏈路管理，計算各路徑負載均衡度，一旦負載均衡度高于設定閾值，則調用自適應路由模塊，根據實時參數對路徑重新評估，選擇合適路徑轉發來降低負載均衡度。

1.1.3 自適應路由模塊

作為整個數據中心網絡架構的關鍵模塊，自適應路由模塊綜合來自信息收集模塊和網絡管理模塊的信息，基于全網路徑重新選路。該模塊主要采用基于蜘蛛猴優化的自適應多路徑負載均衡算法（SMO-LBA）對網絡中的多條路徑進行評估，以鏈路利用率作為目標函數，從局部到全局的過程進行尋優，為數據中心網絡流量尋找最佳轉發路徑，選取適應度值最高的路徑作為目的轉發路徑，對負載均衡度不滿足條件的路徑重新擇路。

1.1.4 流表下發模塊

流表下發模塊是根據自適應路由模塊評估最佳目的轉發路徑，產生對應的路由轉發策略，由Ryu控制器以流表的形式下發到各個交換機節點，交換機按照更新后的新流表執行自適應路由模塊的選路結果，根據轉發規則匹配相應的流表項，對數據中心網絡流量進行轉發，完成SDN 的自適應多路徑負載均衡。

1.2 算法設計思想

蜘蛛猴優化（SMO）算法［13］是受蜘蛛猴覓食行為啟發的群集智能優化算法，利用SMO 算法較強的開采能力和較高的尋優精度，本文針對基于SDN 的數據中心網絡提出了基于蜘蛛猴優化的自適應多路徑負載均衡算法（SMO-LBA），將各個網絡節點作為蜘蛛猴種群尋優的食物源，將數據流通過鏈路到達各個節點的過程模擬成蜘蛛猴種群在尋找最優食物所經過的路徑，獲取每條鏈路負載信息和從每個網絡節點出發所有鏈路的鏈路利用率，建立網內路徑轉發的路徑信息監測表，進行周期性的維護更新。

根據建立的路徑信息監測表，獲取節點以及鏈路的信息，得到實時鏈路負載均衡度V，表示為：

其中：Lp=Max{Lij|(i，j) ∈p}，i和j用來表示路徑上的節點位置，p是用節點表示的路徑集合，Lp表示當前轉發路徑的鏈路負載，把該路徑上各節點間最大的負載作為鏈路負載；Bm是該條路徑的實際帶寬n為當前轉發路徑的鏈路數目，Bmi表示每條轉發路徑的實時帶寬情況；Cp是數據中心網絡的所有數據流量，即所要處理的整體網絡負載；B是建設時總的網絡帶寬，表示為B=N×BMAX，N為總的傳輸鏈路條數，BMAX為鏈路的最大傳輸帶寬。以比值形式計算所有轉發路徑的負載均衡度，當負載均衡度越高時，說明這條鏈路上承載的流量越重，更需要通過重新選路來均衡負載，即觸發自適應路由模塊工作，開始執行SMO-LBA 擇路。依據大量研究中對負載均衡度閾值的設定，本文假設滿足觸發條件的最大負載均衡度閾值Vth為75%。

SMO-LBA 機制的原理是：首先，初始化網絡中的數據流，將其分為多個小組來盡量減少競爭的壓力，以便提高尋優效率和尋找最佳轉發路徑；其次，對于各小組，將尋優過程分為本地領導者（Local Leader）階段和全局領導者（Global Leader）階段，從局部到全局的順序不斷反饋更新，更新其在組內的最優結果；最后，全局領導者根據反饋結果更新至最優值，若結果未達到預先設定的閾值，則將組分為更小的組，重復執行上述步驟，直到找到最優的轉發路徑。

首先對所需相關參數初始化，構造數量為N的蜘蛛猴種群，DFi(i=1，2，…，N)是一個D維變量，代表種群中的第i只蜘蛛猴，即作為被優化問題的潛在解，按式（2）對其進行種群初始化：

式中：DFij是第i只蜘蛛猴的第j維分量；DFminj和DFmax_j是第j維上的邊界；U(0，1)是［0，1］上的隨機數。

在本地領導者階段，每個DF根據本地領導者和小組信息更新在網絡中的節點位置，計算新節點位置相應的適應度值Fit(DFi)：

其中：f(DFi)表示當前路徑的鏈路利用率；f(DFi)越小說明此路徑的占用程度越小，更易被選擇為解決負載問題需要的轉發路徑，計算出的適應度值相應變高，在位置更新過程中，新位置的適應度值高于原位置，則更新位置。

在繼承更新原位置的信息時，為了使算法在后期迭代的過程中有較好的局部搜索能力，考慮在位置更新中引入一個基于目標函數的動態自適應慣性權重［14］為w，由w表示在每次更新中，新位置對于原位置信息繼承的程度，通常取w為0到1 之間的常數。本文將鏈路利用率作為目標函數引入自適應慣性權重中，即把優化問題與蜘蛛猴個體的適應度建立映射關系，當隨著各負載鏈路情況發生變化，其所對應的適應度也相應變化。首先計算λ(k)：

其中：k(k=1，2，…) 為更新次數；f(DFi(k)) 為第i(i=1，2，…，N) 只猴子第k次更新相應位置的目標函數值；f(DFbest(k))為第k次更新的最優蜘蛛猴相應的目標函數值。根據λ(k)得到對應的w：

此處，當k=1時，取λ(0)=0.9，λ(k)用來衡量慣性權重w變化的平滑程度。

因此本地領導者階段的位置更新公式為：

其中：LLlj和DFrj分別表示第l組內本地領導者和第r只蜘蛛猴的第j維分量，r可以隨機選取。

完成本地領導者的尋優過程后，進入到全局領導者階段，在此階段蜘蛛猴通過全局領導者和本地小組信息更新在全局層面的位置。全局領導者階段更新公式如下：

其中：GLj為全局領導者的第j(j∈{}1，2，…，D)維分量，且j隨機選擇。

在全局領導者階段，蜘蛛猴種群對于全局的搜索能力變差，需要增大它對于全局的開發能力，因此在適應度計算的基礎上，通過適應度值再得到一個概率計算公式如式（8），用來獲得更大的開發幾率：

通過本地領導者階段和全局領導者階段的位置更新過程，最終獲取在分組情況下全網中最優轉發路徑，對超過負載閾值的數據流選擇最佳轉發路徑，通過控制器下發流表的形式，形成新的流表轉發策略，由流表下發模塊匹配轉發。

2 仿真與性能評估

2.1 仿真環境

本文使用Mininet2.3.0 版本仿真軟件［15］和Ryu 開源控制器完成仿真實驗平臺搭建，模擬基于SDN 的數據中心網絡運行環境，部署網絡實現架構中的各模塊。Mininet 是一個輕量級的虛擬網絡仿真平臺，它可以模擬一個真實完整的網絡環境，支持OpenFlow 協議與Ryu 控制器相連接，Ryu 是一款基于Python編寫的開源SDN控制器，作為算法實現的控制平臺，使用Iperf工具，模擬產生各主機之間的數據流量。

因為胖樹網絡具有多層次的樹狀拓撲結構固有的容錯能力，因此本文選擇構建一個K=4 的簡單胖樹網絡拓撲［16-17］，它能夠在核心層對多路徑負載及時處理，故選用它來模擬數據中心網絡場景，如圖2 所示。其中，匯聚層和邊緣層分為4個Pod，每個Pod 里都分別有2 臺交換機在匯聚層和2 臺交換機在邊緣層，核心層共有4 臺核心交換機，每臺交換機端口都與匯聚層交換機向上的級聯口相連接，網絡所支持的服務器總數為16臺。

圖2 K=4的胖樹網絡拓撲Fig.2 Fat-tree network topology with K=4

為完成蜘蛛猴種群在本地領導者階段和全局領導者階段的位置更新，在進行模擬仿真實驗時，將蜘蛛猴種群規模設置為數量為N=50的種群［13］，模擬數據在網絡中的尋優過程。

2.2 對比分析

搭建完整仿真實驗平臺之后，將數據中心網絡與Ryu 控制器遠程連接，用Iperf 流量工具模擬數據中心網絡多路徑數據流量，設置鏈路帶寬為100 Mb/s，控制器監控周期為5 s，逐步增大負載進行對比實驗。選取節點過載次數、傳輸時延和平均鏈路利用率三個性能指標，將本文算法與FSC-CCRA 和ECMP算法進行性能對比實驗，得到的實驗對比效果如下。

1）節點過載次數。

節點過載次數表示在數據流轉發過程中，由于負載過大使得節點發生過載情況的次數，轉發路徑的過載次數反映算法均衡負載的能力。若節點過載次數過大，表示在針對數據中心多路徑負載均衡時，算法不能根據實時網絡狀態，合理均衡負載完成數據轉發。節點過載次數實驗結果如圖3所示。

圖3 不同算法節點過載次數對比Fig.3 Comparison of node overload times of different algorithms

從圖3 可以看出，ECMP 算法處理負載時，出現過載的情況最嚴重；FSC-CCRA 處理負載有一定效果，但隨著負載的逐漸增加，也開始出現一定程度的過載問題，但發生節點過載的情況不嚴重；SMO-LBA 實現的效果最優，針對負載過大的路徑自適應重新選路，動態調整轉發路徑，避免節點過載情況發生，但當系統流量達到飽和時，網絡處理負載的能力受到限制，最終各算法節點過載次數趨近相同。

2）傳播時延。

傳播時延作為數據轉發過程中的常見指標，是指從發送端發送數據開始，到接收端接收數據總共經歷的時間。不同算法選路策略不同，導致傳播時延出現差異，實驗結果如圖4所示。由圖4 可看出：實驗最初三種算法傳播時延都同步上升，這是因為網絡還沒有數據流量轉發行為，需要上報Ryu控制器計算轉發路徑，下發安裝流表導致時延上升，但很快就回落到正常水平。當負載從10 Mb/s 增大到42 Mb/s 的過程中，系統鏈路健壯性良好，三種算法都能有效處理負載，所以傳播時延無太大差異。當負載超過42 Mb/s時，系統承載流量的加重使不同算法處理負載的能力出現差別，ECMP 算法傳播時延有較大變化，FSC-CCRA變化趨勢與SMO-LBA相近，但傳播時延還是呈現出較小的抖動，而本文的SMO-LBA 傳播時延雖然也有抖動現象，但基本平穩且傳播時延低于基于流調度代價的擁塞控制路由算法。

圖4 不同算法傳播時延對比Fig.4 Comparison of propagation delay of different algorithms

3）平均鏈路利用率。

平均鏈路利用率取所有鏈路利用率的平均值，表示為網絡運行時所有鏈路的占用帶寬與總帶寬之比，計算公式為：

式中：bmi(t)表示在t時刻，數據在第m條路徑第i條鏈路的傳輸帶寬；N為總的傳輸鏈路條數；BMAX為鏈路的最大傳輸帶寬。平均鏈路利用率實驗結果如圖5所示。

圖5 不同算法平均鏈路利用率對比Fig.5 Comparison of average link utilization of different algorithms

從圖5可看出：ECMP算法只是將負載均衡在所有等價路徑轉發，容易導致鏈路擁塞，故它的平均鏈路利用率最低；FSC-CCRA 對數據進行大小流區分，在網絡運行前期可以較好均衡負載，但隨著流量負載加重，由于自適應不足會造成局部鏈路承載流量過多，所以其鏈路利用率變化逐漸變緩；而SMO-LBA 綜合考慮了局部和全局的尋優，基于網絡實時鏈路負載，選取全網最優轉發路徑，因而其平均鏈路利用率呈現一定優越性。

2.3 實驗結論

綜上，實驗結果表明，當數據中心網絡負載較少、多路徑帶寬足夠時，三種算法仿真效果相當；但隨著數據流量的增大，對比算法處理負載的能力表現不足，出現局部負載過重或網絡擁塞問題，網絡系統無法承載當前流量，而本文提出的SMO-LBA 能夠實現全局動態尋優，通過重新選路自適應調整流量負載，實現網絡更高效的轉發。

3 結語

本文基于SDN 體系結構，針對數據中心網絡無法感知底層網絡細節以及缺少動態自適應選路方法的問題，提出了一種基于蜘蛛猴優化的自適應多路徑負載均衡算法（SMO-LBA），通過Ryu 控制器南向接口獲取網絡實時狀態及負載信息，對負載均衡度較高的路徑，調用自適應路由模塊重新選路，從局部到全局的選路過程使得數據中心尋優精度提高，選擇的路徑對負載均衡的改善效果更好，最后發揮軟件定義網絡集中控制的作用，下發流表轉發數據中心網絡流量。經過在Mininet仿真平臺進行實驗，結果表明本文的SMO-LBA明顯提高了鏈路利用率，呈現的尋優效果也更好，能夠較好實現基于SDN 的數據中心網絡的自適應多路徑負載均衡。本文選用胖樹網絡拓撲進行實驗，但實際的網絡傳輸場景要復雜很多，因此在之后的工作中，將研究更為復雜的數據中心網絡場景來進行模擬負載均衡實驗。