毛宇星 郭云飛 王志明 扈紅超

?

基于資源區(qū)域聚集度的虛擬網(wǎng)映射算法

毛宇星*①郭云飛②王志明②扈紅超②

①(解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院 南京 210007)②(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)

虛擬網(wǎng)映射是網(wǎng)絡(luò)虛擬化研究中亟待解決的問題，針對已有映射算法中存在的對于網(wǎng)絡(luò)拓?fù)湫畔⒗貌蛔愕默F(xiàn)狀，該文提出了基于資源區(qū)域聚集度的虛擬網(wǎng)映射算法(RCI-VNE)。在映射預(yù)處理階段，根據(jù)局部拓?fù)湫畔⒑蛥^(qū)域資源聚集度提出節(jié)點區(qū)域資源聚集評價算法。在節(jié)點映射階段，提出一種基于節(jié)點區(qū)域資源聚集排名的2-近鄰聚集映射算法，該算法將虛擬網(wǎng)節(jié)點集中映射到底層網(wǎng)絡(luò)中可用資源豐富的區(qū)域，減小承載鏈路的長度。實驗結(jié)果表明，該算法降低了虛擬網(wǎng)映射開銷，且具有較高的虛擬網(wǎng)請求接受率和較低的平均執(zhí)行時間。

網(wǎng)絡(luò)虛擬化；網(wǎng)絡(luò)虛擬化映射；拓?fù)湫畔?；區(qū)域資源聚集指數(shù)

1 引言

網(wǎng)絡(luò)僵化問題[1]是當(dāng)前互聯(lián)網(wǎng)發(fā)展所面臨的一個巨大挑戰(zhàn)，網(wǎng)絡(luò)虛擬化技術(shù)[2]由于能夠有效地解決互聯(lián)網(wǎng)在技術(shù)創(chuàng)新上面臨的瓶頸而受到了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注。網(wǎng)絡(luò)虛擬化是指通過虛擬化技術(shù)在共同的底層物理設(shè)施上同時運(yùn)行多個虛擬網(wǎng)，不同的虛擬網(wǎng)使用不同的路由策略和網(wǎng)絡(luò)協(xié)議。單個虛擬網(wǎng)絡(luò)是根據(jù)需求由一組虛擬節(jié)點和虛擬鏈路連接而成的一個服務(wù)切面，虛擬網(wǎng)映射主要完成如何將這些虛擬節(jié)點和虛擬鏈路對應(yīng)匹配到底層物理網(wǎng)絡(luò)中的節(jié)點和鏈路上的任務(wù)，是網(wǎng)絡(luò)虛擬化研究的關(guān)鍵內(nèi)容。

由于存在多個目標(biāo)和約束，虛擬網(wǎng)映射問題已經(jīng)被證明為NP-hard[3]問題，通常使用基于啟發(fā)式算法的方法求解，如文獻(xiàn)[4]提出的節(jié)點/鏈路負(fù)載均衡的啟發(fā)式算法，文獻(xiàn)[5]提出的基于鏈路可分割的多商品流映射算法，文獻(xiàn)[6]提出了一種分布式的虛擬網(wǎng)映射算法，底層網(wǎng)絡(luò)節(jié)點之間傳遞資源信息并將虛擬網(wǎng)分為若干星型拓?fù)浣Y(jié)構(gòu)。上述算法將虛擬網(wǎng)映射問題分成節(jié)點映射和鏈路映射兩個階段，各個階段分別依據(jù)自身的目標(biāo)函數(shù)和約束條件進(jìn)行求解。文獻(xiàn)[7,8]使用整數(shù)規(guī)劃方法將節(jié)點映射和鏈路映射統(tǒng)一進(jìn)行求解，在節(jié)點映射階段就考慮了負(fù)載均衡和最大化映射利潤，但是該方法在本質(zhì)上仍然是兩階段的映射方法。兩階段映射算法的優(yōu)點在于縮小了解空間，能夠獲得較快的執(zhí)行速度，但算法的成功率和對底層網(wǎng)絡(luò)的資源利用情況還有待提高。文獻(xiàn)[9]提出了一種基于子圖同型檢測的一階段虛擬網(wǎng)映射算法，該算法使用回溯機(jī)制統(tǒng)一進(jìn)行節(jié)點和鏈路映射。一階段方法在整個解空間進(jìn)行搜索，能夠取得較好的映射方案，但是也造成了算法復(fù)雜度高、執(zhí)行速度慢的問題。文獻(xiàn)[10]提出了一種支持接入控制的虛擬網(wǎng)映射近似算法，能夠提高物理網(wǎng)資源的負(fù)載均衡度和利用率。文獻(xiàn)[11]提出了一種基于人工魚群的網(wǎng)絡(luò)虛擬化映射算法，該算法根據(jù)虛擬網(wǎng)絡(luò)請求與底層網(wǎng)絡(luò)節(jié)點和鏈路之間的約束關(guān)系建立二進(jìn)制組合優(yōu)化模型，能夠有效降低底層網(wǎng)絡(luò)的開銷和求解時間。文獻(xiàn)[12]研究了分布式環(huán)境下的虛擬網(wǎng)映射方法，提出了基于多節(jié)點協(xié)商的映射機(jī)制，實驗表明該算法能夠降低資源和通信開銷。

