Towards unbiased end-to-end network diagnosis

Yao Zhao*, Yan Chen, David Bindel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Internet fault diagnosis is extremely important for end-users, overlay network service providers (like Akamai ), 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 MILSs 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 MILSs, 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)
Article number5272259
Pages (from-to)1724-1737
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 1 2009


  • Internet diagnosis
  • Linear algebra
  • Network measurement

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

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

Cite this