Crovella

Information about Crovella

Published on October 5, 2007

Author: Mertice

Source: authorstream.com

Content

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)

Related presentations


Other presentations created by Mertice

Lec11 Algae
01. 01. 2008
0 views

Lec11 Algae

carter200603
04. 10. 2007
0 views

carter200603

Jutta Immanen Poyry
09. 10. 2007
0 views

Jutta Immanen Poyry

symbiosis2
11. 10. 2007
0 views

symbiosis2

street children denver handouts
12. 10. 2007
0 views

street children denver handouts

252b lecture1
15. 10. 2007
0 views

252b lecture1

CROP Cosmic Ray History 2005
15. 10. 2007
0 views

CROP Cosmic Ray History 2005

BMI705 Lecture1
15. 10. 2007
0 views

BMI705 Lecture1

Lecture14 Lin
16. 10. 2007
0 views

Lecture14 Lin

Chapter31
22. 10. 2007
0 views

Chapter31

posters zwickel
22. 10. 2007
0 views

posters zwickel

Chain reactions
16. 10. 2007
0 views

Chain reactions

HistoryTalk4
23. 10. 2007
0 views

HistoryTalk4

73
24. 10. 2007
0 views

73

ps 22
09. 10. 2007
0 views

ps 22

Matthew Bick Panama Canal
25. 10. 2007
0 views

Matthew Bick Panama Canal

1 Introduction Y050823
02. 11. 2007
0 views

1 Introduction Y050823

TORNADO DRAGON
02. 10. 2007
0 views

TORNADO DRAGON

qcd3
27. 09. 2007
0 views

qcd3

T Maruyama
09. 10. 2007
0 views

T Maruyama

Cloud Formation
05. 01. 2008
0 views

Cloud Formation

2002interimresults
07. 01. 2008
0 views

2002interimresults

Islamic Empires 2
07. 01. 2008
0 views

Islamic Empires 2

Module54 Aggregate Project Plan
07. 01. 2008
0 views

Module54 Aggregate Project Plan

change prof
27. 09. 2007
0 views

change prof

InformationSystem
17. 10. 2007
0 views

InformationSystem

AFS explanation
04. 01. 2008
0 views

AFS explanation

dwyer SAC 2005 v2
23. 10. 2007
0 views

dwyer SAC 2005 v2

loi entreprise
23. 10. 2007
0 views

loi entreprise

sovietep
31. 12. 2007
0 views

sovietep

CROP Ionizing Detectors
13. 10. 2007
0 views

CROP Ionizing Detectors

RUSSIA Sergey Tikhonov
26. 11. 2007
0 views

RUSSIA Sergey Tikhonov

510 shortPRESEN
10. 10. 2007
0 views

510 shortPRESEN

leethao
19. 02. 2008
0 views

leethao

SelfInjury
20. 02. 2008
0 views

SelfInjury

MCOR 384 Presentation Okinawa
26. 02. 2008
0 views

MCOR 384 Presentation Okinawa

Lecture19 Uranus Neptune
15. 11. 2007
0 views

Lecture19 Uranus Neptune

Concrete
29. 02. 2008
0 views

Concrete

Chapter 1 Intro
04. 03. 2008
0 views

Chapter 1 Intro

Forum Casablanca
24. 10. 2007
0 views

Forum Casablanca

fulbright3
10. 03. 2008
0 views

fulbright3

Lecture One
13. 03. 2008
0 views

Lecture One

Objective1
20. 03. 2008
0 views

Objective1

Estrategia Nacional de Comercio
22. 10. 2007
0 views

Estrategia Nacional de Comercio

TRANS WP29 132 inf09e
25. 03. 2008
0 views

TRANS WP29 132 inf09e

prohibiteddogs
19. 11. 2007
0 views

prohibiteddogs

Ch 08
09. 04. 2008
0 views

Ch 08

phase out
11. 04. 2008
0 views

phase out

nossdav99pk
16. 04. 2008
0 views

nossdav99pk

qos3
17. 04. 2008
0 views

qos3

RACEM
23. 11. 2007
0 views

RACEM

StuMbr Benefits
18. 04. 2008
0 views

StuMbr Benefits

Tim SBS
22. 04. 2008
0 views

Tim SBS

Module12
28. 04. 2008
0 views

Module12

5 1
11. 10. 2007
0 views

5 1

Be an RT in NC
02. 05. 2008
0 views

Be an RT in NC

452 lecture7
02. 05. 2008
0 views

452 lecture7

5 10
30. 10. 2007
0 views

5 10

Ito
09. 10. 2007
0 views

Ito

sae intro
29. 12. 2007
0 views

sae intro

lecture001
29. 09. 2007
0 views

lecture001

UMDNJ Connell oct29
21. 10. 2007
0 views

UMDNJ Connell oct29

060619 OIF Foisel iPOP2006 01
09. 10. 2007
0 views

060619 OIF Foisel iPOP2006 01

For Every Season 2003
13. 11. 2007
0 views

For Every Season 2003

AMCARO Mineral Ltd
22. 10. 2007
0 views

AMCARO Mineral Ltd

casablanca 1
23. 10. 2007
0 views

casablanca 1

Mito Cinese
24. 10. 2007
0 views

Mito Cinese

CharetteAASL
03. 10. 2007
0 views

CharetteAASL

nfb social impact fr
11. 03. 2008
0 views

nfb social impact fr

Development aid
23. 12. 2007
0 views

Development aid

SFDVpresentation
30. 10. 2007
0 views

SFDVpresentation

ITEK Alvento
02. 11. 2007
0 views

ITEK Alvento

Paraphrasing New
15. 10. 2007
0 views

Paraphrasing New

yurtdisi sunu
23. 11. 2007
0 views

yurtdisi sunu

soldering progress
12. 10. 2007
0 views

soldering progress

Agustin Carstens
10. 04. 2008
0 views

Agustin Carstens

small mediumschools
08. 10. 2007
0 views

small mediumschools

Congres RMRA 07 Marrakech 2007
24. 10. 2007
0 views

Congres RMRA 07 Marrakech 2007

overview 2004 MF Meeting v2
29. 10. 2007
0 views

overview 2004 MF Meeting v2