劉認(rèn)倫，楊龍祥

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

虛擬網(wǎng)絡(luò)映射節(jié)能算法研究

劉認(rèn)倫，楊龍祥

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

虛擬網(wǎng)絡(luò)映射是一種解決未來互聯(lián)網(wǎng)發(fā)展問題的關(guān)鍵技術(shù)，該技術(shù)能夠使多個(gè)異構(gòu)的虛擬網(wǎng)絡(luò)共存于同一個(gè)物理網(wǎng)絡(luò)，共享底層資源。但目前的虛擬網(wǎng)絡(luò)映射算法大多是針對(duì)網(wǎng)絡(luò)負(fù)載較高的情況，且多屬啟發(fā)式的映射算法，在網(wǎng)絡(luò)負(fù)載較低時(shí)，虛擬網(wǎng)絡(luò)映射可能引起底層資源不能被充分利用，導(dǎo)致網(wǎng)絡(luò)能耗的浪費(fèi)。隨著大規(guī)模網(wǎng)絡(luò)的發(fā)展，底層網(wǎng)絡(luò)設(shè)備的能耗問題越來越受到關(guān)注。虛擬網(wǎng)絡(luò)映射節(jié)能算法，通過對(duì)底層網(wǎng)絡(luò)資源的整合，可保證在不影響正常通信的情況下，有效地解決虛擬網(wǎng)絡(luò)映射過程中的能耗浪費(fèi)問題?；诖?，主要對(duì)虛擬網(wǎng)絡(luò)映射的節(jié)能算法進(jìn)行調(diào)查研究，對(duì)虛擬網(wǎng)絡(luò)中的節(jié)能問題進(jìn)行了重點(diǎn)描述，歸納了典型的能耗模型，分析了典型算法的映射過程以及指標(biāo)，并討論了未來的研究方向。

虛擬網(wǎng)絡(luò)映射；節(jié)能；資源整合；能耗模型

0 引 言

作為未來網(wǎng)絡(luò)的一項(xiàng)重要技術(shù)，網(wǎng)絡(luò)虛擬化技術(shù)能夠克服現(xiàn)在因特網(wǎng)中的一些困難。網(wǎng)絡(luò)虛擬化最顯著的優(yōu)點(diǎn)是能夠使多個(gè)異構(gòu)的虛擬網(wǎng)絡(luò)共享同一實(shí)體，即多個(gè)異構(gòu)的虛擬網(wǎng)絡(luò)可以共存于一個(gè)底層網(wǎng)絡(luò)中。將多個(gè)虛擬網(wǎng)絡(luò)映射到同一個(gè)底層網(wǎng)絡(luò)的問題通常被稱為虛擬網(wǎng)絡(luò)映射(VNE)。

虛擬網(wǎng)絡(luò)映射主要解決節(jié)點(diǎn)與鏈路的資源分配問題，因此，虛擬網(wǎng)絡(luò)映射又分為兩個(gè)子問題：虛擬節(jié)點(diǎn)映射(VoNM)和虛擬鏈路映射(VLiM)。虛擬節(jié)點(diǎn)映射會(huì)影響虛擬鏈路映射，所以，在將虛擬網(wǎng)絡(luò)請(qǐng)求映射到底層網(wǎng)絡(luò)時(shí)，首先要解決虛擬節(jié)點(diǎn)映射，然后再解決虛擬鏈路映射。

傳統(tǒng)的虛擬網(wǎng)絡(luò)映射將重點(diǎn)放在網(wǎng)絡(luò)的收益成本上，即盡可能多地將虛擬網(wǎng)絡(luò)映射到底層網(wǎng)絡(luò)上。然而，現(xiàn)有的網(wǎng)絡(luò)都是為峰值負(fù)載而設(shè)計(jì)，即使面臨高的網(wǎng)絡(luò)請(qǐng)求時(shí)仍然過度分配資源，以確保正常運(yùn)行。因此，這種最大限度地利用資源的方式會(huì)引起過高的資源利用不足和不必要的能量消耗。隨著近年來人們環(huán)保意識(shí)的提高，生產(chǎn)過程中能耗以及碳排放越來越受到研究者的關(guān)注。根據(jù)文獻(xiàn)[1]，在大型ISP的骨干網(wǎng)中，鏈路利用率僅有30%～40%。因此，綠色網(wǎng)絡(luò)這一課題引起了研究者們的興趣。

虛擬網(wǎng)絡(luò)映射的綠色網(wǎng)絡(luò)課題即節(jié)能問題，旨在不影響網(wǎng)絡(luò)性能的前提下，盡可能少地使用底層網(wǎng)絡(luò)資源或是盡可能使用能耗低的底層網(wǎng)絡(luò)資源映射虛擬網(wǎng)絡(luò)。

文中主要針對(duì)虛擬網(wǎng)絡(luò)映射的節(jié)能算法和方案進(jìn)行研究，重點(diǎn)介紹了虛擬網(wǎng)絡(luò)映射節(jié)能算法的基本問題定義，節(jié)能的數(shù)學(xué)模型，典型算法的映射過程和優(yōu)化策略，以及映射的性能指標(biāo)。分析了目前節(jié)能方案中尚未解決的問題，對(duì)未來的工作進(jìn)行了展望。

1 虛擬網(wǎng)絡(luò)映射節(jié)能算法

1.1 問題描述

虛擬網(wǎng)絡(luò)映射節(jié)能算法可以根據(jù)底層網(wǎng)絡(luò)是否以實(shí)際資源為模型稱為能量感知型VNE(Energy-aware VNE)或能量效率型VNE(Energy-efficient VNE)。以能量感知型VNE為例，描述虛擬網(wǎng)絡(luò)映射中的節(jié)能問題。非能量感知的虛擬網(wǎng)絡(luò)映射算法不考慮網(wǎng)絡(luò)中閑置的節(jié)點(diǎn)和鏈路的能耗，所以造成網(wǎng)絡(luò)能耗的浪費(fèi)。為了解決這個(gè)問題并優(yōu)化網(wǎng)絡(luò)資源配置，能量感知的虛擬網(wǎng)絡(luò)映射節(jié)能算法把目標(biāo)定為使用網(wǎng)絡(luò)中最少的資源為現(xiàn)有虛擬網(wǎng)絡(luò)請(qǐng)求分配資源，關(guān)閉網(wǎng)絡(luò)中未被映射的節(jié)點(diǎn)與鏈路。如圖1所示，非能量感知VNE并未充分利用節(jié)點(diǎn)與鏈路中的資源，并且閑置的節(jié)點(diǎn)和鏈路仍有能耗；而能量感知的VNE通過資源整合重新分配資源，使節(jié)點(diǎn)和鏈路都能得到充分利用，并關(guān)閉未被映射的節(jié)點(diǎn)和鏈路，使整個(gè)網(wǎng)絡(luò)的能耗最小。

圖1 非能量感知的VNE(左)與能量感知的VNE(右)

1.2 能耗模型

根據(jù)不同的節(jié)能目的，需要為底層網(wǎng)絡(luò)建立不同的數(shù)學(xué)模型。VNE節(jié)能算法的最終目的是使底層網(wǎng)絡(luò)能耗盡可能小，因此，以網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路能耗直接建模是最合理的方法，實(shí)際中可能會(huì)遇到CO2排放、電力成本等問題。于是，提出一些考慮這些問題的VNE節(jié)能算法，把這些算法歸納到一類中進(jìn)行陳述。

(1)節(jié)點(diǎn)與鏈路的簡單模型。

文獻(xiàn)[2]中使用只考慮節(jié)點(diǎn)與鏈路數(shù)量的模型，是最早提出的一種VNE節(jié)能能耗模型。這種算法將底層網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路資源視為一個(gè)點(diǎn)和一條線，并假設(shè)各個(gè)節(jié)點(diǎn)、各條鏈路的能耗相等，這樣，底層網(wǎng)絡(luò)的能耗模型簡化，網(wǎng)絡(luò)總能耗只需算出節(jié)點(diǎn)和鏈路的數(shù)量或是其數(shù)量的加權(quán)值。但由于這種模型過于簡單，尤其是節(jié)點(diǎn)能耗模型與實(shí)際的能耗方式不同，因而其作用有限，在綠色節(jié)能課題研究初期，此模型使用較多，例如文獻(xiàn)[3-4]。

(2)節(jié)點(diǎn)與鏈路的能耗模型。

這種模型考慮實(shí)際中節(jié)點(diǎn)和鏈路的能耗特點(diǎn)，是目前課題研究中使用較為廣泛的一種模型。一種典型的方法是將節(jié)點(diǎn)和鏈路能耗分為基礎(chǔ)能耗和維持虛擬網(wǎng)絡(luò)的能耗[5]。這種模型考慮底層節(jié)點(diǎn)CPU使用率同節(jié)點(diǎn)能耗呈線性的特點(diǎn)以及底層鏈路的帶寬使用率和鏈路長度同鏈路能耗呈線性的特點(diǎn)，將這類能耗定義為維持虛擬網(wǎng)絡(luò)的能耗。并且節(jié)點(diǎn)可以根據(jù)需要進(jìn)行分類，文獻(xiàn)[6]中將節(jié)點(diǎn)分為兩類：有虛擬節(jié)點(diǎn)映射到的底層節(jié)點(diǎn)(host node，維持節(jié)點(diǎn))和只有虛擬鏈路經(jīng)過的底層節(jié)點(diǎn)(forwarding node，轉(zhuǎn)發(fā)節(jié)點(diǎn))。這種模型雖然較為簡單，但很實(shí)用，以此模型進(jìn)行的研究也較多。文獻(xiàn)[7]中給出了應(yīng)用此類模型的四個(gè)定理，闡述了節(jié)點(diǎn)能耗、鏈路能耗和全局網(wǎng)絡(luò)能耗的關(guān)系以及計(jì)算方法。另一典型模型是考慮實(shí)際網(wǎng)絡(luò)中的器件能耗，這種模型常用于云網(wǎng)絡(luò)、數(shù)據(jù)中心等現(xiàn)實(shí)場景[8-10]。

(3)其他模型。

文獻(xiàn)[6]提出了一種以一天的電力價(jià)格為目標(biāo)函數(shù)的模型，需要考慮不同時(shí)段、不同區(qū)域的電價(jià)的變化。另外一種較為少見的模型在文獻(xiàn)[11]中提出，這種模型以底層網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的CO2排放量為目標(biāo)函數(shù)，當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求到達(dá)時(shí)，優(yōu)先為其分配CO2排放少的節(jié)點(diǎn)和鏈路資源。

