Systems Seminar - CSE

Scheduling High Speed Wireless Data in an Adversarial Environment

Dr Lisa Zhang

Anyone wishing to meet with Dr Zhang please contact Kirsten Knecht at
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 aim to transmit between two users
during the times when the associated wireless channel has good

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 I will compare some of these models
and present recent scheduling results that arise in the adversarial
queueing model (AQM). AQM focuses on the worst-case behavior and
assumes an adversary that controls both the arrival process and the
channel conditions.

Lisa Zhang received her PhD in Theory of Computing from MIT in
1997. Since then she has been a member of the Computing Sciences
Research Center at Bell Labs. Her research area is algorithm design
and analysis. She is particularly interested in network optimization
and protocol design. In 2001 she won the Bell Labs Gold Award for
technical excellency. Since 2000 she has been serving on the DIMACS
award committee. Right now she is editing a special issue on network
design for the journal Algorithmica. She is also organizing an IMA
workshop on wireless communications.

Sponsored by