近年來，由於雲端應用服務及巨量資料需求日益增加，造成網際網路越來越複雜且難以管理，軟體定義網路（Software Defined Networks，SDN）架構成為了虛擬化與智能控制的新趨勢，其特色是修改了傳統網路架構的控制模式，將網路分為控制層（Control Plane）與傳輸層（Data Plane），網路的管理權限交由控制層的控制器（Controller）軟體負責，採用集中控管的方式，藉由統一下達指令給網路設備來達到容易管理的目的。事實上，這樣的架構意味著傳輸層的網路設備不再具備自主性，在面臨線路中斷或路由器故障時並無法自行解決，而是需要大量時間來等候遠端控制器進行計算並下達新的指令，因此SDN在面對修復時效性問題時多仰賴快速故障轉移（Fast Failover）機制，預先將備用路徑載入到網路設備中來達到保護及快速修復的作用。然而這樣的作法下，網路設備的記憶體資源將被過度消耗，進而衍生出競爭記憶體資源的現象，對整體網路造成延遲及Controller負擔等問題。基於此，本研究提出一套分段保護機制，在快速故障轉移機制下節約網路設備的記憶體消耗，並針對不同類型的網路故障提供可行的傳輸修復方法。最後透過模擬結果證明本機制不僅可以降低網路設備在備用指令上的額外記憶體消耗，同時也可以確保修復的穩健度與時效性。

Due to the increasing demand for cloud application services and big data, the Internet has become increasingly complex and difficult to manage in recent years. In addition, Software Defined Network (SDN) architectures have become increasingly prevalent. In contrast to traditional networks, in which the control plane and data plane are embedded in the same device, SDN architectures implement the control plane on a centralized controller and the data plane on the SDN switches. This centralized control architecture allows for an easy management of the SDN network by configuring the flow entries on the data plane of the SDN switches. However, the data planes of the switches are no longer autonomous. Hence, in the event of link or node failures, the impacted switches cannot solve the problem on their own, but need to wait to receive instructions from the remote controller. To resolve the resulting latency problem, various fast failover mechanisms based on installing the flow entries on the SDN switches with precomputed multiple-path information have been proposed. However, these approaches typically create a large number of rarely-utilized flow entries, and hence incur a problem similar to thrashing, thereby causing delays and an additional controller overhead. Accordingly, this thesis proposes a segmented rerouting scheme that provides a feasible protection method for both node failures and link failures while simultaneously minimizing the Ternary Content Addressable Memory (TCAM) consumption. The simulation results show that the proposed scheme not only ensures the robustness and timeliness of the failure recovery process, but also minimizes the TCAM consumption in the SDN switches.

[1] D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao, “Overview and Principles of Internet Traffic Engineering”, RFC 3272, May 2002.
[2] J. Menuka and P. Maria, “The IMS 2.0 Service Architecture”, The Second International Conference on Next Generation Mobile Applications, Services, and Technologies, pp. 3-9, 2008.
[3] S. Hassas, A. Tootoonchian, and Y. Ganjali, “On scalability of software-defined networking”, IEEE Communications Magazine, vol. 51, no. 2, pp. 136-141, February 2013.
[4] B. Nunes, M. Mendonca, X. Nguyen, K. Obraczka, and T. Turletti, “A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks”, IEEE Communications Surveys & Tutorials, vol. 16, no. 3, pp. 1617-1634, 2014.
[5] Wenfeng Xia, Yonggang Wen, Chuan Heng Foh, Dusit Niyato, and Haiyong Xie, “A Survey on Software-Defined Networking”, IEEE Communications Surveys & Tutorials, vol. 17, no. 1, pp. 27-51, 2015.
[6] Diego Kreutz, Fernando M. V. Ramos, Paulo Esteves Veríssimo, Christian Esteve Rothenberg, Siamak Azodolmolky, and Steve Uhlig, “Software-Defined Networking: A Comprehensive Survey”, Proceedings of the IEEE, vol. 103, no. 1, pp. 14-76, January 2015.
[7] Safae Zerrik, Amina El ouadghiri, Driss El ouadghiri, Rachid Atay, Mohamed Bakhouya, and Jaafar Gaber, “Towards a decentralized and adaptive software-defined networking architecture”, International Conference on Next Generation Networks and Services (NGNS), pp. 326-329, May 2014.
[8] Nick Feamster, Jennifer Rexford, and Ellen Zegura, “The Road to SDN: An Intellectual History of Programmable Networks”, ACM SIGCOMM Computer Communication Review, vol. 44, no. 2, pp. 87-98, April 2014.
[9] Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peterson, Jennifer Rexford, Scott Shenker, and Jonathan Turner, “OpenFlow: Enabling Innovation in Campus Networks”, ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69-74, March 2008.
[10] Open Networking Foundation, “OpenFlow Switch Specification version 1.5.0”, December 19, 2014.
[11] Open Networking Foundation, “OpenFlow Table Type Patterns version no. 1.0”, August 15, 2014.
[12] Open Networking Foundation, “Simplifying OpenFlow Interoperability with Table Type Patterns (TTP)”, May 7, 2015.
[13] D. S. Vijayasarathi, M. Nourani, M. J. Akhbarizadeh, and P. T. Balsara, “Ripple-precharge TCAM: a low-power solution for network search engines”, International Conference on Computer Design, pp. 243-248, 2005.
[14] Hsiang-Jen Tsai, Keng-Hao Yang, Yin-Chi Peng, Chien-Chen Lin, Ya-Han Tsao, Meng-Fan Chang, and Tien-Fu Chen, “Energy-Efficient TCAM Search Engine Design Using Priority-Decision in Memory Technology”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 3, pp. 962-973, March 2017.
[15] Sachin Sharma, Dimitri Staessens, Didier Colle, Mario Pickavet, and Piet Demeester, “Enabling fast failure recovery in OpenFlow networks”, 8th International Workshop on the Design of Reliable Communication Networks (DRCN), pp. 164-171, 2011.
[16] Dimitri Staessens, Sachin Sharma, Didier Colle, Mario Pickavet, and Piet Demeester, “Software defined networking: Meeting carrier grade requirements”, 18th IEEE Workshop on Local & Metropolitan Area Networks (LANMAN), pp. 1-6, 2011.
[17] Sachin Sharma, Dimitri Staessens, Didier Colle, Mario Pickavet, and Piet Demeester, “OpenFlow: Meeting Carrier-Grade Requirements”, Computer Communications, vol. 36, no. 6, pp. 656-665, March 2013.
[18] Andrea Sgambelluri, Alessio Giorgetti, Filippo Cugini, Francesco Paolucci, and Piero Castoldi, “OpenFlow-based segment protection in Ethernet networks”, Journal of Optical Communications and Networking, vol. 5, no. 9, pp. 1066-1075, September 2013.
[19] Niels L. M. van Adrichem, Benjamin J. van Asten, and Fernando A. Kuipers, “Fast Recovery in Software-Defined Networks”, Third European Workshop on Software Defined Networks, pp. 61-66, 2014.

