Scalable Routing Overlay Networks
Report ID: TR-712-04Author: Nakao, Akihiro / Peterson, Larry
Date: 2004-08-00
Pages: 14
Download Formats: |PDF|
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.