Konstantin Andreev
ABSTRACT
In this paper we present 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 alogarithmic factor. The class of networks that our algorithm applies to includes the one used by Akamai Technologies to deliver live media streams over the Internet. In particular, we analyze 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 trave 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. We assume that the loss rate between any pair of nodes in the network is known, and that losses between different pairs are independent, but discuss extensions in which some losses may be correlated.
- Probability Inequalities for Sums, Hoeffding, W., American Statistical Assocation Journal,1963]]Google Scholar
- A Case For End System Multicast, Chu, Y. and Rao, S. and Zhang, H., Proceedings of ACM SIGMETRICS, 2000]]Google Scholar
- The complexity of enumeration and reliability problems, Valiant, L., SIAM Journal on Computing, 1979]]Google Scholar
- A randomized fully polynomial time approximation scheme for all-terminal network reliability problem, Karger, D., Proceedings of the 27th ACM STOC, 1995]] Google ScholarDigital Library
- Multicast routing in a datagram internetwork, Deering, S., Ph. D. Dissertation, 1991]]Google Scholar
- Heuristics for the Fixed Cost Median Problem, Hochbaum, D., Mathematical Programming, 1982]]Google Scholar
- Improved Approximation Algorithms for Metric Facility Location Problems, Mahdian, M. and Ye, Y. and Zhang, J., APPROX, 2002]]Google Scholar
- A New Greedy Approach for Facility Location Problem, Jain, K. and Mahdian, M. and Saberi, A., Proceedings of the 34th ACM STOC, 2002]] Google ScholarDigital Library
- Approximation Algorithms for Facility Location Problems, Shmoys, D. B. and Tardos, 'E. and Aardal, K., Proceedings of 29th ACM STOC, 1997]] Google ScholarDigital Library
- Greedy strikes back: Improved facility location algorithms, Guha, S. and Khuller, S., Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998]] Google ScholarDigital Library
- Improved algorithms for uncapacitated facility location problem, Chudak, F.A., Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization, 1998]]Google Scholar
- Improved Combinatorial Algorithms for Facility Location and k-median problems, Charikar, M. and Guha, S., Proceedings of 40th IEEE FOCS, 1999]] Google ScholarDigital Library
- Primal-Dual Approximation Algorithms for Metric Facility Location and k-median Problems, Jain, K. and Vazirani, V., Proceedings of 40th IEEE FOCS, 1999]] Google ScholarDigital Library
- An 1.67-approximation algorithm for the metric uncapacitated facility location problem, Sviridenko, M., Unpublished Manuscript, 2001]]Google Scholar
- Facility Location with Nonuniform Hard Capacities, P'al, M. and Tardos, 'E and Wexler, T., Proceedings of the 42nd IEEE Symposium on the Foundations of Computer Science, 2001]] Google ScholarDigital Library
- Meyerson, A. and Munagala, K. and Plotkin, S., Web Caching using Access Statistics, Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, 2001]] Google ScholarDigital Library
- Korupolu, M. and Plaxton, G. and Rajaraman, R., Placement Algorithms for Hierarchical Cooperative Caching, Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, 1999]] Google ScholarDigital Library
- Baev, I.D. and Rajaraman, R., Approximation Algorithms for Data Placement in Arbitrary Networks, Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, 2001]] Google ScholarDigital Library
- Guha, S. and Munagala, K., Improved Algorithms for the Data Placement Problem, Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, 2002]] Google ScholarDigital Library
- Improved Algorithms for Fault-Tolerant Facility Location, Guha, S. and Meyerson, A. and Munagala, K., Proceedings of the 12th Annual ACM-SIAM SODA, 2001]] Google ScholarDigital Library
- Jain, K. and Vazirani, V., An Approximation Algorithm for the Fault Tolerant Metric Facility Locaiton Problem, APPROX, 2000]] Google ScholarDigital Library
- An Approximation Algorithm for the Generalized Assignment Problem, Shmoys, D. and Tardos, 'E., Proceedings of the 4th Annual ACM-SIAM SODA, 1993]]Google Scholar
- A Greedy Heuristic for the Set Covering Problem, Chvatal, V., Math. Operations Research, 1979]]Google Scholar
- Approximation Algorithms for Combinatorial Problems, Johnson, D.S., Journal of Computer and System Sciences, 1974]]Google Scholar
- On the Hardness of Approximating Minimization Problems, Lund, C. and Yannakakis, M., Journal of the ACM, 1994]] Google ScholarDigital Library
- A Threshold of ln n for Approximating Set Cover, Feige, U., Journal of the ACM, 1998]] Google ScholarDigital Library
- Hofri, M., Probabilistic Analysis of Algorithms, Springer--Verlag, 1987]] Google ScholarDigital Library
- Eriksson, H., Mbone: The multicast backbone, Communications of the ACM, 37(8), 1994]] Google ScholarDigital Library
- Srinivasan, A. and Teo, C., A constant-factor approximation algorithm for packet routing and balancing vs. global critiria, SIAM Journal of Computing, 30(6), 2001]] Google ScholarDigital Library
- Padmanabhan, V. and Wang, H. and Chou, P. and Sripanidkulchai, K., Distributing streaming media content using cooperative networking, To appear in ACM NOSSDAV, 2002]] Google ScholarDigital Library
Index Terms
- Designing overlay multicast networks for streaming
Recommendations
Soft ARQ for Layered Streaming Media
Special issue on multimedia signal processingA growing and important class of traffic in the Internet is so-called "streaming media," in which a server transmits a packetized multimedia signal to a receiver that buffers the packets for playback. This playback buffer, if adequately sized, ...
Cross Layer Protocol Support for Live Streaming Media
AINA '08: Proceedings of the 22nd International Conference on Advanced Information Networking and ApplicationsDelivering live streaming content over the Internet requires low delay and smooth packet transmission rate. TCP introduces rate oscillations and requires more buffering andbandwidth to sustain uninterrupted playback. In this paper we propose a new ...
Supporting large scale e-Research infrastructures with adapted live streaming capabilities
AusGrid '08: Proceedings of the sixth Australasian workshop on Grid computing and e-research - Volume 82Large scale e-Research environments face classical distributed challenges: performance, heterogeneous equipment and variable contexts. The users of such infrastructures want to benefit from full interactive environments based on multimedia streams (voice,...
Comments