Internet可看作由不同自治系统AS组成课件

1、Inferring Autonomous System Relationships in the InternetLixin Gao第1页，共41页。outlineintroductionAS relationshipsRouting PoliciesRouting Table Entry PatternsAlgorithm - Basic, Refined, FinalExperimental Result第2页，共41页。introductionInternet可看作由不同自治系统AS组成Each AS assigned unique ID（16位）A set of routers und

2、er a single technical administration, using an interior gateway protocol ( IGP) and common metrics to route packets within the AS and using an exterior gateway protocol to route packets to other ASs第3页，共41页。AS3847207.240.0.0/16AS1673140.222.0.0/16AS701192.67.95.0/24192.67.95.0/24 3847 701 i140.222.0

3、.0 3847 1673 i207.240.0.0/16 3847 iAS6201ECFDBABGP is a path-vector protocol that constructs paths by successively propagating updates between pairs of BGP speaking routers that establish BGP sessions. one key feature of BGP is that it allows each AS to choose its own policy in selecting routes and

4、propagating reachability information to others第4页，共41页。当两个AS交换路由表信息时，并不会交换所有的update,采取一定的策略Import polices:1.denying an update: loop avoidance rule2.permit an update and assign a local_preferenceLocal_pref: customerpeerproviderExport polices:1.select every B(u,d) of d to propagate or not(decided by A

5、S relationship)Local_pref-shortest as_path -smallest med - smallest intradomain routing cost - smallest as numberVU第5页，共41页。These routing policies are constrained by the contractual commercial agreements which can be classified into customer-provider, peering, mutual-transit and mutual-backup agreem

6、ent.For example: Customer pays provider for access to the Internet 。AS sets policy so that it does not provide transit services between its providers。Peers agree to exchange traffic between their respective customers free of charge.Mutual-transit allows a pair of AS to provide connectivity to the re

7、st of internet for each other.uwv第6页，共41页。connectivity does not imply reachabilityUnderstanding Internet structureUnderstanding why certain paths are used for trafficPlacement of Web serversWant to be close to most customer networks, Interdomain routing is not shortest-path routingSecurity policiesK

8、nowing which BGP routes look suspiciousHence there is a necessity to understand the relationships between ASes第7页，共41页。总结relationship- policy- routing tableAsking AS authorities for the Commercial Relationships they establish is unfeasible since they are even not willing to reveal their policies!So

9、this paper : relationship traffic第10页，共41页。Customer pays provider for access to the Internet 。Sibling provide connectivity to the rest of the Internet for each other.dcustomerproviderTraffic to the customeradvertisementstrafficdsiblingsiblingTraffic to the siblingtraffic第11页，共41页。dprovidercustomerTr

10、affic from the customerMulti-homingExtra reliability, survive single ISP failureFinancial leverage through competitionBetter performance by selecting better pathCustomer does not let its providers route through it第12页，共41页。Reduces upstream transit, increase end-to-end performanceMay be the only way

11、to connect your customers to some part of the Internet (“Tier 1”)第13页，共41页。 customer (provider, or peer) route : Let r.as_path = (u1,u2,un)，If (ui,ui+1) is a sibling-to-sibling edge for all ipolicy-routing table第15页，共41页。Selective Export RuleIn summary, AS selectively provides transit services for i

12、ts neighboring ASes. An AS sets up its export policy according to the following rule.第16页，共41页。ASs u and v have a peering relationship iff neither u transits traffic for v nor v transits traffic for u. AS u is a provider of AS v iff u transits traffic for v and v does not transit traffic for u.AS u

13、is a customer of AS v iff v transits traffic for u and v does not transit traffic for v ASs u and v have a sibling relationship iff both u transits traffic for v and v transits traffic for u.relationship - export routeAS u transits traffic for AS v: there is a best route r of u such that r is a prov

14、ider or peer route of u and export(v,u)r!= 。若此，则（u，v）是sibing or provider-to-customer edge.第17页，共41页。Theorem 3.1: If all ASs set their export policies according to the selective export rule,then the AS path in any BGP routing table entry is valley-free.Valley-Free: After traversing a provider-to-cust

