Root cause diagnosis in error-propagating networks

Eunsoo Seo, Gulustan Dogan, Tarek Abdelzaher, Theodore Brown

Research output: Contribution to journalArticle

Abstract

Various types of errors can propagate in networks, and they are usually hard to diagnose. For example, social networks spread rumors as well as useful information. Computer networks can spread Internet worms or malicious packets. In many cases, it is very hard to find the root cause (a.k.a. initial rumor spreader) of such errors without complete knowledge of the error propagation. We aim to find the root cause node when there is limited information about error propagation. We assume that there are very small number of monitor nodes in the network reporting whether error reached them or not. With this assumption, we first propose an algorithm that finds the most probable root cause node. Second, to improve the accuracy of root cause analysis, we propose another algorithm that makes use of timestamp of error reception. Finally, we study how to select monitors effectively so that root cause analysis can be accurate. With real networks from various domains, our algorithms are shown to be very effective.

Original languageEnglish (US)
Pages (from-to)1297-1308
Number of pages12
JournalSecurity and Communication Networks
Volume9
Issue number11
DOIs
StatePublished - Jul 25 2016

    Fingerprint

Keywords

  • distributed systems
  • error classification
  • error propagation
  • error-propagating networks
  • root cause diagnosis

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this