一種自適應(yīng)擴(kuò)展的虛擬網(wǎng)絡(luò)映射算法

彭利民

(1.廣州體育學(xué)院計(jì)算機(jī)教研室，廣州510500;2.華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣州510006)

隨著互聯(lián)網(wǎng)新型應(yīng)用的層出不窮，不同的應(yīng)用對(duì)底層物理網(wǎng)絡(luò)在安全性、服務(wù)質(zhì)量和可擴(kuò)展性等方面提出了不同的需求. 現(xiàn)有的互聯(lián)網(wǎng)架構(gòu)很難滿足新型應(yīng)用的發(fā)展需求，在某種程度上呈現(xiàn)出僵化現(xiàn)象，導(dǎo)致一些新型應(yīng)用很難應(yīng)用到現(xiàn)有的網(wǎng)絡(luò)架構(gòu)上［1］. 虛擬網(wǎng)絡(luò)映射允許多個(gè)虛擬網(wǎng)絡(luò)(Virtual Network，VN)運(yùn)行在同一個(gè)物理網(wǎng)絡(luò)(Substrate Network，SN)之上，被公認(rèn)為是解決當(dāng)前互聯(lián)網(wǎng)架構(gòu)問(wèn)題的有效手段.在網(wǎng)絡(luò)虛擬化環(huán)境下，傳統(tǒng)的互聯(lián)網(wǎng)服務(wù)運(yùn)營(yíng)商被分為了2個(gè)角色:一個(gè)是底層基礎(chǔ)設(shè)施運(yùn)營(yíng)商，負(fù)責(zé)部署和維護(hù)底層網(wǎng)絡(luò)資源，另一個(gè)是服務(wù)提供商，負(fù)責(zé)租用一個(gè)或多個(gè)底層基礎(chǔ)設(shè)施提供商提供的底層網(wǎng)絡(luò)資源，為用戶提供定制的、可擴(kuò)展的網(wǎng)絡(luò)服務(wù)［2］.

虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化中的關(guān)鍵問(wèn)題，文獻(xiàn)［3］將虛擬網(wǎng)絡(luò)映射分為節(jié)點(diǎn)映射和鏈路映射，首先采用貪婪算法將資源需求較大的虛擬節(jié)點(diǎn)映射到可用資源量較多的物理節(jié)點(diǎn)上，然后利用K-最短路徑算法完成虛擬鏈路的映射操作. 在文獻(xiàn)［3］的基礎(chǔ)上，文獻(xiàn)［4］在節(jié)點(diǎn)映射過(guò)程中綜合考慮了虛擬節(jié)點(diǎn)和物理網(wǎng)絡(luò)中節(jié)點(diǎn)之間的位置關(guān)系，將虛擬網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò)的局部區(qū)域內(nèi). 雖然這些算法的執(zhí)行效率較高，但兩階段的映射方法破壞了節(jié)點(diǎn)和鏈路之間的耦合關(guān)系，使虛擬網(wǎng)絡(luò)映射的質(zhì)量受到影響.文獻(xiàn)［5］通過(guò)擴(kuò)展物理網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路，將虛擬網(wǎng)絡(luò)映射轉(zhuǎn)化為混合整數(shù)規(guī)劃問(wèn)題，然后利用整數(shù)規(guī)劃松弛算法協(xié)調(diào)完成節(jié)點(diǎn)和鏈路的映射操作，但整數(shù)規(guī)劃算法的時(shí)間復(fù)雜度較高，算法的執(zhí)行效率受到影響;在文獻(xiàn)［5］的基礎(chǔ)上，文獻(xiàn)［6］將所有符合條件的物理節(jié)點(diǎn)都作為虛擬節(jié)點(diǎn)的候選宿主，擴(kuò)大了宿主的選擇空間，同時(shí)選擇那些分布緊湊的節(jié)點(diǎn)作宿主，將相鄰的虛擬節(jié)點(diǎn)映射到鄰近的物理節(jié)點(diǎn)之上，減少虛擬鏈路對(duì)網(wǎng)絡(luò)資源的占用，但該算法仍然沒(méi)有考慮虛擬節(jié)點(diǎn)間的鄰接關(guān)系，相鄰的虛擬節(jié)點(diǎn)被映射到物理網(wǎng)絡(luò)中無(wú)法保持相鄰關(guān)系，增加了虛擬網(wǎng)絡(luò)映射的資源開銷. 文獻(xiàn)［7］將物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)描述為帶權(quán)有向圖，然后采用同構(gòu)子圖搜索方法，在同一階段內(nèi)協(xié)調(diào)完成節(jié)點(diǎn)映射和鏈路的映射操作. 針對(duì)文獻(xiàn)［7］在映射過(guò)程中僅考慮節(jié)點(diǎn)自身資源能力的局限性，文獻(xiàn)［8］在虛擬網(wǎng)絡(luò)映射過(guò)程中綜合考慮節(jié)點(diǎn)的資源屬性和網(wǎng)絡(luò)拓?fù)鋵傩?，盡管這2個(gè)算法在同構(gòu)子圖搜索時(shí)限制了回溯次數(shù)(4n 次)，但時(shí)間復(fù)雜度仍然較高，在虛擬網(wǎng)絡(luò)映射過(guò)程中沒(méi)有考慮虛擬網(wǎng)絡(luò)中節(jié)點(diǎn)之間的鄰接關(guān)系，增加了虛擬網(wǎng)絡(luò)映射的資源開銷.

