Scalability of multicast delivery for non-sequential streaming access

ABSTRACT

To serve asynchronous requests using multicast, two categories of techniques---stream merging and periodic broadcasting---have been proposed. For sequential streaming access, where requests are uninterrupted from the beginning to the end of an object, these techniques are highly scalable: the required server bandwidth for stream merging grows logarithmically as request arrival rate, and the required server bandwidth for periodic broadcasting varies logarithmically as the inverse of start-up delay. A sequential access model, however, is inappropriate to model partial requests and client interactivity observed in various streaming access workloads. This paper analytically and experimentally studies the scalability of multicast delivery under a non-sequential access model where requests start at random points in the object. We show that the required server bandwidth for any protocol providing immediate service grows at least as the square root of request arrival rate, and the required server bandwidth for any protocol providing delayed service grows linearly with the inverse of start-up delay. We also investigate the impact of limited client receiving bandwidth on scalability. We optimize practical protocols which provide immediate service to non-sequential requests. The protocols utilize limited client receiving bandwidth, and they are near-optimal in that the required server bandwidth is very close to its lower bound.

REFERENCES

• 1: Emmanuel L. Abram-Profeta , Kang G. Shin, Providing Unrestricted VCR Functions in Multicast Video-on-Demand Servers, Proceedings of the IEEE International Conference on Multimedia Computing and Systems, p.66, June 28-July 01, 1998 [doi>10.1109/MMCS.1998.693626]
• 2: Charu Aggarwal , Joel Wolf , Philip S. Yu, On optimal piggyback merging policies for video-on-demand systems, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.200-209, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 3: C. C. Aggarwal, J. L. Wolf, and P. S. Yu. A permutation-based pyramid broadcasting scheme for video-on-demand systems. In Proceedings of ICMCS, 1996.
• 4: Jussara M. Almeida , Jeffrey Krueger , Derek L. Eager , Mary K. Vernon, Analysis of educational media server workloads, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.21-30, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378348]
• 5: K. C. Almeroth and M. H. Ammar. The use of multicast delivery to provide a scalable and interactive video-on-demand service. IEEE Journal on Selected Areas in Communications, 14:1110-1122, 1996.
• 6: A. Bar-Noy, J. Goshi, R. E. Ladner, and K. Tam. Comparison of stream merging algorithms for media-on-demand. In Proceedings of MMCN, January 2002.
• 7: Amotz Bar-Noy , Richard E. Ladner, Competitive on-line stream merging algorithms for media-on-demand, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 07-09, 2001, Washington, D.C., United States
• 8: Ying Cai , Kien A. Hua, An efficient bandwidth-sharing technique for true video on demand systems, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.211-214, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319607]
• 9: Y. Cai, K. A. Hua, and K. Vu. Optimizing patching performance. In Proceedings of MMCN, 1999.
• 10: Steven W. Carter , Darrell D. E. Long, Video-on-Demand Server Efficiency through Stream Tapping, Proceedings of the 6th International Conference on Computer Communications and Networks, p.200, September 22-25, 1997
• 11: Steven W. Carter , Darrell D. E. Long , Jehan-François Pâris, An Efficient Implementation of Interactive Video-on-Demand, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.172, August 29-September 01, 2000
• 12: M. Chesire, A. Wolman, G. Voelker, and H. Levy. Measurement and analysis of a streaming workload. In Proceedings of USITS, March 2001.
• 13: T. Chiueh and C. Lu. A periodic broadcasting approach to video-on-demand service. In Proceedings of MMCN, 1995.
• 14: E. G. Coffman, J. P. Jelenhovic, and P. Momcilovic. Provably efficient stream merging. In Proceedings of Web Caching Workshop, June 2001.
• 15: Asit Dan , Dinkar Sitaram , Perwez Shahabuddin, Dynamic batching policies for an on-demand video server, Multimedia Systems, v.4 n.3, p.112-121, June 1996 [doi>10.1007/s005300050016]
• 16: Derek L. Eager , Mary K. Vernon, Dynamic Skyscraper Broadcasts for Video-on-Demand, Proceedings of the 4th International Workshop on Advances in Multimedia Information Systems, p.18-32, September 24-26, 1998
• 17: D. Eager, M. Vernon, and J. Zahorjan. Minimizing bandwidth requirements for on-demand data delivery. In Proceedings of MIS, 1998.
• 18: Derek Eager , Mary Vernon , John Zahorjan, Optimal and efficient merging schedules for video-on-demand servers, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.199-202, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319601]
• 19: D. Eager, M. Vernon, and J. Zahorjan. Bandwidth skimming: A technique for cost-efficient video-on-demand. In Proceedings of MMCN, January 2000.
• 20: Derek Eager , Mary Vernon , John Zahorjan, Minimizing Bandwidth Requirements for On-Demand Data Delivery, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.742-757, September 2001 [doi>10.1109/69.956098]
• 21: L. Gao and D. Towsley. Efficient schemes for broadcasting popular videos. In Proceedings of NOSSDAV, June 1998.
• 22: Lixin Gao , Don Towsley, Supplying Instantaneous Video-on-Demand Services Using Controlled Multicast, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.117, June 07-11, 1999
• 23: Leana Golubchik , John C. S. Lui , Richard Muntz, Reducing I/O demand in video-on-demand storage servers, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.25-36, May 15-19, 1995, Ottawa, Ontario, Canada
• 24: Leana Golubchik , John C. S. Lui , Richard R. Muntz, Adaptive piggybacking: a novel technique for data sharing in video-on-demand storage servers, Multimedia Systems, v.4 n.3, p.140-155, June 1996 [doi>10.1007/s005300050019]
• 25: N. Harel, V. Vellanki, A. Chervenak, G. Abowd, and U. Ramachandran. Workload of a media-enhanced classroom server. In Proceedings of Workshop on Workload Characterization, 1999.
• 26: A. Hu. Video-on-demand broadcasting protocols: A comprehensize study. In Proceedings of INFOCOM, April 2001.
• 27: Kien A. Hua , Ying Cai , Simon Sheu, Patching: a multicast technique for true video-on-demand services, Proceedings of the sixth ACM international conference on Multimedia, p.191-200, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290771]
• 28: Kien A. Hua , Simon Sheu, Skyscraper broadcasting: a new broadcasting scheme for metropolitan video-on-demand systems, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.89-100, September 14-18, 1997, Cannes, France
• 29: L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, 44(1):100-105, 1998.
• 30: Siu-Wah Lau , John C. S. Lui , Leana Golubchik, Merging video streams in a multimedia storage server: complexity and heuristics, Multimedia Systems, v.6 n.1, p.29-42, Jan. 1998 [doi>10.1007/s005300050074]
• 31: V. O. Li, W. Liao, X. Qiu, and E. Wong. Performance model of interactive video-on-demand systems. IEEE Journal on Selected Areas in Communications, 14:1099-1109, 1996.
• 32: Wanjiun Liao , Victor O. K. Li, The Split and Merge Protocol for Interactive Video-on-Demand, IEEE MultiMedia, v.4 n.4, p.51-62, October 1997 [doi>10.1109/93.641879]
• 33: Anirban Mahanti , Derek L. Eager , Mary K. Vernon , David Sundaram-Stukel, Scalable on-demand media streaming with packet loss recovery, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.97-108, August 2001, San Diego, California, United States
• 34: J. Padhye and J. Kurose. An empirical study of client interactions with a continuous-media courseware server. In Proceedings of NOSSDAV, June 1998.
• 35: J. Paris. An interactive broadcasting protocol for video-on-demand. In Proceedings of IPCCC, April 2001.
• 36: Jehan-Francois Pâris , Steven W. Carter , Darrell D. E. Long, Efficient Broadcasting Protocols for Video on Demand, Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.127, July 19-24, 1998
• 37: A Low Bandwidth Broadcasting Protocol for Video on Demand, Proceedings of the International Conference on Computer Communications and Networks, p.690, October 12-15, 1998
• 38: J. Paris, S. W. Carter, and D. D. E. Long. A hybrid broadcasting protocol for video on demand. In Proceedings of MMCN, 1999.
• 39: J. Paris, S. W. Carter, and D. D. E. Long. A reactive broadcasting protocol for video on demand. In Proceedings of MMCN, January 2000.
• 40: Jehan-François Pâris , Darrell D. E. Long , Patrick E. Mantey, Zero-delay broadcasting protocols for video-on-demand, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.189-197, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319600]
• 41: S. Sen, L. Gao, J. Rexford, and D. Towsley. Optimal patching schemes for efficient multimedia streaming. In Proceedings of NOSSDAV, June 1999.
• 42: S. Sen, L. Gao, and D. Towsley. Frame-based periodic broadcast and fundamental resource tradeoffs. In Proceedings of IPCCC, April 2001.
• 43: S. Viswanathan and T. Imielinski. Pyramid broadcasting for video on demand service. In Proceedings of MMCN, 1995.
• 44: Y. Zhao, D. Eager, and M. Vernon. Efficient delivery techniques for variable bit rate multimedia. In Proceedings of MMCN, January 2002.