Heavy-traffic - Introduction to Queueing Networks

Advanced Stochastic Processes. LECTURE 24 G/G/1 in heavy­traffic. Introduction to queueing networks Lecture outline • G/G/1 in heavy­traffic (continued) • Introduction to queueing networks. Generalized Jackson Network 24.1. G/G/1 queueing system in heavy­traffic. Generalized Jackson Network We begin by proving Theorem 23.3. Proof of Theorem 23.3. We have almost completed the proof when we did the analysis for the case ρ < 1 is a constant. Now we have ρn = 1 − √θn as well as interarrival times are rescaled n n n n n n by the same factor ρ−1 n . We recall Z (t) = V (Q (0) + A (t)) − B (t) = X (t) + I (t), where as usual X n (t) = V (Qn (0) + An (t)) − t and I n (t) = t − B n (t) (recall that service times are uneffected by n). As before we consider time nt instead of t and write V (Qn (0) + An (nt)) − µ−1 (Qn (0) + An (nt)) X n (nt) √ √ = n n n n Q (0) + A (nt) − λn nt √ + µ−1 n n ρ nt − nt √ + n 1 2 Now we have An (nt) = ρn A(nt), implying by FSLLN that An (nt)/n → λt, since limn ρn = 1. Also Qn (0)/n → 0. Therefore V (Q(0) + An (nt)) − µ−1 (Qn (0) + An (nt)) √ n V (Qn (0) + An (nt)) − µ−1 (Qn (0) + An (nt)) � = Qn (0) + An (nt) � Qn (0) + An (nt) n 1 ⇒ λ 2 µ−1 cs W1 (t) 1 = λ− 2 cs W1 (t) where W1 is a standard Brownian motion, where we again use Donsker’s Theorem for V . Using FCLT for counting process A(t) we obtain µ−1 Qn (0) + An (nt) − λn nt Qn (0) + ρn (A(nt) − λnt) √ √ = µ−1 n n 1 ⇒ qµ−1 + µ−1 λ 2 ca W2 (t) 1 = qµ−1 + λ− 2 ca W2 (t) where W2 is a standard Brownian motion independent from W1 . Finally ρn nt − nt √ = −θt. n √ Putting all this together, we conclude that X n (nt)/ n converges weakly to a Brownian motion W with W (0) = q/µ, drift −θ and variance λ−1 (c2a +cs2 ). Also X n (nt), I n (nt), Z n (nt) solve jointly the Skorohod mapping problem. Moreover, recall that the mappings Ψ(X n ) = I n , Φ(X n ) = Z n are (Lipshitz) continuous mappings on D[0, T ]. Using Mapping Theorem (Theorem 20.1 from Lecture 20), we conclude that Z n ⇒ RBM which starts from q/µ, has drift −θ and variance λ−1 (c2a + cs2 ), and I n (t) ⇒ sup0≤s≤t (−W (s))+ , where W is a Brownian motion with the same drift, variance and starting value. This concludes the derivation for the workload process Z. The derivation for the queue length process is similar and involves ”inverting” the process V . We skip these technical, but not insightful details. � 24.2. Generalized Jackson Network. Model description A G/G/1 queueing system we considered thus far is limited in its modeling power. We now extend this model to a network case – Generalized Jackson Network (GJN). This is a queueing network consisting of J single servers. Each server j = 1, 2, . . . , J process jobs with i.i.d. service time vnj , n ≥ 1, with service rate µj = 1/E[v1j ]. There are J external arrival processes, each having i.i.d. interarrival times ujn , n ≥ 1. Upon arrivals the jobs enter buffers corresponding to server j and form a queue, but upon service completion the jobs do not necessarily depart from the network but join a another queue corresponding to a different server k. The mechanism for this transitions is as follows. � We fix a J × J matrix P with non­negative entries, such that each row sum is at most unity k pjk ≤ 1. To each server j = 1, 2, . . . , J we associate an i.i.d. sequence j of vectors Rnj , n ≥ 1, where pjk and value � each Rn takes value ek , 1 ≤ k ≤ J with probability j 0 with probability 1 − k pjk . Here ek is the k­th unit vector. The event Rn = ek corresponds LECTURE 24. QUEUEING SYSTEMS 3 to sending the n­job completing service in server j to the queue of server k. The event Rnj = 0 corresponds to this job exiting the network. For each pair j, k we also let Rjk (n) denote the counting process – the number of times that Rnk = ej out of the first n trials. That is the number of jobs which were sent to server j after service completion in k, out of the first n jobs served there. The jobs joining the queue corresponding to each server j are merged together, whether they arrive externally or internally, and they are served using the First­In­First­Out rule. We use the same notations as for G/G/1 queueing system, but now the processes are indexed by j: Aj , Sj , Dj , Bj , Ij , Zj , Qj . The balance equation for the queue length are written as � Qj (t) = Qj (0) + Aj (t) + Rjk (Sk (Bk (t))) − Sj (Bj (t)), 1≤k≤J � Bj (t) = t 1{Qj (s) > 0}ds 0 � Zj (t) = Vj (Qj (0) + Aj (t) + Rjk (Sk (Bk (t)))) − Bj (t) 1≤k≤J = Vj (Qj (t) + Sj (Bj (t))) − Bj (t). 24.3. Additional reading materials • Chapter 6 of Chen & Yao book [1] from the course packet.