More Web Proxy on the site http://driver.im/

Article

Growing half-balls: minimizing storage and communication costs in CDNs

Authors:

Reuven Bar-Yehuda,

Dror RawitzAuthors Info & Claims

ICALP'12: Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II

Pages 416 - 427

https://doi.org/10.1007/978-3-642-31585-5_38

Published: 09 July 2012 Publication History

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.

References

[1]

Net-HD Consortium, http://www.nethd.org.il

[2]

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

[3]

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

[4]

Abell, J.C.: Netflix instant account for 20 percent of peek U.S. bandwidth use. Wire Magazine (October 21, 2010).

[5]

Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM 45(5), 753-782 (1998).

Digital Library

[6]

Awerbuch, B., Bartal, Y., Fiat, A.: Competitive distributed file allocation. In: 25th ACM STOC, pp. 164-173 (1993).

Digital Library

[7]

Bartal, Y., Fiat, A., Rabani, Y.: Competitive algorithms for distributed data management. In: 24th ACM STOC, pp. 39-50 (1992).

Digital Library

[8]

Black, D., Sleator, D.: Competitive algorithms for replication and migration problems. Tech. Rep. CMU-CS-89-201, CMU (1989).

[9]

Charlikar, M., Halperin, D., Motwani, R.: The dynamic servers problem. In: 9th Annual Symposium on Discrete Algorithms, pp. 410-419 (1998).

Digital Library

[10]

Cidon, I., Kutten, S., Soffer, R.: Optimal allocation of electronic content. Computer Networks 40(2), 205-218 (2002).

Digital Library

[11]

Dowdy, L.W., Foster, D.V.: Comparative models of the file assignment problem. ACM Comp. Surveys 14(2), 287-313 (1982).

Digital Library

[12]

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).

[13]

Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks 22(1), 55-89 (1992).

[14]

Jones, D.: Proof that telstra is throtteling youtube bandwidth in australia, http://www.eevblog.com, http://www.youtube.com/watch?v=9iDRynyBl0c

[15]

Kopytoff, V.G.: Shifting online, Netflix faces new competition. New York Times (Business Day, Technology) (September 26, 2010).

[16]

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).

[17]

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).

Digital Library

[18]

Papadimitriou, C., Ramanathan, S., Rangan, P., Sampathkumar, S.: Multimedia information caching for personalized video-on demand. Computer Communications 18(3), 204-216 (1995).

Digital Library

[19]

Schaffa, F., Nussbaumer, J.P.: On bandwidth and storage tradeoffs in multimedia distribution networks. In: IEEE INFOCOM, pp. 1020-1026 (1995).

Digital Library

[20]

Xiuzhen Cheng, B.D., Lu, B.: Polynomial time approximation scheme for symmetric rectilinear steiner arborescence problem. J. Global Optim. 21, 385-396 (2001).

Digital Library

Cited By

Zuo TTang XLee BAgrawal KPetrank E(2024)Cost-Driven Data Replication with PredictionsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659964(309-320)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659964
Kantor EKutten S(2015)Optimal Competitiveness for the Rectilinear Steiner Arborescence ProblemProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_54(675-687)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_54

Recommendations

Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks

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 ...
Balls and Bins: Smaller Hash Families and Faster Evaluation
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

A fundamental fact in the analysis of randomized algorithms is that when n balls are hashed into n bins independently and uniformly at random, with high probability each bin contains at most O(log n / log(log n)) balls. In various applications, however, ...
Balls and Bins: Smaller Hash Families and Faster Evaluation
^† Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010)

A fundamental fact in the analysis of randomized algorithms is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n/\log\log n)$ balls. In various applications, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'12: Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II

July 2012

676 pages

ISBN:9783642315848

Editors:
Artur Czumaj
Department of Computer Science and Centre for Discrete Mathematics and its Applications, University of Warwick, Warwick, UK
,
Kurt Mehlhorn
Department of Computer Science and Centre for Discrete Mathematics and its Applications, Max-Planck-Institut für Informatik, Saarbrücken, Germany
,
Andrew Pitts
Computer Laboratory, University of Cambridge, Saarbrücken, UK
,
Roger Wattenhofer
Computer Laboratory,, ETH Zurich, Saarbrücken, Switzerland

Sponsors

Springer-Verlag
Microsoft Research: Microsoft Research
EATCS: European Association for Theoretical Computer Science

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 July 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zuo TTang XLee BAgrawal KPetrank E(2024)Cost-Driven Data Replication with PredictionsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659964(309-320)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659964
Kantor EKutten S(2015)Optimal Competitiveness for the Rectilinear Steiner Arborescence ProblemProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_54(675-687)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_54

View Options

View options

Media

Figures

Other

Tables

View Table of Contents