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

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

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

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

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

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

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

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