劉光遠(yuǎn)，安秀芳，蘇森

（1. 石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043；2. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100876）

基于節(jié)點(diǎn)可靠性感知和共享路徑保護(hù)的虛擬網(wǎng)映射算法研究

劉光遠(yuǎn)1，安秀芳1，蘇森2

（1. 石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043；2. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100876）

網(wǎng)絡(luò)虛擬化技術(shù)為目前的網(wǎng)絡(luò)架構(gòu)提供了一種有效的擴(kuò)展手段。近年來，底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施失效事件頻發(fā)，因此如何提高虛擬網(wǎng)絡(luò)的可靠性成為目前該領(lǐng)域一個(gè)研究熱點(diǎn)。對(duì)在保證虛擬網(wǎng)絡(luò)可靠性的同時(shí)如何最小化底層網(wǎng)絡(luò)映射開銷問題進(jìn)行研究，設(shè)計(jì)了一個(gè)新的啟發(fā)式算法對(duì)其進(jìn)行求解。實(shí)驗(yàn)表明，相比其他算法，所提算法網(wǎng)絡(luò)帶寬資源開銷更低。

網(wǎng)絡(luò)虛擬化；虛擬網(wǎng)絡(luò)映射；啟發(fā)式

1 引言

目前，互聯(lián)網(wǎng)應(yīng)用在人們的日常生活中發(fā)揮了重要作用[1]，但是其固有的設(shè)計(jì)規(guī)則和多服務(wù)提供商的特征，使評(píng)估和部署新的網(wǎng)絡(luò)應(yīng)用變得越來越難。近年來，人們提出了網(wǎng)絡(luò)虛擬化技術(shù)，用來解決“網(wǎng)絡(luò)僵化”問題[2,3]。該技術(shù)允許多個(gè)異構(gòu)的虛擬網(wǎng)絡(luò)共享一個(gè)底層物理網(wǎng)絡(luò)，因此得到了越來越多的應(yīng)用，但是虛擬網(wǎng)絡(luò)仍需面臨不可預(yù)測(cè)的底層網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路失效問題，嚴(yán)重的會(huì)導(dǎo)致虛擬網(wǎng)絡(luò)不再可用。

虛擬網(wǎng)絡(luò)映射問題已被證明為 NP難題[4]，早期的虛擬網(wǎng)研究[5～7]以底層網(wǎng)絡(luò)資源利用最優(yōu)為目標(biāo)，設(shè)計(jì)不同的啟發(fā)式算法，但是均沒有考慮底層網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路失效時(shí)虛擬網(wǎng)絡(luò)的可靠性問題。在映射的過程中加入虛擬網(wǎng)絡(luò)可靠性約束無疑使該問題變得更加復(fù)雜。由于提供虛擬網(wǎng)絡(luò)可靠性保證需要消耗更多的底層網(wǎng)絡(luò)資源，因此所設(shè)計(jì)的算法應(yīng)該在虛擬網(wǎng)絡(luò)可靠性和底層網(wǎng)絡(luò)資源消耗之間做一個(gè)權(quán)衡。文獻(xiàn)[8～10]基于完全冗余機(jī)制對(duì)底層鏈路或節(jié)點(diǎn)失效進(jìn)行了保護(hù)，但是資源使用效率還有待提高。本文提出了一個(gè)新的可靠虛擬網(wǎng)絡(luò)映射算法RVNM，目的是在保證虛擬網(wǎng)絡(luò)可靠性的同時(shí)最小化底層網(wǎng)絡(luò)資源開銷。在節(jié)點(diǎn)映射階段，該方法不預(yù)留底層網(wǎng)絡(luò)保護(hù)資源，將底層物理節(jié)點(diǎn)按照可靠性和資源負(fù)載平衡綜合進(jìn)行評(píng)估并排序，然后將虛擬節(jié)點(diǎn)映射到具有高評(píng)估值的底層物理節(jié)點(diǎn)上，實(shí)驗(yàn)表明該機(jī)制可以大大提高虛擬節(jié)點(diǎn)的抗毀性。在鏈路映射階段，本文設(shè)計(jì)了一個(gè)新的鏈路映射機(jī)制，該機(jī)制基于共享路徑保護(hù)策略。實(shí)驗(yàn)表明，該機(jī)制可在底層網(wǎng)絡(luò)帶寬使用方面接近最優(yōu)。

