research-article

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

Authors:

Vaneet Aggarwal,

Robert Caldebank,

Vijay Gopalakrishnan,

K. K. Ramakrishnan,

Fang YuAuthors Info & Claims

MM '09: Proceedings of the 17th ACM international conference on Multimedia

Pages 421 - 430

https://doi.org/10.1145/1631272.1631330

Published: 19 October 2009 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[16]

C. Huang, J. Li, and K. Ross. Can Internet Video-on-Demand Be Profitable? In Proc. of ACM SIGCOMM, Kyoto, Japan, August 2007.

Digital Library

[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.

Digital Library

[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.

Digital Library

[20]

H. Ma and K. G. Shin. Multicast Video-on-Demand Services. In ACM SIGCOMM Computer Communication Review, volume 32, pages 31--43, 2002.

Digital Library

[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.

Digital Library

[22]

J. A. Stankovic, M. Spuri, K. Ramamritham, and G. C. Buttazzo. Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms. Springer, 1998.

Digital Library

[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.

Digital Library

[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.

Cited By

Xie JGuo DWu JRen BChen TChen H(2021)Exploiting Reliable and Scalable Multicast Services in IaaS DatacentersIEEE Transactions on Services Computing10.1109/TSC.2018.287773314:5(1370-1383)Online publication date: 1-Sep-2021
https://doi.org/10.1109/TSC.2018.2877733
Al-Abbasi AAggarwal VRa M(2019)Multi-Tier Caching Analysis in CDN-Based Over-the-Top Video Streaming SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2019.290043427:2(835-847)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2900434
Koch CHacker SHausheer D(2017)VoDCast: Efficient SDN-based multicast for video on demand2017 IEEE 18th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM.2017.7974319(1-6)Online publication date: Jun-2017
https://doi.org/10.1109/WoWMoM.2017.7974319
Show More Cited By

Index Terms

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

Recommendations

Multicast Video-on-Demand services

The server's storage I/O and network I/O bandwidths are the main bottleneck of VoD service. Multicast offers an efficient means of distributing a video program to multiple clients, thus greatly improving the VoD performance. However, there are many ...
Multicast Pull Scheduling: When Fairness Is Fine

We investigate server scheduling policies to minimize average user perceived latency in pull-based client-server systems (systems where multiple clients request data from a server) where the server answers requests on a multicast/ broadcast channel. We ...
Peer-assisted multimedia delivery using periodic multicast

Multimedia content distribution is one of the most popular services available on the Internet, and several approaches have been developed to satisfy user requirements and reduce server load. IP multicast is one efficient mechanism for distributing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MM '09: Proceedings of the 17th ACM international conference on Multimedia

October 2009

1202 pages

ISBN:9781605586083

DOI:10.1145/1631272

General Chairs:
Wen Gao
Peking University, China
,
Yong Rui
Microsoft, China
,
Alan Hanjalic
Delft University of Technology, The Netherlands
,
Program Chairs:
Changsheng Xu
Institute of Automation, Chinese Academy of Sciences, China
,
Eckehard Steinbach
Technical University of Munich, Germany
,
Abdulmotaleb El Saddik
University of Ottawa, Canada
,
Michelle Zhou
IBM T. J. Watson Research Center, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMM: ACM Special Interest Group on Multimedia

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MM09

Sponsor:

SIGMM

MM09: ACM Multimedia Conference

October 19 - 24, 2009

Beijing, China

Acceptance Rates

Overall Acceptance Rate 2,145 of 8,556 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
414
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xie JGuo DWu JRen BChen TChen H(2021)Exploiting Reliable and Scalable Multicast Services in IaaS DatacentersIEEE Transactions on Services Computing10.1109/TSC.2018.287773314:5(1370-1383)Online publication date: 1-Sep-2021
https://doi.org/10.1109/TSC.2018.2877733
Al-Abbasi AAggarwal VRa M(2019)Multi-Tier Caching Analysis in CDN-Based Over-the-Top Video Streaming SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2019.290043427:2(835-847)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2900434
Koch CHacker SHausheer D(2017)VoDCast: Efficient SDN-based multicast for video on demand2017 IEEE 18th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM.2017.7974319(1-6)Online publication date: Jun-2017
https://doi.org/10.1109/WoWMoM.2017.7974319
Junjie Xie Deke Guo Zhiyao Hu Jie Wu Tao Chen Honghui Chen (2017)Reliable multicast routing with uncertain sources2017 IEEE/ACM 25th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS.2017.7969158(1-6)Online publication date: Jun-2017
https://doi.org/10.1109/IWQoS.2017.7969158
Kuo JShen SYang MYang DTsai MChen W(2017)Service Overlay Forest Embedding for Software-Defined Cloud Networks2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2017.62(720-730)Online publication date: Jun-2017
https://doi.org/10.1109/ICDCS.2017.62
Zhang WYang LZhang KPeng C(2017)Collaborate Algorithms for the Multi-channel Program Download Problem in VOD ApplicationsCollaborate Computing: Networking, Applications and Worksharing10.1007/978-3-319-59288-6_30(333-342)Online publication date: 5-Jul-2017
https://doi.org/10.1007/978-3-319-59288-6_30
Chen JArumaithurai MFu XRamakrishnan KAsami TFu XBurke JRossi DPsaras I(2016)SAIDProceedings of the 3rd ACM Conference on Information-Centric Networking10.1145/2984356.2984370(11-20)Online publication date: 26-Sep-2016
https://dl.acm.org/doi/10.1145/2984356.2984370
Rahman MWagner A(2016)A Downlink Scheduler for Multicasting Wireless Video-on-DemandIEEE Transactions on Mobile Computing10.1109/TMC.2016.253524815:12(2921-2938)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TMC.2016.2535248
Nayfeh KSarhan N(2016)A Scalable Solution for Interactive Near Video-on-Demand SystemsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2015.247870826:10(1907-1916)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TCSVT.2015.2478708
Al-Hadrusi MSarhan N(2014)A scalable delivery solution and a pricing model for commercial video-on-demand systems with video advertisementsMultimedia Tools and Applications10.1007/s11042-013-1597-373:3(1417-1443)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1007/s11042-013-1597-3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents