基于數(shù)據(jù)中心光網(wǎng)絡(luò)的節(jié)能虛擬網(wǎng)絡(luò)嵌入算法

聶嘉琪

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 沈陽(yáng) 110169)

0 引 言

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

能耗問(wèn)題有兩個(gè)來(lái)源：頻譜消耗和網(wǎng)絡(luò)中的硬件消耗。研究者對(duì)上述兩個(gè)部分均進(jìn)行了研究。文獻(xiàn)[5]研究了嵌入EONs的虛擬光網(wǎng)絡(luò)的能量和頻譜效率的聯(lián)合優(yōu)化問(wèn)題；文獻(xiàn)[6]考慮了EONs中的能量感知虛擬光網(wǎng)絡(luò)嵌入問(wèn)題；文獻(xiàn)[7]研究了基于正交頻分復(fù)用的軟件定義網(wǎng)絡(luò)跨數(shù)據(jù)中心EONs中受限于服務(wù)質(zhì)量和物理要求的節(jié)能光收發(fā)器(Optical Transponder，OTP)配置問(wèn)題。

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

1 問(wèn)題描述

1.1 基板網(wǎng)絡(luò)(Substrate Network，SN)

本文把數(shù)據(jù)中心光網(wǎng)絡(luò)(Data Center Optical Networks，DCONs)作為SN，用無(wú)向加權(quán)連通圖GS=(NS,ES)來(lái)描述，式中：NS為基板節(jié)點(diǎn)的集合；ES為基板鏈路的集合。對(duì)于一個(gè)SN節(jié)點(diǎn)nS∈NS，設(shè)c(nS)為節(jié)點(diǎn)的計(jì)算資源，b(eS)為基板鏈路的帶寬資源，eS∈ES為ES中的一條鏈路。圖1所示為一個(gè)擁有6個(gè)基板節(jié)點(diǎn)和8條鏈路的SN示意圖，圖中，方框內(nèi)的數(shù)字為基板節(jié)點(diǎn)的計(jì)算資源，鏈路上的數(shù)字為鏈路的帶寬資源，橫線(xiàn)外的數(shù)字為節(jié)點(diǎn)間的距離。

圖1 SN示意圖

為了快速匹配節(jié)點(diǎn)，減少時(shí)間的復(fù)雜度，提出了節(jié)點(diǎn)匹配資源R(i)的概念：

式中，lS(i)為與節(jié)點(diǎn)i相連的鏈路。

1.2 VRs

VRs用無(wú)向加權(quán)連通圖GV=(NV,EV)來(lái)表示，式中：NV為虛擬節(jié)點(diǎn)的集合；EV為虛擬鏈路的集合。對(duì)于一個(gè)虛擬節(jié)點(diǎn)nV∈NV，設(shè)c(nV)為節(jié)點(diǎn)的計(jì)算資源需求，b(eV)為虛擬鏈路的帶寬資源，eV∈EV為ES中的一條鏈路。圖2所示為一個(gè)VRs的示意圖，圖中，方框內(nèi)的數(shù)字為虛擬節(jié)點(diǎn)的計(jì)算資源需求，鏈路上的數(shù)字為鏈路的帶寬資源需求。

圖2 VRs示意圖

1.3 功耗模型

