基于PMT技術(shù)的網(wǎng)絡(luò)節(jié)能算法研究

趙 曦

(91550部隊(duì)，遼寧 大連 116023)

互聯(lián)網(wǎng)設(shè)備和業(yè)務(wù)的發(fā)展，不斷豐富著人們的日常與社交生活，卻也帶來(lái)了能耗急劇升高的關(guān)鍵問(wèn)題[1-2]。據(jù)統(tǒng)計(jì)和報(bào)道，互聯(lián)網(wǎng)能耗占據(jù)了美國(guó)總能耗的2%～10%[3]。此外，互聯(lián)網(wǎng)能源效率也極低，為互聯(lián)網(wǎng)的可持續(xù)發(fā)展帶來(lái)了挑戰(zhàn)[4]。因此，如何有效減少互聯(lián)網(wǎng)(IP網(wǎng)絡(luò))所需能耗受到了業(yè)界關(guān)注。

開(kāi)放最短路徑優(yōu)先(OSPF)是IP網(wǎng)絡(luò)中較為常見(jiàn)且使用頻繁的域內(nèi)路由協(xié)議。然而，由于業(yè)務(wù)流量的動(dòng)態(tài)變化特性，OSPF利用鏈路權(quán)重優(yōu)化流量分布的節(jié)能效果不佳[5-6]。此外，目前的文獻(xiàn)對(duì)節(jié)能中業(yè)務(wù)量時(shí)間段的劃分標(biāo)準(zhǔn)和方法不清晰，且業(yè)務(wù)量在各時(shí)間段切換的拓?fù)涫諗扛聲r(shí)間會(huì)降低網(wǎng)絡(luò)性能[7-8]。因此，以動(dòng)態(tài)變化的流量為依據(jù)，對(duì)時(shí)間片段進(jìn)行合理劃分是非常重要的。

針對(duì)上述問(wèn)題，本文基于預(yù)置多拓?fù)?PMT)技術(shù)設(shè)計(jì)了一種互聯(lián)網(wǎng)節(jié)能(ESPMT)算法。該算法先以歷史動(dòng)態(tài)業(yè)務(wù)量為依據(jù)，對(duì)時(shí)間進(jìn)行劃分，并將各時(shí)間片中出現(xiàn)的流量峰值輸入到該片段的節(jié)能問(wèn)題中，從而得到流量最小的冗余和較好的節(jié)能效果。之后，利用鄰域搜索設(shè)計(jì)快速啟發(fā)式算法對(duì)鏈路權(quán)重進(jìn)行優(yōu)化，完成節(jié)能子拓?fù)涞脑O(shè)計(jì)，從而實(shí)現(xiàn)鏈路容量約束下的單拓?fù)錁O限節(jié)能。

1 多拓?fù)涞臅r(shí)間分割設(shè)計(jì)

本文基于歷史記錄中各時(shí)間段所表現(xiàn)出的流量特征對(duì)節(jié)能子拓?fù)溥M(jìn)行設(shè)計(jì)，以實(shí)現(xiàn)業(yè)務(wù)流量動(dòng)態(tài)變化下網(wǎng)絡(luò)設(shè)備的工作和休眠調(diào)節(jié)。通常，IP網(wǎng)絡(luò)流量曲線圖在正常工作時(shí)會(huì)同時(shí)呈現(xiàn)波峰和波谷特征(帶寬余量充足)。因此，在某個(gè)時(shí)間片范圍內(nèi)必定也會(huì)出現(xiàn)波峰值與供應(yīng)量恰好相等的情形，劃分的基準(zhǔn)點(diǎn)便可選擇該時(shí)間片下的波峰[9]。最終流量曲線圖在波峰分割法下被劃分為業(yè)務(wù)量需求上升和下降階段，如圖1所示。從圖中可以看到，該曲線圖按照波峰分割法可被劃分為4個(gè)時(shí)間片。

