基于數據中心光網絡的節能虛擬網絡嵌入算法

聶嘉琪

(東北大學 計算機科學與工程學院， 沈陽 110169)

0 引 言

隨著通信技術的迅猛發展，以及新興網絡服務的出現，數據中心網絡(Data Center Networks，DCNs)中的流量呈指數型增長。彈性光網絡(Elastic Optical Networks，EONs)通過設置具有一系列光譜連續細粒度頻隙(Frequency Slots，FSs)的信道，為光學層中的光譜管理者提供了前所未有的靈活性[1-3]。EONs成為數據中心互連有前途的候選者。人們對互聯網需求的多樣化使網絡出現僵化問題。網絡虛擬化技術允許多個虛擬請求(Virtual Requests，VRs)共享底層物理網絡的資源，可實現物理資源的合理分配和管理。網絡虛擬化技術的核心問題是虛擬網絡嵌入(Virtual Network Embedding，VNE)。VNE可以分為兩個子問題：節點嵌入和鏈路嵌入[4]。

能耗問題有兩個來源：頻譜消耗和網絡中的硬件消耗。研究者對上述兩個部分均進行了研究。文獻[5]研究了嵌入EONs的虛擬光網絡的能量和頻譜效率的聯合優化問題；文獻[6]考慮了EONs中的能量感知虛擬光網絡嵌入問題；文獻[7]研究了基于正交頻分復用的軟件定義網絡跨數據中心EONs中受限于服務質量和物理要求的節能光收發器(Optical Transponder，OTP)配置問題。

基于上述嵌入和節能方法，針對網絡能耗問題，本文提出了基于匹配網絡資源的節能嵌入(Energy Efficient Embedding based on Matching Network Resources，3E-MNR)算法。

1 問題描述

1.1 基板網絡(Substrate Network，SN)

本文把數據中心光網絡(Data Center Optical Networks，DCONs)作為SN，用無向加權連通圖GS=(NS,ES)來描述，式中：NS為基板節點的集合；ES為基板鏈路的集合。對于一個SN節點nS∈NS，設c(nS)為節點的計算資源，b(eS)為基板鏈路的帶寬資源，eS∈ES為ES中的一條鏈路。圖1所示為一個擁有6個基板節點和8條鏈路的SN示意圖，圖中，方框內的數字為基板節點的計算資源，鏈路上的數字為鏈路的帶寬資源，橫線外的數字為節點間的距離。

圖1 SN示意圖

為了快速匹配節點，減少時間的復雜度，提出了節點匹配資源R(i)的概念：

式中，lS(i)為與節點i相連的鏈路。

1.2 VRs

VRs用無向加權連通圖GV=(NV,EV)來表示，式中：NV為虛擬節點的集合；EV為虛擬鏈路的集合。對于一個虛擬節點nV∈NV，設c(nV)為節點的計算資源需求，b(eV)為虛擬鏈路的帶寬資源，eV∈EV為ES中的一條鏈路。圖2所示為一個VRs的示意圖，圖中，方框內的數字為虛擬節點的計算資源需求，鏈路上的數字為鏈路的帶寬資源需求。

圖2 VRs示意圖

1.3 功耗模型

DCONs節點和鏈路示意圖如圖3所示，模塊主要由網際互連協議 (Internet Protocol，IP) 路由器、再生器、帶寬可變的光交叉連接器(Bandwidth Variable Optical Cross Connector，BV-OXC)和帶寬可變的OTP(Bandwidth Variable -OTP，BV-OTP)構成。各部分的功能總結如下：IP路由器在光電轉換之前/之后執行所有必需的電氣處理；再生器必要時再生光信號以保證傳輸質量；BV-OXC執行光信號交換和添加/刪除功能，根據請求建立容量恰當的傳輸光路，當客戶端產生的應用請求大小改變時，BV-OXC會適當地改變其交換窗口的大小從而改變光路的帶寬容量，繼而實現光路容量的靈活配置；BV-OTP包含光正交頻分復用發送機和光正交頻分復用接收機，用于生成和接收光正交頻分復用信號。發送模塊BV-OTP由3個主要部分組成：(1) 數字信號處理器；(2) 數/模轉換器；(3) 激光器和馬赫曾德爾調制器。而接收模塊與發送模塊相反。

圖3 DCONs節點和鏈路示意圖

在本文中，DCONs的整體能耗主要考慮數據中心、BV-OTP和再生器。數據中心的能耗PDC可描述為

式中：Pidle為在沒有流量負載的情況下，用于冷卻、照明和電源配置損耗的激活數據中心的閑置功耗；Pl為數據中心在最大流量負載下的比例功耗；ρ(0<ρ<1)為比例因子。

