Results of AS clustering

Figure 2: Results of AS cluster formation. The left graph shows how the number of clusters declines as clusters are coalesced. The right graph shows how the path length in the derived tree compares to the path length in the original graph of best paths.

For this study a $\delta$ tolerance growth of 0.25 per pass was chosen. Figure 2 shows the number of clusters at the end of each pass through the list of AS's. The first four passes cluster all of the easily-classified AS's with small out-degree. Passes five through ten found a large number of national, government, and educational transit AS's. After the pass 37, further reduction in the number of clusters takes much longer. To avoid excess layers at the top of the tree, we stopped the algorithm at pass 40 and declared the 21 remaining exemplars to be the first layer of the tree.

Figure 2 also compares the cumulative distribution of distances to the backbone in both the original full graph and the tree left at the end of clustering. The maximum distance from the backbone was 5 in the full graph but rose to 8 in the tree. There were only 56 nodes in the tree farther than 5 hops from the backbone. This matched our goal for the backbone since over 90 percent of the 6395 nodes are within 2 hops of a backbone node in the graph and within 3 hops of a backbone node in the tree. The average node is 1.61 hops away from the 21 ``backbone'' nodes in the full graph, and 1.96 hops away from those same 21 nodes in the computed tree.

Table 1: Clusters identified as Backbone by the algorithm. Peers are the number of connections the exemplar has to other exemplars also in this list.

=18pt Clstr #	Exemplar AS	Members	Out Degree	Peers	Depth
1	2914: Verio	150	235	13	5
2	1: BBNPlanet	171	284	12	4
3	701: Alternet	492	878	12	8
4	7018: AT&T	281	374	11	4
5	2828: Concentric	30	85	9	5
6	3549: Globalcenter	33	60	9	2
7	3561: Cable&Wireless	287	482	9	5
8	6453: Teleglobe	57	124	9	6
9	293: ESnet	41	112	8	5
10	1239: Sprint	407	645	8	5
11	2497: JNIC	45	82	8	6
12	3356: Level3	33	60	8	3
13	209: QWest	83	112	7	4
14	3300: Infonet-Europe	21	40	6	3
15	702: UUNet-Europe	56	80	5	5
16	1221: Telstra	27	61	5	1
17	1755: EBone	59	97	4	6
18	5378: INSNET	32	59	4	8
19	1849: PIPEX	26	47	3	5
20	2548: ICIX	158	189	2	3
21	5459: LINX	26	49	1	4

The resulting clustering contains 21 large subtrees, each headed by a particular AS. Table 1 shows the names of those Autonomous Systems. The list does not contain some of the AS's with high out-degree. Presumably, this is because they were dominated (at some small tolerance) by an AS that is on the list. Alternet had the largest number of immediate children at 492, a little over half of its out-degree (878) in the full graph.

The tree looks more like a long row of short bushes than a tall tree. There were 2515 AS's at the second level of the tree, making the average number of children per backbone node 120. The top three levels include a total of 4833 AS's that are within 2 hops of the backbone.