. Shanghai Jiao Tong University M/G/1 QUEUE Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks M/G/1 QUEUE Shanghai Jiao Tong University
M/G/1 queue The M/G/1 queue General service time distribution -i.i.d(identical independent distribution) Service time is independent from arrival -X=1/u,average service time -x2:Second moment of service time, Poisson Arrival rateλ：Markovian Poisson arrivals M/G/1 General independent service times Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks M/G/1 queue 2 The M/G/1 queue General service time distribution - i.i.d (identical independent distribution) - Service time is independent from arrival - = 1/μ, average service time - : Second moment of service time, <∞ X 2 X Poisson Arrival rate λ: Markovian M/G/1 Poisson arrivals General independent service times
Pollaczek-Khinchin (P-K)formula W:Average waiting time in queue AX2 W ,p=2= 21-p) Applying Little's Theorem N。=2W Number of customers in queue T=W+X Average system time:queueing delay service time Again Little's Theorem,we get the number of customers in system N=T=W+p=N。+P Weigiang Sun Communication Networks 3
Weiqiang Sun Communication Networks Pollaczek-Khinchin (P-K) formula Applying Little’s Theorem 3 2 2(1 ) X W X , N W Q T W X Number of customers in queue W: Average waiting time in queue Average system time: queueing delay + service time Again Little’s Theorem, we get the number of customers in system N T W N Q
M/G/1 examples Example 1:M/M/1 x=1X=2 2 0 W u21-p) (1-p) Example 2:M/D/1 X=1:X-I Deterministic service time:1/u 2 W- 2u2(1-p)2u(1-p) Waiting time of M/D/1 is half of M/M/1,in fact the results of M/G/1 is a lower bound for all M/G/1 with same A and u Weigiang Sun Communication Networks 4
Weiqiang Sun Communication Networks M/G/1 examples • Example 1: M/M/1 4 • Example 2: M/D/1 2 2 1 2 X X ; 2 (1 ) (1 ) W Deterministic service time: 1/μ 2 2 1 1 X X ; 2 2 (1 ) 2 (1 ) W • Waiting time of M/D/1 is half of M/M/1, in fact the results of M/G/1 is a lower bound for all M/G/1 with same λ and μ
Proof of P-K formula Suppose customer i arrives to the system and finds N,customers waiting in queue Up to one customer receiving service And also define: -R,:the residual service time seen by i -W,:the waiting time in queue of customer i X Customer i arrives Xi-1 Xi-2 X3X.4 N,=3 Weigiang Sun Communication Networks 5
Weiqiang Sun Communication Networks Proof of P-K formula • Suppose customer i arrives to the system and finds – Ni customers waiting in queue – Up to one customer receiving service • And also define: – Ri : the residual service time seen by i – Wi : the waiting time in queue of customer i 5 Customer i arrives Xi-1 Xi-2 Xi-3 Xi Xi-4 Ni =3
Proof of P-K formula(Cont. Customer i starts to receive service Customer i arrives W X Xi-1 Xi-2 Xi-3 Xi-4 W=R+∑X, R N,3 EW,]=E[R]+E[X]E[N,]=R+X·N。 W=R+X·No By Little's Theorem,No =2.W W=R/-p).P=-X Weigiang Sun Communication Networks 6
Weiqiang Sun Communication Networks Proof of P-K formula (Cont.) 6 Xi Xi-1 Xi-2 Xi-3 Xi-4 Customer i starts to receive service Customer i arrives Wi Ri Ni =3 1 i i i i j W R X j i N [ ] [ ] [ ] [ ] E W E R E X E N R X N i i i Q By Little’s Theorem, N W Q W R X N Q W R /(1 ) X ,
R-The average residual service time 1R(t) residual service time X X X2 X Average residual service time is the sum of area of the triangles divided by time t Let M(t)=the number of customers served by time t 0-0*-兰2 一X2 M(t) Ast→0， M(t) is the average departure rate,and is equal to arrival rate A 元X2 Hence,R The P-K formula is then proved. 2 Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks R – The average residual service time • Average residual service time is the sum of area of the triangles divided by time t 7 R(t) residual service time t Let M(t) = the number of customers served by time t X1 X1 X2 X3 X4 X2 X3 X4 2 ( ) 0 1 1 1 ( ) ( ) 2 t M t i i X R t R d t t ( ) 2 1 ( ) 2 ( ) M t i i M t X t M t As ( ) , M t t t is the average departure rate, and is equal to arrival rate λ Hence, 2 X 2 2 Xi R The P-K formula is then proved
R in M/M/1 For M/M/1,we already know that ·So,R for M/M/1is: x=X=2 2 R= 2 Why it is not equal to 1/u,given the PASTA property? R(t) residual service time X3 t X2 Weigiang Sun Communication Networks 8
Weiqiang Sun Communication Networks R in M/M/1 • For M/M/1, we already know that 8 2 2 1 2 X X ; • So, R for M/M/1 is: 2 2 1 2 Xi R • Why it is not equal to 1/μ, given the PASTA property? R(t) residual service time t X1 X1 X2 X3 X4 X2 X3 X4
M/G/1 with vacations Once the system is empty,the server takes a vacation If system is still empty after the vacation,the server takes another vacation Useful in analyzing some polling and reservation systems Vacation times are i.i.d and independent of service times and arrival times The only impact on analysis is that a customer may enter to find the server on vacation,and must wait until end of that vacation Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks M/G/1 with vacations • Once the system is empty, the server takes a vacation – If system is still empty after the vacation, the server takes another vacation – Useful in analyzing some polling and reservation systems • Vacation times are i.i.d and independent of service times and arrival times • The only impact on analysis is that a customer may enter to find the server on vacation, and must wait until end of that vacation 9
R(t)with vacations R(t) residual service time X X X V V2 X3 V A customer will always experience some residual time,either because server is on vacation,or is serving a customer Let M(t)=the number of customers served by time t L(t)=the number of vacations taken by time t 0-Σ兰+) Weigiang Sun Communication Networks 10
Weiqiang Sun Communication Networks R(t) with vacations • A customer will always experience some residual time, either because server is on vacation, or is serving a customer 10 R(t) residual service time t X1 X1 X2 X3 X4 X2 X3 X4 V1 V2 V3 Let M(t) = the number of customers served by time t L(t) = the number of vacations taken by time t 2 2 ( ) ( ) 1 1 1 ( ) 2 2 M t L t i i i i X V R t t