1.3 節(jié)能方法的映射過程

底層網(wǎng)絡(luò)中，能耗的主要來源只有兩個(gè)：節(jié)點(diǎn)和鏈路。因此，底層網(wǎng)絡(luò)節(jié)能的方向主要在節(jié)點(diǎn)和鏈路上。節(jié)能的方法主要有兩種：節(jié)點(diǎn)節(jié)能和鏈路節(jié)能。為了區(qū)別底層網(wǎng)絡(luò)中被映射的資源和未被映射的資源，所有的能耗模型都會(huì)為節(jié)點(diǎn)和鏈路設(shè)定兩種狀態(tài)：喚醒和休眠。當(dāng)節(jié)點(diǎn)或者鏈路被映射，則此節(jié)點(diǎn)或鏈路處于喚醒狀態(tài)；反之，處于休眠狀態(tài)。并且，一個(gè)節(jié)點(diǎn)休眠時(shí)，與這個(gè)節(jié)點(diǎn)直接相連的所有鏈路也被迫休眠。因此，節(jié)點(diǎn)休眠的條件高于鏈路。

(1)節(jié)點(diǎn)節(jié)能方法的映射過程。

節(jié)點(diǎn)節(jié)能方法主要依靠節(jié)點(diǎn)休眠實(shí)現(xiàn)。在上文中提到節(jié)點(diǎn)休眠會(huì)導(dǎo)致鏈路被迫休眠，根據(jù)文獻(xiàn)[12]，底層網(wǎng)絡(luò)中能耗較高的是節(jié)點(diǎn)，相對(duì)鏈路休眠，關(guān)閉節(jié)點(diǎn)能夠節(jié)省更多的能量。而且，節(jié)點(diǎn)映射過程必然影響鏈路映射過程。文獻(xiàn)[3]中給出了一種在選取休眠節(jié)點(diǎn)后，如何尋找合理的鏈路的可行方案：由于鏈路能耗與路徑長度有關(guān)，所以在選定節(jié)點(diǎn)后，鏈路的選取應(yīng)遵循兩個(gè)原則：一是路徑最短；二是鏈路已用。找不到已用鏈路時(shí)遵循路徑最短原則?？紤]到節(jié)點(diǎn)映射先于鏈路，因此節(jié)能算法中少有只考慮優(yōu)化節(jié)點(diǎn)映射的節(jié)能方案。因此，將這類算法歸納到節(jié)點(diǎn)節(jié)能方法中。

作為第一個(gè)討論虛擬網(wǎng)絡(luò)映射節(jié)能的算法，文獻(xiàn)[2，13-16]分別給出了一種典型的節(jié)能方法。研究者假設(shè)所有的節(jié)點(diǎn)能耗相同、容量相等，所有的鏈路能耗相同、帶寬相等，即使用簡單的能耗模型。在映射第一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的第一個(gè)節(jié)點(diǎn)時(shí)，隨機(jī)選取節(jié)點(diǎn)映射，依據(jù)最小路徑選取其他節(jié)點(diǎn)，并且要保證對(duì)同一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求中的節(jié)點(diǎn)不能同時(shí)映射到同一個(gè)底層節(jié)點(diǎn)上。連在映射后繼到達(dá)的虛擬網(wǎng)絡(luò)請(qǐng)求時(shí)，則盡量使用已經(jīng)使用過的節(jié)點(diǎn)。由于這個(gè)算法中對(duì)鏈路帶寬的約束要求不高，所以約束主要來自于節(jié)點(diǎn)，所以這是一種典型的節(jié)點(diǎn)節(jié)能算法。

Sen Su等在文獻(xiàn)[5-6]中細(xì)化了節(jié)點(diǎn)和鏈路的能耗，給出了一種節(jié)點(diǎn)和鏈路分別依據(jù)CPU和帶寬使用率計(jì)算能耗的模型。并且在文獻(xiàn)[5]中，研究者提出節(jié)點(diǎn)在映射過程中必須考慮虛擬節(jié)點(diǎn)和底層節(jié)點(diǎn)的距離因素，如果單純地將虛擬節(jié)點(diǎn)映射到底層節(jié)點(diǎn)上，可能會(huì)出現(xiàn)一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的所有虛擬節(jié)點(diǎn)映射到同一個(gè)底層節(jié)點(diǎn)上的狀況，這樣一來，映射看似變得簡單了，而且不需要鏈路映射過程，數(shù)據(jù)的傳輸和交換完全可以在同一個(gè)底層節(jié)點(diǎn)中完成。但是，考慮到節(jié)點(diǎn)的距離，這種方案在實(shí)際中是不可行的。另外，研究者將節(jié)點(diǎn)進(jìn)行了分類，認(rèn)為底層網(wǎng)絡(luò)中的節(jié)點(diǎn)可以分為主節(jié)點(diǎn)(host node)和路由節(jié)點(diǎn)(router node)，見圖2。其中，主節(jié)點(diǎn)在網(wǎng)絡(luò)中只負(fù)責(zé)虛擬節(jié)點(diǎn)的映射，而路由節(jié)點(diǎn)不負(fù)責(zé)映射虛擬節(jié)點(diǎn)，只負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)(這樣的節(jié)點(diǎn)也稱為跳(hop))。在映射時(shí)，算法也遵循最短路徑和優(yōu)先已用資源的原則。但在將虛擬節(jié)點(diǎn)映射到主節(jié)點(diǎn)上時(shí)，應(yīng)考慮與主節(jié)點(diǎn)間的距離。

