Degree distributions

The degree of a node provides a first-level quantification of the fault tolerance of that node in a given topology. A node with a degree $k$ can tolerate up to $k$ geographic failures before getting completely disconnected from all other nodes in the topology. In particular, a leaf node is not resilient to the geographic failure of its neighbor, but the failure of a leaf node itself has minimal impact on the rest of the network. On the other hand, the failure of a node with a very high degree would impact its many neighbors (corresponding to many different geographic regions). Given complete freedom in placing $E=k*N$ edges on $N$ nodes, it is possible to construct a topology that has a minimum vertex-cut of $2k$. In other words, the $E$ edges can be placed in such a way that even in the presence of any $2k-1$ node failures in the graph, the resulting topology will still remain connected. We term such a placement of edges that maximizes the size of the vertex cut as an optimal placement. In the optimal placement, all the vertices have the same degree, viz. $2*k$. For the simple case of $k=1$, the optimal placement results in a ring topology. Although this optimal placement may be difficult to construct due to practical constraints, it provides us a nice reference point for comparing the fault tolerance of ISP topologies. In order to contrast an ISP's topology from the optimal scenario, we look at the degree distribution of the nodes. We say that a graph has a skewed degree distribution if its node degrees are distributed over a wide range with a few large node degrees and a high percentage of the nodes are leaves. The Internet topology exhibits a skewed degree distribution which can be characterized by a power law as described in [4].

Figure 15: Degree Distribution of Geographic Topologies of ISPs

Among the 9 commercial ISPs, some of them such as AT&T and Genuity have a very skewed degree distributions while other ISPs such as PSINet and Verio have much less skewed degree distributions (closer to optimal). The degree distribution will not be affected much due to a few missing links. Figure 15 shows the degree distributions of AT&T and PSINet. AT&T's topology has the maximum percentage of leaves among the 9 ISP topologies (62%) and has a few nodes with a degree greater than 12 (Chicago, Dallas). On the other hand, more than 50% of PSINet's nodes have a degree of either 2 or 3. This matches the optimal degree for Verio given that it has an edge to node ratio $k = 1.5$, which corresponds to an optimal degree of $2*k = 3$. The ISP-Combine curve shows the degree distribution of the geographic topology obtained by combining the topology graphs of all 9 ISPs. The geographic nodes corresponding to the same city in the individual ISP topologies map to a single node in the combined topology. The combined topology still has a significant skew in its degree distribution. $29\%$ of the nodes continue to be leaves. This happens despite the combined topology having an edge to node ratio of $k = 2.5$, which corresponds to an optimal degree of 5. On the other hand, nodes located in the important networking hubs of U.S. (e.g, San Jose, Washington DC, Chicago) have a degree of more than $20$ in the combined topology.