為了在映射方案的效果和算法復(fù)雜度之間取得平衡，近年來的研究傾向于在節(jié)點映射階段就考慮鏈路映射的限制條件，利用節(jié)點的拓?fù)湫畔⑻摂M網(wǎng)請求映射到底層網(wǎng)絡(luò)中可用資源豐富的位置，提高映射的成功率和底層網(wǎng)絡(luò)資源的利用率。文獻(xiàn)[13~17]利用節(jié)點在網(wǎng)絡(luò)中位置的全局拓?fù)湫畔⒃O(shè)計虛擬網(wǎng)映射算法，在一定程度上避免了上述問題，但仍然存在以下不足：(1)評價節(jié)點重要性時依賴全局信息，增加了算法的復(fù)雜度，并且忽視了被評價節(jié)點附近其他節(jié)點之間的連接關(guān)系對該節(jié)點重要性造成的影響；(2)沒有設(shè)計將虛擬節(jié)點集中映射到底層網(wǎng)絡(luò)某個區(qū)域的機(jī)制，承載物理節(jié)點的間距無法控制，增加映射開銷。

為了解決上述問題，本文首先提出一種基于局部拓?fù)湫畔⒑蛥^(qū)域資源聚集度的節(jié)點區(qū)域資源聚集評價算法，該算法根據(jù)目標(biāo)節(jié)點與其兩層鄰居的可用資源數(shù)量以及該區(qū)域節(jié)點之間連接的緊密程度對目標(biāo)節(jié)點的重要性進(jìn)行評價。其次，本文提出基于節(jié)點區(qū)域資源聚集排名的2-近鄰聚集虛擬網(wǎng)映射算法RCI-VNE，該算法將虛擬網(wǎng)節(jié)點集中映射到底層網(wǎng)絡(luò)中可用資源數(shù)量較多的區(qū)域，降低了虛擬網(wǎng)映射開銷，且具有較高的虛擬網(wǎng)請求接受率和較低的平均執(zhí)行時間。

2 問題分析

2.1網(wǎng)絡(luò)模型

虛擬網(wǎng)映射問題的網(wǎng)絡(luò)模型如圖1所示。

圖1 虛擬網(wǎng)映射模型解析

3 基于節(jié)點區(qū)域資源聚集度的虛擬網(wǎng)映射

3.1 節(jié)點區(qū)域資源聚集程度評價方法

