Back to search

University of Washington

Scheduling protocols for media-on-demand systems

Abstract

dc:description.abstract

Today's abundance of personal electronic devices and the growth of communications networks gives rise to a new set of applications. One such application allows clients to access high-bandwidth streaming media at times of their choosing. The focus of this dissertation is on the media-on-demand application for use in high-bandwidth communications networks. A media-on-demand server stores and distributes one or more media files to clients who wish to view/play them. Because server bandwidth can be quickly consumed when delivering the full media file to each client under high loads, protocols for delivering streaming media try to reduce the server bandwidth used to satisfy client requests. Our work focuses on the stream merging technique, where clients can receive two streams simultaneously and buffer data for future parts of the media file. When clients have the same data as other clients in the system, we merge the clients into a single group and eliminate unnecessary streams. This dissertation introduces, analyzes, and empirically compares algorithms for three media-on-demand models. The first model, which we call media-on-demand, assumes the media file requested is of finite length and clients always consume the media file from its beginning. The second model, media-on-demand with time-shifting, supports access to any portion of a live broadcasted stream. Our contributions include devising an algorithm for media-on-demand systems under high client loads, modeling media-on-demand with time-shifting as a rectilinear tree, finding the complexity class for the optimal offline solution to media-on-demand with time-shifting, and introducing an online algorithm for the time-shifting case. Finally, we introduce a network cost model where we try to optimize the network bandwidth instead of the server bandwidth. We describe an algorithm to compute the network cost given a stream merging schedule and introduce an online stream merging algorithm for the network cost model.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • VanDeGrift, Tammy

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright is held by the individual authors.
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Other
b54313478
63934498
Thesis 55058

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

VanDeGrift, Tammy. Scheduling protocols for media-on-demand systems. 2005. http://hdl.handle.net/1773/6868