彭利民

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

1.3 優(yōu)化模型

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

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

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

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

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

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

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

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

算法1 AAG-VNM 算法

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

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

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

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

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

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

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

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

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

3 性能評估與分析

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

3.1 實驗設(shè)置

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

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

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

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

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

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

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

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

圖5 物理節(jié)點的平均負載強度(β=30)Figure 5 Load stress of substrate nodes

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

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

4 結(jié)語

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

［1］李小玲，王懷民，丁博，等. 虛擬網(wǎng)絡(luò)映射問題研究及其進展［J］.軟件學(xué)報，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］劉光遠，蘇森. 面向底層單節(jié)點失效的輕量級可靠虛擬網(wǎng)絡(luò)映射算法［J］.電子與信息學(xué)報，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］劉新剛，懷進鵬，高慶一，等. 一種保持結(jié)點緊湊的虛擬網(wǎng)絡(luò)映射方法［J］.計算機學(xué)報，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é)報:工學(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.