軟體定義網路(Software Defined Network, SDN)是一種集中式路由，需要建立一個控制器(Controller)來維護網路拓樸，其目的是讓控制器可以找到一條最適當的路徑讓來源端傳送資料封包到目的地。目前的控制器是使用最少跳躍數 (minimum number of hop counts)路徑的方式來傳送資料封包，此方法的最大缺點是很多來源端可能會選擇同一條路徑到其目的地，其結果會造成資料封包在交換器(Switch)大量遺失。因此本論文提出一個路徑選擇演算法(Route Selection Algorithm, RSA)，每台交換器會傳送其負載率(load ratio)給控制器且會週期性地更新此負載率。當來源端的第一個資料封包進入交換機時，交換機會比對自己的flow table，若flow table內沒有到目的地的路徑時，交換機會傳送這個資料封包給控制器，控制器會根據此資料封包的目的地IP從拓樸中找到所有可以從來源端到達目的地的路徑。控制器為了要選擇一條最適當的路徑會計算每一條可能路徑上所有交換機的負載率並計算每一條可能路徑的平均負載，若有多條路徑的平均負載均小於一個預設的門檻值時，控制器會再計算符合平均負載小於門檻值的剩餘路徑的終點端到終點端的延遲(end-to-end delay)並找出延遲最小的路徑，若負載大於門檻值時，控制器會刪除此條路徑，若不只一條路徑的延遲最小時，控制器會再計算符合最小延遲的剩餘路徑的跳躍數(hop counts)，最後控制器會選擇跳躍數最少的路徑讓來源端傳送資料封包到目的地，最後我們使用程式來模擬並分析使用本論文提出的RSA與目前控制器使用的最短路徑選擇法的網路效能，這些網路效能包含交換機的負載率、封包遺失率(packet loss rate)與產出(throughput)。

Software Defined Networks (SDN) adopt a centralized routing method. It needs to establish a Controller to maintain the network topology. The purpose is to enable the Controller to find the most appropriate path for the source to transmit data packets to its destination. Current Controller uses the shortest path (the minimum number of hops) to transmit data packets. The biggest disadvantage of this method is that all the sources may choose the same path to their destination, which may cause serious packet loss in the switches on the path. Therefore, in this thesis we propose a Route Selection Algorithm (RSA) to remedy the problem. Each switch will transmit its load ratio to the Controller and updates the load ratio periodically. When the first data packet from the source enters a switch, the switch will find a path from its flow table. If a path cannot be found from the flow table, the Switch will forward the packet to the Controller. The Controller then identifies all the possible paths from the source to the destination according to the destination’s IP. To select the most appropriate path, the Controller calculates the average load ratio of each possible path. If the average load ratio of multiple paths is less than a default threshold, the Controller will select the smallest end-to-end delay of the remaining paths. If more than one path has minimal delay, the Controller selects the minimum hop counts of the remaining paths. Finally, we write a program to simulate and analyze the performance of the proposed RSA and compare with the shortest-path method currently used. Performance metrics include switch load ratio, packet loss rate, and the overall system throughput.

論文審定書 i
致謝 ii
摘要 iii
Abstract iv
第一章 導論 1
1.1 研究動機 1
1.2 研究方法 1
1.3 論文架構 2
第二章 SDN的網路路由差異 3
2.1 軟體定義網路 3
2.2 IP路由 4
2.2.1 分散式路由 5
2.2.2 集中式路由 6
2.2.2.1 單一控制器 7
2.2.2.2 多重控制器 8
2.3 終點端到終點端的延遲 9
2.4 相關研究 10
第三章 SDN的路徑選擇機制 13
3.1 路徑選擇機制 13
3.1.1 交換機上負載率計算的流程 14
3.1.2 控制器上的路徑選擇演算法 18
第四章 模擬與結果 23
4.1 SDN的路徑選擇 23
4.2 結果與分析 25
第五章 結論與未來工作 28
5.1 結論 28
5.2 未來工作 28
Reference 29
Acronyms 33
Index 34

