CSE 525
(Winter 2004)
Topic #2: Internet Tomography
Chris Chambers
[1] M. Andrews, B. Shepherd, A. Srinivasan, P. Winkler,
F. Zane, "Clustering and Server Selection using Passive
Monitoring", INFOCOM 2002. paper
[2] V. N. Padmanabhan and L. Subramanian. “An
Investigation of Geographic Mapping Techniques for Internet Hosts”, ACM
SIGCOMM, August 2001. paper
[3] E.Ng and H.Zhang, "Predicting Internet network
distance with coordinates-based approaches," INFOCOM 2001. paper
Summary: These papers are in the area of Internet Tomography,
which answers questions about the state of the Internet as a whole, such as
its topology, its bottlenecks, or what it would look like as a two- or
three-dimensional space. This topic is important to content delivery networks
as well as anyone seeking to improve performance of Internet applications.
They solve different problems with different techniques, but some common
dimensions of solutions in this area include: a decision between passive or
active latency determination, and how to cluster the Internet into subnets.
- Clustering and Server
Selection
- Problem: Find the best
content server for a given IP
- Passively monitor
latency from clients to servers
- Use stochastic modeling
to cluster co-located IP addresses
- Rotate clients between
servers to gain new information (like multi-armed bandit solution)
- Geographic Mapping Techniques
- Problem: Find the world
location for a given IP
- GeoTrack: infer
location by DNS / traceroute textual information
- GeoPing: ping target IP
from a set of known locations, triangulate
- GeoCluster: build on
BGP routing table as a clustering basis
- Predicting Internet network
distance with coordinates
- Problem: Find the
latency between two IP’s
- Set up known landmarks,
actively pinging each other
- Build a 3-d
mathematical model based on their locations and latencies
- Fit new IP’s into
model
- Comments
- How do you know if you
have a good cluster?
- How can you seamlessly
switch content servers?
Presentation: slides