基于預(yù)測的數(shù)據(jù)中心間混合流量調(diào)度算法

王 然 張宇超 王文東 徐 恪 崔來中

1(北京郵電大學(xué)計算機學(xué)院(國家示范性軟件學(xué)院) 北京 100876)

2(網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室(北京郵電大學(xué)) 北京 100876)

3(清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084)

4(深圳大學(xué)計算機與軟件學(xué)院 廣東深圳 518060)

(wangranse＠bupt.edu.cn)

如今,越來越多的大型企業(yè)在世界各地構(gòu)建起了自己的數(shù)據(jù)中心(data center,DC)以及跨數(shù)據(jù)中心域的數(shù)據(jù)傳輸平臺.但是,連接每個數(shù)據(jù)中心對的長途鏈路十分昂貴,因此提高數(shù)據(jù)中心間鏈路的利用率毫無疑問能夠為企業(yè)帶來巨大的效益,尤其是隨著5G的到來,傳輸數(shù)據(jù)量會急劇膨脹,數(shù)據(jù)中心間鏈路利用率的提升將更為緊迫,其帶來的效益也將更為顯著.

國內(nèi)的數(shù)據(jù)中心網(wǎng)絡(luò)一般將在線流量和離線流量混合部署,其中在線流量是為用戶提供在線服務(wù)所產(chǎn)生的延遲敏感型的流量,而離線流量是由數(shù)據(jù)中心間數(shù)據(jù)復(fù)制等原因產(chǎn)生的較為不緊急的流量.文獻[1]也指出,數(shù)據(jù)中心間廣域網(wǎng)(wide area network,WAN)的流量大致可以描述為2種類型流量的混合:1)高優(yōu)流量,由用戶所面臨的需求即時到達的流量組成.到達的需求數(shù)量是無法預(yù)測的,雖然比總?cè)萘啃〉枚嗟枰怀浞譂M足.2)數(shù)據(jù)中心之間的大規(guī)模傳輸?shù)牧髁?是周期性時間需求的流量.這2類組成了廣域網(wǎng)上的大部分流量.由于2種流量共享帶寬,因此需要考慮帶寬的分離模式,也就是決定給每種流量分配多少帶寬,采用動態(tài)的還是固定的分配比例.

目前有許多關(guān)于數(shù)據(jù)中心間網(wǎng)絡(luò)性能優(yōu)化的研究[2-7],但這些傳統(tǒng)的數(shù)據(jù)中心間的數(shù)據(jù)傳輸方法具有2方面的局限:

1)固定的帶寬分離模式.在這種模式中,鏈路總帶寬被以固定的比例劃分給在線流量和離線流量,這會導(dǎo)致在線流量很少的時候,預(yù)分配給它的那部分空閑帶寬無法被數(shù)量眾多的離線流量利用.現(xiàn)有的固定帶寬分離模式是造成目前鏈路利用率低的最主要原因.理論上,如果我們能夠?qū)崟r地充分利用在線流量所剩的可用帶寬,則鏈路利用率會大大提高.

2)單一條件的最早截止時間(earliest deadline first,EDF)算法.傳統(tǒng)的EDF調(diào)度方式會根據(jù)流量的截止時間對所有流量進行調(diào)度,截止時間越早的越被優(yōu)先調(diào)度.在需要最大程度增加可完成的流量數(shù)量時,僅考慮流量截止時間的做法并不能達到期望的調(diào)度效果,因為在鏈路容量有限的情況下,當(dāng)流量截止時間相差不大但流量大小相差很大時,優(yōu)先調(diào)度較小但截止時間稍晚的流量可以在提高鏈路利用率的同時最大化完成流量的數(shù)量.

根據(jù)分析,本文提出了一種基于帶寬使用情況預(yù)測的實時調(diào)度算法,能夠解決傳統(tǒng)數(shù)據(jù)復(fù)制傳輸方式存在的以上2方面不足.本系統(tǒng)采用集中式的同時考慮流量截止時間和流量大小的調(diào)度方式,通過控制器來維護鏈路的全局信息,同時,預(yù)測模塊通過各鏈路的歷史觀測值預(yù)測出當(dāng)前調(diào)度周期的在線流量(實時到達的流量)使用情況,從而將本周期內(nèi)各鏈路的剩余帶寬充分分配給離線流量(在指定時間段內(nèi)傳輸完即可的流量),即調(diào)度器基于這些全局信息來產(chǎn)生全局最優(yōu)的調(diào)度決策.

1 相關(guān)工作

為了提高數(shù)據(jù)中心間WAN的鏈路利用率,Google先后提出了B4[8]以及它的改良版本B4 and After[9],此外還有支持其中TE組件的BwE組件[10].

B4整體采用軟件定義網(wǎng)絡(luò)(software-defined networking,SDN)的結(jié)構(gòu)來實現(xiàn),主要通過一個集中式的流量工程(traffic engineering,TE)算法來為應(yīng)用分配帶寬,實現(xiàn)最大最小公平(max-min fairness,MMF),這一方式能夠使鏈路利用率達到接近100%.

Google通過集中式的TE來實現(xiàn)全局式的調(diào)度.在B4中,SDN網(wǎng)關(guān)將來自多個站點的拓撲整合到TE控制器,帶寬執(zhí)行器(Bw E)則收集來自不同應(yīng)用的需求然后提交給控制器,然后集中式的控制器利用這些全局的信息,使用max-min fairness的方式對帶寬進行分配,這一分配過程是站在全局的角度上進行的.

