Crovella

On The Marginal Utility of Network Topology Measurements : On The Marginal Utility of Network Topology Measurements Mark Crovella with Paul Barford, Azer Bestavros, and John Byers


Discovering Internet Topology : Discovering Internet Topology Typical goal: discover the router-level Internet graph (nodes and edges) Typical approach: merge a collection of node and edge lists


Using traceroute : Using traceroute Traceroute reports the IP path from A to B Ie, how IP paths are overlaid on the router graph


Traceroute studies : Traceroute studies Yield overlays of projections from S’s to D’s Sources: active, expensive Destinations: passive, cheap S S D D D D D


Motivating Questions : Motivating Questions How should we use traceroute and what can it discover? Physical topology (nodes, links)? IP routing topology? What’s a good way to organize a collection-of-traceroutes study? Many sources? Many destinations? How much is enough?


What might we expect? : What might we expect? Clique: each new Source (Dest) discovers a new path Star: each new Source (Dest) discovers only a small neighborhood Marginal Utility sheds light on this distinction D D D D D D D D D D Clique Star


Skitter to the Rescue : Skitter to the Rescue Two datasets from CAIDA Small dataset: May 2000 8 sources, 1277 destinations, 20K paths Sources in: New Zealand, Japan, Singapore, San Jose (2), Ottawa, London, Washington All sources traced to all destinations Large dataset: October 2000, 30 times bigger 12 sources, 313709 destinations, 600K paths No destination common to all sources, or vice versa


Interface Disambiguation : Interface Disambiguation Traceroutes report only on interfaces used Routers often have multiple interfaces But merging traceroutes requires matching routers Solution: probe each interface from some site X Routers are supposed to respond on the interface used for routing to X Results in set of (probe interface, response interface) pairs Each connected component is taken to be a router


Classifying Nodes : Classifying Nodes Core, border, stub, leaf Solely from traceroute information Leaf Border Core Stub


Classification depends on msmts : Classification depends on msmts Core Stub Border


Limitations : Limitations Interface disambiguation 13% of interfaces never responded Node classification Identifying a border node requires two paths to it Size Datasets may not be representative Unknown coverage of true network Diminishing returns may not signify good coverage


Diminishing Returns: Nodes : Diminishing Returns: Nodes


Diminishing Returns: Links : Diminishing Returns: Links


Large Dataset: Interfaces : Large Dataset: Interfaces


Large Dataset: Links : Large Dataset: Links


Diminishing returns by Classification : Diminishing returns by Classification Core Stub Border


What Does This Suggest? : What Does This Suggest? D D D D D D S S


Adding Destinations: Nodes : Adding Destinations: Nodes Slope is about 3


Adding Destinations: Links : Adding Destinations: Links Slope is about 4


Add Sources or Destinations? : Add Sources or Destinations? Isolines represent constant node discovery, varying S’s or D’s


Node Degree Distribution : Node Degree Distribution 8 Sources 1 Source


Node Degree Distribution: Tail : Node Degree Distribution: Tail 1 Source 8 Sources


Degree distribution convergence: RMSE : Degree distribution convergence: RMSE


Related Work : Related Work Pansiot & Grad ’98 First multi-traceroute study Many similarities, incl. interface disambiguation Chuang & Sirbu ’98 Phillips, Shenker & Tangmunarunkit ’99 single-source case, found sublinear growth of multicast tree with added destinations Govindan & Tangmunarunkit ’00 Extensive node discovery, overcoming limitations of traceroute Broido & Claffy ’01 Larger datasets; more detailed look at graph structure


Conclusions : Conclusions To discover all physical nodes, traceroute is inefficient Diminishing returns: many S’s and D’s needed Trading off S’s and D’s Adding destinations seems more cost-effective To discover how “typical” routes pass through network, traceroute is informative Routing core and feeders Much of routing core is visible from few S’s (given enough D’s)