綜上所述，現(xiàn)有的虛擬網(wǎng)絡(luò)映射算法主要存在以下問(wèn)題:(1)兩階段的虛擬網(wǎng)絡(luò)映射算法破壞了節(jié)點(diǎn)和鏈路之間固有的拓?fù)潢P(guān)系，并且在節(jié)點(diǎn)映射階段無(wú)法預(yù)見鏈路映射階段的網(wǎng)絡(luò)狀態(tài)，使虛擬網(wǎng)絡(luò)映射的性能受到影響;(2)采用整數(shù)規(guī)劃松弛算法和同構(gòu)子圖搜索回溯算法的時(shí)間復(fù)雜度太高，不適合處理動(dòng)態(tài)的虛擬網(wǎng)絡(luò)映射問(wèn)題;(3)虛擬網(wǎng)絡(luò)映射過(guò)程中沒(méi)有考慮虛擬網(wǎng)絡(luò)中節(jié)點(diǎn)間的鄰接關(guān)系，導(dǎo)致虛擬網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路被映射到物理網(wǎng)絡(luò)，無(wú)法保持原有的拓?fù)潢P(guān)系，降低了虛擬網(wǎng)絡(luò)映射的質(zhì)量;(4)在虛擬網(wǎng)絡(luò)映射過(guò)程中，沒(méi)有考慮節(jié)點(diǎn)和鏈路的資源狀態(tài)，物理網(wǎng)絡(luò)中的資源分布易呈現(xiàn)不均衡分布問(wèn)題，使虛擬網(wǎng)絡(luò)映射的質(zhì)量受到影響.針對(duì)這些問(wèn)題，本文根據(jù)節(jié)點(diǎn)和鏈路狀態(tài)，自適應(yīng)擴(kuò)展物理網(wǎng)絡(luò)結(jié)構(gòu)，將相鄰的虛擬節(jié)點(diǎn)和鏈路映射到鄰接的物理節(jié)點(diǎn)和鏈路上，使虛擬網(wǎng)絡(luò)成為物理網(wǎng)絡(luò)或λ 擴(kuò)展物理網(wǎng)絡(luò)的同構(gòu)子圖，協(xié)調(diào)映射虛擬節(jié)點(diǎn)及其鄰接虛擬鏈路，使虛擬網(wǎng)絡(luò)被映射后應(yīng)盡可能地保持原有的拓?fù)浣Y(jié)構(gòu)，降低虛擬網(wǎng)絡(luò)映射的資源開銷.

