Coded Caching With Nonuniform Demands

被引:194
作者
Niesen, Urs [1 ,2 ]
Maddah-Ali, Mohammad Ali [3 ]
机构
[1] Bell Labs, 600 Mt Ave, Murray Hill, NJ 07974 USA
[2] Qualcomm NJ Res Ctr, Bridgewater, NJ 08807 USA
[3] Nokia, Bell Labs, Holmdel, NJ 07733 USA
关键词
Caching; coding; content distribution; prefetching; APPROXIMATION ALGORITHMS; DATA PLACEMENT;
D O I
10.1109/TIT.2016.2639522
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider a network consisting of a file server connected through a shared link to a number of users, each equipped with a cache. Knowing the popularity distribution of the files, the goal is to optimally populate the caches, such as to minimize the expected load of the shared link. For a single cache, it is well known that storing the most popular files is optimal in this setting. However, we show here that this is no longer the case for multiple caches. Indeed, caching only the most popular files can be highly suboptimal. Instead, a fundamentally different approach is needed, in which the cache contents are used as side information for coded communication over the shared link. We propose such a coded caching scheme and prove that it is close to optimal.
引用
收藏
页码:1146 / 1158
页数:13
相关论文
共 24 条
[1]   Network information flow [J].
Ahlswede, R ;
Cai, N ;
Li, SYR ;
Yeung, RW .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216
[2]  
[Anonymous], IMC07 P 2007 ACM
[3]  
[Anonymous], CODED CACHING DELAY
[4]  
[Anonymous], MULTILEVEL CODED CAC
[5]  
[Anonymous], ORDER OPTIMAL RATE C
[6]  
Baev ID, 2001, SIAM PROC S, P661
[7]   APPROXIMATION ALGORITHMS FOR DATA PLACEMENT PROBLEMS [J].
Baev, Ivan ;
Rajaraman, Rajmohan ;
Swamy, Chaitanya .
SIAM JOURNAL ON COMPUTING, 2008, 38 (04) :1411-1429
[8]   Index Coding With Side Information [J].
Bar-Yossef, Ziv ;
Birk, Yitzhak ;
Jayram, T. S. ;
Kol, Tomer .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (03) :1479-1494
[9]   Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clients [J].
Birk, Yitzhak ;
Kol, Tomer .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (06) :2825-2830
[10]   Distributed Caching Algorithms for Content Distribution Networks [J].
Borst, Sem ;
Gupta, Varun ;
Walid, Anwar .
2010 PROCEEDINGS IEEE INFOCOM, 2010,