Iterative Scheduling Algorithms

The input-queued switch architecture is widely used in Internet routers due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is the scheduling algorithm that decides which packets to transfer from ingress ports to egress ports in a given timeslot. It is desirable that such algorithms be iterative (so as to be pipelineable), distributed (allowing flexibility in hardware implementation) and are able to deliver high performance (in terms of throughput and delay). In practice, implementable algorithms have so far had limited success in combining all of the above properties. For example, the popular iSLIP algorithm is known to perform suboptimally, but it is commercially deployed mainly because it is iterative and distributed. The main contribution of this paper is the design and systematic analysis of two algorithms which, to the best of our knowledge, are the first high-performance iterative and distributed scheduling algorithms with possibility of efficient implementation. We first present an iterative, distributed and low-delay maximal throughput algorithm based on the celebrated "auction algorithm". This algorithm can be seen as a natural extension of iSLIP when queue-size information is allowed to be exchanged. The standard auction algorithm can take an unbounded number of iterations to converge in the worst case. However we show that under admissible Bernoulli i.i.d. traffic, our algorithm takes O(n 2 ) iterations, where n is the number of ingress/egress ports in the switch. Moreover for a switch with finite buffer-size, the algorithm allows for a graceful trade-off between running time and performance, which we verify by representative simulation results. Next, we propose and analyze a throughput-optimal, iterative and distributed scheduling algorithm influenced by Max-product belief propagation. Recently the problem of efficient transmission over multi-hop wireless networks has been formulated as that of finding an appropriate schedule over the grid-graph abstraction of the network. A key feature of the multi-hop wireless transmission problem is that while the communication subgraph is bipartite, the bi-partition is allowed to change in each scheduling epoch. We show that our algorithm can be used to efficiently schedule traffic in multi-hop wireless networks.