Queueing Theory (CSE 123A version, 96/1/20)
	Elementary Queueing Theory
		definitions
		M/M/1
		Little's law
		M/M/...
		M/G/1
		queueing networks
		applications
	Queueing Systems
		elements
			server(s)
			queue
			customers
				arrivals
				departures
		system specification
			inter-arrival time
			service time
			number of servers
			size of waiting room
			customer population
			service discipline
	Standard Notation
		inter-arrival and service time
			M: Exponential (Markovian, ~ Poisson)
			D: Deterministic
			G: General (GI: General Independent, for arrivals)
			GI: General Independent (for arrivals)
		number of servers: 1, m, „ (inf)
		size of waiting room: „ (inf), 0, m
		customer population: „ (inf), K
		service discipline
			First Come First Serve (FCFS) = First In First Out (FIFO)
			Last Come First Serve (LCFS) = Last In First Out (LIFO)
			Random
			Preemptive resume
	Examples of the Standard Notation
		M/M/1/„/„/FCFS = M/M/1 (the default, convenient model)
		M/D/1 (constant size ... packets)
		M/G/1 (... doable)
		G/M/1
		GI/G/1 (the ultimate single server queue)
		M/M/m/m (blocked calls cleared)
	Timing Diagram
		xn: service time
		wn: waiting time
		sn: system time
		tn: interarrival time
		interdeparture time
	M/M/1: The Classical Queueing System
		Poisson arrivals Ū exponential interarrival times
			rate: l (customers/unit of time)
			mean time between arrivals = 1/l
		Exponential service times
			rate: m (customers/unit of time)
			mean service time = 1/m
		1 server, infinite waiting room (and population), FCFS
		system state: number of customers in the system
		(server + queue)
			memoryless distributions
		state-transition-rate diagram
	M/M/1 Analysis
		pk = prob. system in state k
		balance equations
			global balance
				transient equations
					dpk(t)/dt = -(l+m) pk(t) + l pk-1(t) + m pk+1(t),  k=1,2,...
					dp0(t)/dt = - l p0(t) + m p1(t)
				equilibrium solution
					limt®„ { dpk(t)/ dt } = 0
					(l+m) pk = l pk-1 + m pk+1,  k=1,2,...
					l p0 = m p1
	M/M/1 Analysis (cont.)
		local balance (in equilibrium)
			l pk = m pk+1 ,  k=0,1,2,...
		"conservation" of probability
			Sk=0„ pk = 1
		solve (infinite) system of equations to get pk, k=0,1,2,...
	Queue Size Distribution, Utilization
		r = l / m
		solution (queue size distribution)
			pk = rk (1-r), k=0,1,2,...
			p0 = (1-r)  (prob. empty system)
			1 - p0 = r : prob. system not empty = utilization
		mean queue size
			N = Sk=0„ k pk  = r / (1-r)
	Little's Theorem
		N = l T
			N : number of customers in the system
			l : arrival rate
			T : mean time of customers in the system
		very general result
			holds for almost any queueing system in steady-state
	M/M/1 Revisited
		mean system time: T
			N = l T Ž T = N / l = [ r / (1-r) ] / l = ...
			T = 1 / (m-l)
		mean wating time: W
			W = T - 1 / m
		mean number of customers in the queue (not server): NQ
			NQ = l W = l [1 / (m-l) - 1 / m ] = r2 / (1-r)
	Queueing Networks
		networks of M/M/1 queues
		queues can be analyzed independently if
			customers after service completion in any queue join any queue randomly, with given prob.
			service time of customers in each queue is independent from any other system metric (random variable)
			Kleinrock's independence assumption
	Applications
		Time-Sharing System
			closed queueing networks
			bounds
				throughput
				response time
			Mean Value Analysis
		Statistical Multiplexing vs. FDM or TDM
			n independent Poisson streams of packets at rate l/n each
				exponential packet size with mean 1/m
			FDM (and TDM, approximately)
				n independent channels with capacity C/n each
				each stream/channel has mean delay
					TFDM = 1 / [ mC/n - l/n ] = n / [ mC - l ] 
			Statistical Multiplexing
				1 channel at rate C
				superposition of n Poisson streams at rate l/n each = Poisson stream at rate l
				mean delay for any packet (belonging to any stream)
					T = 1 / [ mC - l ]
			T = TFDM / n