A Routing Underlay for Overlay Networks

Akihiro Nakao, Larry Peterson, Andy Bavier

Research output: Contribution to journalConference articlepeer-review

67 Scopus citations


We argue that designing overlay services to independently probe the Internet-with the goal of making informed application-specific routing decisions-is an untenable strategy. Instead, we propose a shared routing underlay that overlay services query. We posit that this underlay must adhere to two high-level principles. First, it must take cost (in terms of network probes) into account. Second, it must be layered so that specialized routing services can be built from a set of basic primitives. These principles lead to an underlay design where lower layers expose large-scale, coarse-grained static information already collected by the network, and upper layers perform more frequent probes over a narrow set of nodes. This paper proposes a set of primitive operations and three library routing services that can be built on top of them, and describes how such libraries could be useful to overlay services.

Original languageEnglish (US)
Pages (from-to)11-18
Number of pages8
JournalComputer Communication Review
Issue number4
StatePublished - Oct 2003
Externally publishedYes
EventProceedings of ACM SIGCOMM 2003: Conference on Computer Communications - Karlsruhe, Germany
Duration: Aug 25 2003Aug 29 2003


  • Infrastructure
  • Overlay Networks
  • Routing

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'A Routing Underlay for Overlay Networks'. Together they form a unique fingerprint.

Cite this