Collaborative Research: NEDG: Network Scheduling and Routing under Partial Information Structure

尽管无线网络在公共、商业和政府领域取得了明显的成功，但最近的研究表明，糟糕的路由/调度会严重损害它们的性能。我们注意到，观察到的不可接受的性能损失不是文献中调度/路由算法缺乏或不足的结果；相反，原因是这些算法所假定的信息结构（通道状态、队列状态、拓扑结构等）。这一建议引导了一条不同的道路，开始了一个概念上的转变，即信息结构的首要重要性。我们考虑的实际场景中，只有一小部分的网络状态可以探索。本提案的目标是双重的：(a)描述部分/延迟网络状态信息（NSI）对网络吞吐量和其他性能指标（如延迟和可靠性）的基本影响，以及(b)开发高性能和分布式算法，可以根据部分信息进行最佳操作。更广泛的影响：我们相信这项工作可以为进一步设计具有有限NSI的高性能调度和路由所需的基础网络科学做出贡献。我们还计划将其中一些问题作为有趣的本科项目，以及开发一门新的研究生水平的通信网络设计数学课程。

Despite the clear success stories of wireless networks in the public, commercial, and governmental realms, recent work has shown that poor routing/scheduling can significantly impair their performance. We note that the unacceptable performance loss observed is not a consequence of a lack or deficiency of scheduling/routing algorithms in the literature; rather the cause is the information structure (channel state, queue state, topology, etc) that these algorithms assume. This proposal steers down a different path, initiating a conceptual shift toward the primary importance of information structure. We consider practical scenarios where only a small fraction of the network state can be explored. The goals of this proposal are two-fold: (a) characterizing the fundamental impact of partial/delayed network state information (NSI) on network throughput and other performance metrics such as delay and reliability, and (b) developing high-performance and distributed algorithms that can operate optimally subject to partial information. Broader Impact: We believe this work can contribute towards furthering basic network science required to design high-performance scheduling and routing with limited NSI. We also plan to bring some of the questions both as interesting undergraduate projects, as well as develop a new graduate-level course on the mathematics of the design of communication networks.