學術產出-Theses
Article View/Open
Publication Export
-
題名 樂觀快速重路由
Optimistic Fast Rerouting作者 陳海坤
Tan, Hai-Khun貢獻者 郭桐惟
Kuo, Tung-Wei
陳海坤
Tan, Hai-Khun關鍵詞 快速重路由
多鏈結故障恢復
fast rerouting
multi-link failure recovery日期 2021 上傳時間 2-Sep-2021 16:54:06 (UTC+8) 摘要 在現代網路中，由於網路硬體（例：交換器和鏈結）數量的增加，因此故障經常發生。然而，即使存在故障，我們也必須保證封包可以成功地傳送。當封包在路由過程中遇到故障時，封包會轉而經由故障轉移路由發送。為了減少計算和安裝故障轉移路由的反應時間，過去專家們提出了避免控制平面參與的快速重路由。大多數先前關於快速重路由的工作為了保證傳遞性而犧牲了故障轉移路由的品質（例：故障轉移路由的長度）。在本論文中，我們採取了一種樂觀的方法，它有利於故障轉移路由的品質而不是傳遞上的保證。但是，我們仍然需要保證封包的傳遞。為此，我們提出了一個用於快速重路由的樂觀恢復框架。在此框架中，有兩種可能的模式，一種是樂觀模式，其目標只是優化故障轉移路由的品質，而不考慮保證傳遞性，另一種模式為恢復模式，其目標只是保證封包的傳遞性。最後，此框架還有一個監控子程序，它的目標是確定我們是否應該從樂觀模式切換到恢復模式。我們考慮最小化故障轉移路由長度的問題並實現了該框架。在此框架中我們採用了過去文獻所提的兩種快速重路由演算法作為恢復模式。實驗結果顯示，與過去文獻的解決方案相比，我們的方法可以顯著縮短故障轉移路由。
In modern computer networks, failures occur regularly due to the increasing amount of the communication components (e.g., switches and links). Thus, it is vital to guarantee packet delivery even with the presence of failures. When a packet encounters a failure during routing, a failover route is computed. To reduce the response time of computing and installing the failover route, fast rerouting, which avoids the involvement of the control plane, is proposed. Most prior works on fast rerouting sacrifice the quality of the failover route (e.g., the length of the failover route) for delivery guarantee. In this thesis, we take an optimistic approach, which favors the quality of the failover route over delivery guarantee. Nevertheless, we still need to guarantee packet delivery. To this end, we propose an optimistic-recovery framework for fast rerouting. In this framework, there are two possible modes, the optimistic mode, whose goal is merely to optimize the quality of the failover route without considering delivery guarantee, and the recovery mode, whose goal is merely to guarantee packet delivery. Finally, there is a monitoring subroutine in this framework, whose goal is to determine whether we should switch from the optimistic mode to the recovery mode. We have realized the framework by considering the problem of minimizing the length of the failover route, and we have adopted two prior fast rerouting algorithms as the algorithms for the recovery mode. The simulation results show that, compared to these prior solutions, our approach can significantly shorten the failover route.參考文獻 [1] P. Gill, N. Jain, and N. Nagappan, “Understanding network failures in data centers: Measurement, analysis, and implications,” vol. 41, no. 4, p. 350–361, Aug. 2011. [Online]. Available: https://doi.org/10.1145/2043164.2018477[2] J. Liu, A. Panda, A. Singla, B. Godfrey, M. Schapira, and S. Shenker, “Ensuring connectivity via data plane mechanisms,” in Presented as part of the 10th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 13), 2013, pp. 113–126.[3] K.T. Foerster, Y.A. Pignolet, S. Schmid, and G. Tredan, “Casa: congestion and stretch aware static fast rerouting,” in IEEE INFOCOM 2019IEEE Conference on Computer Communications. IEEE, 2019, pp. 469–477.[4] A. Atlas and A. Zinin, “Basic specification for ip fast reroute: Loopfree alternates,” RFC 5286, September, Tech. Rep., 2008.[5] A. Kamisiński, “Evolution of ip fastreroute strategies,” in 2018 10th International Workshop on Resilient Networks Design and Modeling (RNDM). IEEE, 2018, pp. 1– 6.[6] P. Pan, G. Swallow, A. Atlas et al., “Fast reroute extensions to rsvpte for lsp tunnels,” 2005.[7] Switch Specification 1.3.1, “OpenFlow,＂, 2012. [Online]. Available: https://www. opennetworking.org/wpcontent/ uploads/2013/04/openflowspecv1.3.1. pdf[8] K.T. Foerster, A. Kamisinski, Y.A. Pignolet, S. Schmid, and G. Tredan, “Bonsai: Efficient fast failover routing using small arborescences,” in 2019 49th Annual IEEE/IFIP 20 International Conference on Dependable Systems and Networks (DSN). IEEE, 2019, pp. 276–288.[9] T. Elhourani, A. Gopalan, and S. Ramasubramanian, “Ip fast rerouting for multilink failures,” IEEE/ACM Transactions on Networking, vol. 24, no. 5, pp. 3014–3025, 2016.[10] M. Chiesa, I. Nikolaevskiy, S. Mitrović, A. Gurtov, A. Madry, M. Schapira, and S. Shenker, “On the resiliency of static forwarding tables,” IEEE/ACM Transactions on Networking, vol. 25, no. 2, pp. 1133–1146, 2017.[11] J. Edmonds, “Edgedisjoint branchings,” Combinatorial algorithms, 1973.[12] A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi, “Fast edge splitting and edmonds’ arborescence construction for unweighted graphs,” in Proceedings of the nineteenth annual ACMSIAM symposium on Discrete algorithms. Citeseer, 2008, pp. 455–464.[13] K.T. Foerster, A. Kamisinski, Y.A. Pignolet, S. Schmid, and G. Tredan, “Improved fast rerouting using postprocessing,” IEEE Transactions on Dependable and Secure Computing, 2020.[14] Network topologies, 2013. [Online]. Available: https://github.com/networkresearch/ topologies[15] A. Steger and N. C. Wormald, “Generating random regular graphs quickly,” Combinatorics, Probability and Computing, vol. 8, no. 04, pp. 377–396, 1999.[16] G. Enyedi, G. Rétvári, and T. Cinkler, “A novel loopfree ip fast reroute algorithm,” in Meeting of the European Network of Universities and Companies in Information and Communication Engineering. Springer, 2007, pp. 111–119.[17] S. Nelakuditi, S. Lee, Y. Yu, Z.L. Zhang, and C.N. Chuah, “Fast local rerouting for handling transient link failures,” IEEE/ACM Transactions on networking, vol. 15, no. 2, pp. 359–372, 2007.[18] J. Wang and S. Nelakuditi, “Ip fast reroute with failure inferencing,” in Proceedings of the 2007 SIGCOMM workshop on Internet network management, 2007, pp. 268–273. 21[19] B. Zhang, J. Wu, and J. Bi, “Rpfp: Ip fast reroute with providing complete protection and without using tunnels,” in 2013 IEEE/ACM 21st International Symposium on Quality of Service (IWQoS). IEEE, 2013, pp. 1–10.[20] K. Lakshminarayanan, M. Caesar, M. Rangan, T. Anderson, S. Shenker, and I. Stoica, “Achieving convergencefree routing using failurecarrying packets,” ACM SIGCOMM computer communication review, vol. 37, no. 4, pp. 241–252, 2007.[21] P. Hande, M. Chiang, R. Calderbank, and S. Rangan, “Network pricing and rate allocation with content provider participation,” in IEEE INFOCOM 2009. IEEE, 2009, pp. 990–998.[22] M. Borokhovich and S. Schmid, “How (not) to shoot in your foot with sdn local fast failover,” in International Conference On Principles Of Distributed Systems. Springer, 2013, pp. 68–82.[23] B. Stephens, A. L. Cox, and S. Rixner, “Plinko: Building provably resilient forwarding tables,” in Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, 2013, pp. 1–7.[24] ——, “Scalable multifailure fast failover via forwarding table compression,” in Proceedings of the Symposium on SDN Research, 2016, pp. 1–12.[25] M. Chiesa, A. Gurtov, A. Mądry, S. Mitrović, I. Nikolaevkiy, A. Panda, M. Schapira, and S. Shenker, “Exploring the limits of static failover routing,” arXiv preprint arXiv: 1409.0034, 2014.[26] M. Chiesa, I. Nikolaevskiy, S. Mitrović, A. Panda, A. Gurtov, A. Maidry, M. Schapira, and S. Shenker, “The quest for resilient (static) forwarding tables,” in IEEE INFOCOM 2016The 35th Annual IEEE International Conference on Computer Communications. Ieee, 2016, pp. 1–9.[27] M. Chiesa, A. Gurtov, A. Madry, S. Mitrovic, I. Nikolaevskiy, M. Shapira, and S. Shenker, “On the resiliency of randomized routing against multiple edge failures,” in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss DagstuhlLeibnizZentrum fuer Informatik, 2016. 22[28] K.T. Foerster, Y.A. Pignolet, S. Schmid, and G. Tredan, “Local fast failover routing with low stretch,” ACM SIGCOMM Computer Communication Review, vol. 48, no. 1, pp. 35– 41, 2018. 描述 碩士
國立政治大學
資訊科學系
107753024資料來源 http://thesis.lib.nccu.edu.tw/record/#G0107753024 資料類型 thesis dc.contributor.advisor 郭桐惟 zh_TW dc.contributor.advisor Kuo, Tung-Wei en_US dc.contributor.author (Authors) 陳海坤 zh_TW dc.contributor.author (Authors) Tan, Hai-Khun en_US dc.creator (作者) 陳海坤 zh_TW dc.creator (作者) Tan, Hai-Khun en_US dc.date (日期) 2021 en_US dc.date.accessioned 2-Sep-2021 16:54:06 (UTC+8) - dc.date.available 2-Sep-2021 16:54:06 (UTC+8) - dc.date.issued (上傳時間) 2-Sep-2021 16:54:06 (UTC+8) - dc.identifier (Other Identifiers) G0107753024 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/136961 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 107753024 zh_TW dc.description.abstract (摘要) 在現代網路中，由於網路硬體（例：交換器和鏈結）數量的增加，因此故障經常發生。然而，即使存在故障，我們也必須保證封包可以成功地傳送。當封包在路由過程中遇到故障時，封包會轉而經由故障轉移路由發送。為了減少計算和安裝故障轉移路由的反應時間，過去專家們提出了避免控制平面參與的快速重路由。大多數先前關於快速重路由的工作為了保證傳遞性而犧牲了故障轉移路由的品質（例：故障轉移路由的長度）。在本論文中，我們採取了一種樂觀的方法，它有利於故障轉移路由的品質而不是傳遞上的保證。但是，我們仍然需要保證封包的傳遞。為此，我們提出了一個用於快速重路由的樂觀恢復框架。在此框架中，有兩種可能的模式，一種是樂觀模式，其目標只是優化故障轉移路由的品質，而不考慮保證傳遞性，另一種模式為恢復模式，其目標只是保證封包的傳遞性。最後，此框架還有一個監控子程序，它的目標是確定我們是否應該從樂觀模式切換到恢復模式。我們考慮最小化故障轉移路由長度的問題並實現了該框架。在此框架中我們採用了過去文獻所提的兩種快速重路由演算法作為恢復模式。實驗結果顯示，與過去文獻的解決方案相比，我們的方法可以顯著縮短故障轉移路由。 zh_TW dc.description.abstract (摘要) In modern computer networks, failures occur regularly due to the increasing amount of the communication components (e.g., switches and links). Thus, it is vital to guarantee packet delivery even with the presence of failures. When a packet encounters a failure during routing, a failover route is computed. To reduce the response time of computing and installing the failover route, fast rerouting, which avoids the involvement of the control plane, is proposed. Most prior works on fast rerouting sacrifice the quality of the failover route (e.g., the length of the failover route) for delivery guarantee. In this thesis, we take an optimistic approach, which favors the quality of the failover route over delivery guarantee. Nevertheless, we still need to guarantee packet delivery. To this end, we propose an optimistic-recovery framework for fast rerouting. In this framework, there are two possible modes, the optimistic mode, whose goal is merely to optimize the quality of the failover route without considering delivery guarantee, and the recovery mode, whose goal is merely to guarantee packet delivery. Finally, there is a monitoring subroutine in this framework, whose goal is to determine whether we should switch from the optimistic mode to the recovery mode. We have realized the framework by considering the problem of minimizing the length of the failover route, and we have adopted two prior fast rerouting algorithms as the algorithms for the recovery mode. The simulation results show that, compared to these prior solutions, our approach can significantly shorten the failover route. en_US dc.description.tableofcontents 中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . iAbstract . . . . . . . . . . . . . . . . . . . . . . . iiContents . . . . . . . . . . . . . . . . . . . . . . .iiiList of Tables . . . . . . . . . . . . . . . . . . . . .vList of Figures . . . . . . . . . . . . . . . . . . . .vi1 Introduction . . . . . . . . . . . . . . . . . . . . .12 The Optimistic-Recovery Framework . . . . . . . . . . 42.1 Some Challenges of Realizing the Optimistic-Recovery Framework . . . . . . . . . . . . . . . . . . . . . . . 43 Minimizing the Length of the Failover Route: A Realization of the Optimistic-Recovery Framework . . . .63.1 Network Model and The Definition of Arborescences . 63.2 The Design of the Recovery Mode: EGR and BSC . . . .73.3 The Design of the Optimistic Mode . . . . . . . . . 83.4 The Design of the Monitoring Subroutine . . . . . . 94 Performance Evaluation . . . . . . . . . . . . . . .104.1 Simulation Setting . . . . . . . . . . . . . . . . 104.2 Performance Metrics . . . . . . . . . . . . . . . .114.3 Results on Random k-Regular Networks . . . . . . . 134.3.1 The Comparison of Our Solution and EGR . . . . . 134.3.2 The Comparison of Our Solution and BSC . . . . . 164.4 Results on Rocketfuel Topologies . . . . . . . . . 165 Related Work . . . . . . . . . . . . . . . . . . . . 186 Conclusion . . . . . . . . . . . . . . . . . . . . . 19Bibliography . . . . . . . . . . . . . . . . . . . . . 20 zh_TW dc.format.extent 1009618 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0107753024 en_US dc.subject (關鍵詞) 快速重路由 zh_TW dc.subject (關鍵詞) 多鏈結故障恢復 zh_TW dc.subject (關鍵詞) fast rerouting en_US dc.subject (關鍵詞) multi-link failure recovery en_US dc.title (題名) 樂觀快速重路由 zh_TW dc.title (題名) Optimistic Fast Rerouting en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] P. Gill, N. Jain, and N. Nagappan, “Understanding network failures in data centers: Measurement, analysis, and implications,” vol. 41, no. 4, p. 350–361, Aug. 2011. [Online]. Available: https://doi.org/10.1145/2043164.2018477[2] J. Liu, A. Panda, A. Singla, B. Godfrey, M. Schapira, and S. Shenker, “Ensuring connectivity via data plane mechanisms,” in Presented as part of the 10th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 13), 2013, pp. 113–126.[3] K.T. Foerster, Y.A. Pignolet, S. Schmid, and G. Tredan, “Casa: congestion and stretch aware static fast rerouting,” in IEEE INFOCOM 2019IEEE Conference on Computer Communications. IEEE, 2019, pp. 469–477.[4] A. Atlas and A. Zinin, “Basic specification for ip fast reroute: Loopfree alternates,” RFC 5286, September, Tech. Rep., 2008.[5] A. Kamisiński, “Evolution of ip fastreroute strategies,” in 2018 10th International Workshop on Resilient Networks Design and Modeling (RNDM). IEEE, 2018, pp. 1– 6.[6] P. Pan, G. Swallow, A. Atlas et al., “Fast reroute extensions to rsvpte for lsp tunnels,” 2005.[7] Switch Specification 1.3.1, “OpenFlow,＂, 2012. [Online]. Available: https://www. opennetworking.org/wpcontent/ uploads/2013/04/openflowspecv1.3.1. pdf[8] K.T. Foerster, A. Kamisinski, Y.A. Pignolet, S. Schmid, and G. Tredan, “Bonsai: Efficient fast failover routing using small arborescences,” in 2019 49th Annual IEEE/IFIP 20 International Conference on Dependable Systems and Networks (DSN). IEEE, 2019, pp. 276–288.[9] T. Elhourani, A. Gopalan, and S. Ramasubramanian, “Ip fast rerouting for multilink failures,” IEEE/ACM Transactions on Networking, vol. 24, no. 5, pp. 3014–3025, 2016.[10] M. Chiesa, I. Nikolaevskiy, S. Mitrović, A. Gurtov, A. Madry, M. Schapira, and S. Shenker, “On the resiliency of static forwarding tables,” IEEE/ACM Transactions on Networking, vol. 25, no. 2, pp. 1133–1146, 2017.[11] J. Edmonds, “Edgedisjoint branchings,” Combinatorial algorithms, 1973.[12] A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi, “Fast edge splitting and edmonds’ arborescence construction for unweighted graphs,” in Proceedings of the nineteenth annual ACMSIAM symposium on Discrete algorithms. Citeseer, 2008, pp. 455–464.[13] K.T. Foerster, A. Kamisinski, Y.A. Pignolet, S. Schmid, and G. Tredan, “Improved fast rerouting using postprocessing,” IEEE Transactions on Dependable and Secure Computing, 2020.[14] Network topologies, 2013. [Online]. Available: https://github.com/networkresearch/ topologies[15] A. Steger and N. C. Wormald, “Generating random regular graphs quickly,” Combinatorics, Probability and Computing, vol. 8, no. 04, pp. 377–396, 1999.[16] G. Enyedi, G. Rétvári, and T. Cinkler, “A novel loopfree ip fast reroute algorithm,” in Meeting of the European Network of Universities and Companies in Information and Communication Engineering. Springer, 2007, pp. 111–119.[17] S. Nelakuditi, S. Lee, Y. Yu, Z.L. Zhang, and C.N. Chuah, “Fast local rerouting for handling transient link failures,” IEEE/ACM Transactions on networking, vol. 15, no. 2, pp. 359–372, 2007.[18] J. Wang and S. Nelakuditi, “Ip fast reroute with failure inferencing,” in Proceedings of the 2007 SIGCOMM workshop on Internet network management, 2007, pp. 268–273. 21[19] B. Zhang, J. Wu, and J. Bi, “Rpfp: Ip fast reroute with providing complete protection and without using tunnels,” in 2013 IEEE/ACM 21st International Symposium on Quality of Service (IWQoS). IEEE, 2013, pp. 1–10.[20] K. Lakshminarayanan, M. Caesar, M. Rangan, T. Anderson, S. Shenker, and I. Stoica, “Achieving convergencefree routing using failurecarrying packets,” ACM SIGCOMM computer communication review, vol. 37, no. 4, pp. 241–252, 2007.[21] P. Hande, M. Chiang, R. Calderbank, and S. Rangan, “Network pricing and rate allocation with content provider participation,” in IEEE INFOCOM 2009. IEEE, 2009, pp. 990–998.[22] M. Borokhovich and S. Schmid, “How (not) to shoot in your foot with sdn local fast failover,” in International Conference On Principles Of Distributed Systems. Springer, 2013, pp. 68–82.[23] B. Stephens, A. L. Cox, and S. Rixner, “Plinko: Building provably resilient forwarding tables,” in Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, 2013, pp. 1–7.[24] ——, “Scalable multifailure fast failover via forwarding table compression,” in Proceedings of the Symposium on SDN Research, 2016, pp. 1–12.[25] M. Chiesa, A. Gurtov, A. Mądry, S. Mitrović, I. Nikolaevkiy, A. Panda, M. Schapira, and S. Shenker, “Exploring the limits of static failover routing,” arXiv preprint arXiv: 1409.0034, 2014.[26] M. Chiesa, I. Nikolaevskiy, S. Mitrović, A. Panda, A. Gurtov, A. Maidry, M. Schapira, and S. Shenker, “The quest for resilient (static) forwarding tables,” in IEEE INFOCOM 2016The 35th Annual IEEE International Conference on Computer Communications. Ieee, 2016, pp. 1–9.[27] M. Chiesa, A. Gurtov, A. Madry, S. Mitrovic, I. Nikolaevskiy, M. Shapira, and S. Shenker, “On the resiliency of randomized routing against multiple edge failures,” in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss DagstuhlLeibnizZentrum fuer Informatik, 2016. 22[28] K.T. Foerster, Y.A. Pignolet, S. Schmid, and G. Tredan, “Local fast failover routing with low stretch,” ACM SIGCOMM Computer Communication Review, vol. 48, no. 1, pp. 35– 41, 2018. zh_TW dc.identifier.doi (DOI) 10.6814/NCCU202101280 en_US
