1、1,Internet Topology,COS 461: Computer Networks Spring 2006 (MW 1:30-2:50 in Friend 109)Jennifer Rexford Teaching Assistant: Mike Wawrzoniak http:/www.cs.princeton.edu/courses/archive/spring06/cos461/,2,Returning the Midterm Exam,Exam scoring break down Range: 70-100 Average: 89 Median: 92 See the co
2、urse Web site Exam Answer key,3,Goals of Todays Lecture,Internets two-tiered topology Autonomous Systems, and connections between them Routers, and the links between them AS-level topology Autonomous System (AS) numbers Business relationships between ASes Router-level topology Points of Presence (Po
3、Ps) Backbone and enterprise network topologies Inferring network topologies By measuring paths from many vantage points,4,Internet Routing Architecture,Divided into Autonomous Systems Distinct regions of administrative control Routers/links managed by a single “institution” Service provider, company
4、, university, Hierarchy of Autonomous Systems Large, tier-1 provider with a nationwide backbone Medium-sized regional provider with smaller backbone Small network run by a single company or university Interaction between Autonomous Systems Internal topology is not shared between ASes but, neighborin
5、g ASes interact to coordinate routing,5,Autonomous System Numbers,AS Numbers are 16 bit values.,Level 3: 1 MIT: 3 Harvard: 11 Yale: 29 Princeton: 88 AT&T: 7018, 6341, 5074, UUNET: 701, 702, 284, 12199, Sprint: 1239, 1240, 6211, 6242, ,Currently just over 20,000 in use.,6,AS Topology,Node: Autonomous
6、 System Edge: Two ASes that connect to each other,7,What is an Edge, Really?,Edge in the AS graph At least one connection between two ASes Some destinations reached from one AS via the other,AS 1,AS 2,d,Exchange Point,AS 1,AS 2,d,AS 3,8,Interdomain Paths,1,2,3,4,5,6,7,Client,Web server,Path: 6, 5, 4
7、, 3, 2, 1,9,Business Relationships,Neighboring ASes have business contracts How much traffic to carry Which destinations to reach How much money to pay Common business relationships Customer-provider E.g., Princeton is a customer of AT&T E.g., MIT is a customer of Level 3 Peer-peer E.g., Princeton i
8、s a peer of Patriot Media E.g., AT&T is a peer of Sprint,10,Customer-Provider Relationship,Customer needs to be reachable from everyone Provider tells all neighbors how to reach the customer Customer does not want to provide transit service Customer does not let its providers route through it,d,d,pr
9、ovider,customer,customer,provider,Traffic to the customer,Traffic from the customer,11,Peer-Peer Relationship,Peers exchange traffic between customers AS exports only customer routes to a peer AS exports a peers routes only to its customers Often the relationship is settlement-free (i.e., no $),peer
10、,peer,Traffic to/from the peer and its customers,d,12,Princeton Example,Internet: customer of AT&T and USLEC Research universities/labs: customer of Internet2 Local residences: peer with Patriot Media Local non-profits: provider for several non-profits,AT&T,USLEC,Internet2,Patriot,peer,13,AS Structu
11、re: Tier-1 Providers,Tier-1 provider Has no upstream provider of its own Typically has a national or international backbone UUNET, Sprint, AT&T, Level 3, Top of the Internet hierarchy of 12-20 ASes Full peer-peer connections between tier-1 providers,14,Efficient Early-Exit Routing,Diverse peering lo
12、cations Both costs, and middle Comparable capacity at all peering points Can handle even load Consistent routes Same destinations advertised at all points Same AS path length for a destination at all points,Customer A,Customer B,multiple peering points,Provider A,Provider B,Early-exit routing,15,AS
13、Structure: Other ASes,Tier-2 providers Provide transit service to downstream customers but, need at least one provider of their own Typically have national or regional scope E.g., Minnesota Regional Network Includes a few thousand of the ASes Stub ASes Do not provide transit service to others Connec
14、t to one or more upstream providers Includes vast majority (e.g., 85-90%) of the ASes,16,Characteristics of the AS Graph,AS graph structure High variability in node degree (“power law”) A few very highly-connected ASes Many ASes have only a few connections,1,10,100,1000,CCDF,1,0.1,0.01,0.001,AS degr
15、ee,All ASes have 1 or more neighbors,17,Characteristics of AS Paths,AS path may be longer than shortest AS path Router path may be longer than shortest path,s,d,3 AS hops, 7 router hops,2 AS hops, 8 router hops,18,Intra-AS Topology,Node: router Edge: link,19,Hub-and-Spoke Topology,Single hub node Co
16、mmon in enterprise networks Main location and satellite sites Simple design and trivial routing Problems Single point of failure Bandwidth limitations High delay between sites Costs to backhaul to hub,20,Princeton Example,Hub-and-spoke Four hub routers and many spokes Hub routers Outside world (e.g.
17、, AT&T, USLEC, ) Dorms Academic and administrative buildings Servers,21,Simple Alternatives to Hub-and-Spoke,Dual hub-and-spoke Higher reliability Higher cost Good building blockLevels of hierarchy Reduce backhaul cost Aggregate the bandwidth Shorter site-to-site delay,22,Backbone Networks,Backbone
18、networks Multiple Points-of-Presence (PoPs) Lots of communication between PoPs Accommodate traffic demands and limit delay,23,Abilene Internet2 Backbone,24,Points-of-Presence (PoPs),Inter-PoP links Long distances High bandwidth Intra-PoP links Short cables between racks or floors Aggregated bandwidt
19、h Links to other networks Wide range of media and bandwidth,Intra-PoP,Other networks,Inter-PoP,25,Where to Locate Nodes and Links,Placing Points-of-Presence (PoPs) Large population of potential customers Other providers or exchange points Cost and availability of real-estate Mostly in major metropol
20、itan areas Placing links between PoPs Already fiber in the ground Needed to limit propagation delay Needed to handle the traffic load,26,Customer Connecting to a Provider,Provider,Provider,1 access link,2 access links,Provider,2 access routers,Provider,2 access PoPs,27,Multi-Homing: Two or More Prov
21、iders,Motivations for multi-homing Extra reliability, survive single ISP failure Financial leverage through competition Better performance by selecting better path Gaming the 95th-percentile billing model,Provider 1,Provider 2,28,Shared Risks,Co-location facilities (“co-lo hotels”) Places ISPs meet
22、to connect to each other and co-locate their routers, and share space & power E.g., 32 Avenue of the Americas in NYC Shared links Fiber is sometimes leased by one institution to another Multiple fibers run through the same conduits and run through the same tunnels, bridges, etc. Difficult to identif
23、y and accounts for these risks Not visible in network-layer measurements E.g., traceroute does not tell you links in the same ditch,29,Learning the Internet Topology,Internet does not have any central management No public record of the AS-level topology No public record of the intra-AS topologies So
24、me public topologies are available Maps on public Web sites E.g., Abilene Internet2 backbone Otherwise, you have to infer the topology Measure many paths from many vantage points Extract the nodes and edges from the paths Infer the relationships between neighboring ASes,30,Inferring an Intra-AS Topo
25、logy,Run traceroute from many vantage points Learn the paths running through an AS Extract the hops within the AS of interest,1 169.229.62.12 169.229.59.2253 128.32.255.1694 128.32.0.2495 128.32.0.666 209.247.159.1097 209.247.9.1708 66.185.138.339 66.185.142.97 10 66.185.136.17 11 64.236.16.52,inr-d
26、aedalus-0.CS.Berkeley.EDU soda-cr-1-1-soda-br-6-2 vlan242.inr-202-doecev.Berkeley.EDU gigE6-0-0.inr-666-doecev.Berkeley.EDU qsv-juniper-ucb- POS1-0.hsipaccess1.SanJose1.L pos8-0.hsa2.Atlanta2.L pop2-atm-P0- Pop1-atl-P3- pop1-atl-P4- ,AOL,31,Challenges of Intra-AS Mapping,Firewalls at the network edg
27、e Cannot typically map inside another stub AS because the probe packets will be blocked by firewall So, typically used only to study service providers Identifying the hops within a particular AS Relies on addressing and DNS naming conventions Difficult to identify the boundaries between ASes Seeing
28、enough of the edges Need to measure from a large number of vantage points And, hope that the topology and routing doesnt change,32,Inferring the AS-Level Topology,Collect AS paths from many vantage points Learn a large number of AS paths Extract the nodes and the edges from the path Example: AS path
29、 “1 7018 88” implies Nodes: 1, 7018, and 88 Edges: (1, 7018) and (7018, 88) Ways to collect AS paths from many places Mapping traceroute data to the AS level Measurements of the interdomain routing protocol,33,Map Traceroute Hops to ASes,1 169.229.62.12 169.229.59.2253 128.32.255.1694 128.32.0.2495
30、128.32.0.666 209.247.159.1097 *8 64.159.1.469 209.247.9.170 10 66.185.138.33 11 * 12 66.185.136.17 13 64.236.16.52,Traceroute output: (hop number, IP),34,Challenges of Inter-AS Mapping,Mapping traceroute hops to ASes is hard Need an accurate registry of IP address ownership Whois data are notoriousl
31、y out of date Collecting diverse interdomain data is hard Public repositories like RouteViews and RIPE-RIS Covers hundreds to thousands of vantage points Especially hard to see peer-peer edges,AT&T,Sprint,Harvard,Harvard B-school,?,35,Inferring AS Relationships,Key idea The business relationships de
32、termine the routing policies The routing policies determine the paths that are chosen So, look at the chosen paths and infer the policies Example: AS path “1 7018 88” implies AS 7018 allows AS 1 to reach AS 88 AT&T allows Level 3 to reach Princeton Each “triple” tells something about transit service
33、 Collect and analyze AS path data Identify which ASes can transit through the other and which other ASes they are able to reach this way,36,Paths You Should Never See (“Invalid”),Customer-provider,Peer-peer,37,Challenges of Relationship Inference,Incomplete measurement data Hard to get a complete vi
34、ew of the AS graph Especially hard to see peer-peer edges low in hierarchy Real relationships are sometime more complex Peer is one part of the world, customer in another Other kinds of relationships (e.g., backup and sibling) Special relationships for certain destination prefixesStill, inference wo
35、rk has proven very useful Qualitative view of Internet topology and relationships,38,Conclusions,Two-tiered Internet topology AS-level topology Intra-AS topology Inferring network topologies By measuring paths from many vantage points Next class Vivek Pai guest lecture See reading assignment on the course Web site Mike Wawrzoniak talking about assignment #2 Start the assignment so you can ask questions Next week Intradomain and interdomain routing,
