基于改進(jìn)蟻群算法的SDN數(shù)據(jù)中心流調(diào)度研究

朱素霞，龍翼飛，孫廣路，李純鋒

摘要：目前在軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)中，基于蟻群算法的流調(diào)度策略在對路徑進(jìn)行選擇時(shí)存在收斂過慢和搜索停滯等缺點(diǎn)，容易導(dǎo)致數(shù)據(jù)中心網(wǎng)絡(luò)時(shí)延過高和資源利用率低等問題。為此，提出一種基于蟻群改進(jìn)的流調(diào)度算法。該算法以最大化平均鏈路帶寬利用率為優(yōu)化目標(biāo)，將流調(diào)度問題抽象為整數(shù)線性規(guī)劃模型，通過重定義蟻群算法中的信息素更新方式對大流的重路由路徑進(jìn)行求解。仿真實(shí)驗(yàn)表明，該算法與傳統(tǒng)的經(jīng)典流調(diào)度算法和基于蟻群算法的流調(diào)度策略相比，能夠更有效地提升網(wǎng)絡(luò)平均對分帶寬，同時(shí)降低網(wǎng)絡(luò)傳輸時(shí)延和丟包率，充分利用網(wǎng)絡(luò)資源。

關(guān)鍵詞：軟件定義網(wǎng)絡(luò);流調(diào)度;數(shù)據(jù)中心網(wǎng)絡(luò);蟻群算法;信息素

DOI：10.15938/j.jhust.2022.01.001

中圖分類號： TP391.4? ? 文獻(xiàn)標(biāo)志碼： A? ? 文章編號： 1007-2683（2022）01-0001-07

Improved Ant Colony Algorithm for Network Flow

Scheduling in SDN Data Center

ZHU Suxia，LONG Yifei，SUN Guanglu，LI Chunfeng

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：At present， in the software defined data center network， the flow scheduling strategy based on ant colony algorithm has the disadvantages of too slow convergence and search stagnation in path selection， which easily leads to the problems of excessively high data center network delay and low resource utilization. Therefore， this paper proposes an improved flow scheduling algorithm based on ant colony. In this algorithm， the flow scheduling problem is abstracted as an integer linear programming model to maximize the average link bandwidth utilization， and the reroute path is solved by redefining pheromone updating mode in ant colony algorithm. The simulation results show that this algorithm can effectively improve the average bandwidth of the network， reduce the transmission delay and packet loss rate， and make full use of the network resources， compared with the traditional classical flow scheduling algorithm and the flow scheduling strategy based on ant colony algorithm.

Keywords：software defined network; flow scheduling; data center network; ant colony algorithm; pheromone

0引言

隨著互聯(lián)網(wǎng)業(yè)務(wù)的不斷擴(kuò)展，數(shù)據(jù)中心作為其內(nèi)容的承載體，承載著巨大的網(wǎng)絡(luò)流量，對帶寬的需求日益攀升。由于傳統(tǒng)的網(wǎng)絡(luò)拓?fù)錈o法滿足其對帶寬的需求[1]，為此，諸如FatTree[2]、DCell[3]、PortLand[4]等新型數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)湎嗬^被提出。其中，F(xiàn)atTree網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在當(dāng)今應(yīng)用尤為廣泛。另外，通過對數(shù)據(jù)中心網(wǎng)絡(luò)流量特征的研究，Benson等人發(fā)現(xiàn)在數(shù)據(jù)中心網(wǎng)絡(luò)里大流數(shù)量占比雖然不足網(wǎng)絡(luò)流總數(shù)量的10%，但其卻占了網(wǎng)絡(luò)流量總帶寬的80%[5]。由此可以得出大流是影響數(shù)據(jù)中心網(wǎng)絡(luò)性能的主要因素。因此，如何對網(wǎng)絡(luò)中的大流進(jìn)行合理又高效的路由不僅是保障數(shù)據(jù)中心內(nèi)各類應(yīng)用服務(wù)質(zhì)量的前提，也是當(dāng)今數(shù)據(jù)中心流量調(diào)度領(lǐng)域研究的熱點(diǎn)問題[6]。

傳統(tǒng)網(wǎng)絡(luò)在配置和管理等方面缺乏靈活性，無法適應(yīng)現(xiàn)代化數(shù)據(jù)中心發(fā)展的需求。針對這一問題，新興的網(wǎng)絡(luò)體系架構(gòu)—軟件定義網(wǎng)絡(luò)（software defined network，SDN）應(yīng)運(yùn)而生[7]，它將網(wǎng)絡(luò)數(shù)據(jù)的控制和轉(zhuǎn)發(fā)進(jìn)行解耦，使其具有集中式架構(gòu)的特性，能夠從全局的角度更加靈活地對網(wǎng)絡(luò)流量進(jìn)行調(diào)度。雖然SDN架構(gòu)相比傳統(tǒng)網(wǎng)絡(luò)架構(gòu)在流量調(diào)度方面具有很大優(yōu)勢，但其仍然存在流量負(fù)載分配不合理的問題，無法充分利用網(wǎng)絡(luò)資源[8]。

