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

目錄虛擬網(wǎng)絡(luò)的引入虛擬網(wǎng)絡(luò)概述虛擬網(wǎng)絡(luò)映射問題介紹虛擬網(wǎng)絡(luò)映射問題形式化定義虛擬網(wǎng)絡(luò)映射問題分類虛擬網(wǎng)絡(luò)映射問題評價指標(biāo)虛擬網(wǎng)絡(luò)映射問題研究現(xiàn)狀虛擬網(wǎng)絡(luò)映射問題新方向虛擬網(wǎng)絡(luò)引入虛擬化技術(shù)將計算機物理資源如服務(wù)器、網(wǎng)絡(luò)、內(nèi)存及存儲等予以抽象、轉(zhuǎn)換后呈現(xiàn)出來，使用戶可以比原本的組態(tài)更好的方式來應(yīng)用這些資源。這些資源的新虛擬部份是不受現(xiàn)有資源的架設(shè)方式，地域或物理組態(tài)所限制。一般所指的虛擬化資源包括計算能力和資料儲存。虛擬化技術(shù)分類平臺虛擬化應(yīng)用程序虛擬化存儲虛擬化網(wǎng)絡(luò)虛擬化桌面虛擬化數(shù)據(jù)庫虛擬化網(wǎng)絡(luò)虛擬化一個共享的底層物理網(wǎng)絡(luò)上同時運行多個網(wǎng)絡(luò)架構(gòu)或網(wǎng)絡(luò)的技術(shù)虛擬網(wǎng)絡(luò)概述未來網(wǎng)絡(luò)架構(gòu)InternetServiceProviders(ISPs)InfrastructureProvider(InP)ServiceProvider(SP)VirtualNetworkProvider(VNP)VirtualNetworkOperator(VNO)ServiceProvider(SP)虛擬網(wǎng)絡(luò)概述2. 虛擬網(wǎng)絡(luò)實例

VPNVLANOverlaynetworksProgrammablenetworks虛擬網(wǎng)絡(luò)研究方向ResourceallocationResourcediscoveryAdmissioncontrolandusagepolicingVirtualnodesandvirtuallinksResourceschedulingNamingandaddressingDynamismandmobilitymanagementVirtualnetworkoperationsandmanagementSecurityandprivacyHeterogeneityofnetworkingtechnologiesNetworkvirtualizationeconomics虛擬網(wǎng)絡(luò)映射問題介紹

虛擬網(wǎng)絡(luò)映射（virtualnetworkembedding）為帶有節(jié)點和鏈路資源約束條件的虛擬網(wǎng)絡(luò)請求分配底層網(wǎng)絡(luò)資源的問題，NP-hard問題。虛擬網(wǎng)絡(luò)映射問題，是在共享的底層網(wǎng)絡(luò)中為帶有資源約束的邏輯拓?fù)浞峙湎鄳?yīng)資源。VNE是一個動態(tài)資源分

配問題虛擬網(wǎng)絡(luò)映射問題介紹3. 虛擬網(wǎng)絡(luò)映射實例a10b10c30d50a20c20b15B20C40EFAD30102020abcd1030B10C30EFAD3010bac1515101015202020202020254025252540151215（a）虛擬網(wǎng)絡(luò)請求1（c）虛擬網(wǎng)絡(luò)請求2（b）底層網(wǎng)絡(luò)（d）底層網(wǎng)絡(luò)3030虛擬網(wǎng)絡(luò)問題的形式化定義底層網(wǎng)絡(luò)

帶權(quán)無向圖，其中，表示底層節(jié)點的集合，表示底層鏈路的集合，和

分別表示底層節(jié)點

與底層鏈路

所具有的屬性。2. 虛擬網(wǎng)絡(luò)帶權(quán)無向圖

，其中，

為虛擬節(jié)點的集合，為虛擬鏈路的集合，與分別表示虛擬節(jié)點

與虛擬鏈路

的資源約束。一般來講，虛擬節(jié)點的資源約束主要考慮該虛擬節(jié)點的計算能力需求，虛擬鏈路的資源約束主要考慮該虛擬鏈路的帶寬資源需求。對于一個虛擬網(wǎng)絡(luò)請求，用三元組

來表示，其中，表示虛擬網(wǎng)絡(luò)請求的到達(dá)時刻，表示虛擬網(wǎng)絡(luò)在底層網(wǎng)絡(luò)中持續(xù)的時間。虛擬網(wǎng)絡(luò)映射問題定義為映射：

，其中，

，

。

