Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Competitive on-line scheduling of continuous-media streams

Garofalakis Minos, Ioannidis, Yannis, Özden Banu , Silberschatz Avi

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/26624F19-FEBE-40A7-AA37-D80C07A8D93C-
Αναγνωριστικόhttp://dl.acm.org/citation.cfm?id=639543-
Αναγνωριστικόhttps://doi.org/10.1006/jcss.2001.1799-
Γλώσσαen-
Μέγεθος30 pagesen
ΤίτλοςCompetitive on-line scheduling of continuous-media streamsen
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςIoannidis, Yannisen
ΔημιουργόςÖzden Banu en
ΔημιουργόςSilberschatz Avien
ΕκδότηςAssociation for Computing Machineryen
ΠερίληψηMultimedia applications require a guaranteed level of service for accessing continuous-media data. To obtain such guarantees, the database server where the data are 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 of 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 (W/C) policy, showing that it is within a factor 1+Δ/1-ρ 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 Ω(log Δ\1-ρ) 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 Δ (i.e., they are provably near-optimal) if ρ < 1/⌈log Δ⌉ 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 W C.el
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-10-29-
Ημερομηνία Δημοσίευσης2002-
Θεματική ΚατηγορίαAlgorithmsen
Βιβλιογραφική ΑναφοράM. Garofalakis, Y. Ioannidis, B. Özden and A. Silberschatz, "Competitive on-line scheduling of continuous-media streams", J. Comput. Syst. Sci., vo. 64, no. 2, pp. 219-248, Mar. 2002. doi:10.1006/jcss.2001.1799en

Υπηρεσίες

Στατιστικά