臺灣博碩士論文加值系統

在軟體定義網路中，為了因應日益增加的網路規模以及多樣化的應用，多控制器架構應運而生。而控制器的超載處理以及控制器之間的負載平衡是此架構需要面對的重要議題。在眾多使用交換器轉移的負載平衡演算法中，有些方法會利用交換器分群降低轉移成本，其中較著名的演算法為BalCon。此方法藉由分析交換器與交換器群體之間的流量找出連接較緊密的群體，以此做出最有效的轉移決策。

本篇論文改進現今交換器分群方法的缺陷，我們提出一個更快速而且更能適應拓樸環境的交換器群體找尋方法在控制器負載平衡演算上。針對交換器上的流程進行分類並賦予不同的流程模式權重，使其在不同拓樸環境下的負載平衡效果能夠有最好的表現。由於我們只針對要加入群體的候選交換器進行流量分析，無須對群體內部交換器之間做額外運算，因此整體演算法執行時間有顯著下降。本篇論文使用Matlab進行模擬，透過模擬實驗結果得知，在Fat-tree拓樸環境中，經過我們提出的交換器群體找尋方法改善後的負載平衡演算法，比原分群方法的不平衡百分比少1.48%。除此之外，在相同環境下的演算法執行時間也比原方法少30%。

To deal with the increasing scalar of network and various applications on Software Defined Network(SDN), the multi-controller architecture was born. Handling with overloaded controller and load balancing between controllers is the most important issue that is concerned by this architecture. Among of the algorithms that are used on Switch Migration to implement controller load balancing, one of the methods is known as BalCon which decreases the migration cost by using Switch Grouping. By analyzing the flow rate between the SDN switches and the Cluster, the method collects the switches with strong connections to make the most effective decision of migration.
The disadvantage of Switch Grouping is the subject we have studied and improved in this paper. We propose a Switch Clusters finding method that is faster and more adaptive to many kinds of topologies. We specifically classify every flow on the switches and give weights on different flow patterns in order to have the best effect of the load balancing in various topologies. Without having computation between switches in the Cluster, we only aim at the candidate switches which are going to join the Cluster and analysis the flow patterns. Therefore, we decrease the whole computation time of the algorithm. In this paper, we implement the simulation with Matlab. The results show that the Percent Imbalance Matric of the load balancing algorithm improved by our proposed method is 1.48% less than the original method of Switch Grouping in fat-tree topology environment. In addition, the computation time of the algorithm is 30% less than the original one.

摘要 i
Abstract ii
目錄 iii
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1 研究背景介紹 1
1.2 研究動機與目的 3
1.3 論文架構 4
第二章 問題與文獻探討 5
2.1 多控制器負載平衡議題 5
2.2 多控制器上的負載平衡演算法探討 6
2.2.1 負載平衡方法 6
2.2.2 方法優缺點分析 7
2.2.3 交換器分群的缺陷 8
第三章 我們提出的控制器負載平衡演算法 11
3.1 系統模型 11
3.1.1 系統模型介紹 11
3.1.2 流程呈現 12
3.1.3 參數定義 13
3.2 負載平衡演算法 13
3.3 交換器群體找尋方法 15
3.3.1 流程模式的分類 16
3.3.2 選擇公式 18
3.3.3 權重調整 19
第四章 模擬結果與分析 21
4.1 評估指標及參數說明 21
4.1.1 效能評估指標 21
4.1.2 環境與參數設定說明 22
4.2 模擬結果分析與討論 23
4.2.1 公式權重分析 23
4.2.2 不同拓樸的效能比較 27
第五章 結論 32
參考文獻 33

