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

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

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

近些年,隨著互聯(lián)網用戶數(shù)持續(xù)增長和云存儲、物聯(lián)網等新技術和新模式的不斷涌現(xiàn)和發(fā)展,急劇增長的互聯(lián)網流量呈現(xiàn)出全球化趨勢,預計全球網絡年流量將從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).為此,網絡運營商不得不頻繁增加網絡設備數(shù)量和升級網絡設備性能來容納新增的網絡流量;同時,不得不相應地增強支撐設備(例如冷卻設備和不間斷電源);而且傳統(tǒng)互聯(lián)網遵循過供給原則(為應對峰值流量而配備網絡資源)和冗余設計原則(為應對網絡突發(fā)故障而設置冗余網絡資源),這將進一步增加互聯(lián)網中的網絡設備數(shù)量[1].如此激增的網絡設備,導致互聯(lián)網能耗的爆炸式增長[2].全球互聯(lián)網耗電量約占全球總耗電量的5.3%[3].按目前的增長趨勢,到2025 年,互聯(lián)網耗電量將會達到2006 年的13 倍[4].互聯(lián)網的電費支出預計在未來的7～8 年將翻一番[5].如此高的能耗增長率必將導致網絡運營商的運營成本不斷上漲,這將引發(fā)一系列的經濟問題.

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

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

2 模型建立

2.1 網絡模型

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

2.2 節(jié)點模型

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

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

2.3 鏈路模型

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

2.4 功耗模型

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

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

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

3 網絡級綠色節(jié)能機制

3.1 QoS保證

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

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

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

3.2 SRCF路由算法

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

算法1.SRCF 算法.

輸入:DEMAND,初始網絡圖G0;

輸出:ROUTEorNULL.

3.3 G-BFD算法

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

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

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

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

對流經每個捆綁鏈路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 算法,沿著具有最小剩余容量的路徑路由所有流量需求;而在局部視圖下的邊內部使用G-BFD 算法進行流量分配),我們采用如下5 種機制在功耗和性能方面進行對比.

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

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

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

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

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

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

4.3 參數(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ù),見表3.

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

4.4 網絡功耗對比

從圖6 可以觀察到:

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

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

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

4.5 網絡性能對比

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 那樣對于每個流量需求都獨立選擇功耗權重最小的路徑進行路由,而是當路由一個新的流量需求時,都在邊剩余容量權重最小的路徑中選擇與之前路由其他流量需求所使用的邊重疊最多的路徑進行路由.在低負載情形下,網絡中已開啟的網元較少,這樣在路由流量需求時,SRCF 復用已開啟網元的機會大大減少,而此時,SPT 選擇的功耗權重最小的路徑長度和SRCF 選擇的路徑長度差別很小.

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

從圖8 可以觀察到:

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

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

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

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

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 關鍵參數(shù),這些特征使其路由成功率低于SRCF 而高于僅在帶寬約束下的最短單路徑路由機制SOPF.而SOPF 的路由成功率總是高于SPT-G,表明在全局視圖下路由時,考慮QoS 對路由成功率的貢獻優(yōu)于局部視圖下的流量分配策略.

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

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) 隨著拓撲結構復雜度升高和流量負載變大,各機制的運行時間呈現(xiàn)出不同幅度的增長:

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

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

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

5 總結

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