虛擬網絡映射問題研究.pdf

1、三十年來，各種各樣的網絡技術不斷發(fā)展，使得因特網能夠支持很廣泛的應用，現已成為全球商業(yè)運行、多媒體業(yè)務、信息交換等的重要基礎設施。但是因特網的成功和普遍性也帶來一些問題，其普遍化和集中化的趨勢要求網絡具有靈活性，能夠進行網絡結構變化，但因特網現有網絡構架和協議難以滿足這一要求。網絡虛擬化是解決因特網這一瓶頸的有效方式。虛擬網絡環(huán)境能夠促進共存異質網絡結構的部署實施，不受上述因特網本身固有的限制。
　　本文針對網絡虛擬化中的資源分配

2、問題——虛擬網絡映射問題做了研究，主要解決以下三種虛擬網絡映射問題：
　　(1)動態(tài)虛擬網絡映射(Dynamic Virtual Network Embedding:DVNE))問題：采取根據當前網絡狀態(tài)，最優(yōu)映射當前虛擬網絡的方式，提出漸進貪婪動態(tài)虛擬網絡映射算法(Progressively Greedy VNE Algorithm:PG-DVNE)。在映射過程中，首先建立數學模型實現點邊協調映射，進而松弛模型的整數約束條件使得

3、模型在多項式時間內可解，但這種松弛嚴重削弱虛擬網絡點邊協調映射，通過添加約束增強虛擬網絡結點映射和邊映射的協調性，然后運用漸進貪婪的思想求解模型，最終得到虛擬網絡映射結果和優(yōu)化目標值。仿真表明，此算法在虛擬請求業(yè)務接收比例，網絡收益以及網絡收益和網絡開銷之比這三方面有很好的性能和優(yōu)勢。
　　(2)靜態(tài)虛擬網絡映射(Static Virtual Networks Embedding:SVNE)問題：首先設計數學模型，進而提出基于拉格

4、朗日松弛(Lagrange Relaxation:LR)的LR-SVNE算法和基于貪婪分解(Greedy Decomposition:GD)的GD-SVNE算法。LR-SVNE算法首先對模型中的難約束條件進行拉格朗日松弛，然后通過計算上下界的方式逼近問題的最優(yōu)解，降低了時間復雜度，有很好的收斂性；GD-SVNE算法將多個虛擬網絡按照所需資源從大到小排序，運用貪婪分解的思想將問題分解為多個子問題，每個子問題轉變?yōu)閱蝹€虛擬網絡映射問題，運用

5、漸進貪婪動態(tài)虛擬網絡映射算法(PG-DVNE)中映射每一個虛擬網絡的方法進行單個虛擬網絡的映射，此算法大大降低了時間復雜度，網絡開銷與原模型最優(yōu)目標值接近，在網絡規(guī)模和數量較大時更具有優(yōu)勢。
　　(3)支持業(yè)務量疏導的虛擬網絡映射(Virtual Network Embedding with Traffic Grooming: VNETG)問題：文中提出數學模型對VNETG問題進行描述，通過求解此模型將不同虛擬網絡的鏈路進行捆綁，

6、能夠最大限度地映射多個支持細粒度業(yè)務的虛擬網絡，同時最小化網絡開銷；此外，文中提出基于拓撲合并的映射算法(Topology Combination based VNETG Algorithm:TC-VNETG)，算法首先將多個支持細粒度業(yè)務的虛擬網絡合并成一個虛擬網絡，然后運用PG-DVNE算法中映射一個虛擬網絡的方法對合并后的虛擬網絡進行映射，此算法巧妙地實現了不同虛擬網絡之間的結點資源和光路共享。當虛擬網絡數目較小時，TC-VNET