Transcript Deschenes
Measuring ISP Toplogies with Rocketfuel Neil Spring, Ratul Mahajan, and David Wetherall Presented By: David Deschenes March 25, 2003 Contributions • Presents novel techniques for generating high quality ISP maps while using as few network measurements as possible • Examines several properties of generated maps that are likely to be of use in creating synthetic Internet maps Motivation • Brute-force approaches to Internet mapping produce excessive loads and can take extraordinary amounts of time • Synthetic Internet maps of high quality are useful to researchers, especially with respect to the execution of realistic simulations Terminology • • • • An ISP network consists of multiple POPs Each POP is a collection of routers POPs are connected by backbone links Backbone routers are attached to backbone links • Access routers intermediate between the ISP backbone and routers on neighboring networks Approach • Omit measurements likely to be redundant – Expected BGP routing paths facilitate selection – Trades accuracy for efficiency • Improve alias resolution – Make use of IP identifier, rate-limiting and TTL values • Annotate maps – Hints about geographical location and role may be extracted from DNS names Directed Probing • Selects traceroute measurements that will transit the ISP in question • Measurement Types – Dependent Prefix – Insider – Up/Down Sample BGP Routing Table Destination 1.2.3.0/24 Paths 13 4 2 5 6 9 10 5 11 7 5 4.5.0.0/16 378 78 Path Reductions Ingress Egress Next-hop AS Alias Resolution • Send a series of probe packets to potential matches, and test the following data – Packet TTLs – ICMP Rate-limiting – IP Identifiers • The use of IP Identifiers proved most valuable, while the other data provided greater levels of confidence in IP Identifier matches Rocketfuel BGP Table Egress Discovery Tasklist Generation Alias Resolution Execution Path Reductions ISP Map Impact of Reductions • Direct probing reduced number of traces to 18% depending on the ISP to be mapped • Ingress reduction kept only 12% of those traces selected by direct probing • Egress reduction kept only 18% of those traces selected by direct probing • Next-hop AS reduction kept only 5% of those selected by direct probing • Overall, after reductions, less than 0.1% of the traces required by a brute-force technique were executed by Rocketfuel Accuracy of Generated Maps • Found from 64% to 96% of backbone routers depending on the ISP to be mapped (See Table 2) • BGP adjacencies somewhat consistent with those provided by RouteViews (See Figure 9) • Significant disparity between Rocketfuel and Skitter with regard to adjacencies (See Figure 10) Questions?