1 虛擬網(wǎng)絡(luò)映射模型

1.1 問(wèn)題描述

虛擬網(wǎng)絡(luò)映射問(wèn)題可以抽象為圖論問(wèn)題.文中使用帶權(quán)無(wú)向圖Gs= (Ns，Es，，AE s)表示物理網(wǎng)絡(luò)，其中Ns和Es分別代表物理網(wǎng)絡(luò)節(jié)點(diǎn)集和物理鏈路集表示物理節(jié)點(diǎn)nsNs的資源屬性集合，它們通常指節(jié)點(diǎn)的計(jì)算、存儲(chǔ)和轉(zhuǎn)發(fā)等屬性;表示節(jié)點(diǎn)ni和nj之間物理鏈路es(ni，nj)Es的資源屬性集合，它們通常指物理鏈路的可用帶寬、時(shí)延等屬性.類似地，使用帶權(quán)無(wú)向圖Gv=(Nv，Ev，)表示虛擬網(wǎng)絡(luò)請(qǐng)求，其中Nv和Ev分別表示虛擬網(wǎng)絡(luò)節(jié)點(diǎn)集和虛擬鏈路集，表示虛擬節(jié)點(diǎn)nvNv的資源屬性集，表示虛擬節(jié)點(diǎn)ni和nj之間虛擬鏈路ev(ni，nj)Ev的資源屬性集.

虛擬網(wǎng)絡(luò)映射是指從Gv到G's的一個(gè)映射M:Gv→G's(Ns，Ps)，其中G's是Gs的一個(gè)子圖，Ps表示Gs中無(wú)環(huán)物理路徑集.虛擬網(wǎng)絡(luò)映射M 需同時(shí)滿足以下3個(gè)基本條件:(1)每一個(gè)虛擬節(jié)點(diǎn)i，?iNv映射到不同的物理節(jié)點(diǎn)M(i)之上;(2)每一條虛擬鏈路ev(i，j)Ev，?evEv映射到一條無(wú)環(huán)的物理路徑p(is，js)Ps之上，并滿足M(i)=is，M(j)=js;(3)虛擬網(wǎng)絡(luò)映射需滿足所有虛擬節(jié)點(diǎn)和虛擬鏈路的資源約束條件，則稱M 是一個(gè)可行的虛擬網(wǎng)絡(luò)映射方案.

1.2 自適應(yīng)擴(kuò)展網(wǎng)絡(luò)模型

給定2個(gè)圖G1(V1，E1)和G2(V2，E2)，同構(gòu)子圖映射是指存在一個(gè)映射M:N1→N2，并滿足(u，v)E1?(M(u)，M(v))E2，?u，vV1.同構(gòu)子圖映射是一對(duì)一的映射方式，一個(gè)虛擬節(jié)點(diǎn)映射到一個(gè)物理節(jié)點(diǎn)上，一條虛擬鏈路映射到一條物理鏈路上.由于虛擬網(wǎng)絡(luò)請(qǐng)求拓?fù)浣Y(jié)構(gòu)的多樣性，物理網(wǎng)絡(luò)不可能存在所有虛擬網(wǎng)絡(luò)的同構(gòu)子圖.針對(duì)這個(gè)問(wèn)題，文中根據(jù)節(jié)點(diǎn)和鏈路的資源狀態(tài)，利用自適應(yīng)擴(kuò)展因子λ 對(duì)物理網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)擴(kuò)展，構(gòu)造一個(gè)自適應(yīng)擴(kuò)展的物理網(wǎng)絡(luò)模型，使虛擬網(wǎng)絡(luò)成為擴(kuò)展物理網(wǎng)絡(luò)的同構(gòu)子圖，從而有效地解決虛擬網(wǎng)絡(luò)映射問(wèn)題.)表示λ 擴(kuò)展物理網(wǎng)絡(luò)結(jié)構(gòu)，其中，=Es∪{e(u，v)|1 ＜hop(u，v)≤λ，?u，vNs}，hop(u，v)表示節(jié)點(diǎn)u 和節(jié)點(diǎn)v 之間的路由跳數(shù)，λ 為自適應(yīng)擴(kuò)張因子. 圖1B 是圖1A 的部分節(jié)點(diǎn)擴(kuò)展后的物理網(wǎng)絡(luò)結(jié)構(gòu).

