臺灣博碩士論文加值系統

隨著雲端運算和虛擬化技術的蓬勃發展，全球各地提供各式運算、存儲資源和網路資源的網路測試平台與日俱增，而平台上層應用服務對於多樣化資源和真實實驗網路環境的需求也越發顯著。因此，為了達到應用服務的需求，有別於一般傳統型資源控制架構，一個全域性的資源控制架構需要可以集結多個網路測試平台的資源，佈署應用服務於不同的網路測試平台，並以專屬的資料網段將跨平台佈署的資源做連接，以確保每個應用服務所屬實驗環境的獨立性和安全性。
本論文旨在提出一個全域性的資源控制架構，目的在聚集來自各單位和位於不同地理位置的網路測試平台形成聯盟，共建構一個巨大的虛擬網路資源池，使平台能共享彼此的資源而形成大型的聯合網路測試平台。每個測試平台能獨立的依上層應用服務的需求彈性地分配和管理資源，當遇到原平台不提供的資源型態需求或資源不足的狀況，測試平台會向位在同一個聯盟內的其他測試平台請求支援，而將服務佈建在可支援的測試平台上，再以軟體定義網路來連接資源並設定應用服務實驗網路位於封閉且獨立的VLAN網段。本論文設計了一分散式的跨測試平台虛擬網路嵌入的技術，同時開發LAN社群虛擬網路切割技術來改良跨測試平台，和測試平台內虛擬網路嵌入的效能，而模擬結果顯示改良後的演算法可以提高測試平台的收入和增加服務需求數。VLAN Tag轉換的技術被實作於連接位於不同平台，但被分配到同一個應用服務的資源。
最後，我們將此資源控制架構分別佈署於國立成功大學電機大樓和奇美樓，實作國內第一個聯合且疊加於工作網路的聯合網路測試平台。

With the rapid development of cloud computing and virtualization techniques, the needs for applications to use multiple resources distributed in different network testbeds, a.k.a resource sites have also grown greatly. With this demands, an improved and scalable Resource Control Framework is required to replace the traditional management orchestration used by each resource site. This adaptive Resource Control Framework is supposed to offer a mechanism to dynamically allocate and join physical resources located in varied sites according requirements from applications.
This thesis designs a global Resource Control Framework to provide a platform as Networked Testbed over the Software Defined Network for users to deploy their applications in an isolated network environment. The architecture of RCF realizes the concept of network resource pool to assemble multiple resource sites to share their resources with each other. A distributed inter-domain Virtual Network Embedding method is devised to deploy an application across different resource sites. Moreover, a new LAN community based division method is used to improve the performance of inter-domain and intra-domain VNE algorithm. The simulation results show the better embedding revenue and higher application acceptance ratio. In addition, a VLAN tag translation mechanism is adopted to stitch the application virtual network between resource sites. This thesis implements RCF in two resource sites at NCKU EE building and CHIMEI building respectively, forming the first federated, Network Testbed overlay the production network in Taiwan.

1. Introduction 9
1.1 General Background 9
1.2 Motivation and Purpose 12
1.3 Contributions 13
1.4 Overview 14
2. Related Work 15
2.1 Control Framework 15
2.1.1 PlanetLab 16
2.1.2 GENI 18
2.1.3 ORCA 20
2.2 Network Testbed 22
2.2.1 PlanetLab 22
2.2.2 Emulab 23
2.2.3 ProtoGENI 24
2.2.4 ExoGENI 27
2.3 Virtual Network Embedding 29
2.3.1 Intra-domain VNE 32
2.3.2 Inter-cloud VNE 36
3. System Design 40
3.1 Resource Control Framework 43
3.1.1 Actors in Control Framework 43
3.1.2 Process of Creating Slice 46
3.1.3 Design of Control Network and Data network 49
3.2 LAN Community Division 51
3.3 Resource Allocation Mechanism 57
3.3.1 Inter-domain Virtual Network Embedding Algorithm 57
3.3.2 Intra-domain Virtual Network Embedding Algorithm 60
4. Evaluation 62
4.1 Simulation scenario 62
4.2 Result and Discussion 67
5. Implementation and Use case 71
6. Conclusion and Future Works 75
7. References 76