在復(fù)雜網(wǎng)絡(luò)中為了衡量節(jié)點的重要性，需要對節(jié)點的拓?fù)湫畔⒓右钥紤]。文獻(xiàn)[18]提出了一種利用半局部信息的節(jié)點重要性排序方法，該方法利用節(jié)點二階鄰居信息對節(jié)點的重要性進(jìn)行評價，并指出該方法的時間復(fù)雜度隨網(wǎng)絡(luò)規(guī)模線性增長，實驗顯示，該方法能夠取得優(yōu)于PageRank和LeaderRank算法的結(jié)果。但是該算法只考慮了節(jié)點之間鏈路的權(quán)值，沒有對節(jié)點本身的可用資源數(shù)量進(jìn)行評價，無法直接應(yīng)用在虛擬網(wǎng)映射問題上。本文對該方法進(jìn)行改進(jìn)，考慮了節(jié)點本身的可用資源數(shù)量，提出了節(jié)點區(qū)域資源因子。

定義1 節(jié)點區(qū)域資源因子：

節(jié)點的聚集因子[19]反映了節(jié)點與其鄰居以及鄰居節(jié)點之間連接的緊密程度，該因子越大則節(jié)點與周圍的鄰居以及鄰居之間的連接越緊密，越小則連接越疏松。

定義2 節(jié)點區(qū)域聚集因子：

本文將節(jié)點區(qū)域資源因子與節(jié)點區(qū)域聚集因子相結(jié)合，提出了評價節(jié)點所在區(qū)域資源聚集程度的節(jié)點區(qū)域資源聚集指數(shù)。

定義3 節(jié)點區(qū)域資源聚集指數(shù)：

計算節(jié)點區(qū)域資源聚集指數(shù)的具體算法如表1所示，算法的復(fù)雜度為，其中為網(wǎng)絡(luò)拓?fù)渲泄?jié)點的個數(shù)，為網(wǎng)絡(luò)拓?fù)渲泄?jié)點的平均度數(shù)。

3.2 2-近鄰聚集節(jié)點映射算法

為了充分利用底層物理網(wǎng)絡(luò)中的CPU資源和帶寬資源，本文提出了基于節(jié)點區(qū)域資源聚集指數(shù)的2-近鄰聚集節(jié)點映射算法，該算法的特點是：(1)將對資源要求高的虛擬節(jié)點映射到區(qū)域資源聚集指數(shù)高的物理節(jié)點上，盡量提高節(jié)點映射和鏈路映射階段的成功率。(2)將虛擬網(wǎng)請求映射在底層網(wǎng)絡(luò)中資源聚集度高的區(qū)域，減少承載虛擬鏈路的物理鏈路的長度，降低映射開銷。算法的基本思路為：將虛擬網(wǎng)請求中的節(jié)點和底層網(wǎng)絡(luò)中的節(jié)點分別按照其節(jié)點區(qū)域資源聚集指數(shù)降序排列；將排名靠前的虛擬網(wǎng)請求節(jié)點映射到能夠承載該節(jié)點且排名靠前的底層網(wǎng)絡(luò)節(jié)點上；將映射成功的虛擬網(wǎng)請求節(jié)點的兩層鄰居節(jié)點映射到承載的物理節(jié)點的兩層鄰居節(jié)點中滿足其資源約束的節(jié)點上。算法的具體流程如表2所示。

表1節(jié)點區(qū)域資源聚集指數(shù)算法

算法1 NRCI(Node Regional Resource Clustering Index)算法 輸入：網(wǎng)絡(luò)拓?fù)洹?輸出：節(jié)點區(qū)域資源聚集指數(shù)向量R。 (1);(2) for each do(3) ;(4) for each do(5) ;(6) for each do(7) if k==i(8) continue;(9) end if(10) ;(11) end for(12) ;(13) ;(14) end for

表2基于區(qū)域資源聚集度的虛擬網(wǎng)映射算法

