彭紅姣，潘子輝

（1.南京郵電大學(xué) 工程訓(xùn)練中心，江蘇 南京 210023；2.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210046）

全球互聯(lián)網(wǎng)持續(xù)高速發(fā)展，遠(yuǎn)超出互聯(lián)網(wǎng)原設(shè)計(jì)初衷，使現(xiàn)有網(wǎng)絡(luò)體系架構(gòu)不具備可控可管性、服務(wù)質(zhì)量難以保障、可擴(kuò)展性較差、移動(dòng)性支持較差等問題越為突出。隨著網(wǎng)絡(luò)規(guī)模進(jìn)一步增長(zhǎng)，這些問題暴露更為明顯。云計(jì)算、物聯(lián)網(wǎng)、大數(shù)據(jù)、人工智能、大流量視頻等新應(yīng)用和新技術(shù)的不斷涌現(xiàn)，也對(duì)現(xiàn)有互聯(lián)網(wǎng)提出了更高要求。為從根本上解決現(xiàn)有網(wǎng)絡(luò)面臨的問題，打破互聯(lián)網(wǎng)僵局，研究者們經(jīng)過不懈努力，認(rèn)為網(wǎng)絡(luò)虛擬化（Network Visualization，NV）[1-5]是一個(gè)很有前景的方法，其包括新型網(wǎng)絡(luò)更便捷的遷移方案，更易與現(xiàn)有網(wǎng)絡(luò)共存。本文研究了其虛擬網(wǎng)絡(luò)映射問題并提出一種新算法，與經(jīng)典的兩步式映射算法進(jìn)行了比較，并分析其優(yōu)勢(shì)和適用環(huán)境，驗(yàn)證了其可行性。

1 虛擬網(wǎng)絡(luò)映射算法研究

1.1 現(xiàn)狀和問題

虛網(wǎng)映射問題是網(wǎng)絡(luò)虛擬化最核心的問題之一，也是一個(gè)充滿挑戰(zhàn)性的問題[6]。在虛網(wǎng)映射中，虛擬網(wǎng)絡(luò)請(qǐng)求各自對(duì)應(yīng)的網(wǎng)絡(luò)拓?fù)渫槐M相同，因此要適應(yīng)這些不同的拓?fù)湔?qǐng)求。在分配資源時(shí)，節(jié)點(diǎn)和鏈路需求要同時(shí)滿足要求。一般情況下，虛網(wǎng)請(qǐng)求都是動(dòng)態(tài)的，在分配當(dāng)前物理資源時(shí)，不能預(yù)知將要到達(dá)的虛網(wǎng)請(qǐng)求信息。即使是靜態(tài)請(qǐng)求，或所有請(qǐng)求信息也能預(yù)知，虛網(wǎng)映射問題仍是一個(gè)NP-hard問題，可轉(zhuǎn)化為多路分離器問題[7-10]。另外，即便已確定節(jié)點(diǎn)映射，在流不可分割情況下，即在一個(gè)單一路徑上最佳地分配一個(gè)虛擬鏈路集，虛擬鏈路的映射仍是一個(gè)NP-hard問題，但可轉(zhuǎn)化為不可分割流問題[11-12]。

至今，研究人員已提出不少提高物理資源利用率的虛網(wǎng)映射算法，可得出某種網(wǎng)絡(luò)環(huán)境下較為適合的映射結(jié)果。由于虛網(wǎng)映射是一個(gè)NP-hard問題，需考慮的影響因素非常多，有些算法[13-15]以物理鏈路資源無限大為前提，從而實(shí)現(xiàn)更合理的節(jié)點(diǎn)映射。另一部分算法[1,16-17]側(cè)重于鏈路映射，以尋找最優(yōu)鏈路映射為目的，而相對(duì)的節(jié)點(diǎn)映射則采取簡(jiǎn)單處理。這兩個(gè)偏向都會(huì)存在一些問題[18-19]。

