DIMACS Special Year on Networks Seminar


Dynamic Packet Scheduling in Wireless Networks


Nabil Kahale
AT&T Labs - Research


AT&T, Murray Hill Building, room 2D-101
Note: Visitors not from the MH building should use the east side entrance "stairway 9", and call Carsten Lund, phone number 2398, to let them in. Since entering the MH building takes time, visitors are requested to arrive no later than 1:45pm.
AT&T Host: Carsten Lund


2:00 p.m
Friday, March 7, 1997

We consider the problem of packet access in wireless data networks. The maximum ergodic packet arrival rate is shown to be NP-hard. We give a spectral bound on the maximum ergodic throughput in terms of the path-gain matrix. We present simple heuristic packet access schemes that exhibit good behavior on preliminary simulations. We also give more sophisticated algorithms that yield optimal throughput. Our algorithms generalize to other scheduling problems under stochastic arrivals. In particular, we obtain a recent result of McKeown, Anantharam and Walrand on scheduling of input-queued switches as a byproduct.

[Based on joint work with Paul Wright]

Document last modified on February 28, 1997