算法2 RCI-VNE(Virtual Network Embedding algorithm based on Resource Clustering Index)算法 輸入：。輸出：節(jié)點映射方案。(1) 將虛擬網(wǎng)請求和底層網(wǎng)絡(luò)中的節(jié)點列表和分別按照 其區(qū)域資源聚集指數(shù)分別降序排列； (2) 將中所有節(jié)點置為沒有映射，中所有節(jié)點置為沒有 承載；(3) while 存在沒有映射成功的節(jié)點do(4) vNode中區(qū)域資源聚集指數(shù)最高的節(jié)點 (5) for each (6) if sNode已經(jīng)承載了虛擬節(jié)點；(7) continue;(8) end if(9) else if (10) continue;(11) else(12) 將vNode映射到sNode上；(13) 設(shè)置vNode為已映射；設(shè)置sNode為已承 載；(14) Map_neighbour(vNode, sNode);(15) 將vNode節(jié)點從未映射成功的節(jié)點隊列中 刪除；(16) end if(17) end for(18) if vNode沒有映射成功(19) return false;(20) end if(21) end while(22) return true

子程序Map_neighbour( )負(fù)責(zé)將映射成功的虛擬網(wǎng)請求節(jié)點的兩層鄰居節(jié)點映射在承載該虛擬網(wǎng)節(jié)點的底層網(wǎng)絡(luò)節(jié)點的兩層鄰居節(jié)點上，映射方案見表3。該節(jié)點映射算法的時間復(fù)雜度為。

在鏈路映射階段，如果底層網(wǎng)絡(luò)的支持鏈路分割，就使用多商品流算法將虛擬網(wǎng)請求鏈路映射到底層網(wǎng)絡(luò)的鏈路上。如果底層網(wǎng)絡(luò)不支持鏈路分割則使用K-最短路徑算法進(jìn)行映射。K-最短路徑算法和多商品流問題的時間復(fù)雜度在多項式時間之內(nèi)。所以整個虛擬網(wǎng)映射算法的時間復(fù)雜度在多項式時間之內(nèi)。

表3子程序Map_neighbour映射方案

PROCEDURE Map_neighbour(vNode, sNode):(1)unMapListvNode未映射的鄰居節(jié)點列表；unUseList sNode未承載鄰居節(jié)點列表；(2) for each (3) for each (4) if (5) 將vNei映射到sNei上；(6) 將vNei設(shè)置為已映射；將sNei.used設(shè)置為已承載；(7) 在unMapList上刪除vNei；(8) 在unUseLists上刪除Nei；(9) end if(10) end for(11) end for

4 實驗評估

4.1 實驗環(huán)境

本文實驗使用配置為3.10 GHz Intel Core i7- 4600的計算平臺，利用C++編程仿真虛擬網(wǎng)映射請求的到達(dá)和離開以及虛擬網(wǎng)映射過程。本文使用GT-ITM拓?fù)渖善鱗20]構(gòu)建底層網(wǎng)絡(luò)和虛擬請求拓?fù)洹榱朔奖銓嶒瀸Ρ?，與現(xiàn)有的文獻(xiàn)[15,16]類似，本文實驗生成具有100個節(jié)點的底層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和2000個虛擬網(wǎng)請求。底層網(wǎng)絡(luò)的節(jié)點CPU資源和鏈路帶寬資源的取值服從[50,100]內(nèi)的均勻分布，底層網(wǎng)絡(luò)節(jié)點的連接概率為0.2。虛擬網(wǎng)請求的節(jié)點個數(shù)服從[2,20]內(nèi)的均勻分布，虛擬網(wǎng)請求的節(jié)點連接概率為0.5。虛擬網(wǎng)請求的節(jié)點和鏈路資源取值在[0,50]內(nèi)服從均勻分布。虛擬網(wǎng)請求的到達(dá)過程服從到達(dá)率為平均100個時間單位到達(dá)4個請求的泊松過程，生命周期服從期望為1000個時間單位的指數(shù)分布。此外，設(shè)置RCI-VNE算法中的參數(shù)為0.8,-最短路徑算法中的為10。

4.2 評價指標(biāo)

與現(xiàn)有文獻(xiàn)[14~16]類似，本文使用如下4個評價指標(biāo)對本文提出的映射算法以及現(xiàn)有的映射算法進(jìn)行評價。