圖1 擴(kuò)展物理網(wǎng)絡(luò)實(shí)例Figure 1 An example of augmenting substrate network

對(duì)物理網(wǎng)絡(luò)進(jìn)行λ 擴(kuò)展后，物理節(jié)點(diǎn)u 將新增Ω(u)個(gè)鄰居節(jié)點(diǎn)和η(u)條連接節(jié)點(diǎn)u 和Ω(u)中節(jié)點(diǎn)的鄰接鏈路，Ω(u)={vNs|1 ＜hop(u，v)≤λ}，η(u)={e(u，v)|u，vNs∧vΩ(u)}，其中，η(u)表示節(jié)點(diǎn)u 到Ω(u)中節(jié)點(diǎn)之間物理路徑上的可用帶寬.如圖1 所示，當(dāng)λ 為2 時(shí)，物理網(wǎng)絡(luò)進(jìn)行擴(kuò)展后，節(jié)點(diǎn)A 新增了2個(gè)物理鄰居節(jié)點(diǎn)F 和G，以及2 條物理鄰接鏈路(A，F(xiàn))和(A，G)，它們的可用帶寬分別為30 和10.

1.3 優(yōu)化模型

虛擬網(wǎng)絡(luò)映射的主要研究目標(biāo)是指在滿足虛擬節(jié)點(diǎn)和虛擬鏈路的資源約束條件下，通過(guò)優(yōu)化分配物理網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路資源，提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率和網(wǎng)絡(luò)收益.

(1)虛擬鏈路擴(kuò)張系數(shù). 虛擬鏈路的映射路徑長(zhǎng)度表示虛擬鏈路在物理網(wǎng)絡(luò)中的映射物理路徑長(zhǎng)度，它可以用于表示虛擬鏈路映射消耗的物理鏈路帶寬資源量.虛擬鏈路擴(kuò)張系數(shù)表示虛擬網(wǎng)絡(luò)中所有虛擬鏈路的映射路徑長(zhǎng)度的平均值，它可定義為

(2)網(wǎng)絡(luò)收益與開銷比. 當(dāng)虛擬網(wǎng)絡(luò)被成功映射后，網(wǎng)絡(luò)收益是指虛擬網(wǎng)絡(luò)中節(jié)點(diǎn)的CPU 資源量和鏈路的帶寬資源量總和.類似地，網(wǎng)絡(luò)開銷是指虛擬網(wǎng)絡(luò)中虛擬節(jié)點(diǎn)實(shí)際消耗的CPU 資源量和虛擬鏈路實(shí)際消耗的帶寬資源量總和，因此網(wǎng)絡(luò)收益與開銷比可表示為

(3)節(jié)點(diǎn)、鏈路的負(fù)載強(qiáng)度.在虛擬網(wǎng)絡(luò)映射過(guò)程中，一方面要盡量保證物理網(wǎng)絡(luò)中的節(jié)點(diǎn)資源均衡分布，另一方面也要盡量保證物理網(wǎng)絡(luò)中的鏈路資源均衡分布，從而提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率和物理網(wǎng)絡(luò)資源的利用率. 為了量化物理網(wǎng)絡(luò)的負(fù)載均衡程度，文中使用負(fù)載強(qiáng)度刻畫節(jié)點(diǎn)和鏈路的資源狀態(tài).節(jié)點(diǎn)的負(fù)載強(qiáng)度是指已利用的CPU 資源量和它的CPU 資源總量之比，它可表示為

