Minimizing Bandwidth Requirements for On-Demand Data Delivery

Authors: Derek Eager, Mary Vernon, John Zahorjan

Complete Citation

Derek Eager, Mary Vernon, and John Zahorjan. Minimizing Bandwidth Requirements for On-Demand Data Delivery. IEEE Transactions on Knowledge and Data Engineering, Volume 13, Issue 5, Sept.-Oct. 2001 Page(s):742 - 757 Digital Object Identifier 10.1109/69.956098

Abstract

Two recent techniques for multicast or broadcast delivery of streaming media can provide immediate service to each client request, yet achieve considerable client stream sharing which leads to significant server and network bandwidth savings. The paper considers: 1) how well these recently proposed techniques perform relative to each other and 2) whether there are new practical delivery techniques that can achieve better bandwidth savings than the previous techniques over a wide range of client request rates. The principal results are as follows: First, the recent partitioned dynamic skyscraper technique is adapted to provide immediate service to each client request more simply and directly than the original dynamic skyscraper method. Second, at moderate to high client request rates, the dynamic skyscraper method has required server bandwidth that is significantly lower than the recent optimized stream tapping/patching/controlled multicast technique. Third, the minimum required server bandwidth for any delivery technique that provides immediate real-time delivery to clients increases logarithmically (with constant factor equal to one) as a function of the client request arrival rate. Furthermore, it is (theoretically) possible to achieve very close to the minimum required server bandwidth if client receive bandwidth is equal to two times the data streaming rate and client storage capacity is sufficient for buffering data from shared streams. Finally, we propose a new practical delivery technique, called hierarchical multicast stream merging (HMSM), which has a required server bandwidth that is lower than the partitioned dynamic skyscraper and is reasonably close to the minimum achievable required server bandwidth over a wide range of client request rates

Annotations

This paper proposed a technique for multicast delivery of streaming media, called hierarchical multicast stream merging (HMSM). The HMSM technique attempts to capture the advantages of dynamic skyscraper and piggybacking, as well as the strengths of stream tapping/patching.

• Skyscraper and dynamic skyscraper delivery: a file is divided into K increasing-sized segments. Each segment is continuously broadcast at the file play rate on its own channel. Then, each client is given a schedule for tuning into each of the K channels to receive each of the file segments.
  

• Piggybacking: dynamically speed up and slow down client processing rate so as to bring different streams to the same file position. The streams then can be merged.

• Stream tapping/patching: When a client submits a new request for a file, if the server is delivering the requested file in a multicast, the client begins listening to the multicast, buffering the data received. The client is also provided a new unicast stream (i.e., a patch stream) that sends the data that was delivered in the multicast stream prior to the new client's request. The patch stream terminates when it reaches the point that the client joined the full-file multicast.

• Proposed scheme: clients that request the same file are repeatedly merged into larger and larger groups, leading to a hierarchical merging structure (as in dynamic skyscraper or piggybacking). Furthermore, clients are merged using dynamically scheduled patch streams (as in stream tapping/patching).

• Example of hierarchical multicast stream merging:
  

-- YingxinJiang - 03 Oct 2007