Measurement methods for fast and accurate blackhole identification with binary tomography

Ítalo Cunha, Renata Teixeira, Nick Feamster, Christophe Diot

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

19 Scopus citations


Binary tomography-the process of identifying faulty network links through coordinated end-to-end probes-is a promising method for detecting failures that the network does not automatically mask (e.g., network "blackholes"). Because tomography is sensitive to the quality of the input, however, näive end-to-end measurements can introduce inaccuracies. This paper develops two methods for generating inputs to binary tomography algorithms that improve their inference speed and accuracy. Failure confirmation is a perpath probing technique to distinguish packet losses caused by congestion from persistent link or node failures. Aggregation strategies combine path measurements from unsynchronized monitors into a set of consistent observations. When used in conjunction with existing binary tomography algorithms, our methods identify all failures that are longer than two measurement cycles, while inducing relatively few false alarms. In two wide-area networks, our techniques decrease the number of alarms by as much as two orders of magnitude. Compared to the state of the art in binary tomography, our techniques increase the identification rate and avoid hundreds of false alarms.

Original languageEnglish (US)
Title of host publicationIMC 2009 - Proceedings of the 2009 ACM SIGCOMM Internet Measurement Conference
Number of pages13
StatePublished - 2009
Event2009 9th ACM SIGCOMM Internet Measurement Conference, IMC 2009 - Chicago, IL, United States
Duration: Nov 4 2009Nov 6 2009

Publication series

NameProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC


Other2009 9th ACM SIGCOMM Internet Measurement Conference, IMC 2009
Country/TerritoryUnited States
CityChicago, IL

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • Diagnosis
  • Network tomography
  • Troubleshooting


Dive into the research topics of 'Measurement methods for fast and accurate blackhole identification with binary tomography'. Together they form a unique fingerprint.

Cite this