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

彭紅姣，潘子輝

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

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

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

1.1 現(xiàn)狀和問題

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

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

假設(shè)鏈路資源無限大，節(jié)點(diǎn)映射算法通常能取得非常好的效果，這些算法可有效提高物理節(jié)點(diǎn)資源的利用率，同時可保證節(jié)點(diǎn)相對緊湊（即節(jié)點(diǎn)間距離相對較?。６鴮嶋H上，鏈路資源不可能為無限大，這種理想情況并不存在。故此類節(jié)點(diǎn)映射算法通常會在鏈路映射上遇到困難，最典型的兩個虛擬節(jié)點(diǎn)所映射到的物理節(jié)點(diǎn)之間的物理鏈路資源，無法滿足其虛網(wǎng)請求中虛擬鏈路的需求。其次，如果優(yōu)先選擇帶寬資源較多的節(jié)點(diǎn)進(jìn)行映射，確實能很好地滿足對物理鏈路及物理節(jié)點(diǎn)資源的需求。但由于總是優(yōu)先占用帶寬資源最為充裕的節(jié)點(diǎn)，可能會對后來的虛擬網(wǎng)絡(luò)請求造成一定影響。另外，如將節(jié)點(diǎn)和鏈路映射分別執(zhí)行，對于虛網(wǎng)請求中相鄰或相近的節(jié)點(diǎn)，在映射后其對應(yīng)的物理節(jié)點(diǎn)在物理網(wǎng)絡(luò)中距離可能會非常遠(yuǎn)。這種分布分散的情況常常會導(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é)點(diǎn)映射和虛擬鏈路映射。在虛擬節(jié)點(diǎn)映射中先使用貪婪算法進(jìn)行求解，再在虛擬鏈路映射中使用k最短路徑算法進(jìn)行求解。

定義1映射收益是指映射到物理網(wǎng)絡(luò)成功后，虛網(wǎ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ò)映射算法中，先以時間窗為單位接收虛網(wǎng)請求。再根據(jù)映射收益R(GV)對一個時間窗內(nèi)的虛網(wǎng)請求由高到低排序，收益高優(yōu)先映射。若映射成功，則更新物理網(wǎng)絡(luò)狀態(tài)；若映射失敗，則將其列入等待隊列；若失敗次數(shù)超過預(yù)先設(shè)定的值，則放棄該虛擬網(wǎng)絡(luò)請求。

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

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

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

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

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

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

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

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

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

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

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

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

2.2 割與k-割檢驗

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

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

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

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

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

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

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

圖3 給出了虛擬網(wǎng)絡(luò)請求和供映射的物理網(wǎng)絡(luò)，虛擬網(wǎng)絡(luò)請求a，b，c 三個節(jié)點(diǎn)的節(jié)點(diǎn)需求分別為20，15，10，其間的鏈路需求分別為10，15，20，供映射的物理網(wǎng)絡(luò)A，B，C，D，E 五個節(jié)點(diǎn)的節(jié)點(diǎn)資源分別為40，30，5，10，20，其間的鏈路資源分別為10，30，20，30，15。根據(jù)上述算法，首先尋找虛擬網(wǎng)絡(luò)請求中節(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-割檢驗，所以去除A節(jié)點(diǎn)，再在剩余節(jié)點(diǎn)中尋找資源最多的節(jié)點(diǎn)，即B節(jié)點(diǎn)，其能夠滿足a節(jié)點(diǎn)的需求，又能通過1-割檢驗，因此將虛擬節(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-割檢驗，因此將b節(jié)點(diǎn)映射到A節(jié)點(diǎn)上，并更新A節(jié)點(diǎn)剩余資源為25。之后尋找虛擬網(wǎng)絡(luò)請求中與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)行。尋找虛擬請求中需求資源最多的虛擬節(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-割檢驗，因此將c節(jié)點(diǎn)映射到物理節(jié)點(diǎn)E上，從而完成映射。算法具體步驟如

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

步驟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-割檢驗，則將其記為節(jié)點(diǎn)若其能夠滿足節(jié)點(diǎn)的需求，但不能夠通過1-割檢驗，則將其排除出集合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-割檢驗，則將其排除出集合N，返回步驟8重新執(zhí)行；若最終未能找到可行的節(jié)點(diǎn)或已不存在滿足鏈路需求的鏈路，則將虛擬節(jié)點(diǎn)排除出集合N，跳至步驟6；若尋找到的節(jié)點(diǎn)能夠滿足節(jié)點(diǎn)的需求且通過1-割檢驗，則將其記為節(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 實驗分析

3.1 實驗環(huán)境

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

3.2 仿真實驗結(jié)果與分析

（1）虛擬網(wǎng)絡(luò)請求與物理網(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)來看，本算法雖然會隨虛擬鏈路存在概率的升高（即虛擬網(wǎng)絡(luò)請求的拓?fù)鋸?fù)雜度升高）而降低效果，但始終比兩步式算法高很多，也就是說映射效果要好很多。可以看出，兩種算法都比較好地做到了節(jié)點(diǎn)壓力的均衡，其中兩步式算法表現(xiàn)更為出色一些。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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