代榮榮，李宏慧，付學(xué)良

（內(nèi)蒙古農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，呼和浩特 010011）

0 引言

近年來(lái)，數(shù)據(jù)中心已逐漸成為互聯(lián)網(wǎng)信息化世界的重要組成部分［1］。隨著其規(guī)模擴(kuò)大，導(dǎo)致通信量快速增長(zhǎng)，并且網(wǎng)絡(luò)帶寬的需求也日益增長(zhǎng)［2］。數(shù)據(jù)中心網(wǎng)絡(luò)大多采用樹(shù)形拓?fù)浣Y(jié)構(gòu)，存在根節(jié)點(diǎn)限制網(wǎng)絡(luò)帶寬、擴(kuò)展困難等問(wèn)題［3］。因此，越來(lái)越多的學(xué)者開(kāi)始致力于研究適用于當(dāng)今數(shù)據(jù)中心網(wǎng)絡(luò)的更高效的網(wǎng)絡(luò)結(jié)構(gòu)。其中胖樹(shù)型（Fat-Tree）拓?fù)湟蚱浣Y(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，普遍被數(shù)據(jù)中心網(wǎng)絡(luò)使用；并且由于兩個(gè)節(jié)點(diǎn)間存在多條空閑路徑［4］，易于實(shí)現(xiàn)網(wǎng)絡(luò)沖突時(shí)的重路由，可以有效提高網(wǎng)絡(luò)帶寬。

在傳統(tǒng)的數(shù)據(jù)中心網(wǎng)絡(luò)架構(gòu)中，路由算法無(wú)法收集和了解整個(gè)網(wǎng)絡(luò)的動(dòng)態(tài)信息，故網(wǎng)絡(luò)流量難于實(shí)現(xiàn)全局優(yōu)化的調(diào)度。軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）利用控制器可以實(shí)時(shí)掌握整個(gè)網(wǎng)絡(luò)使用狀況，更精準(zhǔn)地實(shí)現(xiàn)網(wǎng)絡(luò)流量的調(diào)度，為互聯(lián)網(wǎng)技術(shù)的發(fā)展提供了新的技術(shù)支持。到目前為止，等價(jià)多路徑路由（Equal-Cost Multi-Path routing，ECMP）算法［5］已經(jīng)普遍用于網(wǎng)絡(luò)流量調(diào)度中。對(duì)于同一目的節(jié)點(diǎn)，ECMP 算法計(jì)算的等價(jià)可用路徑不止一條，它會(huì)對(duì)每一條數(shù)據(jù)流進(jìn)行哈希散列運(yùn)算，根據(jù)哈希值將數(shù)據(jù)流均勻分布到這些路徑中，從而實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡。研究表明，現(xiàn)今數(shù)據(jù)中心網(wǎng)絡(luò)流量分為大象流和老鼠流這兩種數(shù)據(jù)流［6］。大象流所占數(shù)量并不多，但持續(xù)時(shí)間長(zhǎng)，承載著高達(dá)90%的數(shù)據(jù)量［7］。因?yàn)镋CMP 算法無(wú)法動(dòng)態(tài)觀測(cè)網(wǎng)絡(luò)的通信狀態(tài)，所以當(dāng)網(wǎng)絡(luò)中出現(xiàn)大象流時(shí)，容易出現(xiàn)同一條路徑中有多條數(shù)據(jù)流的情況，導(dǎo)致負(fù)載不均衡和網(wǎng)絡(luò)資源利用率低等。

針對(duì)ECMP 算法在調(diào)度大象流中存在的問(wèn)題，本文提出了一種差分進(jìn)化（Differential Evolution，DE）融合蟻群（Ant Colony Optimization，ACO）算法（combination of DE and ACO algorithm，DE-ACO）的大象流調(diào)度機(jī)制，來(lái)實(shí)現(xiàn)流量的全局動(dòng)態(tài)調(diào)度。本文首先介紹解決SDN 數(shù)據(jù)中心網(wǎng)絡(luò)的流量調(diào)度問(wèn)題的相關(guān)工作，對(duì)該問(wèn)題進(jìn)行數(shù)學(xué)建模；然后設(shè)計(jì)差分進(jìn)化（DE）融合蟻群（ACO）算法的流量調(diào)度方法DE-ACO 求解該優(yōu)化模型；最后對(duì)其進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證流量調(diào)度的性能。

1 數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度問(wèn)題分析及建模

1.1 數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度問(wèn)題分析

Al-Fares 等［8］提出了Hedera 動(dòng)態(tài)流量調(diào)度機(jī)制，并將它實(shí)現(xiàn)在SDN 數(shù)據(jù)中心網(wǎng)絡(luò)多級(jí)交換機(jī)拓?fù)渖希脧慕粨Q機(jī)上獲得的實(shí)時(shí)數(shù)據(jù)流狀態(tài)信息來(lái)識(shí)別大流，并通過(guò)全局首選（Global First Fit，GFF）算法計(jì)算沒(méi)有沖突的路徑，繼而交換機(jī)重新路由數(shù)據(jù)流，實(shí)現(xiàn)網(wǎng)絡(luò)對(duì)方帶寬的最大化和流量調(diào)度開(kāi)銷的最小化。該方法首次結(jié)合了SDN 技術(shù)與數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度，為這方面的研究提供了新的理論基礎(chǔ)。

