- Overview
- Registration Information
- Registration Discounts
- Symposium Organizers
- At a Glance
- Calendar
- Technical Sessions
- Live Streaming
- Purchase the Box Set
- Tutorial on GENI
- Posters and Demos
- Sponsorship
- Activities
- Hotel and Travel Information
- Services
- Students
- Questions?
- Help Promote
- For Participants
- Call for Papers
- Past Proceedings
sponsors
usenix conference policies
LOUP: The Principles and Practice of Intra-Domain Route Dissemination
Error message
You are not authorized to post comments.Nikola Gvozdiev, Brad Karp, and Mark Handley, University College London
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 principles, and show that these pathologies are not fundamental–rather, they are artifacts of iBGP. We propose the Simple Ordered Update Protocol (SOUP) and Link-Ordered Update Protocol (LOUP), clean-slate dissemination protocols for external routes that do not create transient loops, make stable route choices in the presence of failures, and achieve policy compliant routing without any configuration. We prove SOUP cannot loop, and demonstrate both protocols’ scalability and correctness in simulation and through measurements of a Quagga-based implementation.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Nikola Gvozdiev and Brad Karp and Mark Handley},
title = {{LOUP}: The Principles and Practice of {Intra-Domain} Route Dissemination},
booktitle = {10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)},
year = {2013},
isbn = {978-1-931971-00-3},
address = {Lombard, IL},
pages = {413--426},
url = {https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/gvozdiev},
publisher = {USENIX Association},
month = apr
}
Presentation Video
Presentation Audio
by Arvind Krishnamurthy
During the Internet's early years, as it became apparent that the network was growing at an exponential rate, routing protocols were designed with scalability and local responsiveness as first order considerations. Protocol designers developed solutions that didn't require structured or controlled propagation of routing state, especially since globally coordinated adoption of routes was considered to be too expensive and at loggerheads with the need for scalability and responsiveness. The resulting designs have been largely successful at accommodating the Internet's growth and increasing levels of autonomy, with the Internet expanding from a research network connecting a few dozen academic institutions to a global communication infrastructure. However, this routing scalability has not been achieved without certain costs. Routing protocols suffer from many deficiencies such as routing loops, blackholes, instabilities, troubleshooting complexity, and so on. Many of these issues arise from a lack of consistency in routing state across routers and the inability to control the adoption of new routes.
The authors tackle this tension head on and come up with the surprising result that routing consistency and light-weight scalability are not necessarily trade-offs, at least in the intradomain setting. They develop a new intradomain route dissemination protocol that does not suffer from transient routing loops, offers stability in the face of failures, and requires minimal configuration. Moreover, it achieves all of these goals with extremely light-weight techniques that are based on some simple but insightful observations regarding the nature of route propagation through an autonomous system. The protocol disseminates route updates in an ordered fashion along a reverse forwarding tree rooted at a border router. The key insight is that propagation of a route is considered to be separate from the adoption of the route, with the system delaying the adoption of a route till certain other routers have received and adopted the new route. The authors also develop variants of the protocol that trade off some robustness in order to achieve faster convergence.
There are additional reasons to read the paper. It provides a fresh perspective on intradomain routing and has a number of interesting observations regarding the various issues related to the adoption of a BGP-free core. The program committee found the proposal to be practical and an excellent example of the benefits that arise from careful algorithmic design of route propagation and adoption. While it is too early to speculate as to whether the new proposal or some variation would be adopted in practice, we are impressed with the benefits shown both using a formal analysis and a full implementation of the routing protocol.
connect with us