|
|
Randomized Parallel Schedulers for Switch-Memory-Switch Routers
Amit Prakash
Electrical
and Computer Engineering
University of Texas at Austin
Monday,
November 10th,
2003, 4pm - 5pm
540A/B Cory Hall (D.O.P. Center Classroom)
|
Abstract
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.
Speaker
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.
|
