一種面向主干網的器件級動態功率感知節能機制

張金宏 王興偉 易 波 黃 敏

1(東北大學計算機科學與工程學院 沈陽 110169)2(東北大學信息科學與工程學院 沈陽 110819)

近些年，隨著互聯網用戶數不斷激增，互聯網規模持續壯大.思科在其年度互聯網報告白皮書中指出：預計全球互聯網用戶數和設備數將分別從2018年的39億人和184億臺激增到2023年的53億人和293億臺[1]，由此引發互聯網能耗急劇攀升.預計到2030年信息與通信技術(information and comm-unication technologies, ICT)行業耗電量將高達82 650億kW·h，其中，互聯網耗電量高達66 900億kW·h，約占80.94%，主干網高達26 410億kW·h，約占31.95%[2].全球電子可持續發展倡議組織(Global e-Sustainability Initiative, GeSI)在SMART 2020，SMARTer2020，SMARTer2030一系列報告中指出，ICT行業的二氧化碳排放當量將以每年6%的速度遞增，2020年將達到12.7×108t，約占全球總排放量的2.3%[3-5]，預計到2030年此比重將增至23%[6].在波士頓咨詢公司(Boston Consulting Group, BCG) 2017年11月發行的關于互聯網對氣候變化影響的報告中指出互聯網每年釋放大約10×108t溫室氣體(其中主干網約占13)，約占全球二氧化碳排放量的2%[7].面對如此嚴峻的狀況，針對互聯網尤其是主干網的節能變得刻不容緩.

盡管在終端用戶設備和“最后一公里”相關技術與產品中已經采用了一些高能效的方法，但是主干網仍然處于高耗能低能效的狀態[8].這主要源于目前主干網的設計遵循“過供給原則”，即無論當前網絡中流量大小均提供恒定的冗余網絡資源以增加網絡可靠性和容納網絡峰值流量需求[9-10].然而，實際上網絡中的流量大小是動態變化的，并且在峰值和非峰值情況下流量差距很大[11].主干網的最大平均鏈路利用率低于30%，在非峰值流量期間甚至低于5%[12].在非峰值期間，由于現有網絡設備不具備功率感知能力，其功耗無法隨著資源利用率的變化而進行相應的調節，因此網絡資源未得到充分利用，其峰值功耗造成了巨大的能量浪費，導致了嚴重的低功效[13-15].面對此種情況，需要設計一種功率感知機制以實現網元的功耗隨其流量負載變化而自適應調節，即網元功耗能夠緊隨入流量大小而變化，網絡只維持能夠為所有入流量提供足夠處理性能的必需數目的網元部件而休眠其余部件，這樣能夠消除不必要的功耗.該機制的實現需要基于對網元部件功耗狀態的控制，但是如果我們僅僅對其進行粗粒度的功耗控制，則無法實現較為滿意的功率感知效果.因此，我們提出了一種基于網元細粒度控制的功率感知路由機制，將網元的構成部件做進一步的功能拆分，提取出最小的可控器件單元—線卡端口，同粗粒度的路由器底架級控制和線卡級控制相比，基于線卡端口級的控制使得網元功耗能夠更加精細地隨著網絡中流量負載的變化而進行相應的狀態調整，進而實現網絡資源更加充分的利用.此外，我們綜合考慮了2種網元功耗調整策略，即基于動態功率管理(dynamic power management, DPM)技術的低功率閑置(low power idle, LPI)策略和基于動態電壓頻率調節(dynamic voltage and frequency scaling, DVFS)技術的自適應鏈路速率(adaptive link rate, ALR)策略，當網元滿足一定的條件和閾值時可以采用這2種策略進行功耗狀態轉換，從而獲得最大的節能收益.

作為功率感知的基礎，流量負載情況的獲取至關重要.由于主干網在一些時間段具有接近峰值和變化迅速的流量負載，因此我們需要動態獲知主干網中流量的變化情況并基于此實現網絡中各個網元對其相應部件功耗的動態控制.一般說來，基于不同的動態流量獲取方法所做出的管理控制決策可以分為反應式決策和前瞻式決策[16-17].反應式決策需要監測單元實時測量網絡上的流量信息，并將監測結果發送給決策單元供其對相應部件進行管理控制，然而此過程所花費的時間對性能影響很大，因此通常對該策略的處理反應時間有較為苛刻的要求，這樣才能降低因流量信息實時獲取處理而導致的決策滯后性對網絡管理控制產生的負面影響.反應式決策的優勢在于對當前即時流量進行決策，因此決策準確度一般有保障.前瞻式決策依據預測流量進行決策，因此能夠避免反應式決策固有的決策滯后問題，從而能夠更加及時地對網絡進行管理控制，但其準確性嚴重依賴于流量負載預測的準確性.鑒于主干網基礎設施和流量自身的特點以及本文功率感知控制的場景需求，本文采用前瞻式決策對主干網中的流量信息進行及時預測.

迄今為止，對于網絡流量需求的預測方法有許多研究，其中一些預測方法，如基于神經網絡或者小波技術等的重量級預測方法，有著較高的計算復雜度和時間開銷，通常具有秒級甚至更長的預測時間[18-19].但是，由于對主干網流量突變期間部件級的功率狀態動態控制需要更加迅速的流量預測方法來滿足器件級的功率狀態動態控制，因此本文的預測方法使用滑動平均和滑動標準差模型[20]，這樣可以實現對主干網中流量波動情況的快速預測，而且從本文開展的實驗中可以看到，通過進一步調整預測參數能夠提高這種方法的預測準確度，從而提高了決策單元對網元器件的控制精度.此外，本文還使用并行化的預測計數器并擴展入流量的計數窗口，這樣可以增加流量預測中使用的樣本數目，從而使預測模塊對流量負載預測的準確性和穩定性均得到改善.