蟻群算法作為一種啟發(fā)式算法，已被廣泛應(yīng)用于離散域路徑規(guī)劃中的網(wǎng)絡(luò)路由問題及其他應(yīng)用場合[9-11]。目前已有的基于蟻群的流調(diào)度算法在對鏈路信息素更新時(shí)，沒有明顯差異化地更新鏈路信息素。這不僅會(huì)致使算法收斂速度過慢，導(dǎo)致網(wǎng)絡(luò)傳輸時(shí)延過高，而且也無法很好地解決路徑搜索產(chǎn)生的停滯問題。為此，本文針對鏈路信息素更新規(guī)則進(jìn)行改進(jìn)，提出了一種基于蟻群改進(jìn)的流調(diào)度算法（ant colony improvement flow scheduling，ACIFS）。

本文的主要貢獻(xiàn)如下：

1）根據(jù)網(wǎng)絡(luò)鏈路負(fù)載，差異化地初始全網(wǎng)鏈路信息素，使得空閑鏈路獲得更高的信息素初值，從而有效地降低蟻群算法在初期對鏈路選擇的隨機(jī)性，使其更加偏向于選擇負(fù)載更低的鏈路。

2）針對鏈路信息素?fù)]發(fā)系數(shù)，設(shè)計(jì)了一種階段性信息素?fù)]發(fā)系數(shù)。在迭代初期，其值相對較大，以提高螞蟻初期對新路徑的探索能力，隨著迭代次數(shù)的增加，逐漸降低其值，進(jìn)而改善算法的收斂速度。

3）針對鏈路信息素更新規(guī)則，結(jié)合獎(jiǎng)懲制度，提出了一種最優(yōu)最差全局信息素更新規(guī)則。僅對本輪迭代最優(yōu)和最差路徑上的鏈路信息素進(jìn)行額外的“獎(jiǎng)勵(lì)”和“懲罰”，淘汰較差路徑的同時(shí)突出較優(yōu)路徑。

1相關(guān)工作

針對數(shù)據(jù)中心網(wǎng)絡(luò)的流量調(diào)度問題，目前主流方法主要分為確定性方法和非確定性方法兩大類[12]。確定性方法針對特定的輸入產(chǎn)生相同的輸出，非確定性方法對于相同的輸入可能會(huì)有不同的輸出。

在確定性算法中，傳統(tǒng)的等價(jià)多路徑算法（equalcost multipath，ECMP）[13]是將多條數(shù)據(jù)流按照靜態(tài)散列的方式分配到多條等價(jià)路徑上，這可能導(dǎo)致多條大流被分到同一路徑，進(jìn)而引發(fā)碰撞，造成網(wǎng)絡(luò)擁塞。Li J等[14]是利用多屬性綜合模糊評估機(jī)制，提出了模糊綜合評估算法（fuzzy synthetic evaluation mechanism，F(xiàn)SEM），通過對候選路徑上各屬性值的加權(quán)評估，選擇最優(yōu)路徑對流量進(jìn)行路由。然而當(dāng)流量過大導(dǎo)致?lián)砣?，該算法并沒有解決辦法。Yang X 等[15]提出了一種基于 KDijkstra的負(fù)載均衡算法。該算法先是利用KDijkstra算法計(jì)算出主機(jī)間若干條備選路徑，之后則通過高響應(yīng)率優(yōu)先算法（high response ratio first，HRRF）在備選路徑中選出最佳路徑作為流調(diào)度路徑。雖然這樣可以提高網(wǎng)絡(luò)流量傳輸效率，但總體鏈路利用率偏低。

在非確定性算法中，AlFares M等[16]針對數(shù)據(jù)中心網(wǎng)絡(luò)流調(diào)度問題提出了Hedera動(dòng)態(tài)流量調(diào)度系統(tǒng)。其中，提出的全局最先匹配算法（global first fit，GFF）雖然將大流調(diào)度到滿足其需求的路徑上，緩解了網(wǎng)絡(luò)擁塞，但由于其是采用貪心的思想對路徑進(jìn)行選擇，因此所選路徑可能不是全局最優(yōu)路徑。Wang C等[17]提出了一種基于蟻群優(yōu)化的鏈路負(fù)載均衡算法（link load balancing ant colony optimization，LLBACO），該算法針對蟻群優(yōu)化算法的路徑搜索規(guī)則，將鏈路負(fù)載、時(shí)延和丟包率作為影響螞蟻選擇下一節(jié)點(diǎn)的因素，讓螞蟻選擇最寬和最短的路徑，雖然算法能夠有效地平衡網(wǎng)絡(luò)鏈路負(fù)載，但收斂速度過慢。曲樺等[18]提出了一種基于蟻群優(yōu)化的負(fù)載均衡算法（ant colony optimizationbased load balancing，LBACO）。該算法對所有到達(dá)目的節(jié)點(diǎn)的螞蟻進(jìn)行信息素更新，雖然加快了算法的收斂速度，但是會(huì)導(dǎo)致路徑搜索的停滯，使其陷入局部最優(yōu)。Xue H等[19]提出了一種基于遺傳蟻群優(yōu)化的動(dòng)態(tài)負(fù)載均衡算法（geneticant colony optimization，GACO）。該算法將遺傳算法和蟻群算法進(jìn)行了融合，在蟻群算法生成的路徑基礎(chǔ)上，利用遺傳算法中的交叉和變異操作產(chǎn)生新的路徑，有效地?cái)U(kuò)大了路徑的搜索范圍，避免了搜索的停滯，但是相應(yīng)地存在一個(gè)問題就是產(chǎn)生的新路徑可能并不存在。

