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