Pathwise optimality and state space collapse for the exponential rule

We study the problem of scheduling transmissions of multiple data users sharing the same wireless channel. The unique feature of this problem is the fact that the capacity (service rate) of the channel varies with time randomly and asynchronously for different users. Such a problem arises, for example, in the 3G CDMA high data rate (HDR) system, where multiple mobile users in a cell share the same downlink wireless channel by means of time-sharing. Time is divided into fixed size slots, and in each time slot, one user is scheduled for transmission. Each user constantly reports to the base station its "instantaneous" channel capacity, i.e. the rate at which data can be transmitted if this user is scheduled for transmission. In an HDR system (and in the generic variable channel model as well), a "good" scheduling algorithm should take advantage of channel variations by giving some form of priority to users with instantaneously better channels.