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)