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.