(1)虛擬網(wǎng)請求接受率：該指標(biāo)用來衡量在給定的時間間隔之內(nèi)底層物理網(wǎng)絡(luò)接受的虛擬網(wǎng)請求占全部到達(dá)虛擬網(wǎng)請求的比例。

(2)底層網(wǎng)絡(luò)的長期平均收益：該指標(biāo)衡量了虛擬網(wǎng)映射算法給底層網(wǎng)絡(luò)帶來的長期平均收益情況。

(3)長期利潤成本比：該指標(biāo)用于衡量映射算法產(chǎn)生單位利潤所花費(fèi)的資源開銷。

(4)映射算法平均執(zhí)行時間：該指標(biāo)衡量了映射算法執(zhí)行的平均時間。

本文使用上述指標(biāo)比較了本文提出的RCI- VNE算法和現(xiàn)有的其他5種虛擬網(wǎng)映射算法(GRC- VNE[13], R-ViNE-SP[7], VNE-B[9], Hybrid-VNE[15], G-SP[4])的性能。

圖2所示為不同虛擬網(wǎng)映射算法的接受率，從圖2中可以看出，在映射開始階段由于底層物理網(wǎng)絡(luò)可用資源較為充足，各個映射算法都有著較高的請求接受率。隨著時間的推移，各個映射算法的接受率不斷下降，平最終達(dá)到穩(wěn)定。其中RCI-VNE算法的接受率最高，穩(wěn)定接受率保持在54.19%, GRC-VNE, VNE-B, R-ViNE-SP, Hybrid-VNE算法的穩(wěn)定接受率分別保持在47.23%, 39.74%, 33.13%和23.09%, G-SP算法的接受率最低，穩(wěn)定接受率保持在18.35%。該指標(biāo)主要與底層網(wǎng)絡(luò)的資源使用情況有關(guān)。實驗結(jié)果顯示，本文提出的RCI- VNE算法和文獻(xiàn)[13]提出的GRC-VNE算法能夠較好的在物理網(wǎng)絡(luò)和虛擬網(wǎng)請求中對節(jié)點的資源情況進(jìn)行評價，GRC-VNE算法在評價某個節(jié)點的資源能力時考慮了整個物理網(wǎng)絡(luò)中的節(jié)點信息，忽略了底層網(wǎng)絡(luò)拓?fù)溥h(yuǎn)大于虛擬網(wǎng)請求拓?fù)涞氖聦?，使得算法的針對性下降，而且該算法在?jié)點映射時沒有考慮到承載節(jié)點之間的距離，這也造成對底層網(wǎng)絡(luò)資源的過度使用。Hybrid-VNE算法將虛擬網(wǎng)請求中的節(jié)點進(jìn)行了K-core分解，考慮了節(jié)點的拓?fù)鋵傩?，但是沒有考慮到底層網(wǎng)絡(luò)中節(jié)點的可用資源情況，其他算法都沒有考慮節(jié)點的拓?fù)鋵傩浴?/p>

圖3，圖4所示分別是不同虛擬網(wǎng)映射算法的長期平均收益和利潤成本比，由于本文提出的映射算法在節(jié)點映射階段將節(jié)點集中映射在物理網(wǎng)絡(luò)中可用集中的區(qū)域，使得承載虛擬鏈路的物理鏈路的距離更短，降低了承載虛擬網(wǎng)請求的開銷，獲得比其他算法更高的利潤成本比。其他算法在節(jié)點映射時基本都只考慮了底層網(wǎng)絡(luò)節(jié)點的資源豐富程度，這就造成了承載節(jié)點之間的距離可能很大，導(dǎo)致較高的鏈路映射開銷。從圖3和圖4可以看出，本文算法在這兩項指標(biāo)上都有優(yōu)于其他算法的表現(xiàn)。

圖2 虛擬網(wǎng)請求接受率

