Theory Lunch , April 14, 12:05pm.
Computer Science Dept Room 402.
Algorithms for On-Demand Stream Merging
Richard E. Ladner
University of Washington and AT&T Shannon Labs
| As the Internet grows so does the desire for on-demand streams of many
types: movies, songs, news stories, stock quotes, and others. The popularity of a specific
stream may be so high that multicasting may be the only way to satisfy the demand. In
addition, clients requesting a stream will want service as quickly as possible. This may
require repeated multicasts of the same streamto satisfy the delay guarantees. Stream
merging has the potential to help solve the bandwidth problems created by heavy, low
delay, demand for the same stream. In this talk we describe the stream mergingtechnique
and how it can be used to reduce bandwidth requirements at the stream server. We describe
a new quadratic off-line algorithm for minimizing bandwidth. We describe the optimal
solution for the fully loaded case, where streams are requested at unit time intervals. We analyze the approximation ratio for oblivious off-line algorithms that only know the number of requests and not their arrival times. Finally, we briefly describe a new approach to on-line stream merging based on our optimal oblivious offline algorithm. It turns out that the Fibonacci numbers play an important role in the analysis. This research is jointly done with Amotz Bar-Noy. |