Transcript ppt

Heuristics for Internet Map
Discovery
R. Govindan, H. Tangmunarunkit
Presented by Zach Schneirov
Mercator
• Infers a topological Internet map
through
– Hop-limited probes
– Informed random address probing
– Resolution of aliases
Why build router-level maps?
• It is the first step in understanding the
large-scale physical structure of the
Internet
• It can be used in input simulations
• It can directly determine network scaling
limits
What exactly is an Internet map?
• A map in this case is a graph with nodes
as routers and links as indications of
adjacency, where adjacent routers have
one IP hop between them
Previous work
• All previous maps have built router adjacencies
using probes from a single node
• Obtained destination addresses from BGP routing
tables and generated addresses with random
prefixes
• Used routing activity between autonomous
systems, with links representing inter-ISP peering
• Used router-level support, such as SNMP and
multicast IGMP queries to find neighbor lists
Goals
• Map the Internet from any single
arbitrary node
• Use only hop-limited probes (implies an
absence of a database)
• Map must be complete
• Not impose significant overhead
• At least as fast as previous methods
Methods
• Informed random address probing
• Source-routed path probing
• Alias resolution
Informed random address
probing
• Targets of probes depend on previous
probes and IP block allocation policies
• Two ways to generate an address:
– Guess an IP addressable prefix based on
prefix of source address in responses to
probes
– Assume that other subnets at the same prefix
level are neighbors
IRAP Procedure
• Start with an IP prefix (taken from the host
machine by default)
• Repeating these two methods will gradually
build a population of IP address prefixes
– 1st method ensures that addressable prefixes are
explored first
– 2nd ensures that all possible addresses are explored
IRAP Procedure (continued)
• Terminates when one of the following
occurs:
– Subsequent ICMP-time-exceeded packets are
not received
– Mercator detects a loop
– Chosen destination address is reached
• Sequence of routers is inserted into the map
of links:
•
(R1, R2, R3) becomes R1->R2, R2->R3
Reducing Overhead for IRAP
• Avoids probing known routers multiple
times by adjusting the TTL to skip the
furthest known router in the map
Speeding up map discovery
• Uses lottery scheduling algorithm to
select prefixes
– Each prefix is assigned a lottery tick
– Probability of that prefix’s ticket “winning”
is proportional to the faction of successful
probes to the prefix
• Results in a bias towards denselyaddressed prefixes
Source-routing
• Cross-links can be discovered by sending
probes in one direction instead of sending
them radially
That is, send probes to alreadydiscovered routers
• This essentially allows Mercator to send
probes from multiple locations by proxy
Determining if router can do
source-routing
• Send UDP datagrams to a random high
port
• See if router sends back an ICMP-portunreachable message
Alias resolution
• Problem: a single host can have multiple IP
aliases. Probes technically discover router
interfaces--not routers themselves
• Solution: paths from Mercator to destination
host can overlap in the cases of:
– Policy differences
– Primary and backup paths
– Source-routed paths probing from different
perspectives
Alias resolution procedure
• Send UDP packets to non-existent ports on a
router
• ICMP port-unreachable message will contain
the outgoing interface for the return route
• If this is different than the original
destination interface, then these interfaces are
aliases for the same router
• Alias probes can also be source-routed to
deal with incomplete backbone routing tables
Mercator Software Design
• Implemented from scratch for greater
experimental flexibility
• Implemented with Libserv
– Allows non-blocking network and file system
access
– So simultaneous independent path probes,
source-routed path probes, and alias probes are
possible
• Periodically saves map for reverting to and
resumption from previous states
Theoretical Results
• How well do these methods satisfy the
goals?
– Cannot guarantee discovery of all aliases due to
finite perspectives
– Cannot find shared media
– Map is not instantaneous
– Unable to find adjacencies between physical
neighbors who aren’t on speaking terms
More results-Map is incomplete
• Can’t discover details of networks that do
not route traffic to other autonomous
systems
• It is however complete with respect to the
portion of the Internet over which
packets tend to travel between hosts
Real world results
• Ran Mercator on a Linux PC with 15
simultaneous probes
• Found 150,000 interfaces and 200,000 links
in 3 weeks
• Could only discover 20,000 router
interfaces due to unroutable addresses
• Source-routed paths discovered only 3,000
paths
Internet map validation
• Compared subgraphs against published ISP
maps using DNS names of routers
• All but one link was discovered for an ISP
and an educational/research network
• More complexly-meshed ISPs have not
been tested
• Will improve with more widespread use of
ICMP-time-exceeded messages and sourcerouting
Measuring ISP Topologies with
Rocketfuel
N. Spring, R. Mahajan, D. Wetherall
Rocketfuel
• Directly measure router-level ISP
topologies more efficiently than bruteforce
• Uses BGP routing tables
• Eliminates redundant measurement
• Better alias resolution
• DNS for identifying ISPs
Goals
• Infer high quality ISP topological maps
• Use as few measurements as possible
• An ISP will consist of multiple POPs
(point-of-presence) connected by
backbones
Methods
• Uses only traceroute for measuring paths
• Merges traceroute paths from multiple
sources to multiple destinations
• Choose traceroutes that contribute the most
information (directed probing and path
reductions)
• Alias resolution through “personality”
• Identifying routers through DNS
Directed probing
• Use BGP routing information to choose
only the traceroutes likely to transit the
target ISP
• Traceroutes will transit the ISP if they are:
– Sent to dependent prefixes (sent to a destination
within the ISP)
– Sent from within a dependent prefix (traceroute
server is within the ISP)
– Either may be true depending on several
different destination prefixes in BGP table
Expected problems with directed
probing
• Incomplete routing tables or nondeterminism in the routing tables will
cause:
– False positives: when traceroutes are
performed on paths that don’t traverse ISP
– False negatives: when removing traceroutes
results in less information
Path reductions
• Don’t do traceroutes that enter and/or
leave the ISP through the same points;
they will probably take the same path
through the ISP
• Ingress reduction
• Egress reduction
• Next-hop AS reduction
Ingress
Egress
reduction reduction
Next-hop AS
reduction
Alias resolution
• Improves Mercator’s UDP-portunreachable triggering
• Assumes that router aliases will have
some set of characteristics that is
constant between its aliases
• Tests one pair of addresses at a time
Alias resolution methods
• Compare TTLs in responses to UDP requests
• Test ICMP rate limiting
– If two probes to two addresses are sent right away
with only one response returned, then it is a single
router
• Assume that packets sent consecutively will
have incrementing IP ID in the response
Identifying routers
• How to determine
– Which routers correspond to the ISP in question
– What are the routers’ physical locations?
– Which other routers they connect to?
• Use DNS names
– Support of BGP on routers is irrelevant
– Can identify network edges by changes in names
– Customer nodes (cable, DSL, dialup) are named
differently
– Can guess location through naming convention
Rocketfuel Results
Statistics for 10 mapped ISPs using 294 publicly available
traceroute servers
Traceroute reduction results