Scalable routing overlay networks

Akihiro Nakao, Larry Peterson, Andy Bavier

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


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 inter-node links in an overlay - in the routing mesh rather than all N 2 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 quanties 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 - rather than directly on the Internet - itself benefits from having the reduced number of duplicate physical segments in the underlying network, which improves the resilience of the resulting routing mesh.

Original languageEnglish (US)
Pages (from-to)49-61
Number of pages13
JournalOperating Systems Review (ACM)
Issue number1
StatePublished - 2006
Externally publishedYes


  • Infrastructure
  • Overlay networks
  • Routing

ASJC Scopus subject areas

  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Scalable routing overlay networks'. Together they form a unique fingerprint.

Cite this