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 2
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,A2A3) B=(B1,B2,B3) A2 A3 Broadcast C=(C1,C2,C3) channel , B3 C2, 3 K=3 users Back-haul Requirement:Cache size M=1 Uncoded Caching (A1,B1C1) (A1,B1C1) (A1,B1C1) Individual caching gain User 1 User 2 User 3 wants A wants B wants C 3
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,B2B3) C=(C1,C2,C3) Broadcast A2 ⊕ channel B3 中 BG2 K=3 users Back-haul Requirement:Cache size M=1 Uncoded Caching K(1-9）=2 (A1,B1C1) (A2,B2,C2) (A3,B3C3) Bi Coded Caching [1] A3 B3 C2 Global caching User 1 User 2 User 3 gain wants A wants B wants C [1]Fundamental Limits of Caching,M.Maddah-Ali and U.Niesen,IEEE Trans.Inf.Theory,2014. 4
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 NK ·Expected rate: r(Wi)P(Wi) i=1 Worst-case rate [Maddah-Ali and Niesen '14]: max r(Wi) i=1,...NK ·Obviously: NK r(W)P(W)≤ max.r(Wi) i=1,...NK i=1 However,constant-factorresults do NOT carry over from the worst case to the average case max r(Wi) i=1,....NK r(W:)P(W) ≤C maxr*(Wi) ≤c-X→ i=1,...NK Σr*(W)P(W) 5
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 𝑁𝐾 𝑟 ∗(𝑊𝑖)𝑃(𝑊𝑖) ≤ 𝑐