面向主干網(wǎng)的網(wǎng)絡(luò)級綠色節(jié)能機制?

張金宏 , 王興偉 , 易 波 , 黃 敏

1(東北大學(xué) 計算機科學(xué)與工程學(xué)院,遼寧 沈陽 110169)

2(東北大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

近些年,隨著互聯(lián)網(wǎng)用戶數(shù)持續(xù)增長和云存儲、物聯(lián)網(wǎng)等新技術(shù)和新模式的不斷涌現(xiàn)和發(fā)展,急劇增長的互聯(lián)網(wǎng)流量呈現(xiàn)出全球化趨勢,預(yù)計全球網(wǎng)絡(luò)年流量將從2017 年的1.5ZB 上升到2022 年的4.8ZB(Cisco Systems.Cisco visual networking index:Forecast and trends,2017～2022.2019.https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white-paper-c11-741490.html).為此,網(wǎng)絡(luò)運營商不得不頻繁增加網(wǎng)絡(luò)設(shè)備數(shù)量和升級網(wǎng)絡(luò)設(shè)備性能來容納新增的網(wǎng)絡(luò)流量;同時,不得不相應(yīng)地增強支撐設(shè)備(例如冷卻設(shè)備和不間斷電源);而且傳統(tǒng)互聯(lián)網(wǎng)遵循過供給原則(為應(yīng)對峰值流量而配備網(wǎng)絡(luò)資源)和冗余設(shè)計原則(為應(yīng)對網(wǎng)絡(luò)突發(fā)故障而設(shè)置冗余網(wǎng)絡(luò)資源),這將進一步增加互聯(lián)網(wǎng)中的網(wǎng)絡(luò)設(shè)備數(shù)量[1].如此激增的網(wǎng)絡(luò)設(shè)備,導(dǎo)致互聯(lián)網(wǎng)能耗的爆炸式增長[2].全球互聯(lián)網(wǎng)耗電量約占全球總耗電量的5.3%[3].按目前的增長趨勢,到2025 年,互聯(lián)網(wǎng)耗電量將會達到2006 年的13 倍[4].互聯(lián)網(wǎng)的電費支出預(yù)計在未來的7～8 年將翻一番[5].如此高的能耗增長率必將導(dǎo)致網(wǎng)絡(luò)運營商的運營成本不斷上漲,這將引發(fā)一系列的經(jīng)濟問題.

互聯(lián)網(wǎng)能耗的快速增長往往也伴隨著嚴峻的環(huán)境問題,因為目前在整個能源體系中,可再生的清潔能源所占的比重很小,主要還是依賴于傳統(tǒng)的化石能源(大約占全球一次能源消耗的81%[6]),這些都加劇了碳排放,引起了全球氣候變暖.“全球電子可持續(xù)發(fā)展倡議組織(global e-sustainability initiative,簡稱GeSI)”發(fā)表的《節(jié)能化2020 年:在信息時代推動低碳經(jīng)濟》報告認為:2020 年,全球二氧化碳排放當(dāng)量將達到519 億噸(其中,信息通信技術(shù)(information and communication technology,簡稱ICT)領(lǐng)域產(chǎn)生14 億噸)[7].無論從經(jīng)濟角度、能源角度還是環(huán)境角度看,都亟需建設(shè)低能耗高能效的綠色互聯(lián)網(wǎng)[8].

接入網(wǎng)的流量匯聚,使得主干網(wǎng)承受著比接入網(wǎng)更快的流量增長和能耗增長.隨著網(wǎng)絡(luò)流量的激增,主干網(wǎng)路由器將成為互聯(lián)網(wǎng)中最耗能的網(wǎng)絡(luò)設(shè)備[9].因此,面向主干網(wǎng)的節(jié)能問題在綠色互聯(lián)網(wǎng)的建設(shè)與發(fā)展過程中必須加以解決.

此外,隨著互聯(lián)網(wǎng)的飛速發(fā)展,網(wǎng)絡(luò)應(yīng)用類型日益豐富,對文件傳輸?shù)葌鹘y(tǒng)應(yīng)用的盡力而為(best effort)服務(wù)不適用網(wǎng)絡(luò)電話(voice over Internet protocol,簡稱VoIP)、視頻會議(video teleconference,簡稱VTC)、網(wǎng)絡(luò)電視(Internet protocol television,簡稱IPTV)以及視頻點播(video on demand,簡稱VOD)等網(wǎng)絡(luò)應(yīng)用類型[10].鑒于此,互聯(lián)網(wǎng)工程任務(wù)組(Internet engineering task force,簡稱IETF)于1994 年發(fā)布了標準RFC1633,第1 次將服務(wù)質(zhì)量(quality of service,簡稱QoS)引入網(wǎng)絡(luò),提出了綜合服務(wù)(integrated services,簡稱IntServ)模型;此后,為了克服IntServ 可擴展性差的不足,IETF 又于1998 年發(fā)布了標準RFC2474 和RFC2475,提出了差分服務(wù)(differentiated services,簡稱DiffServ)模型,規(guī)定了網(wǎng)絡(luò)對不同類型應(yīng)用的QoS 保證.

