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

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

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