research-article

Integrated prefetching and caching for adaptive video streaming over HTTP: an online approach

Authors:

Roger Zimmermann,

David K. Y. YauAuthors Info & Claims

MMSys '15: Proceedings of the 6th ACM Multimedia Systems Conference

Pages 142 - 152

https://doi.org/10.1145/2713168.2713181

Published: 18 March 2015 Publication History

Abstract

We present an integrated prefetching and caching proxy, termed iPac, for HTTP-based adaptive video streaming services like Netflix and YouTube. The challenge we address is maximizing the byte-hit ratio for proxies through prefetching in the context of the limited bandwidth between proxies and content servers. The problem is NP-hard, and the best approximation ratio that any optimal offline algorithm can achieve is 1-e^--1 ≈ 0.63. Considering that offline algorithms cannot be applied to real-time applications with stringent time constraints, we propose a novel 0.5-competitive online prefetching algorithm which, to the best of our knowledge, has the best lower bound so far. We evaluate the performance of iPac by deploying it over the Amazon EC2 cloud accepting user requests from the video clients deployed on the PlanetLab based on a real trace of user requests for YouTube videos. Our experimental results demonstrate that iPac can significantly improve the performance in terms of byte-hit ratio (up to 84%) and video rates (up to 34%), compared with the state-of-the-art approaches. The proposed iPac is compatible with existing HTTP-based adaptive streaming implementations without requiring any modification to existing content servers and video clients.

References

[1]

RFC 6349. http://www.rfc-editor.org/info/rfc6349.

[2]

VLC Dash Plugin. https://github.com/videolan/vlc.

[3]

YouTube Video Format. https://en.wikipedia.org/wiki/YouTube.

[4]

A. Balachandran, V. Sekar, A. Akella, S. Seshan, I. Stoica, and H. Zhang. A Quest for an Internet Video Quality-of-Experience Metric. In Proc. Hotnets, 2012.

Digital Library

[5]

S. Borst, V. Gupta, and A. Walid. Distributed Caching Algorithms for Content Distribution Networks. In Proc. INFOCOM, 2010.

Digital Library

[6]

H. Che, Y. Tung, and Z. Wang. Hierarchical Web Caching Systems: Modeling, Design and Experimental Results. IEEE Journal on Selected Areas in Communications, 20(7):1305--1314, 2006.

Digital Library

[7]

S. Chen, B. Shen, S. Wee, and X. Zhang. Dsigns of High Quality Streaming Proxy Systems. In Proc. INFOCOM, 2004.

[8]

N. Cranley, P. Perry, and L. Murphy. User Perception of Adapting Video Quality. International Journal of Human-Computer Studies, 64(8):637--647, 2006.

Digital Library

[9]

G. B. Dantzig. Discrete-Variable Extremum Problems. Operations Research, 5(2):266--277, 1957.

Digital Library

[10]

F. Dobrian, V. Sekar, A. Awan, I. Stoica, D. Joseph, A. Ganjam, J. Zhan, and H. Zhang. Understanding the Impact of Video Quality on User Engagement. In Proc. SIGCOMM, 2011.

Digital Library

[11]

D.-Z. Du, K.-I. Ko, and X. Hu. Design and Analysis of Approximation Algorithms. Springer Optimization and Its Applications, 2012.

[12]

X. Jia, D. Li, H. Du, and J. Cao. On Optimal Replication of Data Object at Hierarchical and Transparent Web Proxies. IEEE Transactions on Parallel and Distributed Systems, 16(8):673--685, 2005.

Digital Library

[13]

J. Jiang, V. Sekar, and H. Zhang. Improving Fairness, Efficiency, and Stability in HTTP-based Adaptive Video Streaming with FESTIVE. In Proc. CoNEXT, 2012.

Digital Library

[14]

H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.

[15]

S. Khuller, A. Moss, and J. S. Naor. The Budgeted Maximum Coverage Problem. Information Processing Letters, 70(1): 39--45, 1999.

Digital Library

