ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Throughput-Competitive Admission Control for Continuous Media Databases.

Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden, Abraham Silberschatz: Throughput-Competitive Admission Control for Continuous Media Databases. PODS 1998: 79-88
@inproceedings{DBLP:conf/pods/GarofalakisIOS98,
  author    = {Minos N. Garofalakis and
               Yannis E. Ioannidis and
               Banu {\"O}zden and
               Abraham Silberschatz},
  title     = {Throughput-Competitive Admission Control for Continuous Media
               Databases},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {79-88},
  ee        = {http://doi.acm.org/10.1145/275487.275497, db/conf/pods/GarofalakisIOS98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Multimedia applications require a guaranteed level of service for accessing Continuous Media (CM) data, such as video and audio. To obtain such guarantees, the database server where the data is residing must employ an admission control scheme to limit the number of clients that can be served concurrently. We investigate the problem of on-line admission control where the decision on whether to accept or reject a request must be made without any knowledge about future requests. Employing competitive analysis techniques, we address the problem in its most general form with the following key contributions: (1) we prove a tight upper bound on the competitive ratio of the conventional Work-Conserving (WC) policy, showing that it is within a factor (1 + Delta)/(1- rho) of the optimal clairvoyant strategy that knows the entire request sequence in advance, where Delta is the ratio of the maximum to minimum request length (that is, time duration), and rho is the maximum fraction of the server's bandwidth that a request can demand; (2) we prove a lower bound of Omega((log Delta)/(1-rho)) on the competitive ratio of any deterministic or randomized admission control scheme, demonstrating an exponential gap between greedy and optimal on-line solutions; (3) we propose simple deterministic schemes based on the idea of bandwidth prepartitioning that guarantee competitive ratios within a small constant factor of log Delta (i.e., they are near-optimal) for sufficiently large server bandwidth; (4) we introduce a novel admission control policy that partitions the server bandwidth based on the expected popularities of different request lengths and present a set of preliminary experimental results that demonstrate the benefits of our policy compared to WC. We believe that our results offer new insights to other optimization problems that arise in CM data management, including data placement and load balancing in distributed CM databases.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1351 KB]

References

[1]
Sudhanshu Aggarwal, Juan A. Garay, Amir Herzberg: Adaptive Video on Demand. ESA 1995: 538-553 BibTeX
[2]
James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, Orli Waarts: On-line load balancing with applications to machine scheduling and virtual circuit routing. STOC 1993: 623-631 BibTeX
[3]
Baruch Awerbuch, Yossi Azar, Serge A. Plotkin: Throughput-Competitive On-Line Routing. FOCS 1993: 32-40 BibTeX
[4]
...
[5]
...
[6]
Yossi Azar, Andrei Z. Broder, Anna R. Karlin: On-Line Load Balancing. Theor. Comput. Sci. 130(1): 73-84(1994) BibTeX
[7]
Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber: Bandwidth allocation with preemption. STOC 1995: 616-625 BibTeX
[8]
...
[9]
...
[10]
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
[11]
Asit Dan, Dinkar Sitaram: An Online Video Placement Policy based on Bandwith to Space Ratio (BSR). SIGMOD Conference 1995: 376-385 BibTeX
[12]
Anwar Elwalid, Debasis Mitra, Robert H. Wentworth: A New Approach for Allocating Buffers and Bandwidth to Heterogeneous Regulated Traffic in an ATM Node. IEEE Journal on Selected Areas in Communications 13(6): 1115-1127(1995) BibTeX
[13]
...
[14]
...
[15]
Juan A. Garay, Inder S. Gopal, Shay Kutten, Yishay Mansour, Moti Yung: Efficient On-Line Call Control Algorithms. J. Algorithms 23(1): 180-194(1997) BibTeX
[16]
...
[17]
Minos N. Garofalakis, Banu Özden, Abraham Silberschatz: Resource Scheduling in Enhanced Pay-Per-View Continuous Media Databases. VLDB 1997: 516-525 BibTeX
[18]
...
[19]
...
[20]
...
[21]
...
[22]
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
[23]
...
[24]
Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press 1995, ISBN 0-521-47465-5
BibTeX
[25]
...
[26]
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Disk Striping in Video Server Environments. IEEE Data Eng. Bull. 18(4): 4-16(1995) BibTeX
[27]
...
[28]
Serge A. Plotkin: Competitive Routing of Virtual Circuits in ATM Networks. IEEE Journal on Selected Areas in Communications 13(6): 1128-1136(1995) BibTeX
[29]
P. Venkat Rangan, Harrick M. Vin: Designing File Systems for Digital Video and Audio. SOSP 1991: 81-94 BibTeX
[30]
Daniel Dominic Sleator, Robert Endre Tarjan: Amortized Efficiency of List Update and Paging Rules. Commun. ACM 28(2): 202-208(1985) BibTeX
[31]
...
[32]
Jeffery Westbrook: Load Balancing for Response Time. ESA 1995: 355-368 BibTeX
[33]
Gerhard J. Woeginger: On-Line Scheduling of Jobs with Fixed Start and End Times. Theor. Comput. Sci. 130(1): 5-16(1994) BibTeX
[34]
Joel L. Wolf, Philip S. Yu, Hadas Shachnai: DASD Dancing: A Disk Load Balancing Optimization Scheme for Video-on-Demand Computer. SIGMETRICS 1995: 157-166 BibTeX
[35]
George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:19 2009