Acyclic type of relationships between autonomous systems

Abstract — The Internet connectivity in the Autonomous Sys-tem (AS) level reflects the commercial relationship between ASes. A connection between two ASes could be of type customer-provider when one AS is a provider of the other AS, or of type peer-peer, if they are peering ASes. This commercial relationship induces a global hierarchical structure which is a key ingredient in the ability to understand the topological structure of the AS connectivity graph. Unfortunately, it is very difficult to collect data regarding the actual type of the relationships between ASes, and in general this information is not part of the collected AS connectivity data. The Type of Relationship (ToR) problem attempts to address this shortcoming, by inferring the type of relationship between connected ASes based on their routing policies. However, the approaches presented so far are local in nature and do not capture the global hierarchical structure