Towards unbiased end-to-end network diagnosis

Yao Zhao*, Yan Chen, David Bindel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

36 Scopus citations


Internet fault diagnosis is extremely important for end users, overlay network service providers (like Akamai [1]) and even Internet service providers (ISPs). However, because link-level properties cannot be uniquely determined from end-to-end measurements, the accuracy of existing statistical diagnosis approaches is subject to uncertainty from statistical assumptions about the network. In this paper, we propose a novel Least-biased End-to-end Network Diagnosis (in short, LEND) system for inferring link-level properties like loss rate. We define a minimal identifiable link sequence (MILS) as a link sequence of minimal length whose properties can be uniquely identified from end-to-end measurements. We also design efficient algorithms to find all the MILSes and infer their loss rates for diagnosis. Our LEND system works for any network topology and for both directed and undirected properties, and incrementally adapts to network topology and property changes. It gives highly accurate estimates of the loss rates of MILSes, as indicated by both extensive simulations and Internet experiments. Furthermore, we demonstrate that such diagnosis can be achieved with fine granularity and in near real-time even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.

Original languageEnglish (US)
Pages (from-to)219-230
Number of pages12
JournalComputer Communication Review
Issue number4
StatePublished - Oct 2006


  • Internet diagnosis
  • Linear algebra
  • Network measurement

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Towards unbiased end-to-end network diagnosis'. Together they form a unique fingerprint.

Cite this