假設(shè)鏈路資源無限大，節(jié)點(diǎn)映射算法通常能取得非常好的效果，這些算法可有效提高物理節(jié)點(diǎn)資源的利用率，同時(shí)可保證節(jié)點(diǎn)相對(duì)緊湊（即節(jié)點(diǎn)間距離相對(duì)較?。?。而實(shí)際上，鏈路資源不可能為無限大，這種理想情況并不存在。故此類節(jié)點(diǎn)映射算法通常會(huì)在鏈路映射上遇到困難，最典型的兩個(gè)虛擬節(jié)點(diǎn)所映射到的物理節(jié)點(diǎn)之間的物理鏈路資源，無法滿足其虛網(wǎng)請(qǐng)求中虛擬鏈路的需求。其次，如果優(yōu)先選擇帶寬資源較多的節(jié)點(diǎn)進(jìn)行映射，確實(shí)能很好地滿足對(duì)物理鏈路及物理節(jié)點(diǎn)資源的需求。但由于總是優(yōu)先占用帶寬資源最為充裕的節(jié)點(diǎn)，可能會(huì)對(duì)后來的虛擬網(wǎng)絡(luò)請(qǐng)求造成一定影響。另外，如將節(jié)點(diǎn)和鏈路映射分別執(zhí)行，對(duì)于虛網(wǎng)請(qǐng)求中相鄰或相近的節(jié)點(diǎn)，在映射后其對(duì)應(yīng)的物理節(jié)點(diǎn)在物理網(wǎng)絡(luò)中距離可能會(huì)非常遠(yuǎn)。這種分布分散的情況常常會(huì)導(dǎo)致虛擬鏈路過多占用網(wǎng)絡(luò)資源，致使物理資源利用率降低。本文給出了一種保持節(jié)點(diǎn)相鄰的虛擬網(wǎng)絡(luò)映射算法，可有效避免上述問題，或減少其所帶來的不利影響。

1.2 經(jīng)典的兩步式虛擬網(wǎng)絡(luò)映射算法

文獻(xiàn)[20]介紹了最為經(jīng)典的虛擬網(wǎng)絡(luò)映射算法——兩步式虛擬網(wǎng)絡(luò)映射算法，該算法既簡(jiǎn)潔又通用，映射簡(jiǎn)化為虛擬節(jié)點(diǎn)映射和虛擬鏈路映射。在虛擬節(jié)點(diǎn)映射中先使用貪婪算法進(jìn)行求解，再在虛擬鏈路映射中使用k最短路徑算法進(jìn)行求解。

定義1映射收益是指映射到物理網(wǎng)絡(luò)成功后，虛網(wǎng)請(qǐng)求的收益，由映射的帶寬和CPU資源定義：

其中，B(eν)是映射成功的虛擬網(wǎng)絡(luò)帶寬，C(nν)是映射成功的虛擬網(wǎng)絡(luò)節(jié)點(diǎn)CPU資源，α和β是用于調(diào)節(jié)帶寬和CPU的權(quán)重系數(shù)，在本文研究中均設(shè)為1。

定義2剩余資源（Available Resource,AR）是指某節(jié)點(diǎn)剩余物理資源與連接該節(jié)點(diǎn)的鏈路資源總和的乘積：

其中，nP為物理節(jié)點(diǎn)，lP為物理鏈路，L(nP)為與物理節(jié)點(diǎn)nP直接相連的物理鏈路的集合。

在兩步式虛擬網(wǎng)絡(luò)映射算法中，先以時(shí)間窗為單位接收虛網(wǎng)請(qǐng)求。再根據(jù)映射收益R(GV)對(duì)一個(gè)時(shí)間窗內(nèi)的虛網(wǎng)請(qǐng)求由高到低排序，收益高優(yōu)先映射。若映射成功，則更新物理網(wǎng)絡(luò)狀態(tài)；若映射失敗，則將其列入等待隊(duì)列；若失敗次數(shù)超過預(yù)先設(shè)定的值，則放棄該虛擬網(wǎng)絡(luò)請(qǐng)求。

在每個(gè)虛網(wǎng)映射請(qǐng)求時(shí)，先進(jìn)行節(jié)點(diǎn)映射環(huán)節(jié)。對(duì)于請(qǐng)求中的每個(gè)虛擬節(jié)點(diǎn)(nV)，通過貪婪算法找出能夠滿足其節(jié)點(diǎn)CPU需求，以及剩余資源最大物理節(jié)點(diǎn)(nP)。若能找到滿足nV條件的nP，則將nV映射到nP上，節(jié)點(diǎn)映射成功；否則，節(jié)點(diǎn)映射失敗，虛網(wǎng)請(qǐng)求映射失敗。若每個(gè)節(jié)點(diǎn)映射成功，則虛網(wǎng)請(qǐng)求節(jié)點(diǎn)映射成功。尋找物理節(jié)點(diǎn)過程考慮了與之相連接的物理鏈路資源，鏈路映射率得到提高。在完成節(jié)點(diǎn)映射后，執(zhí)行鏈路映射。對(duì)于虛網(wǎng)請(qǐng)求中的每條虛擬鏈路(lV)，首先確定其兩端點(diǎn)，之后找到其映射的物理節(jié)點(diǎn)，通過k最短路徑算法，找到物理節(jié)點(diǎn)間的1至k條最短路徑，若其中有任意一條路徑滿足lV的帶寬需求，則將lV映射到該路徑上；若物理路徑均不滿足條件，則不能完成虛擬鏈路映射，無法實(shí)現(xiàn)虛網(wǎng)請(qǐng)求映射。只有全部完成每個(gè)虛擬鏈路映射，才能完成虛擬鏈路映射環(huán)節(jié)。兩個(gè)環(huán)節(jié)全部成功后，即可完成整個(gè)虛網(wǎng)請(qǐng)求映射。