[1]D. Kreutz, F. M. Ramos, P. Esteves Verissimo, C. Esteve Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-defined networking: A comprehensive survey,” Proceedings of the IEEE, vol. 103, no. 1, 2015, pp. 14–76.
[2]B. A. A. Nunes, M. Mendonca, X. N. Nguyen, K. Obraczka and T. Turletti, "A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks," in IEEE Communications Surveys & Tutorials, vol. 16, no. 3, Third Quarter 2014, pp. 1617-1634.
[3]J. H. Ahrens, U. Dieter, “Computer Generation of Poisson Deviates from Modified Normal Distributions,” in ACM Transactions on Mathematical Software (TOMS), New York, NY, USA , June 1982, pp. 163-179.
[4]Grid Network, [online] Available: https://en.wikipedia.org/wiki/Grid_network, Accessed on: July. 1, 2017.
[5]C. E. Leiserson, "Fat-trees: Universal networks for hardware-efficient supercomputing," in IEEE Transactions on Computers, vol. C-34, no. 10, Oct. 1985, pp. 892-901.
[6]OpenFlow Switch Specification, [online]. Available: https://www.opennetworking.org/technical-communities/areas/specification/2323-open-datapath, Accessed on: July. 1, 2017.
[7]L. Richardson and S. Ruby, “RESTful Web Services,” Sebastopol, CA, USA: O’Reilly Media, 2008.
[8]A. Tootoonchian, Y. Ganjali, "HyperFlow: A distributed control plane for OpenFlow", Proc. Internet Netw. Manage. Conf. Res. Enterprise Netw., 2010, p. 3.
[9]P. Berde et al., "ONOS: Towards an open distributed SDN OS," Proc. 3rd Workshop Hot Topics Softw. Defined Netw., 2014, pp. 1-6.
[10]F. Botelho, A. Bessani, F. M. V. Ramos and P. Ferreira, "On the Design of Practical Fault-Tolerant SDN Controllers," 2014 Third European Workshop on Software Defined Networks, Budapest, 2014, pp. 73-78.
[11]S. Jain et al., "B4: Experience with a globally-deployed software defined WAN" Proc. ACM SIGCOMM Conf., pp. 3-14, 2013.
[12]M. Cello, Y. Xu, A. Walid, G. Wilfong, H. J. Chao and M. Marchese, "BalCon: A Distributed Elastic SDN Control via Efficient Switch Migration," 2017 IEEE International Conference on Cloud Engineering (IC2E), Vancouver, BC, 2017, pp. 40-50.

[13]A. Dixit, F. Hao, S. Mukherjee, T. V. Lakshman, and R. R. Kompella, "Towards an elastic distributed sdn controller," in Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN ’13, New York, NY, USA, 2013, ACM, pp. 7–12.
[14]A. Dixit, F. Hao, S. Mukherjee, T. V. Lakshman and R. R. Kompella, "ElastiCon; an elastic distributed SDN controller," 2014 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), Marina del Rey, CA, 2014, pp. 17-27.
[15]Y. Chen, Q. Li, Y. Yang, Q. Li, Y. Jiang and X. Xiao, "Towards adaptive elastic distributed Software Defined Networking," 2015 IEEE 34th International Performance Computing and Communications Conference (IPCCC), Nanjing, 2015, pp. 1-8.
[16]C. Liang, R. Kawashima and H. Matsuo, "Scalable and Crash-Tolerant Load Balancing Based on Switch Migration for Multiple Open Flow Controllers," 2014 Second International Symposium on Computing and Networking, Shizuoka, 2014, pp. 171-177.
[17]S. H. Yeganeh, A. Tootoonchian and Y. Ganjali, "On scalability of software-defined networking," in IEEE Communications Magazine, vol. 51, no. 2, February 2013, pp. 136-141.
[18]T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data centers in the wild,” In Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, IMC ’10, New York, NY, USA, 2010, pp. 267–280.
[19]G. Yao, J. Bi, Y. Li and L. Guo, "On the Capacitated Controller Placement Problem in Software Defined Networks," in IEEE Communications Letters, vol. 18, no. 8, Aug. 2014 , pp. 1339-1342.
[20]A. Tootoonchian, S. Gorbunov, Y. Ganjali, M. Casado, and R. Sherwood, "On controller performance in software-defined networks," in Proc. 2nd USENIX Conf. Hot Topics Manage. Internet Cloud Enterprise Netw. Services, 2012, p. 10.
[21]O. Pearce, T. Gamblin, B. R. de Supinski , M. Schulz , N. M. Amato, “Quantifying the effectiveness of load balance algorithms,” in Proceedings of the 26th ACM international conference on Supercomputing, San Servolo Island, Venice, Italy, 2012, pp. 185-194.