Curtis 等［3］提出了Mahout 方法，通過(guò)檢測(cè)終端主機(jī)的連接緩存而不是網(wǎng)絡(luò)中的交換機(jī)來(lái)識(shí)別大象流。所有沒(méi)有標(biāo)記為大象流的數(shù)據(jù)流仍然由ECMP 算法路由。只有當(dāng)檢測(cè)到大象流時(shí)，才通過(guò)帶內(nèi)信號(hào)機(jī)制通知控制器將大象流包匹配到高優(yōu)先級(jí)流表，從而保證大象流的傳輸。實(shí)驗(yàn)結(jié)果表明，Mahout 方法減少了交換機(jī)浪費(fèi)，并且在檢測(cè)大象流方面比所有對(duì)比的流統(tǒng)計(jì)數(shù)據(jù)快一個(gè)數(shù)量級(jí)。

Chakraborty 等［9］研究了數(shù)據(jù)中心網(wǎng)絡(luò)中流量的完成時(shí)間和時(shí)延，提出了一種簡(jiǎn)單有效的多路徑路由方案。該方案采用了將大象流拆分為老鼠流進(jìn)行轉(zhuǎn)發(fā)的思想，并結(jié)合基于虛擬局域網(wǎng)（Virtual Local Area Network，VLAN）的路由方案對(duì)大象流進(jìn)行調(diào)度，減少聚合交換機(jī)上的流完成時(shí)間和流表項(xiàng)的資源消耗。

劉振鵬等［10］提出了一種基于網(wǎng)絡(luò)負(fù)載的動(dòng)態(tài)流量調(diào)度方案，解決了ECMP 算法不考慮流量特性、容易產(chǎn)生鏈路沖突的問(wèn)題。該方案通過(guò)SDN 控制器獲取全局網(wǎng)絡(luò)信息，周期性采集接入層交換機(jī)的數(shù)據(jù)流信息，計(jì)算接入層交換機(jī)的流量閾值，為占用較大帶寬的數(shù)據(jù)流選擇最佳路徑。實(shí)驗(yàn)結(jié)果表明，該方案能夠提高數(shù)據(jù)中心網(wǎng)絡(luò)的負(fù)載均衡效果。

朱素霞等［11］提出了一種基于大流調(diào)度的軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載均衡（Large-flows Routing Load Balancing，LRLB）算法。該算法結(jié)合了SDN 和網(wǎng)絡(luò)流量的特性，將負(fù)載均衡問(wèn)題轉(zhuǎn)化為多商品流問(wèn)題，根據(jù)大象流的負(fù)載狀態(tài)對(duì)其重路由，從而減少其在流量分布不均勻的問(wèn)題上的影響。

近幾年來(lái)，隨著群體智能算法的提出，研究人員將其用于解決SDN 流量調(diào)度優(yōu)化問(wèn)題。比如，林智華等［12］提出了一種在胖樹(shù)數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)湎碌碾x散粒子群優(yōu)化流量調(diào)度（Discrete Particle Swarm Optimization Flow Scheduling，DPSOFS）算法，通過(guò)對(duì)粒子群算法的二進(jìn)制改進(jìn)形成離散粒子群算法，并結(jié)合收集到的全局網(wǎng)絡(luò)視圖，求解出最優(yōu)的網(wǎng)絡(luò)重路由方案。DPSOFS 算法可以提高收斂速度，獲得更好的流量調(diào)度路徑。

李宏慧等［13］提出了基于蟻群算法的SDN 數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度算法（network flow scheduling algorithm of SDN data center based on Ant Colony Optimization algorithm，ACOSDN），通過(guò)對(duì)大象流調(diào)度問(wèn)題建模，基于蟻群算法對(duì)優(yōu)化模型進(jìn)行求解，得到全局最優(yōu)路徑對(duì)大象流進(jìn)行重路由，實(shí)現(xiàn)數(shù)據(jù)中心網(wǎng)絡(luò)鏈路的最大利用率的有效降低和網(wǎng)絡(luò)對(duì)分帶寬的提高；但因ACO-SDN 前期的收斂速度不夠快且易陷入局部最優(yōu)，容易導(dǎo)致大象流二次沖突。

因此，本文提出了一種基于差分進(jìn)化融合蟻群算法的流量調(diào)度機(jī)制DE-ACO。DE-ACO 從網(wǎng)絡(luò)全局的角度，根據(jù)網(wǎng)絡(luò)實(shí)時(shí)狀態(tài)，首先調(diào)用差分進(jìn)化算法選取多條可用路徑，再通過(guò)蟻群算法動(dòng)態(tài)地去近似尋找全局最優(yōu)路徑；然后在ECMP 基礎(chǔ)上重路由擁塞鏈路上的大象流，從而有效地解決傳統(tǒng)數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度缺乏對(duì)全局網(wǎng)絡(luò)信息的感知問(wèn)題，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，提高網(wǎng)絡(luò)資源利用率。

1.2 數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度問(wèn)題建模

本文對(duì)流量調(diào)度問(wèn)題進(jìn)行了建模，在鏈路容量范圍內(nèi)，通過(guò)流量調(diào)度優(yōu)化其目標(biāo)函數(shù)，使流量可以在每條鏈路上都實(shí)現(xiàn)均勻分布，從而實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡。具體建模描述如下。