Google B4 WAN的流量需求在5年內(nèi)增長了100倍,并且從一個要求99%可用性的批量傳輸、內(nèi)容復(fù)制網(wǎng)絡(luò),發(fā)展成為一個可用性要求為99.99%的支持交互的網(wǎng)絡(luò).針對帶寬需求和可靠性要求的增長,Google隨后提出了B4 and After,它改進了B4原有擴展方案,將每一個站點設(shè)計為2層拓撲抽象,同時引入了邊鏈(sidelinks)和超節(jié)點(supernode)級別的TE解決容量不對稱問題.

根據(jù)微軟的SWAN[2]所描述,高容量DC間鏈路是一種昂貴的資源,它可以長距離提供100 Gbps到Tbps的容量,其每年的租賃成本高達100萬美元.但是DC間WAN的使用效率極差,即使是繁忙鏈路的平均利用率也僅為40%～60%,顯然供應(yīng)商目前并未充分利用這些昂貴的資源.因此微軟提出了軟件驅(qū)動的廣域網(wǎng)(software-driven wide area network,SWAN),它通過協(xié)調(diào)不同服務(wù)的發(fā)送速率及集中配置網(wǎng)絡(luò)數(shù)據(jù)平面來提供高效、靈活的數(shù)據(jù)中心互聯(lián)網(wǎng)絡(luò).為了保持較高的使用效率,需要頻繁更新網(wǎng)絡(luò)狀態(tài),為此在鏈路上預(yù)留了少量帶寬,并且在交換機上預(yù)留了少量內(nèi)存.通過這種方式可快速地實現(xiàn)網(wǎng)絡(luò)更新并且不會打斷現(xiàn)有網(wǎng)絡(luò)的運行.

Facebook在Semi-Oblivious[11]中指出,需要在TE中在性能和魯棒性之間達到平衡.大多數(shù)系統(tǒng)都是針對其中一種或另一種進行優(yōu)化而設(shè)計的,但是很少有系統(tǒng)能夠同時實現(xiàn)2種優(yōu)化.由于操作限制而進一步加劇了這一挑戰(zhàn),例如路徑的數(shù)量、重配置產(chǎn)生的開銷、硬件施加的量化分割比等.Facebook因此設(shè)計了Smore,一種通過將仔細路徑選擇與動態(tài)權(quán)重適應(yīng)相結(jié)合的方法.Smore在擁塞和負載均衡指標(biāo)方面實現(xiàn)了近乎最佳的性能,在延遲方面與最短路徑的方法也堪具可比擬性.

然而這些研究的側(cè)重點無法完全與在線流量和離線流量混合部署且要求高鏈路利用率的場景吻合.以Google為例的集中式調(diào)度對于提升鏈路利用率的效果立竿見影,但Google的場景跟國內(nèi)大多數(shù)企業(yè)的場景不同,它具有2套獨立的WAN,除了上述連接眾多數(shù)據(jù)中心的B4之外還有一套是鏈接數(shù)據(jù)中心和用戶的B2,不存在在線數(shù)據(jù)和離線數(shù)據(jù)的帶寬分離問題.SWAN在設(shè)計時主要解決如何快速實現(xiàn)數(shù)據(jù)平面的更新問題,而Smore則致力于同時兼顧性能和可靠性.盡管這些TE系統(tǒng)很好地解決了各自面臨的不同需求,但它們均未深入研究鏈路中的2種流量混合部署的問題.

然而,在線流量和離線流量共用數(shù)據(jù)中心鏈路而引發(fā)的混合流量調(diào)度問題普遍存在并具有研究價值,理想的混合流量調(diào)度方案應(yīng)該在優(yōu)先調(diào)度在線流量的情況下將剩余的鏈路資源充分分配給離線流量需求,這樣一來鏈路利用率就能大大提升,寶貴的數(shù)據(jù)中心鏈路資源就能得到高效地利用,從而為企業(yè)帶來可觀的經(jīng)濟效益.

以國內(nèi)數(shù)據(jù)中心網(wǎng)絡(luò)為例,包括百度、華為在內(nèi)的數(shù)據(jù)中心網(wǎng)絡(luò)均將在線流量和離線流量混合部署,需要進一步考慮帶寬的分離模式.

百度在面臨以上問題時,先后提出了PieBridge[12]和BDS[13].PieBridge通過在殘存網(wǎng)絡(luò)上進行傳輸,最大化通信鏈路的帶寬使用,同時通過使用調(diào)度器選擇數(shù)據(jù)傳輸源,顯著減少了數(shù)據(jù)同步的完成時間.在PieBridge的理論基礎(chǔ)上,BDS具體通過充分利用DC間的覆蓋路徑來減少數(shù)據(jù)同步的完成時間,同時給組播流量(離線流量)和延遲敏感型流量(在線流量)固定地分配帶寬占比來實現(xiàn)鏈路帶寬的共享.

百度同樣指出,依賴于各個服務(wù)器的本地調(diào)度決策由于缺乏全局的信息,通常都是次優(yōu)的.所以百度提出了BDS,這是一個高度集中的結(jié)構(gòu),它通過中央控制器實時地維護agent服務(wù)器數(shù)據(jù)傳輸狀態(tài),以近似實時的方式更新最新的全局信息,以便響應(yīng)動態(tài)的性能變化、請求的變化、和路由決策的更新.這樣一個全局式的調(diào)度系統(tǒng)通常比較復(fù)雜,但是,BDS將控制算法解耦為調(diào)度和路由2個部分,從而減少集中控制的計算開銷.系統(tǒng)在調(diào)度步驟中會選出duplication data的子集,后續(xù)路由步驟僅僅考慮這些被選中的子集,搜索空間因此大大減少,全局式的調(diào)度也因此變得更加高效.

