臺灣博碩士論文加值系統

雲端計算(Cloud Computing)是這一兩年來最熱門的科技，其中一個重要的應用為虛擬化(Virtualization)。網路虛擬化(Network Virtualization)最重要的研究為如何將虛擬網路成功的映射到實體網路，以讓業者有更多的收入。本論文所提出虛擬網路映射演算法分為兩個部分，主要是在網路虛擬化的環境下如何做節點映射、連結映射及路徑遷移。第一部分使用節點映射及連結(Link)映射的演算法將虛擬網路映射至實體網路。第二部分為如何在實體網路做路徑遷移，使得新及舊的虛擬網路都能成功的映射到實體網路。
　路徑映射為如何將虛擬網路映射至實體網路。映射問題可分為兩個部分：節點映射及連結映射。節點映射主要為著重於如何將虛擬節點映射至實體節點，我們有針對節點映射提出節點映射演算法。連結映射又分為兩種：一為單條路徑的映射，二為多條路徑的映射。單條路徑映射是指將一條虛擬連結對應到實體網路的一條連結或路徑；多條路徑映射是指將一條虛擬連結對應到實體網路中的多條連結或路徑，我們皆使用cut-shortest path 演算法來做單條路徑映射。
　路徑遷移為當有一個新的虛擬網路要映射到實體網路時，如果實體網路的可用資源已經無法滿足此虛擬網路的需求時，如何在實體網路做路徑遷移。我們所提出的路徑遷移演算法有三個步驟：第一、先將新的虛擬網路上的虛擬節點映射至實體節點。第二、檢查所有已經映射在實體網路的虛擬網路並做判斷那個虛擬網路較適合遷移。第三、當完成遷移一個虛擬網路時，如果實體網路可提供的最大資源已足以滿足新的虛擬網路，則遷移成功；不然則繼續遷移下一個虛擬網路。我們會使用cut-shortest path演算法來做路徑遷移演算法。

Cloud Computing has been a very popular topic recently. One of the applications in the Cloud Computing is virtualization. Network virtualization has emerged as a powerful way to allow multiple virtual networks, each customized to a particular application, to run on a common substrate network. Our research consists of two parts. The first is a node mapping algorithm and a link mapping algorithm. The second is a path migration algorithm. The first part focuses on how to use the proposed node mapping algorithm and link mapping algorithm to map the virtual networks to a substrate network. The second part focuses on how to use the proposed path migration algorithm to migrate virtual links to different substrate paths, which can improve the substrate’s ability to accept more virtual networks.
The study of the first part concentrates on mapping problems. The mapping problems consist of two parts. The first is node mapping algorithm, which focus on how to map the virtual nodes to substrate nodes. The greedy algorithm is proposed to assign the virtual nodes to substrate nodes. The second is link mapping algorithm. Link mapping algorithm also consists of two problems. One is that a virtual link is mapped to a single substrate path. The widest path algorithm and cut-shortest path algorithm are proposed for this problem. The other is that a virtual link is mapped to multiple substrate paths. In this case, path diversity is enabled in the substrate network. Cut-shortest path algorithm proposed for this problem.
The study of the second part focuses on path migration in the substrate network. When a new virtual network requests to map to a substrate network, it is possible that no resource in the substrate network can meet the requirement of the new virtual network. In this situation, path migration must be enabled to re-arrange all the virtual networks that have already been mapped to the substrate network. The proposed path migration algorithm consists of three steps. First, the virtual nodes in the new virtual network are mapped to the substrate nodes by using node mapping algorithm. Second, the algorithm selects one existing virtual network to migrate to other substrate links. Third, if the resource in the substrate can meet the requirement of the new virtual network, the path migration algorithm stops. Otherwise, the algorithm continues to migrate the next existing virtual network. The cut-shortest path algorithm is proposed for path migration.