將數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浔硎緸閳DG(S，L)，其中：S為所有網(wǎng)絡(luò)節(jié)點(diǎn)（交換機(jī)）的集合，節(jié)點(diǎn)si∈S（i=1，2，…，|S|）；L表示網(wǎng)絡(luò)中所有鏈路的集合，鏈路l∈L的容量為Cl，其鏈路利用率為ul。Li和分別為鏈路集合L的子集，其中任意li∈Li以si為端點(diǎn)，并且數(shù)據(jù)流經(jīng)由li流入節(jié)點(diǎn)si；任意∈以si為端點(diǎn)，且數(shù)據(jù)流經(jīng)由流出節(jié)點(diǎn)si。將數(shù)據(jù)中心網(wǎng)絡(luò)中導(dǎo)致?lián)砣臄?shù)據(jù)流集合表示為E，數(shù)據(jù)流e∈E的帶寬為be，數(shù)據(jù)流e的源節(jié)點(diǎn)和目的節(jié)點(diǎn)分別用和表示。變量表示數(shù)據(jù)流e是否途經(jīng)鏈路l。

鏈路利用率ul定義為所有通過(guò)鏈路l的數(shù)據(jù)流e的總帶寬與鏈路l容量Cl的比值。最大鏈路利用率（Maximum Link Utilization，MLU）umax是指數(shù)據(jù)流途經(jīng)的所有鏈路中利用率的最大值。則流量調(diào)度問(wèn)題的優(yōu)化目標(biāo)［13］，即最小化網(wǎng)絡(luò)中的最大鏈路利用率，可用式（1）表示：

在達(dá)到上述優(yōu)化目標(biāo)時(shí)，流量調(diào)度應(yīng)滿足約束條件（2）～（6）：

式（2）說(shuō)明通過(guò)鏈路l的數(shù)據(jù)流e總帶寬不應(yīng)超過(guò)鏈路容量Cl；式（3）表示如果節(jié)點(diǎn)si為數(shù)據(jù)流e的源節(jié)點(diǎn)，則數(shù)據(jù)流e只從該節(jié)點(diǎn)流出；式（4）說(shuō)明若節(jié)點(diǎn)si為e的目的節(jié)點(diǎn)，則e只流入該節(jié)點(diǎn)；式（5）表示若si為e的中間節(jié)點(diǎn)，則該節(jié)點(diǎn)流入及流出的數(shù)據(jù)流量相同；式（6）定義變量的取值范圍。

動(dòng)態(tài)流量調(diào)度要快速確定需要重路由的數(shù)據(jù)流以及如何對(duì)其進(jìn)行重路由?？紤]到老鼠流持續(xù)時(shí)間相對(duì)較短，如果對(duì)其進(jìn)行重路由極可能會(huì)增加不必要的開(kāi)銷，所以本文在發(fā)生網(wǎng)絡(luò)擁塞時(shí)主要對(duì)大象流進(jìn)行重路由。該模型的本質(zhì)是一種線性規(guī)劃數(shù)學(xué)模型，當(dāng)網(wǎng)絡(luò)中包含的大象流數(shù)目較多時(shí)，其效果較為明顯；同時(shí)，考慮到當(dāng)相同路徑的多條數(shù)據(jù)流發(fā)生網(wǎng)絡(luò)擁塞時(shí)，被重路由到同一條鏈路的概率非常大，仍會(huì)發(fā)生新的網(wǎng)絡(luò)擁塞問(wèn)題，本文利用差分進(jìn)化融合蟻群算法求解該模型的最優(yōu)解，來(lái)降低重路由到同一條鏈路的幾率，并防止二次擁塞。

2 差分進(jìn)化融合蟻群算法的流量調(diào)度機(jī)制

2.1 大象流重路由調(diào)度機(jī)制

本文首先利用差分進(jìn)化算法得到多條滿足條件的可用路徑，為避免差分進(jìn)化算法陷入局部最優(yōu)以及重路由后的二次擁塞問(wèn)題，再融合一種近似尋路最優(yōu)算法的蟻群算法，進(jìn)一步對(duì)多條可用路徑進(jìn)行精細(xì)化搜索得到一條最短路徑，從而確保最終所選路徑既是最短路徑又可避免被重復(fù)選擇，防止產(chǎn)生負(fù)載不均。本文提出的DE-ACO 流量調(diào)度算法進(jìn)行大象流調(diào)度的流程如圖1 所示，具體步驟如下所述。如何利用差分進(jìn)化算法和蟻群算法進(jìn)行求解的詳細(xì)說(shuō)明見(jiàn)2.2 節(jié)和2.3 節(jié)。

圖1 DE-ACO大象流調(diào)度機(jī)制流程Fig.1 DE-ACO elephant flow scheduling process

1）通過(guò)sflow-rt 網(wǎng)絡(luò)信息收集器，持續(xù)收集數(shù)據(jù)中心網(wǎng)絡(luò)鏈路狀態(tài)信息。

