"Throughput-Competitive Admission Control for Continuous Media Databases"
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 of
of the optimal clairvoyant strategy that knows the entire request sequence in
advance, where is the ratio of the maximum to minimum
request length (that is, time duration), and
is the maximum fraction of the server's
bandwidth that a request can demand;
(2) we prove a lower bound of
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 (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, Association for Computing Machinery, Inc. (ACM).
Permission to make digital/ hard copy of all or part of this material without
fee is granted provided that copies are not made or distributed for profit or
commercial advantage, the ACM copyright/server notice, the title of the
publication and its date appear, and notice is given that copying is by
permission of the Association for Computing Machinery, Inc. (ACM).
To copy otherwise, to republish, to post on servers or to redistribute to lists,
requires prior specific permission and/or a fee.