圖2 主節(jié)點(diǎn)與路由節(jié)點(diǎn)

即便是在過度分配資源的網(wǎng)絡(luò)負(fù)載條件下，也有可能是有個(gè)別的節(jié)點(diǎn)或鏈路未被使用到，將這樣的節(jié)點(diǎn)或鏈路休眠并不能滿足節(jié)能的需要。休眠節(jié)點(diǎn)是必要的，但達(dá)到節(jié)能的目的，必須優(yōu)化資源分配，盡可能少地使用節(jié)點(diǎn)和鏈路。對(duì)于底層節(jié)點(diǎn)而言，最主要的資源是CPU，要使虛擬節(jié)點(diǎn)充分利用CPU，則需要盡可能多地將虛擬節(jié)點(diǎn)映射到一個(gè)底層節(jié)點(diǎn)上?？紤]到這點(diǎn)，文獻(xiàn)[6]給出了一種底層節(jié)點(diǎn)的排序方法，以獲得最大CPU利用率。研究者假設(shè)每個(gè)底層節(jié)點(diǎn)的CPU資源相等，在首次映射請(qǐng)求時(shí)，隨機(jī)選取底層節(jié)點(diǎn)分配資源。然后，根據(jù)各個(gè)節(jié)點(diǎn)剩余的資源從小到大進(jìn)行排序。為下一個(gè)請(qǐng)求分配資源時(shí)，從排序集合中按順序選取滿足映射條件的節(jié)點(diǎn)，被使用過的節(jié)點(diǎn)將優(yōu)先選取。當(dāng)請(qǐng)求的映射完成后，需要根據(jù)節(jié)點(diǎn)剩余資源重新排序。若有節(jié)點(diǎn)的資源被用盡，則將這個(gè)節(jié)點(diǎn)從排序集合中移除。這樣，底層節(jié)點(diǎn)的資源不僅得到了充分利用，而且減少了網(wǎng)絡(luò)中應(yīng)用到的底層節(jié)點(diǎn)數(shù)，從而節(jié)省了能量。

映射后的底層節(jié)點(diǎn)排序如圖3所示。

(2)鏈路節(jié)能方法的映射過程。

根據(jù)文獻(xiàn)[1]，鏈路節(jié)能的方法可以有鏈路休眠以及自適應(yīng)流量傳輸兩種。目前，自適應(yīng)流量傳輸尚未有研究者提出。鏈路的休眠條件相對(duì)節(jié)點(diǎn)要低，節(jié)點(diǎn)的休眠必須滿足與其直接相連的所有鏈路休眠，而鏈路休眠只要考慮是否有虛擬鏈路映射到自身?？紤]到節(jié)點(diǎn)在休眠時(shí)節(jié)點(diǎn)中的數(shù)據(jù)無法使用，從而造成通信中斷的狀況，文獻(xiàn)[17-19]提出以鏈路休眠實(shí)現(xiàn)節(jié)能的方案。

①可分割鏈路的鏈路休眠。

鏈路分割是指將一條虛擬鏈路按照其請(qǐng)求帶寬分成數(shù)條虛擬子鏈路，子鏈路帶寬總和與請(qǐng)求帶寬相等。文獻(xiàn)[17]提出了一種基于可分割鏈路的鏈路休眠算法，在網(wǎng)絡(luò)從高負(fù)載時(shí)段進(jìn)入低負(fù)載時(shí)段，一些鏈路的帶寬并不能得到充分利用，將網(wǎng)絡(luò)中帶寬占用率低的底層鏈路上的虛擬鏈路重新映射到帶寬占用率高的鏈路上，并使帶寬占用率低的鏈路休眠。帶寬占用率高的鏈路并不一定能夠滿足需要映射的虛擬鏈路帶寬需求，于是，將這條虛擬鏈路分割成兩條去映射，不僅使底層鏈路帶寬得到充分利用，且提高了映射成功率。

虛擬鏈路的分割映射如圖4所示。

然而，分割鏈路可能帶來通信延遲和數(shù)據(jù)包順序錯(cuò)亂。分割為多條虛擬子鏈路需要為其尋找多條可用路徑，這些路徑的長度不同，因此數(shù)據(jù)在路徑上傳輸?shù)臅r(shí)間也不同，從一個(gè)節(jié)點(diǎn)傳送數(shù)據(jù)到另一個(gè)節(jié)點(diǎn)，數(shù)據(jù)的到達(dá)時(shí)間以耗時(shí)最長的一條數(shù)據(jù)傳輸路徑為準(zhǔn)。另外，短路徑可能在時(shí)間t內(nèi)傳送了多個(gè)數(shù)據(jù)包，而同時(shí)長路徑上的數(shù)據(jù)可能還并未到達(dá)接收節(jié)點(diǎn)，造成數(shù)據(jù)包接受順序錯(cuò)亂。

②不可分割鏈路的鏈路休眠。

