Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/2713168.2713181acmconferencesArticle/Chapter ViewAbstractPublication PagesmmsysConference Proceedingsconference-collections
research-article

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

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.
[5]
S. Borst, V. Gupta, and A. Walid. Distributed Caching Algorithms for Content Distribution Networks. In Proc. INFOCOM, 2010.
[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.
[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.
[9]
G. B. Dantzig. Discrete-Variable Extremum Problems. Operations Research, 5(2):266--277, 1957.
[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.
[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.
[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.
[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.
[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.
[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.
[18]
T. Leighton. Improving Performance on the Internet. Communications of the ACM, 52(2):44--51, Feburary 2009.
[19]
C. Liu, I. Bouazizi, and M. Gabbouj. Rate Adaptation for Adaptive HTTP Streaming. In Proc. MMSys, 2011.
[20]
A. Marchetti-Spaccamela and C. Vercellis. Stochastic On-line knapsack Problems. Mathematical Programming, 68(1--3):73--104, 1995.
[21]
L. Plissonneau and E. Biersack. A Longitudinal View of HTTP Video Streaming Performance. In Proc. MMSys, 2012.
[22]
S. Podlipnig and L. Böszörmenyi. A Survey of Web Cache Replacement Strategies. ACM Computing Surveys, 35(4):374--398, 2003.
[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.
[26]
G. Tian and Y. Liu. Towards Agile and Smooth Video Adaptation in Dynamic HTTP Streaming. In Proc. CoNEXT, 2012.
[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.

Cited By

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Recommendations

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

Check for updates

Author Tags

  1. adaptive streaming
  2. caching
  3. online algorithm
  4. prefetching

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

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (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
  • (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
  • (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
  • (2021)Resource Management in Converged Optical and Millimeter Wave Radio Networks: A ReviewApplied Sciences10.3390/app1201022112:1(221)Online publication date: 27-Dec-2021
  • (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
  • (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
  • (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
  • (2019)LEAPProceedings of the International Symposium on Quality of Service10.1145/3326285.3329051(1-10)Online publication date: 24-Jun-2019
  • (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
  • (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
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media