DATE: Thursday, April 29, 2004
TIME: Noon - 1 pm
PLACE: Wean Hall 8220

Gary Miller
Carnegie Mellon

Scalable Internet Path Selection System

This talk describes the experiments that led to, and the design of a path selection system we developed that optimizes communication over the Internet by capitalizing on the availability of servers in
widespread physical locations.

When we consider the problem of delivering data to a large number of hosts spread all over the world from a few servers, there are a number of independent reasons why we gain in terms of security, reliability and
performance by sending the data to its final destinations via intermediate locations.

Our tests show that even without considering the effect of additional (orthogonal) optimizations, such as taking advantage of open connections or compression in its various forms, we can get a two fold speedup on 16KB downloads for a quarter of all pairs of our North American data-centers, just by picking the appropriate intermediate locations. The downloads that benefit the most happen between hosts that are
further away from each other.

The system designed continuously collects ICMP data, and for each pair of hosts that might wish to communicate, it finds a small set of candidate hosts that based on the ICMP data are suitable as intermediate hosts for the data transfers. When an actual data transfer is to take place, the host initiating the transfer relies on data about recent transfers to compare the direct and indirect alternatives it has, and uses the best of them.

This represents joint work with Claudson Bornstein, Tim Canfield, and Satish Rao.

Gary Miller is a full professor in the School of Computer Science at the Carnegie Mellon University. He received his PhD in Mathematics at the University of California, Berkeley in 1975. He was Asistant and Associate Professor of Mathematics at MIT, a full professor of Computer Science at the University of Southern California.

His research interests includes algorithm desgin, parallel computing, computational geometry, VLSI design, and scientific and numerical computing. He is well-known for his work in primality testing, graph isomorphism, parallel tree contraction, and graph separators.

For Further Seminar Info:
Contact Linda Whipkey, Karen Lindenfelser or visit