CDA6530: Performance Models of Computers and Networks Chapter

CDA6530: Performance Models of Computers and Networks Chapter 6: Elementary Queuing Theory

Definition Queuing system: a buffer (waiting room), service facility (one or more servers) a scheduling policy (first come first serve, etc.) We are interested in what happens when a stream of customers (jobs) arrive to such a system throughput, sojourn (response) time, Service time waiting time number in system, server utilization, etc. 2

Terminology A/B/c/K queue A - arrival process, interarrival time distr. B - service time distribution c - no. of servers K - capacity of buffer Does not specify scheduling policy 3

Standard Values for A and B M - exponential distribution (M is for Markovian) D - deterministic (constant) GI; G - general distribution M/M/1: most simple queue M/D/1: expo. arrival, constant service time M/G/1: expo. arrival, general distr. service time 4

Some Notations Cn: custmer n, n 1,2, an: arrival time of Cn dn: departure time of Cn (t): no. of arrivals by time t (t): no. of departure by time t N(t): no. in system by time t N(t) (t)- (t) 5

(t) (t) Average arrival rate (from t 0 to now): t (t)/t 6

Little’s Law (t): total time spent by all customers in system during interval (0, t) Tt: average time spent in system during (0, t) by customers arriving in (0, t) Tt (t)/ (t) Nt: average no. of customers in system during (0, t) For a stable system, Nt t Tt Nt (t)/t Remmeber t (t)/t For a long time and stable system N T Regardless of distributions or scheduling policy 7

Utilization Law for Single Server Queue X: service time, mean T E[X] Y: server state, Y 1 busy, Y 0 idle ½: server utilization, ½ P(Y 1) Little’s Law: N E[X] While: N P(Y 1) 1 P(Y 0) 0 ½ Thus Utilization Law: ½ E[X] Q: What if the system includes the queue? 8

Internet Queuing Delay Introduction How many packets in the queue? How long a packet takes to go through? 9

The M/M/1 Queue An M/M/1 queue has Poisson arrivals (with rate λ) Exponential time between arrivals Exponential service times (with mean 1/μ, so μ is the “service rate”). One (1) server An infinite length buffer The M/M/1 queue is the most basic and important queuing model for network analysis 10

State Analysis of M/M/1 Queue N : number of customers in the system (including queue server) Steady state ¼n defined as ¼n P(N n) / : Traffic rate (traffic intensity) State transition diagram 11

we can use ¼Q 0 and ¼i 1 We can also use balance equation 12

State Analysis of M/M/1 Queue # of transitions # of transitions ¼n are probabilities: : prob. the server is working (why is called “server utilization”) 13

State Analysis of M/M/1 Queue N: avg. # of customers in the system 100 Packets in Queue 80 60 40 20 0 0 0.2 0.4 14 0.6 0.8 1

M/M/1 Waiting Time Xn: service time of n-th customer, Xn st X where X is exponential rv Wn: waiting time of n-th customer Not including the customer’s service time Tn: sojourned time Tn Wn Xn When ½ 1, steady state solution exists and Xn, Wn, Tn X, W, T Q: E[W]? 15

State Analysis of M/M/1 Queue W: waiting time for a new arrival : service time of i-th customer : remaining service time of the customer in service Exponential r.v. with mean 1/ due to memoryless property of expo. Distr. T: sojourn (response) time 16

Alternative Way for Sojourn Time Calculation We know that E[N] ½/(1-½) We know arrival rate Then based on Little’s Law N T E[T] E[N]/ 1/(¹- ) 17

M/M/1 Queue Example A router’s outgoing bandwidth is 100 kbps Arrival packet’s number of bits has expo. distr. with mean number of 1 kbits Poisson arrival process: 80 packets/sec How many packets in router expected by a new arrival? What is the expected waiting time for a new arrival? What is the expected access delay (response time)? What is the prob. that the server is idle? What is P( N 5 )? Suppose you can increase router bandwidth, what is the minimum bandwidth to support avg. access delay of 20ms? 18

