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

合作研究：NEDG：部分信息结构下的网络调度与路由

• 批准号: 0831580
• 负责人: Constantine Caramanis
• 金额: $ 9.82万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0831580&HistoricalAwards=false
• 关键词: Collaborative; Research; NEDG; Network; Scheduling

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.

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