IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 9, NO. 6, DECEMBER 2001 733On Inferring Autonomous System Relationshipsin the InternetLixin Gao, Member, IEEEAbstract—The Internet consists of rapidly increasing number ofhosts interconnected by constantly evolving networks of links androuters. Interdomain routing in the Internet is coordinated by theBorder Gateway Protocol (BGP). BGP allows each autonomoussystem (AS) to choose its own administrative policy in selectingroutes and propagating reachability information to others. Theserouting policies are constrained by the contractual commercialagreements between administrative domains. For example, anAS sets its policy so that it does not provide transit servicesbetween its providers. Such policies imply that AS relationshipsare an important aspect of Internet structure. We propose anaugmented AS graph representation that classifies AS relation-ships into customer–provider, peering, and sibling relationships.We classify the types of routes that can appear in BGP routingtables based on the relationships between the ASs in the path andpresent heuristic algorithms that infer AS relationships from BGProuting tables. The algorithms are tested on publicly availableBGP routing tables. We verify our inference results with AT&Tinternal information on its relationship with neighboring ASs.As much as 99.1% of our inference results are confirmed by theAT&T internal information. We also verify our inferred siblingrelationships with the information acquired from the WHOISlookup service. More than half of our inferred sibling-to-siblingrelationships are confirmed by the WHOIS lookup service. Tothe best of our knowledge, there has been no publicly availableinformation about AS relationships and this is the first attempt inunderstanding and inferring AS relationships in the Internet. Weshow evidence that some routing table entries stem from routermisconfigurations.Index Terms—Border Gateway Protocol (BGP), Internet, proto-cols, routing.I. INTRODUCTIONTHE INTERNET has experienced a tremendous growth inits size and complexity since its commercialization. TheInternet connects thousands of autonomous systems (ASs) oper-ated by many different administrative domains such as Internetservice providers (ISPs), companies and universities. Since twoISPs might merge into one and each administrative domain canpossess several ASs, an administrative domain can operate oneor several ASs. Routing within an AS is controlled by intrado-main routing protocols such as static routing, OSPF, IS-IS, andManuscript received September 5, 2000; revised November 21, 2000; rec-ommended by IEEE/ACM TRANSACTIONS ON NETWORKING Editor V. Paxson.The author was supported in part by the National Science Foundation underGrants ANI-9977555 and ANI-0085848, and by an NSF CAREER Award GrantANI-9875513.The author is with the Department of Electrical and Computer Engi-neering, University of Massachusetts, Amherst, MA 01003 USA (e-mail:[email protected]).Publisher Item Identifier S 1063-6692(01)10548-0.RIP. A pair of ASs interconnect via dedicated links and/or publicnetwork access points, and routing between ASs is determinedby the interdomain routing protocol such as Border GatewayProtocol (BGP). One key distinct feature of the interdomainrouting protocol is that it allows each AS to choose its own ad-ministrative policy in selecting the best route, and announcingand accepting routes. One of the most important factors in deter-mining routing policies is the commercial contractual relation-ships between administrative domains.The commercial agreements between pairs of administrativedomains can be classified into customer–provider, peering, mu-tual-transit, and mutual-backup agreements [2], [3]. A customerpays its provider for connectivity to the rest of the Internet.Therefore, a provider does transit traffic for its customers.However, a customer does not transit traffic between two of itsproviders. A pair of peers agree to exchange traffic betweentheir respective customers free of charge. A mutual-transitagreement allows a pair of administrative domains to provideconnectivity to the rest of the Internet for each other. Thismutual-transit relationship is typically between two adminis-trative domains such as small ISPs who are located close toeach other and who cannot afford additional Internet servicesfor better connectivity. A pair of administrative domains mayalso provide backup connectivity to the Internet for each otherin the event that one administrative domain’s connection to itsprovider fails.These contractual commercial agreements between adminis-trative domains play a crucial role in shaping the structure ofthe Internet and the end-to-end performance characteristics. Pre-vious work on the Internet topology has been focused on theinterconnection structure at either AS or router level [4]–[9].Since routing between ASs is controlled by BGP, a policy-basedrouting protocol, connectivity does not imply reachability. Forexample, national ISPs A and B are connected to their customer,a regional ISP, C, respectively. Although ISPs A and B are con-nected through ISP C, ISP A cannot reach ISP B via ISP C,since C as a customer does not provide transit services betweenits providers. Even if ISPs A and B can reach each other viaother ISPs, the end-to-end performance characteristics betweenA and B cannot be inferred from that of between A and C andbetween C and B. For example, the delay between A and B isindependent of the total delay between A and C and between Cand B. This has been observed by several measurement studies[10], [11]. Therefore, a global picture of AS relationships is animportant aspect of the Internet structure.We propose an augmented AS graph representation to cap-ture AS relationships. We classify the relationship between apair of interconnected ASs into customer–provider, peering, and1063–6692/01$10.00 © 2001 IEEE734 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 9, NO. 6, DECEMBER 2001sibling relationships. There is no publicly available informa-tion about inter-AS relationships. ISPs do not register their re-lationships to the Internet registries. Internet registries such asARIN [1] do provide information such as who administrates anAS. However, the information can be out of date and does notimply anything about how ASs relate to each other. Contrac-tual agreements between ISPs are proprietary and companiesare unwilling to reveal even the names of their ISPs [12].
View Full Document
Unlocking...