1.3 虛網(wǎng)請(qǐng)求接收算法改進(jìn)思路

一旦虛網(wǎng)請(qǐng)求在短時(shí)間內(nèi)涌入，則會(huì)出現(xiàn)先到請(qǐng)求阻塞，或低收益請(qǐng)求長(zhǎng)時(shí)間得不到滿足而產(chǎn)生饑渴現(xiàn)象等問題。為了保證算法高效運(yùn)行，并取得較高的映射收益，同時(shí)避免低收益請(qǐng)求長(zhǎng)時(shí)間得不到處理，本節(jié)提出了一種算法來應(yīng)對(duì)這些困難。

虛擬網(wǎng)絡(luò)請(qǐng)求將實(shí)時(shí)到達(dá)，并將它們按照時(shí)間窗進(jìn)行劃分。每個(gè)時(shí)間窗收到的虛擬網(wǎng)絡(luò)請(qǐng)求按收益進(jìn)行排序，且按收益由高到低設(shè)立優(yōu)先級(jí)（優(yōu)先級(jí)數(shù)值越大則優(yōu)先級(jí)越低），映射失敗時(shí)設(shè)其優(yōu)先級(jí)為當(dāng)前最低優(yōu)先級(jí)加1，從而加入隊(duì)列末尾，并設(shè)置其count參數(shù)加1，count參數(shù)達(dá)到一定數(shù)值后（數(shù)值大小視具體情況而定），放棄該請(qǐng)求。當(dāng)新的時(shí)間窗到達(dá)時(shí)，釋放已完成或者失效的資源，對(duì)于新到時(shí)間窗內(nèi)的請(qǐng)求，在計(jì)算其優(yōu)先級(jí)后，對(duì)其優(yōu)先級(jí)加上[x/2（]x為上一時(shí)間窗的請(qǐng)求總數(shù)），對(duì)于優(yōu)先級(jí)相同的請(qǐng)求，優(yōu)先處理較早到達(dá)的。這樣可在有效確保較高收益的同時(shí)，保證低收益請(qǐng)求不會(huì)長(zhǎng)時(shí)間得不到處理。

具體算法，步驟1：令x=0，c=0；步驟2：檢測(cè)是否有新的時(shí)間窗到達(dá)，若沒有，則跳至步驟5；步驟3：釋放已完成或者失效的資源，對(duì)時(shí)間窗內(nèi)虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行統(tǒng)計(jì)，令y為該時(shí)間窗內(nèi)虛擬網(wǎng)絡(luò)請(qǐng)求的數(shù)量，令c=c+1；步驟4：將該時(shí)間窗內(nèi)虛擬網(wǎng)絡(luò)請(qǐng)求按收益從高到低進(jìn)行排序，分別設(shè)其優(yōu)先級(jí)為(1+[x/2])到(y+[x/2])β，且分別設(shè)其count[z]為0（z為序號(hào)），W[z]=c，令x=y；步驟5：尋找當(dāng)前優(yōu)先級(jí)最高的虛擬網(wǎng)絡(luò)請(qǐng)求（優(yōu)先級(jí)數(shù)值最?。?，若結(jié)果唯一，跳至步驟7；步驟6：尋找結(jié)果中W[z]最小的虛擬網(wǎng)絡(luò)請(qǐng)求；步驟7：將該虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行映射，若不成功，count[z]=count[z]+1，若count[z]=3，放棄該請(qǐng)求，優(yōu)先級(jí)設(shè)為當(dāng)前最低優(yōu)先級(jí)+1，并跳至步驟2。