本文面向主干網(wǎng)節(jié)能問題,提出了一種網(wǎng)絡(luò)級綠色節(jié)能機制,它包括對功率感知路由器模型和捆綁鏈路模型的刻畫,在全局視圖上,使用基于最小剩余容量優(yōu)先(smallest remaining capacity first,簡稱SRCF)的綠色路由算法對網(wǎng)絡(luò)流量負載進行疏導(dǎo)匯聚,在局部視圖上使用綠色降序最佳適應(yīng)(green-best fit deceasing,簡稱G-BFD)算法求解捆綁鏈路內(nèi)部的流量分配問題(即綠色裝箱問題).該機制在考慮網(wǎng)絡(luò)節(jié)能收益最大化的同時,還基于DiffServ 模型考慮網(wǎng)絡(luò)對不同應(yīng)用的QoS 支持,在實現(xiàn)最大化網(wǎng)絡(luò)節(jié)能的同時,兼顧應(yīng)用QoS 需求.

本文第1 節(jié)綜述目前主干網(wǎng)網(wǎng)絡(luò)級節(jié)能機制的研究工作現(xiàn)狀.第2 節(jié)介紹本文涉及的網(wǎng)絡(luò)模型、節(jié)點模型、鏈路模型和功耗模型.第3 節(jié)給出我們提出的綠色節(jié)能機制所采用的SRCF 算法.第4 節(jié)在3 個實際網(wǎng)絡(luò)拓撲和高、中和低流量負載下將本文提出的路由機制和選定的基準機制在功耗和性能上進行對比分析.第5 節(jié)對全文工作進行總結(jié).

1 相關(guān)工作

目前,針對主干網(wǎng)網(wǎng)絡(luò)級節(jié)能機制的研究工作[1,11]可以按不同的分類標準劃分如下.

1) 按網(wǎng)絡(luò)鏈路類型可以分為基于捆綁鏈路(由多個物理鏈路構(gòu)成的邏輯聚合鏈路)的節(jié)能和基于非捆綁鏈路(由單一物理鏈路構(gòu)成的鏈路)的節(jié)能,現(xiàn)階段,主干網(wǎng)節(jié)點間通常由捆綁鏈路互連[12],這樣既可以更好地維持整個網(wǎng)絡(luò)的連通性,有效避免休眠喚醒鏈路時網(wǎng)絡(luò)拓撲的頻繁切換以及由此引發(fā)的路由振蕩,又可以在必要時快速更新鏈路容量而省去重新布署和更換新鏈路所需花費的時間[13];

2) 按實現(xiàn)目標可以分為約束節(jié)能(在網(wǎng)絡(luò)性能可接受(性能指標通常作為一種約束出現(xiàn))的前提下,僅以最大化網(wǎng)絡(luò)節(jié)能為目標)和權(quán)衡節(jié)能(在能耗和網(wǎng)絡(luò)性能之間尋求一個最佳平衡點);

3) 按演進范疇可以分為革新式節(jié)能(完全打破且不依賴于原有的網(wǎng)絡(luò)架構(gòu)、路由算法、路由協(xié)議等而進行的全新設(shè)計)和增補式節(jié)能(在原有的網(wǎng)絡(luò)架構(gòu)、路由算法、路由協(xié)議等的基礎(chǔ)上進行的擴充和改進),前者通?？梢垣@取更為顯著的節(jié)能效果,但是實現(xiàn)成本巨大;后者通常實現(xiàn)的節(jié)能效果較前者有限,但代價也較前者小很多.

按照上述分類,目前研究工作的特點主要體現(xiàn)在以下幾方面.

1) 當(dāng)前研究工作中,網(wǎng)絡(luò)模型中的鏈路大多為非捆綁鏈路,如文獻[14-22],少數(shù)基于捆綁鏈路,如文獻[23-27].

2) 大多數(shù)工作探索約束節(jié)能,但主要缺陷在于沒有全面考慮對各種 QoS 參數(shù)造成的影響,如文獻[14-17,19-21,23,25-27],只有少數(shù)工作探索權(quán)衡節(jié)能,如文獻[17,21,23].

3) 考慮到部署成本和實現(xiàn)代價,絕大多數(shù)工作采用增補式解決方案,如文獻[14-22,24-27],只有極少數(shù)工作采用革新式解決方案,如文獻[23].