其中nv→ns表示虛擬節(jié)點(diǎn)nv映射到物理節(jié)點(diǎn)ns上;cpu(ns)表示物理節(jié)點(diǎn)ns的CPU 資源總量;als(Ns)表示物理網(wǎng)絡(luò)中節(jié)點(diǎn)的平均負(fù)載均衡度，反映了物理網(wǎng)絡(luò)中節(jié)點(diǎn)資源的分布狀態(tài)，該值越小，物理網(wǎng)絡(luò)中節(jié)點(diǎn)資源分布越均衡，虛擬網(wǎng)絡(luò)映射的質(zhì)量越高.類似地，鏈路的負(fù)載強(qiáng)度指已利用的鏈路帶寬和它的總帶寬量之比，它可表示為

其中ev→es表示虛擬鏈路ev映射到物理鏈路es上;bw(es)表示物理鏈路es的帶寬資源總量;ls(es)表示物理路徑es的負(fù)載強(qiáng)度;als(Es)表示物理網(wǎng)絡(luò)中鏈路的平均負(fù)載強(qiáng)度，可以反映物理網(wǎng)絡(luò)中鏈路資源的分布狀態(tài)，該值越小，物理鏈路的負(fù)載越均衡，虛擬網(wǎng)絡(luò)映射的質(zhì)量越高.

2 虛擬網(wǎng)絡(luò)映射算法

為了減少虛擬網(wǎng)絡(luò)映射的資源開銷，虛擬網(wǎng)絡(luò)被映射后應(yīng)盡可能地保持原有的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu). 針對(duì)這個(gè)目標(biāo)，AAG-VNM 算法根據(jù)節(jié)點(diǎn)和鏈路的資源狀態(tài)，自適應(yīng)地?cái)U(kuò)展物理網(wǎng)絡(luò)，將相鄰的虛擬節(jié)點(diǎn)和其鄰接鏈路映射到鄰接的物理節(jié)點(diǎn)和鄰接的物理鏈路或物理路徑上，使虛擬網(wǎng)絡(luò)成為物理網(wǎng)絡(luò)或λ擴(kuò)展物理網(wǎng)絡(luò)的同構(gòu)子圖，從而降低虛擬網(wǎng)絡(luò)映射的資源開銷.

算法1 AAG-VNM 算法

(1)對(duì)虛擬網(wǎng)絡(luò)進(jìn)行深度優(yōu)先遍歷，構(gòu)造虛擬節(jié)點(diǎn)映射序列;

(2)將第1個(gè)虛擬節(jié)點(diǎn)u 隨機(jī)地映射到物理網(wǎng)絡(luò)中滿足節(jié)點(diǎn)u 的CPU 資源需求的物理節(jié)點(diǎn)上;

(3)如果節(jié)點(diǎn)u 映射成功，則將虛擬節(jié)點(diǎn)u 和對(duì)應(yīng)的物理節(jié)點(diǎn)M(u)分別加入已映射虛擬節(jié)點(diǎn)集Q 和已映射物理節(jié)點(diǎn)集P 中;

(4)從虛擬節(jié)點(diǎn)映射序列中的第2個(gè)節(jié)點(diǎn)i 開始，依次按照以下步驟進(jìn)行虛擬網(wǎng)絡(luò)映射操作:

①如果M(u)存在一個(gè)尚未參加映射的鄰居節(jié)點(diǎn)j，j 的CPU 資源量滿足節(jié)點(diǎn)i 的CPU 資源需求，且物理鏈路(M(u)，j)的帶寬資源量和時(shí)延滿足虛擬鏈路(u，i)的帶寬需求，那么將虛擬節(jié)點(diǎn)i 映射到物理節(jié)點(diǎn)j 上，同時(shí)將虛擬鏈路(u，i)映射到物理鏈路(M(u)，j)上，并分別將節(jié)點(diǎn)i 和節(jié)點(diǎn)j 加入集合Q 和P 中;如果M(u)存在多個(gè)滿足映射條件的鄰居節(jié)點(diǎn)，則優(yōu)先選擇節(jié)點(diǎn)的負(fù)載強(qiáng)度和鏈路的負(fù)載強(qiáng)度相對(duì)較小的鄰居節(jié)點(diǎn)進(jìn)行映射操作;

