"Competitive On-line Scheduling of Continuous-Media Streams"
Abstract
Multimedia applications require a guaranteed level of service for
accessing continuous-media data.
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,
where is the ratio of the maximum to minimum request length
(i.e., 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 provably near-optimal)
if ; and,
(4) we introduce a novel admission control policy that partitions the server
bandwidth based on the expected popularities of different request lengths and
experimentally demonstrate its benefits compared to WC.
Copyright © 2002, Academic Press.
This material has been published in the "Journal of Computer and Systems Sciences",
the only definitive repository of the content that has been certified and accepted
after peer review. Copyright and all rights therein are retained by Academic Press.
This material may not be copied or reposted without explicit permission.