第一章. 緒論 1
第一節. 研究背景與動機 1
第二節. 研究目的及重要性 3
第二章. 參考文獻 3
第一節. 文獻介紹 3
文獻[1] 3
文獻[2] 3
文獻[3] 5
文獻[4] 5
文獻[5] 6
第二節. 文獻[2]及文獻[3]的演算法分析 6
第三章. 研究方法 10
第一節. 虛擬網路映射演算法說明 10
第二節. 問題的定義、描述及解決方法 12
3-2-1. 變數及映射說明 12
3-2-2. 映射問題說明 14
3-2-3. 虛擬網路映射至實體網路流程 15
第三節. 虛擬網路映射-虛擬節點映射 16
第四節. 虛擬網路映射-虛擬連結映射 22
3-4-1. 路徑映射 22
3-4-2. 分流路徑映射-調適映射演算法 25
第五節. 虛擬網路路經遷移 27
3-5-1. 路徑遷移問題說明 27
3-5-2. 路徑遷移演算法 29
第四章. 實驗結果 35
第一節. 實驗環境 35
4-1-1. 實驗環境說明 35
4-1-2. 各種不同方法的比較及比較項目 36
第二節. 實驗數據與結果分析-路徑映射效益分析 36
4-2-1. 映射飽和度及映射效率 36
4-2-2. 實際映射率 44
4-2-3. 端點至端點延遲時間與分流數之比較 48
4-3-1. 路徑遷移的實際映射率 49
第三節. 映射效率與實際映射率的上限探討 50
第四節. 結論 51
第五節. 未來工作 51
參考文獻 52

[1]Jorge Carapinha , Javier Jimenez, “Network Virtualization – a View from the Bottom.”, VISA’09, ACM Workshop, 2009.
[2]Minlan Yu, Yung Yi, Jennifer Rexford, Mung Chiang, ”Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration” ACM SIGCOMM Computer Communication Review, Volume 38 Issue 2, April 2008.
[3]Razzaq A.,Rathore M.S., “An Approach Towards Resource Efficient Virtual Network Embedding”, IEEE, Evolving Internet, 2010 Second International Conference ,P68 – 73,Sept. 2010.
[4]Ines HOUIDI, Wajdi LOUATI, Djamal ZEGHLACHE, “A Distributed Virtual Network Mapping Algorithm”, IEEE 2008.
[5]Nabeel Farooq Butt, N. M. Mosharaf Kabir Chowdhury, Raouf Boutaba, ” Topology-Awareness and Reoptimization Mechanism for Virtual Network Embedding”, LNCS 6091 P27-30 2010.
[6]N. M. Mosharaf Kabir Chowdhury and Raouf Boutaba,“Network Virtualization: State of the Art and Research Challenges,” IEEE Communications Magazine, July 2009, pp. 20-26.
[7]Juan Felipe Botero, Xavier Hesselbach, “The Bottlenecked Virtual Network Problem in Bandwidth Allocation for Network Virtualization,” IEEE LATINCOM’09, Sep. 2009, pp. 1-5.
[8]Karsten Oberle, Marcus Kessler, Manuel Stei, Dominik Lamp, Soren Berger, “Network Virtualization: The missing piece,” ICIN’09, Oct. 2009, pp. 1-6.
[9]David Bernstein, Erik Ludvigson, “Networking Challenges and Resultant Approaches for Large Scale Cloud Construction,” GPC’09, May 2009, pp. 136-142.
[10]Solheim, A.G., Lysne, O., Skeie, T.,Sdring, T.,Reinemo, S.A., “A Framework for Routing and Resource Allocation in Network Virtualization,” HiPC’09, Dec. 2009, pp. 129-139.
[11]Marquezan, C.C. Nobre, J.C. Granville, L.Z. Nunzi, G. Dudkowski, D. Brunner, M., “Distributed Reallocation Scheme for Virtual Network Resources,” IEEE ICC’09, June 2009, pp. 1-5.
[12]Hossfeld, T. Leibnitz, K. Nakao, A., “Modeling of Modern Router Architectures Supporting Network Virtualization,” IEEE GlobeCom’09, Nov. 30 2009-Dec. 4 2009, pp. 1-6.
[13]Martin Ansbjerg Kjar, Maria Kihl, and Anders Robertsson., “Resource Allocation and Disturbance Rejection in Web Servers using SLAs and Virtualized Servers,” IEEE TRANSACTIONS ON NETWORK SERVICE MANAGEMENT, VOL. 6, NO. 4, DECEMBER 2009, pp. 226-239.
[14]Martin Ansbjerg Kjar, Maria Kihl, and Anders Robertsson., “Virtualization: A Survey On Concepts, Taxonomy And Associated Security Issues,” ICCNT’10, Apr. 2010, pp. 222-226.
[15]Kant, K., “Towards a virtualized data center transport protocol,” IEEE INFOCOM’08, Apr. 2008, pp. 1-6.
[16]Gaurav Somani and Sanjay Chaudhary, “Application Performance Isolation in Virtualization,” IEEE CLOUD’09, pp.4 1-48.
[17]C++ Standard Template Library(STL), http://en.cppreference.com/w/cpp
[18]Boost Software, Boost C++ Libraries, http://www.boost.org/