文獻[14]提出一種綠色分布式拓撲管理機制(distributed topology management scheme for energy saving,簡稱DTME),利用VCG(vickrey-clarke-groves)機制對網(wǎng)元進行配置管理,通過信息感知、流量預(yù)測、分布式拓撲決策和休眠控制之間的協(xié)同,對網(wǎng)絡(luò)進行分布式拓撲管理以實現(xiàn)節(jié)能.文獻[15]提出一種高能效路由方法——SPEED(safe and practical energy efficient detour routing).SPEED 不需要修改傳統(tǒng)IP 分組轉(zhuǎn)發(fā)框架和路由協(xié)議,在保證網(wǎng)絡(luò)連通性的前提下,使網(wǎng)絡(luò)中空閑鏈路數(shù)最大化,同時在將流量負載聚集到活動鏈路之后休眠空閑鏈路,以此實現(xiàn)網(wǎng)絡(luò)節(jié)能最大化.文獻[16]提出在關(guān)閉網(wǎng)元實現(xiàn)網(wǎng)絡(luò)總功耗顯著減少的同時,保證網(wǎng)絡(luò)具有全連通性和最大鏈路利用率MLU(maximum link utilization).它將該問題歸結(jié)為帶容量限制的多商品流問題,對節(jié)點采用R(random),LL(least-link),LF(least-flow)和OE(opt-edge)共4 種啟發(fā)式算法進行關(guān)閉,對鏈路采用R(random)和LF(least-flow)兩種啟發(fā)式算法進行關(guān)閉,這樣對網(wǎng)絡(luò)而言,排列組合共有8 種貪婪的啟發(fā)式算法.在網(wǎng)絡(luò)流量依正弦函數(shù)變化的假設(shè)下,對這些算法進行了性能對比分析,但是它未分析關(guān)閉部分網(wǎng)元對丟包率和延遲等網(wǎng)絡(luò)性能的影響.文獻[17]提出了一個依據(jù)流量變化開關(guān)鏈路實現(xiàn)網(wǎng)絡(luò)節(jié)能的分布式能量感知流量工程解決方案DAISIES(distributed and adaptive interface switch-off for Internet energy saving),當(dāng)流量需求發(fā)生變化時,為了盡可能多地關(guān)閉鏈路,同時降低丟包率和避免網(wǎng)絡(luò)擁塞,DAISIES 通過一個特定的代價函數(shù)重新計算其采用的最短路徑路由算法中所需的鏈路權(quán)重.文獻[18]提出了一種選擇性轉(zhuǎn)發(fā)(alternative forwarding,簡稱AF)機制.當(dāng)路由流量需求時,該機制對每跳轉(zhuǎn)發(fā)都盡可能地選擇使用當(dāng)前活動的鏈路而盡量避免喚醒當(dāng)前已休眠的鏈路,從而使已休眠的鏈路獲得更長的休眠時間以實現(xiàn)節(jié)能.但是該機制通常使路由具有更長的路徑長度,增加了端到端延遲,甚至可能導(dǎo)致路由環(huán)路的產(chǎn)生.文獻[19]在運行最短路徑路由協(xié)議的網(wǎng)絡(luò)中提出基于混合整數(shù)線性規(guī)劃的能量感知權(quán)重優(yōu)化算法求解能量感知的域內(nèi)流量工程問題,利用內(nèi)部網(wǎng)關(guān)協(xié)議權(quán)重優(yōu)化算法優(yōu)化鏈路權(quán)重,通過貪婪處理階段以及使用CPLEX 求解帶容量限制的最小化成本多商品流模型,盡可能多地關(guān)閉網(wǎng)元,實現(xiàn)能耗最小化.文獻[20]提出了一種通過調(diào)節(jié)OSPF(open shortest path first)協(xié)議鏈路權(quán)重實現(xiàn)網(wǎng)絡(luò)級節(jié)能的方法.當(dāng)網(wǎng)絡(luò)經(jīng)歷混合全天多個時段的流量矩陣時,這種方法始終使用穩(wěn)定不變的鏈路權(quán)重限制網(wǎng)絡(luò)配置變化,以此減少網(wǎng)絡(luò)振蕩,提升路由配置的穩(wěn)定性.然而這種方法犧牲了較多的節(jié)能收益,存在較大不必要的能耗開銷.文獻[21]面向主干網(wǎng)在多對多組播場景下提出一種支持彈性QoS 的兩階段綠色智能路由算法,用以求解最大化用戶 QoS 區(qū)間需求滿意度且最小化全網(wǎng)絡(luò)功耗的組合優(yōu)化問題.文獻[22]在混合 SDN(software defined network)和IP(Internet protocol)的主干網(wǎng)上研究節(jié)能流量工程問題,基于這種革新式的架構(gòu),提出了一種快速啟發(fā)式算法——混合能量感知流量工程算法HEATE(hybrid energy-aware traffic engineering),所有IP 節(jié)點使用分布式OSPF 鏈路權(quán)重優(yōu)化的最短路徑路由,所有SDN 節(jié)點使用全局SDN 控制器分流管理的多路徑路由,HEATE通過聯(lián)合優(yōu)化鏈路權(quán)重和分流比將流量匯聚到部分鏈路上,通過關(guān)閉剩余未被使用的鏈路而實現(xiàn)節(jié)能.文獻[23]設(shè)計了一個定量刻畫流量和功耗之間關(guān)系的功耗模型,并提出了3 個算法,其中:Dijkstra-Green-B 算法用于實現(xiàn)路由無環(huán),Dijkstra-Green-Adv 算法用于實現(xiàn)大幅節(jié)能,Dijkstra-Green 算法聯(lián)合考慮節(jié)能和路徑伸展.與本文相比,文獻[23]的鏈路模型也考慮了捆綁鏈路,也聯(lián)合考慮了網(wǎng)絡(luò)能耗和QoS,但其在QoS 方面僅僅考慮了路徑伸展,未考慮帶寬、延遲、抖動和出錯率等重要QoS 參數(shù).基于捆綁鏈路模型和休眠喚醒策略,文獻[24]提出一種在路由過程中,通過整合后續(xù)流量進行最短路徑路由的高效節(jié)能路由算法——最短占用路徑優(yōu)先(shortest occupied path first,簡稱SOPF)算法,其在QoS 方面僅僅考慮了帶寬而未考慮其他QoS 參數(shù).文獻[25]研究了如何基于當(dāng)前的網(wǎng)絡(luò)拓撲和流量矩陣,通過選擇性關(guān)閉捆綁鏈路中的部分物理鏈路實現(xiàn)主干網(wǎng)的節(jié)能.它將該問題歸納為整數(shù)線性規(guī)劃問題,提出了3 個啟發(fā)式算法,分別是FGH(fast greedy heuristic),EGH(exhaustive greedy heuristic)和BGH(bi-level greedy heuristic),通過最大限度關(guān)閉物理鏈路來最大化網(wǎng)絡(luò)節(jié)能.文獻[26]把功率感知的邏輯拓撲設(shè)計歸結(jié)為最優(yōu)化問題,通過在低流量時期選擇性關(guān)閉線卡來減少主干網(wǎng)功耗.使用3 種不同的啟發(fā)式算法——LFA(least flow algorithm),GA(genetic algorithm)和EWA(energy watermark algorithm)分別求解此最優(yōu)化問題,在網(wǎng)絡(luò)拓撲變動時,既可以降低流量重配置率,還可以有效地降低網(wǎng)絡(luò)功率.文獻[27]提出了一種可靠綠色路由算法 R-GR(reliable green-routing)用于求解其所提出的可靠流量感知路由問題 R-EAR(reliable energy-aware-routing).雖然在關(guān)閉閑置網(wǎng)元獲取節(jié)能的同時兼顧了網(wǎng)絡(luò)終端可靠性(terminal reliability,簡稱TR)和路線可靠性(route reliability,簡稱RR),但是其主要缺陷在于路由時沒有考慮任何QoS 參數(shù),這樣導(dǎo)致實際應(yīng)用中由R-GR 計算出的路由不能提供一些應(yīng)用所需的必要QoS 支持.

