Inferring AS Relationships Beyond Counting Edges

Abstract

Routing in the Internet is strongly shaped by the business relationships between administrative domains (Autonomous Systems, AS). In this paper we propose new techniques to classify these relationships. Inspired by Lixin Gao’s seminal work on valley-free paths, we explore several ways to measure the importance of an AS which go beyond the original degree-ranking. In addition we study what information can be gathered by parsing the Routing Registry databases. Furthermore we undertake a thorough analysis and experimental comparison of all the proposed approaches known to date. Not surprisingly, the various methods all reveal different views of the business relations. In fact, by using the different measures or even a combination of them, one can tune the ranking of a given AS by a wide margin.