然而,固定的帶寬分離模式仍不能充分地在在線流量和離線流量之間共享帶寬.在線流量的峰值和谷值相差較大,為了保障延遲敏感型的在線流量能夠正常地進行傳輸,采用固定帶寬分離模式的系統(tǒng)往往為在線流量分配多于其一般情況需求的帶寬.這就會造成大多數(shù)情況下,分配給在線流量的帶寬未能得到有效的利用而遭到浪費,此外,在線流量的突發(fā)時有發(fā)生,一旦發(fā)生在線流量的意外激增,固定分配給在線流量的帶寬就會不足,因此,固定帶寬分離的模式不僅無法充分利用鏈路資源,也無法保障在線流量突增時的傳輸.而離線流量作為一種非延遲敏感型且規(guī)模龐大的流量,它可以根據(jù)鏈路中的在線流量占用情況來靈活調(diào)整自身的傳輸.

2 基于預(yù)測的調(diào)度系統(tǒng)概況

在傳統(tǒng)的固定帶寬分離的模式中,由于分配給延遲敏感的在線流量以及對延遲不那么敏感的離線流量的帶寬是固定的,所以即使在線流量很少時,離線流量也不能利用分配給在線流量但目前空閑的帶寬,這將導(dǎo)致很低的鏈路利用率.所以本系統(tǒng)采用了動態(tài)帶寬分離模式,根據(jù)不同的網(wǎng)絡(luò)情況來自動調(diào)整調(diào)度結(jié)果:當(dāng)在線流量突發(fā)時,本系統(tǒng)將會縮減即將分配給離線流量的帶寬以保障在線流量的性能同時避免擁堵;當(dāng)在線流量縮減時,本系統(tǒng)允許離線流量使用更多的帶寬以充分使用剩余帶寬.

圖1為本系統(tǒng)動態(tài)帶寬分離的邏輯圖.系統(tǒng)每5 s制定一次流量的調(diào)度方案,每個周期內(nèi)系統(tǒng)各模塊之間的調(diào)用關(guān)系為:

1)網(wǎng)絡(luò)監(jiān)視器讀取由代理觀察到的歷史流量信息(historical traffic),然后將這部分信息提供給預(yù)測模塊,即由指數(shù)加權(quán)移動平均(exponentially weighted moving average,EWMA)[14]和拐點檢測算法[15]組成的Sliding-k模塊.

2)拐點檢測(change point detection)子模塊依據(jù)歷史在線流量信息判斷當(dāng)前周期是否有突變出現(xiàn),并將拐點檢測結(jié)果通知到EWMA模塊.

3)EWMA模塊負責(zé)計算當(dāng)前周期的在線流量預(yù)測值,它根據(jù)拐點檢測的結(jié)果來調(diào)整自身的參數(shù),并結(jié)合歷史在線流量數(shù)據(jù),計算出當(dāng)前周期在線流量的預(yù)測值.

Fig.1 Logical diagram of dynamic bandwidth separation圖1 動態(tài)帶寬分離的邏輯圖

4)控制器模塊(Controller)負責(zé)收集系統(tǒng)的拓撲信息(包括各鏈路的初始容量、當(dāng)前剩余容量等信息)以及收集到的離線流量需求(demand)(包括需流量需求的到達時間、截止時間、流量大小、源DC、目的DC),并在系統(tǒng)做出調(diào)度決策之后及時地更新這些信息.

5)調(diào)度器(Scheduler)從控制器獲取當(dāng)前周期的拓撲信息,包括各鏈路內(nèi)的剩余帶寬大小,以及本周期內(nèi)可調(diào)度的離線流量需求,通過調(diào)度算法確定離線流量的調(diào)度順序,并使用可繞行的選路決策為每一個離線流量確定目標(biāo)路徑,從而完成調(diào)度.

3 基于預(yù)測的調(diào)度算法

3.1 在線流量預(yù)測機制

目前存在一些基本方法可以檢測在線流量變化并動態(tài)調(diào)整調(diào)度的配置,如EWMA,k-Sigma等[14,16].但這些方法有時候會連續(xù)地重配置,甚至在網(wǎng)絡(luò)很穩(wěn)定的時候也會如此,這是沒有必要的.因此,在預(yù)測可用帶寬的時候面臨著一個權(quán)衡:當(dāng)我們在預(yù)測時更偏向于參考最近的數(shù)據(jù),預(yù)測值將會出現(xiàn)明顯的震蕩,這將引起不必要的連續(xù)重調(diào)度;而當(dāng)我們在預(yù)測時更偏向于參考歷史數(shù)據(jù),預(yù)測值受近期檢測到的拐點的影響就較小,這使得系統(tǒng)對于網(wǎng)絡(luò)變化不那么敏感.

為解決上述問題,本系統(tǒng)將EWMA[14]和拐點檢測算法[15]結(jié)合,并且設(shè)計了本系統(tǒng)定制的Sliding-k算法,如算法1偽代碼所示.具體來說,我們?yōu)镋WMA方法設(shè)置了一個邊界K∈[0,1],K為使用原有EWMA方法時就需要確定的經(jīng)驗值,一般根據(jù)數(shù)據(jù)特征選擇,在本文實驗部分展示了在兼具平穩(wěn)和抖動數(shù)據(jù)時為了達到較好的效果,這一經(jīng)驗值可以設(shè)置為0.5.若當(dāng)前沒有拐點,k將被設(shè)置為K,而當(dāng)一個拐點被檢測到時,k將被設(shè)為1,然后逐漸地降至K.