2ACIFS算法設(shè)計(jì)

2.1流調(diào)度處理流程

本文對進(jìn)入數(shù)據(jù)中心的網(wǎng)絡(luò)流量默認(rèn)采用ECMP的方式進(jìn)行路由。根據(jù)全網(wǎng)狀態(tài)信息，計(jì)算當(dāng)前全網(wǎng)負(fù)載均衡度，并判斷其是否大于指定閾值，若小于，則說明當(dāng)前網(wǎng)絡(luò)處于相對均衡狀態(tài)，無需采取任何措施，否則，采用ACIFS算法對流經(jīng)邊緣交換機(jī)的大流進(jìn)行重調(diào)度。

2.2流調(diào)度問題數(shù)學(xué)建模

流調(diào)度問題實(shí)質(zhì)是根據(jù)路徑信息選擇合適的路徑將流從源節(jié)點(diǎn)調(diào)度到目的節(jié)點(diǎn)。本文將流調(diào)度問題抽象化為整數(shù)線性規(guī)劃模型進(jìn)行求解。問題的具體建模描述如下：

對于經(jīng)典的FatTree數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，可以將其抽象為一個(gè)有向圖G=（H∪S，E）。其中，H與S分別代表主機(jī)節(jié)點(diǎn)集合和交換機(jī)節(jié)點(diǎn)集合，E則代表鏈路集合。網(wǎng)絡(luò)中共有m條鏈路，其中，鏈路可表示為lij，i，j∈H∪S，另外，定義鏈路的最大負(fù)載為Cij。網(wǎng)絡(luò)中共有n條流，流的集合可以表示為F={f1，f2，…，fn}，定義其中一條流fk為一個(gè)三元組（sk，dk，bk），k∈{1，2，…，n}，sk∈H表示源主機(jī)節(jié)點(diǎn)，dk∈H表示目的主機(jī)節(jié)點(diǎn)，bk表示流fk的所占帶寬。

本文的優(yōu)化目標(biāo)是最大化平均鏈路帶寬利用率，即在避免網(wǎng)絡(luò)擁塞的同時(shí)將網(wǎng)絡(luò)資源利用率最大化。對目標(biāo)函數(shù)的具體定義如式（1）所示：

Max∑{（i，j）∈E}（∑1≤k≤nbkij/Cij）m（1）

其中：∑1≤k≤nbkij表示鏈路lij的實(shí)際負(fù)載;bkij表示流fk在鏈路lij上實(shí)際占用帶寬。

其約束條件如下：

∑1≤k≤nbkij≤Cij，（i，j）∈E（2）

0≤bkij≤Cij，i，j∈H∪S，k∈{1，2，…，n}（3）

∑{j：（sk，j）∈E}bkskj-∑{j：（j，sk）∈E}bkjsk=bk，k=1，2，…，n（4）

∑{j：（dk，j）∈E}bkdkj-∑{j：（j，dk）∈E}bkjdk=-bk，k=1，2，…，n（5）

∑{j：（i，j）∈E，i≠sk，dk}bkij=∑{j：（j，i）∈E，i≠sk，dk}bkji，k=1，2，…，n（6）

式（2）代表流容量約束，即任意一條鏈路上的總流量應(yīng)小于等于鏈路容量。式（3）代表流所占帶寬約束，即流fk的所占帶寬應(yīng)大于等于0，不能為負(fù)值，且小于鏈路容量。式（4）～（6）定義了流守恒約束，表示流fk從源主機(jī)流出到流入目的主機(jī)期間途經(jīng)的任意節(jié)點(diǎn)流入和流出的流量相等。

在對流調(diào)度問題建模后，本文將其映射到蟻群算法中，為獲得具體大流調(diào)度方案，這里采用ACIFS算法對上述模型進(jìn)行求解。

2.3全網(wǎng)負(fù)載均衡度的設(shè)定