上述文獻中,各節(jié)能機制間的比較見表1.為了表述簡潔,我們將捆綁鏈路(bundled link)簡記為BL,將非捆綁鏈路(non-bundled link)簡記為NBL,將約束節(jié)能(constrained energy saving)簡記為CE,將權(quán)衡節(jié)能(trade-off energy saving)簡記為TE.

Table 1 Comparison among different network-level energy-saving mechanisms表1 不同網(wǎng)絡(luò)級節(jié)能機制間的比較

相比以上研究工作,本文提出的網(wǎng)絡(luò)級節(jié)能機制是增補式的,它屬于約束節(jié)能,節(jié)能優(yōu)先,兼顧性能,全面考慮對4 個最重要QoS 參數(shù)(帶寬、延遲、抖動和出錯率)造成的影響.而且由于目前典型主干網(wǎng)核心路由器間采用捆綁鏈路進行互連[28],因此本文中節(jié)點間互連鏈路均假設(shè)為捆綁鏈路,下文中如非特殊指明,則鏈路均指捆綁鏈路.

2 模型建立

2.1 網(wǎng)絡(luò)模型

本文將主干網(wǎng)建模為連通圖G(V,E),如圖1 所示.其中,連通圖的頂點表示主干網(wǎng)的節(jié)點,連通圖的邊表示主干網(wǎng)的鏈路.V={v1,…,vn}表示所有節(jié)點的集合,E={e1,…,em}表示所有鏈路的集合.

2.2 節(jié)點模型

參考我們之前的研究工作[14],本文提出的節(jié)點結(jié)構(gòu)如圖2 所示,包括主控引擎、背板、底架、交換結(jié)構(gòu)、調(diào)度引擎、線卡、轉(zhuǎn)發(fā)引擎、復(fù)制引擎和端口等構(gòu)件.

主控引擎是路由器的控制中心,用于完成分組頭部分析和路由表查找等功能.背板由數(shù)據(jù)總線和交換結(jié)構(gòu)組成,是路由器內(nèi)部數(shù)據(jù)交換通道.底架用于承載線卡和交換結(jié)構(gòu),為線卡提供連接槽位.交換結(jié)構(gòu)用于在路由器內(nèi)部連接線卡的輸入端口和輸出端口.線卡用于實現(xiàn)分組處理、隊列調(diào)度和流量管理等功能.轉(zhuǎn)發(fā)引擎用于完成分組輸入、存儲與轉(zhuǎn)發(fā)等功能.復(fù)制引擎用于組播所需的分組復(fù)制.端口用于連接路由器和外部線路,并在兩者之間進行數(shù)據(jù)傳輸.

2.3 鏈路模型

本文采用文獻[29]的做法,假設(shè)節(jié)點vi和節(jié)點vj之間的捆綁鏈路BLij由nij條物理鏈路組成,表示如下:.本文抽象每條物理鏈路的結(jié)構(gòu)如圖3 所示,包括功率放大器、在線放大器、光再生器和前置放大器等中間設(shè)備.其中:功率放大器用來提高信號發(fā)送功率,在線放大器用來延長信號傳輸距離,光再生器用來對信號進行整形,前置放大器用來改善接收端靈敏度.

