More Web Proxy on the site http://driver.im/

research-article

SafeGuard: safe forwarding during route changes

Authors:

David WetherallAuthors Info & Claims

CoNEXT '09: Proceedings of the 5th international conference on Emerging networking experiments and technologies

Pages 301 - 312

https://doi.org/10.1145/1658939.1658974

Published: 01 December 2009 Publication History

Abstract

This paper presents the design and evaluation of SafeGuard, an intra-domain routing system that can safely forward packets to their destinations even when routes are changing. SafeGuard is based on the simple idea that packets carry a destination address plus a local estimate of the remaining path cost. We show that this simple design enables routers to detect path inconsistencies during route changes and resolve on a working path for anticipated failure and restoration scenarios. This in turn means that route changes do not disrupt connectivity although routing tables are inconsistent over the network. We evaluate the router performance of SafeGuard using a prototype based on NetFPGA and Quagga. We show that SafeGuard is amenable to high-speed hardware implementation with low overhead. We evaluate the network performance of SafeGuard via simulation. The results show that SafeGuard converges faster than a state-of-the-art IP fast restoration mechanism and reduces periods of disruption to a minimal duration, i.e., the failure detection time.

References

[1]

Abilene Observatory. http://abilene.internet2.edu/observatory.

[2]

BRITE Topology Generator. http://www.cs.bu.edu/brite.

[3]

OSPF Shortest Path First Throttling. http://cisco.com/en/US/docs/ios/12_2s/feature/guide/fs_spftrl.html.

[4]

Quagga Routing Suite. http://www.quagga.net.

[5]

Reducing Link Failure Detection Time with BFD. http://www.networkworld.com/community/node/23380.

[6]

Scalable Simulation Framework. http://www.ssfnet.org.

[7]

SPF Delay Timer. http://www.juniper.net/techpubs/software/junos/junos74/swconfig74-routing/html/isis-summary53.html#1036104.

[8]

C. Alaettinoglu, V. Jacobson, and H. Yu. Towards Milli-Second IGP Convergence. Internet draft, draft-alaettinogluisis-convergence-00.txt, Nov 2000.

[9]

C. Boutremans, G. Iannaccone, and C. Diot. Impact of link failures on VoIP performance. In NOSSDAV, 2002.

Digital Library

[10]

S. Bryant, M. Shand, and S. Previdi. IP Fast Reroute Using Notvia Addresses. Internet draft, draft-ietf-rtgwg-ipfrrnotvia-addresses-00.txt, Dec 2006.

[11]

M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, and J. Van der Merwe. Design and implementation of a routing control platform. In NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, pages 15--28, Berkeley, CA, USA, 2005. USENIX Association.

Digital Library

[12]

B.-G. Chun, S. Ratnasamy, and E. Kohler. Netcomplex: a complexity metric for networked system designs. In NSDI'08: Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, pages 393--406, Berkeley, CA, USA, 2008. USENIX Association.

Digital Library

[13]

A. Ermolinskiy and S. Shenker. Reducing Transient Disconnectivity using Anomaly-Cognizant Forwarding. In ACM SIGCOMM HotNets VII, 2008.

[14]

P. Francois and O. Bonaventure. Avoiding transient loops during the convergence of link-state routing protocols. IEEE/ACM Transactions on Networking, 15(6):1280--1932, Dec 2007.

Digital Library

[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]

P. François, M. Shand, and O. Bonaventure. Disruption-free topology reconfiguration in OSPF Networks. In IEEE INFOCOM, Anchorage, USA, May 2007.

Digital Library

[17]

J.J. Garcia-Luna-Aceves. Loop-free routing using diffusing computations. IEEE/ACM Trans. Netw., 1(1):130--141, 1993.

Digital Library

[18]

G. Gibb, J. Lockwood, J. Naous, P. Hartke, and N. McKeown. NetFPGA--An Open Platform for Teaching How to Build Gigabit-Rate Network Switches and Routers. Education, IEEE Transactions on, 51(3):364--369, Aug 2008.

Digital Library

[19]

