Network Topology MeasurementOutlineHeuristics for Internet Map DiscoveryWhy do we need the topology?On-going effortsFundamental: tracerouteSlide 7Fundamental: Tree => mapAddress scan spaceSome resultsFor example: degree distributionMeasuring ISP Topologies with RocketfuelISP network infrastructureISP topology measurementSlide 15Focusing on one ISP – Directed probingSlide 17Path/Query reductionImpacts of directed probingImpacts of ingress reductionImpacts of egress reductionImpacts of next-hop reductionPOP sizes analysisPower LawRouter degree distributionPeering structureDifficulties in topology discoveryPOP hierarchyBackbone topologyAlias ProblemAlias: is it a big deal?Alias resolutionCompleteness validationIn Search of Path Diversity in ISP NetworksReal metric instead of counting linksReal topology speaksTake a closer lookInaccuracy introduced during probingInaccuracy from processing probed linksQuestions?1Network Topology MeasurementYang ChenCS 88032Outline•Big Picture•ISP Topology Measurement•Statistical Results•Problems & Solutions3Heuristics for Internet Map DiscoveryR. Govindan and H. TangmunarunkitINFOCOM 20004Why do we need the topology?•Understand the macroscopic properties of the Internet physical structure•Network management•Topology-aware algorithms•Simulation and topology generation tools5On-going efforts•CAIDA Skitter•Router View6Fundamental: tracerouteProber sends packets with successively increased TTL.A router responds with ICMP time exceeded when the probe is with TTL=17Fundamental: tracerouteGeographic info can help on building up the topology. * Data from http://www.linkwan.com/vr/8Fundamental: Tree => map1)Source routing2)Multiple Vantage points9Address scan space•BGP tables•Route Table•Database•Informed Random Address Probing–A response from some IP address is considered as a sign that some prefix P of A must contain addressable nodes;–If P is an addressable prefix, the neighboring prefixes of P are also considered as possibly addressable. (128.8/16 and 128.10/16 are neighbors of 128.9/16)10Some results•150,000 interfaces and nearly 200,000 links•Findings related to source route–Simulation demonstrated that In relatively sparse random networks, a few source route capable nodes (< 5%) are sufficient to discover 90% of the links. In fact, there are 8% routers support source route.–Source route discovered links do not skew the qualitative conclusion on the network statistics.11For example: degree distribution Similar observation on hop-pair distribution12Measuring ISP Topologies with RocketfuelN.Spring, R. Mahajan and D. WetherallACM Sigcomm 200213ISP network infrastructureAccess RouterAccess RouterBackbone RouterBackbone Link14ISP topology measurement•An old story: the blinds and the elephantISPTraceroute15ISP topology measurementTraceroute Server16Focusing on one ISP – Directed probingNetwork Next Hop M/LP/Weight Path * 192.9.9.0 204.212.44.128 0 234 266 237 3561 701 90 i * 205.238.48.3 0 2914 1 90 i * 144.228.240.93 0 1239 701 90 i * 204.70.4.89 0 3561 1 90 i * 194.68.130.254 0 5459 5413 1 90 i *> 134.24.127.3 0 1740 701 90 i * 202.232.1.8 0 2497 701 90 i * 158.43.133.48 0 1849 702 701 90 i * 131.103.20.49 0 1225 2548 1 90 iblackrose.org (Ann Arbor) 204.212.44.128 through AS234 Verio (MAE-WEST) 205.238.48.3 through AS2914 Sprint (Stockton) 144.228.240.93 through AS1239 MCI (San Francisco) 204.70.4.89 through AS3561 LINX (London) 194.68.130.254 through AS5459 CERFnet (San Diego) 134.24.127.3 through AS1740 IIJ (Japan) 202.232.1.8 through AS2497 PIPEX (London) 158.43.133.48 through AS1849 IAGnet (Chicago) 131.103.20.49 through AS1225* BGP table source: RouteView project17Focusing on one ISP – Directed probing•Traceroutes to dependent prefixes: All traceroutes to these prefixes from any vantage point should transit the ISP. Dependent prefixes can be readily identified from the BGP table. All AS-paths for the prefix would contain the number of the AS being mapped.•Traceroutes from insiders: We call a traceroute server located in a dependent prefix an insider. Traceroutes from insiders to any prefix should transit the ISP.•Traceroutes that are likely to transit the ISP based on some AS-path are called up/down traces.18Path/Query reductionShare Ingress Share egressSame next-hop AS number19Impacts of directed probing1) Fraction of useful but pruned traces from 0.1 to 7%2) Unnecessary traces around 6% over all the ISPs*Comparison based on Skitter data20Impacts of ingress reductionOverall, ingress reduction keeps only 12% of the traces chosen by directed probing.The number of vantage points that share an ingress by rank21Impacts of egress reductionThe number of dependent prefixes that share an egress by rankOverall, egress reduction keeps only 18% of the Dependent prefix traceschosen by directed probing.22Impacts of next-hop reductionOverall, Next-hop AS reduction Reduces the number of traces to 5% of those chosen by directed probing.23POP sizes analysis24Power Law•Complementary cumulative distribution function (CCDF) P(X>x)•Pareto Distribution•Power LawkxxxXPmin)(kxxXP )()ln()ln( xCy 25Router degree distribution26Peering structure27Difficulties in topology discovery•Shared media•Backup links•Router Identification and annotation•Alias resolution•Completeness ValidationCurrently, none of them is completely solved!28POP hierarchyNaming convention, DNS information and neighbor inferring29Backbone topologyAT&TLevel 330Alias ProblemOR31Alias: is it a big deal?32Alias resolution•Send a packet with unreachable port to certain interfaces which are possible alias. The corresponding ICMP port unreachable response will contain the source address.•IP identifier33Completeness validation•Comparison with Router Views•Comparison with Skitter •IP address space–Search prefixes of ISP’s address space for additional IP addresses•Validation with ISPs–Is “Good” enough?34In Search of Path Diversity in ISP NetworksP. Teixeira, K. Marzullo, S. Savage and G. M.