Caching through the lens of Index Coding

Sponsors:

1. NSF(Award Number:1527059) CIF: Small: Collaborative Research: From Pliable to Content-Type Coding

Problem Statement and Motivation 

• Caching is an effective way to smooth out network traffic in peak times by storing locally content during peak-off times.
• Caching has two phases: placement (limited only by the size of the local cache and designed without knowledge of future demands) and delivery (where the goal is to minimize the number of broadcast transmissions so that every receiver can decode the desired message)
• Caching is a variation of the Index Coding problem (broadcasting unicast messages with message side information at the receivers) where the side information is a design parameter for the placement phase and where messages are not necessarily unicast.
• Past work by Maddah-Ali & Niesen showed that uncoded cache placement with linear network coding for the delivery is optimal to within a factor 4.

Technical Approach

• In this work we asked how far from optimal the scheme of Maddah-Ali & Niesen under the restriction of uncoded cache placement (which is relevant for practical reasons).
• We approached the problem from the lens of index coding.
• After uncoded cache placement, we look at the resulting multicast index coding problem.
• We extend known information theoretic inner and outer bounds for the classical unicast index coding problem to the multicast case.
• We use combinatorial arguments to account for the worst possible demands in the resulting multicast index coding problem.

Key Achievements and Future Goals

• We showed that indeed the Maddah-Ali & Niesen scheme is optimal under the restriction of uncoded cache placement when there are more users than files.
• In the process, we also derived novel inner bounds for the multicast index coding problem.
• Results presented at:
  1. Kai Wan, Daniela Tuninetti and Pablo Piantanida “On the Optimality of Uncoded Cache Placement,” Proceedings of the 2016 IEEE Information Theory Workshop (ITW 2016);
  2. Kai Wan, Daniela Tuninetti and Pablo Piantanida “On Caching with More Users than Files,” Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT 2016);
  3. Kai Wan, Daniela Tuninetti and Pablo Piantanida, “Caching through the lens of Multicast Index Coding”, IEEE Transactions on Information Theory