Lower bound and optimality in switched networks

We consider a queueing network in which there are constraints on which queues may be served simultaneously. Such networks, called ldquoswitched networksrdquo [3] can be used to model input-queued switches, wireless networks, or bandwidth sharing in the Internet. The scheduling algorithm for such a network specifies which queues to serve at any point in time. The performance of scheduling algorithm is determined by the induced net queue-size. The question of designing optimal scheduling algorithm with this performance metric has been of great recent interest (e.g. [1, 3, 4]). An important step in this quest is that of finding fundamental limitations of scheduling algorithms in terms of the induced queuesize. In this paper, we present a novel technique to characterize lower bound on average queue-size induced by any algorithm. Through an example, we establish the tightness of this technique for a class of problems.