ATM Switch Scheduling

In collaboration with researchers at DEC Systems Research Center, we developed techniques to allow us to build a prototype switch for an arbitrary topology point-to-point network with link speeds of up to one gigabit per second. The switch deals in fixed-length ATM-style cells, which it can process at a rate of 37 million cells per second. It provides high bandwidth and low latency for datagram traffic. In addition, it supports real-time traffic by providing bandwidth reservations with guaranteed latency bounds. The key to the switch's operation is a novel technique called parallel iterative matching, which can quickly identify a set of conflict-free cells for transmission in a time slot. Bandwidth reservations are accommodated in the switch by building a fixed schedule for transporting cells from reserved flows across the switch; we show that we can provide performance guarantees even when the switches and hosts operate with unsynchronized clocks. Parallel iterative matching can fill unused slots with datagram traffic. Finally, we note that parallel iterative matching may not allocate bandwidth fairly among flows of datagram traffic. We present a technique called statistical matching, which can be used to ensure fairness at the switch and to support applications with rapidly changing needs for guaranteed bandwidth. The ideas developed in this work have formed the basis of the next generation of DEC's networking products. More recently, we have examined scheduling algorithms as alternatives to parallel iterative matching, to reduce the hardware complexity of switch scheduling without sacrificing switch throughput.

Selected Publications

N. McKeown and T. Anderson. ``A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches.'' Submitted for publication. Postscript.

T. Anderson, S. Owicki, J. Saxe, and C. Thacker. ``High Speed Switch Scheduling for Local Area Networks.'' ACM Transactions on Computer Systems 11, 4 (November 1993), pp. 319--352 . Selected as Award Paper in Proc. Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS V) (October 1992), pp. 98--110. Also appeared as Digital Equipment Corporation Systems Research Center Technical Report \#99. Postscript.