圖5所示為本文進(jìn)行比較的虛擬網(wǎng)映射算法在同一仿真環(huán)境下映射2000個虛擬網(wǎng)請求的算法平均執(zhí)行時間和標(biāo)準(zhǔn)差。從圖中可以看出本文提出的RCI-VNE算法在評價節(jié)點的承載能力時，只依賴于被評價節(jié)點兩層鄰居的信息，能夠獲得比依賴于全局拓?fù)湫畔⒌腉RC-VNE映射算法更短的執(zhí)行時間。VNE-B映射算法由于將節(jié)點映射和鏈路映射結(jié)合起來，需要的回溯操作較多，算法的執(zhí)行時間相對較長。

由實驗結(jié)果可知，本文提出的基于節(jié)點區(qū)域資源聚集指數(shù)的RCI-VNE虛擬網(wǎng)映射算法在上述3個評價指標(biāo)上具有明顯優(yōu)勢，能夠有效地提高虛擬網(wǎng)請求接受率和利潤成本比，并最終提高底層網(wǎng)絡(luò)的長期平均收益。

5 結(jié)束語

本文基于復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排名的半局部中心拓?fù)鋵傩院蛥^(qū)域聚集因子提出了節(jié)點區(qū)域資源聚集指數(shù)，該指數(shù)能夠評價以節(jié)點為中心的兩層鄰居范圍內(nèi)的可用節(jié)點資源以及該范圍內(nèi)節(jié)點之間可用鏈路資源的水平，并基于該指數(shù)提出了RCI-VNE虛擬網(wǎng)映射算法，該算法將虛擬網(wǎng)請求集中映射到底層網(wǎng)絡(luò)中區(qū)域可用資源豐富的位置，有效地提高了虛擬網(wǎng)請求的接受率和利潤成本比，最終提高底層網(wǎng)絡(luò)的長期平均收益。此外與基于節(jié)點全局拓?fù)鋵傩缘乃惴ㄏ啾?，該算法具有更低的時間復(fù)雜度和平均映射時間。

圖3 長期平均利潤 圖4 利潤成本比

圖5 虛擬網(wǎng)映射算法平均執(zhí)行時間和標(biāo)準(zhǔn)差

[1] Turner J S and Taylor D. Diversifying the Internet[C]. Proceedings of IEEE Conference on Global Telecommunications, St. Louis, 2005: 755-760.

[2] Anderson T, Peterson L, Shenker S,.. Overcoming the Internet impasse through virtualization[J]., 2005, 38(4): 34-41.

[3] Andersen D G. Theoretical Approaches to Node Assignment [M]. New York: Computer Science Department, 2002: 86-123.

[4] Zhang Y, Ammar M,.. Algorithm for assigning substrate network resources to virtual network components[C]. Proceedings of IEEE INFOCOM, Barcelona, 2006: 1-12.

[5] Yu M, Yi Y, Rexford J,.. Rethinking virtual network embedding: substrate support for path splitting and migration[J]., 2008, 38(2): 17-29.

[6] Houidi I, Louati W,.. A distributed virtual network mapping algorithm[C]. IEEE International Conference on Communication, Beijing, 2008: 5634-5640.

[7] Chowdhury M, Rahman M,.. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping[J]./, 2012, 20(1): 206-219.

[8] Melo M, Sargento S, Killat U,.. Optimal virtual network embedding: node-link formulation[J]., 2013, 10(4): 356-368.

[9] Lischka J, Karl H,.. A virtual network mapping algorithm based on subgraph isomorphism detection[C]. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, Barcelona, 2009: 81-88.

[10] 余建軍, 吳春明. 支持接入控制的虛擬網(wǎng)映射近似算法[J]. 電子與信息學(xué)報, 2014, 36(5): 1235-1241.

Yu Jian-jun and Wu Chun-ming. Virtual network mapping approximation algorithm with admission control[J].&, 2014, 36(5):1235-1241.

[11] 朱強(qiáng), 王慧強(qiáng), 等. VNE-AFS: 基于人工魚群的網(wǎng)絡(luò)虛擬化映射算法[J]. 通信學(xué)報, 2012, 33(Z1): 170-177.