2）對(duì)于途經(jīng)數(shù)據(jù)中心網(wǎng)絡(luò)的數(shù)據(jù)流，用ECMP 算法來(lái)進(jìn)行調(diào)度，并對(duì)鏈路上的數(shù)據(jù)流進(jìn)行大小流的區(qū)分。

3）若大象流途徑的某條鏈路的最大鏈路利用率大于閾值60%，則執(zhí)行步驟4）～6），否則轉(zhuǎn)步驟1）。

4）選取與該大象流同源目的節(jié)點(diǎn)的50 條可用路徑，作為重路由的備選路徑。

5）調(diào)用差分進(jìn)化算法，根據(jù)sflow-rt 收集器收集到的當(dāng)前網(wǎng)絡(luò)狀態(tài)，從50 條備選路徑中計(jì)算出多條可用備選路徑。

6）將多條可用備選路徑作為融合蟻群算法的初始化，來(lái)更進(jìn)一步地選取最優(yōu)路徑。

7）將得到的全局最優(yōu)路徑轉(zhuǎn)換成流表項(xiàng)，通過(guò)控制器下發(fā)給各交換機(jī)，重路由大象流，同時(shí)轉(zhuǎn)步驟1）。

2.2 調(diào)用差分進(jìn)化算法計(jì)算可用路徑

差分進(jìn)化（DE）算法是1997 年由Storn 等［14］在遺傳算法基礎(chǔ)上提出的。DE 算法是一種自適應(yīng)全局優(yōu)化算法，通過(guò)迭代變異進(jìn)化，保留適應(yīng)度好的個(gè)體。DE 算法原理簡(jiǎn)單，控制參數(shù)少且收斂速度快［15］。

依據(jù)當(dāng)前數(shù)據(jù)中心網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浜兔織l鏈路的鏈路利用率，計(jì)算出滿足約束條件式（4）～（6）的多條可用備選路徑。算法的輸入為數(shù)據(jù)中心網(wǎng)絡(luò)中鏈路的當(dāng)前利用率和存儲(chǔ)在解空間R的多條大象流備選路徑，輸出為多條可用備選路徑。算法具體步驟如下所述。

步驟1 算法初始化。

1）將循環(huán)控制變量t設(shè)置為1 并設(shè)定最大迭代次數(shù)MaxT。

2）將根據(jù)Yen 算法［16］生成的與導(dǎo)致?lián)砣笙罅魍赐康墓?jié)點(diǎn)的k-最短路徑保存到解空間R。

3）從解空間R中依次選取M個(gè)個(gè)體Xi作為初始種群Pop。其中，個(gè)體Xi為一整條完整路徑。如式（7）所示，每一條路徑由n條鏈路l組成。

4）為實(shí)現(xiàn)式（1）所示的最小化最大鏈路利用率的優(yōu)化目標(biāo)，將適應(yīng)度函數(shù)定義為如式（8）所示：

其中：H(Xi)為個(gè)體Xi的長(zhǎng)度即路徑長(zhǎng)度，MaxU(Xi)為路徑個(gè)體Xi里所有鏈路中的最大鏈路利用率值，a和b為影響因子。個(gè)體Xi適應(yīng)度函數(shù)F(Xi)將本文1.2 節(jié)中的流量調(diào)度模型中的最小化問(wèn)題轉(zhuǎn)化為最大化問(wèn)題，方便后續(xù)調(diào)用差分進(jìn)化融合蟻群算法（DE-ACO）進(jìn)行求解最優(yōu)解。

步驟2 進(jìn)行變異操作。

DE 算法中的變異操作采取從種群Pop中隨機(jī)選擇3 個(gè)個(gè)體來(lái)生成變異個(gè)體［15］。考慮到在網(wǎng)絡(luò)中需要保持路徑的連續(xù)性，本文將在第t次迭代中將個(gè)體Xi(t)中最大鏈路利用率大于閾值H的鏈路替換為相鄰且不擁堵的一條或幾條鏈路形成新路徑個(gè)體Vi(t)。圖2 給出了變異操作示例。其中，圓圈si表示每一個(gè)交換機(jī)節(jié)點(diǎn)，直線lj為一條鏈路，連接si和si+1兩個(gè)相鄰交換機(jī)。

圖2 變異操作示例Fig.2 Variation operation example

假設(shè)圖2（a）所示的路徑中連接鏈路l3的利用率大于閾值，則對(duì)其進(jìn)行替換。利用Yen 算法，以鏈路l3的兩個(gè)端點(diǎn)s2和s3分別為源和目的節(jié)點(diǎn)，生成k-最短路徑并保留到變異候選解空間R'。再?gòu)腞'中選取所有鏈路的最大鏈路利用率均小于閾值H且在解空間R'中長(zhǎng)度最短的候選路徑l*，如圖2（b）所示。將擁堵鏈路l3替換成滿足條件的候選路徑l*，生成如圖2（c）所示的變異個(gè)體Vi(t)。

步驟3 進(jìn)行交叉操作。

在第t次迭代中，從區(qū)間［0，1］中選取一個(gè)隨機(jī)數(shù)r。若r大于交叉因子cr，保留變異個(gè)體Vi(t)，并轉(zhuǎn)至步驟4。