例如，第一個(gè)時(shí)間窗中共有20個(gè)虛網(wǎng)請(qǐng)求，按請(qǐng)求收益由高到底給出優(yōu)先級(jí)1至20。若優(yōu)先級(jí)為5的虛擬網(wǎng)絡(luò)請(qǐng)求失敗，則將其優(yōu)先級(jí)設(shè)為21，從而加入隊(duì)列末尾。若在一個(gè)時(shí)間窗內(nèi)只能處理10個(gè)請(qǐng)求，而第二個(gè)時(shí)間窗又涌入10個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，則將第二個(gè)時(shí)間窗中的虛擬網(wǎng)絡(luò)請(qǐng)求按其受益從大到小優(yōu)先級(jí)分別設(shè)為11至20。然后優(yōu)先處理第一個(gè)時(shí)間窗中優(yōu)先級(jí)為11的虛擬網(wǎng)絡(luò)請(qǐng)求，再處理第二個(gè)時(shí)間窗中優(yōu)先級(jí)為11的請(qǐng)求，之后再處理第一個(gè)時(shí)間窗中優(yōu)先級(jí)為12的請(qǐng)求，依此類推。

2 設(shè)計(jì)保持節(jié)點(diǎn)相鄰的虛擬網(wǎng)絡(luò)映射算法

本節(jié)針對(duì)完成映射后相鄰虛擬節(jié)點(diǎn)所對(duì)應(yīng)的物理節(jié)點(diǎn)過于分散的情況，提出了一種既考慮節(jié)點(diǎn)映射又考慮鏈路需求的保持節(jié)點(diǎn)相鄰的虛擬網(wǎng)絡(luò)映射算法。

如圖1所示，在虛網(wǎng)請(qǐng)求到達(dá)時(shí)，大多算法會(huì)將虛擬節(jié)點(diǎn)a、b、c分別映射到物理節(jié)點(diǎn)A、F、B。這樣，在虛擬網(wǎng)絡(luò)請(qǐng)求中相鄰的兩對(duì)節(jié)點(diǎn)（a與b，b與c）之間的距離就相對(duì)較遠(yuǎn)。但如果將虛擬節(jié)點(diǎn)a、b、c分別映射到物理節(jié)點(diǎn)A、D、E，則既能滿足節(jié)點(diǎn)需求，又能滿足鏈路需求，同時(shí)在虛擬網(wǎng)絡(luò)請(qǐng)求中相鄰的兩對(duì)節(jié)點(diǎn)在實(shí)際物理網(wǎng)絡(luò)中仍舊保持相鄰，大大減少了物理鏈路資源的耗費(fèi)，同時(shí)保持節(jié)點(diǎn)相鄰可以提高實(shí)際工作效率，從而提高了服務(wù)質(zhì)量。

圖1 節(jié)點(diǎn)資源優(yōu)先節(jié)點(diǎn)映射。（a）虛擬網(wǎng)絡(luò)請(qǐng)求；（b）物理網(wǎng)絡(luò)

2.1 物理資源與虛擬網(wǎng)絡(luò)請(qǐng)求的描述

物理資源和虛擬網(wǎng)絡(luò)請(qǐng)求可用無向加權(quán)圖表述。物理資源GP，GP=，其中，NP為物理結(jié)點(diǎn)集合，EP為物理鏈路集合，權(quán)(nP)指結(jié)點(diǎn)nP∈NP的屬性（如計(jì)算能力），權(quán)(eP)指鏈路eP∈EP的屬性（如帶寬大?。?。同理，虛網(wǎng)請(qǐng)求GV，GV=其中，權(quán)為虛擬結(jié)點(diǎn)的資源需求為虛擬鏈路的資源需求（如請(qǐng)求分配的計(jì)算能力和網(wǎng)絡(luò)帶寬等）。將GV部署到GP上的虛網(wǎng)映射記為M:GV→GP，其中，節(jié)點(diǎn)映射記為MN:NV→NP，鏈路映射記為ME:EV→EP。

2.2 割與k-割檢驗(yàn)

定義3（割）[21]N，網(wǎng)絡(luò)G=(N,E,AN,AE)的結(jié)點(diǎn)集合，對(duì)N的一個(gè)劃分稱為G的一個(gè)割。

其中MN(S)={nP|nP=MN(nV),nV∈S}。

