Related Work on the Average Case U.Niesen,and M.A.Maddah-Ali,"Coded Caching with Nonuniform Demands", arXiv:1308.0178v2[cs.T,Mar.2014.(TT2016) >Divide the files into groups The gap between the lower bound and the achievable (upper)bound increases with of groups(unbounded) J.Hachem,N.Karamchandani and S.Diggavi,"Multi-level Coded Caching", arXiv.1404.6563[cs.lT],Apr.2014. Popularity has multiple levels The gap increases with of levels (unbounded) e M.Ji,A.Tulino,J.Llorca and G.Caire,"On the Average Performance of Caching and Coded Multicasting with Random Demands",arXiv:1402.4576v2 [cs.1d,Jul.2014. zipfpopularity distribution The gap increases with when a 1(unbounded) 6
Related Work on the Average Case • U. Niesen, and M.A. Maddah-Ali, “Coded Caching with Nonuniform Demands”, arXiv:1308.0178v2 [cs.IT], Mar. 2014. (TIT 2016) ➢ Divide the files into groups ➢ The gap between the lower bound and the achievable (upper) bound increases with # of groups (unbounded) • J. Hachem, N. Karamchandani and S. Diggavi, “Multi-level Coded Caching”, arXiv:1404.6563 [cs.IT], Apr. 2014. ➢ Popularity has multiple levels ➢ The gap increases with # of levels (unbounded) • M. Ji, A. Tulino, J. Llorca and G. Caire, “On the Average Performance of Caching and Coded Multicasting with Random Demands”, arXiv:1402.4576v2 [cs.IT], Jul. 2014. ➢ Zipf popularity distribution 𝑝𝑖 ∝ 1 𝑖 𝛼 ➢ The gap increases with 1 𝛼−1 when 𝛼 > 1 (unbounded) 6
The Open Question Can we find a coded caching scheme whose average-case performance is at most a constant factor away from the minimum independently of any popularity distributions? 7
The Open Question 7 Can we find a coded caching scheme whose average-case performance is at most a constant factor away from the minimum independently of any popularity distributions?
Our Main Results Constant-factor gap between the lower bound(Ru)and the achievable (upper)bound(Rb)of the expected backhual transmission rate: Rub≤87Rb+2→Rub≤55Rb The achievable bound (Rub) is attained by a simple coded Popularity caching scheme similar to [Ji et al '14] Perform coded caching only 1 among the most popular KM N files - However,all N popular files are Ni File treated uniformly Index The key step is to show a matching lower bound Arbitrary Popularity Distribution! 8
Our Main Results • Constant-factor gap between the lower bound (𝑅𝑙𝑏) and the achievable (upper) bound (𝑅𝑢𝑏) of the expected backhual transmission rate: 𝑅𝑢𝑏 ≤ 87𝑅𝑙𝑏 +2 𝑅𝑢𝑏≤ 55𝑅𝑙𝑏 • The achievable bound (𝑅𝑢𝑏 ) is attained by a simple coded caching scheme similar to [Ji et al ’14] – Perform coded caching only among the most popular N1 files – However, all N1 popular files are treated uniformly • The key step is to show a matching lower bound 8 Arbitrary Popularity Distribution! File Index Popularity 1 𝐾𝑀 𝑁1