Open AccessRoot cause diagnosis in error‐propagating networks
Author(s) -
Seo Eunsoo,
Dogan Gulustan,
Abdelzaher Tarek,
Brown Theodore
Publication year - 2016
Publication title -
security and communication networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.446
H-Index - 43
eISSN - 1939-0122
pISSN - 1939-0114
DOI - 10.1002/sec.1415
Subject(s) - computer science , rumor , timestamp , root cause , root (linguistics) , node (physics) , root cause analysis , network packet , the internet , algorithm , data mining , computer network , world wide web , linguistics , philosophy , public relations , forensic engineering , structural engineering , political science , engineering , reliability engineering
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. Copyright © 2016 John Wiley & Sons, Ltd.