若r小于等于交叉因子cr，將個(gè)體Xi(t)和變異個(gè)體Vi(t)進(jìn)行交叉操作，但考慮到變異個(gè)體Vi(t)是由Xi(t)變異所得，在完成交叉操作后可能交叉?zhèn)€體Ui(t)與原個(gè)體Xi(t)完全相同，從而造成無(wú)效交叉。本文為避免出現(xiàn)無(wú)效交叉現(xiàn)象，針對(duì)傳統(tǒng)交叉操作進(jìn)行了重新定義。首先從種群Pop中隨機(jī)選取一條與變異個(gè)體Vi(t)同源同目的節(jié)點(diǎn)的路徑作為交叉?zhèn)溥x個(gè)體W(t)；再與變異個(gè)體Vi(t)進(jìn)行交叉操作，即將變異個(gè)體Vi(t)與交叉?zhèn)溥x個(gè)體W(t)按順序遍歷每一個(gè)節(jié)點(diǎn)，當(dāng)出現(xiàn)第一個(gè)公共節(jié)點(diǎn)時(shí)，則將公共節(jié)點(diǎn)后的鏈路全部進(jìn)行互換后得到新的交叉?zhèn)€體Ui(t)，由此確保經(jīng)過(guò)變異操作的結(jié)果可以順利保留到下一代種群中。

具體交叉操作示例如圖3 所示，圖3 中的標(biāo)識(shí)說(shuō)明與步驟2 相同。假設(shè)已從種群中隨機(jī)選取一條交叉?zhèn)溥x路徑W(t)（圖3（a）），它與變異個(gè)體Vi(t)（圖2（c））進(jìn)行交叉操作?？梢钥闯鯳(t)和Vi(t)按順序遍歷第一個(gè)公共節(jié)點(diǎn)為，確定公共節(jié)點(diǎn)為后將W(t)和Vi(t)從公共節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的所有鏈路進(jìn)行互換，得到如圖3（b）所示的交叉?zhèn)€體Ui(t)。

圖3 交叉操作示例Fig.3 Crossover operation example

步驟4 進(jìn)行選擇操作。

依據(jù)式（8）計(jì)算交叉?zhèn)€體Ui(t)的適應(yīng)度值，若Ui(t)的適應(yīng)度值優(yōu)于當(dāng)前個(gè)體Xi(t)的適應(yīng)度值，則在第t次迭代中的交叉?zhèn)€體Ui(t)取代當(dāng)前個(gè)體Xi(t)保留到下一代種群Pop中；否則，仍然保留當(dāng)前個(gè)體Xi(t)。

步驟5 如果達(dá)到迭代條件要求，退出循環(huán)；否則，跳轉(zhuǎn)至步驟2。

2.3 調(diào)用蟻群算法選取全局最優(yōu)路徑

在流量調(diào)度中調(diào)用差分進(jìn)化算法的弊端在于個(gè)體的差異會(huì)隨著進(jìn)化迭代不斷變小，導(dǎo)致出現(xiàn)陷入局部最優(yōu)和收斂速度在后期逐步變慢等現(xiàn)象，因此本文選擇調(diào)用蟻群（ACO）算法對(duì)其進(jìn)行優(yōu)化，尋求全局最優(yōu)路徑。

蟻群算法是由Marco Dorigo 首先提出來(lái)的一種模擬蟻群在覓食過(guò)程中尋找最優(yōu)路徑的行為的啟發(fā)式近似優(yōu)化算法［17］。螞蟻與螞蟻之間依靠各自所釋放的信息素來(lái)相互完成信息的交換和傳遞，并且蟻群中的螞蟻們會(huì)向著信息素濃度高的路徑進(jìn)行搜索；途經(jīng)信息素濃度高的路徑的螞蟻也會(huì)釋放信息素，導(dǎo)致該路徑的信息素濃度會(huì)越來(lái)越高；最后，整個(gè)蟻群的螞蟻就會(huì)沿著信息素濃度最高的路徑到達(dá)食物源［13］，該路徑即為最優(yōu)路徑。蟻群算法采用這種多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，極大提高了算法的計(jì)算能力和運(yùn)行效率，適用于多目標(biāo)；但前期信息素匱乏會(huì)導(dǎo)致收斂速度慢。關(guān)于收斂速度的問(wèn)題，本文首先根據(jù)差分進(jìn)化算法得到的多條可用路徑作為初始化信息素濃度，為大象流計(jì)算出全局最優(yōu)路徑，其中以當(dāng)前鏈路利用率和多條可用路徑作為輸入，輸出一條全局最優(yōu)路徑。算法具體步驟如下。

步驟1 初始化算法參數(shù)。

設(shè)置螞蟻數(shù)量為N，每只螞蟻A自帶記錄走過(guò)節(jié)點(diǎn)的禁忌表TA，差分進(jìn)化算法輸出的多條可用路徑設(shè)為初始化信息素。

步驟2 進(jìn)行螞蟻移動(dòng)操作。

設(shè)置數(shù)據(jù)流的源節(jié)點(diǎn)為螞蟻穴，目的節(jié)點(diǎn)為食物位置。所有螞蟻從蟻穴出發(fā)，此時(shí)禁忌表為空。每一只螞蟻A在遍歷多條可用路徑中，可以移動(dòng)到下一個(gè)可到達(dá)的節(jié)點(diǎn)時(shí)，需依據(jù)各條鏈路信息素τ和啟發(fā)信息η計(jì)算出移動(dòng)概率如式（9）所示；再按照輪盤賭法選擇下一節(jié)點(diǎn)進(jìn)行移動(dòng)，并將此節(jié)點(diǎn)添加到禁忌表TA中。