2 相關(guān)工作

由于虛擬節(jié)點(diǎn)和虛擬鏈路的約束限制，虛擬網(wǎng)絡(luò)映射問題已被證明為NP難題。Yu等[5]重新對(duì)底層網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)，通過路徑分裂和路徑遷移機(jī)制使映射問題簡(jiǎn)化。Chowdhury等[6]考慮虛擬節(jié)點(diǎn)位置需求，為該問題建立一個(gè)混合線性規(guī)劃模型，并利用線性松弛技術(shù)對(duì)其進(jìn)行求解。Lischka等[7]基于子圖同構(gòu)理論提出了一種虛擬網(wǎng)映射算法以提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率。CHENG等[11]基于 PageRank理論提出了一種拓?fù)涓兄奶摂M網(wǎng)絡(luò)映射算法，該算法提高了底層網(wǎng)絡(luò)運(yùn)營(yíng)商的收益。盡管如此，以上研究主要將目光集中在底層網(wǎng)絡(luò)資源的高效利用上，忽視了由于底層網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路失效帶來的虛擬網(wǎng)絡(luò)可靠性保護(hù)問題，因此，虛擬網(wǎng)絡(luò)在底層資源失效后無法快速得到恢復(fù)，可能造成嚴(yán)重的經(jīng)濟(jì)損失。

近年來，有關(guān)可靠虛擬網(wǎng)絡(luò)映射的相關(guān)研究逐漸增多。針對(duì)底層網(wǎng)絡(luò)單鏈路失效情境，Rahman等[8]基于快速重路由策略，提出了一種1∶1確定性后備鏈路恢復(fù)機(jī)制，該機(jī)制在考慮最大化長(zhǎng)期收益的同時(shí)盡可能最小化長(zhǎng)期懲罰代價(jià)，但底層網(wǎng)絡(luò)帶寬使用效率較低。針對(duì)相似的問題情境，Chen等[9]基于路徑共享機(jī)制提出一種主動(dòng)鏈路保護(hù)方法，該方法所消耗的底層網(wǎng)絡(luò)帶寬比文獻(xiàn)[8]低，但還有進(jìn)一步優(yōu)化的空間，此外該論文僅考慮了鏈路保護(hù)的情形而忽略了節(jié)點(diǎn)可靠性保護(hù)問題。針對(duì)底層節(jié)點(diǎn)失效情境，Yeow等[10]提出冗余資源共享池的方法，該方法可以達(dá)到n：k的冗余保護(hù)，但是該方法仍舊消耗了許多底層網(wǎng)絡(luò)保護(hù)資源。事實(shí)上，在真實(shí)的網(wǎng)絡(luò)中，底層網(wǎng)絡(luò)節(jié)點(diǎn)失效的可行性很小，所以沒有必要為它們預(yù)留那么多的底層保護(hù)資源。因此，本文提出了一個(gè)新的節(jié)點(diǎn)映射機(jī)制，該機(jī)制在不預(yù)留底層網(wǎng)絡(luò)保護(hù)資源的情況下仍能提高虛擬節(jié)點(diǎn)的抗毀性，而且本文所提出的鏈路映射算法，相比文獻(xiàn)[8,9]算法，在底層網(wǎng)絡(luò)帶寬資源使用方面接近最優(yōu)。本文的研究對(duì)資源有限的底層網(wǎng)絡(luò)來說有重要意義。

3 問題描述

3.1 底層網(wǎng)絡(luò)

