REU Student	Graduate Mentor	Faculty Advisor
Jevan Saks	Konstantin Andreev	Bruce Maggs

In a recent paper, Andreev, Maggs, Meyerson, and Sitaraman [1] designed a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost to within a logarithmic factor. The class of networks that the algorithm applies to includes the one used by Akamai Technologies to deliver live media streams over the Internet. In particular, the algorithm applies to networks consisting of three stages of nodes. The nodes in the first stage are the sources where live streams originate. A source forwards each of its streams to one or more nodes in the second stage, which are called reflectors. A reflector can split an incoming stream into multiple identical outgoing streams, which are then sent on to nodes in the third and final stage, which are called the sinks. As the packets in a stream travel from one stage to the next, some of them may be lost. The job of a sink is to combine the packets from multiple instances of the same stream (by reordering packets and discarding duplicates) to form a single instance of the stream with minimal loss.

This project aims to implement the new algorithm, and to apply it to real-world data collected from Akamai's reflector network. The implementation is challenging because the algorithm makes use of multiple state-of-the-art optimization techniques, including linear programming, randomized rounding, a solution to the generalized assignment problem, and Srinivasan and Teo's rounding technique. The algorithm must be efficient because in practice it would likely be used repeatedly to reoptimize a network as conditions change. Finally, the data set on which the algorithm is tested is large, and includes hundreds of content providers, dozens of potential reflector locations, hundreds of sinks, and reliability estimates on the links connecting them.

[1] K. Andreev, B. M. Maggs, A. Meyerson, and R. Sitaraman, Designing Overlay Multicast Networks for Streaming, Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, June 2003, to appear.

Preliminary Presentation (ppt), (pdf)

Other Mini-PROBEs for Summer 2003

Algorithms for Facility Location
Anonymous Communication
Dynamic Algorithms
HumanAUT
Moving Mesh Simulations
Space-Efficient Point Location