Routers with Input Queueing, Crossbars and QoS
   Shang-Tse Chuang, Ashish Goel, Nick McKeown and Balaji Prabhakar
			 Stanford University

    The Internet is facing two problems simultaneously: we need a
faster switching/routing infrastructure, and we need to introduce QoS.
    As a community, we have solutions to each: we can make the routers
faster by using input-queued crossbars, instead of shared memory
systems; and we can introduce QoS using WFQ-based packet
scheduling. But we don't know how to do both at the same time.  Until
now, the two solutions have been mutually exclusive --- all of the
work on WFQ-based scheduling algorithms has required that
switches/routers used output-queueing, or centralized shared memory.
    We demonstrate that an input-queued crossbar switch running only
twice as fast as the line rate (in fact, 2-1/n, where n is the number
of ports) can provide precise emulation of a class of packet
scheduling algorithms, including WFQ and strict priorities.  We prove
that this "speedup" of two is both necessary and sufficient, and have
a variety of algorithms to implement it.  We believe that, in the
future, this will make possible the support of QoS in very high
bandwidth routers.