Advanced Stochastic Processes. LECTURE 21 G/G/1 queueing systems and Reﬂected Brownian Motion (RBM) Lecture outline • G/G/1 queueing system • One dimensional reﬂection mapping • Reﬂected Brownian Motion (RBM) 21.1. Technical preliminaries We use the following technical facts. If x is a Lipschitz continuous, � t then it also has derivative everywhere except measure zero set of points on [0, ∞) and x(t) = 0 ẋ(u)du. Note, however that if x is a realization of a Brownian motion, then it is nowhere diﬀerentiable and we cannot write this integral representation. Also if x�is a continuous and nondecreasing, then it has derivatives t almost everywhere and again x(t) = 0 ẋ(u)du. 21.2. G/G/1 queueing system We consider the following G/G/1 queueing system consisting of a single server which works at a unit speed. The G/G/1 notation stands for general arrival/general service times/single server type queueing system (as opposed to for example M/M/1 which stands for Poisson ar rival/Exponential service time/single server type systems). Initially we assume there are Q(0) jobs in the system. There is an arrival process into the system. The times between successive λ = 1/E[u1 ] denote the arrivals is an i.i.d. sequence un ≥ 0, n ≥ 1 of random variables. We let� arrival rate. Namely, 1/λ is the mean interarrival time. We let U (n) = 1≤i≤n ui and let A(t) = sup{n : U (n) ≤ t} denote the counting process describing the arrival process. 1 2 The time it takes to process the i job arriving to the server (including the ﬁrst Q(0) jobs) is also assumed to be an i.i.d. � sequence vn ≥ 0, n ≥ 1 of random variables with service rate µ = 1/E[v1 ]. Also V (n) = 1≤i≤n vi and let S(t) = sup{n : U (n) ≤ t} denote the counting process describing the service process. Denote by D(t) the cumulative departure process from the queueing system – the number of jobs that departed up to time t. If the server was working all the time, then we would have D(t) = S(t), but occasionally, the server runs out of jobs. So let B(t) denote the total cumulative time that the server was working on jobs during [0, t]. Naturally B ≥ 0, B is nondecreasing and B(t) ≤ t. Then D(t) = S(B(t)). Note that we can also write � t B(t) = 1{Q(s) > 0}ds. 0 The jobs which have not been processed yet form a queue. Denote by Q(t) the length of the queue at time t. Then we naturally obtain (21.1) Q(t) = Q(0) + A(t) − D(t) = Q(0) + A(t) − S(B(t)). In addition we consider workload process Z(t) – this represents the amount of time it takes to process all the jobs present in the system at time t (queue plus possibly a job being served), assuming no further jobs arrive after time t. Loosely speaking this is the time it takes to clear the system after we ”shut the door”. Note that (21.2) Z(t) = V (Q(0) + A(t)) − B(t). (convince yourself that this is indeed the case). Finally, it is also useful consider the cumulative idling process � t (21.3) I(t) = t − B(t) = 1{Q(s) = 0}ds. 0 Problem 1. Show that Q, Z ∈ D; Y, Z ∈ C The main question we ask for G/G/1 system is to characterize the behavior of the queue length Q(t) and workload Z(t) as a process or in steady state (t = ∞), when steadystate exists, assuming that we know the distribution of the interarrival and service times. Ideally, we would like to compute the distribution of Q(t), Z(t). But this is, with some exceptions, infeasible. Thus the focus will be on obtaining approximations. As we will see we can get good approximations when the system is in so called heavy traﬃc regime. This is the regime when λ ≈ µ. Then the typically observed queue length will be very large and, as we will see, can be approximated by a certain reﬂected Brownian motion, for which both time dependent and steadystate distribution is known. 21.3. One dimensional reﬂection (Skorohod) mapping Introduce (21.4) X(t) = V (Q(0) + A(t)) − t LECTURE 21. QUEUEING SYSTEMS 3 Then X(t) represents the total work that arrived into the system up to time t minus t. Then we can rewrite (21.2) as (21.5) Z(t) = X(t) + I(t) ≥ 0. Observe that I(t) is a nondecreasing piecewise linear continuous process (it increases at rate 1 when there are no jobs in the system, and stays constant when there are jobs in the system). In particular, dY (t) ≥ 0 (21.6) whenever derivative is deﬁned. Moreover, since the cumulative idling time can increase only when there are no jobs in the system, then � ∞ (21.7) Z(t)dI(t) = 0. 0 There is a good reason to write equations (21.5),(21.6),(21.7) – these equations turn out to be deﬁning Q, Y uniquely from X and we now establish this fact in a more general setting. We say that x ∈ D has no downward jumps, if at every point of discontinuity t0 we have limt↑t0 x(t) ≤ x(t0 ). Problem 2. Show that X has no downward jumps. Theorem 21.8 (Reﬂection (Skorohod) Mapping Theorem). Given x ∈ D, x(0) ≥ 0, with no downward jumps, there exists a unique pair y ∈ C, z ∈ D such that (a) z(t) = x(t) + y(t) ≥ 0, t ∈ R+ (b) dy(t) ≥ 0 (c) z(t)dy(t) = 0 for all t ∈ R+ . This pair is uniquely deﬁned by (21.9) y(t) = sup (−x(s))+ 0≤s≤t (21.10) z(t) = x(t) + sup (−x(s))+ 0≤s≤t Moreover, the mappings Ψ, Φ : D → D given by y = Ψ(x), z = Φ(x) are Lipschitz continuous with respect to the uniform norm � · �T for every T > 0. We call z the reﬂected process of x and y the regulator of x Intuitively, the ”role” of the regulator process y is to provide enough ”pushing” to ensure that the modiﬁed process z = x + y remains nonnegative, given a (possibly negative) process x. Proof. We begin by verifying that the solutions given in the theorem are valid. Clearly, z ≥ 0 and y is nondecreasing, implying dy ≥ 0. Let us show that y ∈ C. Fix t. If x is continuous in t then continuity of y in t is immediate, as supremum of a continuous function is a continuous function. Suppose x is discontinuous in t, namely it has an upward jump. Let x− = limt� ↑t x(t). Then x(t) > x− and, since x is rightcontinuous, x(t� ) > x− for all t� in some interval [t, t + δ]. This means y(t� ) = y(t) on [t, t + δ]. Also since x− is the left limit of x, then for every � > 0 there exists δ, such that |x(t� ) − x− | < � for t� ∈ [t − δ, t]. This means |y(t� ) − y(t)| < � for t� ∈ [t − δ, t] and the proof of continuity is complete. Finally, we check that zdy = 0. Suppose dy > 0. Then we claim that x(t) = inf 0≤s≤t x(s) (inf is achieved in t). Indeed, otherwise x(t) > inf 0≤s≤t x(s) and since x can only have upward jumps, x(t + δ) > inf 0≤s≤t x(s) for all suﬃciently small δ. 4 As a result y(t + δ) = y(t) for all suﬃciently small δ, contradicting dy > 0. We conclude x(t) = inf 0≤s≤t x(s), which implies z(t) = 0 and z(t)dy(t) = 0. We now establish the uniqueness of the solution. Suppose there exists an additional solution � y ∈ C, z � ∈ D satisfying the properties of the reﬂection mapping, for the same input process x. Note that z � − z = y � − y is a diﬀerence between two continuous nondecreasing processes. As a result it is diﬀerentiable almost everywhere and � t d 1 � 2 (z(s) − z � (s)) (z(s) − z � (s))ds (z(t) − z (t)) = ds 2 0 � t d d = (z(s) − z � (s))( y(s) − y � (s))ds ds ds 0 But, by assumption zdy = z � dy � = 0, and we obtain an expression � t d d (−z(s) y � (s) − z � (s) y(s)ds) ≤ 0 ds ds 0 � We conclude z(t) = z (t). It is then immediate that y(t) = y � (t). It remains to show that the mappings y = Ψ(x) and z = Φ(x) are Lipschitz continuous. That is, we need to show that for some constants C1 , C2 > 0 and every pair x, x� ∈ D[0, T ], we have �Ψ(x) − Ψ(x� )�T ≤ �x − x� �T , �Φ(x) − Φ(x� )�T ≤ �x − x� �T Denote �x − x� �T by V ≥ 0. For any t ∈ [0, T ] we have Ψ(x)(t) − Ψ(x� )(t) = sup (−x(s))+ − sup (−x� (s))+ 0≤s≤t 0≤s≤t + � ≤ sup (−x (s) + V ) − sup (−x� (s))+ 0≤s≤t 0≤s≤t � ≤ sup (−x (s)) + V − sup (−x� (s))+ 0≤s≤t + 0≤s≤t =V Similarly, we show Ψ(x� )(t) − Ψ(x)(t) ≤ V . This proves Lipschitz continuity of Ψ with constant � C1 = 1. The Lipschitz continuity of Φ follows then immediately with constant C2 = 2. The reﬂection mapping also satisﬁes the following important ”memoryless” property: if we consider the process starting from some time t0 its reﬂection is the same as if we started at time 0: Proposition 1. Given t0 > 0, x ∈ D and the reﬂection y = Ψ(x), z = Φ(x) of x, consider a x)(t) = y(t) − y(t0 ). modiﬁed process x(t) ˆ = z(t0 ) + x(t) − x(t0 ). Then Φ(ˆ x)(t) = z(t0 + t), Ψ(ˆ Problem 3. Establish this proposition. 21.4. Reﬂected Brownian motion We will see later on that when the G/G/1 queueing system is in heavytraﬃc, the process X(t) deﬁned in (21.4) is approximated well by a Brownian motion. For now assume that it is in fact a Brownian motion. Note, that X(t) is a process, whose distribution we now in principle, since it is directly linked the arrival and service processes. Thus if we can ﬁnd a reﬂection of X with respect to the Skorohod mapping, we obtain an approximation of the workload process Z(t). LECTURE 21. QUEUEING SYSTEMS 5 Deﬁnition 21.11. A (onedimensional) Reﬂected Brownian Motion (RBM) is the process Z = Φ(W ) obtained by Skorohod mapping (Ψ, Φ), when the input process is a Brownian motion W (t), W (0) ≥ 0. When W has drift θ and variance σ 2 , we also write Z = RBM (θ, σ 2 ). Knowing the forms (21.9),(21.10) of the reﬂection mapping allows us to obtain say something about the distribution of the reﬂected process Z when the input process is a Brownian motion. Theorem 21.12. A Reﬂected Brownian Motion Z(t) = RBM (θ, σ 2 ), converges in distribution to some limiting random variable Z(∞) iﬀ θ < 0. In this case Z(∞) is exponentially distributed with parameter −2θ/σ 2 . It should not be surprising that we get limiting exponential distribution when the drift is neg ative and no limiting distribution when drift is nonnegative. After all we have established these facts for a maximum of a Brownian motion M (t) = sup0≤s≤t B(s). We just do the appropriate adjustments. Proof. First assume W (0) = 0. Observe that in this case sup0≤s≤t (−W (s))+ = sup0≤s≤t (−W (s)). Then P(Z(t) ≥ z) = P(W (t) + sup (−W (s)) ≥ z). 0≤s≤t ˆ t (u) = W (t) − W (t − u), 0 ≤ u ≤ t and W ˆ t (u) = W (u), u ≥ t. Observe Consider the process W 2 that it is also a Brownian motion with drift θ and variance σ (this is similar to a problem on midterm and some of the hw problems). Therefore P(W (t) + sup (−W (s)) ≥ z) = P( sup (W (t) − W (s)) ≥ z) 0≤s≤t 0≤s≤t ˆ (s) ≥ z) = P( sup W 0≤s≤t = P( sup W (s) ≥ z) 0≤s≤t Now we just recall basic properties of a Brownian motion. When θ ≥ 0 we have sups≥0 W (s) = ∞ with probability one. Therefore P(sup0≤s≤t W (s) ≥ z) → 1 as t → ∞, and limiting distribution does not exist. When θ < 0, we know that P sups≥0 W (s) ≥ z) = exp(−2θ/σ 2 ), thus lim P( sup W (s) ≥ z) = exp(−2θ/σ 2 ). t→∞ 0≤s≤t This concludes the proof for the case W (0) = 0. Suppose now W (0) = w > 0. We let τ = inf{t : W (t) = 0}, including the possibility τ = ∞. When θ ≤ 0 we know that τ < ∞ a.s. Then from strong Markov property of a Brownian motion we know that W (τ + t) is a Brownian motion which starts with origin. Applying Proposition 1, Z(τ + t) is the reﬂected Brownian motion implying lim P(Z(t) ≥ z) = lim P(Z(τ + t) ≥ z) t→∞ t→∞ which is unity when θ = 0 and exp(−2θ/σ 2 ) when θ < 0. When θ > 0 and τ < ∞, we use the same argument to show limt→∞ P(Z(t) ≥ z) = 1. When τ = ∞, we note that P(Z(t) ≥ z |τ = ∞) = P(W (t) ≥ z |τ = ∞) 6 since if τ = ∞ then Brownian motion never hits zero and Y (t) = sup0≤s≤t (−W (s))+ = 0, Z(t) = W (t) + Y (t) = W (t). We have P(W (t) ≥ z, τ = ∞) P(W (t) ≥ z |τ = ∞) = P(τ = ∞) But limt→∞ P(W (t) ≥ z) = 1 since θ > 0. This implies that limt→∞ P(W (t) ≥ z, τ = ∞) = P(τ = ∞) (we use the following fact: if the sequence of events Ak satisﬁes limk P(Ak ) = 1, then for every B, limk (Ak ∩ B) = P(B). Check this identity). This implies limt→∞ P(W (t) ≥ z |τ = ∞) = 1 and we are done. Here is a simpler argument, observed by Premal. We do not need to condition on τ when θ > 0. Observe that Z(t) ≥ W (t) with probability one, as the component Y (t) is always non negative. Therefore P(Z(t) ≥ z) ≥ P(W (t) ≥ z). But limt→∞ P(W (t) ≥ z) = 1. (why does not this apply for the case θ ≤ 0). � This concludes the proof. 21.5. Additional reading materials • Course packet, Chapter 6 from Chen & Yao book ”Fundamentals of Queueing Networks”