Improving Network Robustness

We present a simple, fully decentralized approach to improving robustness of existing unstructured overlay networks, against a selective deletion of nodes (e.g., attacks on network hubs). The approach is based on modifying the network by adding or rewiring links at random.We quantify the effectiveness of adding randomness to the network by computing the curve governing the tradeoff between the number of modifications and the increase in robustness. For certain networks, a relatively modest amount of randomization can significantly improve the average path length (quantifying performance degradation) and the size of the largest connected component (quantifying network availability) after an attack.

By: Alina Beygelzimer, Geoffrey Grinstein, Ralph Linsker, Irina Rish

Published in: Proceedings of First International Conference on Autonomic Computing. Los Alamitos, CA, , IEEE Computer Society. , p.322-3 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .