Hierarchical Caching for Online Video

We survey existing caching algorithms for their suitability to online video in a hierarchical cache. We have proposed a new algorithm based on additional requirements for online video. We propose new evaluation metrics for online video caching such as hit-rate, replacement rate and ability to recover quickly from cache popularity changes. We developed a realistic dynamically changing popularity model expected for online video. Based on this model and the additional criteria, we evaluate the new algorithm's performance against typically deployed algorithms today such as LRU and GDSF as well as algorithms such as a Perfect-LFU and LCD which have shown to produce high performance. We show that the new algorithm performs better than the existing well known algorithms, in terms of hit-rate and replacement with the dynamically changing popularity environment. We also contribute an analytical method to determine hit rate in a LRU based caching hierarchy as well as an estimation of the hit rate with the new algorithm.