Failure of high connectivity nodes

The skewed degree distributions of many tier-1 ISPs indicate that many geographic regions of an ISP may get disconnected if some high connectivity geographic nodes fail. To evaluate this, we consider the failure scenario where the $f$ nodes of highest degrees in a graph fail. We define a pair of geographic nodes that are connected by a network path and can communicate with each other as a communicating pair. A connected topology of $N$ nodes can support $N(N+1)/2$ communicating pairs. (Since each node represents a geographic region, we also consider intra-node communication of a node with itself.) Under the scenario where the $f$ nodes of highest degrees fail, the graph is disconnected into a forest where a node can only communicate with other nodes in its connected component. A connected component with $m<N$ nodes can support $m*(m+1)/2$ communicating pairs. In the simple case where the parent of a leaf node fails, it produces a connected component of size $1$ which supports exactly one communicating pair.

Figure 16: Tolerance to Geographic Failures

Figure 16 shows the percentage of communicating pairs supported in the various ISP networks in face of a varying number of geographic failures. The combined topology of the 9 ISPs supports 68% of the communicating pairs even after the removal of 5 important networking hubs in the US (San Jose, New York, Washington DC, Chicago, Los Angeles). Among the 9 ISPs, while Genuity and PSINet exhibit the least and the best fault tolerance characteristics. In the face of a single node failure, most of the ISPs lose between 15% and 30% of their communicating pairs in the worst case. It is important to note that these results may represent a near-worst case failure scenario for the ISPs. If, however, many backup links are missing from our topology, the fraction of communicating pairs may be much higher than what we have portrayed. However, our essential message from this analysis is that a balanced degree distribution is a good feature for building a fault tolerant topology for an ISP.