Heavy-Traffic Behavior of the MaxWeight Algorithm in a Switch with Uniform Traffic

Friday, June 26, 2015 - 1:15pm - 2:15pm
Keller 3-180
Rayadurgam Srikant (University of Illinois at Urbana-Champaign)
We consider a switch with uniform traffic operating under the MaxWeight scheduling algorithm. This traffic pattern is interesting to study in the heavy-traffic regime since the queue lengths exhibit a multi-dimensional state-space collapse. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state. Specifically, in the case of Bernoulli arrivals, we show that the heavy-traffic scaled queue length is n−3/2+1/2n. Our result implies that the MaxWeight algorithm has optimal queue-length scaling behavior in the heavy-traffic regime with respect to the size of a switch with a uniform traffic pattern. This settles the heavy-traffic version of an open conjecture. Joint work with Siva Theja Maguluri.
MSC Code: