research-article

On improving the efficiency and manageability of NotVia

Authors:

Pierre Francois,

Xiaowei YangAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 26, Pages 1 - 12

https://doi.org/10.1145/1364654.1364688

Published: 10 December 2007 Publication History

Abstract

This paper presents techniques that improve the efficiency and manageability of an IP Fast Reroute (IPFRR) technology: NotVia. NotVia provides the IPFRR service for all destinations in an ISP's network upon any single link or node failure, while previous proposals such as Loop-free Alternates (LFA) can not guarantee this level of coverage. However, NotVia increases the computational and memory costs of the IPFRR service, and poses new challenges to network management, as routers are unaware of the links and nodes (hence the amount of traffic) that they actually protect. This paper introduces three techniques: NotVia aggregation, prioritized NotVia computation, and the rNotVia algorithm that collectively reduce the overhead of NotVia and improve its manageability. We use simulations to evaluate these techniques on real ISP topologies as well as on randomly generated topologies. The results show that the computational and memory overhead of NotVia are reduced to a fraction of their previous values on various topologies, suggesting that the techniques proposed in this paper make NotVia a more efficient and easy-to-manage IPFRR solution.

References

[1]

Project Website. http://nds.ics.uci.edu/notvia.

[2]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. NETWORK FLOWS: THEORY, ALGORITHMS, AND APPLICATIONS. Prentice Hall, 1993.

Digital Library

[3]

A. Atlas. U-turn alternates for IP/LDP Fast-Reroute. Internet draft, draft-atlas-ip-local-protect-uturn-03.txt, Feb 2006.

[4]

A. Atlas and A. Zinin. Basic specification for IP fast-reroute: Loop-free Alternates. Internet draft, draft-ietf-rtgwg-ipfrr-spec-base-06.txt, Feb 2006.

[5]

S. Bryant, C. Filsfils, S. Previdi, and M. Shand. IP Fast Reroute using tunnels. Internet draft, draft-bryant-ipfrr-tunnels-02.txt, Apr 2005.

[6]

S. Bryant and M. Shand. A framework for loop-free convergence. Internet draft, draft-bryant-shand-lf-conv-frmwk-03.txt, Oct 2006.

[7]

S. Bryant, M. Shand, and S. Previdi. IP fast reroute using notvia addresses. Internet draft, draft-ietf-rtgwg-ipfrr-notvia-addresses-00.txt, Dec 2006.

[8]

Cisco. IS-IS Fast-Flooding of LSPs Using the fast-flood Command. Technical document, http://www.cisco.com/univercd/cc/td/doc/product/software/iosi20/120newft/i20limit/i20s/i20s27/fstfld.pdf, 2003.

[9]

N. Feamster and H. Balakrishnan. Packet Loss Recovery for Streaming Video. In International Packet Video Workshop, 2002.

[10]

S. Fischer, N. Kammenhuber, and A. Feldmann. REPLEX --- dynamic traffic engineering based on wardrop routing policies. In CoNext, 2006.

Digital Library

[11]

B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In INFOCOM (2), pages 519--528, 2000.

[12]

P. Francois and O. Bonaventure. Avoiding transient loops during IGP convergence in IP networks. In IEEE INFOCOM, Miami, Florida, USA, Mar 2005.

[13]

P. Francois and O. Bonaventure. An evaluation of ip-based fast reroute techniques. In Co-Next, 2005.

Digital Library

[14]

P. Francois, O. Bonaventure, M. Shand, S. Previdi, and S. Bryant. Loop-free convergence using ordered FIB updates. Internet draft, draft-francois-ordered-fib-01.txt, Mar 2006.

[15]

P. Francois, C. Filsfils, J. Evans, and O. Bonaventure. Achieving sub-second IGP convergence in large IP networks. SIGCOMM Comput. Commun. Rev., 35(3):35--44, 2005.

Digital Library

[16]

M. Gjoka, V. Ram, and X. Yang. Evaluation of IP fast reroute proposals. In IEEE Comsware, 2007.

[17]

W. J. Goralski and H. Gredler. The Complete IS-IS Routing Protocol. Springer, 2005.

Digital Library

[18]

J. He, M. Bresler, M. Chiang, and J. Rexford. Towards multi-layer traffic engineering: Optimization of congestion control and routing. IEEE Journal on Selected Areas in Communications, 2007.

Digital Library

[19]

G. Iannaccone, C. Chuah, S. Bhattacharyya, and C. Diot. Feasibility of IP restoration in a tier-1 backbone. IEEE Network Magazine, Jan-Feb 2004.

Digital Library

[20]

W. Jiang and H. Schulzrinne. Comparison and Optimization of Packet Loss Repair Methods on VoIP Perceived Quality under Bursty Loss. In NOSSDAV, 2002.

Digital Library

[21]

D. Katz, K. Kompella, and D. Yeung. Traffic engineering (te) extensions to ospf version 2. Technical report, Internet Engineering Task Force, United States, 2003.

Digital Library

[22]

A. Kvalbein, A. F. Hansen, T. Cicic, S. Gjessing, and O. Lysne. Fast ip network recovery using multiple routing configurations. In Infocom, 2006.

[23]

K. Lakshminarayanan, M. Caesar, M. Rangan, T. Anderson, S. Shenker, and I. Stoica. Achieving convergence-free routing using failure-carrying packets. In ACM SIGCOMM, 2007.

Digital Library

[24]

A. Li, P. Francois, and X. Yang. On Improving the Efficiency and Manageability of NotVia. Technical report, http://www.ics.uci.edu/~angl/papers/notvia_report.pdf.

[25]

K. McCloghrie and M. T. Rose. Structure and identification of management information for TCP/IP-based internets. Request for Comments 1065, Internet Engineering Task Force, Aug. 1988.

