一種基于占有率反饋的虛擬網(wǎng)絡(luò)映射算法

王慕陽 陳立全　王翔 王延松 盧華

摘要

網(wǎng)絡(luò)虛擬化技術(shù)通過對(duì)物理資源的抽象，可以有效解決現(xiàn)有互聯(lián)網(wǎng)架構(gòu)中存在的網(wǎng)絡(luò)結(jié)構(gòu)僵化、可擴(kuò)展性差等問題。虛擬網(wǎng)絡(luò)映射問題是指將用戶發(fā)送的所有虛網(wǎng)請(qǐng)求映射到底層物理網(wǎng)絡(luò)中，同時(shí)還要滿足虛網(wǎng)請(qǐng)求中對(duì)各個(gè)資源的限制要求（如節(jié)點(diǎn)計(jì)算能力、鏈路帶寬等）。從節(jié)點(diǎn)負(fù)載平衡的角度出發(fā)，在基于就近原則的虛網(wǎng)映射算法基礎(chǔ)上，引入節(jié)點(diǎn)負(fù)載平衡的反饋機(jī)制，引導(dǎo)各個(gè)虛網(wǎng)請(qǐng)求更均勻地映射到底層物理網(wǎng)絡(luò)中。另外，在k短路徑算法機(jī)制中引入了當(dāng)前鏈路資源占有率作為評(píng)價(jià)參考標(biāo)準(zhǔn)，這樣可以盡可能均勻地分散鏈路壓力。同時(shí)，在檢驗(yàn)鏈路資源是否滿足虛網(wǎng)請(qǐng)求的過程中，由于優(yōu)先選中的鏈路資源占有率低，所以算法映射成功率高，映射耗時(shí)更短，虛擬網(wǎng)絡(luò)映射效率得到了有效提高。關(guān)鍵詞網(wǎng)絡(luò)虛擬化；虛網(wǎng)映射；占有率反饋；負(fù)載平衡；鏈路映射

中圖分類號(hào)TP242

文獻(xiàn)標(biāo)志碼A

收稿日期20160725

資助項(xiàng)目國家自然科學(xué)基金（61372103）；中興通訊產(chǎn)學(xué)研項(xiàng)目（2015ZTE0413）

作者簡介

王慕陽，男，碩士生，主要研究方向?yàn)樘摂M網(wǎng)絡(luò)映射機(jī)制與算法。wangmuyang@seu.edu.cn

陳立全（通信作者），男，博士，副教授，博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全.Lqchen@seu.edu.cn

1東南大學(xué)信息科學(xué)與工程學(xué)院，南京，210096

2中興通訊股份有限公司，深圳，518057

0 引言

網(wǎng)絡(luò)虛擬化是為解決網(wǎng)絡(luò)結(jié)構(gòu)僵化問題而提出的新興網(wǎng)絡(luò)技術(shù)。

網(wǎng)絡(luò)虛擬化技術(shù)的核心是虛擬網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路到物理網(wǎng)絡(luò)的映射。在實(shí)際應(yīng)用中，底層物理網(wǎng)絡(luò)承載多個(gè)虛擬網(wǎng)絡(luò)，需要消耗相應(yīng)的物理資源，包括節(jié)點(diǎn)CPU資源、鏈路帶寬等。當(dāng)有一個(gè)新的虛擬網(wǎng)絡(luò)請(qǐng)求需要映射到底層物理網(wǎng)絡(luò)上時(shí)，有些物理節(jié)點(diǎn)和鏈路已經(jīng)無法滿足新到來的虛網(wǎng)請(qǐng)求的資源需求，無法在其上映射此虛擬網(wǎng)絡(luò)。而且，如果虛擬網(wǎng)絡(luò)映射不合理，可能會(huì)出現(xiàn)各個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)流量需要經(jīng)過多個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)，增加額外的帶寬資源消耗，甚至?xí)驗(yàn)樗x節(jié)點(diǎn)之間的鏈路已經(jīng)沒有足夠的帶寬，而導(dǎo)致映射失敗?？梢?，當(dāng)前虛擬網(wǎng)絡(luò)發(fā)展急需要設(shè)計(jì)高效的虛擬網(wǎng)絡(luò)映射算法來將虛擬網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)和鏈路映射到物理網(wǎng)絡(luò)上，并希望在滿足虛網(wǎng)請(qǐng)求的資源需求的同時(shí)，盡可能地提高物理網(wǎng)絡(luò)的資源利用率，降低虛網(wǎng)映射的成本。

