Quality of service evaluations of multicast streaming protocols

ABSTRACT

Recently proposed scalable on-demand streaming protocols have previously been evaluated using a system cost measure termed the "required server bandwidth". For the scalable protocols that provide immediate service to each client when the server is not overloaded, this paper develops simple analytic models to evaluate two client-oriented quality of service metrics, namely (1) the mean client waiting time in systems where clients are willing to wait if a (well-provisioned) server is temporarily overloaded, and (2) the fraction of clients who balk (i.e., leave without receiving their requested media content) in systems where the clients will tolerate no or only very low service delays during a temporary overload. The models include novel approximate MVA techniques that appear to extend the range of applicability of customized AMVA to include questions focussed on state probabilities rather than on mean values, and to systems in which the operating points of interest do not include substantial client queues. For example, the new AMVA models accurately estimate the server bandwidth needed to achieve a balking rate as low as one in ten thousand. The analytic models can easily be applied to determine the server bandwidth needed for a given number of media files, anticipated total client request rate and file access frequencies, and target balking rate or mean wait. Results show that (a) scalable media servers that are configured with the "required server bandwidth" defined in previous work have low mean wait but may have unacceptably high client balking rates (i.e., greater than one in twenty), (b) for high to moderate client load, only a 10 - 50% increase in the previously defined required server bandwidth is needed to achieve a very low balking rate (e.g., one in ten thousand), and (c) media server performance (either mean wait or balking rate) degrades rapidly if the actual client load is more than 10% greater than the anticipated load.

REFERENCES

• 1: Yonathan Bard, A model of shared DASD and multipathing, Communications of the ACM, v.23 n.10, p.564-572, Oct. 1980 [doi>10.1145/359015.359019]
• 2: Y. Bard, "A Simple Approach to System Modeling", Performance Evaluation 1, 3 (Aug. 1981), pp. 225-248.
• 3: A. Bar-Noy, G. Goshi, R. E. Ladner, and K. Tam, "Comparison of Stream Merging Algorithms for Media-on-Demand", Proc. MMCN 2002, San Jose, CA, Jan. 2002.
• 4: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 5: 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
• 6: Y. Cai, K. A. Hua, and K. Vu, "Optimizing Patching Performance", Proc. MMCN '99, San Jose, CA, Jan. 1999.
• 7: E. G. Coffman, Jr., P. Jelenkovic, and P. Momcilovic, "Provably Efficient Stream Merging", Proc. 6th Int'l. Workshop on Web Caching and Content Distribution, Boston, MA, June 2001.
• 8: Asit Dan , Perwez Shahabuddin , Dinkar Sitaram , Don Towsley, Channel allocation under batching and VCR control in video-on-demand systems, Journal of Parallel and Distributed Computing, v.30 n.2, p.168-179, Nov. 1, 1995 [doi>10.1006/jpdc.1995.1135]
• 9: 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
• 10: D. L. Eager, M. K. Vernon and J. Zahorjan, "Bandwidth Skimming: A Technique for Cost-Effective Video-on-Demand", Proc. MMCN 2000, San Jose, CA, Jan. 2000.
• 11: 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]
• 12: 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]
• 13: L. Gao, J. Kurose, and D. Towsley, "Efficient Schemes for Broadcasting Popular Videos", Proc. NOSSDAV '98, Cambridge, UK, July 1998.
• 14: 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
• 15: A. Hu, "Video-on-Demand Broadcasting Protocols: A Comprehensive Study", Proc. IEEE Infocom 2001, Anchorage, AL, Apr. 2001.
• 16: 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]
• 17: 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
• 18: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 19: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 20: J. F. Paris, S. W. Carter, and D. D. E. Long, "A Hybrid Broadcasting Protocol for Video on Demand", Proc. MMCN '99, San Jose, CA, Jan. 1999.
• 21: P. Schweitzer, "Approximate Analysis of Multiclass Closed Networks of Queues", International Conference on Stochastic Control and Optimization, Amsterdam, Netherlands, 1979.
• 22: S. Sen, L. Gao, J. Rexford, and D. Towsley, "Optimal Patching Schemes for Efficient Multimedia Streaming", Proc. NOSSDAV '99, Basking Ridge, NJ, June 1999.
• 23: S. Viswanathan , T. Imielinski, Metropolitan area video-on-demand service using pyramid broadcasting, Multimedia Systems, v.4 n.4, p.197-208, Aug. 1996 [doi>10.1007/s005300050023]