Digital Library

[26]

A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation. In MASCOTS 2001, August 2001.

Digital Library

[27]

S. Nelakuditi, S. Lee, Y. Yu, Z.-L. Zhang, and C.-N. Chuah. Fast local rerouting for handling transient link failures. IEEE/ACM Trans. Netw., 2007.

Digital Library

[28]

rtgwg. IETF routing area working group meeting minutes. http://www3.ietf.org/proceedings/06nov/minutes/rtgwg.txt, Nov 2006.

[29]

M. Shand and S. Bryant. IP Fast Reroute Framework. Internet draft, draft-ietf-rtgwg-ipfrr-framework-06.txt, Oct 2006.

[30]

R. Sridharan and C. Diot. Achieving near-optimal traffic engineering solutions for current ospf/is-is networks, 2002.

[31]

J.-P. Vasseur, M. Pickavet, and P. Demeester. Network Recovery: Protection and Restoration of Optical, SONET-SDH, and MPLS. Morgan Kaufmann, 2004.

Digital Library

[32]

A. Zinin. Analysis and minimization of microloops in link-state routing protocols. Internet draft, draft-zinin-microloop-analysis-00.txt, Oct 2004.

Cited By

Chiesa MKamisinski ARak JRetvari GSchmid S(2021)A Survey of Fast-Recovery Mechanisms in Packet-Switched NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2021.306398023:2(1253-1301)Online publication date: Oct-2022
https://doi.org/10.1109/COMST.2021.3063980
Yang YXu MLi Q(2018)Fast Rerouting Against Multi-Link Failures Without Topology ConstraintIEEE/ACM Transactions on Networking10.1109/TNET.2017.278085226:1(384-397)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TNET.2017.2780852
Gopalan ARamasubramanian S(2016)IP fast rerouting and disjoint multipath routing with three edge-independent spanning treesIEEE/ACM Transactions on Networking10.1109/TNET.2015.244017924:3(1336-1349)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2440179
Show More Cited By

Recommendations

Improving efficiency and effectiveness of multipath routing in computer networks
Improving the Efficiency of Network Topology Discovery
GPC-WORKSHOPS '08: Proceedings of the 2008 The 3rd International Conference on Grid and Pervasive Computing - Workshops

As wireless and mobile networks are getting more of a commonplace, the discovery and management of dynamic networks has become a serious issue. Since the topology of wireless and mobile networks always keeps changing, the key issue of topology discovery ...
RFC 8102: Remote-LFA Node Protection and Manageability

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

December 2007

448 pages

ISBN:9781595937704

DOI:10.1145/1364654

General Chairs:
Jim Kurose
University of Massachusetts
,
Henning Schulzrinne
Columbia University

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Alcatel-Lucent
SIGCOMM: ACM Special Interest Group on Data Communication
Thomson
CISCO
IMDEA
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

National Science Foundation

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
174
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chiesa MKamisinski ARak JRetvari GSchmid S(2021)A Survey of Fast-Recovery Mechanisms in Packet-Switched NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2021.306398023:2(1253-1301)Online publication date: Oct-2022
https://doi.org/10.1109/COMST.2021.3063980
Yang YXu MLi Q(2018)Fast Rerouting Against Multi-Link Failures Without Topology ConstraintIEEE/ACM Transactions on Networking10.1109/TNET.2017.278085226:1(384-397)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TNET.2017.2780852
Gopalan ARamasubramanian S(2016)IP fast rerouting and disjoint multipath routing with three edge-independent spanning treesIEEE/ACM Transactions on Networking10.1109/TNET.2015.244017924:3(1336-1349)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2440179
Yuan Yang Mingwei Xu Qi Li (2016)Tunneling on demand: A lightweight approach for IP fast rerouting against multi-link failures2016 IEEE/ACM 24th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS.2016.7590416(1-6)Online publication date: Jun-2016
https://doi.org/10.1109/IWQoS.2016.7590416
Imura KYoshihiro T(2014)Reactive Load Balancing During Failure State in IP Fast Reroute SchemesJournal of Information Processing10.2197/ipsjjip.22.52722:3(527-535)Online publication date: 2014
https://doi.org/10.2197/ipsjjip.22.527
Yang BLiu JShenker SLi JZheng K(2014)Keep Forwarding: Towards k-link failure resilient routingIEEE INFOCOM 2014 - IEEE Conference on Computer Communications10.1109/INFOCOM.2014.6848098(1617-1625)Online publication date: Apr-2014
https://doi.org/10.1109/INFOCOM.2014.6848098
Nagy MTapolcai JRetvari G(2014)On the design of Resilient IP Overlays2014 10th International Conference on the Design of Reliable Communication Networks (DRCN)10.1109/DRCN.2014.6816147(1-8)Online publication date: Apr-2014
https://doi.org/10.1109/DRCN.2014.6816147
Nagy MTapolcai JRétvári G(2014)Optimization methods for improving IP-level fast protection for local shared risk groups with Loop-Free AlternatesTelecommunications Systems10.1007/s11235-013-9822-y56:1(103-119)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1007/s11235-013-9822-y
Csikor LTapolcai JRéTváRi G(2013)Optimizing IGP link costs for improving IP-level resilience with Loop-Free AlternatesComputer Communications10.5555/2445634.244590236:6(645-655)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.5555/2445634.2445902
Tapolcai JRetvari G(2013)Router virtualization for improving IP-level resilience2013 Proceedings IEEE INFOCOM10.1109/INFCOM.2013.6566882(935-943)Online publication date: Apr-2013
https://doi.org/10.1109/INFCOM.2013.6566882
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten