Designing overlay multicast networks for streaming

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.

REFERENCES

• 1: Probability Inequalities for Sums, Hoeffding, W., American Statistical Assocation Journal,1963
• 2: A Case For End System Multicast, Chu, Y. and Rao, S. and Zhang, H., Proceedings of ACM SIGMETRICS, 2000
• 3: The complexity of enumeration and reliability problems, Valiant, L., SIAM Journal on Computing, 1979
• 4: David R. Karger, A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.11-17, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225069]
• 5: Multicast routing in a datagram internetwork, Deering, S., Ph. D. Dissertation, 1991
• 6: Heuristics for the Fixed Cost Median Problem, Hochbaum, D., Mathematical Programming, 1982
• 7: Improved Approximation Algorithms for Metric Facility Location Problems, Mahdian, M. and Ye, Y. and Zhang, J., APPROX, 2002
• 8: Kamal Jain , Mohammad Mahdian , Amin Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510012]
• 9: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 10: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.649-657, January 25-27, 1998, San Francisco, California, United States
• 11: Improved algorithms for uncapacitated facility location problem, Chudak, F.A., Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization, 1998
• 12: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 13: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 14: An 1.67-approximation algorithm for the metric uncapacitated facility location problem, Sviridenko, M., Unpublished Manuscript, 2001
• 15: M. Pál , É. Tardos , T. Wexler, Facility Location with Nonuniform Hard Capacities, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.329, October 14-17, 2001
• 16: Adam Meyerson , Kamesh Munagala , Serge Plotkin, Web caching using access statistics, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.354-363, January 07-09, 2001, Washington, D.C., United States
• 17: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Placement algorithms for hierarchical cooperative caching, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 17-19, 1999, Baltimore, Maryland, United States
• 18: Ivan D. Baev , Rajmohan Rajaraman, Approximation algorithms for data placement in arbitrary networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.661-670, January 07-09, 2001, Washington, D.C., United States
• 19: Sudipto Guha , Kamesh Munagala, Improved algorithms for the data placement problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.106-107, January 06-08, 2002, San Francisco, California
• 20: Sudipto Guha , Adam Meyerson , Kamesh Munagala, Improved algorithms for fault tolerant facility location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.636-641, January 07-09, 2001, Washington, D.C., United States
• 21: Kamal Jain , Vijay V. Vazirani, An approximation algorithm for the fault tolerant metric facility location problem, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.177-183, September 05-08, 2000
• 22: An Approximation Algorithm for the Generalized Assignment Problem, Shmoys, D. and Tardos, 'E., Proceedings of the 4th Annual ACM-SIAM SODA, 1993
• 23: A Greedy Heuristic for the Set Covering Problem, Chvatal, V., Math. Operations Research, 1979
• 24: Approximation Algorithms for Combinatorial Problems, Johnson, D.S., Journal of Computer and System Sciences, 1974
• 25: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 26: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 27: Micha Hofri, Probabilistic analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1987
• 28: Hans Eriksson, MBONE: the multicast backbone, Communications of the ACM, v.37 n.8, p.54-60, Aug. 1994 [doi>10.1145/179606.179627]
• 29: Aravind Srinivasan , Chung-Piaw Teo, A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria, SIAM Journal on Computing, v.30 n.6, p.2051-2068, 2001 [doi>10.1137/S0097539798335596]
• 30: Venkata N. Padmanabhan , Helen J. Wang , Philip A. Chou , Kunwadee Sripanidkulchai, Distributing streaming media content using cooperative networking, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507695]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
approximation algorithms, network design, network reliability, streaming media