Systems Design Seminar
Randomized Parallel Schedulers for Switch-Memory-Switch Routers
Output queued routers are appealing because they have better latency
and throughput than input queued routers. However, they are difficult
to build: a direct implementation of an N-input, N-output
output-queued router requires the switching fabric and the packet
memories at the outputs to run at N times the line rate. Attempts
have been made to implement output queuing with slow components,
however, in these approaches, even though the packet memory speed is
reduced, the scheduler time complexity is high---at least Omega(N).
We show that a router based on the Switch-Memory-Switch (SMS) architecture---essentially, a partitioned shared memory architecture consisting of an ensemble of memory banks operating at the line rate---could emulate an output-queued switch. Specifically we develop several efficient scheduling algorithms for SMS architecture based on computing perfect matchings in bipartite graphs.
In addition to being able to emulate an output-queued router, the SMS architecture also has the advantage that, if appropriately scheduled, it has a lower drop rate than an output-queued router with the same amount of packet memory, since it can ``pool'' available memory.
In this talk I will present RiPSS, a simple algorithm that requires O(log^* N) rounds of communication to compute a schedule, and PRiPSS, a pipelined version of RiPSS that requires only O(1) rounds of communication per cycle. In addition to asymptotic analysis I will present numerical analysis of these algorithms to show that hidden constants are small. I will conclude the talk with a set of theorems that show that a the amount of memories we use in this architecture is near optimum.
Amit Prakash is a doctoral candidate at the Department of Electrical and Computer Engineering at the University of Texas at Austin. He works with Prof Adnan Aziz on algorithmic aspects of high performance networking hardware. His research interests include Switching systems, Computer Networks, System Architecture, VLSI-CAD, and Algorithm Design.