在網(wǎng)絡(luò)流量處于高峰期時(shí)，為避免因網(wǎng)絡(luò)擁塞而導(dǎo)致的鏈路負(fù)載不均。本文為此設(shè)定一個(gè)全網(wǎng)負(fù)載均衡度δ，用于判斷當(dāng)前網(wǎng)絡(luò)是否處于負(fù)載均衡狀態(tài)。這里引用數(shù)學(xué)中的標(biāo)準(zhǔn)差概念，使用離散程度反應(yīng)均衡度，同時(shí)為避免其因短期的極值而導(dǎo)致不必要的重路由，本文采用一段時(shí)間內(nèi)的均值作為其結(jié)果，以消除短時(shí)間內(nèi)網(wǎng)絡(luò)波動(dòng)產(chǎn)生的影響。具體全網(wǎng)負(fù)載均衡度定義如式（7）所示：

δ（t）=1P∑Tt=T-P1m∑ml=1（load（t）-loadl（t））2（7）

其中：P代表統(tǒng)計(jì)周期;T代表當(dāng)前時(shí)間;load（t）表示在t時(shí)刻所有的鏈路平均負(fù)載;loadl（t）表示在t時(shí)刻鏈路l的實(shí)時(shí)負(fù)載。

針對全網(wǎng)負(fù)載均衡度，這里設(shè)置一個(gè)閾值δ*用來衡量當(dāng)前網(wǎng)絡(luò)負(fù)載情況。其中δ*的值通過實(shí)驗(yàn)來確定。

2.4ACIFS大流調(diào)度算法

蟻群算法作為一種啟發(fā)式算法[9]，被廣泛應(yīng)用于路徑尋優(yōu)問題，其核心思想是根據(jù)蟻群在覓食過程中釋放在路徑上的信息素去引導(dǎo)其找到最優(yōu)路徑。本文利用蟻群算法的思想對上述模型進(jìn)行求解。將螞蟻經(jīng)過的路徑轉(zhuǎn)化為大流調(diào)度的可行解，相應(yīng)整個(gè)蟻群所組成的路徑集合即為大流調(diào)度的解空間。其中，引導(dǎo)螞蟻選擇路徑的啟發(fā)信息可以抽象為網(wǎng)絡(luò)狀態(tài)信息，隨著迭代次數(shù)的增加，路徑越優(yōu)信息素含量就越高。最終，在正反饋的作用下整個(gè)蟻群將收斂到最優(yōu)路徑上，即此時(shí)得到的路徑為大流調(diào)度的最優(yōu)路徑。

本文提出的ACIFS算法對蟻群算法的信息素更新方式還有相關(guān)參數(shù)進(jìn)行了重定義，算法具體執(zhí)行步驟如下：

1）為了避免ACO算法中初期鏈路信息素的匱乏，這里根據(jù)鏈路負(fù)載情況，對全網(wǎng)鏈路信息素進(jìn)行差異化初始。具體方法如下：首先，將所有鏈路按照負(fù)載進(jìn)行升序排列;然后，將負(fù)載最低的前20%鏈路信息素初始化為τmax;最后，將剩余的鏈路信息素初始化為0.8τmax。這樣可以在搜索初期，有效減輕螞蟻搜索的盲目性，使其更加傾向于選擇空閑的鏈路。

2）設(shè)定算法最大迭代次數(shù)為Imax，螞蟻尋找目的節(jié)點(diǎn)最多途經(jīng)跳數(shù)為Nmax，螞蟻數(shù)量為x，同時(shí)將所有螞蟻放置在源節(jié)點(diǎn)。其中，對于每只螞蟻Ak（k=1，2，…，x）都有一個(gè)禁忌表，避免其重復(fù)訪問同一個(gè)節(jié)點(diǎn)。

3）在規(guī)定跳數(shù)Nmax內(nèi)，螞蟻Ak根據(jù)轉(zhuǎn)移概率Pkij選擇下一跳交換機(jī)節(jié)點(diǎn)。具體轉(zhuǎn)移概率如式（8）所示：

Pkij=[τij（t）]α·[ηij（t）]β∑z∈allowedk[τiz（t）]α·[ηiz（t）]βj∈allowedk

0others（8）

其中：Pkij表示螞蟻Ak從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率;α代表信息素的重要程度;β代表啟發(fā)信息的重要程度;τij（t）表示在t時(shí)刻鏈路lij上的信息素含量。ηij（t）為啟發(fā)函數(shù)，表示在t時(shí)刻鏈路lij上的啟發(fā)信息，具體計(jì)算方式如式（9）所示：

ηij（t）=1∑1≤k≤nbkij（t）（9）

其中∑1≤k≤nbkij（t）表示在t時(shí)刻鏈路lij的實(shí)際負(fù)載。鏈路負(fù)載越低時(shí)，被選擇的概率就越高。