文獻(xiàn)[17-19]中均提出了不可分割鏈路的鏈路休眠方法。虛擬鏈路不可分割的好處是數(shù)據(jù)有序傳輸，通信延遲較短。但相比可分割鏈路，帶寬占用率低的底層鏈路在為其虛擬鏈路重新選擇映射路徑時(shí)，變得相對(duì)困難。由于鏈路能耗不僅與其帶寬使用率有關(guān)，還與鏈路自身長度有關(guān)，越長的鏈路能耗越大[5]，所以將鏈路映射到路徑距離短的鏈路上也是一種較好的節(jié)能策略。

1.4 優(yōu)化策略

由于VNE問題是NP困難的，考慮到VNE在大規(guī)模網(wǎng)絡(luò)中的應(yīng)用，相應(yīng)的優(yōu)化方法的尋找也變得費(fèi)時(shí)費(fèi)力。于是，提出了三種適用于不同情景的算法：

(1)精簡式算法(Exact solution)。

精簡式算法適合小規(guī)模網(wǎng)絡(luò)場景，尤其在節(jié)點(diǎn)與鏈路的簡單模型中(1.2節(jié))，有著較好的應(yīng)用。這種優(yōu)化算法的實(shí)現(xiàn)可以通過整數(shù)線性規(guī)劃(Integer Linear Programming)，文獻(xiàn)[2-4]中各自提出了一種混合整數(shù)規(guī)劃(Mixed Integer Programming)，旨在小規(guī)模的底層網(wǎng)絡(luò)中尋找到最少的節(jié)點(diǎn)和鏈路滿足虛擬網(wǎng)絡(luò)請(qǐng)求。由于整數(shù)線性規(guī)劃的NP困難性，精簡式算法可能引起指數(shù)式增長的執(zhí)行時(shí)間，然而，精簡式算法可以為啟發(fā)式的虛擬網(wǎng)絡(luò)映射算法提供最優(yōu)界(optimal bound)。

(2)啟發(fā)式算法(Heuristics solution)。

啟發(fā)式算法的提出，解決了在映射過程中算法執(zhí)行時(shí)間過長的問題。尤其在動(dòng)態(tài)的網(wǎng)絡(luò)中，如果一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的映射時(shí)間過長，將會(huì)影響下一個(gè)到達(dá)的虛擬網(wǎng)絡(luò)請(qǐng)求的映射，啟發(fā)式算法較短的執(zhí)行時(shí)間能夠比較好地克服這個(gè)問題。目前，采用啟發(fā)式算法的方案被廣泛應(yīng)用于研究中，文獻(xiàn)[6，13，16，20-22]均使用了啟發(fā)式算法進(jìn)行優(yōu)化。

在文獻(xiàn)[19]中，研究者分別提出了精簡式的二進(jìn)制整數(shù)線性規(guī)劃算法(Binary Integer Linear Programming，BILP)和啟發(fā)式算法。根據(jù)其仿真結(jié)果，在相同的底層網(wǎng)絡(luò)上運(yùn)行時(shí)，精簡式BILP算法的節(jié)能效果相對(duì)提出的啟發(fā)式算法要好，啟發(fā)式算法的運(yùn)行結(jié)果只能在網(wǎng)絡(luò)負(fù)載較低的時(shí)段逼近BILP，BILP為啟發(fā)式算法提供了節(jié)能上界。但是，BILP的運(yùn)行時(shí)間約為4 000 s，遠(yuǎn)大于啟發(fā)式算法(3 s)，從運(yùn)行時(shí)間上考慮，啟發(fā)式算法遠(yuǎn)好于精簡式。

然而，啟發(fā)式算法得到優(yōu)化結(jié)果僅僅是局部最優(yōu)，不是全局最優(yōu)。針對(duì)這一狀況，元啟發(fā)式算法被提出，旨在合理的時(shí)間范圍內(nèi)獲得比局部最優(yōu)更好的結(jié)果。

(3)元啟發(fā)式算法(Metaheuristics solution)。

在大規(guī)模網(wǎng)絡(luò)中，尋找解決VNE的優(yōu)化方法變得困難起來。精簡式算法只適用于中小規(guī)模網(wǎng)絡(luò)，而啟發(fā)式算法得到的結(jié)果只是局部最優(yōu)解。元啟發(fā)式算法的提出解決了這些問題。文獻(xiàn)[15]使用的貪婪隨機(jī)適應(yīng)性搜索過程(Greedy Randomized Adaptive Search Procedure，GRASP)通常包括兩個(gè)步驟：創(chuàng)建和本地搜索。創(chuàng)建階段需要?jiǎng)?chuàng)建出滿足所有約束條件的隨機(jī)方法；本地搜索負(fù)責(zé)尋找與初始方法相關(guān)的本地優(yōu)化方法。文獻(xiàn)[17]應(yīng)用的多目標(biāo)粒子群優(yōu)化算法，對(duì)粒子群優(yōu)化算法重新定義了一系列的參數(shù)，包括位置、速率、差集等，以更好地用于節(jié)能的目標(biāo)。文獻(xiàn)[23]則將蟻群優(yōu)化算法應(yīng)用到節(jié)能方案中。

1.5 映射性能指標(biāo)

節(jié)能算法的映射是否成功與節(jié)能效果是否滿足需求需要一系列的性能指標(biāo)做評(píng)判。這些性能指標(biāo)可以用于不同算法之間的對(duì)比。按照映射目的，將虛擬網(wǎng)絡(luò)節(jié)能算法映射的性能指標(biāo)分為以下幾種：

1.5.1 能耗相關(guān)指標(biāo)

