Abstract
The Dynamic Content Distribution problem addresses the trade-off between storage and delivery costs in modern virtual Content Delivery Networks (CDNs). That is, a video file can be stored in multiple places so that the request of each user is served from a location that is near by to the user. This minimizes the delivery costs, but is associated with a storage cost. This problem is NP-hard even in grid networks. In this paper, we present a constant factor approximation algorithm for grid networks. We also present an O(logδ)-competitive algorithm, where δ is the normalized diameter of the network, for general networks with general metrics. We show a matching lower bound by using a reduction from online undirected Steiner tree. Our algorithms use a rather intuitive approach that has an elegant representation in geometric terms.
Supported in part by the Net-HD MAGNET Consortium.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Net-HD Consortium, http://www.nethd.org.il
Cisco visual networking index: Usage study. Cisco Visual Networking Index (October 25, 2010), http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/Cisco_VNI_Usage_WP.html
Hyperconnectivity and the approaching zettabyte era. Cisco Visual Networking Index (June 2, 2010), http://www.cisco.com/en/US/solutions/~collateral/ns341/ns525/ns537/ns705/~ns827/VNI_Hyperconnectivity_WP.html
Abell, J.C.: Netflix instant account for 20 percent of peek U.S. bandwidth use. Wire Magazine (October 21, 2010)
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM 45(5), 753–782 (1998)
Awerbuch, B., Bartal, Y., Fiat, A.: Competitive distributed file allocation. In: 25th ACM STOC, pp. 164–173 (1993)
Bartal, Y., Fiat, A., Rabani, Y.: Competitive algorithms for distributed data management. In: 24th ACM STOC, pp. 39–50 (1992)
Black, D., Sleator, D.: Competitive algorithms for replication and migration problems. Tech. Rep. CMU-CS-89-201, CMU (1989)
Charlikar, M., Halperin, D., Motwani, R.: The dynamic servers problem. In: 9th Annual Symposium on Discrete Algorithms, pp. 410–419 (1998)
Cidon, I., Kutten, S., Soffer, R.: Optimal allocation of electronic content. Computer Networks 40(2), 205–218 (2002)
Dowdy, L.W., Foster, D.V.: Comparative models of the file assignment problem. ACM Comp. Surveys 14(2), 287–313 (1982)
Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing steiner minimal trees. SIAM J. on Applied Math. 32(4), 835–859 (1977)
Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks 22(1), 55–89 (1992)
Jones, D.: Proof that telstra is throtteling youtube bandwidth in australia, http://www.eevblog.com , http://www.youtube.com/watch?v=9iDRynyBl0c
Kopytoff, V.G.: Shifting online, Netflix faces new competition. New York Times (Business Day, Technology) (September 26, 2010)
Papadimitriou, C., Ramanathan, S., Rangan, P.: Information caching for delivery of personalized video programs for home entertainment channels. In: IEEE International Conf. on Multimedia Computing and Systems, pp. 214–223 (1994)
Papadimitriou, C., Ramanathan, S., Rangan, P.: Optimal Information Delivery. In: Staples, J., Katoh, N., Eades, P., Moffat, A. (eds.) ISAAC 1995. LNCS, vol. 1004, pp. 181–187. Springer, Heidelberg (1995)
Papadimitriou, C., Ramanathan, S., Rangan, P., Sampathkumar, S.: Multimedia information caching for personalized video-on demand. Computer Communications 18(3), 204–216 (1995)
Schaffa, F., Nussbaumer, J.P.: On bandwidth and storage tradeoffs in multimedia distribution networks. In: IEEE INFOCOM, pp. 1020–1026 (1995)
Xiuzhen Cheng, B.D., Lu, B.: Polynomial time approximation scheme for symmetric rectilinear steiner arborescence problem. J. Global Optim. 21, 385–396 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Yehuda, R., Kantor, E., Kutten, S., Rawitz, D. (2012). Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31585-5_38
Download citation
DOI: https://doi.org/10.1007/978-3-642-31585-5_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31584-8
Online ISBN: 978-3-642-31585-5
eBook Packages: Computer ScienceComputer Science (R0)