A unified analysis of hot video schedulers
Wun-Tat Chan, Tak‐Wah Lam, Hing‐Fung Ting, Wai-Ha Wong · 2002
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.