②否則，λ 值從2 開始逐漸遞增到δ，然后對(duì)物理網(wǎng)絡(luò)進(jìn)行λ 擴(kuò)展，并按照步驟①的映射方法將虛擬節(jié)點(diǎn)i 和其鄰接鏈路映射到λ 擴(kuò)展物理網(wǎng)絡(luò)中，直到映射成功;當(dāng)λ 值達(dá)到閾值δ 時(shí)還沒(méi)找到滿足節(jié)點(diǎn)和鏈路需求的鄰居節(jié)點(diǎn)和鄰接鏈路，則終止算法，映射失敗;

③如果虛擬節(jié)點(diǎn)i 和集合Q 中的節(jié)點(diǎn)之間還有未映射的虛擬鏈路，則使用K-最短路徑算法［9］搜索滿足條件的物理路徑，并優(yōu)先將虛擬鏈路映射到負(fù)載強(qiáng)度相對(duì)較小的物理路徑上;

(5)當(dāng)所有虛擬節(jié)點(diǎn)和鏈路成功映射后，返回虛擬網(wǎng)絡(luò)映射結(jié)果.

AAG-VNM 算法的執(zhí)行時(shí)間主要表現(xiàn)在步驟②中，其時(shí)間復(fù)雜度為O(|Ns|·|Es| +δ|Ns|3)，其中|Ns|和|Es|分別為物理網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)和鏈路個(gè)數(shù)，δ 為自適應(yīng)擴(kuò)展因子.因此，AAG-VNM 算法的時(shí)間復(fù)雜度為O(|Nv|·|Ns|·|Es| +δ|Nv| |Ns|3)，其中|Nv|為虛擬網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù).

3 性能評(píng)估與分析

為了驗(yàn)證AAG-VNM 算法的有效性，文中通過(guò)仿真實(shí)驗(yàn)對(duì)AAG-VNM 算法的性能進(jìn)行測(cè)試. 為了便于比較，本文同時(shí)實(shí)現(xiàn)了文獻(xiàn)［4］和文獻(xiàn)［8］中的算法，它們分別標(biāo)記為TA-VNM 和VF-VNM.

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

與文獻(xiàn)［4］、［8］類似，仿真實(shí)驗(yàn)使用GT-ITM 工具［10］生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，每個(gè)物理網(wǎng)絡(luò)設(shè)置為100個(gè)節(jié)點(diǎn)和大約560 條物理鏈路，每個(gè)物理節(jié)點(diǎn)的CPU 資源量和物理鏈路的帶寬資源量在區(qū)間［50，100］內(nèi)均勻分布，每條物理鏈路的時(shí)延均設(shè)為5.每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的節(jié)點(diǎn)個(gè)數(shù)在區(qū)間［5，15］內(nèi)均勻分布，虛擬網(wǎng)絡(luò)請(qǐng)求的到達(dá)服從泊松分布，每秒平均到達(dá)5個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，任意一對(duì)虛擬節(jié)點(diǎn)之間的連接概率為0.5，虛擬網(wǎng)絡(luò)的生存時(shí)間服從指數(shù)分布，平均生存時(shí)間設(shè)置為10 s，虛擬鏈路的最大時(shí)延在［20，30］內(nèi)均勻分布，虛擬節(jié)點(diǎn)的CPU 資源需求量和虛擬鏈路的帶寬資源需求量在區(qū)間［0，β］內(nèi)均勻分布，當(dāng)β 值為50 時(shí)，節(jié)點(diǎn)CPU 資源需求量和鏈路的帶寬需求量最大為50，β 值越大，虛擬網(wǎng)絡(luò)映射的難度越大.除第一組實(shí)驗(yàn)β 值分別取30 和60 外，其他仿真實(shí)驗(yàn)β 值均為50. AAG-VNM 算法的自適應(yīng)擴(kuò)展閾值δ 設(shè)置為6.每次仿真實(shí)驗(yàn)的時(shí)間為10 min，取10 次實(shí)驗(yàn)的平均值為仿真實(shí)驗(yàn)的最終結(jié)果.

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

