LOUP: The Principles and Practice of Intra-Domain Route Dissemination

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.