Selecting among replicated batching video-on-demand servers

ABSTRACT

A Video-on-Demand (VoD) service offers a large selection of videos from which customers can choose. Designers of VoD systems strive to achieve low access latency for customers. One approach that has been investigated by several researchers allows the server to batch clients requesting the same video and to serve clients in the same batch with one multicast video stream. This approach has the advantage that it can save server resources as well as server access and network bandwidth, thus allowing the server to handle a large number of customers without sacrificing access latency. VoD server replication is another approach that can allow a VoD service to handle a large number of clients, albeit at the additional cost of providing more servers. While replication is an effective way to increase the service capacity, it needs to be coupled with appropriate selection techniques in order to make efficient use of the increased capacity. In this paper, we investigate the design of server selection techniques for a system of replicated batching VoD servers. We design and evaluate a range of selection algorithms as they would be applied to three batching approaches: Batching with Persistent Channel Allocation, Patching, and Hierarchical Multicast Stream Merging (HMSM). We demonstrate that server replication combined with appropriate server selection scheme can indeed be used to increase the capacity of the service leading to improved performance.

REFERENCES

• 1: On Optimal Batching Policies for Video-on-Demand Storage Servers, Proceedings of the 1996 International Conference on Multimedia Computing and Systems (ICMCS '96), p.0253, June 17-23, 1996
• 2: K. Almeroth and M.Ammar. On the Use of Multicast Delivery to Provide a Scalable and Interactive Video-on-Demand Service. In Journal on Selected Areas of Communication, August 1996.
• 3: K. Calvert, M. Doar, and E. Zegura. Modeling Internet topology. IEEE Communications Magazine, June 1997.
• 4: Robert L. Carter , Mark E. Crovella, Server Selection Using Dynamic Path Characterization in Wide-Area Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1014, April 09-11, 1997
• 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: A. Dan , D. Sitaram , P. Shahabuddin, Scheduling policies for an on-demand video server with batching, Proceedings of the second ACM international conference on Multimedia, p.15-23, October 15-20, 1994, San Francisco, California, United States [doi>10.1145/192593.192614]
• 7: H.D. Dykeman, M.H. Ammar, J.W. Wong. Scheduling algorithms for Videotex systems under Broadcast Delivery. In Proceedings of ICC'86.
• 8: 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
• 9: 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]
• 10: 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]
• 11: Z. Fei, S. Bhattacharjee, E. W. Zegura, and M. H. Ammar. A novel server selection technique for improving the response time of a replicated service. In Proceedings of IEEE INFOCOM, 1998.
• 12: Zongming Fei , Mostafa H. Ammar , Ellen W. Zegura, Optimal Allocation of Clients to Replicated Multicast Servers, Proceedings of the Seventh Annual International Conference on Network Protocols, p.69, October 31-November 03, 1999
• 13: Z. Fei, M. Ammar, E. Zegura. Efficient Server Replication and Client Re-Direction for Multicast Services. In Proceedings of SPIE/ITCOM Conference on Scalability and Traffic Control in IP Networks, August 2001.
• 14: Z. Fei, M. Ammar, E. Zegura. Multicast Server Selection: Problems, Complexity and Solutions. To appear in IEEE Journal on Selected Areas in Communication.
• 15: 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
• 16: L. Gao, D. Towsley. Threshold-Based Multicast for Continuous Media Delivery In IEEE Transactions on Multimedia, Dec. 2001
• 17: 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
• 18: 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
• 19: 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]
• 20: J. Veizades, E. Guttman, C. Perkins, and S. Kaplan. Service location protocol. RFC 2165, June 1997.
• 21: 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]
• 22: Ellen W. Zegura , Mostafa H. Ammar , Zongming Fei , Samrat Bhattacharjee, Application-layer anycasting: a server selection architecture and use in a replicated Web service, IEEE/ACM Transactions on Networking (TON), v.8 n.4, p.455-466, Aug. 2000 [doi>10.1109/90.865074]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Algorithms, Design

Keywords:
batching, server selection, video on demand