Pathwise Optimality and State Space Collapse for the Exponential Rule

We consider the problem of scheduling transmissions of multiple data users (flows) sharing the same wireless channel (server). 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. We study a scheduling rule, which we call the exponential rule. Given a system with N users, and any positive numbers {a sub i},i=1,2,...,N, we show that in a heavy-traffic limit, this algorithm has the property that, for each time t, it minimizes the maximum scaled queue-lengths (max sub i a sub i Q sub i(t)).