傳統(tǒng)的虛網(wǎng)映射算法較多是基于啟發(fā)式的兩步映射算法[13]。它們一般先進(jìn)行節(jié)點(diǎn)映射，再進(jìn)行鏈路映射。但目前的虛網(wǎng)映射算法大多基于對(duì)節(jié)點(diǎn)CPU和鏈路資源的貪心算法，這就導(dǎo)致物理網(wǎng)中具有較高CPU資源的節(jié)點(diǎn)及其周邊節(jié)點(diǎn)會(huì)被優(yōu)先映射，從而導(dǎo)致該部分節(jié)點(diǎn)已經(jīng)飽和而其他節(jié)點(diǎn)還尚未映射的情況發(fā)生，甚至?xí)l(fā)生所有虛網(wǎng)競(jìng)爭同一片物理網(wǎng)資源的情況，這對(duì)某一區(qū)域會(huì)形成較大的負(fù)載壓力。

除此之外，在兩步映射算法中，優(yōu)化方案的重點(diǎn)往往放在了節(jié)點(diǎn)映射算法中，對(duì)于鏈路映射算法，如果不支持路徑切割，則通常采用k短路徑算法作為最常見的鏈路算法模型[4]。k短路徑算法一般選取路徑最短的前k個(gè)映射方案，再依次驗(yàn)證這些路徑是否滿足虛網(wǎng)請(qǐng)求中的鏈路資源要求來實(shí)現(xiàn)算法。當(dāng)?shù)讓泳W(wǎng)絡(luò)支持路徑切割時(shí)，鏈路映射算法大多是基于多商品流的線性規(guī)劃進(jìn)行求解[5]。

針對(duì)各種拓?fù)浣Y(jié)構(gòu)，文獻(xiàn)[6]提出了一種針對(duì)星狀拓?fù)涞碾x線的兩階段映射方案，文獻(xiàn)[7]提出了針對(duì)流量矩陣的在線的兩階段映射算法，文獻(xiàn)[8]提出了針對(duì)星狀和輻射狀拓?fù)浣Y(jié)構(gòu)的離線的一階段映射算法。這三種算法都是以減少映射開銷為優(yōu)化目標(biāo)，且在各自的拓?fù)浣Y(jié)構(gòu)中都能取得不錯(cuò)的效果，但是在其他拓?fù)浣Y(jié)構(gòu)，或無明顯拓?fù)涮卣鞯木W(wǎng)絡(luò)中，上述方法的算法性能并不理想。

文獻(xiàn)[9]提出了重映射的概念，這是一種在線的一階段映射算法。它的優(yōu)化目標(biāo)是當(dāng)?shù)讓游?/p>

理網(wǎng)不再滿足虛網(wǎng)需求，或虛網(wǎng)需求發(fā)生改變時(shí)，盡可能地降低虛網(wǎng)重新映射的代價(jià)。

為了解決上述問題，本文從節(jié)點(diǎn)負(fù)載平衡的角度出發(fā)，在基于就近原則的虛網(wǎng)映射算法[10]的基礎(chǔ)上，引入節(jié)點(diǎn)負(fù)載平衡的反饋機(jī)制，引導(dǎo)各個(gè)虛網(wǎng)請(qǐng)求更加均勻地映射到底層物理網(wǎng)絡(luò)中，從而有效避免節(jié)點(diǎn)映射階段資源瓶頸的發(fā)生。另外該算法在k短路徑算法機(jī)制[11]中引入了當(dāng)前鏈路資源占有率作為路徑長度的評(píng)價(jià)參考標(biāo)準(zhǔn)。這樣，在計(jì)算路徑長度的時(shí)候，就會(huì)將剩余鏈路資源較多的物理路徑優(yōu)先映射，就可以盡可能均勻地分散鏈路壓力。同時(shí)，在檢驗(yàn)鏈路資源是否滿足虛網(wǎng)請(qǐng)求的過程中，由于優(yōu)先選中的鏈路資源占有率低，剩余資源較多，所以算法映射成功率高，耗時(shí)較短，虛擬網(wǎng)絡(luò)映射的效率得到了有效的提高。

1 基于占有率反饋的虛擬網(wǎng)絡(luò)映射

1.1 節(jié)點(diǎn)映射方法

完整的節(jié)點(diǎn)映射算法流程如圖1所示。在本文提出的基于占有率反饋的虛擬網(wǎng)絡(luò)映射算法中，首先根據(jù)當(dāng)前的虛網(wǎng)請(qǐng)求，計(jì)算虛網(wǎng)請(qǐng)求中各個(gè)虛網(wǎng)節(jié)點(diǎn)的請(qǐng)求值（rv），將虛網(wǎng)節(jié)點(diǎn)按照其請(qǐng)求值（rv）從大到小順序進(jìn)行節(jié)點(diǎn)映射。請(qǐng)求值（rv）是指虛網(wǎng)節(jié)點(diǎn)映射所需的物理資源，其定義為

其中Bw是指虛擬鏈路lv的帶寬需求，Ccpu指的是虛網(wǎng)節(jié)點(diǎn)nv的CPU容量需求，L（nv）是指與虛網(wǎng)節(jié)點(diǎn)nv相連的虛擬鏈路lv的集合，α和β是用于平衡CPU和帶寬的權(quán)重調(diào)節(jié)參數(shù)，一般情況下，α和β的取值范圍在1～3之間，默認(rèn)α和β取1。式（1）定義了虛網(wǎng)請(qǐng)求中一個(gè)虛擬節(jié)點(diǎn)的請(qǐng)求值rv，它象征了這個(gè)虛擬節(jié)點(diǎn)在虛網(wǎng)請(qǐng)求中的重要程度，也一定程度上代表了該節(jié)點(diǎn)映射的困難程度。因此在節(jié)點(diǎn)映射過程中，將會(huì)優(yōu)先映射rv值較高的虛擬節(jié)點(diǎn)。

在虛網(wǎng)請(qǐng)求中，不斷選取尚未映射的虛網(wǎng)節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)映射，選取的順序就按照rv值從高到低選取。每次節(jié)點(diǎn)映射時(shí)，先從底層物理網(wǎng)中選擇出剩余CPU資源大于此虛網(wǎng)節(jié)點(diǎn)所需CPU資源的所有物理節(jié)點(diǎn)，作為可供映射的物理節(jié)點(diǎn)，然后計(jì)算所有選出的物理網(wǎng)節(jié)點(diǎn)的加權(quán)資源值（rwv），將選出的物理網(wǎng)節(jié)點(diǎn)按照加權(quán)資源值（rwv）從大到小排序，并將加權(quán)資源值（rwv）最大的物理節(jié)點(diǎn)作為當(dāng)前虛網(wǎng)節(jié)點(diǎn)的映射對(duì)象。這樣該節(jié)點(diǎn)的映射過程就算成功了，接著進(jìn)入下一節(jié)點(diǎn)的映射工作。加權(quán)資源值（rwv）是指物理節(jié)點(diǎn)提供資源的能力：

其中，Nneigh是針對(duì)底層物理網(wǎng)節(jié)點(diǎn)ns的相關(guān)系數(shù)，Nneigh為大于1的實(shí)數(shù)，該參數(shù)用來定義兩個(gè)物理節(jié)點(diǎn)的相近程度，指數(shù)m 表示當(dāng)前虛網(wǎng)請(qǐng)求中已經(jīng)映射成功并且映射的物理節(jié)點(diǎn)與ns有直接連接的虛網(wǎng)節(jié)點(diǎn)個(gè)數(shù).一個(gè)物理節(jié)點(diǎn)的Nmneigh值越高，說明該節(jié)點(diǎn)與當(dāng)前虛網(wǎng)請(qǐng)求中已經(jīng)映射的物理節(jié)點(diǎn)集合距離較近，聯(lián)系更密切，有較好的帶寬資源。所以在映射過程中，設(shè)計(jì)的算法會(huì)更傾向于映射該節(jié)點(diǎn)，以提高之后的鏈路映射的成功率。Ooccupy表示物理節(jié)點(diǎn)ns已經(jīng)被其他虛網(wǎng)請(qǐng)求占用的相關(guān)參數(shù)，Ooccupy為0到1之間的實(shí)數(shù)，且隨著Ooccupy的減小，反饋?zhàn)饔玫玫郊訌?qiáng)。n表示物理節(jié)點(diǎn)被其他虛網(wǎng)請(qǐng)求占用的次數(shù)，一個(gè)物理節(jié)點(diǎn)Onoccupy的值越小，說明該節(jié)點(diǎn)已經(jīng)被其他虛網(wǎng)請(qǐng)求映射的次數(shù)越多。出于負(fù)載平衡的考慮，設(shè)計(jì)的算法將更傾向于不再映射該節(jié)點(diǎn)，而是選擇其他尚未被映射的物理節(jié)點(diǎn)。

當(dāng)無法找到滿足虛網(wǎng)節(jié)點(diǎn)CPU需求的物理節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)映射失敗，整個(gè)虛網(wǎng)節(jié)點(diǎn)映射失敗。當(dāng)所有節(jié)點(diǎn)都完成節(jié)點(diǎn)映射時(shí)，該虛網(wǎng)節(jié)點(diǎn)映射成功，準(zhǔn)備進(jìn)入鏈路映射階段。

1.2 鏈路映射方法

在鏈路映射階段，如圖2所示，首先選擇當(dāng)前未鏈路映射的虛網(wǎng)請(qǐng)求，計(jì)算其虛網(wǎng)鏈路的鏈路帶寬Rbw，并從大到小進(jìn)行排序，其中鏈路帶寬Rbw為虛網(wǎng)請(qǐng)求中，虛網(wǎng)鏈路所需的通信帶寬大小。

根據(jù)鏈路帶寬Rbw的排序，依次對(duì)每條虛網(wǎng)鏈路進(jìn)行映射。每次鏈路映射時(shí)，先計(jì)算底層物理網(wǎng)中任意兩個(gè)直接相連的物理節(jié)點(diǎn)的鏈路占用系數(shù)，將該系數(shù)作為這兩個(gè)物理節(jié)點(diǎn)的路徑距離，構(gòu)成一個(gè)新的無向圖Gs′（Ns，Ls，Rls ′）。然后找出待映射鏈路的兩個(gè)端點(diǎn)節(jié)點(diǎn)，虛擬節(jié)點(diǎn)1和虛擬節(jié)點(diǎn)2，再分別找到其映射的物理節(jié)點(diǎn)1 和物理節(jié)點(diǎn)2，將這兩個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)在無向

圖G′s中進(jìn)行k短路徑的求解，尋找出路徑最短的前k條路徑。

最后，依次判斷這前k條最短路徑是否滿足虛網(wǎng)鏈路的帶寬需求。如果滿足，則將滿足帶寬條件的最短路徑作為虛擬鏈路的映射對(duì)象，該虛擬鏈路映射成功，繼續(xù)對(duì)下一條虛擬鏈路進(jìn)行映射。如果在鏈路映射過程中，無法找到滿足虛網(wǎng)鏈路帶寬需求的路徑，則此次虛網(wǎng)鏈路映射失敗。如果虛網(wǎng)中所有的虛擬鏈路都映射成功，則該虛網(wǎng)鏈路映射成功。

在上述鏈路映射算法中，鏈路占用系數(shù)定義為：鏈路占用系數(shù)=1-鏈路可用帶寬鏈路總帶寬+ε，其中ε根據(jù)需要取大于零的值，建議取0.5。無向圖Gs′（Ns，Ls，Rls′）中，Ns為底層物理節(jié)點(diǎn)的集合，Ls為底層物理鏈路的集合，Rls′為底層物理鏈路l的路徑距離，其大小為鏈路占用系數(shù)的值。

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

在Matlab上建立仿真環(huán)境。模擬的底層物理網(wǎng)絡(luò)共有100個(gè)物理節(jié)點(diǎn)，任意兩個(gè)物理節(jié)點(diǎn)之間存在鏈路的概率為0.5。這些節(jié)點(diǎn)的CPU資源和鏈路的帶寬值在50和100之間隨機(jī)分布。虛擬網(wǎng)絡(luò)請(qǐng)求的參數(shù)設(shè)置參照文獻(xiàn)[1213]。虛網(wǎng)請(qǐng)求的到達(dá)頻率是每個(gè)時(shí)間窗5個(gè)請(qǐng)求。對(duì)于每個(gè)虛網(wǎng)請(qǐng)求，虛擬節(jié)點(diǎn)的數(shù)目在2至10之間隨機(jī)生成。虛擬網(wǎng)絡(luò)中每兩個(gè)節(jié)點(diǎn)之間的聯(lián)通概率為0.5。虛擬節(jié)點(diǎn)的CPU值在0和20之間隨機(jī)分布，而虛擬鏈路的帶寬值是在0到Bw，max之間隨機(jī)分布，其中Bw，max默認(rèn)取50。整個(gè)虛網(wǎng)生存周期取10，拒絕次數(shù)取3次。在研究鏈路占用率反饋技術(shù)對(duì)映射時(shí)間的影響時(shí)，Bw，max的取值范圍為10～90。