2.4 功耗模型

根據(jù)節(jié)點內(nèi)部各構(gòu)件的工作原理和功耗特征,抽象出節(jié)點功耗模型,如公式(1)所示:

基于先前給出的鏈路模型,抽象捆綁鏈路功耗模型如公式(2):

基于上述的節(jié)點功耗模型和鏈路功耗模型,全網(wǎng)的功耗模型如式(3)所示:和出端口

3 網(wǎng)絡(luò)級綠色節(jié)能機制

3.1 QoS保證

對于不同的網(wǎng)絡(luò)應(yīng)用,用戶有著不同的QoS 需求.本文基于差分服務(wù)模型[30],并參考國際電信聯(lián)盟相關(guān)標準ITU-T Y.1540[31]和ITU-T Y.1541[32],將網(wǎng)絡(luò)應(yīng)用劃分為K種類型:type1,type2,…,typeK.對于每種類型的應(yīng)用,關(guān)注4 個QoS 參數(shù):帶寬、延遲、延遲抖動和出錯率.對于第k類應(yīng)用,需要網(wǎng)絡(luò)提供的帶寬、延遲、延遲抖動和出錯率分別為,其中,1≤k≤K.

參考我們之前的研究工作[21],本文將路由途經(jīng)的每個節(jié)點處的QoS 合并到與其相連的后向鏈路中,將鏈路l的帶寬、延遲、延遲抖動和出錯率分別表示為bwl,dll,jtl和erl,則路徑P的QoS 可以通過公式(4)得到:

本文提出的路由算法針對每個流量需求計算路徑,判斷路徑QoS 是否落入對應(yīng)應(yīng)用類型所必須滿足的QoS 區(qū)間,以此確定求得的路由是否有效.

3.2 SRCF路由算法

本文設(shè)計了一種單路徑節(jié)能路由算法——基于最小剩余容量優(yōu)先(smallest remaining capacity first,簡稱SRCF)的功率感知路由算法,該算法將初始全網(wǎng)絡(luò)圖和流量需求矩陣作為算法的輸入,以邊的剩余容量配置網(wǎng)絡(luò)圖的邊權(quán)重,每次路由新的流量需求時,都選取和先前所使用路由路線的邊重疊最多的路徑,這樣,隨著路由流量需求的不斷進行,流量被不斷匯聚到一個盡可能小的網(wǎng)絡(luò)子集,通過關(guān)閉剩余的那些未被使用的網(wǎng)元來實現(xiàn)全網(wǎng)節(jié)能,偽代碼如算法1 所示.流量需求矩陣由網(wǎng)絡(luò)中所有節(jié)點對間的流量需求值組成,描述如公式(5)所示,其中,demandii=0(i∈{1,2,…,|V|}):

算法1.SRCF 算法.

輸入:DEMAND,初始網(wǎng)絡(luò)圖G0;

輸出:ROUTEorNULL.

3.3 G-BFD算法

在第3.2 節(jié)中,我們使用SRCF 算法得到所有流量需求的路由路線.由于我們的鏈路模型考慮的是捆綁鏈路,為了保證網(wǎng)絡(luò)綠色節(jié)能,將面臨對于流經(jīng)每條捆綁鏈路的流量,如何使捆綁鏈路中開啟的物理鏈路數(shù)目最少這樣一個裝箱問題,其形式化表述如下:

設(shè)當(dāng)前網(wǎng)絡(luò)中有n個流量需求流經(jīng)捆綁鏈路BLij(由nij條物理鏈路組成),它們的大小分別為.使用當(dāng)前可用容量分別為的N條物理鏈路來容納這n個流量需求,每條物理鏈路容納的流量需求總和不能超過該物理鏈路的可用容量.目標是尋求滿足以上條件,使得所使用物理鏈路的數(shù)目N最小的分配解決方案.

我們可以將上述問題規(guī)劃如下:

由于裝箱問題是一個經(jīng)典的NP 難問題,該問題不存在在多項式時間內(nèi)求得精確解的算法.因此,我們設(shè)計了一種啟發(fā)式算法——綠色降序最佳適應(yīng)(green-best fit deceasing,簡稱G-BFD)算法對其進行求解.

對流經(jīng)每個捆綁鏈路BLij(i,j∈{1,2,…,|V|},i≠j)的n個流量需求(v∈{1,2,…,n}),使用G-BFD 算法獲取流量分配解決方案,其偽代碼如算法2 所示.

算法2.G-BFD 算法.

4 仿真實現(xiàn)與機制評估

為了更好地評價本文提出的SRCF-G 機制(在全局視圖下,采用SRCF 算法,沿著具有最小剩余容量的路徑路由所有流量需求;而在局部視圖下的邊內(nèi)部使用G-BFD 算法進行流量分配),我們采用如下5 種機制在功耗和性能方面進行對比.

· SPT 機制:在全局視圖下,以功耗作為邊權(quán)重,采用SPT(shortest path tree)算法[33]路由所有流量需求;而流量在局部視圖下邊內(nèi)部的分配是隨機的(只要流量能夠被物理鏈路容納即可);