一般說來，無論我們使用什么樣的方法進行流量預測都不可能完全消除所有的預測誤差，因為實際流量大小可能超過或低于預測流量，而這將引發入流量速率和器件處理速率之間的差異，進而可能會導致數據分組丟失.為了盡可能避免數據分組丟失，我們可以使用緩沖區.盡管緩沖區的使用能夠在一定程度上減少數據分組丟失，但是緩沖區過大將導致處理延遲顯著增長，使路由器的性能嚴重下降.鑒于此，本文工作在控制分組丟失的同時，盡可能減少數據分組的處理延遲，在決策模塊中考慮緩沖區的使用狀況以減少緩沖區中因數據分組累積而引發的處理延遲.

此外，基于DiffServ模型，本文在考慮各節點節能收益的同時，還考慮其對不同應用的服務質量(quality of service, QoS)支持，盡可能在獲得最大節能收益的同時，提供必要的QoS支持.由于目前的典型主干網核心路由器間采用捆綁鏈路進行互連[21]，因此本文中節點間的互連鏈路均為捆綁鏈路.

綜上所述，本文的主要貢獻包括6個方面：

1) 面向主干網，提出了基于捆綁鏈路的動態功率感知路由器模型，且在最大化各節點節能的同時兼顧應用QoS需求，在節點調度引擎中提出了層次調度算法，使得不同類型分組的QoS在節點處得以保證.

2) 與大多數研究工作中假設靜態流量需求的做法不同，本文提出的動態功率感知節能機制能夠使得網元功耗自適應于動態流量負載.

3) 不同于基于粗粒度的路由器底架級動態功率控制和線卡級動態功率控制，本文提出了基于線卡端口級的更加細粒度的動態功率控制方案，對不同的流量變化情況給出了相應的定量求解方法，使得網元的功耗能夠更加精細地隨著網絡中流量負載的變化而進行相應的狀態調整.

4) 綜合考慮基于DPM技術的LPI策略和基于DVFS技術的ALR策略，使得這2種功耗調整策略互為補充.

5) 針對主干網基礎設施和流量自身變化的特點，為了避免信息獲取的滯后性以實現及時的控制管理決策，本文采用滑動平均和滑動標準差模型對流量進行快速準確的預測，并且在預測時隙序列的選取上考慮了同期預測和環期預測，并比較了基于兩者的流量負載預測準確性差異，進而針對流量預測過估計誤差和流量預測低估計誤差對節點功耗和節點性能的影響進行了全面的評價.

6) 在不同應用場景下，探索本文機制在功效與最差延遲之間的權衡以及在功效與緩沖區占用率之間的權衡.

1 相關工作

目前，針對主干網器件級節能的研究工作，按控制策略可以分為ALR，LPI和混合策略等；按控制粒度可以分為粗粒度和細粒度；按實現目標可以分為在性能可接受的前提下僅以最大化節能為目標的約束節能和在節能與性能之間尋求最佳平衡點的權衡節能；按演進范疇可以分為完全打破且不依賴于原有的網絡架構和網絡協議等而進行全新設計的革新式以及在原有的網絡架構和網絡協議等的基礎上進行擴充和改進的增補式.盡管革新式通常可以獲取更為顯著的節能效果，但其實現成本巨大；而增補式通常實現的節能效果較前者有限，但代價也較前者小很多.

ALR[22]根據鏈路節點端口的負載情況，自適應動態調節鏈路節點端口中數據傳輸處理速率，使鏈路節點端口能夠在低負載時減小功耗，實現節能.它使不同的鏈路節點端口工作在不同的服務速率和相應的功耗等級上，在鏈路節點端口處于低利用率時降低鏈路節點端口的傳輸處理速率，能夠在保證有限的性能影響下有效地降低功耗.網絡中的任一鏈路節點端口可以根據鏈路傳輸負載情況節點端口處理負載情況，使用基于閾值的方法選擇處于某一工作狀態的傳輸處理速率機制，當鏈路端口利用率超過或低于某一閾值時，相應地調整傳輸處理速率.

LPI[23-25]通過在低鏈路利用率期間關閉鏈路任一端相連的網元或網元部件實現網絡設備功率的節省，在需要正常傳輸數據時恢復對已關閉部分的正常供電，以此節約網絡運營成本和實現網絡通信的高效節能.

文獻[18，26-30]的研究工作均著眼于器件級節能.文獻[18]提出了一種時鐘頻率調節路由器架構，允許其內部模塊依據流量負載采用不同的時鐘頻率運行.它給出了在不同網絡環境下的4種頻率切換策略：休眠喚醒切換策略、上邊界切換策略、雙邊界切換策略和組合切換策略，以減少路由器功耗從而實現網絡節能，但是通常這樣頻繁的調節會導致功率控制復雜化，而且產生的控制延遲不可忽略.文獻[26]針對路由器線卡，提出了一種時鐘頻率自適應調節策略以最小化主干網能耗，該策略依據路由器線卡實際承載的流量需求，自適應調節路由器線卡時鐘頻率，這樣，路由器線卡不需要總保持在全速運行狀態，從而實現節能.在假設已知不同時隙的不同節點對之間的預測流量需求矩陣的前提下，它給出了一個混合整數線性規劃模型，在不同時隙為每個路由器線卡選擇最優時鐘頻率，從而使所有路由器線卡的總能耗最小.文獻[27]提出了一種廣義的ALR策略.它將網元的休眠視為服務速率為0的特殊情形.基于真實的分組軌跡，它分析了使用該策略的路由器對其鄰居路由器產生的影響.結果表明：當一個路由器采用該策略時，其下游路由器可獲得高達30%的節能.文獻[28]提出了一種被稱為“GreenRouter”的新型路由器架構，將一個線卡分成2個部分：網絡接口卡和分組處理卡，且在這2部分之間通過一個2級交換結構相連.在該架構中，從所有網絡接口卡進入的流量能夠共享所有分組處理卡，而且這些流量可以按需聚集到一部分分組處理卡上，這樣其余的分組處理卡可以被關閉以實現節能.文獻[29]提出了一種將能效以太網(energy efficient Ethernet, EEE)協議和eBond(energy-aware bonding)協議相結合的混合協議“eeeBond”，在每個路由器的網絡接口內部執行EEE協議來休眠與喚醒網絡接口，在不同網絡接口間執行eBond協議進行網絡接口切換，從而使路由器能耗自適應動態帶寬需求.它給出了一個統一的協議性能分析模型，推導出了用于設置協議最優參數的閉型表達式.結果表明，通過使用eeeBond協議和設置最優參數，網絡可以實現最大節能.文獻[30]基于NetFPGA平臺，研究網絡設備功率的刻畫方法及其調節機制.它給出了一個量化的NetFPGA交換機路由器部件能耗的測量框架，提出了一個功率調節算法，根據實際流量負載調節FPGA(field programmable gate array)內核和以太網接口的運行時鐘頻率，但是它僅僅是基于硬件的節能.文獻[26-27]是基于路由器線卡級的粗粒度控制，而文獻[18，28-30]是基于路由器線卡端口級的細粒度控制，它們均未考慮QoS支持，大多采用單一節能策略，其中文獻[28-29]基于LPI策略，文獻[18，26，30]基于ALR策略，少數(如文獻[27])考慮了LPI和ALR混合策略.