在一個調(diào)度周期內(nèi),網(wǎng)絡(luò)變化監(jiān)視器不斷地獲取服務(wù)器吞吐量的一系列代理觀測值,這些值在下一個調(diào)度周期內(nèi)被用來預(yù)測可用帶寬.

算法1.Sliding-k算法.

輸入:拐點閾值P、周期t之前的流量時間序列T、EWMA的最佳實踐值K;

輸出:周期t的流量值.

①k←K;

②cp←上一個拐點;

③ifChange Point Detect(T,P)then/?判斷當(dāng)前周期是否為拐點?/

④k＝1;

⑤cp＝t;

⑥T←僅包含周期t的時間序列;

⑦else

⑧ ifT包含周期cpthen

⑨k＝k－1;

⑩ else

?k＝K;

? end if

?T←追加周期t;

? end if

? returnEWMA(k,T)./?使用EWMA方法計算當(dāng)前周期的流量?/

3.1.1 EWMA

EWMA即指數(shù)加權(quán)移動平均法,這一方法可以根據(jù)歷史觀測值來估計當(dāng)前的值,預(yù)測時給觀測值的權(quán)值隨時間呈指數(shù)遞減,離當(dāng)前時間越近的數(shù)據(jù)由于跟當(dāng)前時間的相關(guān)性越高而權(quán)重越大.

EWMA的表達式為

其中,ˉX i為時刻i的實際值,系數(shù)k表示加權(quán)下降的速度,其值越大表示下降得越快,也就是給最近觀測值的權(quán)重更大,Z i為時刻i的EWMA預(yù)測值.

將EWMA的表達式歸納后可寫成:

從式(3)可以看出,觀測值的權(quán)值隨著時間呈指數(shù)式下降.給近期觀測值較大的權(quán)重是因為離當(dāng)前時間點越近的觀測值往往對預(yù)測值有較大的影響,更能反映近期變化的趨勢.

3.1.2 貝葉斯在線拐點檢測算法

為了同時保證穩(wěn)定性以及對網(wǎng)絡(luò)變化的敏感程度,預(yù)測模塊引入貝葉斯拐點檢測算法.

該算法使用消息傳遞算法計算當(dāng)前時間序列的長度或自上一個拐點以來的時間概率分布.

貝葉斯拐點檢測算法在單變量時間序列上以在線方式執(zhí)行貝葉斯拐點檢測.核心思想是在每個新數(shù)據(jù)點到達時遞歸計算時間序列長度的后驗概率.運行長度定義為自上次拐點發(fā)生以來的時間.

給定序列的長度r t可以計算出預(yù)測分布,然后對當(dāng)前序列長度的后驗分布進行積分,找到邊際預(yù)測分布,即“t＋1時刻是序列拐點”這一事件發(fā)生的概率:

式(4)中的后驗分布為

式(5)中,序列長度和觀測值之間的聯(lián)合分布為

其中,x t表示時刻t的觀測值,r t表示時刻t的時間序列的長度,x(r)t表示r t所對應(yīng)的觀測值序列.

3.1.3 Sliding-k

在對序列進行預(yù)測時,若EWMA的參數(shù)k設(shè)置得很小,意味著給更“舊”的觀測值的權(quán)重更大,預(yù)測結(jié)果會更加平穩(wěn),但對于突發(fā)的抖動不夠靈敏;若k很大,意味著給較“新”觀測值的權(quán)重越大,預(yù)測結(jié)果就會越靈敏,但是預(yù)測值會出現(xiàn)頻繁的波動,引起連續(xù)的重配置(如果預(yù)測結(jié)果跟上一周期的預(yù)測值相差不大,則無需重新配置狀態(tài)信息,減小更新壓力).所以本系統(tǒng)采用了Sliding-k的方式,即當(dāng)前無拐點時就給更“舊”的觀測值更大的權(quán)重,以保證預(yù)測結(jié)果的平滑,而一旦檢測出拐點,就給較“新”觀測值更大的權(quán)重,保證預(yù)測結(jié)果的靈敏、準(zhǔn)確.

Sliding-k的詳細處理流程如算法1所列,其主要步驟為:

1)貝葉斯拐點檢測算法計算當(dāng)前周期為拐點的概率.首先,設(shè)定一個拐點判定的概率閾值,通過設(shè)置這一概率閾值,可以指定拐點檢測模塊對當(dāng)前時間節(jié)點的評估概率超過多少時將該節(jié)點判定為拐點.

2)依據(jù)貝葉斯拐點檢測的原理和設(shè)置好的閾值,計算當(dāng)前節(jié)點為拐點的概率.通過將上一步得出的概率值與設(shè)定好的閾值對比,判斷當(dāng)前周期是否為拐點.大于該閾值時,當(dāng)前節(jié)點被判定為拐點;小于該閾值時,當(dāng)前節(jié)點被判定為非拐點.

3)如果當(dāng)前周期為拐點,則EWMA的輸入序列的窗口大小為1,也就是EWMA輸入序列僅包含上一周期的觀測值,且參數(shù)k＝1,即預(yù)測時僅參考上一周期的觀測值,之后每經(jīng)過一個周期k值減小0.1,直到k值降低到指定的穩(wěn)定值K(如0.6).

