On Periodic Resource scheduling for Continuous-Media Databases.

Minos N. Garofalakis, Banu Özden, Abraham Silberschatz: On Periodic Resource scheduling for Continuous-Media Databases. VLDB J. 7(4): 206-225(1998)
  author    = {Minos N. Garofalakis and
               Banu {\"O}zden and
               Abraham Silberschatz},
  title     = {On Periodic Resource scheduling for Continuous-Media Databases},
  journal   = {VLDB J.},
  volume    = {7},
  number    = {4},
  year      = {1998},
  pages     = {206-225},
  ee        = {db/journals/vldb/GarofalakisOS98.html},
  bibsource = {DBLP,}


The Enhanced Pay-Per-View (EPPV) model for providing continuous-media services associates with each continuous-media clip a display frequency that depends on the clip's popularity. The aim is to increase the number of clients that can be serviced concurrently beyond the capacity limitations of available resources, while guaranteeing a constraint on the response time. This is achieved by sharing periodic continuous-media streams among multiple clients. The EPPV model offers a number of advantages over other data-sharing schemes (e.g., batching), which make it more attractive to large-scale service providers. In this paper, we provide a comprehensive study of the resource-scheduling problems associated with supporting EPPV for continuous-media clips with (possibly) different display rates, frequencies, and lengths. Our main objective is to maximize the amount of disk bandwidth that is effectively scheduled under the given data layout and storage constraints. Our formulation gives rise to $\cal NP$-hard combinatorial optimization problems that fall within the realm of hard real-time scheduling theory. Given the intractability of the problems, we propose novel heuristic solutions with polynomial-time complexity. We also present preliminary experimental results for the average case behavior of the proposed scheduling schemes and examine how they compare to each other under different workloads. A major contribution of our work is the introduction of a robust scheduling framework that, we believe, can provide solutions for a variety of realistic EPPV resource-scheduling scenarios, as well as any scheduling problem involving regular, periodic use of a shared resource. Based on this framework, we propose various interesting research directions for extending the results presented in this paper.

Key Words

Continuous media - Multimedia databases - Storage systems - Real-time scheduling

Copyright © 1998 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Emmanuel L. Abram-Profeta, Kang G. Shin: Scheduling Video Programs in Near Video-on-Demand Systems. ACM Multimedia 1997: 359-369 BibTeX
Charu C. Aggarwal, Joel L. Wolf, Philip S. Yu: On Optimal Batching Policies for Video-on-Demand Storage Servers. ICMCS 1996: 253-258 BibTeX
Mee Yee Chan, Francis Y. L. Chin: Schedulers for Larger Classes of Pinwheel Instances. Algorithmica 9(5): 425-462(1993) BibTeX
Mon-Song Chen, Dilip D. Kandlur, Philip S. Yu: Optimization of the Grouped Sweeping Scheduling (GSS) with Heterogeneous Multimedia Streams. ACM Multimedia 1993: 235-242 BibTeX
Asit Dan, Dinkar Sitaram, Perwez Shahabuddin: Scheduling Policies for an On-Demand Video Server with Batching. ACM Multimedia 1994: 15-23 BibTeX
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
Minos N. Garofalakis, Yannis E. Ioannidis: Multi-dimensional Resource Scheduling for Parallel Queries. SIGMOD Conference 1996: 365-376 BibTeX
Minos N. Garofalakis, Banu Özden, Abraham Silberschatz: Resource Scheduling in Enhanced Pay-Per-View Continuous Media Databases. VLDB 1997: 516-525 BibTeX
Jim Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, Lawrence A. Rowe: Multimedia Storage Servers: A Tutorial. IEEE Computer 28(5): 40-49(1995) BibTeX
Leana Golubchik, John C. S. Lui, Richard R. Muntz: Adaptive Piggybacking: A Novel Technique for Data Sharing in Video-on-Demand Storage Servers. Multimedia Syst. 4(3): 140-155(1996) BibTeX
Ching-Chih Han, Kwei-Jay Lin, Chao-Ju Hou: Distance-Constrained Scheduling and Its Applications to Real-Time Systems. IEEE Trans. Computers 45(7): 814-826(1996) BibTeX
Oscar H. Ibarra, Chul E. Kim: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. J. ACM 22(4): 463-468(1975) BibTeX
Mohan Kamath, Krithi Ramamritham, Donald F. Towsley: Continuous Media Sharing in Multimedia Database Systems. DASFAA 1995: 79-86 BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison-Wesley 1981, ISBN 0-201-03822-6
Eugene L. Lawler: Fast Approximation Algorithms for Knapsack Problems. Math. Oper. Res. 4(4): 339-356(1979) BibTeX
M. Y. Y. Leung, John C. S. Lui, Leana Golubchik: Buffer and I/O Resource Pre-allocation for Implementing Batching and Buffering Techniques for Video-on-Demand Systems. ICDE 1997: 344-353 BibTeX
Thomas D. C. Little, Dinesh Venkatesh: Popularity-Based Assignment of Movies to Storage Devices in a Video-on-Demand System. Multimedia Syst. 2(6): 280-287(1995) BibTeX
C. L. Liu, James W. Layland: Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM 20(1): 46-61(1973) BibTeX
Banu Özden, Alexandros Biliris, Rajeev Rastogi, Abraham Silberschatz: A Low-Cost Storage Server for Movie on Demand Databases. VLDB 1994: 594-605 BibTeX
Banu Özden, Alexandros Biliris, Rajeev Rastogi, Abraham Silberschatz: A Disk-Based Storage Architecture for Movie on Demand Servers. Inf. Syst. 20(6): 465-482(1995) BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: A Framework for the Storage and Retrieval of Continous Media Data. ICMCS 1995: 2-14 BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz, Cliff Martin: Demand Paging for Video-on-Demand Servers. ICMCS 1995: 264-272 BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Disk Striping in Video Server Environments. IEEE Data Eng. Bull. 18(4): 4-16(1995) BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Disk Striping in Video Server Environments. ICMCS 1996: 580-589 BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: On the Design of a Low-Cost Video-on-Demand Storage System. Multimedia Syst. 4(1): 40-54(1996) BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: The Storage and Retrieval of Continuous Media Data. Multimedia Database System: Issues and Research Direction 1996: 237-261 BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Periodic Retrieval of Videos from Disk Arrays. ICDE 1997: 333-343 BibTeX
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 BibTeX
P. Venkat Rangan, Harrick M. Vin: Designing File Systems for Digital Video and Audio. SOSP 1991: 81-94 BibTeX
P. Venkat Rangan, Harrick M. Vin: Efficient Storage Techniques for Digital Continuous Multimedia. IEEE Trans. Knowl. Data Eng. 5(4): 564-573(1993) BibTeX
Sartaj Sahni: Approximate Algorithms for the 0/1 Knapsack Problem. J. ACM 22(1): 115-124(1975) BibTeX
Weifeng Shi, Shahram Ghandeharizadeh: Buffer Sharing in Video-On-Demand Servers. SIGMETRICS Performance Evaluation Review 25(2): 13-20(1997) BibTeX
Abraham Silberschatz, Peter Galvin: Operating System Concepts, 4th edition. Addison-Wesley 1994, ISBN 0-201-50480-4
John A. Stankovic, Krithi Ramamritham (Eds.): Advances in Real-Time Systems. IEEE Computer Society 1993
W.-D. Wei, C. L. Liu: On a Periodic Maintenance Problem. Oper. Res. Lett. 2(2): 90-93(1983) BibTeX
Clement T. Yu, Wei Sun, Dina Bitton, Qi Yang, Richard Bruno, John Tullis: Efficient Placement of Audio Data on Optical Disks for Real-Time Applications. Commun. ACM 32(7): 862-871(1989) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:34 2009