相比以上研究工作，本文提出的機制是面向主干網的增補式細粒度短期動態功率感知的約束節能，它在實現各節點功耗最小化的同時，兼顧對不同應用的QoS支持和性能保證，同時綜合運用多種節能策略.

2 問題描述

2.1 網絡模型

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

2.2 節點模型

本文提出的節點結構如圖1所示，包括主控引擎、背板、底架、交換結構、緩沖區、調度引擎、線卡、轉發引擎、復制引擎和端口等構件以及負載預測、緩沖區觀測、決策、休眠喚醒控制和速率調節等功能模塊.

主控引擎是路由器的控制中心，用于運行路由協議、實現配置管理和路由表查找等功能.背板由數據總線和交換結構組成，是路由器內部數據交換通道.底架用于承載線卡和交換結構，為線卡提供連接槽位.交換結構用于在路由器內部連接線卡的輸入端口和輸出端口.線卡用于實現分組處理、隊列調度和流量管理等功能.轉發引擎用于完成分組輸入、存儲與轉發等功能.復制引擎用于組播所需的分組復制.端口用于連接路由器和外部線路，并在兩者之間進行數據傳輸.緩沖區調節數據入口速率和數據出口速率之間的差異，部署緩沖區能夠應對流量預測錯誤的發生.使用較大的緩沖區能夠容忍更大的預測錯誤從而避免包丟失，但是包轉發時延將變大.因此，緩沖區尺寸應該根據延遲容忍來決定.緩沖區觀測模塊對緩沖區的當前使用情況進行周期性觀測并將此觀測結果發送給決策模塊.負載預測模塊使用負載的歷史統計信息和當前的負載情況來估計未來負載.在負載預測模塊中，負載計數器統計入口負載的字節數，預測計算器根據負載計數器統計出的字節數計算預測值.決策模塊根據由負載預測模塊計算出的預測結果和由緩沖區觀測模塊獲取到的緩沖區使用量綜合決策，確定需要調節速率的端口數和或需要喚醒休眠的端口數(負載需求增加時，優先使用速率調節策略，如果將所有活動端口的速率都調至最大后仍無法滿足負載需求時，則使用休眠控制策略喚醒必要數量的端口；否則，反之.)之后，決策模塊將端口狀態轉換結果，即需要調整速率的端口數和需要休眠喚醒的端口數，發送到狀態控制模塊，即速率調節子模塊和休眠喚醒子模塊.

本文把當前節點中所有連接相同下一跳節點的不同端口分到1組，這樣形成的1組端口稱之為端口組.不同的下一跳節點對應不同的端口組，這樣形成的轉發表稱之為端口組轉發表，如表1所示:

Table 1 Forwarding Table Based on Port Groups表1 端口組轉發表

休眠喚醒控制模塊基于決策模塊的端口數量調整信令和器件狀態表中記錄的器件已休眠已喚醒時間，依據已喚醒時間越長休眠優先級越高的休眠原則和已休眠時間越長喚醒優先級越高的喚醒原則，具體得出休眠喚醒端口組中的哪些端口，并向調度引擎和相應的端口下發功率狀態轉換信令.速率調節模塊基于決策模塊的端口數量調整信令和器件狀態表中記錄的器件所處不同速率等級的持續時間，依據同一速率等級持續時間越長調節優先級越高的調節原則，具體得出調節端口組中的哪些端口的轉發速率，并向調度引擎和相應的端口下發功率狀態轉換信令.調度引擎在得到來自休眠喚醒控制模塊和速率調節模塊的相關信令后，向相應端口并行轉發數據分組.相應的端口根據接收到的來自休眠喚醒控制模塊和速率調節模塊的相關信令進行相應的功率狀態轉換操作.節點內部各構件和功能模塊間的邏輯關系如圖2所示:

Fig. 2 Logical relationship among components and function modules inside the node圖2 節點內部各構件和功能模塊間邏輯關系

Fig. 3 Link structure圖3 鏈路結構

2.3 鏈路模型

典型情況下，主干網每對節點間由多條物理鏈路互連，這些鏈路形成一條邏輯捆綁鏈路[21].本文采用文獻[31]的做法假設節點vi和節點vj之間的捆綁鏈路BLij由nij條容量相同的物理鏈路組成，表示為：BLij={li1j1,li2j2,…,linjjnj}.本文抽象每條物理鏈路的結構如圖3所示，包括功率放大器、在線放大器、光再生器和前置放大器等中間設備.其中，功率放大器用來提高信號發送功率，在線放大器用來延長信號傳輸距離，光再生器用來對信號進行整形，前置放大器用來改善接收端靈敏度.

定義1.物理鏈路速率集.假設每條物理鏈路都遵循ALR策略，則對于不同的鏈路利用率LU，其自適應鏈路速率R可以確定:

(1)

其中，θi(i=1,2,…,k-1)表示劃分閾值.我們將這些不同速率組成的集合稱為物理鏈路速率集，記為Rlink={R1,R2,…,Rk}.

2.4 功耗模型