4)如果當(dāng)前周期非拐點,則EWMA的輸入序列為上一個拐點出現(xiàn)時到上一周期這段時間內(nèi)的一系列觀測值.并且在非拐點的情況下,參數(shù)k有2種取值方式.①當(dāng)前時刻為非拐點,且k值不等于指定的最佳實踐值K,說明當(dāng)前正處于拐點發(fā)生之后k由1不斷回降至K的過程,此時k應(yīng)該比上一周期減少一個回降的步長s(如0.1),例如上一周期k＝0.8,則本周期應(yīng)為k＝0.7,s的選取跟數(shù)據(jù)的特征有關(guān),考慮到s過大或過小都將會使Sliding-k回退為接近EWMA的效果,根據(jù)實驗經(jīng)驗一般將s設(shè)置為0.1時能夠達到更好的預(yù)測效果;②當(dāng)前時刻為非拐點,且k值等于指定的最佳實踐值K,說明當(dāng)前已經(jīng)從拐點中恢復(fù)過來,處于較為穩(wěn)定的時期,則此時的k應(yīng)當(dāng)保持為穩(wěn)定環(huán)境下的最佳實踐值K,不需要再進行更新.

5)EWMA方法根據(jù)輸入的序列值和k值預(yù)測當(dāng)前周期的在線流量值,輸出到調(diào)度模塊.

上述5個步驟實現(xiàn)了拐點檢測算法和EWMA方法的結(jié)合,以拐點檢測的判定結(jié)果作為輸入,根據(jù)結(jié)果對預(yù)測時的時間序列窗口進行調(diào)整,然后再使EWMA基于這一窗口內(nèi)的時間序列進行后續(xù)的預(yù)測.Sliding-k算法對簡單的EWMA方法進行了改進,這一做法彌補了EWMA對突發(fā)狀況不敏感的缺陷,同時使得預(yù)測使用的時間序列空間能夠靈活改變,提高預(yù)測性能.

通過拐點檢測算法和EWMA方法的有效結(jié)合,Sliding-k根據(jù)拐點檢測的結(jié)果動態(tài)地調(diào)整預(yù)測方式,使得在無拐點時能夠保證預(yù)測結(jié)果的平滑,而有突發(fā)拐點時又能靈敏地響應(yīng),做出準(zhǔn)確的預(yù)測.在時而平穩(wěn)時而突變的時變網(wǎng)絡(luò)中,簡單地為EWMA的參數(shù)設(shè)置固定值進行預(yù)測顯然無法達到根據(jù)網(wǎng)絡(luò)環(huán)境變化而動態(tài)改變的需求.為了響應(yīng)變化的預(yù)測需求,使用Sliding-k算法并指定穩(wěn)定環(huán)境下的K和突變發(fā)生之后的步長s,就能在不同的網(wǎng)絡(luò)環(huán)境下分別達到不同的預(yù)測需求.

3.2 SEDF調(diào)度算法

鏈路中同時存在著2種流量:1)實時到達的、延遲敏感的在線流量;2)要求在指定時間段內(nèi)完成傳輸即可的離線流量,利用離線流量的這一性質(zhì),我們可以實時地將離線流量調(diào)度到在線流量使用之后仍有剩余的空閑鏈路上.因此在對在線流量進行了預(yù)測之后,系統(tǒng)需要使用合適的調(diào)度策略,將大量的離線流量分配到鏈路的剩余空間上.

對于具有截止時間的離線流量,傳統(tǒng)的調(diào)度方法是常用于實時調(diào)度系統(tǒng)的EDF調(diào)度算法,即具有最早截止時間的離線流量會被優(yōu)先調(diào)度,常用于各領(lǐng)域的實時調(diào)度系統(tǒng)當(dāng)中[17-21].

由于調(diào)度是以流量需求為單位的,對于服務(wù)提供商來說,可完成的流量需求的個數(shù)越多意味著調(diào)度效果越佳.由于離線流量需求的大小和截止時間都不盡相同,因此,完全按照截止時間來對離線流量進行調(diào)度的方式是不合理的,無法盡可能多地完成流量需求.

例如,有3個流量需求A,B,C,它們都需要使用同一段鏈路進行傳輸.由于一個離線流量需求通常無法在一個調(diào)度周期內(nèi)完成而需要在多個周期進行傳輸,在本例中為了方便說明,對于使用同一段鏈路的流量需求,使用調(diào)度周期(scheduling period,SP)來衡量流量需求的大小,且A,B,C三個流量需求的大小分別為5SP,3SP,2SP.同時假設(shè)A,B,C均在第1個周期開始時到達,截止時間分別為第5,6,7個周期.即這3個流量需求按照截止時間從早到晚排序同時按照流量大小由大到小排序.由于鏈路容量大小(一個周期對應(yīng)1SP)的限制,按照EDF的調(diào)度方式,將會依次調(diào)度A,B,C三個需求.第5個周期結(jié)束時,A完成傳輸,B開始傳輸;第6個周期結(jié)束時,B由于達到截止時間而終止傳輸,C開始傳輸;第7個周期結(jié)束時,C由于達到截止時間而終止傳輸.截至第7個周期結(jié)束,僅A能夠完成全部傳輸,而B和C均為部分完成,因此不能達到盡可能多地完成流量需求的要求.

而如果對A,B,C三個流量需求按照流量大小進行調(diào)度,則會優(yōu)先調(diào)度B和C這2個相對較小的流量,B,C均能全部完成,而A由于鏈路容量限制而無法全部完成,此時可完成的流量需求數(shù)量將會增加.并且隨著流量需求規(guī)模的增加,增加的可完成傳輸?shù)牧髁啃枨髷?shù)目會更多.然而,僅考慮流量需求大小的調(diào)度順序顯然會使部分截止時間靠前的大型流量得不到調(diào)度.

