On-line scheduling of video streams

by Wong, Wai-ha

Abstract (Summary)
(Uncorrected OCR) Abstract of Thesis Entitled "On-line Scheduling of Video Streams" Submitted by Wong Wai Ha For the Degree of Doctor of Philosophy at The University of Hong Kong in August 2002 In a video-on-demand (VOD) system, a client can request a video at any time and the video server has to serve the request immediately (say, within 10 seconds) by delivering high quality video data in a continuous manner. Advances in technologies such as high-speed networks and optical storage have made VOD feasible. Yet there is still a concern o the huge bandwidth requirement. A typical scenario is that a popular video is requested by a large number o clients over a short period o time (say, Friday 7 p.m. to 9 p.m.). Many video streams, initiated at different times, are required to deliver the video in parallel. This demands a huge server bandwidth. Stream merging is a technology to reduce the bandwidth requirement. There are two approaches to enable stream merging: piggybacking and skimming. To adopt either approach, an on-line scheduling algorithm is needed to determine an effective schedule in real time. This thesis investigates on-line scheduling algorithms for piggybacking and skimming with an objective to minimize the total bandwidth or the maximum bandwidth. The contribution o this thesis includes the first on-line algorithm for skimming that can handle an arbitrary client bandwidth and buffer size, and the first on-line algorithm for piggybacking that can handle an arbitrary rate. These on-line algorithms are proven mathematically to be very effective even in the worst case; precisely, they are the first on-line algorithms known to be (l)competitive for skimming and piggybacking, respectively. Another contribution is a systematic approach to adapt our on-line algorithms for piggybacking and skimming that can exploit extra resources to obtain a better performance guarantee. This thesis quantifies how much the performance can be improved by extra resources. From a methodological perspective, this thesis introduces the notion o relative competitive analysis, which is a generalization o the conventional competitive analysis and extra-resource analysis. Both piggybacking and skimming can reduce bandwidth, yet it has not been known before which approach is more effective.

This thess apples relatve competve analyss to compare piggybacking and skimming and quantify the amount o resources required for skimming to match the performance o piggybacking and vice versa.

Bibliographical Information:


School:The University of Hong Kong

School Location:China - Hong Kong SAR

Source Type:Master's Thesis

Keywords:streaming technology telecommunications computer algorithms interactive multimedia


Date of Publication:01/01/2003

© 2009 All Rights Reserved.