對于BV-OTP，其能耗Potp可描述為

式中：TR為傳輸速率；Poverhead為空閑功耗；η為比例參數。

對于再生器，其能耗Pre可描述為

式中：Pspare為空閑功耗；μ為比例參數；Pd為再生器在調制格式下，最大傳輸距離下的比例功耗。

因此，總能耗P可表示為

本文的目標是最小化總能耗。

2 啟發式算法

本文主要針對BV-OTP和再生器來設計啟發式算法，在VNE的過程中考慮整個網絡的能耗，根據節點匹配資源，為VRs選擇能耗最低的節點和鏈路完成嵌入。

2.1 基于節點匹配資源的節能嵌入算法

首先，計算SN和VRs節點匹配資源的大小，并將其按照降序排序，若SN節點之間或VRs節點之間的匹配資源大小相等，則將節點計算資源較大的排序在前，將排序好的SN和VRs節點分別放進集合中。接下來，按照集合中的順序為VRs的各個節點找到候選嵌入節點;按照鏈路的帶寬資源限制，為VRs找到候選鏈路。接著，根據路徑的長度選擇合適的調制格式，放置合適數量的OTP和再生器。最后，計算各個候選路徑的能耗，進而計算所有候選嵌入網絡的能耗，然后，比較所有候選嵌入的能耗，選擇能耗最低的候選方式完成嵌入。

值得注意的是，VRs節點選擇SN節點時，SN節點不僅要滿足VRs節點的計算資源限制，還要滿足與VRs節點相連的VRs鏈路的帶寬限制。一旦排序靠前的VRs節點被選定為候選節點，排序靠后的節點便不可再選擇。尋找候選鏈路時，按照廣度優先搜索(Breadth First Search，BFS)算法遍歷整個網絡。選擇調制格式的原則是：在不超過最大傳輸距離的情況下，選擇高的調制格式，若路徑長度等于調制格式的最大傳輸距離，則選擇更低一級的調制格式。3E-MNR算法的流程圖如圖4所示。

圖4 3E-MNR算法流程圖

偽代碼如下所示。

輸入： SN， VRs；

輸出：嵌入完成的SN；

1．初始化集合ps，pv，pq，m(i)，p(i)；

2．//尋找候選路徑

4． 計算SN節點的計算匹配資源RS(i)；

5． ifRS(i)=RS(j),i≠j

6． 按SN節點的計算資源降序排序；

7． else

8． 按SN節點的匹配網絡資源降序排序；

9． end if

10． 將排序結果放入ps中；

11．end for

13． 計算VRs節點的匹配資源RV(i)；

14． ifRV(i)=RV(j),i≠j

15． 按VRs節點的計算資源降序排序；

16． else

17． 按VRs節點的匹配網絡資源降序排序；

18． end if

19． 將排序結果放入pv中；

20．end for

21．//尋找候選鏈路

23． 按照pv中的順序從ps中尋找候選節點，放入m(i)中；

24． 根據m(i)中的VRs節點情況得到候選嵌入方式；

25．end for

26．do

27． 按照BFS算法為候選嵌入中的VRs找到候選路徑；

28．until 找到所有候選嵌入方式的路徑；

29．for 每一種候選嵌入的路徑

30． 計算路徑長度；

31． 根據路徑長度選擇調制格式；

32． 計算候選嵌入的網絡能耗，將網絡能耗存入p(i)；

33．end for

34．將p(i)中的數值按降序排序放入pq；

35．選擇pq中第一個數值所對應的候選嵌入完成嵌入。

2.2 基于節點匹配資源的節能嵌入算法舉例

為了進一步解釋3E-MNR算法的步驟，根據圖1和圖2來說明算法的過程。VRs節點的匹配資源和SN節點的匹配資源由式(1)計算，得到SN節點的順序為{D，C，B，F，E，A}，VRs節點的順序為{b，a，c}。根據計算資源和帶寬資源的約束，找到各VRs節點的候選節點為：b{F}，a{D，B}，c{A，E}，得到如圖5所示的4種候選嵌入方式。以候選嵌入方式4為例來說明剩余步驟。按照BFS算法找到VRs a-b的候選路徑為D-F，a-c的候選路徑為D-C-E。由圖1可知，D-F之間的距離為1 000 km，D-C-E之間的距離為1 100 km。表1給出了各調制格式的最大傳輸距離及OTP的能耗，都選擇正交相移鍵控(Quadrature Phase Shift Keying，QPSK)的調制格式，D-F的能耗為266.92 W，D-C-E的能耗為533.84 W，候選嵌入方式4的總能耗為800.76 W。比較4種候選嵌入方式的能耗，最后，選擇能耗最低的候選嵌入方式4完成嵌入。