15、omer or peer-to-peer edge, the AS path cannot traverse a customer-to-provider or peer-to-peer edge. Routing table entry patternstype-1type-2possibly missingpossibly missingpossibly missingpossibly missingpeer-to-peer第18页，共41页。Not Valley-Free1. 2.3. 4.peer-to-peerpeer-to-peerpeer-to-peer第19页，共41页。Rou

16、ting table entry patternsDownhill Path: A sequence of edges that are either provider-to-customer or sibling-to-sibling edges.Uphill Path: A sequence of edges that are either customer- to-provider or sibling-to-sibling edges.Uphill Top Provider: the last AS in its maximal uphill pathDownhill Top Prov

17、ider: the first AS in its maximal downhill pathTop Provider: is an AS that has the heighest degree among all Ass in the AS path第20页，共41页。Corollary 3.1: An AS path of a BGP routing table entry has one of the following patterns:1) an uphill path;2) a downhill path;3) an uphill path followed by a downh

18、ill path;4) an uphill path followed by a peer-to-peer edge;5) a peer-to-peer edge followed by a downhill path; or6) an uphill path followed by a peer-to-peer edge, which is followed by a downhill path.type-1type-2possibly missingpossibly missingpossibly missingpossibly missing第21页，共41页。introductionR

19、outing PoliciesAS Relationship and Routing Table Entry PatternsAlgorithm - Basic, Refined, FinalExperimental Result第22页，共41页。Basic Algorithm先只推断provider-customer and sibling relationships。基本思想AS的度往往和它的重要程度密切相关,寻找每条AS Path中度最高的点作为顶级Provider。由于valley-free性质，有：consecutive AS pairs on the left of the to

20、p provider are customer-to-provider or sibling-to-sibling edges and on the right are provider-to-customer or sibling-to-sibling edges possibly missingpossibly missing第23页，共41页。u2u1un-1unuj+1uj第24页，共41页。u2u1ubucudua第25页，共41页。u2u1un-1unuj+1ujubucuduaSibling-siblingu1,u2 = 1第26页，共41页。第27页，共41页。第28页，共41

21、页。Rifined AlgorithmIt is possible that some BGP speaking routers are misconfigured in the sense that they do not conform to the selective export rule.Example. ( u, w, v )Specifically, we use the heuristic that if no more than L routing table entries infer that AS u provides transit services for AS v

22、 and more than L routing table entries infer that AS v provides transit services for AS u, then we ignore the routing table entries that infer that AS u transits for AS v and we conclude that u is a customer of v, where L is a small constant.uwv第29页，共41页。第30页，共41页。Final Algorithm(peer推断)Phase 1: Use

23、 the algorithm to coarsely classify AS pairs into having provider-to-customer or sibling-to-sibling relationshipsPhase 2: Identify AS pairs that can not have a peer-to-peer relationshipPhase 3: Assign peer-to-peer relationships from rest of the connected AS pairs as long as the pair degrees do not d

24、iffer by more than R times第31页，共41页。According to Corollary 3.1, if an AS pair appear consecutively in an AS path and neither of the AS pair is the top provider then the AS pair do not have a peering relationship.a top provider can have a peering relationship with at most one of its neighbors in the

25、AS path.(since an AS pair that have a peering relationship are typically of comparable size, Top provider do not have a peering relationship with)We assume that the degrees of the two ASs that have a peering relationship do not differ by more than R times, where R is a constant.notpeeringnotpeeringn

26、otpeeringpeering第32页，共41页。第33页，共41页。introductionRouting PoliciesAS Relationship and Routing Table Entry PatternsAlgorithm - Basic, Refined, FinalExperimental Result第34页，共41页。Experimental ResultsUse BGP routing tables from Route Views router in Oregon第35页，共41页。Verification of inferred relationships b

27、y AT&T第36页，共41页。 第37页，共41页。第38页，共41页。Verifications by the WHOIS ServerSince the WHOIS lookup service supplies the name and address of the company that owns an ASconfirm that an AS pair has a sibling relationship :if the two ASs belong to the same company or two merging companies (such as AT&T and Cerfnet).if the ASs belong to two small c