Abstract
We consider a packing problem arising in storage management of Video on Demand (VoD) systems. The system consists of a set of video files (movies) and several servers (disks), each having a limited storage capacity, C, and a limited bandwidth (load capacity), L. The goal in the storage allocation problem is to assign the video files to the servers and the bandwidth to the clients. The induced class-constrained packing problem was studied in the past assuming each client provides a single request for a single movie. This paper considers a more general and realistic model—in which each client ranks all the movies in the system. Specifically, for each client j and movie i, it is known how much client j is willing to pay in order to watch movie i. The goal is to maximize the system’s profit. Alternatively, the client might provide a ranking of the movies and the goal is to maximize the lexicographic profile of the solution.
We prove that the problem is NP-complete and present approximation algorithms and heuristics for systems with a single or multiple disks. For a single disk we present an (1−1/e)-approximation algorithm that is extended for systems with storage costs, and for k-round broadcasting, in which each client might be serviced multiple times. For multiple disks we present a (C−1)(e−1)/Ce-approximation algorithm, two heuristics for determining the storage allocation, and an optimal bandwidth-allocation algorithm.
In our simulation of a VoD system, we compared the performance of the suggested heuristics for systems with variable parameters and clients with variable preference distributions. We focused on systems in which client preferences and payment are power-law distributed: a few movies are very popular and clients are willing to pay significantly more for watching them.
Our results can be applied to other packing and subset selection problems in which clients provide preferences over the elements.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bar-Noy A, Ladner RE (2004) Efficient algorithms for optimal stream merging for media-on-demand. SIAM J Comput 33(5):1011–1034
Bar-Noy A, Ladner RE, Tamir T (2003) Scheduling techniques for media-on-demand. In: Proc of the 14th ACM-SIAM symposium on discrete algorithms, pp 791–800
Chou CF, Golubchik L, Lui JCS (2000) A performance study of dynamic replication techniques in continuous media servers. In: Proc of the international symposium on modeling, analysis and simulation of computer and telecommunication systems (IEEE MASCOTS), pp 256–264
Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45(4):634–652
Feige U (2003) Vertex cover is hardest to approximate on regular graphs. Technical Report MCS03-15, Computer Science and Applied Mathematics, The Weizmann Institute of Science
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Golubchik L, Khanna S, Khuller S, Thurimella R, Zhu A (2000) Approximation algorithms for data placement on parallel disks. In: Proc of SODA, pp 223–232
Harvey NJA, Ladner RE, Lovász L, Tamir T (2006) Semi-matchings for bipartite graphs and load balancing. J Algorithms 59(1):53–78
Ibaraki T, Katoh N (1988) Resource allocation problems—algorithmic approaches. MIT Press, Cambridge
Kamath M, Ramamritham K, Towsley D (1995) Continuous media sharing in multimedia database systems. In: Proc of the 4th intl conf on database systems for advanced applications, pp 79–86
Kang S (2004) Video-on-demand system using multicast and web-caching techniques. In: Grid and cooperative computing. LNCS, vol 3032. Springer, Berlin, pp 273–276
Kashyap S, Khuller S (2006) Algorithms for non-uniform size data placement on parallel disks. J Algorithms 60(2):144–167
Khuller S, Moss A, Naor J (1999) The budgeted maximum coverage problem. Inf Process Lett 70(1):39–45
Klein M (1967) A primal method for minimal cost flows. Manag Sci 14:205–220
Little TC, Venkatesh D (1995) Popularity-based assignment of movies to storage devices in a video-on-demand system. Multimedia Syst 2(6):280–287
Nemhauser G, Wolsey L, Fisher M (1978) An analysis of the approximations for maximizing submodular set functions. Math Program 14:265–294
Shachnai H, Tamir T (2001a) On two class-constrained versions of the multiple knapsack problem. Algorithmica 29(3):442–467
Shachnai H, Tamir T (2001b) Polynomial time approximation schemes for class-constrained packing problems. J Sched 4(6):313–338
Shachnai H, Tamir T (2003) Approximation schemes for generalized 2-dimensional vector packing with application to data placement. In: Proc of RANDOM-APPROX, pp 165–177
Sviridenko M (2004) A Note on maximizing a submodular set function subject to knapsack constraint. Oper Res Lett 32:41–43
Wang Y, Liu JCL, Du DHC, Hsieh J (2004) Efficient video file allocation schemes for video-on-demand services. J Multimedia Syst 5:1432–1882
Wolf JL, Yu PS, Shachnai H (1996) Scheduling issues in video-on-demand systems. Multimedia Inf Storage Manag 183–207
Wolf JL, Yu PS, Shachnai H (1997) Disk load balancing for video-on-demand systems. ACM Multimedia Syst J 5:358–370
Yu H, Zheng D, Zhao BY, Zheng W (2006) Understanding user behavior in large scale video-on-demand systems. In: The 1st ACM SIGOPS/EuroSys European conference on computer systems, pp 333–344
Zhou X, Xu CZ (2002) Optimal video replication and placement on a cluster of video-on-demand servers. In: Proc of the 2002 international conference on parallel processing (ICPP’02), pp 547–555
Zipf GK (1949) Human behavior and the principle of least effort. Addison-Wesley, Cambridge
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tamir, T., Vaksendiser, B. Algorithms for storage allocation based on client preferences. J Comb Optim 19, 304–324 (2010). https://doi.org/10.1007/s10878-009-9259-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9259-0