能耗指標(biāo)是虛擬網(wǎng)絡(luò)節(jié)能算法的最主要指標(biāo)。節(jié)能算法性能的優(yōu)劣，主要看在底層網(wǎng)絡(luò)中映射相同的虛擬網(wǎng)絡(luò)請(qǐng)求時(shí)，在不影響正常通信的情況下，哪一種算法能夠節(jié)省更多的能耗。

(1)節(jié)點(diǎn)能耗：底層網(wǎng)絡(luò)中所有激活的底層節(jié)點(diǎn)的能耗。根據(jù)能耗模型的不同，不同的底層節(jié)點(diǎn)能耗可能會(huì)有不同。例如維持節(jié)點(diǎn)和轉(zhuǎn)發(fā)節(jié)點(diǎn)，維持節(jié)點(diǎn)的能耗組成有基礎(chǔ)能耗和維持虛擬節(jié)點(diǎn)的能耗，而轉(zhuǎn)發(fā)節(jié)點(diǎn)只有基礎(chǔ)能耗。

(2)鏈路能耗：底層網(wǎng)絡(luò)中所有激活的底層鏈路的能耗。鏈路能耗可能與映射到這條鏈路上的虛擬鏈路所占帶寬有關(guān)或是與鏈路所連接的兩個(gè)節(jié)點(diǎn)間的距離有關(guān)。

(3)網(wǎng)絡(luò)能耗：底層網(wǎng)絡(luò)中所有激活的節(jié)點(diǎn)和鏈路的能耗。

(4)激活的節(jié)點(diǎn)數(shù)：底層網(wǎng)絡(luò)中所有激活的節(jié)點(diǎn)數(shù)量。在節(jié)能算法中，激活節(jié)點(diǎn)定義為虛擬網(wǎng)絡(luò)請(qǐng)求提供資源并維持其通信的節(jié)點(diǎn)，處于喚醒狀態(tài)；而休眠節(jié)點(diǎn)稱為非激活節(jié)點(diǎn)。

(5)激活的鏈路數(shù)：底層網(wǎng)絡(luò)中所有激活的鏈路數(shù)量。激活的鏈路定義為連接兩個(gè)激活節(jié)點(diǎn)并維持節(jié)點(diǎn)之間數(shù)據(jù)傳輸?shù)逆溌贰?/p>

(6)遷移能耗：在將一個(gè)已映射的虛擬網(wǎng)絡(luò)重新映射到另一個(gè)實(shí)體期間，維持原虛擬網(wǎng)絡(luò)通信的能耗。文獻(xiàn)[8]定義了遷移能耗的概念，將這種能耗應(yīng)用在對(duì)遷移敏感的網(wǎng)絡(luò)中。

(7)節(jié)點(diǎn)開啟能耗。一些算法認(rèn)為，在節(jié)點(diǎn)從休眠狀態(tài)激活轉(zhuǎn)為喚醒狀態(tài)時(shí)，需一個(gè)觸發(fā)節(jié)點(diǎn)開啟能耗，這個(gè)能耗區(qū)別于節(jié)點(diǎn)上的其他能耗并不可忽略。

1.5.2 服務(wù)質(zhì)量相關(guān)指標(biāo)

在虛擬網(wǎng)絡(luò)映射的節(jié)能算法中，對(duì)于服務(wù)質(zhì)量的要求只需要在網(wǎng)絡(luò)負(fù)載較低的時(shí)段進(jìn)行重新映射時(shí)不影響原有請(qǐng)求的正常通信或是在低負(fù)載時(shí)映射性能與非節(jié)能算法逼近。

(1)路徑長度：定義為一個(gè)虛擬網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)映射到底層節(jié)點(diǎn)上，連接這兩個(gè)節(jié)點(diǎn)間的物理鏈路數(shù)量。

(2)延遲：數(shù)據(jù)包從一個(gè)節(jié)點(diǎn)傳輸?shù)搅硪粋€(gè)節(jié)點(diǎn)需要的時(shí)間。

(3)使用率：映射虛擬網(wǎng)絡(luò)的底層資源量與底層網(wǎng)絡(luò)總資源量之比。

1.5.3 其他指標(biāo)

(1)算法運(yùn)行時(shí)間：虛擬網(wǎng)絡(luò)映射的完成時(shí)間，與映射的完成度和映射質(zhì)量是一對(duì)矛盾。

(2)虛擬網(wǎng)絡(luò)請(qǐng)求接收率：算法實(shí)際完成映射的虛擬網(wǎng)絡(luò)請(qǐng)求與全部的虛擬網(wǎng)絡(luò)請(qǐng)求之比。

(3)收益：虛擬網(wǎng)絡(luò)需要的虛擬資源總數(shù)。

2 結(jié)束語