步驟3 更新信息素。

1）為更真實(shí)地模擬螞蟻覓食的自然現(xiàn)象，需依據(jù)信息素?fù)]發(fā)因子ρ對(duì)當(dāng)前所有信息素進(jìn)行揮發(fā)后，再進(jìn)行信息素的更新。

2）當(dāng)所有螞蟻到達(dá)目的節(jié)點(diǎn)sd或禁忌表TA達(dá)到上限時(shí)，表示第t次迭代結(jié)束。根據(jù)式（10）更新第t+1 次的鏈路信息素

3）若t未達(dá)到最大迭代次數(shù)，轉(zhuǎn)至步驟2 繼續(xù)下一輪循環(huán)；否則，轉(zhuǎn)至步驟4。

步驟4 選取全局最優(yōu)路徑。

當(dāng)t大于最大迭代次數(shù)時(shí)，停止循環(huán)。在所有到達(dá)目標(biāo)節(jié)點(diǎn)的螞蟻禁忌表中按照最小化最大鏈路利用率的優(yōu)化目標(biāo)選取最優(yōu)路徑，返回給控制器進(jìn)行重路由。

3 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證所提出的DE-ACO 算法的性能，本文將與目前數(shù)據(jù)中心網(wǎng)絡(luò)中普遍應(yīng)用的ECMP 算法和采用群體智能算法進(jìn)行流量調(diào)度中效果較好的ACO-SDN 進(jìn)行對(duì)比。用平均對(duì)分帶寬和最大鏈路利用率作為衡量算法性能的指標(biāo)［13］：對(duì)分帶寬［18］指的是把一個(gè)網(wǎng)絡(luò)平均分成兩個(gè)相同的子網(wǎng)，這兩個(gè)子網(wǎng)中所有的鏈路在規(guī)定的單位時(shí)間內(nèi)通過(guò)的數(shù)據(jù)流流量的總帶寬；最大鏈路利用率是指在網(wǎng)絡(luò)傳輸時(shí)，網(wǎng)絡(luò)所有路徑的鏈路利用率值中鏈路利用率達(dá)到最高的值。當(dāng)在同一個(gè)負(fù)載情況下，對(duì)分帶寬越大表示網(wǎng)絡(luò)吞吐量越大，最大鏈路利用率越低則表示網(wǎng)絡(luò)的鏈路利用分配均勻，沒(méi)有造成某一條鏈路利用過(guò)度的情況，即網(wǎng)絡(luò)負(fù)載均衡性能越好。

3.1 實(shí)驗(yàn)環(huán)境

3.1.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

實(shí)驗(yàn)采用Mininet 仿真平臺(tái)模擬拓?fù)?，用Python 構(gòu)建一個(gè)k=4 的Fat-Tree 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。其中，所有交換機(jī)均為OpenFlow 交換機(jī)共20 臺(tái)，接入層交換機(jī)連接16 臺(tái)主機(jī)，各條鏈路帶寬設(shè)定為100 Mb/s。

3.1.2 通信模式

為了正確評(píng)估本文所提出的DE-ACO 流量調(diào)度算法，實(shí)驗(yàn)中數(shù)據(jù)流的大小服從指數(shù)分布，其中指數(shù)函數(shù)的參數(shù)r=0.23。產(chǎn)生每條流的時(shí)間間隔服從泊松分布，每條流的持續(xù)時(shí)間為60 s，取第20～40 s 時(shí)間段的數(shù)據(jù)流作為有效實(shí)驗(yàn)數(shù)據(jù)。

本文使用流量生成工具Iperf，并對(duì)其進(jìn)行二次開(kāi)發(fā)，通過(guò)擴(kuò)展Mininet 的內(nèi)部命令，生成3 種不同通信模式的數(shù)據(jù)流。這3 種不同的通信模式如下所述。

1）隨機(jī)模式Random。網(wǎng)絡(luò)中隨機(jī)選取源主機(jī)和目的主機(jī)，同時(shí)生成流量的方式和流量的大小都是隨機(jī)產(chǎn)生的。

2）間隔模 式Stride（i）。編 號(hào)x的主機(jī) 向編號(hào) 為（x+i）modn的主機(jī)傳輸數(shù)據(jù)，其中n為網(wǎng)絡(luò)中主機(jī)數(shù)量。

3）交錯(cuò)模式Staggered（p1，p2）。每臺(tái)主機(jī)以概率p1 向同屬于一個(gè)接入層交換機(jī)的主機(jī)發(fā)送數(shù)據(jù)，以概率p2 向同屬于一個(gè)pod 的主機(jī)發(fā)送數(shù)據(jù)，以概率1-p1-p2 向其他pod 內(nèi)主機(jī)發(fā)送數(shù)據(jù)［13］。

3.1.3 算法相關(guān)參數(shù)設(shè)置

