摘要
目前網路的路由方法是使用分散式的，路徑上的每一個router使用routing tables來儲存IP住址與port ID當作封包轉傳的依據，反之，軟體定義網路(Software Define Network, SDN)是使用集中式路由，SDN網路必須在Controller建立一個網路拓撲讓來源端的封包可以根據此網路拓撲找出一條最適當的路徑傳送到目的端，IEEE 802.1AB使用鏈結層尋找協定(Link Layer Discovery Protocol, LLDP)在Controller建立網路拓撲，此方法是將一個SDN網路分為多個群組讓Controller可以建立整個網路拓撲，但是Controller必須花較久的時間來整合全部群組所送回來的路徑資訊，而且採用群播式建立拓撲的方法無法找到終點端(end station)到終點端的最短路徑。因此本論文提出兩種建立網路拓撲的方法，第一種方法是採用Switch主動式並且透過Hello封包來獲得Switches彼此間互連的ports，第二種方法是採用Controller廣播式並且透過廣播式LLDP封包(Broadcasting LLDP Packet, BLP)來獲得路徑上所經過的switch ID與port ID。最後，我們使用程式模擬來分析Switch主動式與Controller廣播式的網路效能，包含拓撲建立時間與控制封包產生的數目，我們與群播式建立拓撲的方法做效能比較，從比較中我們證明本論文所提出的兩個方法確實可以減少網路拓撲建立的時間與控制封包的數目。
關鍵詞 : SDN、Controller、拓撲建立、廣播式、群播式

Abstract
Current Internet uses distributed routing to forward packets. Each router on the path builds a routing table to store the IP addresses and port IDs as the basis for packet forwarding. Conversely, Software Defined Network (SDN) uses centralized routing. In SDN networks, a network topology must be established on the Controller so that packets from the source can find the most appropriate path to its destination according to the network topology. IEEE 802.1AB uses Link Layer Discovery Protocol (LLDP) to create network topology on the Controller. This method divides an SDN network into multiple groups so that the Controller can build network topology, but the Controller has to take considerably long time to integrate all the path information sent back from all the multicasting groups. Another drawback is that the shortest path from one end station to another may not be found by using the multicasting method. Therefore, this thesis proposes two methods to establish network topology on the Controller. The first method uses the switch-activating method, which can obtain the port ID of any two interconnecting switches through Hello packets. The second method uses the controller-broadcasting method, which can obtain the switch ID and port ID on the path through broadcasting LLDP packets (referred to as BLP in the thesis). Finally, we use simulation to analyze the network performance for the two proposed methods. The performance metrics include the topology establishment time and the number of control packets generated. We compare the performance of two proposal methods with the conventional method using multicasting and demonstrate that the two proposed methods can significantly reduce the topology establishment time and the number of control packets generated.
Keywords: SDN, Controller, Topology Establishment, Broadcasting, Multicasting.

論文審定書 i
致謝 ii
摘要 iii
Abstract iv
第一章 導論 1
1.1研究動機 1
1.2研究方法 1
1.3章節介紹 2
第二章 建立SDN網路拓撲 3
2.1 目前網路的路由方法 3
2.2 SDN路由方法 5
2.2.1 SDN Switches與Controllers 6
2.2.1.1 SDN Switches 6
2.2.1.2 SDN Controllers 9
2.2.2 SDN拓樸的建立 11
2.2.2.1 LLDP封包的欄位 12
2.2.2.2使用群播建立網路拓撲 13
2.2.3 SDN路由的過程 15
2.3 相關研究與文獻的比較 17
第三章 使用Hello與BLP建立網路拓樸 20
3.1 Switch主動式與Controller廣播式 20
3.1.1 Switch主動式 21
3.1.1.1 Switch主動式的封包格式設計 22
3.1.1.2 Switch主動式的演算法流程 24
3.1.2 Controller廣播式 26
3.1.2.1 Controller廣播式的封包格式設計 27
3.1.2.2 Controller廣播式的演算法流程 28
3.2 階層式SDN網路的設計 32
3.2.1 CTP封包的設計 33
3.2.2 階層式Controller運作的流程 34
3.2.2.1傳送網路拓撲的流程 35
3.2.2.2重建網路拓樸的流程 37
第四章 建立SDN拓撲的效能分析 39
4.1 SDN網路拓撲的模擬環境 39
4.2 模擬所新增的虛擬碼 40
4.2.1建立隨機拓撲的虛擬碼 42
4.2.2 Switch主動式的虛擬碼 45
4.2.3 Controller廣播式的虛擬碼 50
4.2.4 階層式Controller的虛擬碼 58
4.3 模擬結果與分析 63
4.3.1 Hello與LLDP的封包數目比較 64
4.3.2 群播式與Switch主動式的建立時間比較 65
4.3.3 群播式與Controller廣播式的封包數目比較 67
4.3.4 群播式與Controller廣播式的建立時間比較 68
第五章 結論與未來工作 72
5.1 結論 72
5.2遭遇的困難 73
5.3未來工作 73
Reference 74
Acronyms 80
Index 82