· SPT-G 機制:在全局視圖下,以功耗作為邊權(quán)重,采用SPT 算法路由所有流量需求;而在局部視圖下的邊內(nèi)部使用G-BFD 算法進行流量分配;

· SOPF 機制:采用SOPF 算法[24]路由所有流量需求,由于此算法是基于捆綁鏈路模型提出的,故無需進一步改造,可將其直接進行比較;

· MSPF 機制:采用MSPF-NF2(multiple paths by shortest path first-node first version 2)算法[34]路由所有流量需求.同樣,由于該算法也是基于捆綁鏈路模型提出的,可以將其直接進行比較;

· SRCF 機制:在全局視圖下,采用SRCF 算法,沿著具有最小剩余容量的路徑路由所有流量需求;而流量在局部視圖下邊內(nèi)部的分配是隨機的(只要流量能夠被物理鏈路容納即可).

4.1 仿真環(huán)境

以上所有方案均在如下仿真環(huán)境下進行仿真實現(xiàn).

· 硬件配置:CPU:Intel Quad-Core i5-4590@3.30GHz,RAM:4GB (DDR3,1600MHz);

· 操作系統(tǒng):Windows 7 professional 64bits;

· 開發(fā)平臺:Microsoft Visual Studio 2010;

· 開發(fā)語言:C++.

4.2 仿真數(shù)據(jù)集

· 仿真用例

