Scalable Routing Overlay Networks

Abstract:

Routing overlays have become a viable approach to working
around slow BGP convergence and sub-optimal path selection.
A common sub-component of a routing overlay is a
routing mesh: the route-selection algorithm considers only
virtual links in the mesh rather than all N2 paths connecting
an N-node overlay, thereby reducing routing overhead
and improving the scalability of the overlay. This paper proposes
and evaluates an 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, thereby
improving scalability. Additional analysis quantifies the impact
on route selection of more aggressively removing mesh
edges, documenting the cost/benefit tradeoff that is intrinsic
to routing.