本文采用文獻(xiàn)[1]給出的虛擬網(wǎng)絡(luò)映射模型描述。底層物理網(wǎng)絡(luò)拓?fù)淇捎脦?quán)無向圖表示，其中，N和E分別表示底層物理網(wǎng)ss節(jié)點(diǎn)和鏈路的集合，和分別表示物理網(wǎng)節(jié)點(diǎn)的計(jì)算能力和鏈路帶寬。底層物理網(wǎng)絡(luò)可以是電信網(wǎng)絡(luò)或者數(shù)據(jù)中心網(wǎng)絡(luò)資源。圖1(a)給出了一個(gè)底層物理網(wǎng)絡(luò)拓?fù)鋵?shí)例，節(jié)點(diǎn)附近方框中的數(shù)字表示可用的計(jì)算資源，鏈路附近的數(shù)字表示可用的帶寬資源。

圖1 虛擬網(wǎng)絡(luò)映射實(shí)例

3.2 虛擬網(wǎng)絡(luò)請(qǐng)求

3.3 帶有可靠性保護(hù)需求的虛擬網(wǎng)絡(luò)映射問題

對(duì)于可靠的虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射，由于本文的目標(biāo)是盡可能減少底層網(wǎng)絡(luò)資源消耗，所以本文沒有設(shè)計(jì)基于預(yù)留底層保護(hù)資源的映射方法，而是設(shè)計(jì)了不預(yù)留底層網(wǎng)絡(luò)資源，提高虛擬節(jié)點(diǎn)抗毀性的虛擬節(jié)點(diǎn)映射方法。對(duì)于可靠的虛擬鏈路映射，在完成底層網(wǎng)絡(luò)基本虛擬鏈路映射以后，需要針對(duì)底層鏈路失效情境，為每個(gè)虛擬鏈路選擇保護(hù)路徑。給定一個(gè)虛擬鏈路euv，首先，應(yīng)該保證主鏈路和相應(yīng)保護(hù)鏈路不共享任何底層的物理鏈路或節(jié)點(diǎn)。直觀上說，本文可以簡(jiǎn)單采用冗余機(jī)制選取2條底層不相交的路徑進(jìn)行映射，但是這個(gè)方法會(huì)浪費(fèi)大量的底層網(wǎng)絡(luò)資源。事實(shí)上，由于鏈路保護(hù)資源存在共享使用的可能性，所以保護(hù)路徑不一定必須預(yù)留和主路徑相等的帶寬資源。通常情況下，會(huì)被設(shè)置為2條可共享保護(hù)路徑的主路徑帶寬的最大值，而不是它們2個(gè)帶寬之和。本文對(duì)簡(jiǎn)單的共享路徑保護(hù)機(jī)制進(jìn)行改進(jìn)，其帶寬消耗大大低于現(xiàn)有算法。值得注意的是，相關(guān)研究表明單鏈路失效數(shù)量占所有失效數(shù)量的70%[2,3]，所以本文主要針對(duì)單鏈路失效保護(hù)問題進(jìn)行研究。

3.4 目標(biāo)

本文設(shè)計(jì)了基于底層網(wǎng)絡(luò)資源約束的在線可靠虛擬網(wǎng)絡(luò)映射算法。主要目標(biāo)是在保證虛擬網(wǎng)絡(luò)可靠性的同時(shí)最小化底層網(wǎng)路資源開銷。因?yàn)楦俚馁Y源開銷表示底層網(wǎng)絡(luò)可以節(jié)省更多資源以用于接受更多的虛擬網(wǎng)絡(luò)請(qǐng)求。下面給出后面實(shí)驗(yàn)中用到的性能參數(shù)及說明，包括平均網(wǎng)絡(luò)帶寬消耗、長(zhǎng)期帶寬資源利用率、虛擬網(wǎng)絡(luò)請(qǐng)求接受率和長(zhǎng)期收益開銷比（）。

1)平均網(wǎng)絡(luò)帶寬消耗定義為

其中，BW表示底層網(wǎng)絡(luò)帶寬消耗。

2)長(zhǎng)期帶寬資源利用率定義為

其中，RBW表示預(yù)留的保護(hù)帶寬資源，PBW表示主帶寬資源。