DCONs節(jié)點(diǎn)和鏈路示意圖如圖3所示，模塊主要由網(wǎng)際互連協(xié)議 (Internet Protocol，IP) 路由器、再生器、帶寬可變的光交叉連接器(Bandwidth Variable Optical Cross Connector，BV-OXC)和帶寬可變的OTP(Bandwidth Variable -OTP，BV-OTP)構(gòu)成。各部分的功能總結(jié)如下：IP路由器在光電轉(zhuǎn)換之前/之后執(zhí)行所有必需的電氣處理；再生器必要時(shí)再生光信號(hào)以保證傳輸質(zhì)量；BV-OXC執(zhí)行光信號(hào)交換和添加/刪除功能，根據(jù)請(qǐng)求建立容量恰當(dāng)?shù)膫鬏敼饴罚?dāng)客戶(hù)端產(chǎn)生的應(yīng)用請(qǐng)求大小改變時(shí)，BV-OXC會(huì)適當(dāng)?shù)馗淖兤浣粨Q窗口的大小從而改變光路的帶寬容量，繼而實(shí)現(xiàn)光路容量的靈活配置；BV-OTP包含光正交頻分復(fù)用發(fā)送機(jī)和光正交頻分復(fù)用接收機(jī)，用于生成和接收光正交頻分復(fù)用信號(hào)。發(fā)送模塊BV-OTP由3個(gè)主要部分組成：(1) 數(shù)字信號(hào)處理器；(2) 數(shù)/模轉(zhuǎn)換器；(3) 激光器和馬赫曾德?tīng)栒{(diào)制器。而接收模塊與發(fā)送模塊相反。

圖3 DCONs節(jié)點(diǎn)和鏈路示意圖

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

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

對(duì)于BV-OTP，其能耗Potp可描述為

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

對(duì)于再生器，其能耗Pre可描述為

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

因此，總能耗P可表示為

本文的目標(biāo)是最小化總能耗。

2 啟發(fā)式算法

本文主要針對(duì)BV-OTP和再生器來(lái)設(shè)計(jì)啟發(fā)式算法，在VNE的過(guò)程中考慮整個(gè)網(wǎng)絡(luò)的能耗，根據(jù)節(jié)點(diǎn)匹配資源，為VRs選擇能耗最低的節(jié)點(diǎn)和鏈路完成嵌入。

2.1 基于節(jié)點(diǎn)匹配資源的節(jié)能嵌入算法

首先，計(jì)算SN和VRs節(jié)點(diǎn)匹配資源的大小，并將其按照降序排序，若SN節(jié)點(diǎn)之間或VRs節(jié)點(diǎn)之間的匹配資源大小相等，則將節(jié)點(diǎn)計(jì)算資源較大的排序在前，將排序好的SN和VRs節(jié)點(diǎn)分別放進(jìn)集合中。接下來(lái)，按照集合中的順序?yàn)閂Rs的各個(gè)節(jié)點(diǎn)找到候選嵌入節(jié)點(diǎn);按照鏈路的帶寬資源限制，為VRs找到候選鏈路。接著，根據(jù)路徑的長(zhǎng)度選擇合適的調(diào)制格式，放置合適數(shù)量的OTP和再生器。最后，計(jì)算各個(gè)候選路徑的能耗，進(jìn)而計(jì)算所有候選嵌入網(wǎng)絡(luò)的能耗，然后，比較所有候選嵌入的能耗，選擇能耗最低的候選方式完成嵌入。

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

圖4 3E-MNR算法流程圖

偽代碼如下所示。

輸入： SN， VRs；

輸出：嵌入完成的SN；

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

2．//尋找候選路徑

4． 計(jì)算SN節(jié)點(diǎn)的計(jì)算匹配資源RS(i)；

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

6． 按SN節(jié)點(diǎn)的計(jì)算資源降序排序；

7． else

8． 按SN節(jié)點(diǎn)的匹配網(wǎng)絡(luò)資源降序排序；

9． end if

10． 將排序結(jié)果放入ps中；

11．end for

13． 計(jì)算VRs節(jié)點(diǎn)的匹配資源RV(i)；

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

15． 按VRs節(jié)點(diǎn)的計(jì)算資源降序排序；

16． else

17． 按VRs節(jié)點(diǎn)的匹配網(wǎng)絡(luò)資源降序排序；

18． end if

19． 將排序結(jié)果放入pv中；

20．end for

21．//尋找候選鏈路

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

24． 根據(jù)m(i)中的VRs節(jié)點(diǎn)情況得到候選嵌入方式；

25．end for

26．do

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

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

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

30． 計(jì)算路徑長(zhǎng)度；

31． 根據(jù)路徑長(zhǎng)度選擇調(diào)制格式；

32． 計(jì)算候選嵌入的網(wǎng)絡(luò)能耗，將網(wǎng)絡(luò)能耗存入p(i)；

33．end for

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

35．選擇pq中第一個(gè)數(shù)值所對(duì)應(yīng)的候選嵌入完成嵌入。

2.2 基于節(jié)點(diǎn)匹配資源的節(jié)能嵌入算法舉例

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

圖5 候選嵌入方式

表1 各調(diào)制格式下的最大傳輸距離及OTP能耗

3 實(shí)驗(yàn)結(jié)果與分析

本文將所提3E-MNR算法與兩種現(xiàn)有的基線(xiàn)算法：距離自適應(yīng)(Distance-adaptive，DA)算法[8]和能源感知虛擬嵌入(Virtual Network Embedding Energy Aware Problem,VNE-EA)算法[9]進(jìn)行對(duì)比。把擁有15個(gè)節(jié)點(diǎn)27條鏈路的National網(wǎng)絡(luò)和20個(gè)節(jié)點(diǎn)32條鏈路的ARPANet網(wǎng)絡(luò)作為SN，網(wǎng)絡(luò)拓?fù)淙鐖D6所示。假設(shè)VRs服從泊松分布隨機(jī)到達(dá)，并且其生存時(shí)間遵循負(fù)指數(shù)分布。虛擬節(jié)點(diǎn)的數(shù)量是隨機(jī)生成的，范圍為[2，7]，具有統(tǒng)一分布的計(jì)算資源和帶寬資源需求，每個(gè)FSs寬度為12.5 GHz。VRs以先到先得的方式嵌入。

