Kavita Ramanan (Brown University, USA)

Scaling Limits of Stochastic Networks

ABSTRACT

Stochastic networks arise in a variety of applications, ranging from communication and service networks to biochemical reaction networks.  In most cases of interest, these networks are too complex to be amenable to an exact analysis, and instead, suitable scaling limits serve to provide useful qualitative insight into the system.   This lecture series will describe mathematical methods that have been developed for establishing scaling limits of stochastic networks. We will describe suitable representations of different classes of stochastic networks, methods to establish asymptotic convergence of the state processes, as well as methods to analyse the obtained scaling limits.  Time permitting, we will also provide some examples to illustrate how the mathematical tools developed in the context of stochastic networks have been applied in other areas of probability, for the study of interacting particle systems, and models in math finance.

Lecture 1. REFLECTED DIFFUSION APPROXIMATIONS OF STOCHASTIC NETWORKS

(Tuesday May 16, 10:00-12:00, CDT Teaching Room 2)

In this lecture, we will first introduce reflected diffusions in domains with piecewise smooth boundaries, describe their construction and characterization via the extended Skorokhod map and the submartingale problem.  We will then describe how reflected diffusions arise as scaling limits of a large class of stochastic networks.   Finally, we will also describe pathwise differentiability of reflected diffusions, and discuss applications to interacting particle systems, Atlas models in math finance and sensitivity analysis.  

Lecture 2. INFINITE-DIMENSIONAL SCALING LIMITS AND MEAN-FIELD MODELS

(Thursday May 18, 14:00-16:00, CDT Teaching Room 2)

The second lecture will consist of two parts. In the first part, we will describe single-server network models that employ non-head-of-the-line scheduling policies, such as Earliest-Deadline-First, Shortest-Remaining-Processing-Time, for which the state space is most conveniently represented in terms of a measure-valued process. We will describe tools that help establish convergence to hydrodynamic (or functional strong law of large numbers) limits and diffusion limits, which capture stochastic fluctuations around the hydrodynamic limits.   In the second part of the lecture, we will describe networks that are modeled in terms of weakly interacting jump Markov processes, review classical results on their fluid or mean-field limits, and describe more recent results on their stability and large deviations asymptotics. 

Lecture 3.  HYDRODYNAMIC LIMITS OF MANY-SERVER NETWORKS  

(Tuesday May 23, 15:00-17:00, CDT Teaching Room 2)

In the third lecture, we will describe a large class of many-server networks with general service distributions that arise in a broad range of applications, and introduce a convenient state representation in terms of (interacting) measure-valued stochastic processes.  We then show how to establish convergence to a hydrodynamic limit, describe its equilibrium behavior, and show how our framework provides a useful infinite-dimensional generalization of the classical ODE method used to study limits of jump Markov processes.

REFERENCES:

[1] R. Atar, A. Biswas, H. Kaspi, and K. Ramanan, "A Skorokhod map on measure-valued paths and priority queues." Annals of Applied Probability, (2016), to appear.

[2] A. Budhiraja, P. Dupuis, M. Fischer, and K. Ramanan, "Local stability of Kolmogorov forward equations for finite state nonlinear Markov processes," Electronic Journal of Probability, 20, Article 81, (2015), 1 – 30

[3] M. Bramson, Y. Lu and B. Prabhakar. “Decay of tails at equilibrium for FIFO join the shortest queue networks,”  Annals of Applied Probability, 23(5):1841—1878, 2013.

[4] D. Lipshutz and K. Ramanan, "Directional derivatives of Skorokhod maps on convex polyhedral domains." Annals of Applied Probability, (2016), to appear.

[5] W. Kang and K. Ramanan, "On the submartingale problem for reflected diffusions in piecewise smooth domains," Annals of Probability, Vol. 45 (2017) No. 1, 404-468.

[6] W.N. Kang and K. Ramanan, "Fluid limits for many-server queues with reneging" Annals of Applied Probability, 20 (2010) 2204-2260

[7] W.N. Kang and K. Ramanan, "A Dirichlet process characterization of a class of reflected diffusions," Annals of  Probability, 38 (2010) 1062-1105.

[8] W.N. Kang and R. J. Williams, An invariance principle for semimartingale reflecting Brownain motions in domains with piecewise smooth boundaries, Annals of Applied Probability, 17 (2007), 741—779.

[9] H. Kaspi and K. Ramanan. "Law of large numbers limits for many-server queues," Annals of Applied Probability, 21 (2011), 33-114.

[10] L. Kruk, J. Lehoczky, K. Ramanan and S. Shreve. "An explicit formula for the Skorokhod map on [0; a]," Annals of Probability, 35 (2007) 5:1740-1768.

[11] L. Kruk, J. Lehoczky, K. Ramanan and S. Shreve, "Heavy traffic analysis for EDF queues with reneging," Annals of Applied Probability, 21, No. 2 (2011) 484-545

[12] A. Mandelbaum and K. Ramanan. "Directional derivatives of oblique reflection maps," Mathematics of Operations Research, 35 (2010) 527-558.

[13] M. Mitzenmacher.  The power of two choices in randomized load balancing. IEEE Transactions in Parallel Distributed Systems, 12 (10): 1094—1104, October 2001.

[14] K. Ramanan. "Reflected diffusions defined via the extended Skorokhod map," Electronic Journal of Probability (EJP) 11 (2006), 934-992.

[15] K. Ramanan and M. Reiman. "The heavy traffic limit of an unbalanced generalized processor sharing model," Annals of Applied Probability, 18 (2008) 1:22-58.  

[16] N.D. Vvedenskaya, R.L. Dobrushin and F.I. Karpelevich, “A queuing system with the choice of the shortest of the two queues—the asymptotic approach”, Problemy Peredachi Informatsii, 32(1):20—34, 1996.

[17] R. J. Williams, Reflecting diffusions and queueing networks, Invited paper, Proceedings of the International Congress of Mathematicians, Berlin, 1998.