|
URL:
|
https://research.cs.washington.edu/networking/rocketfuel/papers/sigcomm2002.pdf
|
|
Entry Date:
|
2002-5-30
|
|
Abstract:
|
To date, realistic ISP topologies have not been accessible to the research
community, leaving work that depends on topology on an uncertain footing. In
this paper, we present new Internet mapping techniques that have enabled us to
directly measure router-level ISP topologies. Our techniques reduce the number
of required traces compared to a brute-force, all-to-all approach by three
orders of magnitude without a significant loss in accuracy. They include the
use of BGP routing tables to focus the measurements, exploiting properties of
IP routing to eliminate redundant measurements, better alias resolution, and
the use of DNS to divide each map into POPs and backbone. We collect maps from
ten diverse ISPs using our techniques, and find that our maps are substantially
more complete than those of earlier Internet mapping efforts. We also report on
properties of these maps, including the size of POPs, distribution of router
outdegree, and the inter-domain peering structure. As part of this work, we
release our maps to the community.
|
|
Results:
|
-
Presents new techniques to measure router-level ISP topologies. These and
other techniques are used by Rocketfuel to discover ISP maps that consist of
backbone, access and directly connected neighouring domain routers along with
the IP-level interconnections between them. The new techniques reduce the
number of required traces compared to a brute-force, all-to-all approach by
three orders of magnitude without significant loss in accuracy.
The techniques used are:
-
Use of BGP routing tables (obtained from Routeviews) to focus
measurements. Only traceroutes are performed that will likely transit the
ISP.
-
Exploiting properties of IP routing to eliminate likely redundant
traceroutes.
-
Alias resolution: Uses the existing technique (from Mercator) of
eliciting a "UDP port unreachable" message (from Mercator). New techiques
used are router identification hints such as IP identifier (IP
fragmentation), ICMP rate-limiting by routers of "unreachable" messages,
and TTL values in "unreachable" messages.
-
o Use of hints embedded in DNS names to determine which routers belong
to the ISP, the role of routers (e.g. backbone vs access), and the
geographical location of routers (to determine POPs).
-
Collected maps from ten ISPs and claim that they are substantially more
complete than earlier Internet mapping efforts. The maps and raw measurement
data are released to the community.
-
Report refined results for the distribution of POP sizes and router
outdegree, and the inter-domain peering structure.
-
Found that ISPs have differing backbone designs but similar POP designs.
-
To evaluate the ISP maps produced by Rocketfuel the maps are compared with:
-
Public ISP maps. Found that public ISP maps often have missing POPs,
optimistic deployment projections, and contain parts of partner networks
of other IPSs.
-
An email survey with three ISPs. Results are favorable.
-
The total number of routers found by scanning sampled subnets. 41-79% of
such routers were found by Rocketfuel (64-96% of backbone routers and
35-92% of access routers).
-
Peerings from Routeviews BGP tables. In the worst case (Sprint) 70% of
peerings visible in RV were found. Rocketfuel finds a small number of
additional peerings. BGP tables find more small (low AS degree)
neighbours, whereas Rocketfuel finds more large neighbours.
-
Skitter maps. Rocketfuel finds seven times as many nodes and links in the
area of focus. Skitter finds a small number of additional nodes and
links.
-
To evaluate alias resolution, a comparison was made with:
-
Mercator. A superset of Mercator aliases was found which was almost
three times as large.
-
DNS-predicted aliases of Ebone (119 out of 139 correct) and Sprint (240
out of 303? correct).
|
|
Datasets:
|
-
Analysis of ten ISPs: Abovenet, AT&T, Ebone, Exodus, Level3, Sprint,
Telstra,
Tiscali (Europe), Verio, VSNL (India), using 294 public traceroute servers
representing 784 vantage points.
-
Routeviews BGP table snapshots.
-
Email survey of three ISPs.
-
Public ISP maps.
-
For comparison with Skitter:
- Skitter data of Nov 27 2001 and Nov 28 2001.
- Rocketfuel data of Jan 2002.
|
|
References:
|
- Complements:
-
k. claffy, T. E. Monk, and D. McRobb. Internet tomography. In Nature,
January 1999.
- Refines some of:
-
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of
the Internet topology. In ACM SIGCOMM, 1999.
-
R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery.
In IEEE INFOCOM, 2000.
- Comparable:
-
H. Burch and B. Cheswick. Mapping the Internet. IEEE Computer, 32(4):97 98,
102, 1999.
-
k. claffy, T. E. Monk, and D. McRobb. Internet tomography. In Nature,
January 1999.
-
R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery.
In IEEE INFOCOM, 2000.
- Builds on:
-
V. N. Padmanabhan and L. Subramanian. An investigation of geographic
mapping techniques for Internet hosts. In ACM SIGCOMM, August 2001.
|
