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

今天，互联网数据流量正在经历巨大的增长，其中大部分将是以内容为导向的应用，如视频点播服务。然而，传统技术在实现如此显著的吞吐量增加的目标方面受到严重限制。编码缓存是在流量高峰期平滑网络流量的有效方法。如果共同设计高速缓存放置和编码传送方案，则编码高速缓存有可能将(相对)便宜的存储器变成昂贵的带宽，即网络中的总流量负载与每个用户的存储器成反比。尽管在过去的几年里做了大量的工作，但大多数关于编码缓存的研究都集中在相对简单的对称网络拓扑结构上，如共享链路、设备到设备和分层网络，并且主要利用由于网络上的聚合存储而产生的全局乘性缓存收益。在实践中，用户和服务器可以在一般网络拓扑下通信，例如经由中间交换机/路由器。研究一般的拓扑缓存网络是至关重要的，因为网络拓扑为缓存设计增加了一个有价值的新维度。这允许从网络拓扑中获得新的全局缓存收益，而不是从聚合内存中获得收益。由于与一般拓扑相关的技术挑战，一般网络的编码缓存的基本限制的研究在文献中很少有尝试。这些工作的信息理论逆要么被遗漏，要么基于高度限制性的假设。因此，一般拓扑缓存网络的基本限制在很大程度上是未知的。这个项目迈出了重要的第一步，通过研究通用缓存网络的基本限制来应对它们的挑战。该项目的主要目标是开发基于拓扑的编码缓存方案，并利用信息论逆来利用作为网络拓扑的函数的附加全局乘性增益。该项目有两个主要研究主题：1)基于拓扑的一般有线缓存网络可实现方案的设计；2)一般有线缓存网络的信息论逆的表征。对于推力1，我们的方法是通过新颖的组合设计方法，基于特定的网络拓扑，对缓存放置、编码组播消息生成和传递进行联合设计。所提出的方法将导致独特的可实现的编码方案，该编码方案可以利用来自缓存和网络拓扑的编码缓存增益。这些将显著改进将缓存、消息生成和交付分开的现有设计，并且可以在某些参数制度下实现信息理论的外部边界。对于推力2，我们的方法是基于从网络拓扑派生的新的信息论不等式来建立信息论外部边界(不可能)，并允许联合生成和传递依赖于网络拓扑的编码多播消息。虽然这个项目的重点是开发新的方法，以深入了解一般拓扑有线缓存网络的基本限制，但它也为进一步研究一般拓扑无线缓存网络奠定了坚实的技术基础。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.