3)參考文獻(xiàn)[3,4]的工作，虛擬網(wǎng)絡(luò)請(qǐng)求接受率被定義為

其中，VNR表示虛擬網(wǎng)絡(luò)請(qǐng)求， VNRa表示底層網(wǎng)絡(luò)成功接受了虛擬網(wǎng)絡(luò)請(qǐng)求。

4）長(zhǎng)期收益開銷比通常表示資源使用的效率，被定義為

4 RVNM啟發(fā)式算法

本節(jié)對(duì)本文設(shè)計(jì)的可靠虛擬網(wǎng)絡(luò)映射算法進(jìn)行描述。該算法包括底層節(jié)點(diǎn)可靠性感知的節(jié)點(diǎn)映射機(jī)制和優(yōu)化共享路徑保護(hù)鏈路映射機(jī)制。

4.1 抗毀的虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射機(jī)制

該算法首先基于底層節(jié)點(diǎn)先前的失效次數(shù)對(duì)底層物理節(jié)點(diǎn)進(jìn)行可靠性評(píng)估，失效次數(shù)越多表明這個(gè)底層節(jié)點(diǎn)的可靠性越低。除此之外，算法還考慮了節(jié)點(diǎn)負(fù)載狀態(tài)，因?yàn)楣?jié)點(diǎn)hot-spot問題會(huì)導(dǎo)致虛擬網(wǎng)絡(luò)請(qǐng)求拒絕數(shù)量的增加。而且，當(dāng)?shù)讓觝ot-spot節(jié)點(diǎn)失效后，被影響的虛擬網(wǎng)絡(luò)數(shù)量通常要多于其他失效節(jié)點(diǎn)所帶來的影響。所以，節(jié)點(diǎn)映射算法綜合考慮了底層節(jié)點(diǎn)可靠性和資源使用負(fù)載平衡這2個(gè)方面。因此本文給出如下定義

其中，F(xiàn)T(ns)表示節(jié)點(diǎn) ns∈Ns的失效次數(shù)，PR(ns)表示節(jié)點(diǎn) ns上已使用資源的百分比。值得注意的是，這里所說的節(jié)點(diǎn)資源包括 CPU能力和與節(jié)點(diǎn)ns相連的所有鏈路帶寬資源。k表示節(jié)點(diǎn)ns上已經(jīng)映射的虛擬網(wǎng)絡(luò)的數(shù)量。

在虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射階段，算法首先計(jì)算每個(gè)底層網(wǎng)絡(luò)節(jié)點(diǎn)的R(ns)值，并對(duì)其進(jìn)行降序排列。然后將虛擬節(jié)點(diǎn)依次映射到具有高 R(ns)值的底層網(wǎng)絡(luò)節(jié)點(diǎn)上，且該節(jié)點(diǎn)必須滿足虛擬節(jié)點(diǎn) CPU能力和鏈路能力需求。

4.2 優(yōu)化共享保護(hù)虛擬網(wǎng)絡(luò)鏈路映射機(jī)制

如 3.1節(jié)所述，將虛擬節(jié)點(diǎn)全部映射到底層物理節(jié)點(diǎn)后，RVNM需要為每個(gè)虛擬鏈路選擇一個(gè)底層主路徑進(jìn)行映射。但是即使虛擬節(jié)點(diǎn)已經(jīng)固定，虛擬鏈路最優(yōu)映射問題仍是 NP難的。因此，為了簡(jiǎn)單起見，本文工作集中于底層網(wǎng)絡(luò)不支持路徑分裂的情形，通過最短路徑算法找到最小帶寬消耗（最小跳數(shù)）的主路徑。本文的工作成果也可應(yīng)用于其他情境，僅需要底層網(wǎng)絡(luò)支持路徑分裂即可。

由于本文考慮的是底層單鏈路失效的虛擬網(wǎng)絡(luò)可靠性保護(hù)問題，所以為主路徑預(yù)留的保護(hù)路徑資源有可能實(shí)現(xiàn)共享。如果它們的保護(hù)路徑占用同樣的鏈路，則必須保證這2個(gè)保護(hù)路徑對(duì)應(yīng)的主路徑不相交。