因此本系統(tǒng)提出了這種基于EDF算法的SEDF(Smart EDF)算法,在每個調(diào)度周期中,調(diào)度順序?qū)C合考慮流量需求的大小和截止時間.算法首先按照流量需求截止時間將需求分為指定數(shù)量的優(yōu)先級段,截止時間越早的段優(yōu)先級越高,將被優(yōu)先調(diào)度,而同一優(yōu)先級段內(nèi)的需求按需求由小到大的順序調(diào)度,如算法2偽代碼所示.

算法2.SEDF算法.

輸入:流量需求集合R、優(yōu)先級段的數(shù)量n.

①R1,R2,…,R n←Segment EDF(R);/?按照流量需求截止時間將需求分為指定數(shù)量的優(yōu)先級段?/

②for優(yōu)先級從高到低的每一個優(yōu)先級段R i

③R′i←Sort BySize(R i);/?按需求由小到大的順序?qū) i段內(nèi)的需求排序?/

④ forR i段內(nèi)的每一個需求r

⑤Select Path(r);/?為需求r選擇目標(biāo)路徑?/

⑥ end for

⑦end for

當(dāng)離線流量的負載增加和離線流量需求的數(shù)量增加時,如果僅僅按照EDF的順序進行調(diào)度意味著有些本可以完成傳輸?shù)碾x線流量需求無法完成傳輸而被丟棄.而如果在離線流量需求的截止時間相差不大,且同處于一個截止時間優(yōu)先級段內(nèi)的情況下,傳輸多個粒度較小但截止時間稍晚的離線流量需求,比傳輸一個截止時間較早但粒度較大的離線流量需求要劃算,因為此時有更多的需求能被滿足.因此本文提出了SEDF算法,它在調(diào)度時同時考慮離線流量需求的截止時間和大小,從而盡可能地增加可全部傳完的離線流量需求數(shù)目.

4 實驗評估

4.1 實驗配置

本文在華為數(shù)據(jù)中心場景中驗證了基于預(yù)測的數(shù)據(jù)中心間混合流量調(diào)度算法的有效性.實驗的數(shù)據(jù)中心網(wǎng)絡(luò)劃分為北、東、南3個數(shù)據(jù)中心域,每個數(shù)據(jù)中心域內(nèi)包含8～10個DC,且每個域中包含一個稱為DC Core的特殊DC,它作為域內(nèi)和域外傳輸?shù)奈ㄒ怀鋈肟?域間為全網(wǎng)狀的連接形式,且域間鏈路的帶寬均為50 Gbps;域內(nèi)僅存在由普通DC到DC Core的連接,且域內(nèi)鏈路的帶寬為數(shù)十至數(shù)百Mbps.

實驗的時間長度為某天20:00開始之后的24 h,調(diào)度周期為5 s.各周期各鏈路上的在線流量大小由網(wǎng)絡(luò)監(jiān)視器實時測量并提供.離線流量需求根據(jù)鏈路容量和使用情況模擬生成,每一個離線流量需求信息為一個六元組,包含需求的編號、到達時間、截止時間、流量大小、源DC、目的DC,如(1,1,79,8350112502.68,Ningbo,Fuzhou).其中到達時間和截止時間均為從實驗開始時間(20:00)算起的累計分鐘數(shù),流量大小的單位為字節(jié)(B).在實際場景中,離線流量需求量遠大于在線流量,且離線流量的時間跨度不盡相同,為了滿足離線流量的這一特征,實驗在生成模擬的離線流量的同時需要考慮鏈路使用情況,使離線流量需求稍大于剩余鏈路容量,并且到達時間、截止時間、源DC和目的DC均采用隨機的方式確定.

4.2 實驗結(jié)果和分析

為了驗證Sliding-k算法的預(yù)測效果,我們隨機生成了分段的帶“毛刺”的序列,分段平穩(wěn)的數(shù)據(jù)模擬平穩(wěn)網(wǎng)絡(luò)下的數(shù)據(jù),分段交界處的突增或突降模擬突變網(wǎng)絡(luò)下的數(shù)據(jù).實驗首先使用已有的EWMA方法對這部分模擬生成的在線流量序列進行預(yù)測,當(dāng)k設(shè)置為0.3,0.5,0.9時預(yù)測效果分別如圖2～4所示,其中黑線代表真實值,灰線代表預(yù)測值.

Fig.2 Prediction effect when the EWMA parameter k is 0.3圖2 EWMA參數(shù)k＝0.3時的預(yù)測效果

Fig.3 Prediction effect when the EWMA parameter k is 0.5圖3 EWMA參數(shù)k＝0.5時的預(yù)測效果

Fig.4 Prediction effect when the EWMA parameter k is 0.9圖4 EWMA參數(shù)k＝0.9時的預(yù)測效果

