Tomography-based overlay network monitoring

Yan Chen*, David Bindel, Randy H. Katz

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations


Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with n end hosts, existing systems either require O(n2) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Unlike other network tomography systems, we characterize end-to-end losses (this extends to any additive metrics, including latency) rather than individual link losses. We find a minimal basis set of k linearly independent paths that can fully describe all the O(n2) paths. We selectively monitor and measure the loss rates of these paths, then apply them to estimate the loss rates of all other paths. By extensively studying synthetic and real topologies, we find that for reasonably large n (e.g., 100), k is only in the range of O(n log n). This is explained by the moderately hierarchical nature of Internet routing. Our scheme only assumes the knowledge of underlying IP topology, and any link can become lossy or return to normal. In addition, our technique is tolerant to topology measurement inaccuracies, and is adaptive to topology changes.

Original languageEnglish (US)
Title of host publicationProceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003
Number of pages6
StatePublished - Dec 1 2003
EventProceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003 - Miami Beach, FL, United States
Duration: Oct 27 2003Oct 29 2003


OtherProceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003
Country/TerritoryUnited States
CityMiami Beach, FL


  • Network measurement and monitoring
  • Network tomography
  • Numerical linear algebra
  • Overlay networks

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Tomography-based overlay network monitoring'. Together they form a unique fingerprint.

Cite this