BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-98-758
       ENTRY:: February 26, 1999 
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: Matching Output Queueing with a Combined Input Output Queued Switch
	TYPE:: Technical Report
      AUTHOR:: Chuang, Shang-Tse
      AUTHOR:: Goel, Ashish
      AUTHOR:: McKeown, Nick
      AUTHOR:: Prabhakar, Balaji
	DATE:: April 1998
       PAGES:: 25
    ABSTRACT:: The Internet is facing two problems simultaneously: we need a faster
		switching/routing infrastructure, and we need to introduce guaranteed 
		qualities of service (QoS).  As a community, we have solutions to each: we
		can make the routers faster by using input-queued crossbard, 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 use output-queueing,
		or centralized shared memory.  We demonstrate that a Combined Input Output
		Queueing (CIOQ) switch running twice as fast as an input-queued switch can
		provide precise emulation of a broad class of packet scheduling algorithms,
		including WFQ and strict priorities.  More precisely, we show that a "speedup"
		of 2 - 1/N is both necessary and sufficient for this precise emulation.  We 
		introduce a variety of algorithms that configure the crossbar so that 
		emulation is achieved with a speedup of two, and consider their running
	 	time and implementation complexity.  We believe that, in the future, these
		results will make possible the support of QoS in very high bandwidth routers. 
NOTES:: [Adminitrivia V1/Prg/19980121]
         END:: STAN//CSL-TR-98-758