從圖2 可以看出，3個(gè)算法在β 值為30 時(shí)的平均執(zhí)行時(shí)間基本相等，β 值為60 時(shí)的平均執(zhí)行時(shí)間均呈增加趨勢(shì)，VF-VNM 算法的平均執(zhí)行時(shí)間最多.

如圖3 和圖4 所示，在物理網(wǎng)絡(luò)資源和虛擬網(wǎng)絡(luò)請(qǐng)求一定的情況下，AAG-VNM 算法的虛擬鏈路擴(kuò)張系數(shù)相對(duì)較小，網(wǎng)絡(luò)收益與開銷比相對(duì)較大，其主要原因是AAG-VNM 算法根據(jù)節(jié)點(diǎn)和鏈路的資源狀態(tài)，自適應(yīng)地?cái)U(kuò)展物理網(wǎng)絡(luò)，將相鄰的虛擬節(jié)點(diǎn)和鏈路映射到鄰接的物理節(jié)點(diǎn)和鏈路上，降低了虛擬鏈路的映射路徑長(zhǎng)度和虛擬網(wǎng)絡(luò)映射的資源開銷，因此提高了虛擬網(wǎng)絡(luò)映射的質(zhì)量.

圖2 算法的平均執(zhí)行時(shí)間圖Figure 2 Algorithms'running time under different β value

圖3 虛擬鏈路擴(kuò)張系數(shù)圖Figure 3 Stretch factor of virtual links

圖4 網(wǎng)絡(luò)收益與開銷比(β=30)Figure 4 Network revenue-to-cost ratio

如圖5 和圖6 所示，AAG-VNM 算法的平均負(fù)載強(qiáng)度相對(duì)較小，其主要原因是在虛擬網(wǎng)絡(luò)映射過(guò)程中，AAG-VNM 算法根據(jù)物理網(wǎng)絡(luò)資源的分布狀態(tài)，優(yōu)先選擇負(fù)載強(qiáng)度相對(duì)較小的物理節(jié)點(diǎn)和物理鏈路進(jìn)行映射操作，降低了物理節(jié)點(diǎn)和物理鏈路的平均負(fù)載強(qiáng)度.如圖7 所示，AAG-VNM 算法的虛擬網(wǎng)絡(luò)請(qǐng)求接受率相對(duì)較高，進(jìn)一步驗(yàn)證了AAGVNM 算法能根據(jù)節(jié)點(diǎn)、鏈路的資源狀態(tài)，通過(guò)采用自適應(yīng)擴(kuò)展物理網(wǎng)絡(luò)和負(fù)載均衡操作方法，不僅降低了虛擬網(wǎng)絡(luò)映射的資源開銷，而且均衡了物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的資源分布水平，有效地提高了虛擬網(wǎng)絡(luò)映射的質(zhì)量和物理網(wǎng)絡(luò)資源的利用率，獲得了較優(yōu)的資源分配性能.

圖5 物理節(jié)點(diǎn)的平均負(fù)載強(qiáng)度(β=30)Figure 5 Load stress of substrate nodes

圖6 物理鏈路的平均負(fù)載強(qiáng)度(β=30)Figure 6 Load stress of substrate links

圖7 虛擬網(wǎng)絡(luò)請(qǐng)求接受率(β=30)Figure 7 Acceptance ratio of virtual network requests

4 結(jié)語(yǔ)

