The effectiveness of intelligent scheduling for multicast video-on-demand

ABSTRACT

As more and more video content is made available and accessed on-demand, content and service providers face challenges of scale. Today's delivery mechanisms, especially unicast, require resources to scale linearly with the number of receivers and library sizes. Unlike these mechanisms, with multicast, the load on a server is relatively independent of the number of receivers. Adopting multicast for on-demand access, however, is challenging because of the need to temporally aggregate requests. In this paper, we investigate the importance of an intelligent scheduler and a good data model for achieving good aggregation of requests into multicast groups. We examine the use of an Earliest Deadline First (EDF)-like scheduler that aims to schedule the transmission of "chunks" of video according to their "deadlines" using multicast. We show through analysis that this approach is optimal in terms of the data transmitted by the server. Using trace data from an operational service, we show that our approach reduces server bandwidth by as much as 65% compared to traditional techniques such as unicast and cyclic multicast. Finally, our approach achieves good aggregation even when 50% of the users use a typical VoD stream-control function like skip, to view different parts of the video.

REFERENCES

• 1: S. Acharya, B. Smith, and P. Parnes. Characterizing User Access To Videos On The World Wide Web. In Proc. of MMCN, San Jose, CA, January 2000.
• 2: C. C. Aggarwal, J. L. Wolf, and P. S. Yu. On Optimal Batching Policies for Video-on-Demand Storage Servers. In Proc. of IEEE ICMCS, Hiroshima, Japan, June 1996.
• 3: K. V. Almeroth, M. H. Ammar, and Z. Fei. Scalable Delivery of Web Pages Using Cyclic Best-Effort Multicast. In Proc. of IEEE INFOCOM, San Francisco, CA, March 1998.
• 4: M. Cha, H. Kwak, P. Rodriguez, Y.-Y. Ahn, and S. Moon. I Tube, You Tube, Everybody Tubes: Analyzing the World's Largest User Generated Content Video System. In Proc. of ACM IMC, San Diego, CA, October 2007.
• 5: Y. Chai, Z. Du, and S. Li. A New Scheduling Algorithm for Distributed Streaming Media System based on Multicast. In Proc. of ICDCS Workshops, Beijing, China, June 2008.
• 6: X. Cheng, C. Dale, and J. Liu. Statistics and Social Network of YouTube Videos. In Proc. of IWQoS, Enschede, Netherlands, June 2008.
• 7: B. Cohen. Incentives to Build Robustness in BitTorrent. In Proc. of P2PECON, Berkeley, CA, June 2003.
• 8: A. Dan, D. Sitaram, and P. Shahabuddin. Scheduling Policies for an On-Demand Video Server with Batching. In Proc. of ACM Multimedia, San Francisco, CA, October 1994.
• 9: D. L. Eager, M. K. Vernon, and J. Zahorjan. Optimal and Efficient Merging Schedules for Video-on-Demand Servers. In Proc. of ACM Multimedia, Orlando, FL, November 1999.
• 10: D. L. Eager, M. K. Vernon, and J. Zahorjan. Minimizing Bandwidth Requirements for On-Demand Data Delivery. In IEEE Transactions on Knowledge and Data Engineering, pages 742--757, October 2001.
• 11: L. Gao, J. Kurose, and D. Towsley. Efficient Schemes for Broadcasting Popular Videos. In Proc. of ACM NOSSDAV, Cambridge, United Kingdom, July 1998.
• 12: L. Gao and D. Towsley. Supplying Instantaneous Video-on-Demand Services Using Controlled Multicast. In Proc. of IEEE ICMCS, Florence, Italy, June 1999.
• 13: V. Gopalakrishnan, B. Bhattacharjee, K. K. Ramakrishnan, R. Jana, and D. Srivastava. CPM: Adaptive Video-on-Demand with Cooperative Peer Assist and Multicast. In Proc. of IEEE INFOCOM, Rio de Janerio, Brazil, April 2009.
• 14: K. A. Hua, Y. Cai, and S. Sheu. Patching: A Multicast Technique for True Video-on-Demand Services. In Proc. of ACM Multimedia, Bristol, England, September 1998.
• 15: K. A. Hua and S. Sheu. Skyscraper Broadcasting: A New Broadcasting Scheme for Metropolitan Video-on-Demand Systems. In Proc. of ACM SIGCOMM, pages 89--100, Cannes, France, September 1997.
• 16: C. Huang, J. Li, and K. Ross. Can Internet Video-on-Demand Be Profitable? In Proc. of ACM SIGCOMM, Kyoto, Japan, August 2007.
• 17: G. Huang. Experiences with PPLive. In Proc. of ACM SIGCOMM - P2P-TV Workshop, Kyoto, Japan, August 2007.
• 18: Y. Huang, T. Fu, D. M. Chiu, J. Lui, and C. Huang. Challenges, Design and Analysis of a Large-scale P2P-VoD System. In Proc. of ACM SIGCOMM, Seattle, WA, August 2008.
• 19: C. L. Liu and J. W. Layland. Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment. Journal of the ACM, 20(1):46--61, 1973.
• 20: H. Ma and K. G. Shin. Multicast Video-on-Demand Services. In ACM SIGCOMM Computer Communication Review, volume 32, pages 31--43, 2002.
• 21: S. Sheu, K. A. Hua, and W. Tavanapong. Chaining: A Generalized Batching Technique for Video-on-Demand Systems. In Proc. of IEEE ICMCS, Ottawa, Canada, June 1997.
• 22: J. A. Stankovic, M. Spuri, K. Ramamritham, and G. C. Buttazzo. Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms. Springer, 1998.
• 23: D. Thaler, M. Talwar, A. Aggarwal, L. Vicisano, and T. Pusateri. http://tools.ietf.org/id/draft-ietf-mboned-automulticast-05.txt. IETF, October 2005.
• 24: S. Viswanathan and T. Imielinski. Metropolitan Area Video-on-Demand Service Using Pyramid Broadcasting. Multimedia Systems, 4(4):197--208, 1996.
• 25: C. Wu, B. Li, and S. Zhao. Diagnosing network-wide p2p live streaming inefficiencies. In IEEE INFOCOM 2009, Rio De Janeiro, Brazil, April 2009.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Experimentation

Keywords:
EDF, VoD, multicast, scheduling