Conclusions

In this paper we have described methods for creating AS clusters based on BGP routing data. The algorithm for creating a tree of AS numbers objectively discovers the Autonomous Systems that form a highly interconnected backbone for the Internet. The resulting tree slightly overstates the average number of hops from any point in the Internet to a common backbone, but is close enough to allow us to study cache placement.

We have also presented an optimal method for placing caches in the AS hierarchy generated by our clustering method. We compared it to two incremental techniques and found that greedy placement of caches worked nearly as well as the sophisticated, optimal technique when the number of caches was small or large. In the middle, however, the optimal method reduces total traffic by 50% using 20% fewer caches than a greedy algorithm.