Routers
with a Single Stage of Buffering. Sundar Iyer, Rui Zhang, Nick McKeown (Stanford)
Most high performance routers today use combined input and output queueing
(CIOQ). The CIOQ router is also frequently used as an abstract model
for routers: at one extreme is input queueing, at the other extreme
is output queueing, and in-between there is a continuum of performance
as the speedup is increased from 1 to N (where N is the number of linecards).
The model includes architectures in which a switch fabric is sandwiched
between two stages of buffering. There is a rich and growing theory
for CIOQ routers, including algorithms, throughput results and conditions
under which delays can be guaranteed. But there is a broad class of
architectures that are not captured by the CIOQ model, including routers
with centralized shared memory, and load-balanced routers. In this paper
we propose an abstract model called Single-Buffered (SB) routers that
includes these architectures. We describe a method called Constraint
Sets to analyze a number of SB router architectures. The model helped
identify previously unstudied architectures, in particular the Distributed
Shared Memory router. Although commercially deployed, its performance
is not widely known. We find conditions under which it can emulate an
ideal shared memory router, and believe it to be a promising architecture.
Questions remain about its complexity, but we find that the memory bandwidth,
and potentially the power consumption of the router is lower than for
a CIOQ router.
Papers are provided as
a service to all by the members of ACM SIGCOMM.
This
paper is available in Adobe PDF format.
|