定理1（可行性檢驗(yàn)定理）[22]當(dāng)且僅當(dāng)MN通過所有的k-割檢驗(yàn)，MN有可行的鏈路映射與之對(duì)應(yīng)，其中k∈[1,[|NV|/2]]。

文獻(xiàn)[30]表明，當(dāng)節(jié)點(diǎn)映射MN通過k-割檢驗(yàn)時(shí)，對(duì)應(yīng)存在可行鏈路映射的概率為93.9%，故可排除掉絕大部分不具備相應(yīng)可行鏈路映射的節(jié)點(diǎn)映射。本文所提算法需要k-割檢驗(yàn)時(shí)，都只進(jìn)行1-割檢驗(yàn)，1-割檢驗(yàn)的實(shí)例如圖2所示。

圖2 節(jié)點(diǎn)資源優(yōu)先節(jié)點(diǎn)映射

2.3 保持節(jié)點(diǎn)相鄰的虛擬網(wǎng)絡(luò)映射算法

本節(jié)提出的算法在略微降低映射效率的情況下，提升了映射成功率和物理資源，特別是物理鏈路得到高效利用，并使虛網(wǎng)請(qǐng)求中相鄰的節(jié)點(diǎn)在實(shí)際映射后的物理網(wǎng)路中盡可能保持相鄰，從而提升映射后虛擬網(wǎng)絡(luò)的運(yùn)行效率，提高了服務(wù)質(zhì)量并改善了映射效果。具體算法描述如下文。

圖3 給出了虛擬網(wǎng)絡(luò)請(qǐng)求和供映射的物理網(wǎng)絡(luò)，虛擬網(wǎng)絡(luò)請(qǐng)求a，b，c 三個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)需求分別為20，15，10，其間的鏈路需求分別為10，15，20，供映射的物理網(wǎng)絡(luò)A，B，C，D，E 五個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)資源分別為40，30，5，10，20，其間的鏈路資源分別為10，30，20，30，15。根據(jù)上述算法，首先尋找虛擬網(wǎng)絡(luò)請(qǐng)求中節(jié)點(diǎn)需求資源最大的節(jié)點(diǎn)，即為a 節(jié)點(diǎn)，然后尋找物理網(wǎng)絡(luò)中節(jié)點(diǎn)資源最多的節(jié)點(diǎn)，即為A 節(jié)點(diǎn)。經(jīng)過判斷，A節(jié)點(diǎn)的節(jié)點(diǎn)資源滿足需求，但是不能通過1-割檢驗(yàn)，所以去除A節(jié)點(diǎn)，再在剩余節(jié)點(diǎn)中尋找資源最多的節(jié)點(diǎn)，即B節(jié)點(diǎn)，其能夠滿足a節(jié)點(diǎn)的需求，又能通過1-割檢驗(yàn)，因此將虛擬節(jié)點(diǎn)a映射到物理節(jié)點(diǎn)B上，并更新B節(jié)點(diǎn)剩余資源為10。之后尋找與a節(jié)點(diǎn)相鄰的需求資源最多的虛擬節(jié)點(diǎn)，即為b節(jié)點(diǎn)，a，b節(jié)點(diǎn)間的虛擬鏈路需求為10。之后尋找與物理節(jié)點(diǎn)B相鄰且之間鏈路能夠滿足鏈路需求的節(jié)點(diǎn)，即為A和C，其中節(jié)點(diǎn)資源最多的是A節(jié)點(diǎn)。經(jīng)過判斷，A節(jié)點(diǎn)既能滿足b節(jié)點(diǎn)需求，又能通過1-割檢驗(yàn)，因此將b節(jié)點(diǎn)映射到A節(jié)點(diǎn)上，并更新A節(jié)點(diǎn)剩余資源為25。之后尋找虛擬網(wǎng)絡(luò)請(qǐng)求中與a節(jié)點(diǎn)相鄰的、除b節(jié)點(diǎn)外的，且節(jié)點(diǎn)資源需求最多的節(jié)點(diǎn)，即c節(jié)點(diǎn)，a，c節(jié)點(diǎn)間的虛擬鏈路需求為20。之后尋找物理資源中與B節(jié)點(diǎn)相鄰的、能夠滿足鏈路需求的節(jié)點(diǎn)中，節(jié)點(diǎn)剩余資源最大的節(jié)點(diǎn)，即C節(jié)點(diǎn)。經(jīng)過判斷，C節(jié)點(diǎn)不能滿足虛擬節(jié)點(diǎn)c的節(jié)點(diǎn)需求，而有沒有其他與A相鄰的節(jié)點(diǎn)，因此將已映射的虛擬節(jié)點(diǎn)a，b，物理節(jié)點(diǎn)B，A排除，將剩下的節(jié)點(diǎn)繼續(xù)回到算法最初開始進(jìn)行。尋找虛擬請(qǐng)求中需求資源最多的虛擬節(jié)點(diǎn)，即c節(jié)點(diǎn)。之后尋找物理網(wǎng)絡(luò)中節(jié)點(diǎn)資源最多的節(jié)點(diǎn)，即E 節(jié)點(diǎn)。經(jīng)過判斷，物理節(jié)點(diǎn)E 能夠滿足虛擬節(jié)點(diǎn)c 的節(jié)點(diǎn)資源需求，并且能夠通過1-割檢驗(yàn)，因此將c節(jié)點(diǎn)映射到物理節(jié)點(diǎn)E上，從而完成映射。算法具體步驟如