虛擬網(wǎng)絡(luò)映射問題評價指標(biāo)虛擬網(wǎng)絡(luò)映射的主要目標(biāo)

充分利用有限的底層網(wǎng)絡(luò)資源，為更多的虛擬網(wǎng)絡(luò)請求提供服務(wù)，從而提高底層網(wǎng)絡(luò)運營收益，相應(yīng)的評價指標(biāo)有：1)底層網(wǎng)絡(luò)長期平均運營收益；2)虛擬網(wǎng)絡(luò)請求接受率；3)虛擬網(wǎng)絡(luò)映射長期平均收益開銷比。底層網(wǎng)絡(luò)長期平均運營收益

在t時刻底層網(wǎng)絡(luò)接受一個虛擬網(wǎng)絡(luò)的收益可以定義為：

其中，

表示虛擬節(jié)點的計算能力需求值，

表示虛擬鏈路的帶寬能力需求值。參數(shù)和

可用于調(diào)節(jié)計算資源與帶寬資源的相對權(quán)重。在虛擬網(wǎng)絡(luò)映射問題中，收益一般是指接受該虛擬網(wǎng)絡(luò)請求為底層網(wǎng)絡(luò)運營商帶來的經(jīng)濟(jì)收益。

在t時刻接受一個虛擬網(wǎng)絡(luò)的開銷定義為底層網(wǎng)絡(luò)分配給該虛擬網(wǎng)絡(luò)資源的和：虛擬網(wǎng)絡(luò)映射問題評價指標(biāo)

其中，

，當(dāng)?shù)讓渔溌废蛱摂M鏈路分配帶寬資源時=1，否則=0。

表示向分配帶寬的值。參數(shù)和1-的含義與式(1)一致。

底層網(wǎng)絡(luò)運營商需要高效的虛擬網(wǎng)絡(luò)映射算法以最大化其運營收益。底層網(wǎng)絡(luò)的長期平均運營收益可以定義為：3. 虛擬網(wǎng)絡(luò)請求接受率

在相同的底層網(wǎng)絡(luò)資源狀況下，高效的虛擬網(wǎng)絡(luò)映射算法應(yīng)能夠接受更多的虛擬網(wǎng)絡(luò)請求。對虛擬網(wǎng)絡(luò)請求接受率可以做如下定義：其中，

表示從t=0時刻起到T時刻被成功映射的虛擬網(wǎng)絡(luò)個數(shù)，表示從t=0時刻起到T時刻虛擬網(wǎng)絡(luò)請求的總數(shù)。虛擬網(wǎng)絡(luò)映射問題評價指標(biāo)4. 虛擬網(wǎng)絡(luò)映射長期平均收益開銷比

虛擬網(wǎng)絡(luò)映射長期平均收益開銷比可以在一定程度上反映底層網(wǎng)絡(luò)資源的利用效率，它被定義為在一段時間內(nèi)所有接受的虛擬網(wǎng)絡(luò)請求的映射收益與其相應(yīng)的資源開銷的比值:

虛擬網(wǎng)絡(luò)映射問題分類靜態(tài)映射算法與動態(tài)映射算法（S/D）按照不同的底層網(wǎng)絡(luò)資源分配方式，可以將虛擬網(wǎng)絡(luò)映射算法分為靜態(tài)映射算法與動態(tài)映射算法。靜態(tài)映射算法是指靜態(tài)地為虛擬網(wǎng)絡(luò)分配固定比例的底層網(wǎng)絡(luò)資源。而動態(tài)映射算法又可以分為動態(tài)自適應(yīng)和動態(tài)重配置的映射算法，其中，動態(tài)自適應(yīng)的映射算法根據(jù)虛擬網(wǎng)絡(luò)自身的資源需求動態(tài)為其分配底層網(wǎng)絡(luò)資源；而動態(tài)重配置的映射算法是指在虛擬網(wǎng)絡(luò)資源需求不改變的情況下，根據(jù)某種性能指標(biāo)動態(tài)地調(diào)整映射方案。

圖.動態(tài)映射算法虛擬網(wǎng)絡(luò)映射問題分類2. 離線映射算法與在線映射算法離線映射是指所有虛擬網(wǎng)絡(luò)請求信息在其被映射前均是已知的；而在線映射算法則不對虛擬網(wǎng)絡(luò)請求的到達(dá)時間，持續(xù)時間以及拓?fù)湫畔⒌茸魅魏渭僭O(shè)。

