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.