圖3 保持節(jié)點(diǎn)相鄰的虛擬網(wǎng)絡(luò)映射算法實(shí)例

步驟1：記虛擬節(jié)點(diǎn)集合為N(nV)，物理節(jié)點(diǎn)集合為N(nP)；

步驟2：若集合N(nV)為空，則映射成功，結(jié)束算法；若集合N(nV)不為空，則尋找集合N(nV)中節(jié)點(diǎn)資源要求最高的虛擬節(jié)點(diǎn)，記為節(jié)點(diǎn)

步驟3：尋找集合N(nP)中剩余節(jié)點(diǎn)資源最多的物理節(jié)點(diǎn)，若其能夠滿足節(jié)點(diǎn)的需求，并且能夠通過1-割檢驗(yàn)，則將其記為節(jié)點(diǎn)若其能夠滿足節(jié)點(diǎn)的需求，但不能夠通過1-割檢驗(yàn)，則將其排除出集合N(nP)，返回步驟3重新執(zhí)行；若其不能滿足節(jié)點(diǎn)的需求，則映射失敗；

步驟6：在N()中尋找需求最大的虛擬節(jié)點(diǎn)，記為節(jié)點(diǎn)，且節(jié)點(diǎn)與節(jié)點(diǎn)之間的虛擬鏈路為；

步驟8：尋找集合N中節(jié)點(diǎn)資源最多的節(jié)點(diǎn)，若其不能滿足節(jié)點(diǎn)的需求，則將節(jié)點(diǎn)排除出集合N，跳至步驟6；若是能夠滿足節(jié)點(diǎn)的需求但不能夠通過1-割檢驗(yàn)，則將其排除出集合N，返回步驟8重新執(zhí)行；若最終未能找到可行的節(jié)點(diǎn)或已不存在滿足鏈路需求的鏈路，則將虛擬節(jié)點(diǎn)排除出集合N，跳至步驟6；若尋找到的節(jié)點(diǎn)能夠滿足節(jié)點(diǎn)的需求且通過1-割檢驗(yàn)，則將其記為節(jié)點(diǎn)若是集合N中所有虛擬節(jié)點(diǎn)都已經(jīng)通過步驟8 但沒有成功映射，則更新集合N(nV)為還未被映射的虛擬節(jié)點(diǎn)集合，跳至步驟2；若是集合N中所有虛擬節(jié)點(diǎn)都已經(jīng)通過步驟8且成功映射，則跳至步驟11；

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

本文采用自主設(shè)計(jì)的虛擬網(wǎng)絡(luò)映射仿真器進(jìn)行仿真實(shí)驗(yàn)。其中，網(wǎng)絡(luò)拓?fù)淝闆r（包括虛擬網(wǎng)絡(luò)請(qǐng)求虛擬節(jié)點(diǎn)個(gè)數(shù)、虛擬節(jié)點(diǎn)的節(jié)點(diǎn)資源、鏈路狀況、物理節(jié)點(diǎn)、鏈路資源等）由GT-ITM[23]隨機(jī)生成。仿真器通過設(shè)置不同的參數(shù)（如虛擬網(wǎng)絡(luò)請(qǐng)求虛擬節(jié)點(diǎn)個(gè)數(shù)取值范圍、虛擬節(jié)點(diǎn)的節(jié)點(diǎn)資源取值范圍等）來模擬不同的虛擬網(wǎng)絡(luò)請(qǐng)求與物理網(wǎng)絡(luò)環(huán)境。在各種情況下，對(duì)保持節(jié)點(diǎn)相鄰的虛擬網(wǎng)絡(luò)映射算法（以下稱本算法）進(jìn)行仿真，并將其與經(jīng)典的兩步式虛擬網(wǎng)絡(luò)映射算法（以下稱兩步式算法）進(jìn)行比較。

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

