. 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