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

University Of Texas At Austin, Austin TX

Investigators

Abstract

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.