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

VPNVLANOverlaynetworksProgrammablenetworks虛擬網絡研究方向ResourceallocationResourcediscoveryAdmissioncontrolandusagepolicingVirtualnodesandvirtuallinksResourceschedulingNamingandaddressingDynamismandmobilitymanagementVirtualnetworkoperationsandmanagementSecurityandprivacyHeterogeneityofnetworkingtechnologiesNetworkvirtualizationeconomics虛擬網絡映射問題介紹

虛擬網絡映射（virtualnetworkembedding）為帶有節點和鏈路資源約束條件的虛擬網絡請求分配底層網絡資源的問題，NP-hard問題。虛擬網絡映射問題，是在共享的底層網絡中為帶有資源約束的邏輯拓撲分配相應資源。VNE是一個動態資源分

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

帶權無向圖，其中，表示底層節點的集合，表示底層鏈路的集合，和

分別表示底層節點

與底層鏈路

所具有的屬性。2. 虛擬網絡帶權無向圖

，其中，

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

與虛擬鏈路

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

來表示，其中，表示虛擬網絡請求的到達時刻，表示虛擬網絡在底層網絡中持續的時間。虛擬網絡映射問題定義為映射：

，其中，

，

。

虛擬網絡映射問題評價指標虛擬網絡映射的主要目標

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

在t時刻底層網絡接受一個虛擬網絡的收益可以定義為：

其中，

表示虛擬節點的計算能力需求值，

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

可用于調節計算資源與帶寬資源的相對權重。在虛擬網絡映射問題中，收益一般是指接受該虛擬網絡請求為底層網絡運營商帶來的經濟收益。

在t時刻接受一個虛擬網絡的開銷定義為底層網絡分配給該虛擬網絡資源的和：虛擬網絡映射問題評價指標

其中，

，當底層鏈路向虛擬鏈路分配帶寬資源時=1，否則=0。

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

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

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

表示從t=0時刻起到T時刻被成功映射的虛擬網絡個數，表示從t=0時刻起到T時刻虛擬網絡請求的總數。虛擬網絡映射問題評價指標4. 虛擬網絡映射長期平均收益開銷比

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

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

圖.動態映射算法虛擬網絡映射問題分類2. 離線映射算法與在線映射算法離線映射是指所有虛擬網絡請求信息在其被映射前均是已知的；而在線映射算法則不對虛擬網絡請求的到達時間，持續時間以及拓撲信息等作任何假設。

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

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