1Lecture 15: MeasurementStudies on Internet RoutingLakshminarayanan SubramanianCS 268 classMarch 10th, [email protected] 2Internet RoutingInternet organized as a two level hierarchyFirst level – autonomous systems (AS’s)- AS – region of network under a single administrative domainAS’s run an intra-domain routing protocols- Distance Vector, e.g., RIP- Link State, e.g., OSPFBetween AS’s runs inter-domain routing protocols, e.g., Border Gateway Routing (BGP)- De facto standard today, BGP-4 [email protected] 3ExampleAS-1AS-2AS-3Interior routerBGP [email protected] 4Intra-domain Routing ProtocolsBased on unreliable datagram deliveryDistance vector- Routing Information Protocol (RIP), based on Bellman-Ford- Each router periodically exchange reachability information to its neighbors- Minimal communication overhead, but it takes long to converge, i.e., in proportion to the maximum path lengthLink state- Open Shortest Path First Protocol (OSPF), based on Dijkstra- Each router periodically floods immediate reachabilityinformation to other routers- Fast convergence, but high communication and computation [email protected] 5Inter-domain RoutingUse TCPBorder Gateway Protocol (BGP), based on Bellman-Ford path vectorAS’s exchange reachability information through their BGP routers, only when routes changeBGP routing information – a sequence of AS’s indicating the path traversed by a route; next hopGeneral operations of a BGP router:- Learns multiple paths- Picks best path according to its AS policies- Install best pick in IP forwarding [email protected] 6End-to-End Routing Behavior in the Internet [Paxson ’95]Idea: use end-to-end measurements to determine- Route pathologies - Route stability - Route [email protected] 7MethodologyRun Network Probes Daemon (NPD) on a large number of Internet sites Courtesy of Vern [email protected] 8MethodologyEach NPD site periodically measure the route to another NPD site, by using Two sets of experimentsD1– measure each virtual path between two NPD’s with a mean interval of 1-2 days, Nov-Dec 1994D2– measure each virtual path using a bimodal distribution inter-measurement interval, Nov-Dec 1995- 60% with mean of 2 hours- 40% with mean of 2.75 daysMeasurements in D2were paired- Measure AB and then B[email protected] 9Traceroute Exampletraceroute to whistler.cmcl.cs.cmu.edu (128.2.181.87), 30 hops max, 38 byte packets 1 snr45 (128.32.45.1) 0.570 ms 0.434 ms 0.415 ms 2 gig10-cnr1.EECS.Berkeley.EDU (169.229.3.65) 0.506 ms 0.513 ms 0.434 ms 3 gigE5-0-0.inr-210-cory.Berkeley.EDU (169.229.1.45) 0.726 ms 0.570 ms 0.553 ms 4 fast1-0-0.inr-001-eva.Berkeley.EDU (128.32.0.1) 1.357 ms 0.998 ms 1.020 ms 5 pos0-0.inr-000-eva.Berkeley.EDU (128.32.0.65) 1.459 ms 2.371 ms 1.600 ms 6 pos3-0.c2-berk-gsr.Berkeley.EDU (128.32.0.90) 3.103 ms 1.406 ms 1.575 ms 7 SUNV--BERK.POS.calren2.net (198.32.249.14) 3.005 ms 3.085 ms 2.407 ms 8 abilene--QSV.POS.calren2.net (198.32.249.62) 6.112 ms 6.834 ms 6.218 ms 9 dnvr-scrm.abilene.ucaid.edu (198.32.8.2) 34.213 ms 27.145 ms 27.368 ms10 kscy-dnvr.abilene.ucaid.edu (198.32.8.14) 38.403 ms 38.121 ms 38.514 ms11 ipls-kscy.abilene.ucaid.edu (198.32.8.6) 47.855 ms 47.558 ms 47.649 ms12 clev-ipls.abilene.ucaid.edu (198.32.8.26) 54.037 ms 53.849 ms 53.492 ms13 abilene.psc.net (192.88.115.122) 57.109 ms 56.706 ms 57.343 ms14 cmu.psc.net (198.32.224.36) 58.794 ms 58.237 ms 58.491 ms15 CS-VLAN255.GW.CMU.NET (128.2.255.209) 58.072 ms 58.496 ms 57.747 ms16 WHISTLER.CMCL.CS.CMU.EDU (128.2.181.87) 57.715 ms 57.932 ms 57.557 mssky.cs.berkeley.edu[email protected] 10MethodologyLinks traversed during D1 andD2Courtesy of Vern [email protected] 11MethodologyExponential sampling- Unbiased sampling – measures instantaneous signal with equal probability- PASTA principle – Poisson Arrivals See Time AveragesIs data representative?- Argue that sampled AS’s are on half of the Internet routesConfidence intervals for probability that an event [email protected] 12LimitationsJust a small subset of Internet pathsJust two points at a timeDifficult to say why something happened5%-8% of time couldn’t connect to NPD’sIntroduces bias toward underestimation of the prevalence of network [email protected] 13Routing PathologiesPersistent routing loopsTemporary routing loopsErroneous routingConnectivity altered mid-streamTemporary outages (> 30 sec)[email protected] 14Routing Loops & Erroneous RoutingPersistent routing loops (10 in D1 and 50 inD2)- Several hours long (e.g., > 10 hours)- Largest: 5 routers- All loops intra-domainTransient routing loops (2 in D1 and 24 in D2)- Several seconds- Usually occur after outages Erroneous routing (one in D1)- A route UKUSA goes through IsraelQuestion: Why do routing loops occur even [email protected] 15Route ChangesConnectivity change in mid-stream (10 in D1 and 155 in D2)- Route changes during measurements- Recovering bimodal: (1) 100’s msec to seconds; (2) order of minutesRoute fluttering- Rapid route [email protected] 16Example of Route FlutteringCourtesy of Vern [email protected] 17Problems with FlutteringPath properties difficult to predict- This confuses RTT estimation in TCP, may trigger false retransmission timeoutsPacket reordering- TCP receiver generates DUPACK’s, may trigger spurious fast retransmitsThese problems are bad only for a large scale flutter; for localized flutter is usually [email protected] 18Infrastructure FailuresNPD’s unreachable due to many hops (6 in D2)- Unreachable more than 30 hops- Path length not necessary correlated with distance• 1500 km end-to-end route of 3 hops• 3 km (MIT – Harvard) end-to-end route of 11 hops• Question: Does 3 hops actually mean 3 physical links?Temporary outages- Multiple probes lost. Most likely due to:• Heavy congestions lasting 10’s of seconds • Temporary lost of [email protected] 19Distribution of Long Outages (> 30 sec)Geometric distributionCourtesy of Vern [email protected] 20Pathology [email protected]
View Full Document
Unlocking...