算法的最終目標(biāo)是要找到最小化底層鏈路映射消耗的映射方案，即滿足的主鏈路和保護(hù)鏈路的映射方案。

鏈路映射算法的主程序如算法1所示。S 表示最終的鏈路映射結(jié)果。如果沒有可用的映射方案，算法返回NULL。

算法中用到的變量說明如下。

L：表示所有的底層鏈路集合。

BW：表示鏈路j上的帶寬總能力。

Cj：表示鏈路j 上的可用帶寬能力。

pj：表示鏈路j上所有主帶寬使用資源。

rj：表示鏈路j上所有保護(hù)帶寬使用資源。

pi：承載虛擬鏈路 i 的主路徑。

ri：承載虛擬鏈路 i 的保護(hù)路徑。

M：迭代限制次數(shù)。

cj：表示計(jì)算最小帶寬消耗。

算法1主路徑和保護(hù)路徑選擇策略

步驟1按照式(6)計(jì)算最小帶寬消耗對(duì)應(yīng)的主路徑pi；如果pi存在，則執(zhí)行步驟2。

否則，拒絕映射當(dāng)前虛擬網(wǎng)絡(luò)請(qǐng)求，算法返回NULL。

步驟2如果Tgt;M，執(zhí)行步驟6。

否則，固定主路徑pi、按照式(7)計(jì)算最小消耗對(duì)應(yīng)的保護(hù)路徑ri。

如果ri存在，則執(zhí)行步驟3。

否則，執(zhí)行步驟6。

步驟3計(jì)算當(dāng)前主路徑pi和保護(hù)路徑ri資源消耗之和C。

步驟4固定保護(hù)路徑ri，按照式(8)重新計(jì)算新的最小花費(fèi)對(duì)應(yīng)的主路徑

否則，執(zhí)行步驟6。

如果C*＜C,則且返回執(zhí)行步驟2。

否則，執(zhí)行步驟 6。

步驟6如果S=NULL，算法返回NULL。

否則，按照方案S更新所有的鏈資源分配并將結(jié)果返回。

算法中變量T和S初始化分別被設(shè)置為1和NULL。式(6)表示一個(gè)計(jì)算鏈路消耗函數(shù)，鏈路存在更多空閑資源表示其鏈路消耗更低。此外，如果主路徑占用這些鏈路，則底層鏈路資源消耗會(huì)更平均，更能達(dá)到負(fù)載均衡的目的。式(7)中表示鏈路j上預(yù)留的保護(hù)資源需求，假設(shè)j∈ri,?n∈L}，其中，表示虛擬鏈路的集合，該集合中元素的主路徑為n，保護(hù)路徑為j。容易看出，在已經(jīng)分配了保護(hù)路徑的鏈路上分配新的保護(hù)路徑會(huì)占被認(rèn)為更低的鏈路消耗，從而使保護(hù)資源利用率提高。在式(9)中，ε表示一個(gè)極小門限值（例如ε=10?3），表示鏈路 l上的保護(hù)資源需求。其中，表示虛擬鏈路的集合，該集合中元素的主路徑為 n，保護(hù)路徑為l。

為了更好地說明算法，現(xiàn)舉一實(shí)例，在某時(shí)刻，需要映射虛擬鏈路L，按照RVNM算法執(zhí)行流程。首先通過最短路徑算法為該虛擬鏈路選擇底層網(wǎng)絡(luò)映射的主路徑和保護(hù)路徑。然后將保護(hù)路徑固定，重新計(jì)算一個(gè)新的主路徑。如果這個(gè)新的主路徑可以使鏈路使用總資源消耗更少（按照算法 1中的公式計(jì)算，實(shí)質(zhì)為可以實(shí)現(xiàn)保護(hù)鏈路共享，從而降低資源消耗），則保留并更新現(xiàn)有的鏈路映射方案。接著再固定主路徑，按照類似的思路重新計(jì)算保護(hù)路徑以使帶寬資源使用更優(yōu)（按照算法和計(jì)算公式進(jìn)行執(zhí)行，由于每個(gè)階段都對(duì)所有可能的映射方案進(jìn)行了比較，因此通過迭代可以得到全局最優(yōu)解，即最優(yōu)帶寬資源消耗值）。當(dāng)新的結(jié)果比先前結(jié)果差或者到達(dá)了限定的迭代次數(shù)（由于迭代次數(shù)或時(shí)間的限制，該結(jié)果接近最優(yōu)值），重映射過程就停止。

