Basic Search / Detailed Display

Author: 鄭詠儒
Albert Cheng
Thesis Title: 軟體定義網路中基於中國剩餘定理轉發架構下單鏈路故障快速恢復系統
CRT-­based Fast Failover Routing in Software­-Defined Networking
Advisor: 金台齡
Tai-Lin Chin
Committee: 沈中安
Chung-An Shen
Chin-Ya Huang
Shan-Hsiang Shen
Degree: 碩士
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2021
Graduation Academic Year: 109
Language: 英文
Pages: 44
Keywords (in Chinese): 軟體定義網路源路由偏轉可靠性中國剩餘定理
Keywords (in other languages): Chinese Remainder Theorem
Reference times: Clicks: 152Downloads: 2
School Collection Retrieve National Library Collection Retrieve Error Report
  • 軟體定義網路殘數系統是一種新的網路架構,它依靠簡單的同餘運算來取代軟體定義網路交換機依靠流表轉發封包的操作。 當前的軟體定義網路殘數系統不包括有效率的單鏈路故障恢復機制。 本文提出了 KeyPair,旨在通過添加單鏈路故障快速轉發封包機制來增強殘數係統結構。 本論文提出的 KeyPair 是一種新的域內可靠源路由系統,它依靠控制器事先將主要路徑以及偏轉路徑的訊息編碼在轉發標籤中,每個數據包的封包內,交換機只需要透過封包編碼資訊即可以有效轉發封包。在 KeyPair 路由系統中,每個交換機包含兩個密鑰,每個封包發送端口都為轉發標籤 除上和該路徑上交換機上密鑰所獲得的餘數。本文通過實驗模擬對 KeyPair 進行了評估,結果表明 KeyPair 有效地將數據包轉發到目的地,並保持高吞吐量和低數據包丟失率。

    Chinese Remainder Theorem (CRT) based forwarding system is a new network architecture that replaces the SDN switch flow table lookup operation by relying on a simple modulo operation. The current CRT-based forwarding system does not include an effective mechanism for recovery. This paper proposed KeyPair that aims to enhance the forwarding architecture by adding a fast failover mechanism. KeyPair is a new intradomain resilient source routing system that relies on the controller to encode route path information in the packet header for each switch on the routing path. KeyPair path selection mechanism guarantees that each switch along the path contains the shortest rerouting path to reach the destination. This paper evaluates KeyPair through extensive simulations. The results show that KeyPair efficiently recovers the route when a link failure occurs and maintains high throughput and low packet loss rates.

    AbstractinChinese AbstractinEnglish Contents ListofFigures ListofTables ListofAlgorithms 1 Introduction 2 RelatedWork ........................... 4 2.1 PacketForwardingUsingLabels.............. 4 2.2 ResilientRouting ...................... 7 2.3 SDNCRT­basedForwarding ................ 9 2.4 ProtocolIndependentArchitecture . . . . . . . . . . . . . 10 3 PreliminariesForCRT­BasedRouting . . . . . . . . . . . . . . 12 4 KeyPairResilientRoutingSystemDesign . . . . . . . . . . . . 15 4.1 PathSelectionAlgorithm.................. 16 4.2 KeySelectionforPathEncoding.............. 20 4.3 KeyPairSwitchForwarding ................ 22 4.4 EncodingSize........................ 24 5 KeyPairPrototypeImplementation ................ 25 5.1 KeyPair Core Network Implementation . . . . . . . . . . 25 5.2 KeyPairSwitchImplementation .............. 27 5.3 KeyPairSwitchModificationProcess . . . . . . . . . . . 32 6 Experiment ............................ 33 6.1 Setup ............................ 33 6.2 Result............................ 36 7 Conclusions ............................ 41 References............................... 42

    [1] A. Sgambelluri, A. Giorgetti, F. Cugini, F. Paolucci, and P. Castoldi, “Openflow­based segment pro­ tection in ethernet networks,” Journal of Optical Communications and Networking, vol. 5, no. 9, pp. 1066–1075, 2013.

    [2] Y. D. Lin, H. Y. Teng, C. R. Hsu, C. C. Liao, and Y. C. Lai, “Fast failover and switchover for link failures and congestion in software defined networks,” in IEEE International Conference on Commu­ nications, pp. 1–6, 2016.

    [3] E. Spitznagel, D. Taylor, and J. Turner, “Packet classification using extended tcams,” in 11th IEEE International Conference on Network Protocols., pp. 120–131, 2003.

    [4] H. Huang, S. Guo, P. Li, W. Liang, and A. Y. Zomaya, “Cost minimization for rule caching in software defined networking,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 4, pp. 1007– 1016, 2015.

    [5] S. H. Yeganeh, A. Tootoonchian, and Y. Ganjali, “On scalability of software­defined networking,” IEEE Communications Magazine, vol. 51, no. 2, pp. 136–141, 2013.

    [6] S. Sharma, D. Staessens, D. Colle, M. Pickavet, and P. Demeester, “Enabling fast failure recovery in openflow networks,” in International Workshop on the Design of Reliable Communication Networks, pp. 164–171, 2011.

    [7] S. Sharma, D. Staessens, D. Colle, M. Pickavet, and P. Demeester, “Openflow: Meeting carrier­grade recovery requirements,” Computer Communications, vol. 36, no. 6, pp. 656–665, 2013.

    [8] X. Yang and D. Wetherall, “Source selectable path diversity via routing deflections,” ACM SIGCOMM Computer Communication Review, vol. 36, no. 4, pp. 159–170, 2006.

    [9] M. Motiwala, M. Elmore, N. Feamster, and S. Vempala, “Path splicing,” in ACM SIGCOMM confer­ ence on data communication, pp. 27–38, 2008.

    [10] R. M. Ramos, M. Martinello, and C. E. Rothenberg, “Slickflow: Resilient source routing in data center networks unlocked by openflow,” in IEEE conference on local computer networks, pp. 606–613, 2013.

    [11] M. Martinello, M. R. Ribeiro, R. E. Z. de Oliveira, and R. de Angelis Vitoi, “KeyFlow: A prototype for evolving sdn toward core network fabrics,” IEEE Network, vol. 28, no. 2, pp. 12–19, 2014.

    [12] M. Martinello, A. B. Liberato, A. F. Beldachi, K. Kondepu, R. L. Gomes, R. Villaca, M. R. Ribeiro, Y. Yan, E. Hugues­Salas, and D. Simeonidou, “Programmable residues defined networks for edge data centres,” in International Conference on Network and Service Management, pp. 1–9, 2017.

    [13] C. K. Dominicini, G. L. Vassoler, R. Valentim, R. S. Villaca, M. R. Ribeiro, M. Martinello, and E. Zam­ bon, “Keysfc: Traffic steering using strict source routing for dynamic and efficient network orches­ tration,” Computer Networks, vol. 167, p. 106975, 2020.

    [14] R. R. Gomes, A. B. Liberato, C. K. Dominicini, M. R. Ribeiro, and M. Martinello, “KAR: Key­for­ any­route, a resilient routing system,” in IEEE/IFIP International Conference on Dependable Systems and Networks Workshop, pp. 120–127, 2016.

    [15] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: enabling innovation in campus networks,” ACM SIGCOMM computer com­ munication review, vol. 38, no. 2, pp. 69–74, 2008.

    [16] E. Rosen, A. Viswanathan, et al., “Multiprotocol Label Switching Architecture.” RFC 3031, Jan. 2001.

    [17] “Virtual Bridged Local Area Networks Amendment 12: Forwarding and Queuing Enhancements for Time­Sensitive Streams,” IEEE Std 802.1Qav­2009, pp. C1–72, 2009.

    [18] C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, and P. Francois, “The segment routing architec­ture,” in IEEE Global Communications Conference, pp. 1–6, 2015.

    [19] R. MacDavid, R. Birkner, O. Rottenstreich, A. Gupta, N. Feamster, and J. Rexford, “Concise encoding of flow attributes in sdn switches,” in Proceedings of the Symposium on SDN Research, pp. 48–60, 2017.

    [20] A. Hari, T. Lakshman, and G. Wilfong, “Path switching: Reduced­state flow handling in sdn using path information,” in ACM Conference on Emerging Networking Experiments and Technologies, pp. 1–7, 2015.

    [21] C. Filsfils, S. Previdi, A. Bashandy, B. Decraene, S. Litkowski, M. Horneffer, R. Shakir, J. Tantsura, and E. Crabbe, “Segment Routing with MPLS data plane,” IETF Internet Draft, 2014.

    [22] R. Bhatia, F. Hao, M. Kodialam, and T. Lakshman, “Optimized network traffic engineering using segment routing,” in IEEE Conference on Computer Communications, pp. 657–665, 2015.

    [23] C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, and P. Francois, “The segment routing architec­ ture,” in Global Communications Conference, pp. 1–6, 2015.
    [24] A. S. Iyer, V. Mann, and N. R. Samineni, “SwitchReduce: Reducing switch state and controller in­ volvement in openflow networks,” in IFIP Networking conference, pp. 1–9, 2013.

    [25] S. A. Jyothi, M. Dong, and P. B. Godfrey, “Towards a flexible data center fabric with source routing,” in ACM SIGCOMM Symposium on Software Defined Networking Research, pp. 1–8, 2015.

    [26] Z. Guo, Y. Xu, M. Cello, J. Zhang, Z. Wang, M. Liu, and H. J. Chao, “Jumpflow: Reducing flow table usage in software­defined networks,” Computer Networks, vol. 92, no. 2, pp. 300–315, 2015.

    [27] P. Pan, G. Swallow, A. Atlas, et al., “Fast reroute extensions to rsvp­te for lsp tunnels,” 2005.

    [28] F. Hao, M. Kodialam, and T. Lakshman, “Optimizing restoration with segment routing,” in IEEE International Conference on Computer Communications, pp. 1–9, 2016.

    [29] G. T. Nguyen, R. Agarwal, J. Liu, M. Caesar, P. B. Godfrey, and S. Shenker, “Slick packets,” ACM SIGMETRICS Performance Evaluation Review, vol. 39, no. 1, pp. 205–216, 2011.

    [30] A. Li, X. Yang, and D. Wetherall, “Safeguard: safe forwarding during route changes,” in International Conference On Emerging Networking Experiments And Technologies, pp. 301–312, 2009.

    [31] V. Padma and P. Yogesh, “Proactive failure recovery in openflow based software defined networks,” in International Conference on Signal Processing, Communication and Networking, pp. 1–6, 2015.

    [32] S. Sharma, D. Staessens, D. Colle, M. Pickavet, and P. Demeester, “A demonstration of fast failure recovery in software defined networking,” in International Conference on Testbeds and Research Infrastructures, pp. 411–414, 2012.

    [33] A. Liberato, M. Martinello, R. L. Gomes, A. F. Beldachi, E. Salas, R. Villaca, M. R. Ribeiro, K. Kon­ depu, G. Kanellos, R. Nejabati, et al., “RDNA: Residue­defined networking architecture enabling ultra­reliable low­latency datacenters,” IEEE Transactions on Network and Service Management, vol. 15, no. 4, pp. 1473–1487, 2018.

    [34] Y. Ren, T.­H. Tsai, J.­C. Huang, C.­W. Wu, and Y.­C. Tseng, “Flowtable­free routing for data cen­ ter networks: A software­defined approach,” in IEEE Global Communications Conference, pp. 1–6, 2017.

    [35] C. Dominicini, D. Mafioletti, A. C. Locateli, R. Villaca, M. Martinello, M. Ribeiro, and A. Gorodnik, “Polka: Polynomial key­based architecture for source routing in network fabrics,” in IEEE Conference on Network Softwarization, pp. 326–334, 2020.

    [36] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, et al., “P4: Programming protocol­independent packet processors,” ACM SIGCOMM Computer Communication Review, vol. 44, no. 3, pp. 87–95, 2014.

    [37] H. Song, “Protocol­oblivious forwarding: Unleash the power of sdn through a future­proof forwarding plane,” in ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, pp. 127–132, 2013.

    [38] S. Li, K. Han, N. Ansari, Q. Bao, D. Hu, J. Liu, S. Yu, and Z. Zhu, “Improving sdn scalability with protocol­oblivious source routing: A system­level study,” IEEE Transactions on Network and Service Management, vol. 15, no. 1, pp. 275–288, 2017.

    [39] S. Li, D. Hu, W. Fang, and Z. Zhu, “Source routing with protocol­oblivious forwarding (POF) to enable efficient e­health data transfers,” in International Conference on Communications, pp. 1–6, 2016.

    [40] C. Albert, “Keypair.”