表目錄
Table 1 Extended RM APIs 46

圖目錄
Figure 1 Federated Testbeds in Taiwan 11
Figure 2 Architecture of MyPLC [15] 17
Figure 3 GENI Control Framework [19] 19
Figure 4 Interaction between users and GENI Control Framework [19] 20
Figure 5 Architecture of ORCA [14] 21
Figure 6 Process of creating Slice in ORCA [14 ] 22
Figure 7 Architecture of Emulab [27] 24
Figure 8 Architecture of ProtoGENI [28] 25
Figure 9 Process of Creating slice at the back end in ProtoGENI [28] 27
Figure 10 ExoGENI Software stack [32] 28
Figure 11 Architecture of ExoGENI [32] 29
Figure 12 Two virtual networks mapped onto one substrate network [42] 30
Figure 13 Two step of virtual network embedding procedure 32
Figure 14 (a) virtual network (b) Process of embedding VNR in (a) [50] 39
Figure 15 System Overview 41
Figure 16 System Architecture 42
Figure 17 Process of creating a slice in single site 47
Figure 18 Process of creating slice across 2 sites 49
Figure 19 Control Network and Data Network 51
Figure 20 (a) Virtual network, and (b) shows the embedded link cost of (a) 52
Figure 21 LAN Community Division Algorithm. 53
Figure 22 (c) New VNR generated at 2ndt run. (d) New VNR generated at 3rd run 55
Figure 23 Inter-domain VNE Algorithm 58
Figure 24 Allocation Results 59
Figure 25 Intra-domain virtual network embedding algorithm 61
Figure 26 Simulated physical network 64
Figure 27 Performance of simulated results in small sized physical network. (a) Revenue, (b) Cost, (c) Cost and Revenue Ratio, (d) Solution Level, (e) Run time of VNR presented by nodes number, (g) Acceptance Ratio 65
Figure 28 Performance of simulated results in small sized physical network. (a) Revenue, (b) Cost, (c) Cost and Revenue Ratio, (d) Solution Level, (e) Run time of VNR presented by nodes number, (g) Acceptance Ratio 66
Figure 29 Radial topology with one node at center. 68
Figure 30, Radial topology with LAN in center 69
Figure 31 Single LAN topology 70
Figure 32 Federated Testbed at NCKU 71
Figure 33 (a) Network Security use case, (b) mapped topology of (a) 72
Figure 34 VNR is embedded inter-hosts at Site A in (a). VNR is embedded across Site A and Site B in (b) 73
Figure 35 Slice Distribution 74
Figure 36 Resource Utilization and Slice Distribution 74

