Cluster generation example

A simple example demonstrates how the clustering operates in practice. In Figure 1, AS 2, AS 3, and AS 6 are connected to many other nodes. In this example $N_7 = \{4,7\}$ is dominated by $N_4 = \{4,5,7\}$ so $dom(4,7) = true$. For each pass, each node makes a list of candidate parents. During the first pass, AS 7 coalesces with AS 4. AS 4 is now the exemplar for a cluster and AS 7 is removed from $N_4$ reducing it to $\{4,5\}$. The parent of AS 7, $p(7)$, is set to 4. Similarly, AS 8 is dominated by AS 5. During the second pass, AS 4 coalesces with AS 5 to form an even bigger cluster with AS 5 as the exemplar.

Figure 1: Walk-through of the clustering algorithm

In the third pass, the algorithm has nothing to coalesce, since no node is dominated by any single neighbor. In this case $N_1 = \{1,2,3,5\}$ is not dominated by AS 2, AS 3, or AS 5. Since AS 1 connects to one node (AS 2) missing from the AS 5 list, $overhang(1,5) = 1$. Similarly, $overhang(5,1) = 1$ because of AS 6.

In a later pass, the tolerance grows above 1.0 and the candidate parent set of AS 1 becomes $C_1 = \{3,5\}$. The nearest of these is AS 5, so AS 1 coalesces with AS 5. During the same pass, the candidate parents of AS 5 becomes $C_5 = \{3\}$. Note that AS 1 is not a candidate parent of AS 5 because it originally had a smaller out-degree.

In the example, AS 7 would be denoted as AS3.5.4.7. The name shows the relationship that AS 7 is a child of the progressively larger super-clusters. Clients in AS 7 would benefit (albeit progressively less) from caches on the path to the backbone.