Abstract:

The interdomain routing system based on BGP is the key routing infrastructure of the Internet. Understanding the Internet AS topology structure and the connectivity properties gives important implications on enhancing the security, robustness and performance of the Internet. The AS business relationship, as the fundamental model of AS topology, gives rise to the difference between AS graphs and general directed/undirected graphs: the AS hierarchical structure and the valleyfree property of AS paths. This paper proposes an algorithm for the hierarchical characterization based on the fundamental model of AS commercial relationships. Additionally, we give a further study on the AS connectivity, and validate the Tier1 full mesh AS topology. Finally, we propose a method on how to measure the connectivity for individual ASes.

Key words: interdomain routing;autonomous system;commercial relationship;hierarchy;connectivity