圖1 取波峰作為基準(zhǔn)點(diǎn)的網(wǎng)絡(luò)流量曲線圖

2 節(jié)能子拓?fù)渌惴ㄔO(shè)計(jì)

由于OSPF協(xié)議下的路由，是以鏈路權(quán)重為依據(jù)通過(guò)最短路徑計(jì)算而進(jìn)行的。因此，在節(jié)能路由的相關(guān)設(shè)計(jì)中應(yīng)休眠部分鏈路集合(利用率較低)，并轉(zhuǎn)移業(yè)務(wù)流量到其他正常工作的鏈路[10-12]。由此可知，可以借助權(quán)重來(lái)調(diào)整網(wǎng)絡(luò)中各鏈路上分布的業(yè)務(wù)流量。如下圖2的網(wǎng)絡(luò)拓?fù)?7條鏈路和5個(gè)節(jié)點(diǎn)，括號(hào)左右分別為權(quán)重及業(yè)務(wù)流量)所示。若節(jié)點(diǎn)a向e傳送業(yè)務(wù)(6個(gè)單位)，則易知a-c-b-d-e以及a-b-d-e為該網(wǎng)絡(luò)中的最短路徑。此外，從圖中也可以發(fā)現(xiàn)，鏈路權(quán)重越小(大)則流量越大(小)，優(yōu)化鏈路權(quán)重可有效改變網(wǎng)絡(luò)中的流量分布，進(jìn)而完成節(jié)能的設(shè)計(jì)目標(biāo)。

圖2 拓?fù)錂?quán)重及相應(yīng)業(yè)務(wù)流量分布圖

本文在權(quán)重優(yōu)化的啟發(fā)式算法上選用Fortz設(shè)計(jì)的鄰域搜索算法，設(shè)定最大鏈路利用率的最小化為問(wèn)題的優(yōu)化目標(biāo)，并調(diào)整權(quán)重搜索方法以實(shí)現(xiàn)負(fù)載和節(jié)能的均衡[13]。該算法具體為：

(1)權(quán)重向量及其他變量的初始化。其中，搜索面積q和次數(shù)z分別初始化為0；

(2)調(diào)整鏈路權(quán)重，產(chǎn)生新的權(quán)重向量；

(3)令z自加1，若z已累加至搜索次數(shù)，則跳轉(zhuǎn)至步驟(8)；否則跳轉(zhuǎn)至步驟(4)；

(4)利用最短路徑算法計(jì)算網(wǎng)絡(luò)中可能存在的最短路徑鏈路(設(shè)定的業(yè)務(wù)工作節(jié)點(diǎn)之間)，從而獲知流量分布情況及開(kāi)關(guān)狀態(tài)，并依照目標(biāo)函數(shù)計(jì)算該權(quán)重向量作用下的能耗；

(5)評(píng)估能耗，若能滿足鏈路容量約束，并能小于目前計(jì)算得到的最小能耗，則更新該最小能耗及最優(yōu)權(quán)重向量，使q為0，跳轉(zhuǎn)至步驟(7)；否則跳轉(zhuǎn)至步驟(6)；

(6)令q自加1，若q已累加至搜索面積，則對(duì)權(quán)重向量實(shí)行擾動(dòng)操作，并令z自加1，跳轉(zhuǎn)至步驟(7)；否則，跳轉(zhuǎn)至步驟(2)；

(7)判斷搜索次數(shù)是否已經(jīng)達(dá)到，若是則跳轉(zhuǎn)至步驟(8)；否則跳轉(zhuǎn)至步驟(2)；

(8)結(jié)束當(dāng)前算法。

上述算法中的鏈路權(quán)重調(diào)整策略應(yīng)使利用率較低(低于閾值Tlow)或較高(高于閾值Thigh)的鏈路上承擔(dān)的工作業(yè)務(wù)盡量向利用率中等的相關(guān)鏈路轉(zhuǎn)移，此時(shí)鏈路具有兩級(jí)分布特性。因此，也具備較好的節(jié)能效果，并能滿足一定的容量約束。本文取Tlow=0.90，Thigh=0.33，以消除網(wǎng)絡(luò)擁塞并維持一定的網(wǎng)絡(luò)性能。由于算法中的鏈路權(quán)重被初始化為1，增幅單位也為1。因此，鏈路權(quán)重的相應(yīng)增減可具體為

(1)

其中，l，c和l/c分別代表的是鏈路負(fù)載、容量和利用率。

3 仿真及分析

結(jié)合仿真在多拓?fù)涞臅r(shí)間片劃分以及節(jié)能子拓?fù)鋬蓚€(gè)方面對(duì)ESPMT算法進(jìn)行性能驗(yàn)證，并與目前存在的其他算法進(jìn)行對(duì)比及分析。

3.1 時(shí)間片劃分對(duì)比和分析

本算法和等時(shí)間片劃分方法在Matlab仿真中的冗余流量變化結(jié)果與對(duì)比，如圖3所示。從圖中可以看到，兩種算法的預(yù)估流量均隨時(shí)間片數(shù)目的不斷增多而減少。在相同時(shí)間片數(shù)目下，ESPMT算法具有更小的冗余流量，與實(shí)際情況吻合較好。然而隨著時(shí)間片數(shù)目的不斷增加，ESPMT算法在冗余流量上的優(yōu)勢(shì)會(huì)不斷變小，直至消失。

圖3 本文算法和等時(shí)間片劃分方法對(duì)比結(jié)果

3.2 節(jié)能子拓?fù)渌惴▽?duì)比和分析

結(jié)合C++仿真，本文對(duì)ESPMT算法、基于代數(shù)連通度節(jié)能(ESACON)算法、最小流量(LF)算法和能量感知路由(EAR)算法的節(jié)能效果進(jìn)行了分析和對(duì)比。該仿真拓?fù)渚W(wǎng)絡(luò)分別為APARNET(32條鏈路和20個(gè)節(jié)點(diǎn))和USANET網(wǎng)絡(luò)(42條鏈路和24個(gè)節(jié)點(diǎn))，各鏈路均為雙向。此外，鄰域擾動(dòng)的權(quán)重在1～40范圍內(nèi)隨機(jī)產(chǎn)生，搜索次數(shù)和面積分別為3 000和100，并取概率p為0.3以實(shí)現(xiàn)權(quán)重向量分量的改變。假設(shè)各鏈路由休眠轉(zhuǎn)變?yōu)殚_(kāi)啟時(shí)具有相同的能耗，故目標(biāo)函數(shù)可簡(jiǎn)化為工作鏈路總數(shù)的最小化。

本算法借助波峰將一天(5:00開(kāi)始)劃分成6個(gè)時(shí)間片(分別命名為1～6)，并針對(duì)各時(shí)間片的業(yè)務(wù)流量峰值進(jìn)行對(duì)應(yīng)的節(jié)能設(shè)計(jì)。各節(jié)能算法在兩個(gè)網(wǎng)絡(luò)下的能耗對(duì)比，如圖4所示。從圖中可知，ESPMT算法具有最優(yōu)的節(jié)能效果；ESACON和EAR算法由于未曾對(duì)流量進(jìn)行考慮，其能耗基本沒(méi)有變化；而ESPMT和LF算法能耗與業(yè)務(wù)呈正相關(guān)。由此可知，ESPMT算法由于按照設(shè)定的流量矩陣，對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行了確定，并借助權(quán)重調(diào)整產(chǎn)生了最優(yōu)權(quán)重向量。最終趨使整個(gè)網(wǎng)絡(luò)的流量向節(jié)能鏈路轉(zhuǎn)移，因此具有良好的節(jié)能效果。

