虛擬網(wǎng)絡(luò)的高效和可靠映射算法研究.pdf

1、網(wǎng)絡(luò)虛擬化在底層基礎(chǔ)設(shè)施上抽象出多個相互獨立的虛擬網(wǎng)絡(luò)，不同的虛擬網(wǎng)絡(luò)可以使用不同的網(wǎng)絡(luò)技術(shù)和構(gòu)架。由此可以克服當(dāng)前網(wǎng)絡(luò)僵化，即部署全新網(wǎng)絡(luò)技術(shù)不靈活的問題。另外，多個虛擬網(wǎng)絡(luò)共享相同的底層基礎(chǔ)設(shè)施，由此可以更有效和靈活地利用底層資源，是云計算的關(guān)鍵技術(shù)。
　　將底層（節(jié)點）計算和（鏈路）通信資源分配給虛擬網(wǎng)絡(luò)是部署虛擬網(wǎng)絡(luò)的基礎(chǔ)。虛擬網(wǎng)絡(luò)是由虛擬節(jié)點和虛擬鏈路構(gòu)成，其中虛擬節(jié)點有計算資源（如CPU）需求且虛擬鏈路有帶寬需求。虛擬

2、網(wǎng)絡(luò)的資源分配，即虛擬網(wǎng)絡(luò)映射就是指將虛擬節(jié)點和虛擬鏈路映射到哪些底層節(jié)點和底層路徑上。本文研究了基本的虛擬網(wǎng)絡(luò)映射、跨域（管理域和數(shù)據(jù)中心）虛擬網(wǎng)絡(luò)映射和可靠虛擬網(wǎng)絡(luò)映射，并為相應(yīng)的問題提出了相比現(xiàn)有算法，映射成本（即資源成本）、運行時間或服務(wù)質(zhì)量更好的算法。
　　基本的虛擬網(wǎng)絡(luò)映射是指給定虛擬網(wǎng)絡(luò)請求和底層基礎(chǔ)設(shè)施，采用集中式的方法用最小的資源成本完成虛擬網(wǎng)絡(luò)到底層基礎(chǔ)設(shè)施的映射。虛擬網(wǎng)絡(luò)映射問題是NP-hard，需要啟發(fā)式算

3、法求解。目前知名的vnmFlib算法基于同構(gòu)圖搜索尋找虛擬網(wǎng)絡(luò)在底層基礎(chǔ)設(shè)施上的可行映射。vnmFlib算法內(nèi)部基于不同的設(shè)置，存在或是運行時間較長或是映射成本較高的缺點。本文提出了 vnmFlib的改進算法Improved-vnmFlib，通過預(yù)估成本來引導(dǎo)映射，令I(lǐng)mproved-vnmFlib算法同時具有運行時間短和映射成本低的優(yōu)點，即更高效。
　　相比基本虛擬網(wǎng)絡(luò)映射，跨域虛擬網(wǎng)絡(luò)映射問題中底層基礎(chǔ)設(shè)施的構(gòu)成更加復(fù)雜。本文

4、研究了給定虛擬網(wǎng)絡(luò)請求和多管理域構(gòu)成的底層基礎(chǔ)設(shè)施，以優(yōu)化全局映射價格和服務(wù)質(zhì)量為目標完成虛擬網(wǎng)絡(luò)的跨域映射。其中，由于底層的每個管理域不公開域內(nèi)的拓撲和資源信息，所以需要采用分布式的方法完成映射?，F(xiàn)有的跨域映射方法都是先在不同的管理域內(nèi)完成虛擬網(wǎng)絡(luò)子圖的映射，再為端點在不同域中的虛擬鏈路建立跨域路徑，該類方法缺少全局視角以優(yōu)化全局映射表現(xiàn)。本文提出了全局映射價格更低且服務(wù)質(zhì)量更好，即更高效的跨域虛擬網(wǎng)絡(luò)映射框架MD-VNM（Multi

5、ple Domain Virtual Network Mapping）。MD-VNM通過不同管理域提供的候選映射，建立出一個全局視角，令候選映射的選擇可以考慮到全局的映射表現(xiàn)。
　　另外，本文還研究了給定虛擬網(wǎng)絡(luò)請求和多數(shù)據(jù)中心構(gòu)成的底層基礎(chǔ)設(shè)施，以最小化成本為目標完成虛擬網(wǎng)絡(luò)映射。其中，數(shù)據(jù)中心通過廣域網(wǎng)互聯(lián)，且數(shù)據(jù)中心內(nèi)的單位帶寬成本比廣域網(wǎng)低。目前的研究中缺少為跨數(shù)據(jù)中心虛擬網(wǎng)絡(luò)保證針對數(shù)據(jù)中心失效的生存能力。本文則研究了該

6、問題，提出了 SG-VNM（Survivability Guarantee Virtual Network Mapping）算法，通過適當(dāng)?shù)貙⑻摂M節(jié)點分布于多個數(shù)據(jù)中心，在保證生存能力需求的同時減少了域間帶寬成本。在保證生存能力需求的條件下，SG-VNM算法可以得到比現(xiàn)有算法更低的映射成本。
　　可靠虛擬網(wǎng)絡(luò)映射是指給定虛擬網(wǎng)絡(luò)請求和底層基礎(chǔ)設(shè)施，基于物理服器的概率失效，在保證一定可靠性的條件下以最小化成本為目標完成虛擬網(wǎng)絡(luò)到底層

7、基礎(chǔ)設(shè)施的映射。為保證虛擬網(wǎng)絡(luò)的可靠性，工作虛擬網(wǎng)絡(luò)需要增加備份虛擬節(jié)點和備份虛擬鏈路，即可靠虛擬網(wǎng)絡(luò)。為了最小化映射成本，可靠虛擬網(wǎng)絡(luò)映射需要考慮資源共享。而目前關(guān)于可靠虛擬網(wǎng)絡(luò)映射的研究中只考慮了備份帶寬之間的共享，而忽略了工作帶寬的再利用（即工作帶寬和備份帶寬之間的共享）。首先，本文基于集中共享備份虛擬節(jié)點的方法，提出了可靠虛擬網(wǎng)絡(luò)映射算法RVNM（Reliable Virtual NetworkMapping）。RVNM算法同時