Reference
[1] 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.
[2] D. Kreutz, F. M. V. Ramos, P. E. Veríssimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-Defined Networking: A Comprehensive Survey,” Proceedings of the IEEE, Vol: 103, Issue: 1, pp.14-76, Dec. 19, 2014.
[3] S. Khan, A. Gani, A. W. A. Wahab, M. Guizani, and M. K. Khan “Topology Discovery in Software Defined Networks: Threats, Taxonomy, and State-of-the-Art,” IEEE Communications Surveys & Tutorials, Vol: 19, Issue: 1, pp. 303-324, Aug. 05, 2016.
[4] F. M. Shuker, “Improvement of Routing Protocol for IoT Network Using SDN/OpenFlow,” 2019 1st AL-Noor International Conference for Science and Technology (NICST), Sulimanyiah, Iraq, pp. 1-4, Mar. 23, 2020.
[5] A. Kelkawi, A. Mohammed, and A. Alyatama, “Incremental Deployment of Hybrid IP/SDN Network with Optimized Traffic Engineering,” 2020 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), Leganes, Spain, pp. 1-7, Dec. 24, 2020.
[6] S. Islam, N. Muslim, and J. W. Atwood, “A Survey on Multicasting in Software-Defined Networking,” IEEE Communications Surveys & Tutorials, Vol: 20, Issue: 1, pp. 355-387, Nov. 21, 2017.
[7] H. Y. Ibrahim, P. M. Ismael, A. A. Albabawat, and A. B. Al-Khalil, “A Secure Mechanism to Prevent ARP Spoofing and ARP Broadcasting in SDN,” 2020 International Conference on Computer Science and Software Engineering (CSASE), Iraq, pp. 1-7, Jul. 16, 2020.
[8] K. Atefi, A. H. Shahin, S. Yahya, and A. Erfanian, “Performance Evaluation of RIP and EIGRP Routing Protocols in IEEE 802.3u standard,” 2016 3rd International Conference on Computer and Information Sciences (ICCOINS), Kuala Lumpur, Malaysia, pp. 1-6, Dec. 15,2016.
[9] M. Jayakumar; N. R. S. Rekha, and B. Bharathi, “A comparative study on RIP and OSPF protocols,” 2015 International Conference on Innovations in Information, Embedded and Communication Systems (ICIIECS), Coimbatore, India, pp. 1-5, Mar. 19-20, 2015.
[10] A. Nygren, B. Pfaff, B. Lantz, B. Heller, and C. Barker, “OpenFlow Switch Specification,” Open Network Foundation TS-025, Ver 1.5.1, pp. 249, Mar. 26, 2015.
[11] D. Hasan and M. Othman, “Efficient Topology Discovery in Software Defined Networks Revisited,” 2nd International Conference on Computer Science and Computational Intelligence 2017 (ICCSCI 2017), Bali, Indonesia, pp. 1-9, Oct. 13-14, 2017.
[12] K. Qiu, J. Yuan, J. Zhao, X. Wang, S. Secci, and X. Fu, “FastRule: Efficient Flow Entry Updates for TCAM-Based OpenFlow Switches,” IEEE Journal on Selected Areas in Communications, Vol: 37, Issue: 3, pp. 484-498, Jan. 23, 2019.
[13] 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. 01, 2019.
[14] S. H. Yeganeh, A. Tootoonchian, and Y. Ganjali, “On Scalability of Software-Defined Networking,” IEEE Communications Magazine, pp. 136-141, Feb. 14, 2013.
[15] B. Nunes, M. Mendonca, and X. Nguyen, “A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks,” IEEE Communications Surveys & Tutorials, pp. 1617-1634, Feb. 13, 2014.
[16] R. Wazirali, R. Ahmad, and S. Alhiyari, “SDN-OpenFlow Topology Discovery: An Overview of Performance Issues,” Multidisciplinary Digital Publishing Institute (MDPI), pp. 1-30, Jul. 29, 2021.
[17] J. Kipongo, T. O. Olwal, and A. M. Abu-Mahfouz, “Topology Discovery Protocol for Software Defined: Wireless Sensor Network: Solutions and Open Issues,” 2018 IEEE 27th International Symposium on Industrial Electronics (ISIE), Cairns, QLD, Australia, pp. 1-6, Aug. 13, 2018.
[18] J. Alvarez-Horcajo, E. Rojas, I. Martinez-Yelmo, M. Savi, and D. Lopez-Pajares, “HDDP: Hybrid Domain Discovery Protocol for Heterogeneous Devices in SDN,” IEEE Communications Letters, Vol. 24, Issue: 8, pp. 1655-1659, Apr. 29, 2020.
[19] A. K. Saha, K. Sambyo, and C.T. Bhunia, “Topology Discovery, Loop Finding and Alternative Path Solution in POX Controller,” International Multi Conference of Engineers and Computer Scientists (IMECS), Hong Kong, pp. 1-5, Mar. 16, 2016.
[20] F. Hauser, M. Schmidt, M. Häberle, and M. Menth “P4-MACsec: Dynamic Topology Monitoring and Data Layer Protection With MACsec in P4-Based SDN,” IEEE Access, Vol: 8, pp. 58845-58858, Mar. 23, 2020.
[21] G. Parsons, J. Messenger, and T. Jeffree, “IEEE Standard for Local and metropolitan area networks— Station and Media Access Control Connectivity Discovery,” IEEE Std 802.1AB-2016, pp. 19-29, Jan. 29, 2016.
[22] T. Humernbrum, B. Hagedorn, and S. Gorlatch, “Towards Efficient Multicast Communication in Software-Defined Networks,” 2016 IEEE 36th International Conference on Distributed Computing Systems Workshops (ICDCSW), Nara, Japan, pp. 1-8, Nov. 24, 2016.
[23] L. Mamushiane1, J. Mwangama1, and A. A. Lysko, “Given a SDN Topology, How Many Controllers are Needed and Where Should They Go,” 2018 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), Verona, Italy, pp. 1-6, Nov. 27-29, 2018.
[24] Z. Jia, Y. Sun, Q. Liu, S. Dai, and C. Liu, “cRetor: An SDN-Based Routing Scheme for Data Centers With Regular Topologies,” IEEE Access, Vol. 8, pp. 1-7, Jun. 24, 2020.
[25] A. Azzouni1, R. Boutaba, N. T. M. Trang, and G. Pujolle, “sOFTDP: Secure and Efficient OpenFlow Topology Discovery Protocol,” NOMS 2018-2018 IEEE/IFIP Network Operations and Management Symposium, Taipei, Taiwan, Apr. 23-27, 2018.
[26] Y. Jia, L. Xu, Y. Yang, and X. Zhang, “Lightweight Automatic Discovery Protocol for OpenFlow-Based Software Defined Networking,” IEEE Communications Letters, Vol. 24, No. 2, pp. 312-315, Feb. 2020.
[27] Y. Chang, H. Lin, H. Chu, and P. Wang, “Efficient Topology Discovery for Software-Defined Networks,” IEEE Transactions on Network and Service Management, Vol. 18, No. 2, pp. 1375-1388, Jun. 2021.
[28] L. Ochoa-Aday, C. Cervelló-Pastor, and A. Fernández-Fernández, “eTDP: Enhanced Topology Discovery Protocol for Software-Defined Networks,” IEEE Access, Vol. 7, pp. 1-17, Feb. 15, 2019.
[29] G. Tarnaras, E. Haleplidis, and S. Denazis, “SDN and ForCES Based Optimal Network Topology Discovery,” Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft), London, UK, pp. 1-6, Apr. 13-17, 2015.
[30] E. Rojas, J. Alvarez-Horcajo, I. Martinez-Yelmo, J. A. Carral, and J. M. Arco “TEDP: An enhanced topology discovery service for Software-Defined Networking,” IEEE Communications Letters, Vol. 22, No. 8, pp. 1-5, June 08, 2018.
[31] J. S. Choi and X. Li “Hierarchical Distributed Topology Discovery Protocol for Multi-Domain SDN Networks,” IEEE Communications Letters, Vol. 21, Issue: 4, pp. 773 – 776, Dec. 08, 2017.
[32] M. W. Hussain, K. H. K. Reddy, J. J. P. C. Rodrigues, and D. S. Roy, “An Indirect Controller-Legacy Switch Forwarding Scheme for Link Discovery in Hybrid SDN,” IEEE Systems Journal, Vol. 15, Issue: 2, pp. 3142-3149, Aug. 10, 2020.
[33] Y. Tsukuda, M. Kosugi, K. Shiomoto, T. Morita, and T. Hayashi, “Reducing Inconsistency between Software-Defined Networking Controllers,” 2019 IEEE Conference on Network Softwarization (NetSoft), Paris, France, pp. 1-5, Jun. 24-28, 2019.
[34] S. K. Nivetha, N. Senthilkumaran, P. Suguna, and T. Vanaja, “On Optimal Topology Verification and Failure Localization for Software Defined Networks,” 2021 International Conference on Computer Communication and Informatics (ICCCI), Coimbatore, India, pp. 1-4, Jan. 27-29, 2021.
[35] J. Flathagen and O. I. Bentstuen, “Proxy-based Optimization of Topology Discovery in Software Defined Networks,” 2019 International Conference on Military Communications and Information Systems (ICMCIS), Budva, Montenegro, pp. 1-5, May 14-15, 2019.
[36] Y. Zhao, X. Chen, and F. Yang, “Automatic Topology Discovery and Control Paths Establishment in Transport SDN,” 2014 Asia Communications and Photonics Conference (ACP), Shanghai, China, pp. 1-3, Nov. 11-14, 2014.