虛擬網(wǎng)絡(luò)映射的綠色節(jié)能課題自興起以來，已得到較為深入與廣泛的開發(fā)與研究。在底層網(wǎng)絡(luò)中，能量消耗的載體是物理實(shí)體，所以節(jié)能的基本思想是盡可能少地使用底層資源實(shí)現(xiàn)映射。文中主要對(duì)虛擬網(wǎng)絡(luò)映射節(jié)能算法的研究及現(xiàn)狀進(jìn)行了調(diào)查。目前，虛擬網(wǎng)絡(luò)映射的節(jié)能模型的種類已較為全面，有些研究中的能耗模型已經(jīng)細(xì)化到網(wǎng)絡(luò)端口的能耗上。節(jié)能的方法有節(jié)點(diǎn)節(jié)能和鏈路節(jié)能，應(yīng)用于各種規(guī)模網(wǎng)絡(luò)的節(jié)能方案已有了較多進(jìn)展(例如應(yīng)用在小規(guī)模網(wǎng)絡(luò)的精簡型算法，應(yīng)用在中規(guī)模網(wǎng)絡(luò)的啟發(fā)式算法以及大規(guī)模網(wǎng)絡(luò)的元啟發(fā)式算法)；然而節(jié)點(diǎn)與鏈路結(jié)合的節(jié)能方案還未得到充分研究。映射的性能指標(biāo)也較為完備，能量效率的節(jié)能研究中也細(xì)化到了網(wǎng)絡(luò)元件上。

日益嚴(yán)重的碳排放問題和能源危機(jī)，使得虛擬網(wǎng)絡(luò)映射節(jié)能算法越來越受到重視，亦得到充分研究。目前，仍有如下問題和方向有待進(jìn)一步研究：

(1)節(jié)點(diǎn)休眠和鏈路分割結(jié)合。

作為鏈路節(jié)能的一種可行方法，基于可分割鏈路的鏈路休眠能夠較好地節(jié)省鏈路能耗。然而，在節(jié)點(diǎn)節(jié)能方案中，尚未有結(jié)合可分割鏈路的鏈路休眠的方案。考慮先使用節(jié)能方案解決節(jié)點(diǎn)映射，并且在鏈路映射時(shí)采取分割鏈路的做法，可以使得在一些節(jié)點(diǎn)滿足約束條件時(shí)，解決鏈路不滿足所需帶寬約束的問題。

(2)方案中加入遷移能耗。

在一次虛擬網(wǎng)絡(luò)請(qǐng)求的通信過程中，可能會(huì)出現(xiàn)個(gè)別的節(jié)點(diǎn)遇到異常中斷工作的情況，需要重新為這個(gè)節(jié)點(diǎn)分配合適的資源，以維持正常通信。在中斷的節(jié)點(diǎn)重新映射結(jié)束前，移動(dòng)資源和維持額外鏈路的能耗需要考慮到算法中。文獻(xiàn)[11]提出的算法考慮到了這種遷移能耗。

(3)節(jié)能算法的規(guī)模較小。

目前，節(jié)能算法的研究多集中于中小規(guī)模的網(wǎng)絡(luò)中，適用于大規(guī)模網(wǎng)絡(luò)的元啟發(fā)式算法的研究較少。在大規(guī)模網(wǎng)絡(luò)中應(yīng)用網(wǎng)絡(luò)虛擬化技術(shù)時(shí)，可以繼續(xù)探索適合不同應(yīng)用場景的虛擬網(wǎng)絡(luò)映射的節(jié)能算法。

(4)虛擬網(wǎng)絡(luò)請(qǐng)求發(fā)生變化的情況。

在一些特殊情況下，可能面臨虛擬網(wǎng)絡(luò)請(qǐng)求中的某個(gè)節(jié)點(diǎn)先于其他節(jié)點(diǎn)結(jié)束通信，這樣一來，這個(gè)虛擬節(jié)點(diǎn)將在虛擬請(qǐng)求中消失，不再消耗能量。文獻(xiàn)[14]中考慮了這種案例的簡單情況，并給出了一種重新分配資源的優(yōu)化方案。在未來的研究中，可以深入探討多個(gè)節(jié)點(diǎn)結(jié)束通信的情況，并給出性能更好的優(yōu)化方案。

(5)虛擬網(wǎng)絡(luò)技術(shù)在光網(wǎng)絡(luò)中的節(jié)能。

在光網(wǎng)絡(luò)中，虛擬網(wǎng)絡(luò)映射技術(shù)也得到了充分的研究和發(fā)展，相應(yīng)的節(jié)能技術(shù)也被提出[24-26]。未來的節(jié)能算法也可以考慮應(yīng)用到光網(wǎng)絡(luò)當(dāng)中。

[1] Fisher W, Suchara M, Rexford J.Greening backbone networks:reducing energy consumption by shutting off cables in bundled links[C]//ACM SIGCOMM workshop on green networking.New Delhi,India:ACM,2010:29-34.

[2] Botero J F,Hesselbach X,Duelli M,et al.Energy efficient virtual network embedding[J].IEEE Communications Letters,2012,16(5):756-759.

[3] Fischer A,Beck M T,de Meer H.An approach to energy-efficient virtual network embeddings[C]//IFIP/IEEE international symposium on integrated network management.[s.l.]:IEEE,2013:1142-1147.

[4] Wang B,Chang X,Liu J,et al.Reducing power consumption in embedding virtual infrastructures[C]//Globecom Workshops.[s.l.]:IEEE,2012:714-718.

[5] Su S,Zhang Z,Liu A X,et al.Energy-aware virtual network embedding[J].IEEE/ACM Transactions on Networking,2014,22(5):1607-1620.

[6] Zhang Z,Su S,Niu X,et al.Minimizing electricity cost in geographical virtual network embedding[C]//Global communications conference.[s.l.]:IEEE,2012:2609-2614.

