Scheduling high speed data in (adversarial) wireless networks

Monday, June 27, 2005 - 3:15pm - 4:15pm
EE/CS 3-180
Matthew Andrews (Alcatel-Lucent Technologies Bell Laboratories)
Wireless networks for transmitting high speed data are becoming increasingly common. Such networks lead to new and interesting scheduling problems, in large part because the quality of a wireless channel constantly changes over time. It is important to schedule in an opportunistic fashion, i.e. we want to transmit data between two users during the times when the associated wireless channel has good quality.

A number of models have been proposed for studying such systems. These differ according to the assumptions made on the arrival process, the assumptions made on the channel conditions, and the metrics that are to be optimized. In this talk we shall survey some of these models and present contrasting scheduling results that arise in each model. We shall concentrate on the case in which the channel conditions are governed by an adversary and present limits on the optimum fairness and quality-of-service that can be achieved in the resulting adversarial environment.