最小化路徑長度虛擬網路嵌入演算法

Virtual Network Embedding Algorithm with Minimized Path Length

劉冠逸

指導教授 ： 許健平

國立清華大學/電機資訊學院/資訊工程學系/碩士(2014年)

https://doi.org/10.6843/NTHU.2014.00633

摘要

網路虛擬化技術能使多個異質虛擬網路在同一個實體網路共存，並使得網路更加有彈性更便於管理。網路虛擬化的最大挑戰在於如何有效率的將一個虛擬網路嵌入至實體網路，這個問題被稱作虛擬網路嵌入問題。虛擬網路嵌入問題已經被證實是一個NP困難問題，在這之前已有多項研究提出了許多啟發式(Heuristic)演算法來解決虛擬網路嵌入問題。實體網路路徑長度是解決虛擬網路嵌入問題的重要因素，然而前人的研究大多並未注重在最小化實體網路路徑長度上。
在這篇論文裡我們提出了一個注重於最小化實體網路路徑長度的虛擬網路嵌入演算法。和兩階段演算法不同，我們演算法同時進行節點嵌入以及連結嵌入。在我們所提出的演算法中，我們將有著最高鄰近頻寬(Adjacent Bandwidth)的虛擬節點嵌入至實體網路，並將虛擬連結嵌入至有著最大瓶頸頻寬(Bottleneck Bandwidth)的最短實體路徑上。實驗結果顯示我們的演算法比起其他演算法，有著更高的嵌入成功率以及更短的路徑長度。

關鍵字

網路虛擬化 ； 資源分配 ； 虛擬網路嵌入

並列摘要

Network virtualization is a technology which allows multiple heterogeneous virtual networks (VNs) to coexist on one substrate network (SN) at the same time and makes the internet more flexible and manageable. The main challenge for network virtualization is how to map a VN to a SN efficiently, which is known as the virtual network embedding (VNE) problem. VNE problem is proved as an NP-Hard problem, previous works have presented several heuristic algorithms to solve VNE problem.
In this thesis, we present a virtual network embedding algorithm which is focus on minimizing the average path length of the virtual links. Unlike the two-stage algorithm, our algorithm adopts node mapping and link mapping in the same time. Our algorithm maps the largest adjacent bandwidth virtual node to SN then map the virtual links to the substrate shortest paths which has the maximum bottleneck bandwidth. Simulation results show that our algorithm has better mapping successful rate and shorter average path length of the virtual links than others.

並列關鍵字

Network Virtualization ； Resource Allocation ； Virtual Network Embedding

參考文獻

[1] J. Matias, B. Tornero, A. Mendiola, E. Jacob, N. Toledo “Implementing Layer 2 Network Virtualization Using OpenFlow: Challenges and Solutions,” European Workshop on Software Defined Networking (EWSDN), pp. 30 –35, Darmstadt, Oct. 2012.

[3] T. Anderson, L. Peterson, S. Shenker, and J. Turner, “Overcoming the Internet Impasse through Virtualization,” Computer, Vol. 38, No. 4, pp.34–41, April 2005.

[5] D. G. Andersen, “Theoretical Approaches to Node Assignment,” unpublished Manuscript, Dec. 2002.

[7] M. Chowdhury, M. Rahman, and R. Boutaba, “Vineyard: Virtual Network Embedding Algorithms with Coordinated Node and Link Mapping,” IEEE/ACM Transactions on Networking , Vol. 20, No. 1, pp. 206 –219, Feb. 2012.

[9] S. Qing, Qi Qi, J. Wang, T. Xu and J. Liao, “Topology-aware Virtual Network Embedding through Bayesian Network Analysis,” Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), pp. 2621 –2627, Anaheim, CA, Dec. 2012.