[1] Z. Li, L. Ji, R. Huang, and S. Liu, “Improving Centralized Path Calculation Based on Graph Compression,” China Communications, Vol. 15, No. 6, pp. 120-124, Jun. 2018.
[2] M. Markowski, P. Ryba, and K. Puchała, “Software Defined Networking Research Laboratory-Experimental Topologies and Scenarios,” Third European Network Intelligence Conference (ENIC), Wroclaw, Poland, pp. 1-5, Sep. 5-7, 2016.
[3] M. Alsaeedi, M. M. Mohamad, and A. A. Al-Roubaiey, “Toward Adaptive and Scalable OpenFlow-SDN Flow Control: A Survey,” IEEE Access, Vol. 7, pp. 107346-107379, Aug. 2019.
[4] A. Nygren, B. Pfaf, B. Lantz, and B. Heller, “OpenFlow Switch Specification,” ONF TS-025, Ver. 1.5.1, Mar. 26, 2015.
[5] A. Lara, A. Kolasani, and B. Ramamurthy, “Network Innovation using OpenFlow: A Survey,” IEEE Communications Surveys & Tutorials, Vol. 16, No. 1, pp. 493-512, Aug. 2013.
[6] J. Xie, F. R. Yu, T. Huang, R. Xie, J. Liu, C. Wang, and Y. Liu, “A Survey of Machine Learning Techniques Applied to Software Defined Networking (SDN): Research Issues and Challenges,” IEEE Communications Surveys & Tutorials, Vol. 21, No. 1, pp. 393-430, Aug. 2018.
[7] S. Baik, Y. Lim, J. Kim, and Y. Lee, “Adaptive Flow Monitoring in SDN Architecture,” 17th Asia-Pacific Network Operations and Management Symposium (APNOMS), Busan, Korea, pp. 1-3, Aug. 19-21, 2015.
[8] X. N. Nguyen, D. Saucez, C. Barakat, and T. Turletti, “Rules Placement Problem in OpenFlow Networks: A Survey,” IEEE Communications Surveys & Tutorials, Vol. 18, No. 2, pp. 1273-1286, Dec. 2015.
[9] C. S. Khin, M. Z. Oo, and A. T. Kyaw, “Packet-in Messages Handling Scheme to Reduce Controller Bottlenecks in OpenFlow Networks,” 17th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications, and Information Technology (ECTI-CON), Phuket, Thailand, pp. 1-4, Jun. 24-27, 2020.
[10] A. Zacharis, S. V Margariti, E. Stergiou, and C. Angelis, “Performance Evaluation of Topology Discovery Protocols in Software Defined Networks,” IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), Heraklion, Greece, pp. 1-6, Nov. 09-11, 2021.
[11] H. Xin, “Introduction of Centralized and Distributed Routing Protocols,” International Conference on Electronics, Communications and Control (ICECC), Ningbo, China, pp. 1-4, Sep. 9-11, 2011.
[12] E. Rotenberg, C. Crespelle and M. Latapy, “Measuring Routing Tables in The Internet,” IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Toronto, Canada, pp. 1-6, Jul. 08, 2014.
[13] J. Bian and S.P. Khatri, “IP Routing Table Compression using ESPRESSO-MV,” The 11th IEEE International Conference on Networks, Sydney, Australia, pp. 1-6, Oct. 2003.
[14] C.L. Hedrick, “Routing Information Protocol,” RFC 1058, Jun. 1988.
[15] J. Postel, “Introduction to the STD Notes,” RFC 1311, Mar. 1992.
[16] Kaveh Pahlavan and Prashant Krishnamurthy, “802.3-2018 - IEEE Standard for Ethernet,” IEEE, pp. 119, Aug. 31, 2018.
[17] A. Almohaimeed and A. Asaduzzaman, “Dedicated Backup Units to Alleviate Overload on SDN Controllers,” 2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC), Las Vegas, USA, pp. 1-6, Jun. 7-9, 2019.
[18] A. V. Atli, M. S. Uluderya, S. Tatlicioglu, B. Gorkemli, and A. M. Balci, “Protecting SDN Controller with Per-Flow Buffering Inside OpenFlow Switches,” IEEE International Black Sea Conference on Communications and Networking, Istanbul, Turkey, pp. 1-5, Jun. 5-8, 2018.
[19] D. Kreutz, F. M. V. Ramos, P. E. Veríssimo, C. E. Rothenberg, S. Azodolmolky, and S, Uhlig, “Software-Defined Networking: A Comprehensive Survey,” IEEE, Vol. 103, No. 1, pp. 14-76, Dec. 19, 2014.
[20] P. D. Bhole and D. D. Puri, “Distributed Hierarchical Control Plane of Software Defined Networking,” International Conference on Computational Intelligence and Communication Networks (CICN), Jabalpur, India, pp. 1-7, Dec. 12-14, 2015.
[21] S. Karnani and H. K. Shakya, “Leveraging SDN for Load Balancing on Campus Network (CN),” 13th International Conference on Computational Intelligence and Communication Networks (CICN), Lima, Peru, pp. 1-5, Sep. 22-23, 2021.
[22] F. P. C. Lin and Z. Tsai, “Hierarchical Edge-Cloud SDN Controller System with Optimal Adaptive Resource Allocation for Load-Balancing,” IEEE Systems Journal, Vol. 14, No. 1, pp. 265-276, Feb. 12, 2019.
[23] H. Wang, X. Cai, Y. Guo, S. Zhang, and J. Zhao, “Multipath Routing Algorithm in SDN-based Power Communication Network,” IEEE 5th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), Xi’an, China, pp. 1-5, Oct. 15-17, 2021.
[24] C. Singhal and K. Rahul, “LB-UAVnet: Load Balancing Algorithm for UAV Based Network Using SDN,” 2019 22nd International Symposium on Wireless Personal Multimedia Communications (WPMC), Lisbon, Portugal, pp. 1-5, Nov 24-27, 2019.
 
[25] Y. Wang, R. Liu, Y. Li, Z. Chen, N. Zhang, and B. Han, “SDN Controller Network Load Balancing Approach for Cloud Computing Data Center,” 2022 14th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), Changsha, China, pp. 1-5, Jan. 15-16, 2022.
[26] S. Zhu, Z. Sun, Y. Lu, L. Zhang, Y. Wei, and G. Min, “Centralized QoS Routing Using Network Calculus for SDN-Based Streaming Media Networks,” IEEE Access, Vol. 7, pp. 146566-146576, Sep. 24, 2019.
[27] D. Todorov, H. Valchanov, and V. Aleksieva, “Load Balancing model based on Machine Learning and Segment Routing in SDN,” 2020 International Conference Automatics and Informatics (ICAI), Varna, Bulgaria, pp. 1-4, Oct. 1-3, 2020.
[28] M. Chen, M. Xiang, C. Huang, and H. Mao, “Dynamic Load Balancing Strategy Based on Link Preference in SDN,” 2021 7th International Conference on Computer and Communications (ICCC), Chengdu, China, pp. 1-5, Dec. 10-13, 2021.