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

CIF：小：具有一般拓扑的缓存网络的基本限制

• 批准号: 1817154
• 负责人: Mingyue Ji
• 金额: $ 30万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1817154&HistoricalAwards=false
• 关键词: CIF; Small; Fundamental; Limits; Caching

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.

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

项目成果

Secure Distributed Linearly Separable Computation

安全分布式线性可分离计算

• DOI: 10.1109/isit45174.2021.9517896
• 发表时间: 2021
• 期刊: 2021 IEEE International Symposium on Information Theory (ISIT
• 作者: Wan, Kai;Sun, Hua;Ji, Mingyue;Caire, Giuseppe
• 通讯作者: Caire, Giuseppe

Cache-Aided Scalar Linear Function Retrieval

缓存辅助标量线性函数检索

• DOI: 10.1109/isit44484.2020.9173997
• 发表时间: 2020
• 期刊: 2020 IEEE International Symposium on Information Theory (ISIT
• 作者: Wan, Kai;Sun, Hua;Ji, Mingyue;Tuninetti, Daniela;Caire, Giuseppe
• 通讯作者: Caire, Giuseppe

Private Cache-aided Interference Alignment for Multiuser Private Information Retrieval

用于多用户私有信息检索的私有缓存辅助干扰对齐

• 发表时间: 2020
• 期刊: and Wireless Networks (WiOPT
• 作者: Zhang, Xiang;Wan, Kai;Sun, Hua;Ji, Mingyue Ji;Caire, Giuseppe
• 通讯作者: Caire, Giuseppe

Fundamental Limits of Decentralized Data Shuffling

• DOI: 10.1109/tit.2020.2966197
• 发表时间: 2020-06-01
• 期刊: IEEE TRANSACTIONS ON INFORMATION THEORY
• 影响因子: 2.5
• 作者: Wan, Kai;Tuninetti, Daniela;Piantanida, Pablo
• 通讯作者: Piantanida, Pablo

Throughput-Outage Analysis and Evaluation of Cache-Aided D2D Networks With Measured Popularity Distributions

• DOI: 10.1109/twc.2019.2935452
• 发表时间: 2019-11-01
• 期刊: IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS
• 影响因子: 10.4
• 作者: Lee, Ming-Chun;Ji, Mingyue;Sastry, Nishanth
• 通讯作者: Sastry, Nishanth