Caching Networks

Lecture 1

1. Introduction to Caching Networks (Motivations)

2. Examples Caching Networks: shared link and Device-to-Device (D2D) caching networks

Lecture 2

1. Basic Information Theory: Entropy
   

• References:

  • C. E. Shannon, “A mathematical theory of communication,” in The Bell System Technical Journal, vol. 27, no. 3, pp. 379-423, July 1948.

  • Cover, Thomas M., and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2012. (Chapter 2)

Lecture 3

1. Basic Information Theory:

   1. Entropy Family: Joint Entropy, Conditional Entropy, Chain Rule

   2. Relative Entropy Family: Mutual Information, Relative Entropy, Chain Rule

   3. Fundamental Information Inequalities: Data Processing Inequality

• References:

  • Cover, Thomas M., and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2012. (Chapter 2)

  • El Gamal, Abbas, and Young-Han Kim. Network information theory. Cambridge university press, 2011. (Chapter 2)

Lecture 4

1. Basic Information Theory:

   1. Fundamental Information Inequalities: Fano's Inequality

   2. Asymptotic Equipartition Property: Definition, Typical Average Lemma, 4 Properties

• References:

  • Cover, Thomas M., and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2012. (Chapter 2, 3)

  • El Gamal, Abbas, and Young-Han Kim. Network information theory. Cambridge university press, 2011. (Chapter 2)

Lecture 5

1. Lossless Source Coding Theorem

   1. Achievability: Typicality Coding, Random Binning

   2. Converse

• References:

  • El Gamal, Abbas, and Young-Han Kim. Network information theory. Cambridge university press, 2011. (Chapter 3, 10)

Lecture 6

1. Introduction to Network Coding

   1. Historic Notes

      1. Multiuser Information Theory: Point-to-Point channel, Multiple Access Channel, Broadcast Channel

      2. Networking: Noiseless Link, Routing

   2. The Butterfly Network: Single Source Multicast, Multiple Source Multicast

• References:

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 17)

Lecture 7

1. Introduction to Network Coding

   1. The Butterfly Network: Single Source Multicast, Multiple Source Multicast, Multiple Source Unicast

   2. Wireless/Satellite System and Examples of Index Coding

   3. Source Separation

2. Definition of Point-to-Point Communication Networks (Graphical Networks)

3. Max-Flow Min-Cut Theorem

   1. Examples of Routing achieving min-cut

• References:

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 17, 18)

Lecture 8

1. Examples of Routing and Networks Coding (Butterfly networks, Storage System)

2. Proof of Max-Flow Min-Cut Theorem via Linear Programming

• References:

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 18)

  • El Gamal, Abbas, and Young-Han Kim. Network information theory. Cambridge university press, 2011. (Chapter 15)

Lecture 9

1. Definition of Network Codes (NC)

2. Proof of Max-Flow Upper Bounds

• References:

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 18)

Lecture 10

1. Global and Local Encoding Kernels

2. Koetter Medard Formula

• References:

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 19)

  • Koetter, Ralf, and Muriel Medard. “An algebraic approach to network coding.” IEEE/ACM Transactions on Networking (TON) 11, no. 5 (2003): 782-795.

Lecture 11

1. Implementation of Linear Network Codes (LNC)

2. Existence and Constructions

• References:

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 19)

  • Koetter, Ralf, and Muriel Medard. “An algebraic approach to network coding.” IEEE/ACM Transactions on Networking (TON) 11, no. 5 (2003): 782-795.

Lecture 12

1. Combination Networks

2. Desirable Properties of LNC

• References:

  • Xiao, Ming, Muriel Medard, and Tor Aulin. “A binary coding approach for combination networks and general erasure networks.” In 2007 IEEE International Symposium on Information Theory, pp. 786-790. IEEE, 2007.

  • Yeung, Raymond W. Information theory and network coding. Springer Science & Business Media, 2008. (Chapter 19)

Lecture 13

1. Index Coding (IC)

   1. Definitions and Examples

   2. Graph Theory and Index Codes (clique number, chromatic number, independence number, etc)

• References:

  • Birk, Yitzhak, and Tomer Kol. “Informed-source coding-on-demand (ISCOD) over broadcast channels.” In INFOCOM’98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 3, pp. 1257-1264. IEEE, 1998.

  • Bar-Yossef, Ziv, Yitzhak Birk, T. S. Jayram, and Tomer Kol. “Index coding with side information.” IEEE Transactions on Information Theory 57, no. 3 (2011): 1479-1494.

Lecture 14

1. Minrank

2. Interference Alignment and Index Coding

• References:

  • Bar-Yossef, Ziv, Yitzhak Birk, T. S. Jayram, and Tomer Kol. “Index coding with side information.” IEEE Transactions on Information Theory 57, no. 3 (2011): 1479-1494.

  • Jafar, Syed Ali. “Topological interference management through index coding.” IEEE Transactions on Information Theory 60, no. 1 (2014): 529-568.