圖.在線映射算法虛擬網(wǎng)絡(luò)映射問題分類3. 集中式映射算法與分布式映射算法集中式的虛擬網(wǎng)絡(luò)映射算法由中心決策機構(gòu)根據(jù)底層網(wǎng)絡(luò)資源狀況，為虛擬網(wǎng)絡(luò)請求分配相應(yīng)資源。而分布式的虛擬網(wǎng)絡(luò)映射算法一般通過底層節(jié)點協(xié)同完成虛擬網(wǎng)絡(luò)映射過程。4. 二階段映射與一階段映射算法按照不同的虛擬節(jié)點與虛擬鏈路映射順序，可以將虛擬網(wǎng)絡(luò)映射算法分為虛擬節(jié)點優(yōu)先映射(或稱為二階段映射)與虛擬節(jié)點和鏈路同時映射(或稱為一階段映射)2類算法。5. 冗余映射與非冗余（簡單）映射算法簡單的映射算法是盡量充分利用網(wǎng)絡(luò)資源去滿足虛擬網(wǎng)絡(luò)請求，沒有預(yù)留多余的冗余資源。那么一旦底層資源失敗，很難從失敗中恢復(fù)。冗余映射算法是，在進(jìn)行虛擬網(wǎng)絡(luò)映射時，同時提供節(jié)點、鏈路的備份，使得一旦資源失敗能夠快速切換。虛擬網(wǎng)絡(luò)映射問題的研究現(xiàn)狀面向負(fù)載均衡的虛擬網(wǎng)絡(luò)映射算法包括無重配置的虛擬網(wǎng)絡(luò)映射算法與

帶有重配置的虛擬網(wǎng)絡(luò)映射算法。無重配置的虛擬網(wǎng)絡(luò)映射算法，基本思想是將虛擬節(jié)點映射到負(fù)載較輕并且離已被映射的虛擬節(jié)點較近的底層節(jié)點上，當(dāng)映射完所有虛擬節(jié)點后，使用最短路徑算法映射虛擬鏈路。由于底層網(wǎng)絡(luò)資源狀況隨著虛擬網(wǎng)絡(luò)請求的到達(dá)與離開而變化，會導(dǎo)致底層網(wǎng)絡(luò)負(fù)載不均衡，資源利用率下降等問題。帶有重配置的虛擬網(wǎng)絡(luò)映射算法，該算法周期性地檢查底層節(jié)點和鏈路負(fù)載狀況，當(dāng)節(jié)點或鏈路負(fù)載超越預(yù)先定義的閾值后，將對映射于該節(jié)點或鏈路上的所有虛擬網(wǎng)絡(luò)進(jìn)行重映射，以消除資源熱點問題。這2種虛擬網(wǎng)絡(luò)映射算法在提高底層網(wǎng)絡(luò)資源利用率方面具有較好效果，但這2種算法在虛擬網(wǎng)絡(luò)映射過程中均沒有考慮底層網(wǎng)絡(luò)與虛擬網(wǎng)絡(luò)資源約束條件，并且提出的對已映射的虛擬網(wǎng)絡(luò)進(jìn)行重映射的算法雖然可以在一定程度上平衡底層網(wǎng)絡(luò)負(fù)載，但會導(dǎo)致虛擬網(wǎng)絡(luò)服務(wù)中斷等嚴(yán)重問題。虛擬網(wǎng)絡(luò)映射問題的研究現(xiàn)狀2. 基于流量約束的虛擬網(wǎng)絡(luò)映射算法主要目標(biāo)是尋找一種既能滿足虛擬網(wǎng)絡(luò)流量需求又能高效利用底層網(wǎng)絡(luò)資源的映射方案。流量約束由以下3類約束構(gòu)成：1)終端流量約束；2)點對問流量約束；3)距離約束。雖然充分考慮了虛擬網(wǎng)絡(luò)的流量需求，但該算法在映射過程中忽略了虛擬節(jié)點資源約束條件，并且該算法只適用于拓?fù)浣Y(jié)構(gòu)為骨干-星型的虛擬網(wǎng)絡(luò)請求。底層網(wǎng)絡(luò)支持路徑分裂與遷移的虛擬網(wǎng)絡(luò)映射算法同時考慮虛擬網(wǎng)絡(luò)映射問題中的節(jié)點與鏈路資源約束、虛擬網(wǎng)絡(luò)拓?fù)湫枨蟮亩鄻有?，以及虛擬網(wǎng)絡(luò)準(zhǔn)入控制等因素，支持在線虛擬網(wǎng)絡(luò)請求的虛擬網(wǎng)絡(luò)映射算法。屬于節(jié)點映射和鏈路