4）當(dāng)所有螞蟻都完成一次迭代后，采用最優(yōu)最差全局信息素更新規(guī)則對鏈路信息素進(jìn)行更新。相比ACO算法中對所有到達(dá)目的節(jié)點(diǎn)的螞蟻所經(jīng)過路徑上的信息素進(jìn)行更新，這里則通過進(jìn)一步沉積信息素的方式獎(jiǎng)勵(lì)最優(yōu)路徑，進(jìn)一步揮發(fā)信息素的方式懲罰最差路徑。這樣有利于更快地排除相對較差的路徑，同時(shí)突出較好的路徑，進(jìn)而提高算法的收斂速度，具體最優(yōu)最差全局信息素更新規(guī)則如式（10）所示：

τgbij（t+1）=（1-ρphase）·τij（t）+Δτij（t）（10）

其中：τgbij（t+1）表示本輪迭代后鏈路lij上的信息素含量;ρphase為階段性信息素?fù)]發(fā)系數(shù)，具體計(jì)算方式如式（11）所示。

ρphase=0.5if Icur<0.3Imax and pcur=pall

0.4others

0.3if Icur>0.7Imax（11）

其中：Icur代表算法當(dāng)前迭代次數(shù);pcur代表本輪迭代最優(yōu)路徑;pall代表至今為止最優(yōu)路徑。Δτij（t）表示本輪迭代鏈路lij上的信息素增量，具體計(jì)算方式如式（12）和（13）所示。

Δτij（t）=∑xk=1Δτkij（t）（12）

Δτkij（t）=1/LbestAk is best ant

1/Lworst-1/LbestAk is worst ant

0others（13）

其中：Δτkij（t）表示螞蟻Ak在迭代過程中釋放在鏈路lij上的信息素;Lbest和Lworst則分別表示在本輪迭代成功到達(dá)目的節(jié)點(diǎn)的最優(yōu)和最差螞蟻所經(jīng)過的路徑長度，即交換機(jī)節(jié)點(diǎn)間跳數(shù)。其中，源節(jié)點(diǎn)和目的節(jié)點(diǎn)間跳數(shù)越少，其所經(jīng)過路徑上的信息素沉積量就越大，這有利于螞蟻選擇更短的路徑，從而降低網(wǎng)絡(luò)的傳輸時(shí)延。

其次，這里采用對本輪迭代最優(yōu)和最差路徑進(jìn)行更新。由于每輪迭代的結(jié)果可能不同，這使得更多路徑上的信息素將會(huì)得到沉積，從而可以有效地防止搜索過早地陷入局部最優(yōu)。

此外，就階段性信息素?fù)]發(fā)系數(shù)而言，初期其值偏高，有利于螞蟻對路徑進(jìn)行更加全面地搜索。隨著迭代次數(shù)的增加，其值逐漸降低，可以讓螞蟻漸進(jìn)地匯集到最優(yōu)路徑上，從而避免算法過早或過晚的收斂。另外，當(dāng)本輪迭代最優(yōu)路徑和至今為止迭代最優(yōu)路徑相同時(shí)，則說明算法已有收斂趨勢。如果該現(xiàn)象發(fā)生在算法初期，則說明其過早地陷入了局部最優(yōu)，理應(yīng)保持其相對較高的揮發(fā)值。

5）當(dāng)算法到達(dá)指定迭代次數(shù)Imax時(shí)，則根據(jù)優(yōu)化目標(biāo)選出最優(yōu)路徑，并將其作為大流調(diào)度的最終路由方案。

在算法執(zhí)行期間，ACO算法中節(jié)點(diǎn)間鏈路信息素會(huì)隨迭代次數(shù)的增加差值越來越大，容易導(dǎo)致路徑搜索過早停滯，從而錯(cuò)過更優(yōu)的路徑。本文為避免上述現(xiàn)象的發(fā)生，將鏈路信息素范圍限制在一定區(qū)間內(nèi)，即τij∈[τmin，τmax]，τmax>τmin>0。其中，當(dāng)信息素在更新過程中大于τmax時(shí)，則將其設(shè)置為τmax，反之，當(dāng)信息素在更新過程中小于τmin時(shí)，則將其設(shè)置為τmin。其中，τmin代表信息素的下限值，τmax代表信息素的上限值。

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

為了驗(yàn)證本文所提出的ACIFS算法性能，這里采用平均對分帶寬和端到端的往返時(shí)延，還有丟包率作為算法性能評價(jià)指標(biāo)，在FatTree網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下進(jìn)行實(shí)驗(yàn)測試。為進(jìn)一步展現(xiàn)ACIFS算法的優(yōu)勢，本文將對比在目前數(shù)據(jù)中心中應(yīng)用廣泛的ECMP算法[13]和基于GFF算法的Hedera動(dòng)態(tài)流量調(diào)度系統(tǒng)[16]，還有基于蟻群算法[9]的流調(diào)度策略。

3.1仿真環(huán)境參數(shù)設(shè)置

1.3.1網(wǎng)絡(luò)環(huán)境