[20] D. Katz and D. Ward, “Bidirectional Forwarding Detection (BFD)”, RFC 5880 (Proposed Standard), Internet Engineering Task Force (IETF), June 2010.
[21] Dimitrios Katsaros, Nikos Dimokas, and Leandros Tassiulas, “Social network analysis concepts in the design of wireless Ad Hoc network protocols”, IEEE Network, vol. 24, no. 6, pp. 23-29, November 2010.
[22] Antonio Capone, Carmelo Cascone, Alessandro Q. T. Nguyen, and Brunilde Sansò, “Detour planning for fast and reliable failure recovery in SDN with OpenState”, 11th International Conference on the Design of Reliable Communication Networks (DRCN), pp. 25-32, 2015.
[23] Carmelo Cascone, Luca Pollini, Davide Sanvito, Antonio Capone, and Brunilde Sansò, “SPIDER: Fault resilient SDN pipeline with recovery delay guarantees”, NetSoft Conference and Workshops (NetSoft), pp. 296-302, 2016
[24] Purnima Murali Mohan, Tram Truong-Huu, and Mohan Gurusamy, “TCAM-Aware Local Rerouting for Fast and Efficient Failure Recovery in Software Defined Networks”, Global Communications Conference (GLOBECOM), pp. 1-6, 2015.
[25] Yury Jimenez, Juan Antonio Cordero, and Cristina Cervelló-Pastor, “Measuring robustness of SDN control layers”, IFIP/IEEE International Symposium on Integrated Network Management (IM), pp. 774-777, 2015.
[26] Neda Beheshti and Ying Zhang, “Fast failover for control traffic in Software-defined Networks”, Global Communications Conference (GLOBECOM), pp. 2665-2670, 2012.
[27] Siddharth S. Kulkarni and Venkataramana Badarla, “On multipath routing algorithm for software defined networks”, IEEE International Conference on Advanced Networks and Telecommuncations Systems (ANTS), pp. 1-6, 2014.
[28] Yi-Chen Chan, Kuochen Wang, and Yi-Huai Hsu, “Fast Controller Failover for Multi-domain Software-Defined Networks”, European Conference on Networks and Communications (EuCNC), pp. 370-374, 2015.
[29] M. Rifai, N. Huin, C. Caillouet, F. Giroire, D. Lopez-Pacheco, J. Moulierac, and G. Urvoy-Keller, “Too Many SDN Rules? Compress Them with MINNIE”, Global Communications Conference (GLOBECOM), pp. 1-7, 2015.
[30] Greedy algorithm Wikipedia. [Online]. Available : https://en.wikipedia.org/wiki/Greedy_algorithm
[31] Dijkstra’s algorithm Wikipedia. [Online]. Available : https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[32] SDNlib library. [Online]. Available : http://sndlib.zib.de/home.action
[33] Mininet. [Online]. Available : http://mininet.org/
[34] Ryu OpenFlow controller. [Online]. Available : http://osrg.github.io/ryu/
[35] Barabási–Albert model Wikipedia. [Online]. Available : https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model
[36] Scale-free network Wikipedia. [Online]. Available : https://en.wikipedia.org/wiki/Scale-free_network
[37] Preferential attachment Wikipedia. [Online]. Available : https://en.wikipedia.org/wiki/Preferential_attachment