Internet可看作由不同自治系統(tǒng)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可看作由不同自治系統(tǒng)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頁。當(dāng)兩個(gè)AS交換路由表信息時(shí)，并不會交換所有的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頁?？偨Y(jié)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的度往往和它的重要程度密切相關(guān),尋找每條AS Path中度最高的點(diǎn)作為頂級Provider。由于valley-free性質(zhì)，有：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