圖3顯示當(dāng)Nneigh就近系數(shù)取1，即不考慮就近因素時(shí)，虛網(wǎng)接收率明顯較低，且隨著時(shí)間窗的增加，虛網(wǎng)請(qǐng)求不斷到來，虛網(wǎng)接收率持續(xù)降低，直到在8～10個(gè)時(shí)間窗后，部分映射成功的虛網(wǎng)完成映射周期，結(jié)束映射并釋放出物理資源，虛網(wǎng)接收率才逐步穩(wěn)定在0.75至0.8之間。而當(dāng)Nneigh取2或3時(shí)，虛網(wǎng)優(yōu)先映射相鄰的節(jié)點(diǎn)，所以鏈路映射成功率較高，虛網(wǎng)接收率始終維持在較高的0.9，說明虛網(wǎng)所能承受的最大虛網(wǎng)個(gè)數(shù)提高了，在8～10個(gè)時(shí)間窗內(nèi)，還沒有虛網(wǎng)釋放物理資源的時(shí)候，物理網(wǎng)絡(luò)仍然能較好地映射新到的虛網(wǎng)請(qǐng)求，并且2和3的曲線十分接近，說明Nneigh的值不需要過高，過高對(duì)映射性能沒有太大的改觀。

圖4顯示當(dāng)Ooccupy占用系數(shù)取1，即不考慮節(jié)點(diǎn)占用率反饋的時(shí)候，虛網(wǎng)接收率開始較高，然后隨著虛網(wǎng)的不斷加入，有一個(gè)輕微下滑的過程，最終穩(wěn)定在0.89左右，而當(dāng)引入節(jié)點(diǎn)占用率反饋機(jī)制，并取Ooccupy為0.75時(shí)，虛網(wǎng)接收率的一直穩(wěn)定維持在0.91左右，這說明隨著虛網(wǎng)的加入，節(jié)點(diǎn)占有率反饋機(jī)制很好地分散了節(jié)點(diǎn)負(fù)載壓力，有效緩解了資源瓶頸的產(chǎn)生。但是，若取Ooccupy為0.5，可以看出虛網(wǎng)接收率明顯較低，且有一個(gè)明顯的下滑過程。經(jīng)過分析，這是由于Ooccupy系數(shù)取得過小，映射算法過于追求將節(jié)點(diǎn)分散映射，而導(dǎo)致將底層物理網(wǎng)資源碎片化，從而大幅降低映射成功率。這一現(xiàn)象在虛網(wǎng)請(qǐng)求數(shù)量較多的時(shí)候尤為明顯。

圖5顯示各映射算法在虛網(wǎng)鏈路帶寬最大值Bw，max從10增加到90時(shí)對(duì)算法運(yùn)行時(shí)間的影響.當(dāng)Bw，max小于30時(shí)，底層物理鏈路資源充足，所有鏈路映射幾乎都是一次成功，所以時(shí)間很短，但隨著虛網(wǎng)鏈路繼續(xù)增加，雖然總體趨勢(shì)都是映射時(shí)間大幅增加，但是相比于隱藏跳數(shù)算法[14]、基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[1516]的映射算法、k短路徑的映射算法[11]等其他算法，基于占有率反饋的映射算法在Bw，max在50到70之間的映射時(shí)間明顯較短，在這一階段，雖然鏈路資源已經(jīng)相對(duì)不足，但所有映射成功的鏈路基本都是在前幾次映射中就成功的，所以本文提出的算法耗時(shí)較短。

圖6顯示各映射算法的物理節(jié)點(diǎn)CPU利用率隨時(shí)間窗增加的變化情況.從圖6中看出各個(gè)算法的底層物理節(jié)點(diǎn)利用率隨著每個(gè)時(shí)間窗中虛網(wǎng)請(qǐng)求的到來而不斷上升，并最終趨于穩(wěn)定。其中基于就近原則的映射算法[10]的節(jié)點(diǎn)CPU利用率最高，基于占有率反饋的映射算法次之，相較于前者，基于占有率反饋的映射在優(yōu)化目標(biāo)上犧牲了部分節(jié)點(diǎn)資源利用率以換取物理節(jié)點(diǎn)的負(fù)載平衡?；诰W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的映射算法[1516]和普通的k短路徑映射算法[11]相對(duì)于以上兩種算法的節(jié)點(diǎn)CPU利用率則更低。

3 結(jié)束語