本實(shí)驗(yàn)采用Mininet[20]網(wǎng)絡(luò)仿真工具來模擬真實(shí)數(shù)據(jù)中心網(wǎng)絡(luò)環(huán)境。實(shí)驗(yàn)拓?fù)洳捎胟=4的FatTree網(wǎng)絡(luò)拓?fù)?，具體如圖1所示。

其中，內(nèi)部的虛擬交換機(jī)采用支持OpenFlow協(xié)議的OpenvSwitch。相關(guān)網(wǎng)絡(luò)環(huán)境參數(shù)如表1所示。

1.3.2控制器

本實(shí)驗(yàn)采用開源的Ryu[21]控制器，并在上面實(shí)現(xiàn)了ACIFS等算法原型。其中，ACIFS算法的參數(shù)設(shè)定將直接影響其性能。為此，本文針對流調(diào)度問題的模型約束進(jìn)行大量的仿真實(shí)驗(yàn)，通過對實(shí)驗(yàn)結(jié)果的研究進(jìn)行算法的參數(shù)設(shè)置。具體ACIFS算法的參數(shù)如表2所示。

1.3.3通信模式

關(guān)于虛擬主機(jī)之間通信模式，本文采用隨機(jī)通信模式和交錯(cuò)通信模式。其中，在隨機(jī)通信模式Random里，網(wǎng)絡(luò)中虛擬主機(jī)之間以相等的概率進(jìn)行隨機(jī)通信，在交錯(cuò)通信模式Staggered（pEdge，pPod）里，pEdge表示同一邊緣交換機(jī)內(nèi)主機(jī)間通信概率，而pPod則表示同一Pod內(nèi)不同子網(wǎng)主機(jī)之間通信概率，相應(yīng)不同Pod間主機(jī)通信概率為1pEdgepPod。

為了公平起見，本實(shí)驗(yàn)針對交錯(cuò)通信模式采用具有不同特點(diǎn)的兩種流量模型，分別為Staggered（0.4，0.4）、Staggered（0.2，0.4）。這里使用Iperf工具生成相應(yīng)流量模型，同時(shí)對每組流量模型重復(fù)測試10次，每次測試運(yùn)行時(shí)間為60s。另外，測試期間使用bwmng工具對網(wǎng)絡(luò)帶寬進(jìn)行監(jiān)測，對每組流量模型測試結(jié)果取平均值作為最終實(shí)驗(yàn)結(jié)果。

3.2算法性能分析

針對平均對分帶寬，具體實(shí)驗(yàn)結(jié)果對比如圖2所示。從圖中可以明顯發(fā)現(xiàn)，無論在哪種流量模型下，ACIFS算法在平均對分帶寬上都高于ECMP和GFF，還有ACO算法。其中，在Random流量模型下，ACIFS算法較ECMP提高了約27%，較GFF提高了約20%，較ACO提高了約13%。在Staggered（0.2，0.4）流量模型下，ACIFS算法較ECMP提高了約35%，較GFF提高了約16%，較ACO提高了約10%。在Staggered（0.4，0.4）流量模型下，ACIFS算法較ECMP提高了約6%，較GFF提高了約4%，較ACO提高了約3%。

針對包的平均往返時(shí)延，具體實(shí)驗(yàn)結(jié)果對比如圖3所示。從圖中不難發(fā)現(xiàn)，不管在哪種流量模型下，ACIFS算法在網(wǎng)絡(luò)數(shù)據(jù)包的平均往返時(shí)延上都優(yōu)于ECMP和GFF，還有ACO算法。其中，在Random流量模型下，ACIFS算法較ECMP降低了約45%，較GFF降低了約39%，較ACO降低了約18%。在Staggered（0.2，0.4）流量模型下，ACIFS算法較ECMP降低了約49%，較GFF降低了約41%，較ACO降低了約19%。在Staggered（0.4，0.4）流量模型下，ACIFS算法較ECMP降低了約36%，較GFF降低了約32%，較ACO降低了約27%。

針對丟包率，具體實(shí)驗(yàn)結(jié)果對比如圖4所示。從圖中各算法在不同流量模型下的丟包率可以看出，在任何流量模型下，ACIFS算法在丟包率上都低于ECMP和GFF，還有ACO算法。其中，在Random流量模型下，ACIFS算法較ECMP降低了約47%，較GFF降低了約28%，較ACO降低了約14%。在Staggered（0.2，0.4）流量模型下，ACIFS算法較ECMP降低了約66%，較GFF降低了約43%，較ACO降低了約24%。在Staggered（0.4，0.4）流量模型下，ACIFS算法較ECMP降低了約46%，較GFF降低了約41%，較ACO降低了約29%。

