虛擬網(wǎng)絡(luò)映射問題研究.pdf

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

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

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

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

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

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