An algebraic approach to practical and scalable overlay network monitoring

Yan Chen, David Bindel, Hanhee Song, Randy H. Katz

Research output: Contribution to journalConference article

88 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(n 2) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Our earlier extended abstract [1] briefly proposes an algebraic approach that selectively monitors k linearly independent paths that can fully describe all the O(n 2) paths. The loss rates and latency of these k paths can be used to estimate the loss rates and latency of all other paths. Our scheme only assumes knowledge of the underlying IP topology, with links dynamically varying between lossy and normal. In this paper, we improve, implement and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis indicating that for reasonably large n (e.g., 100), the growth of k is bounded as O(n log n), ii) efficient adaptation algorithms for topology changes, such as the addition or removal of end hosts and routing changes, iii) measurement load balancing schemes, and iv) topology measurement error handling. Both simulation and Internet experiments demonstrate we obtain highly accurate path loss rate estimation while adapting to topology changes within seconds and handling topology errors.

Original languageEnglish (US)
Pages (from-to)55-66
Number of pages12
JournalComputer Communication Review
Issue number4
StatePublished - 2004
EventACM SIGCOMM 2004: Conference on Computer Communications - Portland, OR, United States
Duration: Aug 30 2004Sep 3 2004


  • Dynamics
  • Load balancing
  • Network measurement and monitoring
  • Numerical linear algebra
  • Overlay
  • Scalability

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'An algebraic approach to practical and scalable overlay network monitoring'. Together they form a unique fingerprint.

  • Cite this