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

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

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

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

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

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

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

與底層鏈路

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

，其中，

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

與虛擬鏈路

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

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

，其中，

，

。

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

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

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

其中，

表示虛擬節(jié)點(diǎn)的計(jì)算能力需求值，

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

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

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

其中，

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

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

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

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

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

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

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

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

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

帶有重配置的虛擬網(wǎng)絡(luò)映射算法。無(wú)重配置的虛擬網(wǎng)絡(luò)映射算法，基本思想是將虛擬節(jié)點(diǎn)映射到負(fù)載較輕并且離已被映射的虛擬節(jié)點(diǎn)較近的底層節(jié)點(diǎn)上，當(dāng)映射完所有虛擬節(jié)點(diǎn)后，使用最短路徑算法映射虛擬鏈路。由于底層網(wǎng)絡(luò)資源狀況隨著虛擬網(wǎng)絡(luò)請(qǐng)求的到達(dá)與離開(kāi)而變化，會(huì)導(dǎo)致底層網(wǎng)絡(luò)負(fù)載不均衡，資源利用率下降等問(wèn)題。帶有重配置的虛擬網(wǎng)絡(luò)映射算法，該算法周期性地檢查底層節(jié)點(diǎn)和鏈路負(fù)載狀況，當(dāng)節(jié)點(diǎn)或鏈路負(fù)載超越預(yù)先定義的閾值后，將對(duì)映射于該節(jié)點(diǎn)或鏈路上的所有虛擬網(wǎng)絡(luò)進(jìn)行重映射，以消除資源熱點(diǎn)問(wèn)題。這2種虛擬網(wǎng)絡(luò)映射算法在提高底層網(wǎng)絡(luò)資源利用率方面具有較好效果，但這2種算法在虛擬網(wǎng)絡(luò)映射過(guò)程中均沒(méi)有考慮底層網(wǎng)絡(luò)與虛擬網(wǎng)絡(luò)資源約束條件，并且提出的對(duì)已映射的虛擬網(wǎng)絡(luò)進(jìn)行重映射的算法雖然可以在一定程度上平衡底層網(wǎng)絡(luò)負(fù)載，但會(huì)導(dǎo)致虛擬網(wǎng)絡(luò)服務(wù)中斷等嚴(yán)重問(wèn)題。虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀2. 基于流量約束的虛擬網(wǎng)絡(luò)映射算法主要目標(biāo)是尋找一種既能滿足虛擬網(wǎng)絡(luò)流量需求又能高效利用底層網(wǎng)絡(luò)資源的映射方案。流量約束由以下3類約束構(gòu)成：1)終端流量約束；2)點(diǎn)對(duì)問(wèn)流量約束；3)距離約束。雖然充分考慮了虛擬網(wǎng)絡(luò)的流量需求，但該算法在映射過(guò)程中忽略了虛擬節(jié)點(diǎn)資源約束條件，并且該算法只適用于拓?fù)浣Y(jié)構(gòu)為骨干-星型的虛擬網(wǎng)絡(luò)請(qǐng)求。底層網(wǎng)絡(luò)支持路徑分裂與遷移的虛擬網(wǎng)絡(luò)映射算法同時(shí)考慮虛擬網(wǎng)絡(luò)映射問(wèn)題中的節(jié)點(diǎn)與鏈路資源約束、虛擬網(wǎng)絡(luò)拓?fù)湫枨蟮亩鄻有?，以及虛擬網(wǎng)絡(luò)準(zhǔn)入控制等因素，支持在線虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬網(wǎng)絡(luò)映射算法。屬于節(jié)點(diǎn)映射和鏈路映射分開(kāi)的兩階段算法。該算法有益于提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率和底層網(wǎng)絡(luò)資源利用率，但由于該算法在虛擬節(jié)點(diǎn)映射階段并沒(méi)有對(duì)虛擬鏈路的映射進(jìn)行考慮，因此可能會(huì)導(dǎo)致虛擬鏈路映射開(kāi)銷較大的問(wèn)題。虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀底層網(wǎng)絡(luò)支持路徑分裂與遷移的虛擬網(wǎng)絡(luò)映射算法圖.支持路徑分裂的虛擬網(wǎng)絡(luò)映射算法虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀底層網(wǎng)絡(luò)支持路徑分裂與遷移的虛擬網(wǎng)絡(luò)映射算法圖.支持路徑遷移的虛擬網(wǎng)絡(luò)映射算法虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀4. 協(xié)同節(jié)點(diǎn)與鏈路映射的虛擬網(wǎng)絡(luò)映射算法節(jié)點(diǎn)與鏈路協(xié)同是指在虛擬節(jié)點(diǎn)的映射階段同時(shí)考慮虛擬鏈路映射。一定程度上降低了每次虛擬網(wǎng)絡(luò)映射的資源開(kāi)銷，為接受更多的虛擬網(wǎng)絡(luò)請(qǐng)求當(dāng)?shù)讓泳W(wǎng)絡(luò)不支持路徑分裂時(shí)，該算法性能較差。提供了空間，但該算法過(guò)度地依賴底層網(wǎng)絡(luò)支持路徑分裂這一特性，忽略了其帶來(lái)的負(fù)面影響。虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀5. 基于子圖同構(gòu)檢測(cè)的虛擬網(wǎng)絡(luò)映射算法該算法的基本思想是在同一階段映射虛擬節(jié)點(diǎn)和鏈路，當(dāng)虛擬節(jié)點(diǎn)被成功映射后，便采用最短路徑算法映射與該節(jié)點(diǎn)相連的虛擬鏈路。在映射過(guò)程中，如果有虛擬鏈路映射失敗的情況發(fā)生，則回溯到上一個(gè)虛擬節(jié)點(diǎn)映射階段進(jìn)行節(jié)點(diǎn)重映射。由于該算法在同一階段映射虛擬節(jié)點(diǎn)和鏈路，因此它可以有效避免虛擬鏈路被映射到底層網(wǎng)絡(luò)中長(zhǎng)路徑的問(wèn)題，從而降低了虛擬網(wǎng)絡(luò)映射的底層網(wǎng)絡(luò)資源開(kāi)銷，提高底層網(wǎng)絡(luò)資源利用效率，但該算法本質(zhì)是一種回溯算法，計(jì)算開(kāi)銷較大，而且．該算法不能夠處理虛擬節(jié)點(diǎn)帶有位置需求的虛擬網(wǎng)絡(luò)請(qǐng)求。6. 面向QoS的虛擬網(wǎng)絡(luò)映射算法該算法的基本思想是盡可能地將一條虛擬鏈路映射到一條底層鏈路上。該算法能夠處理帶有高級(jí)別QOS需求的虛擬網(wǎng)絡(luò)請(qǐng)求，但由于其虛擬節(jié)點(diǎn)與虛擬鏈路的映射過(guò)程采用回溯方式進(jìn)行，計(jì)算開(kāi)銷大。此外，當(dāng)?shù)讓泳W(wǎng)絡(luò)資源不充足或虛擬網(wǎng)絡(luò)規(guī)模較大時(shí)，采用該算法很難獲得能夠滿足虛擬網(wǎng)絡(luò)映射資源需求的可行映射方案。虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀分布式的虛擬網(wǎng)絡(luò)映射算法該算法由虛擬網(wǎng)絡(luò)拓?fù)浞纸夂陀成?個(gè)階段組成。雖然該算法可有效避免集中式虛擬網(wǎng)絡(luò)映射算法單點(diǎn)故障問(wèn)題，能夠快速應(yīng)對(duì)底層網(wǎng)絡(luò)局部故障，但當(dāng)?shù)讓泳W(wǎng)絡(luò)規(guī)模較大時(shí)，代理節(jié)點(diǎn)間信息同步與交互通信開(kāi)銷大，性能方面還不能與集中式算法相比。動(dòng)態(tài)自適應(yīng)的虛擬網(wǎng)絡(luò)映射算法底層鏈路監(jiān)測(cè)各個(gè)虛擬網(wǎng)絡(luò)的流量狀況，并根據(jù)其承載的虛擬鏈路的擁塞級(jí)別和性能指標(biāo)等局部信息，周期性地重新為虛擬鏈路分配共享的底層帶寬資源。夠動(dòng)態(tài)自適應(yīng)地為虛擬網(wǎng)絡(luò)分配底層網(wǎng)絡(luò)帶寬資源，從而提高了底層網(wǎng)絡(luò)帶寬資源利用效率，但它并沒(méi)有對(duì)虛擬節(jié)點(diǎn)的映射和資源分配問(wèn)題進(jìn)行考慮，而且由于周期性地對(duì)所有虛擬網(wǎng)絡(luò)的帶寬資源分配進(jìn)行調(diào)整，系統(tǒng)的穩(wěn)定性是一個(gè)值得關(guān)注的問(wèn)題。虛擬網(wǎng)絡(luò)映射問(wèn)題的研究現(xiàn)狀9. 拓?fù)涓兄奶摂M網(wǎng)絡(luò)映射算法借鑒GooglePageRank思想，基于馬爾科夫隨機(jī)游動(dòng)(randomwalk)模型。為底層(或虛擬)節(jié)點(diǎn)資源度量方法NodeRank。節(jié)點(diǎn)的NodeRank值不僅可以反映當(dāng)前節(jié)點(diǎn)的資源能力(例如，計(jì)算能力與帶寬能力)，而且還能夠反映其周?chē)?jié)點(diǎn)的資源能力?；谶@種拓?fù)涓兄墓?jié)點(diǎn)資源度量方法，有2種虛擬網(wǎng)絡(luò)映射算法：RW-MaxMatch和RW-BFS。RW-MaxMatch是一種二階段的虛擬網(wǎng)絡(luò)映射算法，該算法的主要思想是：將具有較大NodeRank值的虛擬節(jié)點(diǎn)映射到具有較大NodeRank值的底層節(jié)點(diǎn)上，然后利用最短路徑算法或多商品流算法映射虛擬鏈路。而RW-BFS是一種一階段的虛擬網(wǎng)絡(luò)映射算法，虛擬節(jié)點(diǎn)的映射順序和底層節(jié)點(diǎn)的選取均按照廣度優(yōu)先搜索的順序進(jìn)行，并且廣度優(yōu)先搜索的每一層網(wǎng)絡(luò)節(jié)點(diǎn)按NodeRank值大小排序。當(dāng)每個(gè)虛擬節(jié)點(diǎn)映射成功后便同時(shí)映射其虛擬鏈路，若虛擬節(jié)點(diǎn)或鏈路映射失敗則重新映射前一個(gè)虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)映射和虛擬鏈路映射在映射過(guò)程中交替進(jìn)行。其主要思想是：虛擬網(wǎng)絡(luò)映射研究新方向底層網(wǎng)絡(luò)資源的高效利用

對(duì)于靜態(tài)的虛擬網(wǎng)絡(luò)映射算法，如果要底層網(wǎng)絡(luò)支持路徑分裂和遷移，導(dǎo)致分組無(wú)序和分組丟失問(wèn)題，從而對(duì)虛擬網(wǎng)絡(luò)性能造成影響。可以考慮在底層網(wǎng)絡(luò)不支持路徑分裂時(shí)，將虛擬網(wǎng)絡(luò)映射問(wèn)