CAREER: Meeting Deadlines: Theories and Algorithms to Support Delay Constrained Communication in Wireless Networks

Intellectual Merit Wireless technology has emerged as a low-cost, and infrastructure-free method to deploy communication networks and has inspired a wide range of applications. Many of these applications require effective delay-control for desired performance, which, however, is one of the most difficult problems in wireless network design due to the inherent weaknesses of wireless communication such as limited bandwidth, channel fading, and interference. In the past few years, a major breakthrough in wireless network research has been to harness the power of optimization theory and stochastic network theory for network design. This theoretically grounded approach has witnessed impressive advances and resulted in a rich class of network protocols that are optimal in theory and perform well in experimental implementations. These advances, however, shed little light on communication latency (or delay) because the focus is almost exclusively on the long-term throughput. Recently, there has been a renewed interest in understanding communication latency, butmost of ongoing research focuses on analyzing the delay performance of existing mechanisms that are designed for optimizing throughput rather than delay. This CAREER proposal will take a bold step to break away from todays throughput first mentality. We will directly design networks to meet delay constraints rather than design for maximizing throughput and then study the delay performance of the resulting algorithms. Two central themes of this proposal are: This CAREER proposal will embrace a delay-oriented approach where delay is a primary design objective, not a byproduct of throughput-oriented designs. Because delay and throughput are fundamentally related metrics (a high throughput with unacceptable transmission latency or a small latency with extremely low throughput are of no use), we will establish a theoretically grounded methodology to characterize the effective throughput (the achievable throughput under delay constraints) of wireless networks and develop algorithms that achieve the effective throughput. This CAREER proposal will consider both micro-scale (packet-level and channel-level) approaches such as packet scheduling and channel interference management, and macro-scale (flow-level and network-level) approaches such that rate control, routing, and network-wide interference management, for delay control. So far, problems at different scales have been dealt with independently because of the difficulty in modeling micro-scale dynamics (at a fast time-scale) in a network optimization framework (at a slow time-scale). This proposal will close this gap by developing a unified methodology. Specifically, the effective throughput quantifies the resources required for delay constrained communications under micro-scale dynamics, and allows us to incorporate micro-scale dynamics as optimization constraints. With this unified methodology, we will develop comprehensive delay control solutions spanning multiple network layers. The objective of this CAREER proposal is to develop: (i) new network theories that quantify fundamental delay and throughput limits of wireless networks; (ii) transformative algorithms (functionalities spanning multiple network layers and their interactions) that are optimized for communications requiring delay guarantees; and (iii) distributed and low-complexity implementations. The success of this project will lead to transformative theories and algorithms for delay constrained applications such as multimedia communications in cellular networks, emergency response inwirelessmesh networks, and sensor networks for medical care