AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

A Comparison of Cache Replacement Algorithms for Video Services


Affiliations
1 College of Computer Science and Information Technology, Sudan University of Science and Technology, Sudan
 

The increasing demand for video services has made video caching a necessity to decrease download times and reduce Internet traffic. In addition, it is very important to store the right content at the right time in caches to make effective use of caching. An informative decision has to be made as to which videos are to be evicted from the cache in case of cache saturation. Therefore, the best cache replacement algorithm is the algorithm which dynamically selects a suitable subset of videos for caching, and maximizes the cache hit ratio by attempting to cache the videos which are most likely to be referenced in the future. In this paper we study the most popular cache replacement algorithms (OPT, CC, QC, LRU-2, LRU, LFU and FIFO) which are currently used in video caching. We use simulations to evaluate and compare these algorithms using video popularities that follow a Zipf distribution. We consider different cache sizes and video request rates. Our results show that the CC algorithm achieves the largest hit ratio and performs well even under small cache sizes. On the other hand, the FIFO algorithm has the smallest hit ratio among all algorithms.

Keywords

Cache Update, Hit Ratio, Video Popularity, Zipf Distribution.
User
Notifications
Font Size

  • Kapil Arora and Dhawaleswar Rao, "Web Cache Page Replacement by Using LRU and. LFU Algorithms with Hit Ratio: A Case Unification," International Journal of Computer Science & Information Technologies, Vol. 5 (3), 2014, pp.3232 – 3235.

  • Abdullah Balamash and Marwan Krunz, "An Overview of Web Caching Replacement Algorithms," IEEE Communications Surveys and Tutorials, vol. 6, no. 2, 2004.

  • Philip Koopman, "Cache Organization", September 2.1998 [Online]. Available: https://www.ece.cmu.edu/~ece548/handouts/04cachor.pdf.

  • Pablo Rodriguez, Christian Spanner, and Ernst W. Biersack, "Analysis of Web Caching Architectures: Hierarchical and Distributed Caching", IEEE/ACM Transactions on Networking, Vol. 9, no. 4, August 2001.

  • Lei Shi, Zhimin Gu, Lin Wei, and Yun Shi," An Applicative Study of Zipf’s Law on Web Cache," International Journal of Information Technology, Vol. 12, No.4, 2006.

  • Dong Zheng," Differentiated Web Caching – A Differentiated Memory Allocation Model on Proxies," PhD Thesis, Queen's University, (2004).

  • "Least Recently Used Caching Algorithms definition" [Online]. Available: https://en.wikipedia.org/wiki/Cache_algorithms#LRU.

  • "The Least Recently Used (LRU) Page Replacement Algorithm".” [Online]. Available: http://www.informit.com/articles/article.aspx?p=25260&seqNum=7, [Accessed: 7-10-2016].

  • S.M. Shamsheer Daula, Dr. K.E Sreenivasa Murthy and G Amjad Khan,"A Throughput Analysis on Page Replacement Algorithms in Cache Memory Management," International Journal of Engineering Research and Applications (IJERA) Vol. 2, Issue 2, Mar-Apr 2012, pp.126-130.

  • Dohy Hong, Danny De Vleeschauwer and Fran¸cois Baccelli "A chunk-based caching algorithm for streaming video", NET-COOP 2010 - 4th Workshop on Network Control and Optimization, Nov 2010.

  • Stefan Podlipnig and Uszlo' Boszonnbnyi, “Replacement strategies for quality based video caching", IEEE International Conference on Multimedia and Expo, Vol. 2, 2002.

  • Suoheng Li, JieXu, Mihaela van der Schaar and Weiping Li, "Trend-Aware Video Caching through Online Learning,” IEEE Transactions on Multimedia, vol. 18, pp. 2503–2516 , July 2016.

  • Yipeng Zhou, Member, IEEE, Liang Chen, Chunfeng Yang, and Dah Ming Chiu, Fellow, IEEE "Video Popularity Dynamics and Its Implication for Replication,” IEEE Transactions on Multimedia, vol. 17, No.8, pp. 2503–2516, August 2015.

  • Cisco Visual Networking Index: Forecast and Methodology, 2016–2021 [Online]. Available: https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/ complete-white-paper-c11-481360.html, [Accessed: 30/4/2018].

  • Kianoosh Mokhtarian, Hans-Arno Jacobsen, "Caching in Video CDNs: Building Strong Lines of Defense," Proceedings of the Ninth European Conference on Computer Systems, April, 2014.

  • Soam Acharya, and Brian Smith," MiddleMan: A Video Caching Proxy Server”, Proceedings of NOSSDAV, 2000.

  • Niemah I. Osman, Taisir El-Gorashi, Louise Krug, and Jaafar M. H. Elmirghani, "Energy-Efficient Future High-Definition TV," Journal of Lightwave Technology, vol. 32, pp. 2364-2381, 2014.


Abstract Views: 356

PDF Views: 145




  • A Comparison of Cache Replacement Algorithms for Video Services

Abstract Views: 356  |  PDF Views: 145

Authors

Areej M. Osman
College of Computer Science and Information Technology, Sudan University of Science and Technology, Sudan
Niemah I. Osman
College of Computer Science and Information Technology, Sudan University of Science and Technology, Sudan

Abstract


The increasing demand for video services has made video caching a necessity to decrease download times and reduce Internet traffic. In addition, it is very important to store the right content at the right time in caches to make effective use of caching. An informative decision has to be made as to which videos are to be evicted from the cache in case of cache saturation. Therefore, the best cache replacement algorithm is the algorithm which dynamically selects a suitable subset of videos for caching, and maximizes the cache hit ratio by attempting to cache the videos which are most likely to be referenced in the future. In this paper we study the most popular cache replacement algorithms (OPT, CC, QC, LRU-2, LRU, LFU and FIFO) which are currently used in video caching. We use simulations to evaluate and compare these algorithms using video popularities that follow a Zipf distribution. We consider different cache sizes and video request rates. Our results show that the CC algorithm achieves the largest hit ratio and performs well even under small cache sizes. On the other hand, the FIFO algorithm has the smallest hit ratio among all algorithms.

Keywords


Cache Update, Hit Ratio, Video Popularity, Zipf Distribution.

References