定義2.端口休眠喚醒狀態集與合并狀態集.當端口處于活動狀態Sa時，端口正常運行和處理分組；當端口處于淺層休眠狀態Ss時，端口不處理分組，但是使用一小部分功耗以維持端口的初始化狀態，這樣可以實現其從該狀態返回到活動狀態的快速蘇醒；當端口處于深層休眠狀態Sd時，端口被完全關閉，其功耗為0.因此，端口的休眠喚醒狀態集可以表示為S={Sa,Ss,Sd}.此外，再考慮到與上述物理鏈路速率集相對應的端口速率集R=Rlink={R1,R2,…,Rk}，我們得到端口的合并狀態集S={Sa1,Sa2,…,Sak,Ss,Sd}.

在休眠喚醒3個狀態中只有端口處于活動狀態才能夠處理數據分組，如果處于活動狀態的端口不足以滿足流量需求，則將引起包丟失，因此處于休眠狀態的端口必須在可接受的時間內按需激活；相反，如果因流量需求減少而不再需要過多處于活動狀態的端口，則需使多余的端口進入休眠狀態以實現節能.圖4展示了端口狀態之間的轉換.

Fig. 4 Transforming among port states圖4 端口狀態之間的轉換

從深層休眠狀態到活動狀態或淺層休眠狀態，需要包括更新內存和存儲初始信息等操作.在淺層休眠狀態，功率被持續供給以保持內存芯片上所有的數據，只是沒有提供時鐘信號，因此喚醒器件從淺層休眠狀態到活動狀態只需要重新提供時鐘信號.同深層休眠狀態的喚醒時間相比，從淺層休眠狀態到活動狀態的喚醒時間很短.表2比較了3種狀態的屬性細節，本文設從活動狀態到淺層深層休眠狀態和從淺層休眠狀態到深層休眠狀態的轉換時間為0，因為這些轉換僅是簡單地停止供電.

Table 2 Property Comparison Among Different Port States表2 不同端口狀態間的屬性比較

定義3.端口之外的器件(如線卡和底架)狀態.開啟狀態，器件正常運行和處理分組；關閉狀態，完全關閉器件，其功耗為0.

當且僅當一個線卡上的所有端口都處于深度休眠狀態，這個線卡才能關閉；同理，當且僅當一個底架上的所有線卡都關閉了，這個底架才能關閉.

表3是器件狀態表，包括所有器件當前的狀態以及該狀態所持續的時間.

根據節點內部各構件的工作原理、彼此間的交互方式、DPM技術、LPI策略以及功率狀態劃分定義，抽象出節點功耗模型:

(2)

Table 3 Component State Table表3 器件狀態表

基于DVFS技術、上述的ALR策略和先前給出的鏈路模型，抽象捆綁鏈路功耗模型:

(3)

(4)

(5)

(6)

基于上述的節點功耗模型和鏈路功耗模型，全網的功耗模型為

(7)

3 器件級功控機制

器件級功控機制既要考慮流量預測又要考慮緩沖區的占用情況.圖5展示了對從當前節點vi流向下一跳節點vj的數據分組，器件級功控機制(component-level power controlling mechanism, CPCM)是如何進行工作的，其中，Ipre為預測時隙，Iobs為緩沖區觀測時隙，Ipre=Iobs，Iswi為端口進行功率狀態轉換的時隙，Dcal為因預測計算而產生的時延，Ddec為因確定需要進行狀態轉換的端口數目而產生的時延，Dide為因落實需要進行功率轉換的具體端口而產生的時延，Dtra為因端口進行功率狀態轉換而產生的時延.

從圖5可以看出，器件級功控機制主要包括6個階段：

1) 負載預測模塊收集流量負載信息(從t=t0到t=t0+Ipre)；

經過調查發現，蘋果主要貯藏病害是在果園或采收、分級、運輸等過程中感染的，在貯藏期間遇到適宜條件就會發病。因此，蘋果苦痘病、蘋果霉心病、蘋果虎皮病等主要貯藏病害的防治須采取綜合措施，部分措施要在蘋果生長期實施。同時要盡量減少病原體，加強果園管理，防止機械損傷，創造適宜的貯藏環境，確保貯藏質量。

2) 根據第1階段收集的信息計算出預測的負載大小(從t=t0+Ipre到t=t0+Ipre+Dcal)；

3) 通過緩沖區觀測模塊獲取緩沖區使用量(在t=t0+Ipre)；

4) 根據從第2,3階段獲取的結果，決策模塊決定當前節點未來需要運行所處的功耗狀態等級(需要多少器件運行并運行在怎樣的速率級別上)，并將決策結果發送給休眠喚醒控制模塊和速率調節模塊(從t=t0+Ipre+Dcal到t=t0+Ipre+Dcal+Ddec)；

6) 所有收到信令的端口開始進行相應的狀態轉換，調度引擎根據信令將數據分組發送給相應端口(從t=t0+Ipre+Dcal+Ddec+Dide到t=t0+Ipre+Dcal+Ddec+Dide+Dtra).

3.1 預測模塊

3.1.1 預測時隙序列的選取

選取不同的時隙序列(1,2,…,t-1)進行預測直接影響到預測準確性，本文嘗試采用3種方法確定預測所需的時隙序列(1,2,…,t-1)以對時隙t內的負載大小進行較為全面地預測.

定義5.狹義同期預測.將基于先前每周對應工作日中與當前時隙相同時隙負載大小對當前時隙負載大小進行的預測稱為狹義同期預測(special same-period prediction, SSP).

定義6.環期預測.將基于先前連續時隙負載大小對當前時隙負載大小進行的預測稱為環期預測(continuous-period prediction, CP).

3.1.2 計數器數目的選取

1) 單一計數器

(8)

(9)

其中，α和β分別表示滑動平均和滑動標準差的平滑參數.從式(8)和式(9)可以看出，由于預測計算能夠通過移位寄存器來實現高速運算，因此在負載預測模塊中的計算時延可以忽略，器件級功控機制的總時延可以表示為D=Dcal+Ddec+Dide+Dtra≈Ddec+Dide+Dtra.由于此預測方法計算量較小，因此適合負載高的核心路由器.

Fig. 6 Comparison among single counter and multiple counters圖6 單個計數器和多個計數器的比較

2) 多計數器

以圖6為例，如果單一計數器，則在一個計數窗口中的分組數在[0,4]之間變化，而如果4個計數器，則在一個計數窗口中的分組數在[54,114]之間緩慢變化.可見，多計數器窗口的使用增強了的統計穩定性，可以顯著改善流量負載預測準確度以及進一步避免頻繁的預測決策帶來的網元器件功率狀態切換震蕩.

(10)

(11)

3.2 緩沖區

無論采用何種預測方法都會有誤差存在，因此本文在節點內部引入緩沖區來容忍這些誤差.然而，這些誤差可能會逐漸累積在緩沖區中，從而增加緩沖區溢出風險，因此需要定期觀測緩沖區的使用量.

為了避免緩沖區溢出導致數據分組丟失，本文設置緩沖區警戒閾值.當緩沖區使用量超過該閾值時，緩沖區觀測模塊啟用觀測值加倍機制，即將雙倍的當前緩沖區實際使用量作為觀測值向決策模塊進行反饋，以便預留足夠的端口容量.

(12)

由于使用緩沖區會增加數據分組的等待時延，因此為了既實現節省網絡功耗又避免節點處理性能下降，需要在功效和緩沖區占用率之間進行必要的均衡(詳見4.3.2節).

3.3 決策模塊

決策模塊根據負載預測模塊的預測結果和由緩沖區觀測模塊獲取到的緩沖區使用量，綜合確定如何調整端口狀態和數目.

(13)

(14)

(15)

在決策模塊中嵌入應對不同流量負載變化趨勢的端口數轉換算法(詳見算法1和算法2)，用于得出在任一預測時隙的數量轉換矩陣，從而明確各狀態端口間的數量變化情況，決策模塊據此將端口數量調整信令分別發送給休眠喚醒控制模塊和速率調節模塊.

為了確保節能收益最大化，同時考慮到喚醒端口需要付出一定的轉換代價(使端口復蘇至正常工作狀態需要一定的時延，并且該時延不可忽略[12])而休眠端口是瞬間完成的(只需對端口停止供電即可)，算法1和算法2分別基于不同的流量變化趨勢權衡休眠喚醒和速率調整所需付出的代價以及所能獲得的節能收益.且在算法1和算法2中，為了書寫簡潔，我們將端口組Gij中在時隙t-1處于狀態的全部端口切換到狀態而產生的容量變化量簡記為.

對于流量負載增加的情形，首先進行提升速率操作，即反復將當前處于最低速率等級的端口的速率等級進行逐級提升，直至能夠滿足流量增長需求為止；若所有開啟端口的速率等級升至最高后仍不能滿足流量增長需求，則進行喚醒端口操作，先喚醒淺層休眠端口，后喚醒深層休眠端口，并且為了盡可能減少喚醒端口數量，將休眠端口直接喚醒到速率等級3(對于流量負載增加剩余量不足速率等級3的部分，按流量負載實際剩余量將休眠端口喚醒至速率等級1或速率等級2).算法1的行①初始化各狀態端口間的數量轉換矩陣為零矩陣；行②③是對流量負載增幅較小(將端口速率升至2級即可滿足)時的調整；行④～是對流量負載增幅較大(所有開啟端口速率提升至最高級仍無法滿足)時的調整；行～是對流量負載增幅居中(通過提升速率操作可以滿足)時的調整；行返回更新后的各狀態端口間的數量轉換矩陣.

算法1.流量負載增加時各狀態端口間的數量轉換算法.

then

對于流量負載減少的情形，為了盡可能增加休眠端口數量，首先盡可能多地休眠當前處于低速率等級的端口，之后進一步通過降低速率，盡可能多地減少當前處于高速率等級的端口數量.算法2的行①初始化各狀態端口間的數量轉換矩陣為零矩陣；行②～是對流量負載降幅較小(將處于速率等級1的端口休眠即可滿足)時的調整；行～是對流量負載降幅居中(將處于速率等級1和2的端口休眠即可滿足)時的調整；行～是對流量負載降幅較大(將處于速率等級1，2，3的端口休眠才可滿足)時的調整；行返回更新后的各狀態端口間的數量轉換矩陣.

算法2.流量負載減小時各狀態端口間的數量轉換算法.

then

⑩ else

3.4 狀態控制模塊

3.4.1 休眠喚醒子模塊

休眠喚醒控制模塊的工作分為2個階段：

1) 接收來自決策模塊的端口數量調整信令，確定哪幾種狀態端口需要進行休眠喚醒操作以及每種狀態端口需要調整多少個.

3.4.2 速率調節子模塊

速率調節模塊的工作分為2個階段：

1) 接收來自決策模塊的端口數量調整信令，確定哪幾種速率端口需要進行速率調節操作以及每種速率端口需要調整多少個.

2) 對于同種速率端口，依據速率調節規則，具體得出調節端口組中的哪些端口的轉發速率，并向調度引擎和相應的端口下發速率轉換信令.

3.5 調度引擎

為了避免單一采用優先級排隊調度算法(priority queuing, PQ)可能出現的低優先級隊列“餓死”現象以及單一采用輪詢類算法(如輪詢調度(round robin, RR)、加權輪詢調度(weighted round robin, WRR)、赤字加權輪詢調度(deficit weighted round robin, DWRR))可能出現的無法對延遲、抖動和丟包率等敏感的關鍵分組提供優先級保證的問題，并考慮面向主干網節點和高速鏈路的應用場景(面向低速鏈路的公平排隊(fair queuing, FQ)類調度算法不適用該情形)，本文在調度引擎設計中提出了一種層次調度算法PDL(PQ-DDWRR-LRMDTF).它的隊列由2大類組成：1個PQ隊列和m個動態赤字加權輪詢調度(dynamic deficit weighted round robin, DDWRR)隊列，且PQ隊列優先級高于所有DDWRR隊列.只有當PQ隊列中的所有分組都被調度完成，才會對DDWRR隊列中的分組進行調度，并且兩者之間是搶占式的，以此確保后面隨時到來的緊急分組可以被高優先級調度.