算法相關(guān)參數(shù)設(shè)置會(huì)直接對(duì)流量調(diào)度優(yōu)化算法的效果產(chǎn)生影響，本文以優(yōu)化流量調(diào)度問(wèn)題的目標(biāo)函數(shù)為目的，并依據(jù)文獻(xiàn)［15，19-22］的研究結(jié)果和對(duì)比多次仿真實(shí)驗(yàn)結(jié)果后進(jìn)行相關(guān)參數(shù)的設(shè)置。其中，DE-ACO 的主要參數(shù)設(shè)置如表1 所示。

表1 DE-ACO主要參數(shù)值Tab.1 Major parameter values of DE-ACO

通過(guò)多次仿真實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)?shù)螖?shù)在50～100 時(shí)，算法性能均穩(wěn)定，本文選取MaxT=50 以減輕Floodlight 控制器的運(yùn)算負(fù)荷。為實(shí)現(xiàn)最小化最大鏈路利用率，本文選取a=1，b=10 作為當(dāng)前適應(yīng)度函數(shù)值產(chǎn)生的權(quán)重。實(shí)驗(yàn)將兩節(jié)點(diǎn)間的路徑固定為11 跳。當(dāng)k=4 時(shí)，F(xiàn)at-Tree 網(wǎng)絡(luò)拓?fù)渲谐^(guò)11跳的路徑所需路由時(shí)間過(guò)長(zhǎng)，易造成網(wǎng)絡(luò)不可達(dá)，所以設(shè)置途經(jīng)最多的節(jié)點(diǎn)數(shù)是10。

3.2 平均對(duì)分帶寬比較

由于數(shù)據(jù)中心網(wǎng)絡(luò)中的數(shù)據(jù)流類型復(fù)雜且流量龐大，仿真實(shí)驗(yàn)決定選取3.1.2 節(jié)中3 種通信模式在虛擬主機(jī)之間進(jìn)行通信。為了實(shí)驗(yàn)的公平性，在3 種通信模式下均調(diào)用3 種流量調(diào)度算法，各算法分別進(jìn)行20 組仿真實(shí)驗(yàn)并記錄實(shí)驗(yàn)數(shù)據(jù)，再經(jīng)過(guò)平均值計(jì)算得到最終的實(shí)驗(yàn)結(jié)果，如圖4～6所示。

3.2.1 Random通信模式

在Random 通信模式下，對(duì)3 種算法分別都進(jìn)行了兩組隨機(jī)通信模式的實(shí)驗(yàn)Random1、Random2，結(jié)果如圖4 所示。從圖4 中可以看出，在平均對(duì)分帶寬上DE-ACO 算法相較于ECMP 和ACO-SDN 算法分別提高了29.42%～36.26%和5%～11.51%。

圖4 Random模式下平均對(duì)分帶寬比較Fig.4 Comparison of average bisection bandwidth in Random mode

3.2.2 Stride通信模式

為模擬網(wǎng)絡(luò)負(fù)載不均衡，便于仿真真實(shí)網(wǎng)絡(luò)的流量復(fù)雜性，在Stride（i）間隔模式下，分別取i=2、4、6 這3 種通信方式做3 組對(duì)比實(shí)驗(yàn)Stride（2）、Stride（4）和Stride（6）。從圖5 中可知，在3 種間隔模式下，DE-ACO 算法的平均對(duì)分帶寬都優(yōu)于其他兩種對(duì)比算法。其中，DE-ACO 算法的平均對(duì)分帶寬相較于ECMP 算法提高了32.04%～34.78%，相較于ACOSDN 算法提高了2.50%～12.07%。

圖5 Stride 模式下平均對(duì)分帶寬比較Fig.5 Comparison of average bisection bandwidth in Stride mode

3.2.3 Staggered通信模式

在Staggered 交錯(cuò)模式下，用Staggered（0，0.2）和Staggered（0，0.4）兩種交錯(cuò)模式進(jìn)行實(shí)驗(yàn)，以Staggered（0，0.2）模式為例，在通信實(shí)驗(yàn)中每一臺(tái)主機(jī)向同一個(gè)pod 發(fā)送流的概率是0.2，則向除了同pod 以外的剩余主機(jī)發(fā)送數(shù)據(jù)流的概率為0.8。從圖6 中可知，DE-ACO 算法的平均對(duì)分帶寬優(yōu)于ACO-SDN 算法，而ACO-SDN 的平均對(duì)分帶寬數(shù)值比ECMP 算法有所提高，但低于DE-ACO 算法。其中，在Staggered（0，0.2）交錯(cuò)模式下DE-ACO 算法相較于ECMP 平均對(duì)分帶寬提高了50.07%，相較于ACO-SDN 算法提高了36.74%；在Staggered（0，0.4）下，DE-ACO 算法相較于ECMP算法提高了8.45%，相較于ACO-SDN 算法的平均對(duì)分帶寬提高了2.98%。

圖6 Staggered模式下平均對(duì)分帶寬比較Fig.6 Comparison of average bisection bandwidth in Staggered mode

3.3 最大鏈路利用率比較

