Fluid Model of a Queueing System

Advanced Stochastic Processes. LECTURE 22 Fluid model of a G/G/1 queueing system Lecture outline • Stationary distribution of RBM • Fluid model of G/G/1 queueing system 22.1. Stationary distribution of RBM In the previous lecture we showed that the distribution of RBM (θ, σ 2 ) is exponential with parameter −2θ/σ 2 , when θ < 0. In fact, as is not surprising, this distribution is also stationary distribution of the RBM. First we define stationarity for any stochastic process. Definition 22.1. A stochastic process X(t) is defined to be stationary if for any t1 < t2 < · · · < tk and t, the joint distribution of (X(t1 + t), . . . , (X(tk + t)) is the same as of (X(t1 ), . . . , (X(tk )). d Observe that when the process is Markovian, it suffices to require that X(t + s) = X(t) for any t, s. The Proposition states that the RBM is a Markovian process. Proposition 1. The exponential distribution π with parameter 2θ/σ 2 is the unique stationary distribution of the RBM when θ < 0. Proof. Since, as we said, the RBM process is Markovian, it suffices to establish that the dis­ tribution of Z(0) and Z(t) is the same under π. We fix t. Portmentau Theorem establishes that weak convergence of measures occurs if and only if convergence of expectations holds for every bounded continuous function. This also implies that two measure are the same iff for every bounded continuous function f , its expectation with respect to two measures is the same. Thus it suffices to show that Eπ [f (Z(0))] = Eπ [f (Z(t))] for every bounded continuous f . We have es­ tablished that π is the limiting distribution of RBM . Namely, lims→∞ E[f (Z(s))] = Eπ [f (Z(0))]. But lim E[f (Z(s))] = lim E[f (Z(s + t))] = lim E[EZ(s) [f (Z(s + t))]] s→∞ s→∞ s→∞ 1 2 Thus lim E[EZ(s) [f (Z(s + t))]] = Eπ [f (Z(0))]. s→∞ Let g(x) = Ex [f (Z(t))]. We just showed lim E[g(Z(s))] = Eπ [f (Z(0))]. (22.2) s→∞ We claim that g(x) is a bounded continuous function. It is bounded since f is bounded. It is continuous follows from the following fact given any function x ∈ D if we change its starting point x(0) to a different point xˆ(0) = xˆ by value �x(0) − xˆ(0)| ≤ δ, but otherwise leave the function intact, then the function xˆ satisfies �ˆ x − x�T = |x(0) − xˆ(0)| < δ. The reflected process z = Φ(x) is a Lipshitz continuous (with constant 2) image of x. Thus changing the starting point by amount δ changes creates a new process zˆ such that �ẑ − z �T ≤ 2|x(0) − xˆ(0)| = 2δ. This means that the expected value Ex [f (Z(s + t))] changes also by at most δ and indeed g(x) is a continuous function. But then Portmentau Theorem, the fact Z(s) ⇒ π imply that (22.3) lim E[g(Z(s))] = Eπ [g] = Eπ [Z(t)]. s→∞ Combining with (22.3) we complete the proof of stationarity. � There is an alternative derivation of the fact that exponential distribution with parameter −2θ/σ 2 is stationary distribution of the RBM. It uses Ito formula, see Section 6 of Chen and Yao [1] in the course packet. 22.2. Convergence of reflected processes For the following discussion we will be considering convergence of functions in D = D[0, ∞) uniformly on compact sets (u.o.c.). Recall, that in the context of this space xn ∈ D converges u.o.c. to x ∈ D if for every T > 0, we have �xn − x�T → 0. We now pose the following question: if a sequence of functions (processes) xn converges to x does the same apply to the reflected processes zn and z? The answer is yes, as we will establish soon. The importance of this property stems from the fact that we will be able to approximate process X(t) corresponding to the queueing process by a Brownian motion. As a result we can approximate the workload process Z(t) by an RBM. Lemma 22.4. Given sequences xn ∈ D, suppose xn → x u.o.c. Let yn = Ψ(xn ) zn = x n + y n y = Ψ(x) z =x+y Then yn → y and zn → z u.o.c. Proof. The proof follows from reflection mapping Theorem 21.8 from Lecture 21, in particular, the Lipschitz continuity of the mappings Ψ, Φ. Fix any T > 0. We have from Theorem 21.8 that �yn − y�T = �Ψ(xn ) − Ψ(x)�T ≤ �xn − x�T ≤ �xn − x�T . It follows that zn → z u.o.c. Similar result follows for zn and z. � LECTURE 22. QUEUEING SYSTEMS 3 22.3. Fluid model of a G/G/1 queueing network Our next goal is to establish essentially FSLLN for a queueing system. SLLN says that averages converges to a mean a.s. FSLLN says that functions interpolating averages converge uniformly to a mean process which is just a linear function. We now establish a similar result for counting (renewal) processes and ”pass” it through the Skorohod mapping. On the output we obtain the following process which approximates the workload process but has a very simple piece­wise linear form. Let ρ = λ/µ. Parameter ρ is called average workload or utilization of the queueing system. Z(t) = Z(0) + (ρ − 1)t for t ≤ Z(0)/(1 − ρ) and Z(t) for larger t, when ρ < 1 and Z(t) = Z(0) + (λ/µ − 1)t for all t when λ ≥ µ. We call this fluid model of a queueing system. It does have the following indeed fluid model interpretation. Imagine that you have a queue with a large number n of jobs at initial time 0. As time goes on jobs arrive at rate λ and depart at rate µ. When ρ < 1, namely λ < µ the queue length will be decreasing with rate λ − µ < 0 and workload will be decreasing with rate ρ − 1 and roughly at time Z(0)/(1 − ρ), the queue will be closed to empty. Starting from this time the workload will be fluctuating between zero and non­zero, but typically will be much smaller than n. Thus we approximate it by Z(t) = 0. When ρ ≥ 1, however, the queue length will stay roughly the same when ρ = 1 and will be linearly increasing when ρ > 1. We can draw the following analogy with the fluid system. Imagine water goes through a pipe, which has processing rate µ. If water arrives with rate λ < µ and initially there is some amount x of water in the tank, then the water in the tank will decrease to zero at time x/(1 − λ/µ) and will stay at zero level ever after. But if water rate λ ≥ µ then the amount in the tank will stay the same (λ = µ) or will start increasing (λ > µ). We begin by strengthening FSLLN. In particular, we now show that SLLN implies FSLLN as well as � FSLLN for the corresponding renewal�process. Thus, consider a sequence Xn of r.v. Let Sn = 1≤k≤n Xk and let N (t) = max{n : 1≤j≤n Xj ≤ t} be the corresponding counting process. Theorem 22.5 (FSLLN for renewal processes). Suppose Sn /n → m ¯ almost surely, for some −1 ¯ Then S(�nt�)/n → mt ¯ and N (nt)/n → m ¯ t almost surely u.o.c. constant m. ¯ a.s. point­wise for each fixed t. For this we simply Proof. We first prove that S(�nt�)/n → mt observe that S(�nt�) S(�nt�) �nt� → mt = ¯ n n �nt� a.s. as n → ∞ since Sn /n → m ¯ a.s. The proof of u.o.c. convergence follows exactly the same argument as the proof of FSLLN – Theorem 20.5 from Lecture 20. (There we considered a continuous interpolation of Sn instead of simply S�nt� but the argument is the same). We now prove that for every t there holds N (nnt) → m ¯ −1 t a.s. The proof of u.o.c. again follows the same line as the proof of Theorem 20.5. We have SN (nt) ≤ nt ≤ SN (t)+1 , implying SN (nt)+1 N (nt) + 1 SN (nt) nt ≤ ≤ . N (nt) N (nt) + 1 N (nt) N (nt) 4 The assumption Sn /n → m̄ a.s. implies that N (nt) → ∞ a.s. as n → ∞ and therefore S (nt) S (nt)+1 N (nt)+1 → 1 a.s. Then we obtain that a.s. NN(nt) →m ¯ a.s. and NN(nt)+1 →m ¯ a.s. Combining, we N (nt) obtain that nt N (nt) →m ¯ a.s. or N (nt) n →m ¯ −1 t. � We now return to the queueing processes. We consider the following setting. Initial queue length is assumed to be large: Q(0) = �qn� for some non­negative real q and large positive integer n. We would like to analyze the queue length, workload and idling time processes at time scale comparable to n: Q(nt), Z(nt), I(nt). To obtain some limiting statement we also rescale these values by n and thus introduce ¯ n (t) = Q(nt) , Z̄ n (t) = Z(nt) , I¯n (t) = I(nt) Q n n n Theorem 22.6 (Fluid model of a G/G/1 queueing system). Given a G/G/1 queueing system with arrival rate λ and service rate µ, Consider the sequence of processes (Q(t), Z(t), B(t)) cor­ responding to Qn (0) = �qn�, for some q ∈ R+ . Then q (22.7) lim Z̄ n (t) = ( + (ρ − 1)t)+ , n→∞ µ q (22.8) lim I¯n (t) = (− + (1 − ρ)t)+ , n→∞ µ n ¯ (22.9) lim Q (t) = (q + (λ − µ)t)+ n→∞ a.s. u.o.c. Before we prove the result, let us interpret it. First, while we assumed that our G/G/1 queueing system has i.i.d. interarrival and service times, as we will see in the proof the result of the theorem holds under any conditions provided that arrival process A(t) and service process S(t) satisfy FSLLN: A(nt)/n → λ, S(nt)/n → µt for some constant λ, µ > 0. This covers the far larger class of arrival and service processes than covered by i.i.d. case. To obtain the limiting behavior we essentially rescale the time and space by the same factor n by which we rescale the initial queue length. In this case the theorem says the following: when ρ < 1, the rescaled queue length and workload processes drop to zero at the same time q/(µ − λ) and from then on stay at zero level. The idle time process is zero up until this time and from then on has rate 1 − ρ. Namely, the server works ρ percent of time and idles the rest of the time. On the other hand, when ρ ≥ 1, the rescaled queue length and workload processes become linear processes with non­negative rate λ − µ and ρ − 1 respectively. Also the idling process is always zero ­ the server works ”almost” all the time. We say ”almost” because we only know that the limit is zero. We will prove this theorem in the next lecture. 22.4. Additional reading materials • Chapter 6 of Chen & Yao book [1] from the course packet.