首页 | 本学科首页   官方微博 | 高级检索  
     


Optimal smoothing schedules for real-time streams
Authors:Email author" target="_blank">Yishay?MansourEmail author  Boaz?Patt-Shamir  Ofer?Lapid
Affiliation:(1) Department of Computer Science, Tel-Aviv University, 69978 Tel-Aviv, Israel;(2) Deptartment of Electrical Engineering, Tel-Aviv University, 69978 Tel-Aviv , Israel
Abstract:We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable-bandwidth stream remotely, while minimizing bandwidth cost, space requirement, and playback delay. We focus on lossy schedules, where data may be dropped due to limited bandwidth or space. We present the following results. First, we determine the optimal tradeoff between buffer space, smoothing delay, and link bandwidth for lossy smoothing schedules. Specifically, this means that if two of these parameters are given, we can precisely calculate the value for the third which minimizes data loss while avoiding resource wastage. The tradeoff is accomplished by a simple generic algorithm, that allows one some freedom in choosing which data to discard. This algorithm is very easy to implement both at the server and at the client, and it enjoys the nice property that only the server decides which data to discard, and the client needs only to reconstruct the stream.In a second set of results we study the case where different parts of the data have different importance, modeled by assigning a real ldquoweightrdquo to each packet in the stream. For this setting we use competitive analysis, i.e., we compare the weight delivered by on-line algorithms to the weight of an optimal off-line schedule using the same resources. We prove that a natural greedy algorithm is 4-competitive. We also prove a lower bound of 1.23 on the competitive ratio of any deterministic on-line algorithm. Finally, we give a few experimental results which seem to indicate that smoothing is very effective in practice, and that the greedy algorithm performs very well in the weighted case.Received: 21 November 2001, Accepted: 6 November 2003, Published online: 6 February 2004Research supported in part by Israel Ministry of Science. An extended abstract of this paper appeared in Proc. 19th ACM Symp. on Principles of Distributed Computing, July 2000.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号