隨著虛擬化技術的普及以及虛擬交換器的技術越發成熟，未來的虛擬機器網路的規模將越來越大且趨於複雜。而隨著其規模的增長，這當中將衍生出許多新的問題，網路迴圈的問題將會是其中之一。在虛擬機器網路當中，網路迴圈一直不是一個重大的問題，但隨著虛擬機器網路的擴大，網路迴圈將隨處可見。一個網路迴圈就能造成很大的問題，更別說許多的迴圈將可能癱瘓整個網路。雖然在傳統網路中我們透過生成樹協議可以解決迴圈問題，但是現有的虛擬交換器因為設定的因素, 與生成樹協議分散式運算的特性並不相容。因此在本篇論文中，我們將提出一個新的方法來解決虛擬機器網路當中的迴圈問題。我們利用虛擬交換器的軟體特性來建構一個迴圈警報偵測系統，除此之外，我們也提出了一個演算法用以消除在我們系統中所發現的迴圈。

The virtualization technic has come of age and the virtual switch is getting fully developed. As the network scale getting so large and complex, some important issues should be discussed and solved for performance enhancement of cloud virtual machine networks. One of the important issues is the routing loop problem. In a small virtual machine network, the routing loop is not a problem. In a large cloud virtual machine the network, due to complicated configurations by different cloud managers, routing loops could easily appear. A single loop can cause a big problem, not to mention much of them might paralyze the network. The routing loop problem in a real network can be solved by Spanning Tree Protocol. However, the so far configuration-based virtual machine network fails to be capable to run the spanning tree protocol in an efficiently distributed way. In this paper, we came up with an idea to deal with the looping problem. We explore the characteristics and configurations of software-based virtual switches and propose a loop detection and notification system. Furthermore, we also design an efficient algorithm to eliminate the routing loop.

[1] Peter Mell and Timothy Grance, "The NIST Definition of Cloud Computing" , National Institute of Standards and Technology, Information Technology Laboratory, September 2011.
[2] Justin Pettit, Jesse Gross, Ben Pfaff, and Martin Casado, “Virtual Switching in an Era of Advanced Edges,” 2nd Workshop on Data Center-Converged and Virtual Ethernet Switching (DC-CAVES), ITC 22, September 2010.
[3] IEEE standard for Information Technology-MAC bridges. ANSI/IEEEStd 802.1D, 1998.
[4] IEEE standard for Local and Metropolitan Area Networks Media Access Control MAC bridges. IEEE Std 802.1D-2004, 2004.
[5] Cisco Technology Support, http://www.cisco.com/en/US/tech/tk389/tk621/tk846/tsd_technology_support_sub-protocol_home.html
[6] Srikant Sharma, Katrik Gopalan, Susanta Nanda and Tzi-cker Chiueh, “Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks,” INFOCOM 2004, March 2004.
[7] Joris Soeurt and Iwan Hoogendoorn, “Shortest Path Forwarding using OpenFlow.” University of Amsterdam, February 2012.
[8] Miao Tang, Qiaochu Lv, Zheng Lu, Qi Zhao and Yichuan Song, “Dynamic Virtual Switch Protocol Using Openflow”, 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, 2012.
[9] Open vSwitch Features, http://openvswitch.org/features/
[10] VMware Information Guide, http://www.vmware.com/files/pdf/virtual_networking_concepts.pdf
[11] Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt and Andrew Warfield, “Xen and the Art of Virtualization”, 2003.
[12] Bo-Lin Chen, “Experimental Factorial Design Analysis of Virtual Switch Performance in Cloud Computing”, A Thesis for the Master of Computer and Communication Engineering, National Cheng Kung University, 2013.
[13] Hui-Min Tseng, Hui-Lan Lee, Jen-Wei Hu, Te-Lung Liu, Jee-Gong Chang and Wei-Cheng Huang, “Network Virtualization with Cloud Virtual Switch”, IEEE 17th International Conference on Parallel and Distributed Systems (ICPADS), December, 2011.
[14] Open vSwitch Manual Page, http://openvswitch.org/ovs-vswitchd.conf.db.5.pdf
[15] Donald Johnson, “Finding all the Elementary Circuits of a directed graph.”, SIAM J. Comput, Vol.4, No.1, pp.77-84, 1975.
[16] James Tiernan, “An efficient search algorithm to find the elementary circuits of a graph.”, Comm. ACM, Vol.13, Issue.12, December. 1970.
[17] Robert Tarjan, “Enumeration of the elementary circuits of a directed graph.” , SIAM J. Comput, Vol.2, No.3, pp.211-216, 1973.
[18] Maytham Safar, Khalid Alenzi and Saud Albehairy, “Counting Cycles in an Undirected Graph using DFS-XOR Algorithm.”, Networked Digital Technologies, July 2009.
[19] Etienne Birmele, Rui Ferriera, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, Gustavo Scomoto, “Optimal Listing of Cycles and st-Paths in Undirected Graphs.”, In Proc. SODA’13, pp.1884-1896, 2013.
[20] D.S. Johnson, J.K. Lenstra, A.H.G. Rinnooy Kan, “The Complexity of the Network Design Problem”, Network 8, pp.279-285, 1978.