CIF: Small: Network Information Theory Meets Network Optimization: Optimal Linear Network Coding for Packet Erasure Networks

CIF：小型：网络信息理论与网络优化的结合：数据包擦除网络的最优线性网络编码

• 批准号: 1422997
• 负责人: Chih-Chun Wang
• 金额: $ 49.31万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-11-01 至 2019-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422997&HistoricalAwards=false
• 关键词: CIF; Small; Network; Information; Theory

The development of high-rate, more efficient, and ubiquitous communication networks is a critical backbone infrastructure requirement of the 21st century. A fundamental query in studying network is thus how much information one can reliably send and how to design a scheme that attains the optimal network throughput. Presently, almost all network information theory results consist of two parts: Firstly, devising a clever solution, and then mathematically proving its optimality. Both tasks are highly non-trivial and our understanding of optimal network communications is thus still nascent. This project proposes a fundamentally new methodology, called knowledge space partition, to drastically reduce the size of the design space of network communication schemes. This allows us to use computers to systematically search for the best possible solution and automate the design of high-performance network protocols. The optimality of the resulting scheme is also guaranteed since the computer-aided search is exhaustive in nature. Based on this central idea, this project will (i) Systematically compute the linear network coding capacity for various small packet erasure networks; (ii) Design and implement optimal linear network coding protocols in practice; and (iii) Generalize the results from network-layer processing to physical-layer processing. The new methodology will unify the concepts of stability region and capacity region, with the two concepts that having long separated the networking and information theory communities. The success of this project will also imbue next generation network engineers with back-to-basics information-theoretic thinking with enormously rich network optimization techniques. With realistic settings and implementation-friendly constructions, the optimal theoretic results of this project should spur significant developments in system-level research as well. Preliminary results of this project have shown that the network coding benefits are especially significant for the loosely-coordinated low-cost solutions operated in unlicensed bands, such as Wi-Fi. The findings of this project will thus further bridge both the domestic and global digital divide. Several sub-topics of this project, e.g., using linear algebra to improve network throughput, will be used to attract minorities and women through the Vertically Integrated Projects (VIP) of Purdue, an undergraduate-research course that engages undergraduate students in a team-based hand-on research environment.

高速、更高效和无处不在的通信网络的发展是21世纪世纪的关键骨干基础设施需求。因此，网络研究中的一个基本问题是可以可靠地发送多少信息，以及如何设计一个方案，以达到最佳的网络吞吐量。目前，几乎所有的网络信息论成果都包括两个部分：首先，设计一个巧妙的解决方案，然后从数学上证明其最优性。这两项任务都是非常重要的，因此我们对最佳网络通信的理解仍然处于萌芽状态。该项目提出了一种全新的方法，称为知识空间划分，大大减少了网络通信方案的设计空间的大小。这使我们能够使用计算机系统地搜索最佳解决方案，并自动设计高性能网络协议。由于计算机辅助搜索本质上是穷举的，因此也保证了所得到的方案的最优性。基于这一中心思想，本项目将（i）系统地计算各种小包擦除网络的线性网络编码容量;（ii）在实践中设计和实现最佳线性网络编码协议;（iii）将结果从网络层处理推广到物理层处理。新的方法将统一稳定区域和容量区域的概念，这两个概念长期以来一直分离的网络和信息理论社区。该项目的成功也将为下一代网络工程师注入回归基础的信息理论思维和极其丰富的网络优化技术。随着现实的设置和实现友好的结构，该项目的最佳理论结果应该刺激系统级研究的重大发展。该项目的初步结果表明，网络编码的好处对于在未经许可的频段（如Wi-Fi）中运行的松散协调的低成本解决方案尤为重要。因此，该项目的研究结果将进一步弥合国内和全球的数字鸿沟。该项目的几个分专题，例如，使用线性代数来提高网络吞吐量，将用于通过普渡大学的垂直整合项目（VIP）吸引少数民族和妇女，这是一门本科生研究课程，让本科生参与基于团队的动手研究环境。

项目成果

Coded Caching With Full Heterogeneity: Exact Capacity of the Two-User/Two-File Case

• DOI: 10.1109/tit.2022.3181411
• 发表时间: 2022-11
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Chih-Hua Chang;B. Peleato;Chih-Chun Wang