綜上所述，總體來看，Random流量模型下的網(wǎng)絡(luò)整體性能介于Staggered（0.2，0.4）和Staggered（0.4，0.4）流量模型中間。當(dāng)Pod內(nèi)相同子網(wǎng)流量占比較高時(shí)，由于跨Pod通信的大流數(shù)量相對較少，這導(dǎo)致大流發(fā)生沖突的概率較低。因此，Staggered（0.4，0.4）流量模型相對其它流量模型總體平均對分帶寬偏高，同時(shí)，包平均往返時(shí)延和丟包率偏低。另外，由于大流沖突相對較少，所以ACIFS算法在平均對分帶寬方面相對其它算法沒有很明顯的提升。但隨著跨Pod間流量占比的提高，越來越多的大流在Pod間通信，因此，大流調(diào)度方案的不同將很大程度地影響網(wǎng)絡(luò)的整體性能。

其中，由于ECMP算法沒有考慮當(dāng)前網(wǎng)絡(luò)狀態(tài)，僅采用散列的方式對流量進(jìn)行調(diào)度，這將導(dǎo)致多條大流被分配到同一路徑上，從而引發(fā)嚴(yán)重的網(wǎng)絡(luò)擁塞。GFF算法雖然根據(jù)當(dāng)前網(wǎng)絡(luò)鏈路帶寬，將大流調(diào)度到第一條滿足其帶寬需求的路徑上，有效緩解了網(wǎng)絡(luò)擁塞，但其考慮因素過于單一，可能錯(cuò)過更優(yōu)的路徑。ACO算法則根據(jù)各種網(wǎng)絡(luò)狀態(tài)信息，利用螞蟻并行搜索對大流調(diào)度路徑進(jìn)行求解，進(jìn)一步減輕了網(wǎng)絡(luò)擁塞。ACIFS算法在ACO算法的基礎(chǔ)上通過改進(jìn)信息素的更新方式，不僅提高了算法的收斂速度，使螞蟻可以更快地找到較優(yōu)路徑，同時(shí)也防止了其錯(cuò)失其它更好路徑，進(jìn)而獲得了相對更佳的調(diào)度方案。實(shí)驗(yàn)結(jié)果表明，ACIFS算法相對其它算法在提升網(wǎng)絡(luò)吞吐量的同時(shí)很大程度地降低了網(wǎng)絡(luò)傳輸時(shí)延和丟包率。

針對平均鏈路帶寬利用率，具體實(shí)驗(yàn)對比結(jié)果如圖5所示。從圖中可以看出，隨著模擬時(shí)間的增加，網(wǎng)絡(luò)中鏈路帶寬利用率也在不斷地增長。其中，在25s之前，鏈路帶寬利用率增長較快。這是由于初期網(wǎng)絡(luò)流量剛進(jìn)入網(wǎng)絡(luò)，僅僅占用了網(wǎng)絡(luò)中一部分鏈路帶寬。但隨著時(shí)間的推移，流量將快速填充網(wǎng)絡(luò)中剩余的鏈路帶寬，期間流沖突相對較少，所以算法之間性能差距不明顯。而在25s以后，網(wǎng)絡(luò)中流量趨于穩(wěn)定。其中，ECMP算法由于沒有對流量進(jìn)行重調(diào)度，所以在流量穩(wěn)定后其鏈路帶寬利用率保持不變。GFF算法在30s到35s和55s到60s期間沒有對大流進(jìn)行重調(diào)度致使鏈路帶寬利用率沒有改變，這是因?yàn)樵谶@段時(shí)間內(nèi)沒有滿足大流帶寬需求的鏈路。另外，ACIFS算法和ACO算法的鏈路帶寬利用率增長趨勢相近，但由于ACIFS算法彌補(bǔ)了ACO算法在大流調(diào)度方面的缺陷，所以其增長幅度較ACO算法相對偏大。

4結(jié)語

本文針對基于蟻群的流調(diào)度算法容易導(dǎo)致網(wǎng)絡(luò)傳輸時(shí)延過高和網(wǎng)絡(luò)資源利用率低等問題，提出了ACIFS算法。利用差異化、獎(jiǎng)懲、限制三種策略對ACO算法中信息素的處理模式進(jìn)行改進(jìn)，并將其應(yīng)用到流調(diào)度問題中進(jìn)行求解，從而得出大流調(diào)度方案。通過對比ECMP和GFF，還有ACO算法的實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文所提出的ACIFS算法通過對大流的合理調(diào)度，不僅獲得了在平均對分帶寬上的提升，而且還有效地降低了網(wǎng)絡(luò)傳輸時(shí)延和丟包率，全面提高了網(wǎng)絡(luò)性能。

參 考 文 獻(xiàn)：

[1]HAMMADI A， MHAMDI L. A Survey on Architectures and Energy Efficiency in Data Center Networks[J]. Computer Communications， 2014， 40： 1.

[2]ALFARES M， LOUKISSAS A， VAHDAT A. A Scalable， Commodity Data Center Network Architecture[C]//ACM SIGCOMM Computer Communication Review. ACM， 2008， 38（4）： 63.

