Fundamental Limits of Combinatorial Multi-Access Caching

被引:18
作者
Brunero, Federico [1 ]
Elia, Petros [1 ]
机构
[1] Sophia Antipolis, Commun Syst Dept, EURECOM, F-06410 Biot, France
基金
欧洲研究理事会;
关键词
Topology; Encoding; Network topology; Servers; Libraries; Indexes; 3G mobile communication; Coded caching; combinatorial topology; index coding; information-theoretic converse; multi-access coded caching (MACC); MEMORY TRADE-OFF; DELIVERY; SCHEMES; GAINS;
D O I
10.1109/TIT.2022.3193723
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This work identifies the fundamental limits of multi-access coded caching (MACC) where each user is connected to multiple caches in a manner that follows a generalized combinatorial topology. This topology stands out as it allows for unprecedented coding gains, even with very modest cache resources. First, we extend the setting and the scheme presented by Muralidhar et al. to a much more general topology that supports both a much denser range of users and the coexistence of users connected to different numbers of caches, all while maintaining the astounding coding gains - here proven to be exactly optimal - associated with the combinatorial topology. This is achieved, for this generalized topology, with a novel information-theoretic converse that we present here, which establishes, together with the scheme, the exact optimal performance under the assumption of uncoded placement. We subsequently consider different connectivity ensembles, including the very general scenario of the entire ensemble of all possible network connectivities/topologies, where any subset of caches can serve any arbitrary number of users. For these settings, we develop novel converse bounds on the optimal performance averaged over the ensemble's different connectivities. This novel analysis of topological ensembles leaves open the possibility that currently-unknown topologies may yield even higher gains, a hypothesis that is part of the bigger question of which network topology yields the most caching gains.
引用
收藏
页码:1037 / 1056
页数:20
相关论文
共 71 条
[1]   Cache-Aided Content Delivery Over Erasure Broadcast Channels [J].
Amiri, Mohammad Mohammadi ;
Gunduz, Deniz .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2018, 66 (01) :370-381
[2]   Fundamentals of Index Coding [J].
Arbabjolfaei, Fatemeh ;
Kim, Young-Han .
FOUNDATIONS AND TRENDS IN COMMUNICATIONS AND INFORMATION THEORY, 2018, 14 (3-4) :164-346
[3]  
Arbabjolfaei F, 2013, IEEE INT SYMP INFO, P962, DOI 10.1109/ISIT.2013.6620369
[4]   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
[5]   Cache-Aided Communications With Multiple Antennas at Finite SNR [J].
Bergel, Itsik ;
Mohajer, Soheil .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2018, 36 (08) :1682-1691
[6]  
Brunero F, 2021, Arxiv, DOI arXiv:2109.04807
[7]   Degrees of Freedom of Cache-Aided Wireless Cellular Networks [J].
Cao, Youlong ;
Tao, Meixia .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2020, 68 (05) :2777-2792
[8]  
Chang C.-H., 2020, IEEE ICC, DOI DOI 10.1109/icc40277.2020.9149113
[9]  
Chang CH, 2019, IEEE INT SYMP INFO, P11, DOI 10.1109/ISIT.2019.8849357
[10]   A Novel Transformation Approach of Shared-link Coded Caching Schemes for Multiaccess Networks [J].
Cheng, Minquan ;
Liang, Dequan ;
Wan, Kai ;
Zhang, Mingming ;
Caire, Giuseppe .
2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2021, :849-854