Title: Streaming cache placement problems: complexity and algorithms

Authors: Carlos A.S. Oliveira, Panos M. Pardalos, Oleg A. Prokopyev, Mauricio G.C. Resende

Addresses: 2 Research Way, Princeton Consultants, Princeton, NJ, 08540, USA. ' Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA. ' Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA. ' Internet and Network Systems Research, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ 07932, USA

Abstract: Multicast networks are used to distribute live content, such as video or audio streams, to a potentially large number of destinations. Streaming caches are deployed in these multicast systems to allow content distribution without network overload. We consider two related problems that arise in multicast networks: the tree cache placement and the flow cache placement problems. These problems are shown to be NP-hard, and we give a proof of hardness of approximation using a gap-preserving reduction. We also present approximation algorithms, as well as special cases where these problems can be solved in polynomial time.

Keywords: multicast networks; streaming service placement; virtual private networks; computational complexity; approximation algorithms; streaming caches; tree cache placement; flow cache placement.

DOI: 10.1504/IJCSE.2007.017823

International Journal of Computational Science and Engineering, 2007 Vol.3 No.3, pp.173 - 183

Published online: 18 Apr 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article