虛擬網(wǎng)映射算法研究

　　目前，互聯(lián)網(wǎng)應(yīng)用在人們的日常生活中發(fā)揮了重要作用，但是其固有的設(shè)計(jì)規(guī)則和多服務(wù)提供商的特征，使評(píng)估和部署新的網(wǎng)絡(luò)應(yīng)用變得越來(lái)越難。近年來(lái)，人們提出了網(wǎng)絡(luò)虛擬化技術(shù)，用來(lái)解決“網(wǎng)絡(luò)僵化”問(wèn)題。該技術(shù)允許多個(gè)異構(gòu)的虛擬網(wǎng)絡(luò)共享一個(gè)底層物理網(wǎng)絡(luò)，因此得到了越來(lái)越多的應(yīng)用，但是虛擬網(wǎng)絡(luò)仍需面臨不可預(yù)測(cè)的底層網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路失效問(wèn)題，嚴(yán)重的會(huì)導(dǎo)致虛擬網(wǎng)絡(luò)不再可用。

　　虛擬網(wǎng)絡(luò)映射問(wèn)題已被證明為NP難題，早期的虛擬網(wǎng)研究以底層網(wǎng)絡(luò)資源利用最優(yōu)為目標(biāo)，設(shè)計(jì)不同的啟發(fā)式算法，但是均沒(méi)有考慮底層網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路失效時(shí)虛擬網(wǎng)絡(luò)的可靠性問(wèn)題。在映射的過(guò)程中加入虛擬網(wǎng)絡(luò)可靠性約束無(wú)疑使該問(wèn)題變得更加復(fù)雜。由于提供虛擬網(wǎng)絡(luò)可靠性保證需要消耗更多的底層網(wǎng)絡(luò)資源，因此所設(shè)計(jì)的算法應(yīng)該在虛擬網(wǎng)絡(luò)可靠性和底層網(wǎng)絡(luò)資源消耗之間做一個(gè)權(quán)衡。本文提出了一個(gè)新的可靠虛擬網(wǎng)絡(luò)映射算法RVNM，目的是在保證虛擬網(wǎng)絡(luò)可靠性的同時(shí)最小化底層網(wǎng)絡(luò)資源開(kāi)銷(xiāo)。在節(jié)點(diǎn)映射階段，該方法不預(yù)留底層網(wǎng)絡(luò)保護(hù)資源，將底層物理節(jié)點(diǎn)按照可靠性和資源負(fù)載平衡綜合進(jìn)行評(píng)估并排序，然后將虛擬節(jié)點(diǎn)映射到具有高評(píng)估值的底層物理節(jié)點(diǎn)上，實(shí)驗(yàn)表明該機(jī)制可以大大提高虛擬節(jié)點(diǎn)的抗毀性。在鏈路映射階段，本文設(shè)計(jì)了一個(gè)新的鏈路映射機(jī)制，該機(jī)制基于共享路徑保護(hù)策略。實(shí)驗(yàn)表明，該機(jī)制可在底層網(wǎng)絡(luò)帶寬使用方面接近最優(yōu)。