×

Competitive video on demand schedulers for popular movies. (English) Zbl 1023.68010

Summary: We investigate the online video on demand problem, namely having to accept or reject a request for a movie without knowing the future requests. We present online movie-scheduling schemes that implement the principles of refusal by choice and delayed notification. A novel way to schedule movies that exploits the knowledge of the distribution of the preference of requests for movies, is shown to have a competitive ratio that outperforms all the previously known schemes in practical situations. In fact, our scheduler has a competitive ratio bounded above by a constant, independent of the number of the users, channels, or movies, in the case that a large fraction of the requests tends to concentrate in a small number of movies. We extend our approach by presenting an “adaptive” randomized scheduler which initially is not aware of the movie popularities but it adapts to it, and achieves the same asymptotic competitive ratio.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Aggarwal, J.A. Garay, A. Herzberg, Adaptive video on demand, in: Proceedings of the Third Annual European Symposium on Algorithms (ESA’95), Lecture Notes in Computer Science, Vol. 959, Springer, Berlin, pp. 538-553.; S. Aggarwal, J.A. Garay, A. Herzberg, Adaptive video on demand, in: Proceedings of the Third Annual European Symposium on Algorithms (ESA’95), Lecture Notes in Computer Science, Vol. 959, Springer, Berlin, pp. 538-553.
[2] B. Awerbuch, Y. Azar, S. Plotkin, Throughput competitive on-line routing, in: Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS’93), 1993.; B. Awerbuch, Y. Azar, S. Plotkin, Throughput competitive on-line routing, in: Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS’93), 1993.
[3] B. Awerbuch, Y. Bartal, A. Fiat, A Rosén, Competitive non-preemptive call control, in: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’94), 1994.; B. Awerbuch, Y. Bartal, A. Fiat, A Rosén, Competitive non-preemptive call control, in: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’94), 1994. · Zbl 0876.68047
[4] B. Awerbuch, R. Gawlick, T. Leighton, Y. Rabani, On-line admission control and circuit routing for high performance computing and communication, in: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’94), 1994, pp. 412-423.; B. Awerbuch, R. Gawlick, T. Leighton, Y. Rabani, On-line admission control and circuit routing for high performance computing and communication, in: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’94), 1994, pp. 412-423.
[5] Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0931.68015
[6] C. Bouras, V. Kapoulas, G. Pantziou P. Spirakis, Randomized adaptive video on demand, Proceedings of the 15th ACM-PODC, Philadelphia PA, USA, 1996 (short paper).; C. Bouras, V. Kapoulas, G. Pantziou P. Spirakis, Randomized adaptive video on demand, Proceedings of the 15th ACM-PODC, Philadelphia PA, USA, 1996 (short paper).
[7] C. Bouras, V. Kapoulas, G. Pantziou, P. Spirakis, Competitive video on demand schedulers for popular movies, Workshop on Algorithmic Aspects of Communications, July 11-12, Bologna, Italy, 1997.; C. Bouras, V. Kapoulas, G. Pantziou, P. Spirakis, Competitive video on demand schedulers for popular movies, Workshop on Algorithmic Aspects of Communications, July 11-12, Bologna, Italy, 1997. · Zbl 1023.68010
[8] H.J. Chen, T.D.C. Little, Physical storage organizations for time-dependent multimedia data, in: Proceedings of the ACM FODO, 1993.; H.J. Chen, T.D.C. Little, Physical storage organizations for time-dependent multimedia data, in: Proceedings of the ACM FODO, 1993.
[9] Christodoulakis, S.; Faloutsos, C., Design and performance considerations for an optical disk-based, multimedia object server, Computer, 19, 45-56 (1986)
[10] J.A. Garay, I.S. Gopal, Call preemption in communication networks, in: Proceedings of the INFOCOM ’92, Florence, Italy, 1992, pp. 1043-1050.; J.A. Garay, I.S. Gopal, Call preemption in communication networks, in: Proceedings of the INFOCOM ’92, Florence, Italy, 1992, pp. 1043-1050.
[11] J.A. Garay, I. Gopal, S. Kutten, Y. Mansour, M. Yung, Efficient on-line call control algorithms, in: Proceedings of the Second Israeli Symposium on Theory of Computing and Systems, June 1993, pp. 285-293.; J.A. Garay, I. Gopal, S. Kutten, Y. Mansour, M. Yung, Efficient on-line call control algorithms, in: Proceedings of the Second Israeli Symposium on Theory of Computing and Systems, June 1993, pp. 285-293. · Zbl 0866.68042
[12] Horton, C. J., 110 channels without boundaries: why restrict options?, Comm. Eng. Design, 19, 1, 29-30 (1993)
[13] V. Kapoulas, P. Spirakis, Randomized competitive algorithms for admission control in general networks, in: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC’95), August 1995 (short paper).; V. Kapoulas, P. Spirakis, Randomized competitive algorithms for admission control in general networks, in: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC’95), August 1995 (short paper).
[14] J. Koegel, A. Syta, Routing of multimedia connections in hybrid networks, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 2-10.; J. Koegel, A. Syta, Routing of multimedia connections in hybrid networks, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 2-10.
[15] E. Koutsoupias, C. Papadimitriou, Beyond competitive analysis, in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’94), 1994, pp. 394-400.; E. Koutsoupias, C. Papadimitriou, Beyond competitive analysis, in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’94), 1994, pp. 394-400.
[16] W.K.L. Lie, J.C.S. Lui, L. Golubchik, Threshold-based dynamic replication in large-scale video-on-demand systems, in: Proceedings of the Eighth International Workshop on Research Issues in Data Engineering, Orlando, 1998, pp. 52-58.; W.K.L. Lie, J.C.S. Lui, L. Golubchik, Threshold-based dynamic replication in large-scale video-on-demand systems, in: Proceedings of the Eighth International Workshop on Research Issues in Data Engineering, Orlando, 1998, pp. 52-58. · Zbl 1147.68848
[17] Loeb, S., Delivering interactive multimedia documents over networks, IEEE Comm. Magazine, 30, 52-59 (1992)
[18] S.M. McCarthy, Integrating Telco interoffice fiber transport with coaxial distribution, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 23-33.; S.M. McCarthy, Integrating Telco interoffice fiber transport with coaxial distribution, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 23-33.
[19] K. Metz, Next generation CATV networks, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 184-189.; K. Metz, Next generation CATV networks, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 184-189.
[20] R. Ramarao, V. Ramamoorthy, Architectural design of on-demand video delivery systems: the spatio-temporal storage allocation problem, Proceedings of the ICC, 1991.; R. Ramarao, V. Ramamoorthy, Architectural design of on-demand video delivery systems: the spatio-temporal storage allocation problem, Proceedings of the ICC, 1991.
[21] Rangan, P. V.; Vin, H. M.; Ramanathan, S., Designing an on-demand multimedia service, IEEE Commun. Magazine, 30, 56-64 (1992)
[22] C. Sell, Video on demand internal trial, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 168-175.; C. Sell, Video on demand internal trial, Proceedings of the SPIE—International Society on Optical Engineering, Vol. 1786, 1993, pp. 168-175.
[23] Shachnai, H.; Yu, P. S., On analytic modelling of multimedia batching schemes, Performance Evaluation, 33, 201-213 (1998)
[24] Sincoskie, W. D., System architecture for a large scale video-on-demand service, Comput. Networks ISDN Systems, 22, 155-162 (1991)
[25] Wolf, J. L.; Yu, P. S.; Shachnai, H., Disk load balancing for video-on-demand systems, ACM Multimedia Systems J., 5, 358-375 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.