圖4 各算法在不同網(wǎng)絡(luò)中的拓?fù)淠芎膶?duì)比圖

本文也針對(duì)不同的劃分時(shí)間片方法(控制時(shí)間片個(gè)數(shù)為6個(gè))，借助鄰域搜索對(duì)各方法所耗的能量進(jìn)行計(jì)算分析和對(duì)比。由圖5可知，ESPMT算法對(duì)時(shí)間片劃分的節(jié)能效果更優(yōu)，且具有更低的能耗?？傮w來(lái)看，本文設(shè)計(jì)的算法能耗更低且節(jié)能效果更好，滿足了設(shè)計(jì)目標(biāo)和需求。

圖5 不同時(shí)間片劃分方法下鄰域搜索的能耗對(duì)比

4 結(jié)束語(yǔ)

針對(duì)IP網(wǎng)絡(luò)，本文基于預(yù)置多拓?fù)浼夹g(shù)設(shè)計(jì)了一種節(jié)能ESPMT算法。該算法首先利用波峰分割法，對(duì)1天進(jìn)行合理劃分，得到若干個(gè)時(shí)間片；之后在各時(shí)間片中，利用鄰域搜索(啟發(fā)式)的相關(guān)節(jié)能方法和策略設(shè)計(jì)子拓?fù)渌惴?。?jīng)仿真實(shí)驗(yàn)與測(cè)試，證明該算法和其他現(xiàn)有算法相比具有更優(yōu)的節(jié)能效果，為相關(guān)網(wǎng)絡(luò)節(jié)能算法的研究提供了參考。

[1] 張法,Antonio Fernandez Anta,王林,等.網(wǎng)絡(luò)能耗系統(tǒng)模型及能效算法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(3):603-615.

[2] 李偉,張溪.半馬爾科夫鏈的無(wú)線傳感網(wǎng)絡(luò)能耗模型的設(shè)計(jì)與分析[J].電子設(shè)計(jì)工程,2016,24(11):95-98.

[3] 伍元?jiǎng)?郭兵,沈艷,等.面向核心網(wǎng)的多層網(wǎng)絡(luò)能耗優(yōu)化方法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(7):1538-1548.

[4] 陳曉華.高效節(jié)能虛擬網(wǎng)絡(luò)映射模型與算法研究[D].上海:華東師范大學(xué),2016.

[5] Cianfrani A,Eramo V,Listanti M,et al.An energy saving routing algorithm for a green ospf protocol[C]. Honolulu:INFOCOM IEEE Conference on Computer Communications Workshops,IEEE,2010.

[6] Cuomo W F, Abbagnale A, Cianfrani A, et al. Keeping the connectivity and saving the energy in the internet[C].Anchorage:Computer Communications Workshops,IEEE,2011.

[7] Chiaraviglio L,Mellia M,Neri F.Reducing power consumption in backbone networks[C].Seattle:IEEE International Conference on Communications,IEEE,2009.

[8] Jamakovic A,Uhlig S.On the relationship between the algebraic connectivity and graph’s robustness to node and link failures[C].Phoenix:Eurongi Conference on Next Generation Internet Networks,IEEE,2007.

[9] 王夢(mèng)菊,吳小龍,石若玉.基于波峰搜索算法的視頻客流計(jì)數(shù)系統(tǒng)研究[J].現(xiàn)代交通技術(shù),2015,12(6):76-80.

[10] Moy J.OSPF version 2[M].Indianapolis:RFC Editor Press,1998.

[11] Guerin R A,Orda A,Williams D.QoS routing mechanisms and OSPF extensions[C].Detroit:Global Telecommunications Conference,IEEE,1999.

[12] Moy J.Multicast extensions to OSPF[M]. Indianapolis:RFC Editor Press,1994.

[13] Fortz B,Thorup M.Internet traffic engineering by optimizing OSPF weights[C].Vancouver:Proceedings of IEEE INFOCOM,2000.