定義11.RMDT(remaining maximum delay time).對于流入節點的某個數據分組packetk，假設其對應的應用類型為typek，這種應用類型所允許的最大延遲為delaymax k，該數據分組轉發至當前節點已經花費的延遲時間為delayk，則該數據分組所允許的剩余最大延遲時間RMDT為delaymax k-delayk.

PQ隊列和每個DDWRR隊列均采用最小RMDT優先(least RMDT first)對分組進行排序，RMDT最小的分組排在所在隊列的最前面，調度引擎在每個隊列內部總是從隊首分組開始執行調度，并且在2種隊列的內部均采用非搶占式調度，即正在處理的分組即使沒有新進來分組的RMDT小，也不必讓位于新來的分組，而是直到當前分組處理完成后才處理新來的分組.這樣設計的原因是為了避免同種隊列內部的搶占式調度造成的頻繁切換而形成的顛簸現象.在某一時刻，如果所有DDWRR隊列中存在小于PQ隊列隊尾RMDT的分組，則按該分組RMDT大小將其移至PQ隊列相應位置，以防止被“餓死”.

依據國際電信聯盟標準ITU-T Y.1541[33]中關于QoS類別的劃分和定義以及ITU-T Y.1221[34]中關于業務合約(traffic contracts)的劃分和定義，將分組分為4大類：會話類(如VoIP(voice over Internet protocol)，VTC(video teleconferencing)，IPTV(Internet protocol television))、流類(如流媒體、VOD(video on demand))、交互類(如Web訪問、數據庫檢索)和背景類(如FTP(file transfer protocol)和Email)，不同類型分組需滿足的QoS參數指標如表4所示:

Table 4 QoS Constraints Corresponding to Different Types of Packets表4 不同類型分組對應的QoS約束

當出現差分服務代碼點(differentiated services code point, DSCP)的每跳行為PHB標識碼為加急轉發EF、確保轉發AF4，AF3或AF2的分組時，則由分類器將其放入PQ隊列，優先處理；當新到分組的PHB為AF1或BE時，則由分類器依據其所屬的端口組，將其放入對應的DDWRR隊列.DDWRR隊列之間采用動態赤字加權輪詢方式進行調度，每個隊列維護一個赤字計數器(deficit counter, DC)，DC值表示每次允許調度該隊列的字節總數.每次輪詢調度時，首先初始化每個非空隊列的DC值為本隊列上次剩余的DC值和按當前各自權重計算所得的帶寬之和，調度引擎依次訪問所有非空隊列，如果當前隊列隊首分組大小不大于DC值，則DC值減去此分組的大小，并由調度引擎發送該分組到輸出端口，如此不斷更新DC值，發送分組到輸出端口，直到隊首分組大小大于DC值為止，將此時剩余的DC值累加到當前隊列下次輪詢時使用，如果隊列已空，則設置DC值為零，調度引擎移向下一非空隊列進行輪詢調度.

具體地，分配給第j個DDWRR隊列的權重可以計算得出:

(16)

(17)

綜上所述，PDL層次調度算法整體工作流程如圖7所示，調度引擎通過采用PDL層次調度算法對進入當前節點的所有數據分組進行不同優先級的調度轉發，可以確保最緊急的數據分組最先被轉發，而非緊急的數據分組也不會被“餓死”，這樣使得不同應用類型的分組所需的QoS在節點處得以保證.

Fig. 7 Schematic diagram for PDL scheduling algorithm圖7 PDL調度算法示意圖

4 仿真實現與綜合測評

本文以功耗作為網絡圖權值在節點間采用SPT(shortest path tree)算法路由每對流量需求，同時對所有網元都采用器件級功控機制.

在機制測評中，對于探索節能與性能之間的權衡以及探索過估計誤差和低估計誤差、計數窗口數目、環期預測和同期預測方式對預測準確度、節能和性能的影響，由于這些涉及的均是本機制的特有屬性，我們與未采用該機制時進行對比；而對于反映機制功效的比例性，我們選取文獻[32]中提出的節能機制BDTP(buffer dual-threshold policy)作為對比機制，該機制預設端口緩沖區占用率雙閾值，對不同的流量負載動態調整鏈路傳輸速率實現節能.此外，為了對比公平起見，我們將LPI策略引入對比機制BDTP，假設此時物理鏈路同樣具有淺層休眠和深層休眠狀態，當無分組傳輸時其可以立即進入淺層休眠狀態，超過預設時間轉為深層休眠狀態.

4.1 仿真環境

所有方案的仿真環境為:

硬件配置CPU為Intel Quad-Core i5-4590@3.30 GHz,RAM為4 GB(DDR3,1 600 MHz);操作系統為Windows 7 professional 64 bits;開發平臺為Microsoft Visual Studio 2010;開發語言為C++.

4.2 仿真數據集

仿真用例采用3個典型的主干網CERNET2 (20個節點和22條鏈路)、GéANT (41個節點和65條鏈路)和INTERNET2(64個節點和78條鏈路)，拓撲結構如圖8所示，特征屬性如表5所示.

Fig. 8 Topology use-case diagram圖8 拓撲用例

Table 5 Topological Structure Properties表5 拓撲屬性

流量數據集.對于CERNET2拓撲，通過教育網Aladdin網管中心信息平臺(1)阿拉丁網絡信息管理系統,http:219.243.208.6snmpindex.php提取在觀測期間網絡中所有節點間的進出流量監測數據，得到節點間流量分布及交互情況.對于GéANT拓撲和INTERNET2拓撲，采用文獻[35]中提供的流量數據.

環期預測數據集.由于每周對應工作日之間的流量特征具有相似性，本文選取從2016-04-10—2016-04-16期間每天24 h流量軌跡.

