Transcript A CIDR Prefix Stopping Rule for Topology Discovery

A CIDR Prefix Stopping Rule
for Topology Discovery
Benoit Donnet
joint work with Timur Friedman
Algotel 2005 – Presqu'Ile de Giens
Context
●
●
Network measurement
Internet topology discovery using distributed
traceroute monitors
–
●
IP interface level
Existing tools:
–
Skitter (CAIDA)
–
TTM (RIPE NCC)
–
AMP (NLANR)
–
DIMES (Tel Aviv U.)
Scaling Problem
●
●
●
More monitors means more load on
–
network resources
–
destinations
Classical approaches either
–
stay small (skitter, TTM, AMP)
–
trace slowly (DIMES)
Can we trace more efficiently?
Contributions
●
Efficient topology discovery algorithm
[Sigmetrics2005]
–
●
Doubletree
Communication overhead reduction
–
Stopping rule based on CIDR prefixes
Doubletree - Basics
●
Cooperative algorithm
●
Goal: avoiding paths already explored
●
Exploit tree-like structure of routes in the internet
–
from a monitor to a set of destinations
●
–
Backward probing (first suggested by Govindan et al.)
from a set of monitors to a destination
●
Forward probing and monitor coordination
Doubletree: Monitor-rooted tree
Doubletree: Destination-rooted tree
Doubletree: Probing scheme
●
●
Two probing schemes:
–
Backwards
–
Forwards
Stop sets = {(interface, root)}
–
Local Stop Set: B = {interface}
–
Global Stop Set: F = {(interface, destination)}
●
●
shared by monitors
Doubletree starts probing at some hop h from the
monitor
Limitation
●
Communication cost
–
Global stop set exchange needs too high network
resources
–
Up to 20.6MB for only 50,000 destinations
Destination based stopping rule
Solution
●
Communication cost reduction
–
Destination addresses aggregation through the use of
CIDR prefixes
–
Global stop set of {(interface, prefix_destination)}
Solution (2)
Results (1)
Results (2)
Results (3)
Conclusion
●
Improvements to Doubletree
–
●
Communication cost reduced
Future Work
–
Implementation (traceroute@home)
–
BGP-guided topology discovery