政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/136961

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/136961

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113451/144438 (79%)
Visitors : 51245215 Online Users : 887

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/136961

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/136961

Title:	樂觀快速重路由 Optimistic Fast Rerouting
Authors:	陳海坤 Tan, Hai-Khun
Contributors:	郭桐惟 Kuo, Tung-Wei 陳海坤 Tan, Hai-Khun
Keywords:	快速重路由多鏈結故障恢復 fast rerouting multi-link failure recovery
Date:	2021
Issue Date:	2021-09-02 16:54:06 (UTC+8)
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.
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.
Description:	碩士國立政治大學資訊科學系 107753024
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0107753024
Data Type:	thesis
DOI:	10.6814/NCCU202101280
Appears in Collections:	[Department of Computer Science ] Theses

Files in This Item:

File	Description	Size	Format
302401.pdf		985Kb	Adobe PDF2	0	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - Feedback