Affordable Access

Publisher Website

The Dyadic Stream Merging Algorithm

Authors
Journal
Journal of Algorithms
0196-6774
Publisher
Elsevier
Publication Date
Volume
43
Issue
1
Identifiers
DOI: 10.1006/jagm.2002.1220
Keywords
  • Average-Case Analysis
  • Stream Merging
  • Video-On-Demand
Disciplines
  • Computer Science

Abstract

Abstract We study the stream merging problem for media-on-demand servers. Clients requesting media from the server arrive by a Poisson process, and delivery to the clients starts immediately. Clients are prepared to receive up to two streams at any time, one or both being fed into a buffer cache. We present an on-line algorithm, the dyadic stream merging algorithm, whose recursive structure allows us to derive a tight asymptotic bound on stream merging performance. In particular, let λ be the Poisson request arrival rate, and let L be the fixed media length. Then the long-time ratio of the expected total stream length under the dyadic algorithm to that under an algorithm with no merging is asymptotically equal to 3 log(λL) 2λL . Furthermore, we establish the near-optimality of the dyadic algorithm by comparisons with experimental results obtained for an optimal algorithm constructed as a dynamic program. The dyadic algorithm and the best on-line algorithm of those recently proposed differ by less than a percent in their comparison with an off-line optimal algorithm. Finally, the worst-case performance of our algorithm is shown to be no worse than that of earlier algorithms. Thus, the dyadic algorithm appears to be the first near optimal algorithm that admits a rigorous average-case analysis.

There are no comments yet on this publication. Be the first to share your thoughts.