On the probability of facing random breakdowns: a measure of networks’ vulnerability

Abstract

In this paper, we study the vulnerability of networks in the case of random removal of individual nodes. To achieve this goal, a network reliability measure, the probability of messages facing malfunctions, has been proposed. The benefit of this measure is its capability of applying in a wide range of graphs. Moreover, it is well suited to human activities and foraging patterns of some sorts of animals, as they try to make an alternative path in the case of facing failures. We examine the most prominent communication networks such as meshes and tori; further, CAN, Chord, Petersen, PRU, and Hypergrid, which are well suited for P2P networks, have been investigated. In order to gain a better understanding of the studied networks’ vulnerability and easier evaluation of the proposed measure, an ant colony-based communication protocol has been presented. Experimental results verify the correctness of the proposed measure.

Keywords:

• fault-tolerance
• network theory
• network vulnerability
• interconnection networks
• P2P networks
• performance evaluation
• ant colony

2010 AMS Subject Classifications:

• 05A05
• 05C10
• 68M15
• 68R10
• 94C15

Acknowledgements

The authors of the paper would like to express their deep gratitude to Mr. Iman Pakravan for his kind and valuable efforts on implementing computer simulations in the first version of the paper. Since he was busy in the last year and had to leave the research institution, he was out of access and unfortunately not able to continue his collaboration with the authors. Therefore, they had to add a new member to the research group in order to proceed with the work, resulting in the current version of the paper. They hope to have other chances to take part together in future researches.

Disclosure Statement

No potential conflict of interest was reported by the authors.