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设计高性能调度和路由所需的基本网络科学。我们还计划将一些问题既作为有趣的本科项目，并开发有关通信网络设计数学的新研究课程。