（1）虛擬網(wǎng)絡(luò)請(qǐng)求與物理網(wǎng)絡(luò)環(huán)境情況A

根據(jù)表1設(shè)置，得到仿真結(jié)果如圖4～6所示。從映射結(jié)果看，在物理資源充足的網(wǎng)絡(luò)環(huán)境下，兩種算法都有很高的映射成功率，而在保持節(jié)點(diǎn)相鄰、提高物理鏈路利用率、優(yōu)化映射效果的目標(biāo)來看，本算法雖然會(huì)隨虛擬鏈路存在概率的升高（即虛擬網(wǎng)絡(luò)請(qǐng)求的拓?fù)鋸?fù)雜度升高）而降低效果，但始終比兩步式算法高很多，也就是說映射效果要好很多?？梢钥闯?，兩種算法都比較好地做到了節(jié)點(diǎn)壓力的均衡，其中兩步式算法表現(xiàn)更為出色一些。

表1 虛擬網(wǎng)絡(luò)請(qǐng)求與底層物理網(wǎng)絡(luò)的生成相關(guān)參數(shù)

圖4 映射成功率隨虛擬鏈路存在概率變化

圖5 虛擬網(wǎng)絡(luò)請(qǐng)求仍舊相鄰的比率隨虛擬鏈路存在概率變化

圖6 物理節(jié)點(diǎn)利用率的方差隨虛擬鏈路存在概率變化

（2）虛擬網(wǎng)絡(luò)請(qǐng)求與物理網(wǎng)絡(luò)環(huán)境情況B

根據(jù)表2設(shè)置，得到仿真結(jié)果如圖7～9所示。從映射結(jié)果看，隨著虛擬網(wǎng)絡(luò)請(qǐng)求虛擬節(jié)點(diǎn)個(gè)數(shù)取值范圍的增加（即虛擬網(wǎng)絡(luò)請(qǐng)求擴(kuò)大），尤其是虛擬節(jié)點(diǎn)個(gè)數(shù)超過物理節(jié)點(diǎn)個(gè)數(shù)一半時(shí)，兩種算法的映射成功率都有明顯下降。當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求中虛擬鏈路的需求相對(duì)于物理鏈路資源較高時(shí)，本算法的映射成功率明顯高于兩步式算法。同時(shí)，通過圖8 也可得出，當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求中虛擬鏈路的需求相對(duì)于物理鏈路資源較高時(shí)，本算法相對(duì)于兩步式算法仍可達(dá)到一個(gè)較好的虛擬網(wǎng)絡(luò)請(qǐng)求中相鄰節(jié)點(diǎn)映射后仍舊相鄰的比率，也就是能提高虛擬鏈路的利用率，從而達(dá)到一個(gè)較好的映射效果。由物理節(jié)點(diǎn)利用率的方差均較低可以看出，兩種算法都較好地做到了節(jié)點(diǎn)壓力的均衡，而其中兩步式算法表現(xiàn)更為出色一些。

表2 虛擬網(wǎng)絡(luò)請(qǐng)求與底層物理網(wǎng)絡(luò)的生成相關(guān)參數(shù)

圖7 映射成功率隨虛擬節(jié)點(diǎn)個(gè)數(shù)取值變化

圖8 虛擬網(wǎng)絡(luò)請(qǐng)求中仍舊相鄰的比率隨虛擬節(jié)點(diǎn)個(gè)數(shù)取值變化

圖9 物理節(jié)點(diǎn)利用率的方差隨虛擬節(jié)點(diǎn)個(gè)數(shù)取值變化

（3）虛擬網(wǎng)絡(luò)請(qǐng)求與物理網(wǎng)絡(luò)環(huán)境情況C

