Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/631575F9-96CE-47A5-AD98-AA0A97BE0108 | ||
| Year | 1998 | ||
| Type of Item | Conference Publication | ||
| License |
|
||
| Bibliographic Citation | M. Garofalakis, Y. Ioannidis, B. Ozden and A. Silberschatz, "Throughput-competitive admission control for continuous media databases", in Conference SIGMOD/PODS98 Special Interest Group on Management of Data (SIGMOD)/Principles of Data Base Systems (PODS), June 1998, pp. 79-88. | ||
| Appears in Collections |
Multimedia applications require a guaranteed level of servicefor accessing Continuous Media (CM) data, such as videoand audio. To obtain such guarantees, the database serverwhom the data is residing must employ an admission controlschomo to limit the number of clients that can be served concurrently,We investigate the problem of on-line admissioncontrol where the decision on whether to accept or reject arequest must bc made without any knowledge about futurercqucsts. Employing competitive analysis techniques, we addressthe problem in its most general form with the followingkey contributions: (1) we prove a tight upper bound onthe competitive ratio of the conventional Work-Conserving(WC) policy, showing that it is within a factor e of theoptimal clairvoyant strategy that knows the entire requestscquoncc in advance, where A is the ratio of the maximumto minimum request length (that is, time duration), and pis the maximum fraction of the server’s bandwidth that arcqucst can demand; (2) we prove a lower bound of Q(s)on tho competitive ratio of any deterministic or randomizedadmission control scheme, demonstrating an exponentialgap bctwccn greedy and optimal on-line solutions; (3)WC propose simple deterministic schemes based on the ideaof lrandwidth prepartitioning that guarantee competitive ratioswithin a small constant factor of log A (i.e., they arenear-optimal) for sufficiently large server bandwidth; (4) weintroduce a novel admission control policy that partitionstha scrvcr bandwidth based on the expected popularities ofdifferent request lengths and present a set of preliminarycxpcrimontal results that demonstrate the benefits of ourpolicy compared to WC. We believe that our results offernew insights to other optimization problems that arise inCM data management, including data placement and loadbnlancing in distributed CM databases.
Copyright © DIAS 2013