同期預測數據集.選取以上3個拓撲從2016-02-28—2016-09-24每天4:00—5:00，14:00—15:00，21:00—22:00這3個時間段的流量軌跡.

需要指出的是，除了在4.4.5節與環期預測進行比較時我們使用同期預測數據集之外，其余各處仿真均使用環期預測數據集.而且除了4.4.4節之外，其余各處仿真均使用8個計數器.

4.3 參數的設置和確定

參考思科12000系列路由器(2)Cisco XR 12000 Series and Cisco 12000 Series Routers.http:www.cisco.comcenusproductsrouters12000-series-routersdatasheet-listing.html設置仿真中使用的功耗和器件配置等參數，如表6所示:

Table 6 Simulation Parameters Setting表6 仿真參數設置

對于預測參數α，β，Ipre，Iobs的取值需要根據不同的流量負載狀況進行調整，本文在3個典型的代表低負載(4:00—5:00)、中負載(14:00—15:00)和高負載(21:00—22:00)特征的軌跡下對這些參數值進行調整.在這些軌跡下，分別通過式(8)或式(10)來獲取參數α的值，之后分別通過式(9)或式(11)來獲取參數β的值.流量增加時，對這2個參數值向下取整，反之向上取整.根據不同主干網中各節點的歷史流量日志和器件部署情況設置Ipre值，而Iobs取值的標準是在保證沒有分組丟失的條件下選取使當前節點功耗最小化時對應的Ipre值的整數倍.

按上述方法，CERNET2拓撲中的沈陽節點、GéANT拓撲中的丹麥節點以及INTERNET2拓撲中的匹茲堡節點在不同流量等級(traffic level, TL)的負載軌跡下的預測參數設置如表7所示:

Table 7 Prediction Parameters Setting表7 預測參數設置

4.4 機制測評

采用定義12～14中的功效、緩沖區占用率和最差延遲作為參數度量指標評價本文提出的器件級功控機制CPCM.

定義12.功效(power efficiency, PE).將當前所有休眠器件以及低速率器件共同節省的總功耗與所有器件都活動且運行在最大速率時的總功耗的比值稱為功效.功效越高越節能.

當預測開啟的處于各種速率的器件不能滿足實際到來的流量時，即實際入口負載到達速率大于節點處理輸出速率，則需要使用緩沖區來容納未被及時處理的分組，從而增加緩沖區的使用，因此除了需要對功效進行度量之外，還需要對緩沖區的使用情況進行度量.

定義13.緩沖區占用率.將當前已經使用的緩沖區大小占緩沖區總容量的百分比稱為緩沖區占用率.緩沖區占用率越小，分組的等待延遲越小.

定義14.最差延遲.將數據分組進出緩沖區的最大時間間隔稱為最差延遲，用來度量負載延遲.

此外，本文還討論采用不同數目的計數窗口以及環期預測和同期預測對預測準確性的影響，以及過估計誤差和低估計誤差對器件級功控機制的影響.

4.4.1 比例性

比例性可以反映功效隨負載變化的緊密程度，以此評價設計機制的節能潛力.最理想的情況是兩者完全成正比例線性變化，此時節能收益最大化.

定義15.節點負載率.將節點流量負載與節點容量的百分比稱為節點負載率.

定義16.端口開啟率(port opening ratio, POR).將節點中開啟端口數與總端口數的百分比稱為端口開啟率.

定義17.比例性.將端口開啟率隨節點負載率動態變化的線性程度稱為比例性.

Fig. 9 Proportionality test圖9 比例性測試

從圖9可以看出，在CPCM機制下，節點功效和端口開啟率都緊隨節點負載率的變化而趨近線性比例變化，尤其對于規模較小的拓撲比例性更好.而且，通過觀察功效變化情況可以發現，CPCM機制的引入能夠節省大量的功耗，甚至當節點負載率高達70%時，仍能維持14%～20%的功效.由此可見，CPCM機制能夠依據流量負載變化非常有效地控制功效和端口狀態.而在BDTP機制下，節點功效在低負載和高負載時差異很大，近似階躍式變化；端口開啟率始終較高，對節點負載率的變化不敏感，并且拓撲結構越復雜的節點越明顯.2種機制的顯著差異主要來源于前者對捆綁鏈路中全部物理鏈路規劃端口的開關和速率的調整，較大限度地保證了所開即所需，而后者捆綁鏈路各端口之間是相互獨立的，沒有聚合流量，于是開啟了多余的端口或者使用了較大而不必要的高速率，導致功效顯著降低.

4.4.2 節能與性能之間的權衡

權衡是既要保證節能效果又要保障一定的運行性能而不得不在兩者之間做出的折中考量.本文關注功效與最差延遲之間的權衡以及功效與緩沖區占用率之間的權衡.

圖10顯示了在不同的緩沖區使用量警戒閾值ζ下的功效與最差延遲權衡分布以及功效與緩沖區占用率權衡分布.可以看出，當設置最差延遲為某個確定值時，能夠獲得在此限制下的最大功效；反之，當需要實現特定級別的功效時，能夠獲得此時的最壞延遲.例如，觀察區域C1，G1，I1中ζ≥0.8的點，功效達到80%以上，但最差延遲至少30 ms，使用這樣的ζ值能夠以增大最差延遲為代價換取功效最大化.這種情況適用于在注重節能的環境下進行部署，僅需滿足最低的延遲需求即可.又如，在區域C2，G2，I2中的ζ≤0.2的點，此時緩沖區頻繁刷新，與區域C1，G1，I1相比，功效降低超過50%，但最差延遲減小可達23，即最差延遲被最大程度地減小，但功效被最小化.這種情況適用于對負載延遲有苛刻約束而對節能不敏感的環境.最后，在區域C3，G3，I3中的ζ∈[0.6,0.7]的點，這樣的點是權衡后的“甜蜜點”，既沒有太糟糕的最差延遲(比第1種情況少50%)，也能獲得一定的節能效果(比第1種情況少30%).因此，本文通過選擇適當的控制參數 ζ 以滿足在某一環境下的部署需求.

Fig. 10 Tradeoff between energy saving and performance圖10 節能與性能之間的權衡