根據(jù)表3設(shè)置，仿真結(jié)果如圖10～12所示。從映射結(jié)果看，虛擬網(wǎng)絡(luò)請(qǐng)求中虛擬節(jié)點(diǎn)資源的取值變化對(duì)這兩種算法各方面影響都不是很大。但是，從圖10 可以明顯地反映出在這種情況下本算法映射成功率普遍高于兩步式算法。同時(shí)，由圖11可知，本算法映射在提高物理鏈路利用率、提高服務(wù)質(zhì)量、優(yōu)化映射結(jié)果方面要明顯優(yōu)于兩步式算法。由圖12 可知，虛擬網(wǎng)絡(luò)請(qǐng)求中虛擬節(jié)點(diǎn)資源的取值范圍的提高會(huì)降低節(jié)點(diǎn)壓力的均衡程度，雖然上升幅度很大，但絕對(duì)數(shù)值卻很小，因此可以說兩種算法在節(jié)點(diǎn)壓力均衡上都表現(xiàn)良好。

表3 虛擬網(wǎng)絡(luò)請(qǐng)求與底層物理網(wǎng)絡(luò)的生成相關(guān)參數(shù)

圖11 虛擬網(wǎng)絡(luò)請(qǐng)求中仍舊相鄰的比率隨虛擬節(jié)點(diǎn)資源的取值變化

圖12 物理節(jié)點(diǎn)利用率的方差隨虛擬節(jié)點(diǎn)資源的取值變化

（4）虛擬網(wǎng)絡(luò)請(qǐng)求與物理網(wǎng)絡(luò)環(huán)境情況D

根據(jù)表4設(shè)置，仿真結(jié)果如圖13～15所示。從映射結(jié)果看，在虛擬網(wǎng)絡(luò)請(qǐng)求中虛擬鏈路資源需求相對(duì)于物理鏈路資源較低時(shí)，兩種算法都能保證比較高的映射成功率。而當(dāng)虛擬鏈路資源相對(duì)于物理鏈路資源變得較大時(shí)，兩種算法的映射成功率都有明顯下降。由圖13可知，本算法的映射成功率在苛刻的鏈路條件下會(huì)高于兩步式算法。而作為本算法的主要目標(biāo)，由圖14可知，虛擬網(wǎng)絡(luò)請(qǐng)求中相鄰節(jié)點(diǎn)映射后仍舊相鄰的比率在各種虛擬鏈路條件下都比兩步式算法高得多，可見其在提高物理鏈路資源利用率、優(yōu)化映射結(jié)果、提高服務(wù)質(zhì)量方面做得很好。由圖15反映出的較低物理節(jié)點(diǎn)利用率的方差可知，兩種算法在節(jié)點(diǎn)壓力均衡方面都表現(xiàn)優(yōu)良，而本算法只是略微遜色一些。

表4 虛擬網(wǎng)絡(luò)請(qǐng)求與底層物理網(wǎng)絡(luò)的生成相關(guān)參數(shù)

圖13 映射成功率隨虛擬網(wǎng)絡(luò)請(qǐng)求中虛擬鏈路資源的取值變化

圖14 虛擬網(wǎng)絡(luò)請(qǐng)求中仍舊相鄰的比率隨虛擬鏈路資源的取值變化

圖15 物理節(jié)點(diǎn)利用率的方差隨虛擬鏈路資源的取值變化

4 結(jié)束語

相比于經(jīng)典兩步式算法，本算法在相對(duì)物理資源充足、虛擬網(wǎng)絡(luò)請(qǐng)求節(jié)點(diǎn)資源需求較大、虛擬網(wǎng)絡(luò)請(qǐng)求鏈路資源需求較大等幾種情況下都有不錯(cuò)的映射成功率。在虛擬網(wǎng)絡(luò)請(qǐng)求中，只有虛擬鏈路資源需求相對(duì)于實(shí)際物理鏈路資源要求苛刻時(shí)，才會(huì)存在比較低的映射成功率。因此，在絕大多數(shù)虛擬網(wǎng)絡(luò)映射中，本算法可行性比較高，且在虛擬網(wǎng)絡(luò)請(qǐng)求中相鄰節(jié)點(diǎn)映射后仍舊相鄰的比率在虛擬網(wǎng)絡(luò)請(qǐng)求與物理網(wǎng)絡(luò)環(huán)境情況中都表現(xiàn)出色，同時(shí)在提高物理鏈路資源利用率、優(yōu)化虛擬網(wǎng)絡(luò)映射效果、提高映射后的服務(wù)質(zhì)量方面非常好。在對(duì)虛擬網(wǎng)絡(luò)映射結(jié)果要求較高情況下的適用性很高，并且在保持節(jié)點(diǎn)壓力均衡方面也較出色，達(dá)到了現(xiàn)今對(duì)于網(wǎng)絡(luò)負(fù)載均衡方面的需求。