Minimizing Bandwidth Requirements for On-Demand Data Delivery

Authors: Derek Eager, Mary Vernon, John Zahorjan

Complete Citation

Minimizing Bandwidth Requirements for On-Demand Data Delivery. Eager, Derek., Vernon, Mary., Zahorjan, John., IEEE Transactions on Knowlege and Data Engineering, 2001.

Abstract

Recent techniques for multicast or broadcast delivery of streaming media can provide immediate service to each client request yet achieve considerable client stream sharing (i.e., server and network bandwidth savings). This paper considers (1) the maximum savings in the required server (disk I/O and network) bandwidth that any such technique can provide, (2) the interplay between achievable reductions in required server bandwidth and available client receive bandwidth, (3) how well the previously proposed techniques perform relative to each other and to the minimum required server bandwidth for the assumed client capabilities, and (4) whether there are new practical delivery techniques that can achieve better server bandwidth savings than the previous techniques, yet still provide immediate service to client requests.
The principal results are as follows. First, we derive the minimum required server bandwidth for any delivery technique that provides immediate service to client requests, and find that this bandwidth grows logarithmically with the client request arrival rate. Second, we show that the minimum required server bandwidth can be nearly achieved if clients have receive bandwidth equal to three times the streaming rate and have sufficient storage for buffering data from shared streams. Third, we show that a particular implementation of the recently proposed partitioned dynamic skyscraper delivery technique provides immediate service to client requests more simply and directly than the original dynamic skyscraper method. Fourth, the recently proposed optimized stream tapping/grace patching/controlled multicast technique achieves nearly the minimum server bandwidth requirement at low client request rates, but the partitioned dynamic skyscraper delivery method has significantly lower server bandwidth requirements than optimized grace patching at moderate to high client request rates. Furthermore, the dynamic skyscraper technique has required server bandwidth within a small constant factor of the minimum required bandwidth, assuming sufficient client buffering capability. Finally, we propose a new practical delivery technique, namely hierarchical multicast stream merging, that has required server bandwidth significantly lower than for optimized grace patching or partitioned dynamic skyscraper, and close to the minimum achievable when client receive bandwidth is twice the streaming rate.

Annotations

The abstract provides a little information on this paper itself, I will focus on briefly explaining the streaming mechanisms described.
Controlled Multicast, an optimization of Grace Patching, works by, at regular intervals, beginning a full multicast stream for a requester of a given file. Any requests received between those intervals of new multicast streams is added to the stream preceding it, and also receives a unicast "patch" stream to catch it up on what it missed for having arrived late.
The second model described, the sky-scraper, works by having each file broken into K segments of increasing size. A multicast channel is formed for each segment, and that channel repeated broadcasts that segment. I listener may obtain a steady stream of data by hopping from one channel to the next as it progresses through the file. See the diagram below for details.
The novel aspect of this paper is a minor change to the skyscraper model that allows faster service to clients in the second model.
For TailSync? , this paper provides an excellent overview of other techniques in the field, as well as numerous useful references to recent work relating to streaming and multicast file transfers.

-- DavidMoore - 3 Oct 2007