本文分析了傳統(tǒng)映射算法的特點(diǎn)和可能存在的缺陷，提出了基于占有率反饋的虛擬網(wǎng)絡(luò)資源映射方法，詳細(xì)介紹了該算法的主要流程和改進(jìn)的技術(shù)特點(diǎn)，并在仿真實(shí)驗(yàn)中給出了該方法的映射性能的展示。本文所提出的算法在節(jié)點(diǎn)映射階段，在追求節(jié)點(diǎn)CPU資源的同時(shí)，創(chuàng)新性地考慮了節(jié)點(diǎn)的負(fù)載平衡，在基于就近原則的虛網(wǎng)映射算法的基礎(chǔ)上，引入節(jié)點(diǎn)負(fù)載平衡的反饋機(jī)制，從而引導(dǎo)各個(gè)虛網(wǎng)請(qǐng)求更加均勻地映射到底層物理網(wǎng)絡(luò)中，避免了物理網(wǎng)絡(luò)中的核心節(jié)點(diǎn)資源被過早耗盡。在鏈路映射階段，本算法在k短路徑算法機(jī)制中引入了當(dāng)前鏈路資源占有率作為評(píng)價(jià)參考標(biāo)準(zhǔn)，這樣做可以盡可能均勻地分散鏈路壓力，同時(shí)在檢驗(yàn)鏈路資源是否滿足虛網(wǎng)請(qǐng)求的過程中，由于優(yōu)先選中的鏈路資源占有率低，剩余資源較多，算法映射成功率高，耗時(shí)更短，虛擬網(wǎng)絡(luò)映射的效率得到了極大提高。

參考文獻(xiàn)

References

[1] Lu J，Turner J.Efficient mapping of virtual networks onto a shared substrate[J].Washington University in St Louis，2006，35：24552462

[2] Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112

[3] Chen X H，Li C Z，Jiang Y L.A feedback control approach for energy efficient virtual network embedding[J].Computer Communications，2016，80（15）：1632

[4] Hu X B，Wang M，Hu D，et al.A ripplespreading algorithm for the k shortest paths problem[C]∥The 3rd Global Congress on Intelligent Systems，2012：202208

[5] Ciciriello P，Mottola L，Picco G P.Efficient routing from multiple sources to multiple sinks in wireless sensor networks[C]∥Proceedings of 4th European Conference on Wireless Sensor Networks，2007：3450

[6] Kareche S，Ductor S，Guessoum Z，et al.A new robust heuristic for assigning substrate network resources to virtual networks[C]∥International Conference on Advanced Networking Distributed Systems and Applications，2014：4752

[7] Fan J L，Ammar M H.Dynamic topology configuration in service overlay networks：A study of reconfiguration policies[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112

[8] Wei X H，Li H L，Yang K，et al.Topology aware partial virtual cluster mapping algorithm on shared distributed infrastructures[C]∥IEEE Transactions on Parallel and Distributed Systems，2014，25（10）：27212730

[9] Cai Z P，Liu F，Xiao N，et al.Virtual network embedding for evolving networks[C]∥IEEE Global Telecommunications Conference，2010：15

[10] Liu J，Huang T，Chen J Y，et al.A new algorithm based on the proximity principle for the virtual networking embedding problem[J].Journal of Zhejiang University（Science C），2011，12（11）：910918

[11] Wang F，Man Y，Man L C.Intelligent optimization approach for the k shortest paths problem based on genetic algorithm[C]∥10th International Conference on Natural Computation，2014：219224

[12] Gonzlez A，Barra E，Beghelli A，et al.A subgraph mappingbased algorithm for virtual network allocation over flexible grid networks[C]∥17th International Conference on Transparent Optical Network，2015：14

[13] Zegura E W，Calvert K L，Bhattacharjee S.How to model an internetwork[C]∥Proc 15th IEEE International Conference on Computer Communications，1996：594602

[14] Botero J F，Hesselbach X，F(xiàn)ischer A，et al.Optimal mapping of virtual ne tworks with hidden hops[J].Telecommunication Systems，2012，51（4）：273282

[15] Dhanapala D C，Jayasumana A P.Topology preserving maps extracting layout maps of wireless sensor networks from virtual coordinates[J].IEEE/ACM Transactions on Networking，2014，22（3）：784797

[16] Wang Z M，Wu J X，Wang Y，et al.Survivable virtual network mapping using optimal back up topology in virtualized SDN[J].China Communications，2014，11（2）：2637