M. Goyal, G. Choudhury, A. Shaikh, K. Trivedi, and H. Hosseini. LSA correlation to schedule routing table calculations. Internet draft, draft-goyal-ospf-lsacorr-00.txt, Oct 2008.

[20]

G. Iannaccone, C. nee Chuah, R. Mortier, S. Bhattacharyya, and C. Diot. Analysis of link failures in an IP backbone. In IMW, 2002.

Digital Library

[21]

J.P. John, E. Katz-Bassett, A. Krishnamurthy, T. Anderson, and A. Venkataramani. Consensus routing: the internet as a distributed system. In NSDI'08: Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, pages 351--364, 2008.

Digital Library

[22]

D. Katz and D. Ward. Bidirectional Forwarding Detection. Internet draft, draft-ietf-bfd-base-07.txt, Jan 2008.

[23]

N. Kushman, S. Kandula, D. Katabi, and B.M. Maggs. RBGP: Staying connected in a connected world. In NSDI, 2007.

Digital Library

[24]

A. Kvalbein, A.F. Hansen, T. Cicic, S. Gjessing, and O. Lysne. Fast IP Network Recovery using Multiple Routing Configurations. In INFOCOM, pages 23--29, 2006.

[25]

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

Digital Library

[26]

A. Li, X. Yang, and D. Wetherall. SafeGuard: Responsive Routing with Consistent Forwarding. Technical Report DUKE-CS-TR-2008-04, Duke, 2008.

[27]

R. Mahajan, N.T. Spring, D. Wetherall, and T.E. Anderson. Inferring link weights using end-to-end measurements. In Internet Measurement Workshop, pages 231--236, 2002.

Digital Library

[28]

A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N. Chuah, and C. Diot. Characterization of Failures in an IP Backbone Network. In INFOCOM, 2004.

[29]

A.P. Markopoulou, F.A. Tobagi, and M.J. Karam. Assessment of VoIP Quality over Internet Backbones. In INFOCOM, 2002.

[30]

M. Motiwala, N. Feamster, and S. Vempala. Path Splicing: Reliable Connectivity with Rapid Recovery. In ACM SIGCOMM HotNets VI, 2007.

Digital Library

[31]

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., 15(2):359--372, 2007.

Digital Library

[32]

P. Pan, G. Swallow, and A. Atlas. Fast Reroute Extensions to RSVP-TE for LSP Tunnels. RFC4090, May 2005.

[33]

B. Rajagopalan, J. Luciani, and D. Awduche. IP over Optical Networks: A Framework. RFC3717, Mar 2004.

Digital Library

[34]

E. Rosen, A. Viswanathan, and R. Callon. Multiprotocol label switching architecture. RFC3031, Jan 2001.

Digital Library

[35]

M. Seaman. Exact hop count. 802.1aq draft, aq-seamanexact-hop-count-1206-01.pdf, Dec. 2006.

[36]

A. Shaikh and A.G. Greenberg. Experience in black-box ospf measurement. In Internet Measurement Workshop, pages 113--125, 2001.

Digital Library

[37]

M. Shand and S. Bryant. IP Fast Reroute Framework. Internet draft, draft-ietf-rtgwg-ipfrr-framework-08.txt, Feb. 2008.

[38]

N.T. Spring, R. Mahajan, D. Wetherall, and T.E. Anderson. Measuring ISP topologies with rocketfuel. IEEE/ACM Trans. Netw., 12(1):2--16, 2004.

Digital Library

[39]

W. Xu and J. Rexford. Miro: multi-path interdomain routing. In SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, pages 171--182, New York, NY, USA, 2006. ACM.

Digital Library

[40]

X. Yang and D. Wetherall. Source selectable path diversity via routing deflections. In SIGCOMM, pages 159--170, 2006.

Digital Library

[41]

Z. Zhong, R. Keralapura, S. Nelakuditi, Y. Yu, J. Wang, C.-N. Chuah, and S. Lee. Avoiding transient loops through interface-specific forwarding. In IWQoS, pages 219--232, 2005.

Digital Library

Cited By

Ma QYeh EHuang J(2021)Selfish Caching Games on Directed GraphsIEEE/ACM Transactions on Networking10.1109/TNET.2020.304794029:2(709-722)Online publication date: Apr-2021
https://doi.org/10.1109/TNET.2020.3047940
Ganchev IRak JCinkler TO’Droma M(2020)Taxonomy of Schemes for Resilient RoutingGuide to Disaster-Resilient Communication Networks10.1007/978-3-030-44685-7_18(455-482)Online publication date: 23-Jul-2020
https://doi.org/10.1007/978-3-030-44685-7_18
Ma QYeh EHuang J(2019)How Bad is Selfish Caching?Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3323679.3326499(11-20)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3323679.3326499
Show More Cited By

Index Terms

SafeGuard: safe forwarding during route changes
1. Networks
  1. Network architectures
  2. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Stable internet routing without global coordination

The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASs to have conflicting policies that can lead to ...
On inferring autonomous system relationships in the internet

The Internet consists of rapidly increasing number of hosts interconnected by constantly evolving networks of links and routers. Interdomain routing in the Internet is coordinated by the Border Gateway Protocol (BGP). BGP allows each autonomous system (...
Topology Control for Time-Evolving and Predictable Delay-Tolerant Networks

In delay tolerant networks (DTNs), the lack of continuous connectivity, network partitioning, and long delays make design of network protocols very challenging. Previous DTN research mainly focuses on routing and information propagation. However, with a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '09: Proceedings of the 5th international conference on Emerging networking experiments and technologies

December 2009

362 pages

ISBN:9781605586366

DOI:10.1145/1658939

General Chairs:
Jörg Liebeherr
University of Toronto, Canada
,
Giorgio Ventre
University of Napoli, Italy
,
Program Chairs:
Ernst Biersack
Eurecom, France
,
S. Keshav
University of Waterloo, Canada

Copyright © 2009 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Co-NEXT '09

Sponsor:

SIGCOMM

Co-NEXT '09: Conference on emerging Networking EXperiments and Technologies

December 1 - 4, 2009

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
212
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ma QYeh EHuang J(2021)Selfish Caching Games on Directed GraphsIEEE/ACM Transactions on Networking10.1109/TNET.2020.304794029:2(709-722)Online publication date: Apr-2021
https://doi.org/10.1109/TNET.2020.3047940
Ganchev IRak JCinkler TO’Droma M(2020)Taxonomy of Schemes for Resilient RoutingGuide to Disaster-Resilient Communication Networks10.1007/978-3-030-44685-7_18(455-482)Online publication date: 23-Jul-2020
https://doi.org/10.1007/978-3-030-44685-7_18
Ma QYeh EHuang J(2019)How Bad is Selfish Caching?Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3323679.3326499(11-20)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3323679.3326499
Penumarthi PPecora AO'Kane JNelakuditi S(2018)Failure-Inference-Based Fast Reroute with Progressive Link Metric Increments2018 27th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2018.8487413(1-7)Online publication date: Jul-2018
https://doi.org/10.1109/ICCCN.2018.8487413
Robertson GRoy NPenumarthi PNelakuditi SO'Kane J(2017)Loop-Free Convergence With Unordered UpdatesIEEE Transactions on Network and Service Management10.1109/TNSM.2017.267592114:2(373-385)Online publication date: Jun-2017
https://doi.org/10.1109/TNSM.2017.2675921
da Silva RSouza Mota E(2017)A Survey on Approaches to Reduce BGP Interdomain Routing Convergence Delay on the InternetIEEE Communications Surveys & Tutorials10.1109/COMST.2017.272238019:4(2949-2984)Online publication date: Dec-2018
https://doi.org/10.1109/COMST.2017.2722380
Gomes RLiberato ADominicini CRibeiro MMartinello M(2016)KAR: Key-for-Any-Route, a Resilient Routing System2016 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshop (DSN-W)10.1109/DSN-W.2016.11(120-127)Online publication date: Jun-2016
https://doi.org/10.1109/DSN-W.2016.11
Antonakopoulos SBejerano YKoppol P(2015)Full protection made easyIEEE/ACM Transactions on Networking10.1109/TNET.2014.236985523:4(1229-1242)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2369855
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
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