research-article

LOUP: who's afraid of the big bad loop?

Authors:

Nikola Gvozdiev,

Brad Karp,

Mark HandleyAuthors Info & Claims

HotNets-XI: Proceedings of the 11th ACM Workshop on Hot Topics in Networks

Pages 19 - 24

https://doi.org/10.1145/2390231.2390235

Published: 29 October 2012 Publication History

Get Access

Abstract

We consider the intra-AS route dissemination problem from first principles, and illustrate that when known route dissemination techniques propagate even a single external routing change, they can cause transient anomalies. These anomalies are not fundamental; they are artifacts of the order in which existing proposals disseminate routes. We show that carefully ordering route updates avoids transient looping and black holes. Perhaps surprisingly, this ordering may be enforced in a completely distributed fashion, while retaining familiar correctness, scalability, and convergence properties.

References

[1]

Hurricane electric's looking glass server, July 2012.

Google Scholar

[2]

M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, and J. van der Merwe. Design and implementation of a routing control platform. In Proc. ACM/USENIX NSDI, 2005.

Digital Library

Google Scholar

[3]

J. Choi, J. H. Park, P. chun Cheng, D. Kim, and L. Zhang. Understanding BGP next-hop diversity. IEEE INFOCOM, Apr. 2011.

Google Scholar

[4]

A. Fabrikant, U. Syed, and J. Rexford. There's something about MRAI: timing diveristy can exponentially worsen bgp convergence. In Proc. IEEE INFOCOM '11, 2011.

Crossref

Google Scholar

[5]

J. Garcia-Luna-Aceves. Loop-free routing using diffusing computations. IEEE/ACM Transactions on Networking, 1(1), Feb. 1993.

Digital Library

Google Scholar

[6]

T. Griffin and G. T. Wilfong. Analysis of the MED oscillation problem in BGP. In Proc. ICNP '02, pages 90--99, Washington, DC, USA, 2002.

Digital Library

Google Scholar

[7]

N. Gvozdiev, B. Karp, and M. Handley. Loup: The principles and practice of intra-domain route dissemination. Technical Report RN/12/10, University College London, Oct 2012.

Google Scholar

[8]

V. Jacobson, C. Alaettinoglu, and K. Poduri. BST - BGP scalable transport. Presentation at NANOG 27, Feb. 2003.

Google Scholar

[9]

N. Kushman, S. Kandula, and D. Katabi. Can you hear me now?! it must be BGP. ACM CCR, Apr. 2007.

Digital Library

Google Scholar

[10]

N. Kushman, S. Kandula, D. Katabi, and B. Maggs. R-BGP: staying connected in a connected world. In Proc. USENIX NSDI '07, 2007.

Digital Library

Google Scholar

[11]

J. H. Park, R. Oliveira, S. Amante, D. McPherson, and L. Zhang. BGP route reflection revisited. IEEE Communications Magazine, July 2012.

Google Scholar

[12]

M. Shand, S. Bryant, S. Previdi, C. Filsfils, P. Francois, and O. Bonaventure. Loop-free convergence using ofib. IETF Internet Draft draft-ietf-rtgwg-ordered-fib-06, June 2012.

Google Scholar

Cited By

View all

Holterbach TVissicchio SDainotti AVanbever L(2017)SWIFTProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098856(460-473)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098856
Zhu YKang NCao JGreenberg ALu GMahajan RMaltz DYuan LZhang MZhao BZheng H(2015)Packet-Level Telemetry in Large Datacenter NetworksACM SIGCOMM Computer Communication Review10.1145/2829988.278748345:4(479-491)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1145/2829988.2787483
Zhu YKang NCao JGreenberg ALu GMahajan RMaltz DYuan LZhang MZhao BZheng HUhlig SMaennel OKarp BPadhye J(2015)Packet-Level Telemetry in Large Datacenter NetworksProceedings of the 2015 ACM Conference on Special Interest Group on Data Communication10.1145/2785956.2787483(479-491)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1145/2785956.2787483
Show More Cited By

Index Terms

LOUP: who's afraid of the big bad loop?
1. Networks
  1. Network architectures
  2. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

LOUP: the principles and practice of intra-domain route dissemination
nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation

Under misconfiguration or topology changes, iBGP with route reflectors exhibits a variety of ills, including routing instability, transient loops, and routing failures. In this paper, we consider the intra-domain route dissemination problem from first ...
An efficient and secure overlay network for general peer-to-peer systems
On investigating overlay service topologies

Recently, a moderate amount of work has been reported on the use of overlay networks to support value-added network services, such as multicasting, Quality-of-Service (QoS), security, etc. To design an overlay network, the first step is to choose an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

HotNets-XI: Proceedings of the 11th ACM Workshop on Hot Topics in Networks

October 2012

150 pages

ISBN:9781450317764

DOI:10.1145/2390231

General Chairs:
Srikanth Kandula
MSR
,
Jitendra Padhye
MSR
,
Program Chairs:
Emin Gun Sirer
Cornell University
,
Ramesh Govindan
University of Southern California

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

HotNets-XI

Sponsor:

SIGCOMM

HotNets-XI: 11th ACM Workshop on Hot Topics in Networks

October 29 - 30, 2012

Washington, Redmond

Acceptance Rates

Overall Acceptance Rate 110 of 460 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
64
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Holterbach TVissicchio SDainotti AVanbever L(2017)SWIFTProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098856(460-473)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098856
Zhu YKang NCao JGreenberg ALu GMahajan RMaltz DYuan LZhang MZhao BZheng H(2015)Packet-Level Telemetry in Large Datacenter NetworksACM SIGCOMM Computer Communication Review10.1145/2829988.278748345:4(479-491)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1145/2829988.2787483
Zhu YKang NCao JGreenberg ALu GMahajan RMaltz DYuan LZhang MZhao BZheng HUhlig SMaennel OKarp BPadhye J(2015)Packet-Level Telemetry in Large Datacenter NetworksProceedings of the 2015 ACM Conference on Special Interest Group on Data Communication10.1145/2785956.2787483(479-491)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1145/2785956.2787483
Schlinker BZarifis KCunha IFeamster NKatz-Bassett EKatz-Bassett EHeidemann JGodfrey BFeldmann A(2014)PEERINGProceedings of the 13th ACM Workshop on Hot Topics in Networks10.1145/2670518.2673887(1-7)Online publication date: 27-Oct-2014
https://dl.acm.org/doi/10.1145/2670518.2673887
Javed UCunha IChoffnes DKatz-Bassett EAnderson TKrishnamurthy A(2013)PoiRootACM SIGCOMM Computer Communication Review10.1145/2534169.248603643:4(183-194)Online publication date: 27-Aug-2013
https://dl.acm.org/doi/10.1145/2534169.2486036

View Options

Login options

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

Cited By

Index Terms

Recommendations

LOUP: the principles and practice of intra-domain route dissemination

An efficient and secure overlay network for general peer-to-peer systems

On investigating overlay service topologies