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

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

2、問題——虛擬網(wǎng)絡(luò)映射問題做了研究，主要解決以下三種虛擬網(wǎng)絡(luò)映射問題：
　　(1)動(dòng)態(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ò)的方式，提出漸進(jìn)貪婪動(dòng)態(tài)虛擬網(wǎng)絡(luò)映射算法(Progressively Greedy VNE Algorithm:PG-DVNE)。在映射過程中，首先建立數(shù)學(xué)模型實(shí)現(xiàn)點(diǎn)邊協(xié)調(diào)映射，進(jìn)而松弛模型的整數(shù)約束條件使得

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

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

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

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