從圖10還可以看出，如果使用增加功效的參數，則緩沖區占用率將增長，反之功效將減小.這是因為緩沖區中數據分組的累積會導致最差延遲的增長.當選擇減少最差延遲的參數，緩沖區占用率也將減少，因此可以通過恰當地使用緩沖區減小最差延遲.

4.4.3 過估計誤差和低估計誤差的影響

當負載預測模塊得到的預測性能偏離實際需要的性能時會產生過估計或低估計.

如果是過估計，則意味著投入了比實際需要更多的器件用于處理入口負載，降低了功效，造成能源的浪費，但對節點的處理性能沒有影響.

如果是低估計，則意味著投入了比實際需要更少的器件用于處理入口負載.這會導致數據分組在緩沖區中的不斷累積從而導致負載最差延遲的增長，甚至可能導致數據分組累積過多而使緩沖區溢出從而導致分組丟失，嚴重影響節點的處理性能.

圖10中的區域C1，G1，I1中的點可以看作是發生低估計時的狀況，盡管獲得了功效收益，但是最差延遲的增長惡化了節點的性能.區域C2，G2，I2中的點可以看作是發生過估計的狀況，犧牲了功效換取了負載最差延遲的減小.對于運行在主干網中的核心節點來說，與過估計相比，低估計的發生更需要被避免.

4.4.4 計數窗口數目對預測的影響

定義18.端口數平均誤差.將當前開啟端口數Nactive和實際所需開啟端口數Nactual間的平均誤差稱為端口數平均誤差，記為χ，計算為

(18)

χ能夠反映過估計低估計的趨勢.

定義19.端口數均方根誤差.將當前開啟端口數Nactive和實際所需開啟端口數Nactual之間的均方根誤差稱為端口數均方根誤差，記為δ，計算為

(19)

δ能夠反映預測值追蹤實際負載的準確程度.其中，npre是預測的總次數.

記處于過估計狀態的端口數均方根誤差為δover，計算為

(20)

δover值越小，表示過估計的影響越小，可以實現更高的功效控制.

記處于低估計狀態的端口數均方根誤差為δunder，計算為

(21)

δunder值越小，意味著低估計的影響越小，可以實現更小的負載延遲.其中，nover和nunder分別是過估計和低估計發生次數.

圖11展示了節點預測模塊采用不同數目的計數器時的預測準確度比較，在3個拓撲中，在高負載情形下δunder均大于δover而占據主導地位，在低負載情形下δover都大于δunder而占據主導地位，在所有情形下平均誤差χ都趨于0.上述說明，計數器數目不影響預測趨勢.與單個計數器相比，當使用8個計數器時，所有的δover和δunder均大幅降低，這是由于增加計數器數目可以減少流量負載頻繁波動對預測準確度的影響.

Fig. 11 Comparison on prediction accuracy among different number of counters圖11 不同數目計數器間的預測準確度比較

4.4.5 環期預測和同期預測

記環期預測、廣義同期預測和狹義同期預測下的端口數均方根誤差分別為δCP，δGSP，δSSP，均通過式(19)計算得到.

圖12展示了當選取不同的預測時隙序列時對預測準確度的影響.可以看出，低負載時，采用環期預測的均方根誤差明顯小于廣義同期預測和狹義同期預測；高負載時，大多數情況下環期預測的準確度與廣義同期預測較為接近.這是因為環期預測對網絡流量低平穩高抖動的日夜規律依賴性更大，呈現低負載預測準確度高而高負載預測準確率低的特征.在所有負載情形下，對于時間跨度敏感的流量負載，如圖12(b)所示，狹義同期預測準確度明顯下降；而對于時間跨度不敏感的流量負載，如圖12(a)所示，狹義同期預測的準確度超過了廣義同期預測.這主要是由于在前者情形下，與廣義同期預測相比，狹義同期預測的流量負載時間序列抖動偏差變大，導致其預測誤差增大；而在后者情形下，狹義同期預測的由不同周相同工作日相同時隙組成的流量時間序列比廣義同期預測的由不同工作日相同時隙組成的流量時間序列更好地保留了流量相似性，因而具有更小的抖動，提高了預測準確度.

Fig. 12 Accuracy comparison among CP, GSP and SSP圖12 環期預測和同期預測的準確度比較

5 總 結

本文面向主干網提出了一種細粒度器件級功控機制，該機制依據流量負載大小動態調整網元器件功率狀態實現了節能，且在節能的同時兼顧用戶QoS需求的滿足，在提供QoS保證的前提下盡可能最大化節能收益.此外，本文還考慮了在功效和負載最差延遲之間以及在功效和緩沖區占用率之間的權衡問題，同時揭示了預測過估計和預測低估計、環期預測和同期預測以及擴展入口負載計數器的計數窗口對器件級功控機制的影響.仿真結果表明：本文提出的器件級功控機制能夠細粒度、動態和比例性地控制各網元功耗.

由于本文提出的機制是增補式的，并不需要“大刀闊斧”式地更換目前現有的基礎設施、網絡架構和網絡協議等而進行各個層面的全新設計，在實際部署中僅需要適當擴充和增添少許網絡功能模塊以及在現有網絡協議基礎上作相應修改即可，且機制依據的DPM和DVFS等功率調節技術以及ALR和LPI等節能策略也較為成熟，因此本文提出的機制具有實際可行性和可能性.在實際部署本文提出機制時，網絡運營商需要根據不同應用需求場景通過參考我們的實驗結果選取適當的緩沖區使用量警戒閾值使得節能與性能之間達到權衡或者側重于二者之一，同時根據不同的拓撲結構和歷史流量分布情況選擇合適的預測時隙獲取方式和計數器數目，嚴格避免低估計的發生，也盡量避免過估計的發生.

我們未來的工作將著重于探索端口速率調節方法對基于鏈路狀態的開放最短路徑優先路由算法等網絡級路由機制的影響以及兩者之間的協同交互，通過綜合運用器件級和網絡級節能機制，使網絡獲取更大的節能收益.