[16]

D. K. Krishnappa, S. Khemmarat, L. Gao, and M. Zink. On the Feasibility of Prefetching and Caching for Online TV Services: A Measurement Study on Hulu. In Proc. PAM, 2011.

Digital Library

[17]

N. Laoutaris, G. Zervas, A. Bestavros, and G. Kollios. The Cache Inference Problem and its Application to Content and Request Routing. In Proc. INFOCOM, 2007.

Digital Library

[18]

T. Leighton. Improving Performance on the Internet. Communications of the ACM, 52(2):44--51, Feburary 2009.

Digital Library

[19]

C. Liu, I. Bouazizi, and M. Gabbouj. Rate Adaptation for Adaptive HTTP Streaming. In Proc. MMSys, 2011.

Digital Library

[20]

A. Marchetti-Spaccamela and C. Vercellis. Stochastic On-line knapsack Problems. Mathematical Programming, 68(1--3):73--104, 1995.

Digital Library

[21]

L. Plissonneau and E. Biersack. A Longitudinal View of HTTP Video Streaming Performance. In Proc. MMSys, 2012.

Digital Library

[22]

S. Podlipnig and L. Böszörmenyi. A Survey of Web Cache Replacement Strategies. ACM Computing Surveys, 35(4):374--398, 2003.

Digital Library

[23]

S. Sen, J. Rexford, and D. Towsley. Proxy Prefix Caching for Multimedia Streams. In Proc. INFOCOM, 1999.

[24]

L. Shen, W. Tu, and E. Steinbach. A Flexible Starting Point Based Partial Caching Algorithm for Video on Demand. In Proc. ICME, 2007.

[25]

M. Sviridenko. A Note on Maximizing a Submodular Set Function Subject to a Knapsack Constraint. Operations Research Letters, 32(1):41--43, 2004.

Digital Library

[26]

G. Tian and Y. Liu. Towards Agile and Smooth Video Adaptation in Dynamic HTTP Streaming. In Proc. CoNEXT, 2012.

Digital Library

[27]

M. Zink, K. Suh, Y. Gu, and J. Kurose. Characteristics of YouTube Network Traffic at a Campus Network: Measurements, Models, and Implications. Computer Networks, 53(4): 501--514, 2009.

Digital Library

Cited By

Lekharu AChauhan ASur APatra M(2024)Reinforcement Learning-Based Adaptive Bitrate Caching at MEC ServerIEEE Transactions on Network and Service Management10.1109/TNSM.2024.336733321:3(3292-3304)Online publication date: Jun-2024
https://doi.org/10.1109/TNSM.2024.3367333
Chen WChou PWang CHwang RChen W(2023)Dual Pricing Optimization for Live Video Streaming in Mobile Edge Computing With Joint User Association and Resource ManagementIEEE Transactions on Mobile Computing10.1109/TMC.2021.308922922:2(858-873)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TMC.2021.3089229
Behravesh RRao APerez-Ramirez DHarutyunyan DRiggio RBoman M(2022)Machine Learning at the Mobile Edge: The Case of Dynamic Adaptive Streaming Over HTTP (DASH)IEEE Transactions on Network and Service Management10.1109/TNSM.2022.319385619:4(4779-4793)Online publication date: Dec-2022
https://doi.org/10.1109/TNSM.2022.3193856
Show More Cited By

Index Terms

Integrated prefetching and caching for adaptive video streaming over HTTP: an online approach

Recommendations

Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer Architecture

On-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
An integrated prefetching/caching scheme in multimedia servers

Advances in storage and networking technologies have made on-demand multimedia services prevalent these days. To provide numerous concurrent users with such high-quality services, it is essential for storage systems to support sufficient I/O bandwidth ...
Automated Control of Aggressive Prefetching for HTTP Streaming Video Servers
SYSTOR 2014: Proceedings of International Conference on Systems and Storage

