FAD and SPA: End-to-end link-level loss rate inference without infrastructure

Yao Zhao*, Yan Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


It is highly desirable and important for end users, with no special privileges, to identify and pinpoint faults inside the network that degrade the performance of their applications. However, existing tools are inaccurate to infer the link-level loss rates and have large diagnosis granularity. To address these problems, we propose a suite of user-level diagnosis approaches in two categories: (1) the diagnosis tool needs to be deployed only at the source and (2) the tool has to be deployed at both source and destination. For the former, we propose two fragmentation aided diagnosis approaches (FAD), Algebraic FAD and Opportunistic FAD, which use IP fragmentation to enable accurate link-level loss rate inference. For the latter category, we propose Striped Probe Analysis (SPA) which significantly improves the diagnosis granularity over those of the source-only approaches. Internet experiments are applied to evaluate each individual scheme (including an improved version of the state-of-the-art tool, Tulip [R. Mahajan, N. Spring, D. Wetherall, T. Anderson, User-level internet path diagnosis, in: ACM SOSP, 2003]) and various hybrid approaches. The results indicate that our approaches dramatically outperform existing work (especially for diagnosis granularity). But more importantly, we show that combination of different individual approaches (e.g. OFAD + Tulip or OFAD + SPA) provide not only the best performance but also smooth tradeoff among deployment requirement, diagnosis accuracy and granularity.

Original languageEnglish (US)
Pages (from-to)1303-1318
Number of pages16
JournalComputer Networks
Issue number9
StatePublished - Jun 25 2009


  • IP Fragmentation
  • Loss Rate Inference
  • Network Measurement

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'FAD and SPA: End-to-end link-level loss rate inference without infrastructure'. Together they form a unique fingerprint.

Cite this