[3]GUO C， WU H， TAN K， et al. Dcell： A Scalable and Faulttolerant Network Structure for Data Centers[C]//ACM SIGCOMM Computer Communication Review. ACM， 2008， 38（4）： 75.

[4]NIRANJAN MYSORE R， PAMBORIS A， FARRINGTON N， et al. Portland： A Scalable Faulttolerant Layer 2 Data Center Network Fabric[C]//ACM SIGCOMM Computer Communication Review. ACM， 2009， 39（4）： 39.

[5]BENSON T， AKELLA A， MALTZ D A. Network Traffic Characteristics of Data Centers in the Wild[C]//Proceedings of the 10th ACM SIGCOMM conference on Internet Measurement. ACM， 2010： 267.

[6]GREENBERG A， HAMILTON J， MALTZ D A， et al. The Cost of a Cloud： Research Problems in Data Center Networks[J]. ACM SIGCOMM Computer Communication Review， 2008， 39（1）： 68.

[7]MCKEOWN N， ANDERSON T， BALAKRISHNAN H， et al. OpenFlow： Enabling Innovation in Campus Networks[J]. ACM SIGCOMM Computer Communication Review， 2008， 38（2）： 69.

[8]KREUTZ D， RAMOS F， VERISSIMO P. Towards Secure and Dependable Softwaredefined Networks[C]//Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. ACM， 2013： 55.

[9]DORIGO M， STTZLE T. Ant Colony Optimization： Overview and Recent Advances[M]//Handbook of Metaheuristics. Springer， Cham， 2019： 311.

[10]孟慶巖，王晶晶. 基于蟻群算法的分區(qū)揀貨法的改進(jìn)與實(shí)例研究[J]. 電子設(shè)計(jì)工程， 2021， 29（11）：44.

MENG Qingyan，WANG Jingjing. The Improvement and Case Study of the Partition Picking Method Based on Ant Colony Algorithm[J]. Electronic Design Engineering， 2021， 29（11）：44.

[11]胡治鋒， 陳冬方， 李慶奎， 等. 基于模擬退火蟻群算法的揀貨路徑規(guī)劃[J]. 電子設(shè)計(jì)工程， 2021， 29（24）：80.

HU Zhifeng， CHEN Dongfang， LI Qingkui， et al. Picking Path Planning Based on Simulated Annealing Ant Colony Algorithm[J]. Electronic Design Engineering， 2021， 29（24）：80.

[12]NEGHABI A A， NAVIMIPOUR N J， HOSSEINZADEH M， et al. Load Balancing Mechanisms in the Software Defined Networks： a Systematic and Comprehensive Review of the Literature[J]. IEEE Access， 2018， 6： 14159.

[13]HOPPS C. Analysis of An Equalcost Multipath Algorithm[S]. RFC2992， IETF， 2000.

[14]LI J， CHANG X， REN Y， et al. An Effective Path Load Balancing Mechanism Based on SDN[C]// Trust， Security and Privacy in Computing and Communications （TrustCom）， 2014 IEEE 13th International Conference on. IEEE， 2014： 527.

[15]YANG X， WANG L. SDN Load Balancing Method Based on KDijkstra[J].International Journal of Performability Engineering， 2018， 14（4）.

[16]ALFARES M， RADHAKRISHNAN S， RAGHAVAN B， et al. Hedera： Dynamic Flow Scheduling for Data Center Networks[C]//Nsdi. 2010， 10（8）： 89.

[17]WANG C， ZHANG G， XU H， et al. An ACObased Link Loadbalancing Algorithm in SDN[C]//2016 7th International Conference on Cloud Computing and Big Data （CCBD）. IEEE， 2016： 214.

[18]曲樺，趙季紅，樊斌，等.軟件定義網(wǎng)絡(luò)中應(yīng)用蟻群優(yōu)化的負(fù)載均衡算法[J].北京郵電大學(xué)學(xué)報(bào)，2017，40（3）：51.

QU Hua， ZHAO Jihong， FAN Bin， et al. Ant Colony Optimization for Load Balance in Software Defined Network[J]. Journal of Beijing University of Posts and Telecommunications， 2017，40（3）：51.

[19]XUE H， KIM K T， YOUN H Y. Dynamic Load Balancing of SoftwareDefined Networking Based on GeneticAnt Colony Optimization[J]. Sensors， 2019， 19（2）： 311.

[20]LANTZ B， HELLER B， MCKEOWN N. A Network in a Laptop： Rapid Prototyping for Softwaredefined Networks[C]//Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. ACM， 2010： 19.

[21]STANCU A L， HALUNGA S， VULPE A， et al. A Comparison Between Several Software Defined Networking Controllers[C]//Telecommunication in Modern Satellite， Cable and Broadcasting Services （TELSIKS）， 2015 12th International Conference on. IEEE， 2015： 223.

（編輯：王萍）