采用3 個典型的主干網(wǎng)CERNET2(http://www.edu.cn/xxh/ji_shu_ju_le_bu/cernet2_lpv6/cernet2/) (20 個節(jié)點和22 條鏈路),GéANT(http://www.geant.org/Networks/Pan-European_network/Pages/GEANT_topology_map.aspx)(41 個節(jié)點和65 條鏈路)和INTERNET2(https://www.internet2.edu/media/medialibrary/2015/08/04/NetworkMap_all.pdf)(64 個節(jié)點和78 條鏈路)進行測試,如圖4 所示,特征屬性參見表2.

Table 2 Topology properties表2 拓撲屬性

· 流量數(shù)據(jù)集

對于CERNET2 拓撲,采用教育網(wǎng)Aladdin 網(wǎng)管中心信息平臺提供的開放數(shù)據(jù)集(阿拉丁網(wǎng)絡(luò)信息管理系統(tǒng),http://219.243.208.6/snmp/index.php);對于GéANT 拓撲和INTERNET2 拓撲,采用文獻[35]中提供的開放數(shù)據(jù)集.在每天3 個典型時間段,3 個拓撲的節(jié)點進出流量負載平均值變化情況如圖5 所示.

4.3 參數(shù)設(shè)置

參考思科12000 系列路由器(Cisco XR 12000 Series and Cisco 12000 Series Routers.http://www.cisco.com/c/en/us/products/routers/12000-series-routers/datasheet-listing.html)設(shè)置仿真中使用的參數(shù),見表3.

Table 3 Simulation parameters setting表3 仿真參數(shù)設(shè)置

4.4 網(wǎng)絡(luò)功耗對比

從圖6 可以觀察到:

(1) 在所有情形下,6 種機制按網(wǎng)絡(luò)功耗從高到低依次排列為:SOPF/MSPF>SPT>SPT-G>SRCF>SRCF-G,在CERNET2,GéANT 和INTERNET2 低負載情形下,SRCF-G 節(jié)省功耗分別為86.5%,70.7%和65.79%;

(2) 在INTERNET2 中、高負載和GéANT 高負載情形下,SOPF 的功耗是最高的,僅分別節(jié)省功耗7.16%,0.286%和2.13%;而在其他情形下,MSPF 的功耗是最高的;

(3) 在所有情形下,SRCF-G 和SPT-G 的功耗分別比SRCF 和SPT 有較大幅度的降低,尤其是在低流量負載下降幅最大,在CERNET2,GéANT 和INTERNET2 拓撲下分別為30.8%,19.3%,24%和42.4%,18.2%,17.2%;而在高負載情形下差距不明顯,在CERNET2,GéANT 和INTERNET2 拓撲下分別為1.29%,1.9%,1.4%和3.25%,1.82%,2.96%.

對于情況(1):首先,SRCF-G 使得網(wǎng)絡(luò)在全局視圖下,能夠以最小剩余容量路徑和盡量復(fù)用已開啟網(wǎng)元的原則路由每個流量需求,且在局部視圖下每條邊的內(nèi)部采用G-BFD 算法使得開啟的物理鏈路數(shù)最小,這樣得到一個在所有機制中最小的網(wǎng)絡(luò)子圖路由全部流量需求;其次,SRCF 和SPT 因缺少在局部視圖下的流量分配階段而開啟較多的物理鏈路,使得它們功耗分別高于SRCF-G 和SPT-G;再次,SPT-G 的功耗始終大于SRCF,這表明全局路由算法對節(jié)省功耗的貢獻大于在局部視圖下的流量分配策略;最后,SOPF 和MSPF 的功耗最高,這是因為它們都是基于最少跳數(shù)的路由機制,相比于復(fù)用已開啟網(wǎng)元的SRCF-G 和SRCF 以及直接以功耗為邊權(quán)重的SPT-G 和SPT,它們開啟了更多的網(wǎng)元.

對于情況(2):在拓撲復(fù)雜度和流量負載較低時,采用多路徑路由的MSPF 與采用單路徑路由的SOPF 相比開啟了較多的網(wǎng)元;隨著拓撲復(fù)雜度和流量負載的不斷升高,更多的網(wǎng)元不斷被開啟,SOPF 的單路徑優(yōu)勢逐漸被削弱,而MSPF 多路徑路由的優(yōu)勢逐漸顯現(xiàn)出來,較SOPF 更加均勻地在網(wǎng)元間路由流量需求,這使得其功耗最終低于SOPF.

對于情況(3):這主要是由于低負載情形下,G-BFD 算法將零散的流量分配到極少數(shù)物理鏈路上進行傳輸,使得大量的剩余空閑物理鏈路得以休眠,從而獲得盡可能多的節(jié)能收益,而隨機流量分配策略在傳輸相同的流量時使用較多物理鏈路,相比之下,剩余空閑物理鏈路數(shù)目較少,導(dǎo)致網(wǎng)絡(luò)功耗較大.而在高負載情形下,各邊中的物理鏈路利用率近乎飽和,局部視圖下的流量分配策略在此時的作用十分有限,這導(dǎo)致各機制網(wǎng)絡(luò)功耗之間差距不明顯.

4.5 網(wǎng)絡(luò)性能對比

4.5.1 平均路由跳數(shù)

從圖7 可以觀察到:

(1) 在所有情形下,SOPF 的平均路由跳數(shù)均最小,MSPF 次之;

(2) 在所有情形下,SPT 和SRCF 的平均路由跳數(shù)都分別與SPT-G 和SRCF-G 相同;

(3) SRCF 的平均路由跳數(shù)往往會大于SPT(除了在CERNET2 的低負載情形下),且在低負載情形下,兩者差距不大(在GéANT 和INTERNET2 下分別相差0.5 跳和1.3 跳);但是隨著負載的增加,這種差距會被拉大(在GéANT 和INTERNET2 下分別相差2.35 跳和2.8 跳).

對于情況(1):SOPF 的單路徑最短路徑路由使其平均路由跳數(shù)最小,MSPF 的多路徑前k條最短路路由使其僅次于SOPF.

對于情況(2):這是因為局部視圖下的流量分配策略并不影響路由選擇,所以不會影響路由跳數(shù).

對于情況(3):這是由于SRCF 不同于SPT 那樣對于每個流量需求都獨立選擇功耗權(quán)重最小的路徑進行路由,而是當(dāng)路由一個新的流量需求時,都在邊剩余容量權(quán)重最小的路徑中選擇與之前路由其他流量需求所使用的邊重疊最多的路徑進行路由.在低負載情形下,網(wǎng)絡(luò)中已開啟的網(wǎng)元較少,這樣在路由流量需求時,SRCF 復(fù)用已開啟網(wǎng)元的機會大大減少,而此時,SPT 選擇的功耗權(quán)重最小的路徑長度和SRCF 選擇的路徑長度差別很小.

4.5.2 物理鏈路關(guān)閉數(shù)目

從圖8 可以觀察到:

(1) 在所有情形下,6 種機制按關(guān)閉物理鏈路數(shù)目從多到少依次排列為:SRCF-G>SPT-G>SRCF>SOPF>MSPF>SPT,在CERNET2,GéANT 和INTERNET2 的低負載情形下SRCF-G 關(guān)閉物理鏈路數(shù)目分別為64 條、135 條和152 條,分別占物理鏈路總數(shù)的58.2%,41.5%和38.97%;

(2) 隨著流量負載的增長,各機制關(guān)閉物理鏈路數(shù)目不斷減少且差異縮小.

對于情況(1):因為SRCF-G 不僅在全局視圖下依據(jù)最小剩余流量優(yōu)先進行路由,而且局部視圖下的流量分配策略能夠盡可能地減少物理鏈路的使用,兩者的共同作用使得其勝過其他方案.SPT-G>SRCF 說明在關(guān)閉物理鏈路方面,流量分配方案是占主導(dǎo)地位的,SPT 關(guān)閉物理鏈路數(shù)是最少的.因為其沒有采用任何機制保障流量盡量“填滿”每個物理鏈路,MSPF 多路徑路由的固有屬性使其關(guān)閉物理鏈路數(shù)目僅比SPT 多;而SOPF 基于最短路徑的單路徑路由固有屬性使其關(guān)閉的物理鏈路數(shù)目介于基于最少剩余容量的單路徑路由機制SRCF 和MSPF 之間.

對于情況(2):這是因為高流量負載開啟了較多的網(wǎng)元,導(dǎo)致機制之間路由固有屬性差異和局部視圖下的流量分配策略差異都不明顯.

4.5.3 路由成功率

從圖9 可以觀察到:

(1) 在所有情形下,6 種機制按路由成功率從高到低依次排列為:SRCF-G>SRCF>MSPF>SOPF>SPT-G>SPT,即便在CERNET2,GéANT 和INTERNET2 的高負載情形下,SRCF-G 的路由成功率依然分別保持在92.1%,88.4%和84.5%;

(2) 在GéANT 和INTERNET2 的高負載情形下,SRCF-G 和SRCF 之間的路由成功率差距以及SPT-G 和SPT 之間的路由成功率差距都并不明顯.

對于情況(1):SRCF-G 的路由成功率最高,是因為它在全局視圖下路由時考慮了QoS 需求,剔除了不滿足QoS 最低要求的邊,而且局部視圖下的的流量分配策略也提高了路由成功率.SPT 的路由成功率最低,是因為它在路由時沒有考慮任何QoS 參數(shù).MSPF 為在最大鏈路利用率和路徑長度的QoS 約束下的最短多路徑路由機制,但其未考慮延遲抖動出錯率等QoS 關(guān)鍵參數(shù),這些特征使其路由成功率低于SRCF 而高于僅在帶寬約束下的最短單路徑路由機制SOPF.而SOPF 的路由成功率總是高于SPT-G,表明在全局視圖下路由時,考慮QoS 對路由成功率的貢獻優(yōu)于局部視圖下的流量分配策略.

對于情況(2):這是由于此時大部分網(wǎng)元均已被使用且剩余可用容量均較小,因此局部視圖下的流量分配策略對路由成功率的貢獻微乎其微.

4.5.4 運行時間

從圖10 可以觀察到:

(1) 在所有情形下,SPT 的運行時間均是最小的,SPT-G 次之;

(2) 在INTERNET2 中、高負載和GéANT 高負載情形下,剩余4 個機制的運行時間從大到小依次排列為MSPF>SOPF>SRCF-G>SRCF;

(3) 在INTERNET2 低負載和GéANT 中負載情形下,剩余4 個機制的運行時間從大到小依次排列為MSPF>SRCF-G>SRCF>SOPF;

(4) 在其他情形下,剩余4 個機制的運行時間從大到小依次排列為SRCF-G>SRCF>MSPF>SOPF;

(5) 隨著拓撲結(jié)構(gòu)復(fù)雜度升高和流量負載變大,各機制的運行時間呈現(xiàn)出不同幅度的增長:

對于情況(1):SPT 運行時間最小是由其固有的運算復(fù)雜度決定的,SPT-G 次之表明,局部視圖下的G-BFD 算法較SRCF,SOPF 和MSPF 有更低的運算復(fù)雜度.這是由于SRCF 不僅對每個流量需求進行路由時都要檢驗是否滿足QoS 需求,而且不滿足時還要重新選取新路徑再次檢驗,因此運行時間較長;而SOPF 和MSPF 均首先通過最短路徑路由所有流量需求而產(chǎn)生網(wǎng)絡(luò)子圖,然后使用貪婪啟發(fā)式算法對子圖中的每條邊進行逐一試探,以判斷其中的物理鏈路是否可以被關(guān)閉,在最后還需進一步執(zhí)行貪婪啟發(fā)式檢驗階段——通過不斷恢復(fù)已關(guān)閉物理鏈路而檢驗是否可以關(guān)閉更多的物理鏈路,這個階段有著與先前路由階段相同的運算復(fù)雜度,因此運行時間也較長.

對于情況(2)～情況(4):隨著網(wǎng)絡(luò)拓撲復(fù)雜度和流量負載的增加,MSPF 和SOPF 中的貪婪啟發(fā)式算法運算開銷迅速攀升,使得這兩個機制的運行時間急劇惡化(其中,多路徑路由的MSPF 尤為嚴重),直至超過SRCF 和SRCF-G.

對于情況(5):我們能夠得出結(jié)論:運算復(fù)雜度越高的機制,運行時間增長/減少率越依賴于網(wǎng)絡(luò)拓撲復(fù)雜度和流經(jīng)其上的流量負載變化,敏感性越高.

5 總結(jié)

本文從網(wǎng)絡(luò)級粒度出發(fā),研究了主干網(wǎng)綠色節(jié)能機制.本文設(shè)計了基于捆綁鏈路的功率感知功耗模型;提出了一種全局路由算法——SRCF 算法,這使得我們得到一個初步的網(wǎng)絡(luò)子圖,完成了初步的節(jié)能;之后,進一步提出了一種在捆綁鏈路內(nèi)部的局部流量分配算法——G-BFD 算法,這使得在每條捆綁鏈路內(nèi)部開啟的物理鏈路數(shù)最小.這樣,我們得到了一個更小的網(wǎng)絡(luò)子圖,完成了進一步的節(jié)能.此外,本文提出的機制在節(jié)能的同時兼顧用戶QoS 需求,在提供QoS 保證的前提下,盡可能最大化節(jié)能收益.在機制測評中,從網(wǎng)絡(luò)功耗和網(wǎng)絡(luò)性能(平均路由跳數(shù)、物理鏈路關(guān)閉數(shù)目、路由成功率和運行時間)方面對本文機制進行了全面評估.仿真結(jié)果表明:相比其他機制,本文機制在平均路由跳數(shù)和運行時間上略有增加,但在其他方面優(yōu)勢明顯,尤其在低負載時節(jié)能效果顯著.