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

Purdue University, West Lafayette IN

Investigators

Abstract

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.