CIF: Small: Collaborative Research: Perishable Network Information Flow

端到端延迟是所有现代通信系统固有的重要指标。随着端到端延迟要求变得越来越严格（5G无线技术的目标是小于1毫秒的延迟），并且随着本地延迟的改善正在迅速接近各个组件的物理限制，从网络的角度研究端到端延迟的基本限制至关重要。具体地说，在多跳网络中，在满足小的端到端延迟要求的情况下，可以传输的最大吞吐量是多少？该项目的研究将揭示网络通信和计算的新的延迟感知基本限制。这些结果将对信息论、算法图论和通信复杂性理论产生基本影响，并促进通常由不同科学界研究的技术学科之间的桥接和共享。低延迟方案的设计也将对许多实际应用产生直接和长期的影响，包括物联网、网络物理系统、视频会议和移动的游戏。该项目还包括将研究纳入研究生水平的讲座材料的计划。在严格（小）有限端到端延迟要求下，网络系统的信息理论容量是多少？这个问题的独特性质需要一个跨学科的方法跨越图论，计算机科学和信息理论。该项目开发了各种新的工具，包括新的流量模型，新的概率框架，和新的分布式功能计算范式，并提供了一个期待已久的理论研究，探索易逝网络信息流的图论和信息论方面。研究分为两个方向：一个是端到端时延受限的多跳网络容量，另一个是时延受限的分布式函数计算。

End-to-end delay is an inherent important metric of all modern communication systems. As the end-to-end delay requirement is becoming more stringent (5G wireless technology is aiming for a latency of less than one millisecond) and as the improvement of local delay is quickly approaching the physical limits of the individual components, it is of paramount interest to study the fundamental limits of end-to-end delay from a network's perspective. Specifically, what is the largest throughput one can transmit over a multihop network while respecting a small end-to-end delay requirement? The research in this project will uncover new delay-aware fundamental limits of network communication and computation. Such results will have a basic impact on information theory, algorithmic graph theory, and communication complexity theory and promote bridging and sharing across technical disciplines that are normally studied by different scientific communities. The design of low-delay schemes will also have immediate and long-standing impact on many practical applications, including Internet of Things, cyber-physical systems, video conferencing, and mobile gaming. The project also includes plans for integrating the research into graduate-level lecture materials.The research in this project is centered around answering the question ?what is the information-theoretic capacity of a networked system under a stringent (small) finite end-to-end delay requirement??. The distinct nature of this problem requires a cross-disciplinary approach spanning graph-theory, computer science, and information theory. This project develops various new tools including new traffic models, new probabilistic frameworks, and new distributive functional computation paradigms and provides a long overdue theoretic study that explores both the graph-theoretic and information-theoretic aspects of perishable network information flow. The research is divided into two thrusts: one focused on end-to-end delay-constrained multihop network capacity and the other focused on delay-constrained distributed function computation.