Optimal Heavy-Traffic Queue Length Scaling in an Incompletely Saturated Switch

Abstract

We consider an input queued switch operating under the MaxWeight scheduling algorithm. This system is interesting to study because it is a model for Internet routers and data center networks. Recently, it was shown that theMaxWeight algorithm has optimal heavy-traffic queue length scaling when all ports are uniformly saturated. Here we consider the case where a fraction of the ports are saturated and others are not (which we call the incompletely saturated case), and also the case where the rates at which the ports are saturated can be different. We use a recently developed drift technique to show that the heavy-traffic queue length under the MaxWeight scheduling algorithm has optimal scaling with respect to the switch size even in these cases.