摘要: We consider a basic content distribution scenario consisting of single origin server connected through shared bottleneck link to number users each equipped with cache finite memory. The issue sequence requests from set popular files, and the goal is operate caches as well such that these are satisfied minimum bits sent over link. Assuming Markov model for renewing we characterize approximately optimal long-term average rate further prove online scheme has same performance offline scheme, in which contents can be updated based on entire files before new request. To support theoretical results, propose an coded caching termed least-recently (LRS) simulate it demand time series derived dataset made available by Netflix Prize. For this series, show proposed LRS algorithm significantly outperforms used (LRU) algorithm.
sci-hub.se 参考文章(14)
Matthias Westermann, Caching in Networks GI Jahrestagung. pp. 297- 304 ,(1999) , 10.1007/978-3-662-01069-3_42
Laszlo A. Belady, None, A study of replacement algorithms for a virtual-storage computer Ibm Systems Journal. ,vol. 5, pp. 78- 101 ,(1966) , 10.1147/SJ.52.0078
Alejandro López-Ortiz, Reza Dorrigiv, Spyros Angelopoulos, On the separation and equivalence of paging strategies symposium on discrete algorithms. pp. 229- 237 ,(2007) , 10.5555/1283383.1283408
Baruch Awerbuch, Amos Fiat, Yair Bartal, Distributed paging for general networks symposium on discrete algorithms. pp. 574- 583 ,(1996) , 10.5555/313852.314122
Marek Chrobak, John Noga, LRU is better than FIFO symposium on discrete algorithms. pp. 78- 81 ,(1998) , 10.5555/314613.314655
Mohammad Ali Maddah-Ali, Urs Niesen, Decentralized coded caching attains order-optimal memory-rate tradeoff allerton conference on communication, control, and computing. pp. 421- 427 ,(2013) , 10.1109/ALLERTON.2013.6736555
Daniel D. Sleator, Robert E. Tarjan, Amortized efficiency of list update and paging rules Communications of The ACM. ,vol. 28, pp. 202- 208 ,(1985) , 10.1145/2786.2793
Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, Arun Venkataramani, Online Hierarchical Cooperative Caching Theory of Computing Systems. ,vol. 39, pp. 851- 874 ,(2006) , 10.1007/S00224-006-1250-X
E. Torng, A Unified Analysis of Paging and Caching Algorithmica. ,vol. 20, pp. 175- 200 ,(1998) , 10.1007/PL00009192
Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, Neal E Young, Competitive paging algorithms Journal of Algorithms. ,vol. 12, pp. 685- 699 ,(1991) , 10.1016/0196-6774(91)90041-V