[1].B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. “An Integrated Experimental Environment for Distributed Systems and Networks. In Proc. of the Fifth Symposium on Operating Systems Design and Implementation, pages 255–270, Boston, MA, Dec. 2002.
[2].Nick McKeown “Software Defined Network
[3].GENI http://www.geni.net/
[4].Larry Peterson, Andy Bavier, Marc E. Fiuczynski, Steve Muir “Experiences Building PlanetLab
[5].ProtoGENI http://www.protogeni.net/
[6].GRE tunnel http://en.wikipedia.org/wiki/Generic_Routing_Encapsulation
[7].ExoGENI https://wiki.exogeni.net/doku.php
[8].Internet2 http://www.internet2.edu/
[9].BEN https://ben.renci.org/
[10].NLR http://www.nlr.net/
[11].CSEP http://csep.mgt.ncu.edu.tw/
[12].Testbed@TWISC http://testbed.ncku.edu.tw/
[13].GENI Control Framework http://groups.geni.net/geni/wiki/GeniControl
[14].GENI-ORCA https://geni-orca.renci.org/trac/
[15].PlanetLab Central PLC portable installation https://www.planet-lab.org/
[16].XML-RPC http://xmlrpc.scripting.com/default.html
[17].SSH http://www.ietf.org/rfc/rfc4251.txt
[18].GENI Design http://groups.geni.net/geni/wiki/GeniDesign
[19].GENI Architecture Team, Marshall Brinn and Rob Ricci, “GENI Federation Software Architecture Document
[20].GENI Control Framework Requirement. http://groups.geni.net/geni/wiki/GeniControlFrameworkRequirements
[21].GENI AM API http://groups.geni.net/geni/wiki/GeniApi
[22].ACADEMIA SINCA http://www.sinica.edu.tw/index.shtml
[23].SNMP http://www.snmp.com/protocol/snmp_rfcs.shtml
[24].NFS http://www.ietf.org/rfc/rfc3530.txt
[25].Network Simulator version 2 http://www.isi.edu/nsnam/ns/
[26].NetBuild GUI https://wiki.emulab.net/wiki/netbuilddoc
[27].Emulab Architecture https://wiki.emulab.net/wiki/install/network.html
[28].Protogeni Architecture http://groups.geni.net/geni/wiki/ProtoGENI
[29].Flack http://protogeni.net/flack
[30].GRE Tunnel http://en.wikipedia.org/wiki/Generic_Routing_Encapsulation
[31].StartLight http://www.startap.net/starlight/
[32].ExoGENI https://wiki.exogeni.net/doku.php
[33].GENI I＆M Tool http://groups.geni.net/geni/wiki/GeniInstMeas
[34].FOAM http://groups.geni.net/geni/wiki/OpenFlow/FOAM
[35].Open Network Foundation, “OpenFlow Switch Specification, https://www.opennetworking.org/
[36].OpenStack http://www.openstack.org/
[37].Xcat http://xcat.sourceforge.net/
[38].GENI rack http://groups.geni.net/geni/wiki/GENIRacksHome
[39].FlowVisor https://openflow.stanford.edu/display/DOCS/Flowvisor
[40].SDN Controller https://www.opennetworking.org/
[41].Q in Q Tunneling http://en.wikipedia.org/wiki/IEEE_802.1ad
[42].Andreas Fischer, Juan Felipe Botero, Michael Till Beck, Hermann de Meer, and Xavier Hesselbach, “Virtual Network Embedding: A Survey, IEEE COMMUNICATIONS SURVEYS ＆ TUTORIALS, VOL. 15, NO. 4, FOURTH QUARTER 2013
[43].M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking virtual network embedding: Substrate support for path splitting and migration, ACM SIGCOMM CCR, vol. 38, no. 2, pp. 17–29, Apr. 2008.
[44].D. Chen, X. Qiu, Z. Qu, S. Zhang, and W. Li, “Algorithm for virtual nodes reconfiguration on network virtualization, in Advanced Intelligence and Awareness Internet (AIAI 2011), 2011 International Conference on, oct. 2011.
[45].Gang Sun · Hongfang Yu · Vishal Anand · Lemin Li Hao Di, “Optimal provisioning for virtual network request in cloud-based data centers, Photon Netw Commun (2012) 24:118–131
[46].FIRE project http://www.ict-fire.eu/home/fire-projects.html
[47].Chrysa Papagianni, Aris Leivadeas, Symeon Papavassiliou, Vasilis Maglaris, Cristina Cervello´-Pastor, and Alvaro Monje, “On the Optimal Allocation of Virtual Resources in Cloud Computing Networks, IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013
[48].Yufeng Xin, Ilia Baldine, Anirban Mandal, “Embedding Virtual Topologies in Networked Clouds CFI ’11 June 13-15, 2011, Seoul, Korea
[49].Ines Houidi, Wajdi Louati, Walid Ben Ameur, Djamal Zeghlache, “Virtual network provisioning across multiple substrate networks, Telecom SudParis, 9 rue Charles Fourier, 91011 Evry, France
[50].Fady Samuel, Mosharaf Chowdhury and Raouf Boutaba, “PolyViNE: policy-based virtual network embedding across multiple domains Journal of Internet Services and Applications 2013
[51].Aris Leivadeas, Chrysa Papagianni, “Efficient Resource Mapping Framework over Networked Clouds via Iterated Local Search-Based Request Partitioning IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 24, NO. 6, JUNE 2013
[52].Y. Zhu and M. Ammar, “Algorithms for assigning substrate network resources to virtual network components, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proc.,2006, pp. 1–12.
[53].V. Abedifar and M. Eshghi, “A novel routing and wavelength as-signment in virtual network mapping based on the minimum path algorithm, in Ubiquitous and Future Networks (ICUFN), 2012 Fourth International Conference on, july 2012, pp. 204 –208.
[54].Y. Zhu and M. Ammar, “Algorithms for assigning substrate network resources to virtual network components, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proc.,2006
[55].X.L. Chang, X.M. Mi, J.K. Muppala, “Performance evaluation of artificial intelligence algorithms for virtual network embedding, Engineering Applications of Artificial Intelligence 26 (2013) 2540–2550
[56].X. Chen, Y. Luo, and J. Wang, “Virtual network embedding with border matching, in Communication Systems and Networks (COMSNETS), 2012 Fourth International Conference on, jan. 2012
[57].H. Yu, V. Anand, C. Qiao, H. Di, and X. Wei, “A cost efficient design of virtual infrastructures with joint node and link mapping, J. Network and Systems Management, vol. 20, pp. 97–115, 2012.
[58].Mixed Integer Problem http://en.wikipedia.org/wiki/Integer_programming
[59].Nadjib Aitsaadi, Guy Pujolle and Hubert Zimmermann, “VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic, IEEE Communications Society subject matter experts for publication in the IEEE ICC 2011 proceedings
[60].Xiang Chenga, Sen Sua,, Zhongbao Zhanga, Kai Shuanga, Fangchun Yanga, Yan Luo b, Jie Wang “Virtual network embedding through topology awareness and optimization Computer Networks 56 2012
[61].Sheng Zhang, Zhuzhong Qian, Song Guo, Sanglu Lu “FELL: A Flexible Virtual Network Embedding Algorithm with Guaranteed Load Balancing IEEE ICC 2011
[62].GLPK http://www.gnu.org/software/glpk/
[63].GPLEX http://gplex.codeplex.com/
[64].Relaxed Mixed Integer Program http://www.gams.com/mccarl/mccarlhtml/relaxed_mixed_integer_programming_(rmip).htm
[65].Donald B. Johnson, “A Note on Dijkstra's Shortest Path Algorithm, Journal of the ACM (JACM)
[66].N. M. Mosharaf Kabir Chowdhury, Muntasir Raihan Rahman, Raouf Boutaba, “Virtual Network Embedding with Coordinated Node and Link Mapping, IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings
[67].Multi-Commodity Flow http://en.wikipedia.org/wiki/Multi-commodity_flow_problem
[68].Baruch Awerbuch, Tom Leighton “Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, STOC '94 Proceedings of the twenty-sixth annual ACM symposium on Theory of computing
[69].TSP http://en.wikipedia.org/wiki/Travelling_salesman_problem
[70].Maximum Flow Minimum Cut http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
[71].Bhalgat, Hariharan, Kavitha, Panigrahi, “Gomory-Hu tree
[72].MAX-2-SAT http://en.wikipedia.org/wiki/2-satisfiability
[73].branch and bound algorithm http://see.stanford.edu/materials/lsocoee364b/17-bb_slides.pdf
[74].Xen http://www.xenproject.org/
[75].POX Controller http://www.noxrepo.org/pox/about-pox/
[76].OMNI client http://trac.gpolab.bbn.com/gcf/wiki/Omni
[77].OpenVswitch http://openvswitch.org/
[78].Pei-Wen Cheng, “Design and Implementation of a VLAN Tag-translated Mechanism on OpenFlow Networks
[79].VPN bridge http://www.softether.org/4-docs/1-manual/5._SoftEther_VPN_Bridge_Manual/5.3_Differences_between_VPN_Server_and_VPN_Bridge
[80].NetFPGA http://netfpga.org/
[81].EE Testbed@NCKU http://www.testbed.ee.ncku.edu.tw/