This project aimed to tackle the challenges of general caching networks with different topologies by studying their fundamental limits. The main outcomes are as follows.

First, we aimed to design optimal achievable schemes for caching networks with different topologies. We found that it needs to design topology-based schemes to achieve (order) optimal performance instead of “separate” designs without considering topologies. We mainly studied the following fundamental topologies and corresponding problems. 1) Shared-link Topology. Specifically, we first generalized the seminal coded caching problem on file retrieval to function retrieval, where users may request linear functions of files. We proposed a novel “alternative coding” approach achieving the same communication load as that of file retrieval for scalar linear functions. Then, we studied the file retrieval with correlated files and proposed novel interference alignment-based approaches achieving optimal load within a factor of 2 under uncoded cache placement. 2) Device-to-Device (D2D) Topology. Specifically, we first studied D2D coded caching with low-complexity and introduced a new design framework named Packet Type-based design, which significantly reduces required subpacketizations while keeping the optimal load. This showed that the design philosophy for D2D coded caching is fundamentally different from that for shared-link caching. Second, we studied D2D coded caching with demand privacy. We introduced two novel order optimal approaches based on “virtual users” and “non-virtual users”. Third, we studied D2D uncoded caching under real demand distribution shown to be Mandelbrot-Zipf distribution by us. Using this framework with different channel models, we showed that the promised caching gain can be indeed achieved for single-hop/multi-hop networks. Finally, due to the inherent connection between D2D coded caching and Coded Distributed Computing (CDC), we extended the proposed idea to CDC, where we studied heterogeneous and/or cascaded computations and proposed a novel low-complexity combinatorial design named hypercube/hypercuboid. Importantly, this algorithm was implemented on Amazon EC2, and its computing time coincides the theoretical results, which is the first time shown in the literature. This algorithm is much more flexible and superior to the state-of-the-art approaches. Moreover, we extended the proposed approaches to a more practical fat-tree topology and decentralized data shuffling problem. 3) Combination Network Topology, where the relays can either cache or not. We proposed a new two-phase delivery approach based on this topology. There are four key outcomes, (1) cache placement is asymmetric and depends on topology; (2) cache placement is coded instead of uncoded; (3) delivery scheme is aware of the topology and can be generalized to other topologies; (4) cache placement can be applied at relays and the cache at each relay can play a similar role as the cache at users. 4) Multi-server and Multi-user Topology. Specifically, we studied the cache-aided Multi-user Private Information Retrieval (MuPIR), where there are multiple non-colluding servers, each connecting with all cache-aided users via a shared-link. Under server-/user-privacy, we proposed two novel (order) optimal approaches which are cache-aided interference alignment and “product design”. We found that the benefit of coded caching and PIR can be achieved simultaneously. 5) Fog-Radio-Access-Network (Fog-RAN) Topology, which is a combination of shared-link, combination and D2D topologies. Several novel achievable approaches based on topology and coded cache placement were proposed to achieve the order optimal performance.

Second, we aimed to derive new converses using “cyclic side information graph”, which is challenging and requires to develop new information theoretic tools. Our major achievements are as follows. 1) For the shared-link coded caching with correlated files, we developed converse bound using the “cyclic side information graph” and obtained the best converse bound so far. 2) For D2D coded caching with demand privacy and cache-aided MuPIR, we introduced a novel “converse-tree” tool, which can have wide range of applications for cache and privacy related problems. This is the first converse bound for caching problems that genuinely accounts for the demand privacy constraint. 3) For multi-hop uncoded D2D caching, we proposed a new converse bound based on a novel application of the transport capacity developed for wireless ad-hoc networks. 4) For CDC and Fog-RAN problems, we proposed a new topology-based converse approach and proposed a new converse approach based on a novel application of Han’s inequality. This converse removes the notorious “floor” operator in a typical cut-set bound argument. 

This project built a solid theoretical foundation in caching networks with different topologies. It also shares a significant portion of theoretical perspectives with distributed storage and computing systems. This project provides new methodology in both achievability and information theoretic converse such that it has the potential to revolutionize the state-of-the-art of wireline and wireless networking technologies and to meet the challenges of orders of magnitude increase in network performance. Both undergraduate and graduate students including under-represented groups gained valuable research experiences from this project. The PIs have incorporated the research outcomes into courses such as Information Theory, Error Control Coding, and Fundamentals of Cloud Systems.

Last Modified: 01/29/2023
Modified by: Mingyue Ji