圖6 網(wǎng)絡(luò)拓?fù)鋱D

圖7所示為本文所提3E-MNR算法與兩種基線(xiàn)算法的總能耗對(duì)比圖。由圖可知，在兩種情況下，3E-MNR算法總能耗均隨著VRs數(shù)量的增加而增加，且總能耗總是低于兩種基線(xiàn)算法。在National網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)負(fù)載為40和100 Erl時(shí)，3E-MNR算法與VNE-EA算法相比總能耗平均降低了10.25%和8.25%。相比于DA算法，3E-MNR算法總能耗平均降低了14.38%和13.63%，在低網(wǎng)絡(luò)負(fù)載情況下，3E-MNR算法具有更好的性能。在高VRs數(shù)時(shí)，不同算法的總能耗差別較大。這是因?yàn)楸疚乃崴惴ò裋Rs嵌入到了能耗最低的路徑中，而不僅僅是滿(mǎn)足資源需求的鏈路。

圖7 總能耗對(duì)比圖

圖8所示為不同算法在網(wǎng)絡(luò)負(fù)載為40 Erl時(shí)的運(yùn)行時(shí)間對(duì)比圖。由圖可知，隨著網(wǎng)絡(luò)負(fù)載的增加，3E-MNR算法的運(yùn)行時(shí)間均少于VNE-EA算法，但多于DA算法。圖8(a)中，3E-MNR算法較VNE-EA算法運(yùn)行時(shí)間大大減少。這是因?yàn)楸疚乃崴惴ㄌ岢隽斯?jié)點(diǎn)匹配資源，在節(jié)點(diǎn)嵌入的階段同時(shí)考慮了虛擬節(jié)點(diǎn)相連鏈路的帶寬約束，大大減少了候選節(jié)點(diǎn)的數(shù)量。隨著負(fù)載的增加，兩者運(yùn)行時(shí)間的差值也會(huì)越來(lái)越大。而對(duì)于DA算法來(lái)說(shuō)，在嵌入時(shí)僅考慮距離來(lái)選擇合適的調(diào)制格式并分配資源，而不考慮其他因素，相對(duì)于3E-MNR算法來(lái)說(shuō)要節(jié)省時(shí)間。在VRs數(shù)為35時(shí)，3E-MNR算法比VNE-EA算法運(yùn)行時(shí)間在National和ARPANet網(wǎng)絡(luò)中分別降低了1.94和2.00 s。

圖8 運(yùn)行時(shí)間對(duì)比圖

圖9所示為本文所提3E-MNR算法與基線(xiàn)算法在不同網(wǎng)絡(luò)負(fù)載情況下OTP能耗方面的比較。由圖可知，在VRs數(shù)較少時(shí)，兩種算法性能相差不大，隨著VRs數(shù)的增多，兩者的差距變得越來(lái)越大。這是因?yàn)樵赩Rs數(shù)較少時(shí)，VNE-EA算法在節(jié)點(diǎn)計(jì)算資源和能量守恒等方面進(jìn)行約束，當(dāng)VRs數(shù)變大時(shí)，算法約束性變差，能耗增量變大。如圖9所示，在VRs數(shù)為35時(shí)，3E-MNR算法較VNE-EA算法在網(wǎng)絡(luò)負(fù)載為40和100 Erl時(shí)在Nationl網(wǎng)絡(luò)(ARPANet網(wǎng)絡(luò))中OTP能耗分別減少了8%(6%)和27%(22%)。

圖9 OTP能耗對(duì)比圖

National和ARPANet網(wǎng)絡(luò)中，不同方法在不同網(wǎng)絡(luò)負(fù)載下的阻塞率如圖10所示。在兩種SN拓?fù)渖希兴惴ǖ淖枞识茧S著VRs數(shù)的增加而增加，但本文所提算法的阻塞率均低于DA和VNE-EA算法。DA算法在路徑選擇時(shí)僅選擇使用最少FSs的路徑，而不考慮路徑上FSs的使用情況。3E-MNR算法在鏈路嵌入時(shí)，考慮了帶寬資源的限制，可以在相同的鏈路上傳輸更多的請(qǐng)求。由于網(wǎng)絡(luò)資源的有限性，在高VRs數(shù)的情況下，阻塞可能性的升高受到限制。

圖10 阻塞率對(duì)比圖

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

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