Communication-optimal coding designs for caching networks

Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this survey paper, we review three recent main results on cache networks, which not only considerably sharpen the approximate characterization of the rate-memory trade off, but also extend those results to more general networks. In these systems, a server with a database of some files (e.g. movies) is connected to multiple users via a communication network. Each user has an isolated memory of limited size that can be used for caching. The system operates in two phases: a placement phase where users each store a portion of the files in their local cache, and a delivery phase, where the users each request a file and the server delivers coded messages to the users, fulfilling their file requests. We start by considering the shared bottleneck network in two flavors of the system, with uncoded prefetching and with coded prefetching. First, for uncoded prefetching, an optimal design is proposed, under both centralized and decentralized settings, for both peak rate and average rate. The exact optimality is proven through a matching converse. Second, for caching with coded prefetching, we present a design that is optimal within a factor of approximately 2, which strictly improves the state of the art. Lastly, we move the focus to more general network topologies, and present an order-wise optimal scheme that is independent of the underlying communication network between the server and the users. This scheme is shown to achieve the minimum delivery delay with a constant factor for all memoryless networks.

Original languageEnglish (US)
Title of host publication2017 IEEE Information Theory Workshop, ITW 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509030972
StatePublished - Jul 2 2017
Externally publishedYes
Event2017 IEEE Information Theory Workshop, ITW 2017 - Kaohsiung, Taiwan, Province of China
Duration: Nov 6 2017Nov 10 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2017 IEEE Information Theory Workshop, ITW 2017
Country/TerritoryTaiwan, Province of China

Bibliographical note

Funding Information:
VI. ACKNOWLEDGEMENT This work is in part supported by NSF grants CCF-1408639, NETS-1419632, ONR award N000141612189, NSA grant, and a research gift from Intel.

Publisher Copyright:
© 2017 IEEE.


Dive into the research topics of 'Communication-optimal coding designs for caching networks'. Together they form a unique fingerprint.

Cite this