Final Notes and Ongoing Research Questions

Advanced Stochastic Processes. LECTURE 25 Final notes and ongoing research questions and resources 26.1. GJN and open questions 26.1.1. A brief summary of GJN heavy­traffic theory We have described in previous lecture the GJN model. It is called ”Generalized” because original (Jackson) network assumes exponential interarrival times and exponential service times. As we will mention shortly this dramatically simplifies the picture. From the arrival rates λj we first formulate the vector of so­called ”effective” arrival rates, λ̄j which is defined to be the unique solution to the traffic equation � ¯ j = λj + ¯k λ pjk λ k ¯ j ? In vector form Can you interpret the meaning of λ λ̄ = λ + P t λ̄ or λ̄ = [I − P t ]−1 λ. ¯ j /µj . It turns out that if ρj < 1 From this we formulate workload ρj in every server j as ρj = λ in every server, then the system converges to a steady­state and in steady­state the proportion of time server j is working is ρj . Matrix R = I − P t is the key for formulating the corresponding Skorohod mapping problem: given x ∈ DJ [0, ∞) � D find a unique pair y, z ∈ D such that z = x + Ry ≥ 0 dy ≥ 0, y(0) = 0 zj dyj = 0. Theorem 26.1. The Skorohod mapping problem has a unique solution y = Ψ(x), z = Φ(x). Moreover, the mappings Ψ, Φ are Lipschitz continuous. 1 2 How is this used in GJN to formulate Fluid Model and Heavy­Traffic approximations? Again a corresponding input process X(t) is identified such that Z(t) = X(t) + [I − P t ]I(t). To obtain the fluid model we need to consider X(nt) Z(nt) I(nt) = + [I − P t ] n n n Theorem 26.2. Assume Q(0) = nq for some vector q ≥ 0. X(nt) converges to a linear function n x with rate (ρ − e)t, where ρ = (ρj ) and e is the J ­dimensional unit vector. The unique solution y = Ψ(x), z = Φ(x) are piece­wise linear functions. Moreover z(t) becomes a zero function after some finite time period. A heavy­traffic approximation is obtained similarly to G/G/1 queue as well. First when we take as a input to a multi­dimensional Skorohod problem a J ­dimensional Brownian motion W (t), on the output we obtain Φ(W ) which is also called a (multidimensional) Reflected Brownian Motion. Then we consider a critically loaded system with ρj = 1 for all servers j. For each θ external arrival process j we again rescale interarrival times so that the resulting ρj = 1 − √jn √ for some constants θj . It is then showed that√X(nt)/ n converges weakly to a multidimensional √ Brownian motion, and, as a result, Z(nt)/ n and Q(nt)/ n converge weakly to a Reflected Brownian motion. The drift and covariance matrix of this RBM is explicitly computed knowing θj and parameters of the networks: arrival rates, service rates, coefficients of variations for interarrival and service times and matrix P . This development is primarily due to Harrison and Reiman [3] and Reiman [6]. The second paper, which is the paper developing heavy­traffic approximation of GJN is included in the reading materials. What can be said about the distribution of the RBM as t → ∞? Recall that in G/G/1 case this is simply the exponential distribution. Things are far more complicated here. It is known Harrison and Williams [4] (I only have hard­copy) that the stationary distribution exists if and only if ρj < 1, but it does not necessarily have exponential distribution. It turns out that there are special cases when it does. This was established also by Harrison and Williams [5]. Theorem 26.3. Suppose the coefficient of variations of interarrival and service times are equal to unity (for example when arrival and service processes are Poisson). Then the stationary distribution of the RBM is exponential, with rates explicitly computable from the parameters of the network. As in the case of G/G/1 queueing system, the GJN itself converges to a steady­state when ρj < 1. Thus it has some corresponding steady­state random vectors Q(∞), Z(∞) corresponding to t = ∞. Is there a relationship between these vectors and steady­state of the RBM? We have established this recently √ only √ jointly with Zeevi [2] (included in the reading materials). Namely n n that Q (∞)/ n, Z (∞)/ n converge weakly to the stationary RBM. In the special case when stationary RBM has exponential distributions, this implies exponential distribution for the limits of queue length and workload. One important ”side result” of our analysis was exponential decay for these quantities: P(�Q(∞)� > x) ≈ e−c(1−ρ)x . 26.1.2. Open problems As we have mentioned, simulations show that the predictions of the heavy­traffic theory are pretty good. But there is not good theory around it. LECTURE 25. FINAL NOTES 3 Open problem 1. [Quality of heavy­traffic approximations]. What is the quality of heavy­traffic approximations in G/G/1 and more interestingly GJN. Specifically, try to identify the rate with which Qn (nt) √ − RBM n n converges to zero in various senses. Even better obtain an explicit bound on E[ Q √(nt) − RBM ] n which converges to zero. The corresponding question in stationary regime. With which rate does E[(1 − ρ)Q(∞)] − E[RBM ] converges to zero? Quite often the only problem to solve some performance analysis problem related to a queue­ ing system is via simulations. But how long do we need to simulate in order to get a good confidence? This critically depends on what time does it take for a queueing network to con­ verge to stationarity. It is known that simulations becomes harder and harder when system is in heavy­traffic ρ ≈ 1. Open problem 2. [Relaxation times of queueing networks] What is the rate of convergence to stationarity for GJN? For example, identify the rate of the convergence � � � � t→∞ �E[Z(t)] − E[Z(∞)]� → 0, or in distribution sense � � � � t→∞ �P(Z(t) ≤ x) − P(Z(∞) ≤ x)� → 0. The problem is especially important in heavy­traffic regime when ρ ≈ 1. Heuristic arguments show that the relaxation times is ≈ 1/(1 − ρ)3 , but there is no solid theory. A lot of research is devoted to studying large deviations theory of queueing systems. Here the question is: establish that P(�Q� > x) ≈ e−cx and identify the leading constant c. The full theory is developed for acyclic GJN, but not in general case. Open problem 3. [Large deviations for GJN] Establish whether P(�Q� > x) ≈ e−cx in GJN and identify the leading constant c. The problem can be formulated both as a process level large deviations problem and as large deviations for steady­state. 26.2. ”Hot” research area in stochastic processes – Call centers Call centers can be modeled as queues which tend to operate in heavy­traffic regime. Back in 80’s Halfin and Whitt showed that the appropriate model is a queueing model with n parallel arrival rate µ = λ, servers and arrival rate ≈ λn. The service rate is assume to ”match” the √ but the actual number of servers needs to be increased by a safety stock β n. This results in √ of jobs in the a heavy­traffic regime with utilization ρ ≈ 1 − β/ n. Let Q(t) be the number √ system excluding those in service. Namely the total number is Q(t) + n + β n. Let I(t) be the number of idle servers. 4 Theorem 26.4 (Halfin­Whitt Theory). Suppose the arrival and service processes are Poisson. Then in steady­state Q(∞) P( √ > x|Q(∞) > 0) → e−βt , n I(∞) Φ(β − t) . P( √ > x|I(∞) > 0) → Φ(β) n √ Moreover, on the process level, Q(t)/ n converges weakly to a Brownian motion with a negative √ drift −µβ, and Q(t)/ n converges weakly to a diffusion with drift −µ(x + β). Halfin­Whitt theory is not developed for non­Poisson case. Moreover, in multitype case (several streams of calls with different service requirements) the question is optimal control of the call center. Finally, these days many call­centers have agents with different skills. Skill­based routing is one of the most ”burning” practical problem of modern days call centers. 26.3. Other applications of heavy­traffic theory Production processes (manufacturing, specifically semiconductor wafer fabrication labs, inven­ tory, supply­chains); communication theory (switches, TCP protocols, web servers), service pro­ cesses (real queues). 26.4. Other topics in stochastic processes not touched in this course Regenerative processes, Markov processes in general state space, stochastic differ­ ential equations, rare­event simulations. For this topic see course Stat. 271 in Harvard taught by Jose Blanchet in Statistics department. Mathematical finance. Some courses here in Sloan and Harvard. Heavy­tailed processes. CLT does not hold when the variance is infinite (for example power law distribution P(X > x) ≈ c/xα , α ≤ 2. Instead, the sum of i.i.d. sequence appropriately rescaled converges to a so­called stable process, with a limiting distribution which is not Gaussian, but something else called stable distribution. A special case of a stable distribution is Cauchy distribution � x dt P(X ≤ x) = 2 −∞ π(1 + t ) The functional limit theorems also hold. Instead of a Brownian motion, one obtains a process called Fractional Brownian motion, which has variance growing at a non­linear rate O(tH ), H is called the Hurst parameter. Strong approximations. Donsker Theorem states that a random walk suitably rescaled ”looks” increasingly like a Brownian motion in distribution. It turns out that one can ”embed” a Brow­ nian motion into a random walk.