Black hole search in computer networks: State-of-the-art, challenges and future directions

• We survey 35 single BHS, 9 multiple BHS papers, 14 papers on other malicious hosts.
• We use four categories to classify all surveyed papers.
• We compare papers by their complexity and introduce typical techniques.
• We analyse the impact of different assumptions and point out key observations.
• We mention research areas that are related to BHS and point out future directions.

As the size and use of networks continue to increase, network anomalies and faults are commonplace. Consequently, effective detection of such network issues is crucial for the deployment and use of network-based services. In this paper, we focus on one specific severe and pervasive network problem, namely the presence of one or more black holes. A black hole models a network node that is accidentally off-line or in which a process deletes any visiting agent or incoming data upon arrival without leaving any observable trace. Black Hole Search is the process that leverages mobile agents to locate black holes in a fully distributed way. In this paper, we review the state-of-the-art research in this area. We first distinguish between solutions for synchronous and asynchronous networks. We then consider the communication model between agents, their starting locations and the topological knowledge each may hold. We also report on the proposed algorithms with respect to their complexity and correctness. We remark that most existing work addresses locating a single black hole, multiple black hole search being significantly more complex. We not only summarize major results in this area but also briefly touch on other types of malicious hosts. Finally, we identify some open problems for future research.