References & Further Reading

References

1. M. A. Maddah-Ali and U. Niesen, Fundamental Limits of Caching, 2014

   The founding paper of coded caching. Introduces the shared-link model, the combinatorial placement scheme, and the cut-set converse bound. Essential reading for any student of this book.

2. L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, Web Caching and Zipf-like Distributions: Evidence and Implications, 1999

   The empirical basis for the Zipf assumption in caching. Established that web requests follow a Zipf distribution with exponent 0.6–0.8, which drove two decades of CDN design.

3. T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley-Interscience, 2nd ed., 2006

   The reference for the information-theoretic foundations used throughout this book: entropy, mutual information, Fano's inequality.

4. S. Jin, Y. Cui, H. Liu, and G. Caire, Structural Properties of Uncoded Placement Optimization for Coded Delivery, 2017

   Analyzes the optimal uncoded placement when demands follow a popularity distribution. Establishes the structural result that popular files should be cached uniformly across users.

5. Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, The Exact Rate-Memory Tradeoff for Caching with Uncoded Prefetching, 2018

   The definitive converse result: under uncoded placement, the MAN scheme is exactly optimal for worst-case demands. Closes the factor-of-12 gap from Maddah-Ali–Niesen 2014 to exactly 1.

6. M. Ji, G. Caire, and A. F. Molisch, Fundamental Limits of Caching in Wireless D2D Networks, 2016

   Caire group's foundational paper on D2D coded caching. Establishes the $\Theta(M/N)$ per-user throughput scaling law we will meet in Chapter 10. Cite this when discussing how caching + D2D trade off.

7. M. Z. Shafiq, A. X. Liu, and A. R. Khakpour, Revisiting Caching in Content Delivery Networks, 2014

   Empirical study of real CDN workloads. Validates Zipf assumptions in practice and quantifies the working-set-size effect in production caches.

8. A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011

   The textbook for multiuser information theory: broadcast channels, interference channels, relay networks. Our shared-link caching network inherits notation and concepts from Chapters 5 and 6.

9. S. Borst, V. Gupta, and A. Walid, Distributed Caching Algorithms for Content Distribution Networks, 2010

   Pre-coded-caching perspective on CDN design. Good for understanding why the Caire–Maddah-Ali–Niesen question was so surprising: for a decade researchers had studied caching without considering codes.

10. A. Dan and D. Towsley, An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes, 1990

    Classical analysis of cache replacement policies. The LFU (popularity caching) optimality result traces back to this era of caching theory.

11. N. C. Fofack, M. Dehghan, D. Towsley, and D. F. Towsley, Performance Evaluation of Hierarchical TTL-Based Cache Networks, 2014

    Modern CDN analysis with TTL (time-to-live) dynamics. Useful complement to our static model for understanding commercial deployments.

Further Reading

• The original Maddah-Ali–Niesen paper

  M. A. Maddah-Ali and U. Niesen, 'Fundamental limits of caching,' IEEE Trans. IT, 2014

  There is no substitute for reading the founding paper. Section II formalizes the model exactly as we do here; Section III constructs the scheme; Section IV proves the converse. Budget a full weekend.

• A CDN engineer's view

  G. Pallis and A. Vakali, 'Insight and Perspectives for Content Delivery Networks,' Communications of the ACM, 2006

  Non-technical overview of how commercial CDNs work. Useful for understanding why production systems still run popularity caching despite the theoretical superiority of coded schemes.

• Network information theory background

  A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge 2011 — Chapters 5–6

  The broadcast channel and multi-user channels section. Foundational for understanding why coded caching is not just a CDN trick but a fundamental information-theoretic phenomenon.

• The cache-hit debate

  Sen et al., 'Analyzing Peer-Assisted Online Hosting Services,' IMC 2012

  Empirical evidence that peer-assisted delivery (a form of D2D caching) already works in the wild. Sets up the motivation for the D2D coded caching of Chapters 10–11.