針對(duì)現(xiàn)有虛擬網(wǎng)絡(luò)映射的主要問(wèn)題，本文根據(jù)物理網(wǎng)絡(luò)的資源分布狀態(tài)，采用自適應(yīng)擴(kuò)展物理網(wǎng)絡(luò)的映射方法，將節(jié)點(diǎn)映射和鏈路映射階段有機(jī)地綜合為一個(gè)映射過(guò)程，均衡地消耗物理網(wǎng)絡(luò)資源，協(xié)調(diào)地解決虛擬節(jié)點(diǎn)和虛擬鏈路的映射操作，使虛擬網(wǎng)絡(luò)成為物理網(wǎng)絡(luò)或λ 擴(kuò)展物理網(wǎng)絡(luò)的同構(gòu)子圖.仿真結(jié)果表明，AAG-VNM 算法提高了物理網(wǎng)絡(luò)的負(fù)載均衡性能，有效地降低了虛擬鏈路的映射路徑長(zhǎng)度，獲得了較優(yōu)的資源分配性能.由于底層物理網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路可能出現(xiàn)失效等問(wèn)題，從而導(dǎo)致多個(gè)虛擬網(wǎng)絡(luò)服務(wù)無(wú)法使用，在現(xiàn)有工作的基礎(chǔ)上，將進(jìn)一步研究容錯(cuò)性虛擬網(wǎng)絡(luò)映射問(wèn)題.

［1］李小玲，王懷民，丁博，等. 虛擬網(wǎng)絡(luò)映射問(wèn)題研究及其進(jìn)展［J］.軟件學(xué)報(bào)，2012，23(11):3009－3028.Li X L，Wang H M，Ding B，et al. Research and development of virtual network mapping problem［J］. Journal of Software，2012，23(11):3009－3028.

［2］劉光遠(yuǎn)，蘇森. 面向底層單節(jié)點(diǎn)失效的輕量級(jí)可靠虛擬網(wǎng)絡(luò)映射算法［J］.電子與信息學(xué)報(bào)，2013，35(11):2644－2649.Liu G Y，Su S. Less stringent reliable virtual network mapping algorithm for substrate single node failure［J］.Journal of Electronic ＆ Information Technology，2013，35(11):2644－2649.

［3］Yu M L，Yi Y，Jennifer R，et al. Rethinking virtual network embedding:Substrate support for path splitting and migration［J］. ACM Sigcomm Computer Communication Review，2008，38(2):17－29.

［4］Li X L，Wang H M，Guo C G，et al. Topology awareness algorithm for virtual network mapping［J］.Journal of Zhejiang University:Science C，2012，13(3):178－186.

［5］Chowdhury M，Rahman M R，Boutaba R. ViNEYard:Virtual network embedding algorithms with coordinated node and link mapping［J］. IEEE/ACM Transactions on Networking，2012，34(3):206－219.

［6］劉新剛，懷進(jìn)鵬，高慶一，等. 一種保持結(jié)點(diǎn)緊湊的虛擬網(wǎng)絡(luò)映射方法［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35(12):2492－2503.Liu X G，Huai J P，Gao Q Y，et al. A virtual network embedding approach to preserving node closeness［J］.Chinese Journal of Computers，2012，35(12):2492－2503.

［7］Lischka J，Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection［C］∥Proceeding of the 1st ACM workshop on virtualized infrastructure systems and architectures. Barcelona，Spain，2009:81－88.

［8］魏曉輝，鄒磊，李洪亮.基于優(yōu)化的同構(gòu)子圖搜索的虛擬網(wǎng)絡(luò)映射算法［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2013，43(1):165－171.Wei X H，Zou L，Li H L. Virtual network embedding algorithm based on improved sub-graph isomorphism search［J］. Journal of Jilin University:Engineering and Technology Edition，2013，43(1):165－171.

［9］Eppstein D. Finding the k shortest paths［J］. SIAM Journal of Computer，1994，28(2):652－763.

［10］Zegura E，Calvert K，Bhattacharjee S. How to model an internetwork［C］∥Proceeding of the 15th annual joint conference of the IEEE computer and communications society. San Francisco CA，USA，1996:594－602.