Network Systems Group Princeton University   Publication Info

Title

Scalable Routing Overlay Networks

Authors

Aki Nakao
Larry Peterson
Andy Bavier

Abstract

Routing overlays have become a viable approach to working around slow BGP convergence and sub-optimal path selection, as well as to deploy novel forwarding architectures. A common sub-component of a routing overlay is a routing mesh: the route-selection algorithm considers only those virtual links &mdash inter-node links in an overlay &mdash in the routing mesh rather than all N² virtual links connecting an N-node overlay. Doing so reduces routing overhead, thereby improving the scalability of the overlay, as long as the process of constructing the mesh doesn't itself introduce overhead.

This paper proposes and evaluates a low-cost approach to building a topology-aware routing mesh that eliminates virtual links that contain duplicate physical segments in the underlying network. An evaluation of our method on PlanetLab shows that a conservative link pruning algorithm reduces routing overhead by a factor of two without negatively impacting route selection. Additional analysis quantifies the impact on route selection of defining an even sparser mesh on top of the topology-aware routing mesh, documenting the cost/benefit tradeoff that is intrinsic to routing. It also shows that constructing a sparser routing mesh on the topology-aware routing mesh &mdash rather than directly on the Internet &mdash itself benefits from having the reduced number of duplicate physical segments in the underlying network, which improves the resilience of the resulting routing mesh.

Published
As

In Operating Systems Review
Vol 40, No 1, Jan 2006

Download

paper gzip'd PostScript, 374 kB
paper PDF, 709 kB
BibTeX