Past work has shown that disk prefetching can be an effective technique for improving the performance of disk bound workloads. However, the performance gains are highly dependent on selecting a prefetch size that is appropriate for a specific system and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MMSys '15: Proceedings of the 6th ACM Multimedia Systems Conference

March 2015

277 pages

ISBN:9781450333511

DOI:10.1145/2713168

General Chair:
Wei Tsang Ooi
National University of Singapore, Singapore
,
Program Chairs:
Wu-chi Feng
Portland State University
,
Feng Liu
Portland State University

Copyright © 2015 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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Singapore Agency for Science, Technology and Research (A*STAR)

Conference

MMSys '15

Sponsor:

MMSys '15: Multimedia Systems Conference 2015

March 18 - 20, 2015

Oregon, Portland

Acceptance Rates

MMSys '15 Paper Acceptance Rate 12 of 41 submissions, 29%;

Overall Acceptance Rate 176 of 530 submissions, 33%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
517
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lekharu AChauhan ASur APatra M(2024)Reinforcement Learning-Based Adaptive Bitrate Caching at MEC ServerIEEE Transactions on Network and Service Management10.1109/TNSM.2024.336733321:3(3292-3304)Online publication date: Jun-2024
https://doi.org/10.1109/TNSM.2024.3367333
Chen WChou PWang CHwang RChen W(2023)Dual Pricing Optimization for Live Video Streaming in Mobile Edge Computing With Joint User Association and Resource ManagementIEEE Transactions on Mobile Computing10.1109/TMC.2021.308922922:2(858-873)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TMC.2021.3089229
Behravesh RRao APerez-Ramirez DHarutyunyan DRiggio RBoman M(2022)Machine Learning at the Mobile Edge: The Case of Dynamic Adaptive Streaming Over HTTP (DASH)IEEE Transactions on Network and Service Management10.1109/TNSM.2022.319385619:4(4779-4793)Online publication date: Dec-2022
https://doi.org/10.1109/TNSM.2022.3193856
Sahinel DRommel SMonroy I(2021)Resource Management in Converged Optical and Millimeter Wave Radio Networks: A ReviewApplied Sciences10.3390/app1201022112:1(221)Online publication date: 27-Dec-2021
https://doi.org/10.3390/app12010221
Shi WWang CJiang YLi QShen GMuntean G(2021)CoLEAP: Cooperative Learning-Based Edge Scheme With Caching and Prefetching for DASH Video DeliveryIEEE Transactions on Multimedia10.1109/TMM.2020.302989323(3631-3645)Online publication date: 2021
https://doi.org/10.1109/TMM.2020.3029893
Behravesh RPerez-Ramirez DRao AHarutyunyan DRiggio RSteinert R(2020)ML-Driven DASH Content Pre-Fetching in MEC-Enabled Mobile Networks2020 16th International Conference on Network and Service Management (CNSM)10.23919/CNSM50824.2020.9269054(1-7)Online publication date: 2-Nov-2020
https://doi.org/10.23919/CNSM50824.2020.9269054
Carlsson NEager DAmaral JKoziolek ATrubiani CIosup A(2020)Had You Looked Where I'm Looking? Cross-user Similarities in Viewing Behavior for 360-degree Video and Caching ImplicationsProceedings of the ACM/SPEC International Conference on Performance Engineering10.1145/3358960.3379129(130-137)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3358960.3379129
Shi WLi QWang CShen GLi WWu YJiang Y(2019)LEAPProceedings of the International Symposium on Quality of Service10.1145/3326285.3329051(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3326285.3329051
Coutinho RChiariotti FZucchetto DZanella A(2018)Just-in-time proactive caching for DASH video streaming2018 17th Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net)10.23919/MedHocNet.2018.8407087(1-6)Online publication date: Jun-2018
https://doi.org/10.23919/MedHocNet.2018.8407087
Petrangeli SHooft JWauters TTurck F(2018)Quality of Experience-Centric Management of Adaptive Video Streaming ServicesACM Transactions on Multimedia Computing, Communications, and Applications10.1145/316526614:2s(1-29)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1145/3165266
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