The Connectivity and Fault-Tolerance of the Internet Topology

In this paper, we apply data mining analysis to study the topology of the Internet, thus creating a new processing framework. To the best of our knowledge, this is one of the first studies that focus on the Internet topology at the router level. i.e. each node is a router. The size (280K nodes) and the nature of the graph are such that new analysis methods have to be employed. First, we suggest computationally-expensive metrics to characterize topological properties. Then, we present an efficient approximation algorithm that makes the calculation of these metrics possible. Finally, we demonstrate the initial results of our framework. For example, we show that we can identify central routers, and poorly connected or even isolated nodes. We also find that the Internet is surprisingly resilient to random link and router failures, having only small changes in the connectivity for fewer than 10,000 failures. Our framework seems a promising step towards understanding and characterizing the Internet topology and possible other real communication graphs such as web-graphs.