A Fast Local Search Algorithm for Virtual Network Embedding

一個虛擬網路映射的快速區域搜尋演算法

王偉一(Wang, Wei Yi)

指導教授 ： 張正尚

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2016年)

摘要

網路虛擬化是為了提供下世代網路服務的一個新興題目。它透過切割原本的網際網路服務供應商的角色，把底層網路設備的管理交給基礎設備供應商（InP），把頂層提供使用者服務的任務交給服務供應商（SP），這使得資源利用和使用者分割的概念更加鮮明。
　　訂價的問題激發了我們的想法，所以我們設定我們的目標函數就是虛擬網路的價格。我們主要提出一個相對於精確解較快的演算法，來解決虛擬網路映射的問題。這演算法叫做「排列互換法」。我們利用它在可接受的時間內（幾秒鐘）來尋找一個區域最佳解。排列互換法先用虛擬結點的排列組合來表示一個虛擬網路的映射，再兩兩結點互換排列使得目標函數的值能疊代的下降至區域最佳解。
　　在排列互換法中，我們比較四種方法：最適配置－貪婪選擇、最適配置－隨機選擇、混合隨機配置－貪婪選擇和混合隨機配置－隨機選擇。我們在四種底層網路上面做模擬：Fat-Tree、BCube、VL2和Cogent，比較它們的效能和效率。
　　我們實驗結果是沒有隨機變數的演算法是最差的，而且貪婪選擇對效能的提升比混合隨機配置來得低。因此要兼顧效能和效率，混合隨機配置－隨機選擇會是最好的演算法。

關鍵字

虛擬網路映射 ； 網路虛擬化 ； 軟體定義網路

並列摘要

Network virtualization is a popular topic about providing next-generation Internet
services. It primarily virtualizes the resources managed by the Infrastructure Provider
(InP) and the demands claimed by the Service Provider (SP) to make the concepts of
the resource allocation and the user isolation to be more clearly.
We inspired by the insight of the pricing problem, so that we set the price of virtual
requests on the objective function. Then we focuses on a relatively fast algorithm for
solving the VNE than exact solutions. We propose the Permutation Swap Method (PSM)
to nd a local optimal solution in a reasonable computation time (few seconds). The
PSM represents a network mapping by a node permutation, and it iteratively swaps two
nodes' permutation to obtain a lower objective value until reaching a local minimum.
We apply four different algorithms: Best Fit with Greedy Selection (BF-GS), Best Fit
with Random Selection (BF-RS), Mixed Random Fit with Greedy Selection (MRF-GS)
and Mixed Random Fit with Random Selection (MRF-RS) in the PSM, and we conduct
experiments to compare the performance and efficiency of these algorithms in three data
center networks: Fat-Tree, BCube, VL2 and an inter-data-center network: Cogent.
The experimental results are that the algorithm without random factor has the worst
performance, and the performance gain by using the greedy selection is less than the one
by using the mixed random t solution. Hence to take into account both the performance
and efficiency, the MRF-RS method is the best algorithm.

並列關鍵字

Virtual Network Embedding ； Network Virtualization ； Software Defined Network

參考文獻

[1] A. Khan, A. Zugenmaier, D. Jurca, and W. Kellerer, Network virtualization: a

hypervisor for the internet?" IEEE Communications Magazine, vol. 50, no. 1, pp.

Technologies, perspectives, and frontiers," Journal of Lightwave Technology, vol. 31,

no. 4, pp. 523{537, 2013.

[3] J. Lischka and H. Karl, A virtual network mapping algorithm based on subgraph