Related Work on the Average case U Niesen, and M.A. Maddah-Ali, "Coded Caching with Nonuniform Demands aXiv:13080178V2[cs,Ma.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 arXiy:14046563[cs,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.,Jul.2014 Zipf popularity distribution pi a The gap increases with when a>1(unbounded)
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?
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 (rib)and the achievable (upper) bound(rub)of the expected backhual transmission rate Rb≤87Rb+2□R2b≤55Rb The achievable bound (rub) is attained by a simple coded Popularity caching scheme similar to [iet al 14 Perform coded caching only among the most popular KM Files However, all N, popular files are N1 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