Switching Fabrics
	Switching Fabrics
		Click here for subtitle 
		CSE 222: Communication Networks
		
		George C. Polyzos
		
		Department of Computer Science and Engineering
		University of California, San Diego
	Switches
		scope
			small, organization, local (LAN) switches
				bus (TDM) based (?)
			carrier switches
				large, reliable
				multiple parallel (independent?) paths
		functionality: the canonical switch
			VPI/VCI lookup
	Switches (cont.)
		requirements
			low loss rate
			no reordering within a VC
		issues
			finite, little(?) buffering
			blocking
				internal contention while output available
			multicast and broadcast
	Buffering Strategies
		no buffering
		input buffering
		output buffering
		internal buffering
	Output vs. Input Buffering 
		increased throughput
		HoL blocking
		intuitive arguments
		probabilistic analysis
			output buffering (N --> infinity)
				superposition of N Bernoulli processes
					Poisson (as N --> infinity)
				discrete time M/D/1 queue
			input buffering
				capacity = 0.586 = 2 - sqrt(2)
	Crossbar Switches
		non-blocking
		easy multicast
		output queueing
		expensive: O(n^2)
	Knockout Switch
		time slotted, crossbar switch
		concentrator (for each output)
			L out of up to N cells accepted per cycle
			fair discarding of cells
			L parallel queues and a circular shifter
		homogeneous, uncorrelated traffic
			L = 8 (N = infinity)
				40 buffers sufficient for
					 loss rate < 10^(-6)
					 for up to 84% of capacity
			not so realistic assumption
	Banyan Switches
		routing stage of Batcher-Banyan
		simple (binary?) switches at each stage
		self-routing
		synchronous (efficiency)
		blocking
		O(n (log n)^2)
	Batcher Sorting Networks
		O(n (log n)^2) sorting network [Batcher68]
		bitonic sort
		Batcher-Banyan non-blocking switches
	Starlite
		concentrator
			m out of n input cells
		Batcher sorting network
		trap
			eliminate multiple cells to the same output
			recirculator lines
		expander
			adjusts cell positions to not block
		Banyan switch
	Starlite (cont.)
		recirculator minimizes cell loss
			avoid cell re-ordering
			priorities
		multicast
			copy network at the input
		Starlite: essentially input buffering
	Sunshine
		improving on Starlite
		k Banyan networks in parallel
		each output port can accept up to
		k cells per cycle
		closer to output buffering