An adaptive caching algorithm suitable for time-varying user accesses in VOD systems

详细信息    查看全文

• 作者：Qiang Ling ; Lixiang Xu ; Jinfeng Yan ; Yicheng Zhang
• 关键词：Caching ; Segmentation ; Average access interval ; Byte ; hit ratio
• 刊名：Multimedia Tools and Applications
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：74
• 期：24
• 页码：11117-11137
• 全文大小：1,097 KB
• 参考文献：1.Dyaberi JM (2011) Networking and storage support for video-on-demand data delivery. Purdue University, West Lafayette, Indiana
  2.Yu H, Zheng D, Zhao BY, Zheng W (2006) Understanding user behavior in large-scale video-on-demand systems. In: EuroSys, pp 333-44
  3.Yu J, Chou CT, Du X, Wang T (2006) Internal popularity of streaming video and its implication on caching. In: the 20th International Conference on Advanced Information Networking and Applications (AINA06)
  4.Yu J , Chou CT, Yang Z, Du X, Wang T (2006) A dynamic caching algorithm based on internal popularity distribution of streaming media. Multimedia Systems 12(2):135-49CrossRef
  5.Hofmann M, Ng TE, Guo K, Paul S, Zhang H (1999) Caching techniques for streaming multimedia over the internet. Bell Laboratories Technical Report, pp BL011345-90409-4TM
  6.Wu KL, Yu PS, Wolf JL (2001) Segment based proxy caching of multimedia streams.In:the 10th international conference on World Wide Web, pp 36-4
  7.Wu KL, Yu PS, Wolf JL (2004) Segmentation of multimedia streams for proxy caching. IEEE Trans Multimed 6(5):770-80CrossRef
  8.Zhang X, Chen S, Shen B, Wee S (2003) Adaptive and lazy segmentation based proxy caching for streaming media delivery. In: The 13th international workshop on Network and Operating Systems Support for Digital Audio and Video, pp 22-1
  9.Sen S, Rexford J, Towsley D (1999) Proxy prefix caching for multimedia streams. In: IEEE International Conference on Computer and Communications Societies(INFOCOM 99), pp 1310-319
  10.Park SH, Lim EJ, Chung KD (2001) Popularity-based partial caching for VOD systems using a proxy server. In: IEEE International Parallel and Distributed Processing Symposium (IPDPS 01), pp 11-19
  11.Miao Z, Ortega A (1999) Proxy caching for efficient video services over the Internet. In: The 9th international packet video workshop
  12.Liu J, Xu J (2004) Proxy caching for media streaming over the internet. IEEE Commun Mag 42(8):88-4CrossRef
  13.Chen S, Wang H, Zhang X, Shen B, Wee S (2005) Segment-based proxy caching for internet streaming media delivery. IEEE Trans Multimed 12(3):59-7CrossRef
  14.Miao Z, Ortega A (2002) Scalable proxy caching of video under storage constraints. IEEE J Sel Areas Commun 20(7):1315-327CrossRef
  15.Kangasharju J, Hartanto F, Reisslein M, Ross KW (2002) Distributing layerd encoded video through caches. IEEE Trans Comput 51(6):622-36CrossRef
  16.Hartanto F, Kangasharju J, Reisslein M, Ross K (2006) Caching videos objects: layers vs versions. Multimedia Tools Appl 31(2):221-45CrossRef
  17.Brampton A, MacQuire A, Fry M, Rai IA, Race NJP, Mathy L (2009) Characterising and exploiting workloads of highly interactive video-on-demand. Multimedia Systems 15(1):3-7CrossRef
  18.Vakali A (2000) LRU-based algorithms for web cache replacement.In: International conference on electronic commerce and web technologies, pp 409-18
  19.Sokolinsky LB (2004) LFU-K: An effective buffer management replacement algorithm. In: The 9th international conference on database systems for advanced applications, pp 670-81
  20.Cherkasova L, Gupta M (2004) Analysis of enterprise media server workloads: access patterns, locality, content evolution and rates of change. IEEE/ACM Trans Networking 12(5):781-94CrossRef
  21.Guo L, Tan E, Chen S, Xiao Z, Zhang X (2007) Does internet media traffic really follow zipf-like distribution. In: SIGMETRICS07, pp 35-60
  22.Chen T (2007) Obtaining the optimal cache document replacement policy for the caching system of an EC website. Eur J Oper Reserach 181(2):828-41CrossRef MATH
  23.Robinson J, Edvarakonda M (1990) Data cache management using frequency-based replacement. In: Proceedings of the 1990 ACM SIGMETRICS on the measurement and modeling of computer systems, pp 132-4
  24.Lau PY, Park S, Kim T (2010) Dynamic time-weighted popularity index:a video-on-demand case. In: IEEE international conference on network infrastructure and digital content, pp 809-14
  25.Sheikh R, Kharbutli M (2010) Improving cache performance by combining cost-sensitivity and locality principles in cache replacement algorithms. In: IEEE international conference on computer design, pp 76-3
  26.Cao P, Irani S (1997) Cost-aware www proxy caching algorithms. In: Proceedings of the USENIX symposium on internet technologies and systems
  27.Nair T R G, Jayarekha P (2010) A rank based replacement policy for multimedia server cache using zipf-like law. J Comput 4(3):14-2
  28.Li F, Li J, Hu Z, Zhou J (2009) Common caching replacement algorithm for video-on-demand system. In: 2009 international conference on web information systems and mining, pp 748-51
  29.Shen L, Tu W, Steinbach E (2007) A flexible starting point based partial caching algorithm for vido on demand. In: IEEE international conference on multimedia and exop, pp 76-9
  30.Muhammad M, Tu W, Steinbach E (2008) Evaluation of segment-based proxy caching for video on demand. In: IEEE i
• 作者单位：Qiang Ling (1)
  Lixiang Xu (1)
  Jinfeng Yan (1)
  Yicheng Zhang (1)
  
  1. Deparment of Automation, University of Science and Technology of China, Hefei, 230027, China
  
• 刊物类别：Computer Science
• 刊物主题：Multimedia Information Systems
  Computer Communication Networks
  Data Structures, Cryptology and Information Theory
  Special Purpose and Application-Based Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7721

文摘

With the fast progresses of network technology, Video-On-Demand (VOD) service has found more and more applications. The transmission of multimedia files places heavy burdens on the Internet owing to their large sizes. To resolve this issue, caching servers are deployed at the edge of the Internet to meet most needs of local users by caching some popular videos. This paper provides an approach to choose the cached videos under the time-varying user behavior. Our approach estimates the average access intervals of a video with an Exponential Weighted Moving Average (EWMA) approach and furthermore predicts the video’s future popularity based on its historical access intervals. The forgetting and predicting operations enable the algorithm to not only track the change of the time-varying user accesses, but also reduce the effects of the randomness of a single user access on the caching performance. In addition, we propose a new segmentation approach, which makes the storage granularity independent from the management granularity and can make a better use of the cache space. Simulation results show that our segmentation approach has a higher Byte-Hit Ratio than uniform segmentation and chunk segmentation, and our caching algorithm outperforms Least Recently Used (LRU), Least Frequently Used (LFU) and EWMA. Keywords Caching Segmentation Average access interval Byte-hit ratio