5 性能評(píng)估

本節(jié)首先對(duì)模擬實(shí)驗(yàn)設(shè)置進(jìn)行了描述，然后給出了實(shí)驗(yàn)數(shù)據(jù)和分析評(píng)估結(jié)果。

5.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證RVNM的有效性，在先前工作開發(fā)的虛擬網(wǎng)絡(luò)映射模擬平臺(tái)上[11]對(duì)算法進(jìn)行了測(cè)試。與早期工作[11～14]相似，底層網(wǎng)絡(luò)拓?fù)溆蒅T-ITM[15]生成，包含100個(gè)節(jié)點(diǎn)和500條鏈路。底層網(wǎng)絡(luò)的節(jié)點(diǎn) CPU能力和鏈路帶寬能力為40～90均勻分布。虛擬節(jié)點(diǎn)個(gè)數(shù)服從 2～7均勻分布。虛擬節(jié)點(diǎn)的CPU能力需求為0～15均勻分布，帶寬能力需求在0～40。此外，虛擬網(wǎng)絡(luò)請(qǐng)求的到達(dá)頻率服從每100個(gè)時(shí)間單位到達(dá)率為4的泊松分布。虛擬網(wǎng)絡(luò)的平均生存時(shí)間為500個(gè)時(shí)間單位。模擬實(shí)驗(yàn)共運(yùn)行大約50 000個(gè)時(shí)間單位，在這期間大約有2 500個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求。實(shí)驗(yàn)中算法迭代限制參數(shù)M設(shè)為6。

實(shí)驗(yàn)中，本文比較了許多參數(shù)指標(biāo)，包括式(1)中定義的平均網(wǎng)絡(luò)帶寬花費(fèi)、式(2)定義的長(zhǎng)期帶寬資源利用率、式(3)定義的虛擬網(wǎng)絡(luò)請(qǐng)求接受率、式(4)定義的長(zhǎng)期收益開銷比和算法成功接受一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的平均時(shí)間花費(fèi)。

實(shí)驗(yàn)中被比較的算法如表1所示，且所有算法都采用相同的輸入。實(shí)驗(yàn)硬件平臺(tái)配置為Intel 4.0 GHz內(nèi)核CPU、8 GB內(nèi)存、1 TB硬盤,Linux OS 2.8。

表1 比較的算法

5.2 實(shí)驗(yàn)結(jié)果及分析

由于采用了新的虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射策略，實(shí)驗(yàn)表明，在不預(yù)留底層網(wǎng)絡(luò)資源的情況下，RVNM提高了虛擬網(wǎng)絡(luò)節(jié)點(diǎn)的抗毀性，其他2個(gè)算法僅考慮了鏈路保護(hù)而忽略了節(jié)點(diǎn)保護(hù)。此外，算法的收益和花費(fèi)是本文工作主要考慮的因素。下面給出具體的實(shí)驗(yàn)結(jié)果和分析。

1)RVNM相比其他2個(gè)算法，大大降低了底層網(wǎng)絡(luò)帶寬消耗