Sojourn Time Distribution T’s pdf is denoted as fT(t), t 0 T X1 X2 Xn X Given there are N n customers in the system Then, T is sum of n 1 exponential distr. T is (n 1)-order Erlang distr. When conditioned on n, the pdf of T (n 1 order Erlang) is denoted as fT N(t n) ¹ (¹ t) ne¡ ¹ t f T jN (tjn) n! 19

Sojourn Time Distribution Remove condition N n: Remember P(N n) ¼n (1-½)½n f T (t) f T j0(tj0)¼0 f T j1(tj1)¼1 X1 n e¡ ¹ t ¹ (¹ t) f T (t) ( 1 ¡ ½)½n n! n 0 (1 ¡ ½)¹ e¡ ¹ t X1 (½¹ t) n n! n 0 ¡ ¹ t t (¹ ¡ )e e (¹ ¡ )e¡ (¹ ¡ )t Thus, T is exponential distr. with rate (¹- ) 20

M/M/1/K Queue Arrival: Poisson process with rate Service: exponential distr. with rate ¹ Finite capacity of K customers Customer arrives when queue is full is rejected Model as B-D process N(t): no. of customers at time t State transition diagram 21

Calculation of ¼0 Balance equation: ¼i ½¼i-1 ½i¼0, i 1, , K If ¹: XK i 0 XK 1 ¡ ½K 1 ¼i ¼0 ½ ¼0 1¡ ½ i 0 i 0 ¼i 1 ) If ¹: XK XK i 0 i 1¡ ½ ¼0 1 ¡ ½K 1 ¼i ¼0 XK i 0 ½i (K 1)¼0 ¼i 1 (K 1); i 0; ; K 22

E[N] If ¹: E [N ] XK i 0 If ¹: i¼i 1 ¡ ½ XK i i ½ 1 ¡ ½K 1 i 0 E [N ] XK i 0 i¼i XK 1 i K 1 i 0 1 K (K 1) K K 1 2 2 23

Throughput Throughput? When not idle ¹ When idle 0 Throughput (1-¼0)¹ ¼0 0 When not full When full (arrive pass) 0 (arrive drop) Prob. Buffer overflow ¼K Throughput (1-¼K) ¼K 0 24

Sojourn Time One way: T X1 X2 Xn if there are n customers in (n·K) Doable, but complicated Another way: Little’s Law N T The means actual throughput E [N ] E [N ] E [T ] throughput (1 ¡ ¼0)¹ 25

M/M/c Queue c identical servers to provide service Model as B-D process, N(t): no.of customers State transition diagram: Balance 8 equation: ¼ i¡ 1 : ¼ i¡ 1 i¹ ¼i ; i · c; c¹ ¼i ; i c 26

Solution to balance equation: 8 i ½¼ ; 0 i! ¼i : ½i ¼ ; c!ci¡ c 0 0 · i · c; c i Prob. a customer has to wait (prob. of queuing) P (queuing) P (wait) 27 X1 n c ¼n

M/M/1 Queue Infinite server (delay server) Each user gets its own server for service No waiting time Balance equation: ¼i¡ 1 i¹ ¼i ; i 0; 1; i ½i ½ ¼i ¼0 e¡ ½ why? i! i! 28

X1 X1 i½i e¡ ½ E [N ] i¼i i! i 0 i 1 i¡ 1 X1 ½ ¡ ½ ½e i 1 (i ¡ 1)! E [N ] 1 E [T ] ¹ 29 ½ W hy?

PASTA property PASTA: Poisson Arrivals See Time Average Meaning: When a customer arrives, it finds the same situation in the queueing system as an outside observer looking at the system at an arbitrary point in time. N(t): system state at time t Poisson arrival process with rate M(t): system at time t given that an arrival occurs in the next moment in (t, t t) 30

P (M (t) n) P (N (t) njarrival in(t; t t)) P (N (t) n; arrival in (t; t t)) P (arrival in (t; t t)) P (N (t) n)P (arrival in (t; t t)) P (arrival in (t; t t) ) P (N (t) n) If not Poisson arrival, then not correct 31