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

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

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.