圖2和圖3分別給出了3個(gè)算法的網(wǎng)絡(luò)帶寬消耗和帶寬資源利用率的實(shí)驗(yàn)數(shù)據(jù)結(jié)果。HYBIRD算法由于采用確定性路徑保護(hù)方法，其帶寬資源消耗明顯高于其他2個(gè)基于共享路徑保護(hù)的算法，所以在圖3中只比較了另2種算法。相比PARDALIS，RVNM明顯節(jié)省了網(wǎng)絡(luò)帶寬資源，如圖3所示，其保護(hù)資源使用率比PARDALIS 平均降低了10.7%，原因是RVNM算法采用了優(yōu)化共享鏈路映射機(jī)制，更多地保護(hù)帶寬能夠被共享，所以底層網(wǎng)絡(luò)帶寬能夠得到更好的利用。

圖2 平均網(wǎng)絡(luò)資源消耗

圖3 長(zhǎng)期帶寬資源利用率

2)RVNM 相比其他算法能獲得更高的虛擬網(wǎng)絡(luò)請(qǐng)求接受率和長(zhǎng)期收益開銷比

如圖4所示，RVNM算法的虛擬網(wǎng)絡(luò)請(qǐng)求接受率高于PARDALIS和HYBRID算法，結(jié)果平均分別高出9.6% 和 18.3%。這是因?yàn)镽VNM算法更好地節(jié)省了網(wǎng)絡(luò)帶寬資源，從而使更多的空閑資源被用于后續(xù)的虛擬網(wǎng)絡(luò)請(qǐng)求。

圖4 虛擬網(wǎng)絡(luò)請(qǐng)求接受率

如圖5所示，本文提出的算法由最少的資源帶寬消耗，獲得了最好的收益開銷比，從而證明了網(wǎng)絡(luò)資源使用的有效性。HYBRID算法由于無視帶寬共享獲得了最差的比較結(jié)果。

圖5 長(zhǎng)期收益開銷比

3)RVNM 算法在執(zhí)行時(shí)間和資源消耗之間做一平衡

圖6描述了各個(gè)算法成功映射一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求平均所花費(fèi)的時(shí)間。RVNM的執(zhí)行結(jié)果高于其他2個(gè)算法，這主要是因?yàn)楣?jié)點(diǎn)可靠性計(jì)算和優(yōu)化路徑的選擇，但1.8 s的時(shí)間復(fù)雜度是可以滿足在線虛擬網(wǎng)絡(luò)請(qǐng)求的。更重要的是，相比 PARDALIS和HYBRID算法，RVNM算法能提高虛擬節(jié)點(diǎn)的抗毀性而不用預(yù)留底層保護(hù)資源，同時(shí)在網(wǎng)絡(luò)鏈路映射開銷上分別降低了10%和19%左右，為底層運(yùn)營(yíng)商節(jié)省了更多的寶貴資源。

圖6 一個(gè)虛擬請(qǐng)求的平均完成時(shí)間

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

本文研究了可靠的虛擬網(wǎng)絡(luò)映射問題，針對(duì)單鏈路失效情境提出了一個(gè)新的啟發(fā)式算法RVNM。該算法通過節(jié)點(diǎn)可靠性感知策略，在不預(yù)留底層保護(hù)資源的情況下提高了虛擬節(jié)點(diǎn)的抗毀性。此外，算法設(shè)計(jì)的優(yōu)化共享保護(hù)鏈路機(jī)制能最小化底層網(wǎng)絡(luò)帶寬消耗。實(shí)驗(yàn)表明，該算法是一種有效的可靠虛擬網(wǎng)絡(luò)映射算法。今后的工作將進(jìn)一步研究跨域虛擬網(wǎng)絡(luò)映射可靠性問題。

[1]MEEKER M. Internet Trends 2016[EB/OL].http://www. kpcb.com/internet-trends,2016-06-01.

[2]CHOWDHURY N M M K,BOUTABA R. Network virtualization:state of the art and research challenges[J]. Communications Magazine,IEEE,2009,47(7): 20-26.

[3]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.

[4]肖藹玲,王穎,孟洛明,等. 基于知識(shí)描述和遺傳算法的跨域虛擬網(wǎng)絡(luò)映射[J]. 軟件學(xué)報(bào),2014,25(10): 2189-2205.XIAO A L,WANG Y,MENG L M,et al. Knowledge description and genetic algorithm based multi-domain virtual network embedding [J].Journal of Software,2014,25(10): 2189-2205.

[5]YU M,YI Y,REXFORD J,et al. Rethinking virtual network embed-ding: substrate support for path splitting and migration[J]. ACM Sigcomm Computer Communication Review,2008,38(2): 17-29.

[6]CHOWDHURY M,RAHMAN M R,BOUTABA R. ViNEYard:virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE Transactions on Networking,2012,20(1):206-219 .

[7]LISCHKA J,KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]//The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. c2009: 81-88.

[8]RAHMAN M,AIB I,BOUTABA R. SVNE: survivable virtual network embedding algorithms for network virtualization[J]. IEEE Transactions on Network and Service Management,2014,10 (2): 105-118.

[9]CHEN Y,LI J,WO T,et al. Resilient virtual network service provision in network virtualization environments[C]//IEEE ICPADS. c2010: 51-58.

[10]YEOW W L,WESTPHAL C,KOZAT U. Designing and embedding reliable virtual infrastructures[J]. ACM Sigcomm Computer Communication Review,2011,41(2): 57-64.

[11]CHENG X,SU S,ZHANG Z,et al. Virtual network embedding through topology-aware node ranking[J]. ACM Sigcomm Computer Communication Review,2011,41(2): 39-47.

[12]CHENG X,SU S,ZHANG Z,et al. Virtual network embedding through topology awareness and optimization[J]. Elsevier Computer Networks,2012,56(6): 1797-1813.

[13]SU S,CHENG X,ZHANG Z,et al. Virtual network embedding with survivable routing[J]. Journal of Internet Technology,2014,14(5):741-750.

[14]劉光遠(yuǎn),雙鍇,蘇森. 區(qū)分服務(wù) QoP的可生存虛擬網(wǎng)絡(luò)映射算法研究[J]. 通信學(xué)報(bào),2013,34(12):79-84.LIU G Y,SHUANG K,SU S. Survivable virtual network mapping with differentiated services QoP[J]. Journal on Communications,2013,34(12):79-84.

[15]ZEGURA E W,CALVERT K L,BHATTACHARJEE S. How to model an Internet work[C]//IEEE Infocom,c1996: 594-602.

Virtual network mapping algorithm with node reliability awareness and shared-path protection

LIU Guang-yuan1,AN Xiu-fang1,SU Sen2

(1.School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China;2. State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China)

Network virtualization has been proposed as a promising way for expanding the network architecture. However,how to provide reliable VN against substrate infrastructure failures has become an increasingly important issue. Meanwhile the substrate network resource cost should be minimized under VN reliability guarantees to maximize the revenue for the infrastructure providers (InP). A novel heuristic VN mapping algorithm was presented. Simulation results show that proposed algorithm can gain near optimal network bandwidth usage compared to the previous algorithms.

network virtualization,virtual network mapping,heuristic

s:The National Natural Science Foundation of China (No.61170274,No.61373160),Colleges and Universities in Hebei Province Science and Technology Research Fund (No.QN2016270),Undergraduate Training Programs for Innovation and Entrepreneurship (No.201510107098)

TP393.1

A

2015-10-21；

2016-06-13

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61170274,No.61373160）；河北省高等學(xué)?？茖W(xué)技術(shù)研究基金資助項(xiàng)目（No.QN2016270）；大學(xué)生創(chuàng)新創(chuàng)業(yè)基金資助項(xiàng)目（No.201510107098）

10.11959/j.issn.1000-436x.2016155

劉光遠(yuǎn)（1981-），男，河北石家莊人，博士，石家莊鐵道大學(xué)講師，主要研究方向?yàn)橄乱淮ヂ?lián)網(wǎng)與云計(jì)算技術(shù)。

安秀芳（1993-），女，河北滄州人，主要研究方向?yàn)樵朴?jì)算技術(shù)。

蘇森（1971-），男，山東菏澤人，北京郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榉?wù)計(jì)算、云計(jì)算、大數(shù)據(jù)處理。