圖5 候選嵌入方式

表1 各調制格式下的最大傳輸距離及OTP能耗

3 實驗結果與分析

本文將所提3E-MNR算法與兩種現有的基線算法：距離自適應(Distance-adaptive，DA)算法[8]和能源感知虛擬嵌入(Virtual Network Embedding Energy Aware Problem,VNE-EA)算法[9]進行對比。把擁有15個節點27條鏈路的National網絡和20個節點32條鏈路的ARPANet網絡作為SN，網絡拓撲如圖6所示。假設VRs服從泊松分布隨機到達，并且其生存時間遵循負指數分布。虛擬節點的數量是隨機生成的，范圍為[2，7]，具有統一分布的計算資源和帶寬資源需求，每個FSs寬度為12.5 GHz。VRs以先到先得的方式嵌入。

圖6 網絡拓撲圖

圖7所示為本文所提3E-MNR算法與兩種基線算法的總能耗對比圖。由圖可知，在兩種情況下，3E-MNR算法總能耗均隨著VRs數量的增加而增加，且總能耗總是低于兩種基線算法。在National網絡中，當網絡負載為40和100 Erl時，3E-MNR算法與VNE-EA算法相比總能耗平均降低了10.25%和8.25%。相比于DA算法，3E-MNR算法總能耗平均降低了14.38%和13.63%，在低網絡負載情況下，3E-MNR算法具有更好的性能。在高VRs數時，不同算法的總能耗差別較大。這是因為本文所提算法把VRs嵌入到了能耗最低的路徑中，而不僅僅是滿足資源需求的鏈路。

圖7 總能耗對比圖

圖8所示為不同算法在網絡負載為40 Erl時的運行時間對比圖。由圖可知，隨著網絡負載的增加，3E-MNR算法的運行時間均少于VNE-EA算法，但多于DA算法。圖8(a)中，3E-MNR算法較VNE-EA算法運行時間大大減少。這是因為本文所提算法提出了節點匹配資源，在節點嵌入的階段同時考慮了虛擬節點相連鏈路的帶寬約束，大大減少了候選節點的數量。隨著負載的增加，兩者運行時間的差值也會越來越大。而對于DA算法來說，在嵌入時僅考慮距離來選擇合適的調制格式并分配資源，而不考慮其他因素，相對于3E-MNR算法來說要節省時間。在VRs數為35時，3E-MNR算法比VNE-EA算法運行時間在National和ARPANet網絡中分別降低了1.94和2.00 s。

圖8 運行時間對比圖

圖9所示為本文所提3E-MNR算法與基線算法在不同網絡負載情況下OTP能耗方面的比較。由圖可知，在VRs數較少時，兩種算法性能相差不大，隨著VRs數的增多，兩者的差距變得越來越大。這是因為在VRs數較少時，VNE-EA算法在節點計算資源和能量守恒等方面進行約束，當VRs數變大時，算法約束性變差，能耗增量變大。如圖9所示，在VRs數為35時，3E-MNR算法較VNE-EA算法在網絡負載為40和100 Erl時在Nationl網絡(ARPANet網絡)中OTP能耗分別減少了8%(6%)和27%(22%)。

圖9 OTP能耗對比圖

National和ARPANet網絡中，不同方法在不同網絡負載下的阻塞率如圖10所示。在兩種SN拓撲上，所有算法的阻塞率都隨著VRs數的增加而增加，但本文所提算法的阻塞率均低于DA和VNE-EA算法。DA算法在路徑選擇時僅選擇使用最少FSs的路徑，而不考慮路徑上FSs的使用情況。3E-MNR算法在鏈路嵌入時，考慮了帶寬資源的限制，可以在相同的鏈路上傳輸更多的請求。由于網絡資源的有限性，在高VRs數的情況下，阻塞可能性的升高受到限制。

圖10 阻塞率對比圖

4 結束語

本文探索了在節省DCONs能耗的同時保持對請求較高接受率的問題。為了節省DCONs的能耗并有效利用資源，本文提出了3E-MNR算法。為了減少時間復雜度，提出了節點匹配資源的概念，快速匹配虛擬節點的候選節點。仿真結果表明，在總能耗方面，本文所提3E-MNR算法要低于基線算法DA和VNE-EA，且保持了較低的阻塞概率。在運行時間方面也實現了一定的權衡。