Lecture 15

1. Equivalence between IC and NC

• References:

  • El Rouayheb, Salim, Alex Sprintson, and Costas Georghiades. “On the index coding problem and its relation to network coding and matroid theory.” IEEE Transactions on Information Theory 56, no. 7 (2010): 3187-3195.

  • Effros, Michelle, Salim El Rouayheb, and Michael Langberg. “An equivalence between network coding and index coding.” IEEE Transactions on Information Theory 61, no. 5 (2015): 2478-2487.

Lecture 16

1. Conventional Caching Networks

2. Single Cache Systems

• References:

  • ISIT 2015 Tutorial: Part 1, Part 2

Lecture 17

1. Shared Link Caching Networks

   1. Examples

   2. Networking Equivalent problem

• References:

  • ISIT 2015 Tutorial: Part 3

  • Maddah-Ali, Mohammad Ali, and Urs Niesen. “Fundamental limits of caching.” IEEE Transactions on Information Theory 60, no. 5 (2014): 2856-2867.

Lecture 18

1. Shared Link Caching Networks

   1. Converse (example)

   2. Formal Problem Definition

   3. Single-Cache System Converse

   4. General Centralized Achievability

• References:

  • Maddah-Ali, Mohammad Ali, and Urs Niesen. “Fundamental limits of caching.” IEEE Transactions on Information Theory 60, no. 5 (2014): 2856-2867.

Lecture 19

1. General Centralized Achievability (Cont.)

2. General Converse

3. Tight Bound Example (Converse)

• References:

  • Maddah-Ali, Mohammad Ali, and Urs Niesen. “Fundamental limits of caching.” IEEE Transactions on Information Theory 60, no. 5 (2014): 2856-2867.

Lecture 20

1. Tight Bound Example (Achievability)

2. Memory Sharing Scheme (Example)

3. Decentralized Achievability

• References:

  • Maddah-Ali, Mohammad Ali, and Urs Niesen. “Decentralized coded caching attains order-optimal memory-rate tradeoff.” IEEE/ACM Transactions on Networking (TON) 23, no. 4 (2015): 1029-1040.

Lecture 21

1. Complexity Analysis and Greedy Constraint Coloring

2. Device-to-Device Caching Networks

   1. Problem Definitions

• References:

  • Ji, Mingyue, Antonia M. Tulino, Jaime Llorca, and Giuseppe Caire. “Order-optimal rate of caching and coded multicasting with random demands.” arXiv preprint arXiv:1502.03124 (2015).

  • K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca and A. G. Dimakis., “Finite-Length Analysis of Caching-Aided Coded Multicasting,” in IEEE Transactions on Information Theory, vol. 62, no. 10, pp. 5524-5537, Oct. 2016.

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “Fundamental limits of caching in wireless D2D networks.” IEEE Transactions on Information Theory 62, no. 2 (2016): 849-869.

Lecture 22

1. Online Coded Caching

2. Cache-aided Interference Networks

• References:

  • Pedarsani, Ramtin, Mohammad Ali Maddah-Ali, and Urs Niesen. “Online coded caching.” IEEE/ACM Transactions on Networking 24, no. 2 (2016): 836-845.

  • Yan, Qifa, Udaya Parampalli, Xiaohu Tang, and Qingchun Chen. “Online Coded Caching with Random Access.” IEEE Communications Letters (2016).

  • Naderializadeh, Navid, Mohammad Ali Maddah-Ali, and A. Salman Avestimehr. “Fundamental limits of cache-aided interference management.” arXiv preprint arXiv:1602.04207 (2016).

  • Hachem, Jad, Urs Niesen, and Suhas Diggavi. “Degrees of freedom of cache-aided wireless interference networks.” arXiv preprint arXiv:1606.03175 (2016).

Lecture 23

1. D2D Caching Networks

   1. Definition

   2. Achievability (Centralized )

   3. Converse

• References:

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “Fundamental limits of caching in wireless D2D networks.” IEEE Transactions on Information Theory 62, no. 2 (2016): 849-869.

Lecture 24

1. D2D Caching Networks

   1. Achievability ()

   2. Tradeoff between complexity and communication schemes

   3. Throughput-Outage

• References:

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “Fundamental limits of caching in wireless D2D networks.” IEEE Transactions on Information Theory 62, no. 2 (2016): 849-869.

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “The throughput-outage tradeoff of wireless one-hop caching networks.” IEEE Transactions on Information Theory 61, no. 12 (2015): 6833-6859.

Lecture 25

1. Decentralized D2D Caching Networks

2. Concentration of Measure (Entropy Method)

• References:

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “Fundamental limits of caching in wireless D2D networks.” IEEE Transactions on Information Theory 62, no. 2 (2016): 849-869.

  • Ledoux, Michel. The concentration of measure phenomenon. No. 89. American Mathematical Soc., 2005. (Chapter 6)

  • Raginsky, Maxim, and Igal Sason. Concentration of Measure Inequalities in Information Theory, Communications, and Coding. Now Publishers Inc., 2014.

Lecture 26

1. The Proof of the Main Theorem in Decentralized D2D Caching Networks

2. Shared Link Caching Networks with Multiple Requests

• References:

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “Fundamental limits of caching in wireless D2D networks.” IEEE Transactions on Information Theory 62, no. 2 (2016): 849-869.

  • Ji, Mingyue, Antonia M. Tulino, Jaime Llorca, and Giuseppe Caire. “Caching and coded multicasting: Multiple groupcast index coding.” In Signal and Information Processing (GlobalSIP), 2014 IEEE Global Conference on, pp. 881-885. IEEE, 2014.

  • Ji, Mingyue, Antonia Tulino, Jaime Llorca, and Giuseppe Caire. “Caching-aided coded multicasting with multiple random requests.” In Information Theory Workshop (ITW), 2015 IEEE, pp. 1-5. IEEE, 2015.

  • Sengupta, Avik, and Ravi Tandon. “Improved approximation of storage-rate tradeoff for caching with multiple demands.” arXiv preprint arXiv:1606.04202(2016).

  • Hachem, Jad, Nikhil Karamchandani, and Suhas Diggavi. “Effect of number of users in multi-level coded caching.” In 2015 IEEE International Symposium on Information Theory (ISIT), pp. 1701-1705. IEEE, 2015.

Lecture 27

1. Shared Link Caching Networks with Random Demands

2. Femtocell Caching Networks

• References:

  • Niesen, Urs, and Mohammad Ali Maddah-Ali. “Coded caching with nonuniform demands.” In Computer Communications Workshops (INFOCOM WKSHPS), 2014 IEEE Conference on, pp. 221-226. IEEE, 2014.

  • Ji, Mingyue, Antonia M. Tulino, Jaime Llorca, and Giuseppe Caire. “On the average performance of caching and coded multicasting with random demands.” In 2014 11th International Symposium on Wireless Communications Systems (ISWCS), pp. 922-926. IEEE, 2014.

  • Ji, Mingyue, Antonia M. Tulino, Jaime Llorca, and Giuseppe Caire. “Order-optimal rate of caching and coded multicasting with random demands.” arXiv preprint arXiv:1502.03124 (2015).

  • Hachem, Jad, Nikhil Karamchandani, and Suhas Diggavi. “Multi-level coded caching.” In 2014 IEEE International Symposium on Information Theory, pp. 56-60. IEEE, 2014.

  • Shanmugam, Karthikeyan, Negin Golrezaei, Alexandros G. Dimakis, Andreas F. Molisch, and Giuseppe Caire. “Femtocaching: Wireless content delivery through distributed caching helpers.” IEEE Transactions on Information Theory 59, no. 12 (2013): 8402-8413.

  • Karamchandani N, Niesen U, Maddah-Ali MA, Diggavi SN. Hierarchical coded caching. IEEE Transactions on Information Theory. 2016 Jun;62(6):3212-29.

Lecture 28

1. Femtocell Caching Networks

2. Distributed Storage Theory

• References:

  • Shanmugam, Karthikeyan, Negin Golrezaei, Alexandros G. Dimakis, Andreas F. Molisch, and Giuseppe Caire. “Femtocaching: Wireless content delivery through distributed caching helpers.” IEEE Transactions on Information Theory 59, no. 12 (2013): 8402-8413.

  • Dimakis, Alexandros G., P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan Ramchandran. “Network coding for distributed storage systems.” IEEE Transactions on Information Theory 56, no. 9 (2010): 4539-4551.

  • Dimakis, Alexandros G., Kannan Ramchandran, Yunnan Wu, and Changho Suh. “A survey on network codes for distributed storage.” Proceedings of the IEEE 99, no. 3 (2011): 476-489.

Lecture 29

1. Distributed Storage Theory

2. The Relation between Distributed Storage System, Caching Networks and Distributed Computing Systems

• References:

  • Ji, Mingyue, Giuseppe Caire, and Andreas F. Molisch. “Fundamental limits of caching in wireless D2D networks.” IEEE Transactions on Information Theory 62, no. 2 (2016): 849-869.

  • Dimakis, Alexandros G., P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan Ramchandran. “Network coding for distributed storage systems.” IEEE Transactions on Information Theory 56, no. 9 (2010): 4539-4551.

  • Li, Songze, Mohammad Ali Maddah-Ali, Qian Yu, and A. Salman Avestimehr. “A Fundamental Tradeoff between Computation and Communication in Distributed Computing.” arXiv preprint arXiv:1604.07086 (2016).