Zhu Q, Wang Hui-qiang,.. VNE-AFS: virtual network embedding based on artificial fish swarm[J]., 2012, 33(Z1): 170-177.

[12] 江逸茗, 蘭巨龍, 程東年, 等. 分布式環(huán)境中基于協(xié)商的虛擬網(wǎng)映射算法[J]. 通信學(xué)報, 2014, 35(12): 62-69.

Jiang Yi-ming, Lan Ju-long, Cheng Dong-nian,.. Virtual network embedding algorithm based on negotiation in distributed environment[J]., 2014, 35(12): 62-69.

[13] Gong L, Wen Y, Zhu Z,.. Toward profit-seeking virtual network embedding algorithm via global resource capacity[C]. Proceedings of IEEE INFOCOM, Toronto, 2014: 1-9.

[14] Cui H, Gao W, Liu J,.. A virtual network embedding algorithm based on virtual topology connection feature[C]. IEEE 16th International Symposium on Wireless Personal Multimedia Communications, Atlantic City, 2013: 1-5.

[15] Qing S, Liao J, Zhu X,.. Hybrid virtual network embedding with K-core decomposition and time-oriented priority[C]. IEEE International Conference on Communications, Ottawa, Canada, 2012: 2695-2699.

[16] Huang T, Liu J, Chen J,.. A topology-cognitive algorithm framework for virtual network embedding problem [J].,, 2014, 11(4): 73-84.

[17] Cui H, Tang S, Huang X,.. A novel method of virtual network embedding based on topology convergence-degree[C]. IEEE International Conference on Communications Workshops, Budapest, 2013: 246-250.

[18] Chen D, Lü L, Shang M S,.. Identifying influential nodes in complex networks[J]., 2012, 391(4): 1777-1787.

[19] Fagiolo G. Clustering in complex directed networks[J]., 2007, 76(2): 470-475.

[20] Zegura E, Calvert K, and Bhattacharjee S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM, Philadelphia, 1996: 594-602.

Virtual Network Embedding Algorithm Based on Regional Resource Clustering Index

Mao Yu-xing①Guo Yun-fei②Wang Zhi-ming②Hu Hong-chao②

①(,,210007,)②(&,450002,)

Virtual network embedding is a critical issue in network virtualization. To overcome the ignorance of network local topology information in existing literatures, a Virtual Network Embedding (VNE) algorithm based on regional Resource Clustering Index (RCI-VNE), is proposed. In embedding preprocessing stage, a node regional resource clustering index evaluation algorithm is proposed, which considers local topology information and resource aggregation extent. In node embedding stage, a 2-adjacent aggregation node embedding algorithm based on the regional resource clustering index is also proposed. The algorithm embeds virtual nodes intensively to the location of abundant resources in substrate network and decreases embedding cost. Simulation results show that the algorithm improves virtual network request acceptance ratio, long-time average revenue and benefit-cost ratio compared with the existing embedding algorithms.

Network Virtualization; Virtualization Network Embedding (VNE); Topology Information; Regional Resource Clustering Index (RCI)

TP393.4

A

1009-5896(2015)10-2405-06

10.11999/JEIT150278

2015-03-09；改回日期：2015-06-16；

2015-07-27

毛宇星 myx_lgdx@163.com

國家自然科學(xué)基金(61309020)，國家973計劃項目(2012CB315901, 2012CB315905)和國家863計劃項目(2011AA 01A103)

The National Natural Science Foundation of China (61309020); The National 973 Program of China (2012CB 315901, 2012CB315905); The National 863 Program of China (2011AA01A103)

毛宇星： 男，1989年生，博士生，研究方向為寬帶信息網(wǎng)絡(luò).

郭云飛： 男，1963年生，博士，教授，博士生導(dǎo)師，研究方向為下一代網(wǎng)絡(luò).

王志明： 男，1986年生，博士生，研究方向為下一代網(wǎng)絡(luò).

扈紅超： 男，1982年生，博士，研究方向為高性能路由交換技術(shù).