Please use this identifier to cite or link to this item:
Title: A unified analysis of hot video schedulers
Authors: Chan, WT
Lam, TW
Ting, HF
Wong, WH
Issue Date: 2002
Source: STOC '02 Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, May 19-21, 2002, p. 179-188 How to cite?
Abstract: In this paper we consider the notion of relative competitive analysis, which is a simple generalization of the conventional competitive analysis and extra-resource analysis for on-line algorithms. We apply this analysis to study on-line schedulers for stream merging in two different video-on-demand (VOD) systems, which are based on two common approaches, namely, piggybacking and skimming. Our new analysis, in its simplest form, reveals a 3-competitive algorithm for stream merging based on skimming as well as piggybacking. This improves all previous results [4, 8]. We also show how to obtain guarantee on the performance improvement based on adding extra resources, and more interestingly, we provide a unified methodology to compare piggybacking and skimming. We believe that our result gives a clue to system designers for choosing desirable configurations.
ISBN: 1-58113-495-9
DOI: 10.1145/509907.509937
Appears in Collections:Conference Paper

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Jan 14, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.