為更全面地驗(yàn)證DE-ACO 算法的流量調(diào)度能力，本文對(duì)DE-ACO 算法、ECMP 算法和ACO-SDN 算法做了最大鏈路利用率（MLU）的對(duì)比實(shí)驗(yàn)。最大鏈路利用率也是一個(gè)評(píng)價(jià)流量調(diào)度算法能否更好實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡的重要指標(biāo)，它能夠反映網(wǎng)絡(luò)鏈路使用情況，如果網(wǎng)絡(luò)負(fù)載不平衡，網(wǎng)絡(luò)負(fù)載高的鏈路易發(fā)生網(wǎng)絡(luò)擁塞，網(wǎng)絡(luò)負(fù)載低的鏈路會(huì)因?yàn)殒溌窙](méi)有得到充分利用而造成鏈路冗余的情況，從而導(dǎo)致平均對(duì)分帶寬降低。

為逼近真實(shí)的網(wǎng)絡(luò)負(fù)載不均衡情況，實(shí)驗(yàn)選取了Stride（6）通信模式對(duì)比ECMP、ACO-SDN、DE-ACO 的最大鏈路利用率值。為達(dá)到實(shí)驗(yàn)的公平性，對(duì)每一種算法進(jìn)行20組實(shí)驗(yàn)，每組數(shù)據(jù)流傳輸持續(xù)時(shí)間為60 s。最后計(jì)算所有的最大鏈路利用率值的累積分布函數(shù)值（Cumulative Distribution Function，CDF），設(shè)置每個(gè)區(qū)間的頻度為0.1，得到如圖7 所示的折線圖。圖7 中橫坐標(biāo)代表MLU，縱坐標(biāo)為累積分布函數(shù)值CDF，3 條曲線為ECMP、ACO-SDN、DE-ACO算法對(duì)應(yīng)的累積分布函數(shù)曲線。從圖7 可知，ECMP 算法MLU 都分布 在70%～85%，ACO-SDN 算法的MLU 在60%～75%，而DE-ACO 算法相較于ECMP 和ACO-SDN 算法MLU 降低了5%左右，大部分集中在60%～67%。

圖7 Stride模式下最大鏈路利用率比較Fig.7 Comparison of maximum link utilization in stride mode

綜上所述，在3 種通信模式下，DE-ACO 算法平均對(duì)分帶寬均高于ECMP算法和ACO-SDN算法。由于ECMP算法是根據(jù)哈希值將數(shù)據(jù)流均勻分配到不同的等價(jià)路徑中，未考慮網(wǎng)絡(luò)的實(shí)時(shí)狀態(tài)，導(dǎo)致大象流的調(diào)度無(wú)法被妥善地處理，故容易出現(xiàn)數(shù)據(jù)流沖突增多及鏈路擁塞等情況。由此可見(jiàn)，ECMP算法的平均對(duì)分帶寬相比其他兩種調(diào)度算法較低。而ACO-SDN 算法雖然可以實(shí)時(shí)獲取大象流經(jīng)過(guò)的鏈路信息，但由于該算法前期初始化的信息素較少，易導(dǎo)致收斂速度慢，故其實(shí)驗(yàn)結(jié)果比DE-ACO 算法較差，但優(yōu)于ECMP 算法。本文提出的DE-ACO 算法利用差分進(jìn)化算法計(jì)算出多條可用路徑后，融合蟻群算法進(jìn)一步精細(xì)化搜索并選擇一條全局最優(yōu)路徑，從而優(yōu)于ECMP 算法和ACO-SDN 算法，在提升對(duì)分帶寬和降低最大鏈路利用率這兩個(gè)方面的能力顯而易見(jiàn)。

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)數(shù)據(jù)中心網(wǎng)絡(luò)中存在網(wǎng)絡(luò)擁塞和易發(fā)生二次擁塞等問(wèn)題，本文提出了差分進(jìn)化融合蟻群算法的數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度機(jī)制。該機(jī)制通過(guò)sflow-rt 收集并標(biāo)記出擁堵的大象流所在的路徑后，利用差分進(jìn)化算法計(jì)算出若干條可用路徑，再融合蟻群算法來(lái)模仿螞蟻覓食的行為在這若干條可用路徑中搜索全局最優(yōu)的路徑，以達(dá)到網(wǎng)絡(luò)負(fù)載均衡的目的。通過(guò)在Mininet 仿真平臺(tái)進(jìn)行實(shí)驗(yàn)的結(jié)果表明，相較于ECMP 算法和ACO-SDN 算法，DE-ACO 算法能夠完成對(duì)對(duì)分帶寬的提高，防止重路由后的二次擁塞來(lái)有效緩解網(wǎng)絡(luò)負(fù)載不均。雖然本文實(shí)驗(yàn)取得了較好的實(shí)驗(yàn)成果，但仍存在著一些問(wèn)題，比如，因?yàn)檎鎸?shí)的數(shù)據(jù)中心網(wǎng)絡(luò)搭建所需成本和消耗的資源巨大，所以未能在真實(shí)網(wǎng)絡(luò)環(huán)境中進(jìn)行測(cè)試；而且本文實(shí)驗(yàn)采用的是單控制器，易在網(wǎng)絡(luò)中造成單點(diǎn)故障，所以下一步工作希望可以實(shí)現(xiàn)SDN 的多控制器調(diào)度機(jī)制，并擴(kuò)大實(shí)驗(yàn)規(guī)模，也可以結(jié)合不同種類的控制器來(lái)細(xì)化流量調(diào)度方案。