[7] Su S,Zhang Z,Cheng X,et al.Energy-aware virtual network embedding through consolidation[C]//IEEE conference on computer communications workshop.[s.l.]:IEEE,2012:127-132.

[8] Guan X,Choi B Y,Song S.Topology and migration-aware energy efficient virtual network embedding for green data centers[C]//International conference on computer communication and networks.[s.l.]:IEEE,2014:1-8.

[9] Guan X,Choi B Y,Song S.Energy efficient virtual network embedding for green data centers using data center topology and future migration[J].Computer Communications,2015,69:50-59.

[10] Nonde L,Elgorashi T E H,Elmirghani J M H.Energy efficient virtual network embedding for cloud networks[J].Journal of Lightwave Technology,2015,33(9):1828-1849.

[11] Triki N,Kara N,Barachi M E,et al.A green energy-aware hybrid virtual network embedding approach[J].Computer Networks,2015,91(C):712-737.

[12] Bianzino A P,Chaudet C,Rossi D,et al.A survey of green networking research[J].IEEE Communications Surveys & Tutorials,2012,14(1):3-20.

[13] 陳曉華,李春芝,陳良育,等.主動(dòng)休眠節(jié)點(diǎn)鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報(bào),2014,25(7):1416-1431.

[14] Sun G,Yu H,Anand V,et al.A cost efficient framework and algorithm for embedding dynamic virtual network requests[J].Future Generation Computer Systems,2013,29(5):1265-1277.

[15] Lira V,Tavares E.Energy-aware mapping for dependable virtual networks[C]//International workshop on power and timing modeling,optimization and simulation.[s.l.]:IEEE,2015.

[16] Botero J F,Hesselbach X.Greener networking in a network virtualization environment[J].Computer Networks,2013,57(9):2021-2039.

[17] Ghazisaeedi E,Huang C.Off-peak energy optimization for links in virtualized network environment[J].IEEE Transactions on Cloud Computing,2015(99):1.

[18] Ghazisaeedi E,Huang C,Yan J.Off-peak energy-wise link reconfiguration for virtualized network environment[C]//IFIP/IEEE international symposium on integrated network management.[s.l.]:IEEE,2015:814-817.

[19] Ghazisaeedi E,Huang C.Energy-efficient virtual link reconfiguration for off-peak time[C]//2015 IEEE global communications conference.[s.l.]:IEEE,2015:1-7.

[20] 王 博,陳庶樵,王志明,等.基于中心度尋核的能效優(yōu)化虛擬網(wǎng)映射算法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(7):2087-2091.

[21] Shahin A A.Memetic multi-objective particle swarm optimization-based energy-aware virtual network embedding[J].International Journal of Advanced Computer Science & Applications,2015,6(4):1-12.

[22] Huu T N,Ngoc N P,Thu H T,et al.Modeling and experimenting combined smart sleep and power scaling algorithms in energy-aware data center networks[J].Simulation Modelling Practice & Theory,2013,39(8):20-40.

[23] Guan X,Wan X,Choi B Y,et al.Ant colony optimization based energy efficient virtual network embedding[C]//IEEE international conference on cloud networking.[s.l.]:IEEE,2015.

[24] Nonde L,Elgorashi T E H,Elmirghani J M H.Green virtual network embedding in optical OFDM cloud networks[C]//16th international conference on transparent optical networks.[s.l.]:IEEE,2014:1-5.

[25] Perello J,Pavon-Marino P,Spadaro S.Cost-efficient virtual optical network embedding for manageable inter-data-center connectivity[J].ETRI Journal,2013,35(1):142-145.

[26] Melo M,Sargento S,Killat U,et al.Optimal virtual network embedding:energy aware formulation[J].Computer Networks,2015,91(C):184-195.

Investigation on Energy-aware Virtual Network Embedding

LIU Ren-lun，YANG Long-xiang

(College of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Virtual Network Embedding (VNE) is a crucial technique to overcome development barriers of future Internet,which could permit multiple heterogeneous virtual networks to coexist in a common physical one for sharing substrate resources.However,current mapping algorithms of virtual network are mainly suitable for the situation that network traffic load is often high and mostly belong to heuristic mapping algorithm,which could lead to waste of network energy consumption and insufficient utilization of substrate resources as network energy consumption is low.With development of large scale network,problem for energy consumption of substrate network has attracted more and more attention.Energy-aware VNE Algorithm could effectively solve this problem by resource consolidation of substrate network under the condition that normal communication is ensured.Several energy saving algorithms have been investigated besides energy saving problem in virtual network has been emphasized and depicted.Classical models of energy consumption have also been sorted and discussed.Analysis on mapping processes of classical algorithms and their parameter indices have been conducted and the future investigation direction has been proposed.

virtual network embedding;energy-aware;resource consolidation;model of energy consumption

2016-04-22

2016-08-16

時(shí)間：2017-02-17

國家自然科學(xué)基金資助項(xiàng)目(61372124);國家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2013CB329104)

劉認(rèn)倫(1991-)，男，碩士，研究方向?yàn)橐苿?dòng)通信與無線技術(shù)；楊龍祥，教授，博士生導(dǎo)師，研究方向?yàn)橐苿?dòng)無線通信系統(tǒng)和物聯(lián)網(wǎng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1628.038.html

TP301.6

A

1673-629X(2017)03-0029-06

10.3969/j.issn.1673-629X.2017.03.006