Fluid Model of a Queueing System (cont.)

Advanced Stochastic Processes. LECTURE 23 Fluid model of a G/G/1 queueing system Lecture outline • Fluid model of G/G/1 queueing system (continued) • G/G/1 in heavy­traffic 23.1. Fluid model of a G/G/1 queueing system We continue from previous lecture and prove Theorem 21.6. Proof. Recall that Z(t) = V (Q(0) + A(t)) − B(t) which we again rewrite as Z(t) = V (Q(0) + A(t)) − t + Y (t) = X(t) + Y (t), where X(t) = V (Q(0) + A(t)) − t. Then, after rescaling, we obtain Z̄ n (t) = Z(nt) X(nt) I(nt) = + n n n ¯ n (t) = X(nt) , I¯n (t) = I(nt) . Then X ¯ n , I¯n , Z¯ n are the solutions to the Skorohod mapping Let X n n ¯ n ∈ D, and does not have downward jumps, dI¯n (t) ≥ problem from Theorem 21.8. Indeed X n n n ¯ ¯ ¯ ¯ n (t) has a very 0, I (0) = 0 and Z (t)dI (t) = 0 as the same holds for Z and I. We claim that X simple limit: Lemma 23.1. The following converges holds almost surely u.o.c. ¯ n (t) → q + (ρ − 1)t. X µ Before we establish this, let us see how this implies the result of the theorem. We use Lemma ¯ n (t) to conclude that I¯n (t) → Ψ( q + (ρ − 1)t) a.s. u.o.c. and 22.4 with θn = θ = 0, xn = X µ 1 q q 2 Z̄ n(t) → + (ρ − 1)t + Ψ( + (ρ − 1)t) also a.s. u.o.c. But µ µ Ψ( � q �+ q + (ρ − 1)t) = sup − − (ρ − 1)s µ µ 0≤s≤t � q �+ = − − (ρ − 1)t , µ implying I¯n (t) → � − �+ q − (ρ − 1)t µ a.s. u.o.c. As for Z̄ n , we obtain �q �+ q q n + (ρ − 1)t Z̄ (t) → + (ρ − 1)t + Ψ( + (ρ − 1)t) = µ µ µ also a.s. u.o.c. (we used a simple identity x + (−x)+ = x+ ). This concludes the derivation (22.7) an (22.8). In order to derive the corresponding limit (22.9) for the queue length process, we recalls � �+ q that Q(t) = Q(0)+A(t)−S(B(t)) = Q(0)+A(t)−S(t−I(t)). Since I(nt)/n → − µ −(ρ−1)t a.s. u.o.c. then � q �+ B(nt)/n → t − − − (ρ − 1)t . µ By direct inspection, we can see that the expression on the right­hand side is simply equal to t for all t ≥ 0 when ρ ≥ 1 and equal to t for t ≤ q/(µ(1 − ρ)) and q/µ + ρt for t ≥ q/(µ(1 − ρ)), when ρ < 1. Using the result of a problem 1 from HW 6, this implies that when ρ ≥ 1, S(nt − I(nt))/n → µt a.s. u.o.c., and S(nt − I(nt))/n → µt for t ≤ q/(µ(1 − ρ)) and S(nt − I(nt))/n → µ(q/µ + ρt) = q + λt for t ≤ q/(µ(1 − ρ)). On the other hand A(nt)/n → λt a.s. u.o.c. Combining, we obtain that ¯ n (t) = Q(nt) → q + λt − µt Q n when ρ ≥ 1 and q ¯ n (t) = Q(nt) → q + λt − µt, Q when t ≤ n µ(1 − ρ) q ¯ n (t) = Q(nt) → q + λt − (q + λt) = 0, Q when t > . n µ(1 − ρ) ¯ n (t) → (q + λt − µt)+ a.s. u.o.c. This concludes the proof of the We may summarize this as Q theorem. The unfinished business is proof of Lemma 23.1 Proof of Lemma 23.1. Since interarrival and service times are i.i.d. then, applying Theo­ rem 22.5, A(nt)/n → λt, V (nt)/n → µ−1 t a.s. u.o.c. This means in particular that (Q(0) + A(nt))/n → q + λt a.s. u.o.c. In HW 6 you are asked to establish that this implies V (Q(0) + A(nt))/n → (q + λt)µ−1 = qµ−1 + ρt (HW problem covers the case Q(0) = 0 but the extension ¯ n (t) → qµ−1 + (ρ − 1)t. � is immediate). We conclude that X � LECTURE 23. QUEUEING SYSTEMS 3 23.2. G/G/1 queue in heavy­traffic 23.2.1. Preliminary discussion The fluid model analysis given by Theorem 22.6 is essentially FSSLN applied to a queueing system. Unfortunately, at this SLLN type scaling X(nt)/n of various underlying processes, we cannot say much about how the workload Z(t) and queue length Q(t) behave in the limit t, since in this scaling they simply converge to zero when ρ < 1. We would like to obtain a more refined understanding of the behavior of Z(t), Q(t) in the limit when t is large (that is in steady­state), and for this we resort to CLT type of rescaling. Basically everywhere instead of considering √ X(nt)/n for various processes X we will consider instead X(nt)/ n. First, we need an analogue of FCLT for counting processes. We have established in Lecture 20, that, roughly speaking, if Xn , n ≥ 1 is an i.i.d. sequence with zero mean and variance σ 2 , then � for Sn = 1≤k≤n Xk the process S�nt� /n converges weakly to a Brownian motion W (t) with zero mean and standard deviation σ 2 . We have derived this for the continuous interpolation function rather than S�nt� , but with a little extra technicalities, it can be shown that this also applies to S�nt� . In case Xn are not zero mean, the same result applies by simply subtracting the mean from this i.i.d. sequence. What about the corresponding counting process N (t) = max{n : Sn ≤ t}, when Xn is non­negative? It turns out that the following FCLT holds. The proof of this result can be found in Chen & Yao [1]. Theorem 23.2 (FCLT for renewal processes). For every T > 0, the process N (t) as defined on D[0, T ] satisfies the following weak convergence with respect to the uniform metric � · �T : 3 N (nt) − µnt ⇒ µ 2 σW (t), n where W is the standard Brownian motion. Armed with this result, we can try to say something about the queueing system. Let σa2 , ca denote respectively the variance of the interarrival times and the coefficient of variation: ca = σa /E[u1 ] = λσa . Similarly, let σa2 , ca denote respectively the variance of the service times and the coefficient of variation cs = µσs . Unfortunately, in order to obtain meaningful result we also need to consider a queueing system where ρ is not a constant but also ”scales” like 1 − √θn . In order to appreciate why this is the case, let us do analysis for the case ρ < 1 is a constant. For simplicity assume that Q(0) = Z(0) = 0. We recall that Z(t) = V (Q(0) + A(t)) − B(t) = X(t) + I(t), where X(t) = V (Q(0) + A(t)) − t. In our special case Q(0) = 0 we have X(t) = V (A(t)) − t = V (A(t)) − µ−1 A(t) + µ−1 (A(t) − λt) + ρt − t. From FSLLN A(nt)/n → λt a.s. u.o.c. Applying Donsker’s Theorem for cumulative service times V (n): V (�nt�) − µ−1 �nt� √ ⇒ σs W (t) = µ−1 cs W1 (t), n where W1 is a standard Brownian motion. 4 Combining the two convergence statements as well as the fact that the interarrival times and service times are independent from each other, we obtain that � 1 V (A(nt)) − µ−1 A(nt) A(nt) V (A(nt)) − µ−1 A(nt) √ � = ⇒ λ 2 µ−1 cs W1 (t), n n A(nt) Applying Theorem 23.2 for the arrival process A(t) we obtain 1 A(nt) − λnt ⇒ λ 2 ca W2 (t), n where W2 (t) is a standard Brownian motion. Note that W1 , W2 are independent, since the first is obtained from the service times, second is obtained from the interarrival times, and the two √ sequences are independent. Putting this together we obtain that X(nt) behaves like n 1 1 nt λ 2 µ−1 cs W1 (t) + µ−1 λ 2 ca W2 (t) − (1 − ρ) √ . n √ So when ρ < 1 is constant we have a term −(1 − ρ) nt which diverges to −∞ and ”kills” the Brownian term. But if we at the same time make ρ approach unity at the rate such that (1 − ρ) ≈ √θn , then we obtain a non­trivial scaling behavior: Brownian motion with drift −θ and variance λµ−2 (c2s + c2a ). 23.2.2. G/G/1 heavy­traffic theorem √ How can we arrange for ρ ≈ 1 − θ/ n. One natural way to do this is as follows. Assume we have a queueing system such that λ = µ, ρ = 1, namely, it is critically loaded. Fix a parameter θ > 0 and let n ∈ N be large. Let ρn = 1 − √θn and consider a rescaled sequence of interarrival times n n unk = ρ−1 n uk , k ≥ 1. Denote by A (t) the corresponding arrival process. Let also S (t) = S(t) n n n denote the service counting process (unaffected by n), and let Q (t), Z (t), B (t), Z n (t) be the corresponding queue length, workload, busy time and idle time processes. In effect we are considering a sequence of G/G/1 type queueing systems. For this system we obtain that the arrival rate λn = ρn λ and average utilization is ρn . We now state formally the result we are about to derive. Recall that RBM (θ, σ 2 ) stands for Reflected Brownian Motion with drift θ and variance σ 2 . We also let BM (θ, σ 2 ) denote a Brownian motion with the same parameters. √ Theorem 23.3. Consider a sequence of G/G/1 queueing systems with ρn = 1 − θ/ n. Suppose Q(0) √ → q for some q ≥ 0. Then the following weak convergence takes place in D[0, T ] with respect n to � · �T for every T > 0 Z(nt) √ ⇒ RBM (−θ, λ−1 (c2a + c2s )), n Q(nt) √ ⇒ RBM (−θ, c2a + c2s ), n I(nt) √ ⇒ sup (−W (s))+ , n 0≤s≤t where W = BM (−θ, λ(c2a + cs2 )). LECTURE 23. QUEUEING SYSTEMS 5 We recall that λ = µ in this setting, so we could have used µ in the above expressions. We will prove this result in the next lecture. In the remainder of this lecture we state without a proof the following fundamental implication of Theorem 23.3. Our setting is again the same as√in Theorem 23.3: we have sequence of queueing systems G/G/1 with traffic intensities ρn = 1−θ/ n, which is achieved by considering a queueing system with ρ = 1, and rescaling interarrival times by ρ−1 n , and leaving service times intact. We call this sequence of queueing systems simply G/G/1 queueing system in heavy­traffic. We let Exp(z) denote exponential distribution with parameter z. Theorem 23.4 (Heavy­traffic formula for G/G/1 queueing √ system). Consider a G/G/1 queueing system in heavy traffic with traffic intensity ρn = 1 − θ/ n. Then the corresponding queue length and workload processes Qn (t), Z n (t) converge in distribution to a steady state distribution as t → ∞. Moreover, if Qn (∞), Z n (∞) denote r.v. selected according to this distribution, then Z n (∞) 2λθ √ ⇒ Exp( 2 ) ca + c2s n Qn (∞) 2θ √ ⇒ Exp( 2 , ca + c2s ) n as n → ∞. We will not prove this result, just mention some underlying ideas. First it is not obvious that the processes Z(t), Q(t) converge to a stationary regime when ρ < 1. This, however can be established using various ways, for example using so­called Lindeley’s recursion. Provided that convergence to stationarity holds, the main building block is to use Theorem √ 23.3 which states that the processes Z(t), Q(t) look ”increasingly” like RBM as ρn = 1 − θ/ n → 1 and Theorem 21.12 which states that stationary distribution of an RBM is exponential. Although, as we know, convergence in distribution does not necessarily imply convergence of expectations (or higher moments) it turns out that it does in this case, and, in particular (23.5) (23.6) E[Z n (∞)] c2a + c2s √ lim , = n 2λθ n E[Qn (∞)] c2 + cs2 √ lim = a , n 2θ n These two formulas have a great practical use, as they predict a performance of a queueing system using only first and second moments of interarrival and service times. Let us do a quick example of applying these formulas. Suppose we have a queueing system were arrivals occur on average every 3.4 seconds and the variance of interarrival times is estimated to be 2. Suppose the service time takes deterministically 3.3 seconds. What is our prediction of average queue length and average workload? It seems at √ √ first that we are in trouble here: the formulas give n n predictions for E[Z (∞)]/ n, E[Q (∞)]/ n and n is an artifact of the analysis here, but not a parameter of the model. But the approximations (23.5) and (23.6) suggest √ ca2 + cs2 c2a + c2s n = 2λθ 2λ(1 − ρn ) 2 2 √ c + cs c2 + cs2 E[Qn (∞)] = n a = a 2λθ 2(1 − ρn ) E[Z n (∞)] = 6 Thus, we have expressions involving only the data of the model. In particular, for our case λ = 1/3.4 = .2941, ρ = 3.3/3.4 = .9706, c2a = 2/3.42 = .1953 and c2s = 0 (since service time is deterministic). Thus we obtain estimates .1953 E[Z(∞)] ≈ = 11.29, 2 · .2941 · (1 − .9706) E[Q(∞)] ≈ λE[Z(∞)] = 3.32. Even though, this does not look much as a heavy­traffic system, these types of approximations are often remarkably accurate. Refer to Chen & Yao [1] for a summary of simulations and computations experiments done for a more general class of queueing systems, called Generalized Jackson Networks, to see that even when traffic intensities are around .60, the heavy­traffic theory predictions are quite accurate. 23.3. Additional reading materials • Chapter 6 of Chen & Yao book [1] from the course packet.