Coded Caching under Arbitrary Popularity Distributions Jinbei Zhang, Xiaojun Lin, Xinbing Wang
Coded Caching under Arbitrary Popularity Distributions Jinbei Zhang, Xiaojun Lin, Xinbing Wang
Caching and coded-Caching Caching is important for reducing backhaul requirement when serving content that many users are interested in The cache size at each user needs to be reasonable large compared to the amount of"popular"content server Coded caching can further reduce the backhaul requirement even when each individual cache size is small but the global cache size is substantial [Maddah-Ali and cache cache cache Neisen 14 User 1 User 2 User 3
Caching and Coded-Caching 2 Server cache cache cache User 1 User 2 User 3 • Caching is important for reducing backhaul requirement when serving content that many users are interested in • The cache size at each user needs to be reasonable large compared to the amount of “popular” content • Coded caching can further reduce the backhaul requirement even when each individual cache size is small, but the global cache size is substantial [Maddah-Ali and Neisen ’14]
Traditional (Uncoded)Caching: Individual cache size needs to be large N=3 files (unit-size) Server A=(A1,A2,A3) B=(B1,B2,B3) A. A Broadcast 2 C=(C1,C2,C3) channel 2,B2 B 2 3 K=3 users Back-haul requirement Cache size M=1 Uncoded Caching (A1,B1C1)[(A1,B1C1)(A,B1C1) K·(1 Individu caching gain User 1 User 2 User 3 wants a wants wants C
3 (𝐴1 , 𝐵1 , 𝐶1 ) User 1 wants 𝐴 User 2 wants 𝐵 User 3 wants 𝐶 Traditional (Uncoded) Caching: Individual cache size needs to be large Server K=3 users Cache size M=1 Broadcast channel 𝐴 = (𝐴1 , 𝐴2 , 𝐴3 ) 𝐵 = (𝐵1 , 𝐵2 , 𝐵3 ) 𝐶 = (𝐶1 , 𝐶2 , 𝐶3 ) N=3 files (unit-size): • Uncoded Caching 𝐾 ∙ 1 − 𝑀 𝑁 = 2 Back-haul Requirement: (𝐴1 , 𝐵1 , 𝐶1 ) (𝐴1 , 𝐵1 , 𝐶1 ) 𝐴2 , 𝐴3 𝐵2 , 𝐵3 𝐶2 , 𝐶3 Individual caching gain
Coded Caching Global Caching Gains N=3 files: A=(A1, A2, A3) Server B=(B1,B2,B3) C=(C1,C2,C3 Broadcast A2田B1 channel A3 C1 ↓B3C2 K=3 users Back-haul requirement Cache size M=1 Uncoded Caching (A1,B1,C1)[(A2,B2C2)(A3B3C3) K·1 A B Coded Caching [ 1 3 M K…(1N)1N 3 2 KM Global caching User 1 User 2 User 3 gaIn wants a wants wants C [1]Fundamental Limits of Caching, M. Maddah-Ali and U Niesen, IEEE Trans. Inf Theory, 2014
4 (𝐴1 , 𝐵1 , 𝐶1 ) (𝐴2 , 𝐵2 , 𝐶2 ) (𝐴3 , 𝐵3 , 𝐶3 ) 𝐴2 ⊕ 𝐵1 𝐴2 𝐵1 𝐴3 ⊕ 𝐶1 𝐴3 𝐶1 𝐵3 ⊕ 𝐶2 𝐵3 𝐶2 User 1 wants 𝐴 User 2 wants 𝐵 User 3 wants 𝐶 Coded Caching: Global Caching Gains Server 𝐾 ∙ 1 − 𝑀 𝑁 ∙ 1 1 + 𝐾𝑀 𝑁 = 1 • Coded Caching [1] [1] Fundamental Limits of Caching, M. Maddah-Ali and U. Niesen, IEEE Trans. Inf. Theory, 2014. K=3 users Cache size M=1 Broadcast channel 𝐴 = (𝐴1 , 𝐴2 , 𝐴3 ) 𝐵 = (𝐵1 , 𝐵2 , 𝐵3 ) 𝐶 = (𝐶1 , 𝐶2 , 𝐶3 ) N=3 files: Global caching gain • Uncoded Caching 𝐾 ∙ 1 − 𝑀 𝑁 = 2 Back-haul Requirement:
Average-Case vs Worst-Case K Expected rate r WiP(Wi Worst-case rate [Maddah-Ali and Niesen 14 max r =1.NK Obviously N K 7(WL)P(W1)≤.maxr(W) However, constant-factor results do Not carry over from the worst case to the average case max K ∑r(W)P(W≤C max r wWi L=1,,|N K ∑=1r*(W)P(W
Average-Case vs. Worst-Case 5 • Expected rate: • Worst-case rate [Maddah-Ali and Niesen `14]: • Obviously: • However, constant-factor results do NOT carry over from the worst case to the average case 𝑖=1 𝑁 𝐾 𝑟(𝑊𝑖)𝑃(𝑊𝑖) max 𝑖=1,…,𝑁𝐾 𝑟(𝑊𝑖 ) 𝑖=1 𝑁 𝐾 𝑟(𝑊𝑖 )𝑃 𝑊𝑖 ≤ max 𝑖=1,…,𝑁𝐾 𝑟(𝑊𝑖 ) max 𝑖=1,…,𝑁𝐾 𝑟(𝑊𝑖) max 𝑖=1,…,𝑁𝐾 𝑟 ∗(𝑊𝑖) ≤ 𝑐 σ𝑖=1 𝑁 𝐾 𝑟(𝑊𝑖)𝑃(𝑊𝑖) σ𝑖=1 𝑁𝐾 𝑟 ∗(𝑊𝑖)𝑃(𝑊𝑖) ≤ 𝑐