 |
|
|
Throughput-Competitive Admission Control for Continuous Media Databases |
Full Paper (PDF)
Slides (PDF)
|
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. |
References, where available, link to the DBLP on the World Wide Web.
[1]Sudhanshu Aggarwal, Juan A. Garay, Amir Herzberg:
Adaptive Video on Demand.
ESA 1995: 538-553[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[3]Baruch Awerbuch, Yossi Azar, Serge A. Plotkin:
Throughput-Competitive On-Line Routing.
FOCS 1993: 32-40[4]...
[5]...
[6]Yossi Azar, Andrei Z. Broder, Anna R. Karlin:
On-Line Load Balancing.
TCS 130(1): 73-84(1994)[7]Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber:
Bandwidth Allocation with Preemption.
STOC 1995: 616-625[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[11]Asit Dan, Dinkar Sitaram:
An Online Video Placement Policy based on Bandwith to Space Ratio (BSR).
SIGMOD Conference 1995: 376-385[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 of Selected Areas in Communications 13(6): 1115-1127(1995)[13]...
[14]...
[15]Juan A. Garay, Inder Gopal, Shay Kutten, Yishay Mansour, Moti Yung:
Efficient On-Line Call Control Algorithms.
J. Algorithms 23(1): 180-194(1997)[16]...
[17]Minos N. Garofalakis, Banu Özden, Abraham Silberschatz:
Resource Scheduling in Enhanced Pay-Per-View Continuous Media Databases.
VLDB 1997: 516-525[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 Systems 2(6): 280-287(1995)[23]...
[24]Rajeev Motwani, Prabhakar Raghavan:
Randomized Algorithms.
Cambridge University Press 1995, ISBN 0-521-47465-5
[25]...
[26]Banu Özden, Rajeev Rastogi, Abraham Silberschatz:
Disk Striping in Video Server Environments.
Data Engineering Bulletin 18(4): 4-16(1995)[27]...
[28]Serge A. Plotkin:
Competitive Routing of Virtual Circuits in ATM Networks.
IEEE Journal of Selected Areas in Communications 13(6): 1128-1136(1995)[29]P. Venkat Rangan, Harrick M. Vin:
Designing File Systems for Digital Video and Audio.
SOSP 1991: 81-94[30]Daniel Dominic Sleator, Robert Endre Tarjan:
Amortized Efficiency of List Update and Paging Rules.
CACM 28(2): 202-208(1985)[31]...
[32]Jeffery Westbrook:
Load Balancing for Response Time.
ESA 1995: 355-368[33]Gerhard J. Woeginger:
On-Line Scheduling of Jobs with Fixed Start and End Times.
TCS 130(1): 5-16(1994)[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[35]George Kingsley Zipf:
Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology.
Addison-Wesley 1949
|
@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-966-3},
pages = {79-88},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
