text: The type of business relationships between the Internet autonomous systems (AS) determines the BGP inter-domain routing. Previous works on inferring AS relationships relied on the connectivity information between ASes. In this paper we infer AS relationships by analysing the routing polices of ASes encoded in the BGP attributes Communities and the Locpref. We accumulate BGP data from RouteViews, RIPE RIS and the public Route Servers in August 2010 and February 2011. Based on the routing policies extracted from data of the two BGP attributes, we obtain AS relationships for 39 links in our data, which include all links among the Tier-1 ASes and most links between Tier-1 and Tier-2 ASes. We also reveal a number of special AS relationships, namely the hybrid relationship, the partial-transit relationship, the indirect peering relationship and the backup links. These special relationships are relevant to a better understanding of the Internet routing. Our work provides a profound methodological progress for inferring the AS relationships.
  @cite_18: The commercial contractual relationship among autonomous systems (ASs) is important for understanding the reachability and traffic flow in the Internet. Several heuristic algorithms have been proposed for inferring AS relationships by extracting information from border gateway protocol (BGP) routing tables. However, there is no evaluation of the AS relationships inferred from existing algorithms. In this paper, we present the methodology for obtaining partial AS relationships, and use them to evaluate these algorithms. Our result shows that although existing algorithms achieve good overall accuracy, the accuracy on the peer-to-peer relationships is quite poor. Furthermore, we propose an algorithm for inferring AS relationships by taking advantage of this partial information. We show that our proposed algorithm outperforms existing algorithms for inferring peer-to-peer relationships by 1.8 spl sim 3.8 times in accuracy. In addition, the overall accuracy of our algorithm is higher than that of existing algorithms.
  @cite_23: The Internet consists of rapidly increasing number of hosts interconnected by constantly evolving networks of links and routers. Interdomain routing in the Internet is coordinated by the Border Gateway Protocol (BGP). The BGP allows each autonomous system (AS) to choose its own administrative policy in selecting routes and propagating reachability information to others. These routing policies are constrained by the contractual commercial agreements between administrative domains. For example, an AS sets its policy so that it does not provide transit services between its providers. Such policies imply that AS relationships are an important aspect of the Internet structure. We propose an augmented AS graph representation that classifies AS relationships into customer-provider, peering, and sibling relationships. We classify the types of routes that can appear in BGP routing tables based on the relationships between the ASs in the path and present heuristic algorithms that infer AS relationships from BGP routing tables. The algorithms are tested on publicly available BGP routing tables. We verify our inference results with AT&T internal information on its relationship with neighboring ASs. As much as 99.1 of our inference results are confirmed by the AT&T internal information. We also verify our inferred sibling relationships with the information acquired from the WHOIS lookup service. More than half of our inferred sibling-to-sibling relationships are confirmed by the WHOIS lookup service. To the best of our knowledge, there has been no publicly available information about AS relationships and this is the first attempt in understanding and inferring AS relationships in the Internet. We show evidence that some routing table entries stem from router misconfigurations.
summary: Based on the valley-free property, Gao @cite_23 proposed a relationship inference heuristic that classifies the AS links according to their connectivity degree. Gao's algorithm was refined by a follow-up work @cite_18 (PTE) which introduced the use of Partial relationship Information (PI) as a starting point for the inference process.