從圖2可以看到,EWMA方法的參數(shù)k＝0.3時預(yù)測結(jié)果比較平滑但不夠準(zhǔn)確,特別是在拐點出現(xiàn)的時間點上預(yù)測效果較為不理想,如圖2中03:00,13:00,19:00時刻左右,預(yù)測值偏離真實值的程度較大.而當(dāng)EWMA方法的參數(shù)k＝0.9時,不論是在時間序列走勢較為平穩(wěn)的周期還是在拐點出現(xiàn)的周期,預(yù)測值均十分接近真實值,但這樣的預(yù)測效果卻會帶來另一個問題,即預(yù)測結(jié)果在時間序列走勢較為平穩(wěn)的一段時間內(nèi)會出現(xiàn)頻繁的抖動現(xiàn)象,由于重配置會給系統(tǒng)帶來更新的開銷,為了提高處理效率,僅在當(dāng)前周期在線流量的大小跟上一周期的在線流量大小的變化量超過某一固定的閾值時,才會觸發(fā)帶寬分配情況的重配置,一旦出現(xiàn)了圖4中03:00～12:00期間的抖動較大的預(yù)測,將會引起頻繁的重配置,增加更新壓力,即使預(yù)測結(jié)果十分準(zhǔn)確,也不是本文期望達到的最佳效果.而當(dāng)EWMA方法的參數(shù)k＝0.5時,雖然拐點處的預(yù)測值不十分貼近真實值,但是比k＝0.3時預(yù)測得更準(zhǔn)確,同時,雖然在03:00～12:00期間仍然存在著多次抖動,但相較于k＝0.9的情況有所減少,能夠在一定程度上兼顧預(yù)測平滑和預(yù)測靈敏這2點需求.

由此得出了針對這一特定在線流量時間序列的相對最佳EWMA參數(shù)0.5,能夠使得EWMA方法在整段序列上都能得到相對理想的預(yù)測效果.但是,為所有的網(wǎng)絡(luò)情況采用統(tǒng)一固定的參數(shù)來進行預(yù)測無疑是一個不夠靈活的做法.最理想的模式是使EWMA方法能夠針對不同的網(wǎng)絡(luò)環(huán)境動態(tài)地調(diào)整其參數(shù)k.例如,對于圖2～4模擬生成的在線流量序列而言,有23:00,03:00,12:00,14:00,18:00這5個數(shù)據(jù)拐點,拐點情況下EWMA的參數(shù)設(shè)置得越大,預(yù)測的效果越準(zhǔn)確,在前面討論的k分別設(shè)置為0.3,0.5,0.9這3種選擇中,顯然k＝0.9是拐點發(fā)生時最適合EWMA方法采用的參數(shù).而對于23:00～03:00,03:00～12:00這2段波動較小的數(shù)據(jù)段,為了達到盡量減少重配置開銷的目的,在前面所討論的3個k值中,顯然應(yīng)該選擇k＝0.3.

由于想要實現(xiàn)預(yù)測值足夠平滑,且在拐點處的預(yù)測足夠靈敏準(zhǔn)確,因此要使用本文提出的Sliding-k算法.當(dāng)設(shè)置EWMA的參數(shù)值k＝0.3時,使用Sliding-k算法得到的預(yù)測效果如圖5所示,對比圖2所示的k同樣為0.3但僅使用EWMA方法的預(yù)測效果可以發(fā)現(xiàn),Sliding-k能夠彌補EWMA的不足,使拐點出現(xiàn)時(如03:00時刻)的預(yù)測效果更加準(zhǔn)確而貼近真實值.當(dāng)k＝0.5時,Sliding-k的整體預(yù)測效果更好,在無拐點的時段(如03:00～12:00),Sliding-k能夠達到平滑的預(yù)測效果,鮮有預(yù)測值出現(xiàn)較大落差的情況發(fā)生,而在拐點出現(xiàn)的時刻(如03:00和12:00),Sliding-k能夠作出敏感且準(zhǔn)確的預(yù)測,因而在整個時段內(nèi)的不同場景下均達到了預(yù)期的預(yù)測效果,如圖6所示:

Fig.5 Prediction effect with Sliding-k when k is 0.3圖5 Sliding-k算法在k＝0.3時的預(yù)測效果

由此可以總結(jié)出Sliding-k的預(yù)測準(zhǔn)確率和單獨使用EWMA方法相比有所提升,尤其是在拐點出現(xiàn)時,準(zhǔn)確率提升較為明顯.這不僅能在圖3和圖6的對比中直觀地展現(xiàn),而且能通過準(zhǔn)確率的統(tǒng)計來進行驗證.為了進一步評估Sliding-k算法相較EWMA方法的預(yù)測準(zhǔn)確率提升,在2種算法的k均設(shè)置為0.5且均選擇了有拐點出現(xiàn)的01:30～04:30這一時間段時,分別統(tǒng)計使用EWMA和Sliding-k算法時的準(zhǔn)確率CDF圖.這一區(qū)間的數(shù)據(jù)同時包含平穩(wěn)的數(shù)據(jù)段以及突變的數(shù)據(jù)拐點,具有普遍性和代表性.單獨使用EWMA方法時這一拐點區(qū)間的準(zhǔn)確率CDF如圖7所示,而使用Sliding-k算法的準(zhǔn)確率CDF如圖8所示.使用Sliding-k算法在拐點處進行預(yù)測的準(zhǔn)確率明顯提高,這一拐點區(qū)間內(nèi)95%的預(yù)測的準(zhǔn)確率大于90%,而EWMA方法在這一拐點區(qū)間內(nèi)僅有83%左右的預(yù)測準(zhǔn)確率大于90%.

Fig.6 Prediction effect with Sliding-k when k is 0.5圖6 Sliding-k算法在k＝0.5時的預(yù)測效果

Fig.7 Accuracy with EWMA when parameter k is 0.5圖7 使用EWMA方法預(yù)測且k＝0.5的準(zhǔn)確率

Fig.8 Accuracy with Sliding-k when parameter k is 0.5圖8 使用Sliding-k算法預(yù)測且k＝0.5的準(zhǔn)確率

為了驗證改良版的EDF算法(SEDF)的調(diào)度效果,在本系統(tǒng)的調(diào)度模塊中分別應(yīng)用簡單的EDF算法和SEDF進行對比.部分模擬生成的離線流量需求如表1所示.表1中3個離線流量需求均要求從長春數(shù)據(jù)中心傳輸?shù)轿錆h數(shù)據(jù)中心,到達時間和截止時間的大小是以20:00為原點的累計分鐘數(shù),如221即為從某日20:00開始算起的第221分鐘.

Table 1 Part of Offline Traffic Demand表1 部分離線流量需求

如果使用簡單EDF算法對離線流量進行調(diào)度,則編號為222的需求將被優(yōu)先調(diào)度,而表1(表項含義見4.1節(jié)有關(guān)需求信息的介紹)的其余2個需求由于鏈路容量有限而無法完成傳輸,此時3個需求中僅有一個需求能被滿足.而如果使用本系統(tǒng)定制的SEDF算法,編號為302和301的需求被先后調(diào)度,編號為222的需求則由于鏈路容量有限而無法完成,但此時3個需求中有2個需求被滿足.

從對比實驗中觀察到,與傳統(tǒng)的EDF算法相比,采用可以同時感知流量需求截止時間和流量大小的SEDF算法對離線流量進行調(diào)度能夠增加可完成傳輸?shù)碾x線流量需求的數(shù)目.

同時,為了驗證Sliding-k預(yù)測模塊和SEDF調(diào)度模塊共同協(xié)作的效果,實驗對比了BDS采用的固定帶寬分離方案與本系統(tǒng)的動態(tài)帶寬分離方案下的24 h內(nèi)的鏈路使用情況.實驗主要是在系統(tǒng)中為在線流量和離線流量在鏈路中的比值設(shè)定一個固定值來模擬已有的固定帶寬分離模式的效果.而本系統(tǒng)的動態(tài)帶寬分離方案則通過動態(tài)地預(yù)測當(dāng)前周期的在線流量需求大小,然后將剩下的空閑帶寬都分配給離線流量.

如圖9所示,實驗結(jié)果中,“在線流量占比”代表了在線流量占總帶寬的百分比,“固定模式”代表固定帶寬分離方案下總的帶寬利用率(在線流量和離線流量占總帶寬的百分比),“動態(tài)模式”代表本系統(tǒng)方案下的總的帶寬利用率.從圖9可以看到,為在線流量與離線流量設(shè)置固定的比值2∶3時,離線流量最多只能使用完分配給它的60%的總帶寬,盡管在線流量遠未使用完分配給它的總帶寬的40%,離線流量也不能去借用這部分空閑流量,這就造成帶寬的浪費.其中,圖9中“在線流量占比”曲線與“固定模式”曲線形狀相似是因為離線流量在每周期內(nèi)都使用了60%的帶寬(其上限),也就是說“固定模式”曲線是“在線流量占比”曲線往上平移了60%,這與前面的設(shè)想是一致的.

Fig.9 Bandwidth usage on Nanjing-Wuhan link圖9 南京 武漢鏈路上的帶寬使用情況

此外,我們還通過對鏈路容量和在線流量進行擴增以模擬業(yè)務(wù)量不斷擴增的場景.如4.1節(jié)所述,實驗的數(shù)據(jù)中心網(wǎng)絡(luò)共分3個區(qū)域,為了驗證業(yè)務(wù)量擴增時本方案的效果,在對鏈路容量進行擴增時,先找出域內(nèi)鏈路帶寬總量居中的一個域,然后將其擴增至域間鏈路容量大小(50 Gbps),記錄需要擴增的倍數(shù),然后各個域中各IDC的帶寬按照這一倍數(shù)進行擴增.同時,實驗根據(jù)在線流量的歷史觀測值將每條域內(nèi)鏈路的在線流量按倍數(shù)擴增,使擴增后的在線流量峰值至少達到該鏈路容量的60%.從實驗結(jié)果中發(fā)現(xiàn),當(dāng)在線流量的需求量不斷擴增時,基于預(yù)測的調(diào)度方案仍然能夠優(yōu)先保障在線流量不受影響的情況下,充分利用鏈路帶寬.

5 結(jié)束語

傳統(tǒng)固定帶寬分離的方式會造成這樣一種現(xiàn)象,當(dāng)在線流量處于谷值的時候,那些預(yù)留給它的帶寬由于已經(jīng)被固定地分配給了在線流量而不能被大量離線流量充分利用,從而造成數(shù)據(jù)中心間鏈路帶寬的浪費.

而本文使用了動態(tài)帶寬分離的方式,使用將EWMA和拐點檢測算法結(jié)合的Sliding-k算法預(yù)測在線流量的帶寬占用情況,在保證延遲敏感型的在線流量不受影響的條件下將剩余可用的鏈路帶寬容量分配給離線流量.Sliding-k算法在預(yù)測時先判定當(dāng)前是否出現(xiàn)拐點,然后再決定預(yù)測時“回看”多遠,這樣既能夠保證預(yù)測的靈敏,又能夠在網(wǎng)絡(luò)變化不大的時候避免頻繁的重配置.這種基于預(yù)測的流量調(diào)度方式可以使鏈路利用率接近100%,充分地利用了鏈路帶寬.而離線流量的調(diào)度則使用了基于EDF的定制算法,從離線流量需求的截止時間和流量需求大小2個維度考慮,使成功完成的離線流量需求數(shù)盡可能增多.

未來可以考慮使用EWMA之外更好的時間序列預(yù)測算法結(jié)合Sliding-k算法提高預(yù)測效果,使鏈路利用率更高而且更加穩(wěn)定.