CIF: Small: Fundamental Limits of Caching Networks with General Topologies

点击翻译按钮获取中文摘要

Today, Internet data traffic is experiencing a tremendous growth and the majority will be content-oriented application such as video-on-demand services. Conventional technologies, however, are severely limited towards the goal of achieving such a dramatic throughput gain. Coded caching is an effective way to smooth out network traffic during peak traffic hours. If one jointly designs cache placement and coded delivery schemes, coded caching has the potential to turn (relatively) cheap memory into expensive bandwidth, i.e., the total traffic load in the network becomes inversely proportional to the per user memory. Despite a significant amount of work in the past few years, most studies on coded caching focus on relatively simple symmetric network topologies such as shared link, device-to-device, and hierarchical networks, and mainly exploit the global multiplicative caching gain due to the aggregate memory over the network. In practice, users and servers may communicate under general network topologies, e.g., via intermediate switches/routers. It is critical to study general topology caching networks because network topologies add a valuable new dimension to caching designs. This enables new global caching gains from network topologies beyond those from the aggregate memory. Due to the technical challenges associated with general topologies, the study of fundamental limits of coded caching for general networks has very few attempts in the literature. The information theoretic converse for these works are either missed or are based on highly restrictive assumptions. Hence, the fundamental limits of general topology caching networks are largely unknown. This project takes the first major step to tackle the challenges of general caching networks by studying their fundamental limits. The main goal is to develop topology-based coded caching schemes and the information theoretic converse to exploit the additional global multiplicative gain as a function of network topology.This project has two main research thrusts: 1) Topology based design of achievable schemes for general wireline caching networks; 2) Characterization of information theoretic converse for general wireline caching networks. For Thrust 1, our methodology is a joint design of cache placement, coded multicast message generation, and delivery based on specific network topology via novel combinatorial design methods. The proposed approaches will lead to unique achievable coding schemes that can exploit the coded caching gain from both caches and network topologies. These will significantly improve existing designs that separate caching, message generation, and delivery, and can achieve the information theoretic outer bounds under certain parameter regimes. For Thrust 2, our methodology is establishing information theoretic outer bounds (impossibilities) based on novel information theoretic inequalities derived from network topologies and allowing joint generation and delivery of coded multicast messages depending on network topologies. While this project focuses on developing new methodologies towards a deep understanding of the fundamental limits for general topology wireline caching networks, it also lays a strong technical foundation for further studies of general topology wireless caching networks.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.