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

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

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

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

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

(wangranse＠bupt.edu.cn)

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

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

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

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

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

根據(jù)分析,本文提出了一種基于帶寬使用情況預(yù)測(cè)的實(shí)時(shí)調(diào)度算法,能夠解決傳統(tǒng)數(shù)據(jù)復(fù)制傳輸方式存在的以上2方面不足.本系統(tǒng)采用集中式的同時(shí)考慮流量截止時(shí)間和流量大小的調(diào)度方式,通過控制器來維護(hù)鏈路的全局信息,同時(shí),預(yù)測(cè)模塊通過各鏈路的歷史觀測(cè)值預(yù)測(cè)出當(dāng)前調(diào)度周期的在線流量(實(shí)時(shí)到達(dá)的流量)使用情況,從而將本周期內(nèi)各鏈路的剩余帶寬充分分配給離線流量(在指定時(shí)間段內(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)來實(shí)現(xiàn),主要通過一個(gè)集中式的流量工程(traffic engineering,TE)算法來為應(yīng)用分配帶寬,實(shí)現(xiàn)最大最小公平(max-min fairness,MMF),這一方式能夠使鏈路利用率達(dá)到接近100%.

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

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

根據(jù)微軟的SWAN[2]所描述,高容量DC間鏈路是一種昂貴的資源,它可以長距離提供100 Gbps到Tbps的容量,其每年的租賃成本高達(dá)100萬美元.但是DC間WAN的使用效率極差,即使是繁忙鏈路的平均利用率也僅為40%～60%,顯然供應(yīng)商目前并未充分利用這些昂貴的資源.因此微軟提出了軟件驅(qū)動(dòng)的廣域網(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ù)留了少量帶寬,并且在交換機(jī)上預(yù)留了少量內(nèi)存.通過這種方式可快速地實(shí)現(xiàn)網(wǎng)絡(luò)更新并且不會(huì)打斷現(xiàn)有網(wǎng)絡(luò)的運(yùn)行.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 在線流量預(yù)測(cè)機(jī)制

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

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

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

算法1.Sliding-k算法.

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

輸出:周期t的流量值.

①k←K;

②cp←上一個(gè)拐點(diǎn);

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

④k＝1;

⑤cp＝t;

⑥T←僅包含周期t的時(shí)間序列;

⑦else

⑧ ifT包含周期cpthen

⑨k＝k－1;

⑩ else

?k＝K;

? end if

?T←追加周期t;

? end if

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

3.1.1 EWMA

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

EWMA的表達(dá)式為

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

將EWMA的表達(dá)式歸納后可寫成:

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

3.1.2 貝葉斯在線拐點(diǎn)檢測(cè)算法

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

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

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

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

式(4)中的后驗(yàn)分布為

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

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

3.1.3 Sliding-k

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

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

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

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

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

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

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

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

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

3.2 SEDF調(diào)度算法

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

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

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

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

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

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

算法2.SEDF算法.

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

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

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

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

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

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

⑥ end for

⑦end for

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

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)配置

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

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

4.2 實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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