We consider a switched (queuing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result of this paper, we provide a new class of online scheduling policies that achieve optimal queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture (documented in Shah, Tsitsiklis and Zhong [Queueing Syst. 68 (2011) 375-384]) about optimal queue-size scaling for input-queued switches.
In the context of input-queued switches, the example that has primarily motivated this work, the policy that we propose has the average total queue size bounded within factor @math of the same quantity induced by policy, in the heavy-traffic limit. Furthermore, this result does not require conditions like complete resource pooling. More generally, our policy provides non-asymptotic bounds on queue sizes for every arrival rate and switch size. The policy even admits exponential tail bounds with respect to the stationary distribution; and the exponent of these tail bounds is . These results are significant improvements on the state-of-the-art bounds for best performing policies for input-queued switches. As noted in the introduction, our bound on the average total queue size is @math times better than the existing bound for the maximum-weight policy, and @math times better than that for the batching policy in @cite_17 . (Here @math is the number of queues, and @math the system load.) For more details of these results, see @cite_2 .
@cite_2 @cite_17
2065649422 2136380306
We review some known results and state a few versions of an open problem related to the scaling of the total queue size (in steady state) in an n×n input-queued switch, as a function of the port number n and the load factor ?. Loosely speaking, the question is whether the total number of packets in queue, under either the maximum weight policy or under an optimal policy, scales (ignoring any logarithmic factors) as O(n (1??)). We consider the fundamental delay bounds for scheduling packets In an N times N packet switch operating under the crossbar constraint. Algorithms that make scheduling decisions without considering queue backlog are shown to incur an average delay of at least O(N). We then prove that O(log(N)) delay is achievable with a simple frame based algorithm that uses queue backlog information. This is the best known delay bound for packet switches, and is the first analytical proof that sublinear delay is achievable in a packet switch with random inputs.