UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO Doctorado en Ciencias Matemáticas DYNAMICS OF STOCHASTIC NETWORKS AND FLOWS: CONVERGENCE, COUPLING AND LARGE DEVIATIONS. TESIS QUE PARA OPTAR POR EL GRADO DE: DOCTOR EN CIENCIAS PRESENTA: SERGIO IVÁN LÓPEZ ORTEGA DIRECTOR Y CODIRECTOR DE LA TESIS Dr. Pablo Ferrari, Universidad de Buenos Aires Dr. Matthieu Jonckheere, Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina MIEMBROS DEL COMITÉ TUTOR Dra. Begoña Fernández Fernández, Facultad de Ciencias, UNAM Dra. Ana Meda Guardiola, Facultad de Ciencias, UNAM MÉXICO, D. F., Agosto de 2013. UNAM – Dirección General de Bibliotecas Tesis Digitales Restricciones de uso DERECHOS RESERVADOS © PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL Todo el material contenido en esta tesis esta protegido por la Ley Federal del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). El uso de imágenes, fragmentos de videos, y demás material que sea objeto de protección de los derechos de autor, será exclusivamente para fines educativos e informativos y deberá citar la fuente donde la obtuvo mencionando el autor o autores. Cualquier uso distinto como el lucro, reproducción, edición o modificación, será perseguido y sancionado por el respectivo titular de los Derechos de Autor. Dynamics of stochastic networks and flows: convergence, coupling and large deviations. Sergio Iván López Ortega Advisors: Inés Armendáriz, Pablo Ferrari & Matthieu Jonckheere Version 5.0 ii Agradecimientos iv Introducción En esta tesis estudiamos la convergencia y grandes desviaciones de algunos modelos espećıficos de redes y flujos. La técnica de acoplamiento es usada a lo largo de toda la tesis. En el Caṕıtulo 1 estudiamos a la cola Browniana: un modelo de almacenamiento que toma valores continuos no negativos y que evoluciona a tiempo continuo. Para este modelo, Harrison y Williams [HW90] probaron que si el proceso de arribos tiene la distribución de un movimiento Browniano entonces el proceso de salidas efectivas tiene también la distribución de un movimiento Browniano. Es decir, obtuvieron una versión del Teorema de Burke [Bur56] en este contexto. En este trabajo probamos un resultado acerca de la convergencia bajo la operación de cola Browniana: si empezamos con un proceso continuo arbitrario que satisface algunas condiciones generales, y lo pasamos a través de una hilera de colas en tándem, ese proceso convergerá débilmente a un movimiento Browniano. Obtenemos este resultado bajo el supuesto de cargas iniciales independientes y con distribución exponencial para todas las colas. Este caṕıtulo está basado en un trabajo conjunto con Inés Armendáriz y Pablo Ferrari. En el Caṕıtulo 2 estudiamos el modelo de crecimiento polinuclear (PNG, por sus siglas en inglés). Éste es un modelo f́ısico para un cristal que crece capa por capa en una superficie unidimensional debido a posicionamientos aleatorios de part́ıculas. Para el proceso definido en la ĺınea aplicamos una técnica de acoplamiento similar a una utilizada en el contexto de colas con valores discretos en tiempo continuo por [MP95], con el fin de probar la convergencia del modelo. Además, obtenemos un resultado de convergencia local, para un proceso que contiene más información que el modelo PNG: se guarda la información generada por las trayectorias de las part́ıculas, no sólo sus posiciones en un tiempo dado. Este caṕıtulo está basado en un trabajo conjunto con Inés Armendáriz y Pablo Ferrari. El Caṕıtulo 3 es una introducción a las redes de ancho de banda compartido. Primero caracterizamos a los procesos de nacimiento y muerte reversibles y a las redes de Whittle, vi después estudiamos el concepto de insensibilidad, y finalmente introducimos el modelo espećıfico de Redes de ancho de banda. En el caṕıtulo final 4, probamos que la asignación de ancho de banda Proportional fair (PF) bajo un régimen estacionario y Markoviano comparte las mismas grandes desvia- ciones que la asignación modified Proportional fair allocation (mPF), y por lo tanto las mismas que la asignación Balanced Fairness, debido al trabajo previo de Massoulié [Mas07]. Esto es probado en dos pasos: probamos ergodicidad geométrica para PF y mPF, y después controlamos la diferencia de los procesos asociados a PF y mPF processes em- pezando en el origen, utilizando argumentos de martingalas. Finalmente presentamos una prueba independiente para el caso de redes monótonas. Este resultado resuelve una conje- tura propuesta por Massoulié [Mas07]. Este caṕıtulo está basado en un trabajo conjunto con Matthieu Jonckheere aceptado para publicarse en la revista Mathematics of Opera- tions Research. Una versión online está disponible en http://arxiv.org/abs/1207.5908 Bibliography [Bur56] P. Burke. The output of a queuing system. Operations Research, 4(6):pp. 699– 704, 1956. [HW90] M. Harrison and R. Williams. On the quasireversibility of a multiclass brownian service station. The Annals of Probability, 18(3), 1990. [Mas07] L. Massoulié. Structural properties of proportional fairness: Stability and insen- sitivity. Ann. Appl. Probab., 17(3):809–839, 2007. [MP95] T. Mountford and B. Prabhakar. On the weak convergence of departures from an infinite series of ·/M/1 queues. Ann. Appl. Probab., 5(1):121–127, 1995. Structure In this thesis we study the convergence and large deviations of some specific models of networks and flows. The coupling technique is used along the entire thesis. In Chapter 1, our model is given by the Brownian queue: a storage model taking non negative real values and evolving in continuous time. For this model, Harrison and Williams [HW90] proved that if the arrival process has Brownian distribution, then the departure process has Brownian motion as well: that is, they obtained a Burke’s theorem [Bur56] version in this context. We prove a result about the convergence under the queue operation: starting with a continuous arbitrary process satisfying some mild conditions, we show that when we pass it through a tandem network of queues, the resulting process converges weakly to a Brownian motion. This issue is proven under the assumption of independent and exponential initial workloads for all queues. This chapter is based on joint work with Inés Armendáriz and Pablo Ferrari. In Chapter 2, we study the polynuclear growth model (PNG). This is a physical model for a crystal growing layer by layer, through the random deposition of particles. For the process defined on the line, we apply a coupling technique resembling the one used in the context of discrete-valued continuous time queues by Mountford and Prabhakar [MP95], in order to prove the convergence of the model. We also obtain a local convergence result for a process that keeps track of the paths of the particles up to a given time, instead of just their positions at this time. This chapter is based on joint work with Inés Armendáriz and Pablo Ferrari. Chapter 3 is an introduction to Bandwidth-sharing networks. First, we characterize reversible birth and death processes and Whittle networks, then we study the concept of insensibility, and finally we introduce a specific model of Bandwidth-networks that we will study. In Chapter 4, we prove that the proportional fair allocation (PF) under stationary and Markovian regime shares the same large deviations asymptotics as modified proportional viii fair allocation (mPF), and hence the same as balanced fairness, due to the previous work of Massoulié [Mas07]. This is proved in two steps: we show geometric ergodicity for PF and mPF, and then we control the difference of PF and mPF processes starting from the origin, using martingales arguments. At the end, an independent proof is given for the case of monotone networks. This result solves a conjecture proposed by Massoulié [Mas07]. This chapter is based in a joint paper with Matthieu Jonckheere accepted for publication in the Mathematics of Operations Research journal. An online version is available at http://arxiv.org/abs/1207.5908 Bibliography [Bur56] P. Burke. The output of a queuing system. Operations Research, 4(6):pp. 699– 704, 1956. [HW90] M. Harrison and R. Williams. On the quasireversibility of a multiclass brownian service station. The Annals of Probability, 18(3), 1990. [Mas07] L. Massoulié. Structural properties of proportional fairness: Stability and insen- sitivity. Ann. Appl. Probab., 17(3):809–839, 2007. [MP95] T. Mountford and B. Prabhakar. On the weak convergence of departures from an infinite series of ·/M/1 queues. Ann. Appl. Probab., 5(1):121–127, 1995. Contents Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 1 A non stationary Brownian analogue to Mountford-Prabhakar’s theo- rem 3 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 A Brownian analogue to Burke’s theorem . . . . . . . . . . . . . . . . . . . 6 1.3 A non stationary Brownian analogue to Mountford-Prabhakar’s theorem . 11 1.4 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 A version of Mountford-Prabhakar’s theorem for general initial workloads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.2 The Totally Asymmetric Brownian Exclusion Process . . . . . . . . 15 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Convergence of the Polynuclear Growth Model dynamics on the line 21 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Hammersley process . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Polynuclear growth dynamics . . . . . . . . . . . . . . . . . . . . . 25 2.2 Convergence of the PNG model on the line . . . . . . . . . . . . . . . . . . 30 2.3 Hammersley reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.1 Stationary distribution under the Hammersley reflection . . . . . . 38 2.4 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.2 Multiclass version . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2 3 Reversible birth and death processes, Whittle networks, Insensibility and Bandwidth-sharing networks 41 3.1 Reversible birth and death processes . . . . . . . . . . . . . . . . . . . . . 41 3.1.1 Fixed birth rates and state dependent death rates processes . . . . 44 3.2 Whittle networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2.1 Invariant measures for Whittle networks . . . . . . . . . . . . . . . 48 3.3 Insensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.1 Residual times in renewal processes . . . . . . . . . . . . . . . . . . 50 3.3.2 Coupling construction for a processor sharing queue . . . . . . . . . 51 3.3.3 Insensitivity of processor sharing networks . . . . . . . . . . . . . . 53 3.4 Bandwidth-sharing networks. . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4.1 Some examples of bandwidth-sharing networks . . . . . . . . . . . . 56 3.4.2 The α-fairness allocations . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.3 Gradient allocations. . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4.4 Monotone networks with general service time distributions. . . . . . 60 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4 Large deviations for Proportional Fairness allocation 63 4.1 Why to calculate large deviations for Proportional fairness allocation? . . . 63 4.1.1 Insensitivity in telecommunication systems . . . . . . . . . . . . . . 63 4.1.2 The Proportional fairness election. . . . . . . . . . . . . . . . . . . 65 4.2 The Freidlin-Wentzell approach . . . . . . . . . . . . . . . . . . . . . . . . 67 4.3 Large deviations for Markovian dynamics. . . . . . . . . . . . . . . . . . . 70 4.4 Large deviations for monotone networks with general service time distri- butions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.5 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.5.1 Large deviations for discriminatory Processor Sharing . . . . . . . . 82 4.5.2 Large deviations approximations by reversible processes . . . . . . . 83 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Chapter 1 A non stationary Brownian analogue to Mountford-Prabhakar’s theorem 1.1 Introduction In 1956, Burke [Bur56] obtained one of the most fundamental results for queueing theory. The first part of Burke’s theorem states that given an arrival process Poisson with rate λ < 1, and an independent service Poisson process with rate 1, which together define a M/M/1 queue, then the departure process is again Poisson with the parameter λ. The second part of Burke’s theorem states a factorization property : the length of the queue at time t is independent of future arrivals and past departures. After [Bur56] was published, several extensions of this result have followed, such as a version of Burke’s theorem for multiclass queues with priority [MP10], another related to the Asymmetric Simple Exclusion Process [FF94], and a version applied to dual processes in inventory and queueing processes [DMO03]. A tandem queue is a system of queues where there is an arrival process A1, and a sequence {Sn}n≥1 of service processes, all independent. The system is defined recursively. The initial queue is fed from the arrival process A1, and has departures determined by the service process S1. For n ≥ 2, the arrival process for the n-th queue is defined as the departure process of the (n− 1)-th queue and the departures are determined by the service process Sn. When the initial arrival process is Poisson, Burke’s theorem allows us to treat a tandem system of queues at any fixed time as if the queues acted independently. For example, take a two nodes system of tandem queues, Q1 t and Q2 t , with arrivals Poisson(λ), λ < 1, 4 service processes Poisson(1), all independent, and sample the initial length of each queue from its stationary measure, namely a Geometric(λ) random variable. Because of the first part of Burke’s theorem, the departure process of Q1 t is a Poisson(λ) process. Moreover, due to the second part of Burke’s theorem, the departure process of the first queue prior to time t is independent of the length of the queue at time t. Then the Q2 t variable is independent from the variable Q1 t , and it follows that the invariant measure of the system is a product measure. The factorization property from Burke’s theorem has thus enabled the analysis of more complex systems, for example Jackson’s networks [Asm03]. Using similar ideas, a stationary version of a tandem queue system (a double-infinite line of queues) can be constructed and it has indeed the distribution of the holes between particles in the stationary version of the totally asymmetric simple exclusion process (TASEP) [FM06]. When the initial arrival process is not Poisson, a natural question is whether it is possible to prove convergence to the stationary distribution. Assuming an existence result, Anantharam [Ana93] proved the uniqueness of a stationary ergodic fixed point for the ·/M/K queue. Next, Mountford and Prabhakar proved the attractiveness of the Poisson distribution in the class of ergodic stationary point processes on the line with rate λ < 1 [MP95]. In order to obtain this result, they used a coloring coupling technique based on an argument of Ekhaus and Gray (unpublished, cited by [MP95]). In [OY01] some Brownian analogues of Burke’s theorem and further generalizations for geometric functionals of the Brownian Motion were introduced. The proof of some of these versions goes backs to [HW90] in the context of multiclass stations, and it relies on weak convergence arguments, or alternatively, on some properties of the Brownian Motion. One way to construct a queue is by the use of the reflective mapping : Take two Poisson processes A, S with rates λ < 1 and 1 respectively. Construct a simple random walk X by increasing 1 each time there is a mark of A, and decreasing 1 each time there is a mark of S. This random walk with negative drift is called the free process. Now, take the free process X starting at 0 given by some arbitrary non-negative integer (called the initial workload of clients) and map it to another process Q = R(X) in the following way: Q has the same jumps as X, except in case where there is a negative jump of X that would have makeQ cross below the 0 axis. In that case, the jump is ignored. See Figure 1.1. 5 t A S X t t t Q = R (X )t Figure 1.1: Construction of a queue by the reflective mapping with empty initial workload. The reflective mapping is the procedure of mapping a free function f to a non-negative valued function R(f) that follows the trajectory of f , such that a completely inelastic collision occurs at the barrier 0. This operator is very different of the absolute value operator that maps a function f to its absolute value |f |, as in this case where a completely elastic collision happens at 0. This mapping can be generalized to the setting of càdlàg functions, and we will give the formal definition and its properties in Section 1.2. The general definition is used to study properties of reflected Lévy processes, which is an entire area of study in probability, see [Asm03] for an introduction. In the case where the free function is continuous, the resulting R(f) is continuous too [Har90], and can be used to represent a storage flow system taking continuous values that increase and decrease continuously above 0. A well known example is the case when the free process is given by a Brownian motion with negative drift. In this case R(f) is the Brownian queue (also called reflected Brownian motion or regulated Brownian motion), see [Har90] for an introduction. In this work we present analogues of both Burke’s and Mountford-Prabhakar’s theo- rems, for a continuous valued queue which has a Brownian motion as the service process. We first prove a version of Burke’s theorem. This was first obtained by Harrison and Williams [HW90] in the context of Brownian networks using weak convergence. Another proof using Pitman’s Representation theorem and path properties of the Brownian 6 motion was obtained by O’Connell and Yor [OY01] (that proof was originally suggested by Harrison, as O’Connell and Yor [OY01] remark). We present here an independent and direct proof using weak convergence. It turns out to be a particular case of [HW90]. We also show that the Brownian motion is an attractor, under the Brownian queue operator dynamics, in a wide class of continuous-valued processes with a particular set of initial conditions: all the tandem queues begin with independent workloads, identically distributed as the stationary distribution of the Brownian queue, namely an exponential random variable (see [Har90]). The coloring coupling used in the discrete valued case [MP95] is no longer suitable and we introduce an ad-hoc coupling technique that takes advantage of simple path properties of the Brownian motion. This chapter is organized as follow: In Section 1.2 we introduce the reflective mapping to define the continuous queue, and prove the Brownian analogue to Burke’s theorem, in Section 1.3 we prove a version of Mountford-Prabhakar’s theorem in our context, and in the Section 1.4 we discuss some related open problems. 1.2 A Brownian analogue to Burke’s theorem In this section we introduce the queueing operation when both arrival and service pro- cesses are defined by continuous functions. Definition 1. Denote the space of real càdlàg functions f : [0,∞) → R by D[0,∞). We define the reflective Skorokhod mapping (sometimes called regulator mapping) as the operator R : D[0,∞)→ D[0,∞) given by R(f)(t) = f(t)− inf 0≤s≤t {f(s) ∧ 0}. Let us state some fundamental properties of this mapping: Lemma 1. Let R : (D[0,∞), τD)→ (D[0,∞), τD) be the reflective mapping, where τD is the Skorokhod topology. Then (a) For every function f and constant c ≥ 0, R(cf) = cR(f) (homothecy property). (b) The reflective mapping is Lipschitz continuous, with Lipschitz constant equal to 2. Proof. The proof of (a) follows by trivial verification. To prove (b), we prove first an observation about the continuity of the supremum mapping: 7 Observation 1. Let us define the supremum mapping S : (D[0,∞), τD)→ (D[0,∞), τD) by S(f)(t) := sup 0≤s≤t f(s). Then, for fixed T ≥ 0, the supremum mapping is Lipschitz continuous in the uniform topology on [0, T ] with Lipschitz constant equal to 1. Proof. To prove this observation, let f, g ∈ D[0,∞) be two functions, t ∈ [0, T ] fixed, and let us assume without loss of generality that S(f)(t) ≥ S(g)(t). Then S(f)(t)− S(g)(t) ≤ S(f)(t)− g(s) ∀ 0 ≤ s ≤ t. By definition, we know that there exist u ∈ [0, t] such that f(u) = S(f)(t). Then, for any t ∈ [0, T ] we have found u = u(t) ∈ [0, T ] such that |S(f)(t)− S(g)(t)| ≤ |f(u)− g(u)|. By taking the particular case where f and g are two different constant, we see that the bound is tight, so the observation follows. ✷ Now, note that ‖ R(f)(t)−R(g)(t) ‖[0,T ] = ‖ f(t) + sup 0≤s≤t {(−f(s)) ∨ 0} − [g(t) + sup 0≤s≤t {(−g(s)) ∨ 0}] ‖[0,T ] ≤ ‖ f(t)− g(t) ‖[0,T ] +‖ sup 0≤s≤t {(−f(s)) ∨ 0} − sup 0≤s≤t {(−g(s)) ∨ 0}]‖ [0,T ] , ≤ ‖ f(t)− g(t) ‖[0,T ] + ‖ {(−f(t)) ∨ 0} − {(−g(t)) ∨ 0} ‖[0,T ], ≤ 2 ‖ f(t)− g(t) ‖[0,T ], where the second inequality follows from the observation above and the third one holds because ‖ h+ − i+ ‖[0,T ]≤‖ h− i ‖[0,T ] for every pair h, i of continuous real functions. To see that the bound is tight, define f ≡ 0 and g := −1[ 1 3 , 1 2 ) + 1[ 1 2 ,1], both on [0, 1]. Then R(f) ≡ 0 and R(g) = (2) 1[ 1 2 ,1] so ‖ f −g ‖[0,1]= 1 and ‖ R(f)(t)−R(g)(t) ‖[0,1]= 2. The technical details concerning the extension from the continuity of this mapping in the uniform topology to the continuity in the Skorokhod topology, can be found in Whitt [Whi02], pp 439. ✷ We use the reflective mapping to define the reflection of one function on another one. 8 Definition 2. Let f, g ∈ D[0,∞) be such that f(0) > g(0). Define Ug(f) (t) = f(t)− inf 0≤s≤t { (f(s)− g(s)) ∧ 0 } , and Lf (g) (t) = g(t) + inf 0≤s≤t { (f(s)− g(s)) ∧ 0 } . In this case, Ug(f) is a function that has f as free process and g as a lower barrier, and Lf (g) is the function that has g as free process and f as an upper barrier. Note that Ug(f) ≥ f and Lf (g) ≤ g, see Figure 1.2. We immediately obtain that Ug(f) = g +R(f − g), Lf (g) = f −R(f − g). f g U (f) L (g) g f Figure 1.2: Reflection of a function on another one. We are ready to introduce the queueing operation in the context of càdlàg functions. Definition 3. Let f, g ∈ D[0,∞) be such that f(0) > g(0). We will say that f is the arrival process, g the service process, and f(0)− g(0) the initial workload of the queue. We define the queueing operator Q : D[0,∞)2 → D[0,∞) by Q(f, g) = Lf (g) = f −R(f − g), and we will call Lf (g) the departure process of the queue. Other important processes are the queue length process defined as f − Lf (g), and the free process defined as f − g. Note that due to the continuity of the reflective mapping (Lemma 1) the queueing operator is continuous. See Figure 1.3 for an illustration. 9 DS A Q A Figure 1.3: The càdlàg queue. The above definition matches the definition given by O’Connell and Yor [OY01] of the stationary version of the Brownian queue for t ≥ 0 when the initial workload f(0)− g(0) is chosen with the stationary distribution of the queue, as Norros [SN01] pointed out. As we mentioned in Section 1.1, we can represent a standard queue as the result of applying the reflective mapping to the random walk obtained as free process when we have Poisson arrival and service processes. Therefore, the reflective mapping provides a unified way to characterize a queue in both the discrete and continuous valued settings. Now we turn our attention to a similar result to Burke’s theorem, where we have Brow- nian motions as arrival and service processes. Let us denote by ⇒ the weak convergence of processes, see [Bil68] for a classical reference on this topic. We will need the following corollary of the Functional Central Limit theorem for Poisson processes. Lemma 2. Let {P n}n∈N be a sequence of Poisson processes with rate rn > 0. Suppose that rn → r ∈ (0,∞). Then P n(nt)− rn n t√ n ⇒ √r B(t), where {B(t)}t≥0 is a standard Brownian motion. Proof. Let P (t) be a Poisson process with intensity 1. Let us denote equality in law by =d. Note that {P n(t) : t ≥ 0} =d {P (rn t) : t ≥ 0}. Then, P n(nt)− n rnt√ n =d P (n rn t)− n rn t√ n = (P ((n rn) t)− (n rn) t√ n rn )√ rn. The result now follows by an application of the functional CLT. ✷ We state now the main result of this section. 10 Theorem 1. Let B1 t , B 2 t be standard Brownian motions, E an exponential variable with mean 1 c , and x a real number. Let us assume that the random elements defined are inde- pendent. Then 1. Dt = Q(B1 t +x,B 2 t +c t+x−E) has the law of a standard Brownian motion starting at x− E . 2. {Ds : 0 ≤ s < t} and Qt are independent. Proof. 1) Define λn := 1 − c√ n , so that √ n (1 − λn) = c. For each n > [c2] + 1, let An(t) be a Poisson process with parameter λn, S(t) a Poisson process with parameter 1, and Gn a Geometric random variable with parameter λn, all independent from each other. Next, let A∗ n(t) := An(nt)− ntλn√ n . Applying Lemma 2, A∗ n(t) converges weakly to a Brownian motion. We also define S∗ n(t) := S(nt)− ntλn√ n . Then S∗ n(t) = S(nt)− nt√ n + c t⇒ B(t) + c t, where B(t) is a Brownian motion, because √ n(1−λn) = c. Finally, let G∗ n := Gn√ n , so that G∗ n converges to an exponential mean 1 c random variable. Since An, Sn and Gn are independent, we conclude that (A∗ n(t) + x, S∗ n(t) + x − G∗ n) converges weakly to (B1(t) + x,B2(t) + c t + x − E), where B1 and B2 are independent standard Brownian motions and E is an exponencial random variable of mean 1 c . By the Skorokhod continuity of the queueing operator, we can apply the continuous mapping theorem (see [Whi02]) to conclude that Q(A∗ n(t)+x, S∗ n(t)+x−G∗ n) converges weakly to Q(B1(t) + x,B2(t) + c t+ x− E). On the other hand, let Dn(t) := Q(An(t), S(t)−Gn). By Burke’s theorem, Dn has the law of a Poisson process with rate λn. Define the process D∗ n(t) := Dn(nt)− n t λn√ n . 11 By Lemma 2 again, D∗ n converges weakly to an standard Brownian motion. Since D∗ n(t) = Q(An(nt), S(nt)−Gn)− n t λn√ n = Q (An(nt)− n t λn√ n , S(nt)− n t λn −Gn√ n ) = Q(A∗ n(t), S ∗ n(t)−G∗ n), by the uniqueness of the weak limit for stochastic processes, we conclude that Q(B1(t) + x,B2(t) + c t+ x− E) is equal in distribution to B(t) + c t+ x− E . 2) Define Qn as the length of the queue process constructed from the arrival An and S service processes. From Burke’s theorem, we have that {Dn(s) : 0 ≤ s < t} is independent of Qn(t). On the other hand, the queue length process Q constructed from the arrival B1(t) + x and the service B2(t) + c t+ x− E processes, has the explicit formulation Q(t) = B1(t) + x− LB1(t)+x (B 2(t) + c t+ x− E), so by an argument similar to the one applied to prove 1), we conclude that Qn converges weakly to Q and the independence of {Dn(s) : 0 ≤ s < t} and Qn(t) is inherited by D and Q(t). ✷ 1.3 A non stationary Brownian analogue to Mountford-Prabhakar’s theorem We now turn our attention towards obtaining a Brownian analogue of Mountford- Prabhakar’s theorem. We first present a monotonicity result for the reflection dynamics. Here ‖ · ‖[0,T ] denotes the supremum norm on [0, T ]. Lemma 3. Denote the space of continuous real functions by C[0,∞). Let f 1, f 2, g ∈ C[0,∞) be such that f 1(0), f 2(0) > g(0), and let Lf1(g), Lf2(g) be as in Definition 2. Then, for any T > 0, ‖ Lf1(g)− Lf2(g) ‖[0,T ]≤‖ f 1 − f 2 ‖[0,T ] . Proof. 12 We have ‖ Lf1(g)− Lf2(g) ‖[0,T ] = ‖ [gt + inf 0≤s≤t {(f 1 s − gs) ∧ 0}]− [gt + inf 0≤s≤t {(f 2 s − gs) ∧ 0}] ‖[0,T ] = ‖ sup 0≤s≤t {(gs − f 1 s ) ∨ 0} − sup 0≤s≤t {(gs − f 2 s ) ∨ 0} ‖[0,T ] . Then ‖ Lf1(g)− Lf2(g) ‖[0,T ] ≤ ‖ (gt − f 1 t ) ∨ 0− (gt − f 2 t ) ∨ 0 ‖[0,T ] ≤ ‖ f 1 − f 2 ‖[0,T ] . The first inequality follows from the Observation 1 and the second one holds because ‖ h+ − i+ ‖[0,T ]≤‖ h− i ‖[0,T ] for every pair h, i of continuous real functions. ✷ Next theorem is the main result of this chapter. Theorem 2. Let A0 be a continuous process with paths A0(·, ω) : [0,∞) → R that do not explode in finite time almost surely, and A0(0, ω) = 0. Let {W n}n∈N be a family of standard Brownian motions, {En}n∈N a family of exponential random variables with common mean 1 c , c > 0, all independent. We define recursively the sequence of processes An = Q ( An−1,W n + c t− n ∑ i=1 E i ) , n ≥ 1, where Q is the queueing operator (Definition 3). Then An + ∑n i=1 E i converges weakly to a Brownian motion. The proof relies on a coupling argument: we show that if different arrival processes are run through the same services, the resulting trajectories are eventually locally coupled. Since we know that there exists an stationary distribution under the reflecting dynamics of the tandem queues, given by the Theorem 1, we conclude the convergence result. The idea of the proof is the next: we prove that if we begin with two different arrival process, at some step of the tandem dynamics we will have positive workload during a fixed period. Then the departures will coincide with the services in such period, and since we are using the same services processes, the departures of both systems will coincide. This coupling persists in the following iterations of the reflective dynamics. Fix T > 0 and let B0 be an independent Brownian motion. Define Bn = Q ( Bn−1,W n + c t− n ∑ i=1 E i ) , ∀n ≥ 1. 13 That is, we apply the tandem queues dynamics to the process B0 using the same service processes {W n + c t}n∈N and initial workloads {En}n∈N. By Theorem 1, Bn + ∑n i=1 E i has the law of a Brownian motion for every n, so in order to get convergence it is enough to prove that the trajectories of An y Bn eventually couple on [0, T ]. We will use the following version of Borel-Cantelli’s lemma. Lemma 4. Let (Ω,F ,P) a probability space, {Fn}n∈N a filtration such that F = ⋃ n∈NFn and On ∈ Fn, n ∈ N. Then {On i.o.} = { ∑ n∈N P(On+1|Fn) =∞ } a.s.. Proof. See [Kal02]. ✷ Proof of Theorem 2. Let us first make the observation that if W n+1 t + c t− n+1 ∑ i=1 E i ≤ An t , B n t , ∀ t ∈ [0, T ], then An+1 t = Bn+1 t = W n t + c t−∑n+1 i=1 E i, for t ∈ [0, T ], and the trajectories couple. If the two queues have positive workload during a fixed period, then the departures coincide with the services for both queues and this coupling persists in the following iterations of the tandem dynamics. For n ∈ N, define the event On := {ω ∈ Ω : W n t + c t− n ∑ i=1 E i ≤ An−1 t , Bn−1 t , ∀t ∈ [0, T ] }, and the σ-algebra Fn := σ({A0, B0,W i, E i : i ≤ n}). Define for n ∈ Z+, δn :=‖ An t − Bn t ‖[0,T ]. By the observation above, On is a coupling event. And by Lemma 4 it is enough to prove that ∑∞ n=1 E(1On+1 |Fn) =∞. Since the process A0 does not explode in finite time a.s. we have that δ0 < ∞ a.s., hence: ∞ ∑ n=1 E(1On+1 |Fn) = ( ∞ ∑ k=1 1{k−1≤δ0 0. We define the sequence of random variables {Xi}i∈Z by X0 = U , Xi = Ei for i > 0 and Xi = −Ei for i < 0. Set ηi(0) = ∑i r=0X i, so that the initial configuration of particles is given by a rate λ Poisson process on the line. Let {Bi}i∈Z be a sequence of Brownian motions independent of U and {Ej}j∈Z\{0}. Next, we define a probability measure for each finite vector ((i1, t1), ..., (ik, tk)) in ( Z × [0,∞) )k . Let (j1, ..., jk) be the string consisting of the coordinates of (i1, ...., ik) arranged in non-decreasing order, and τ the permutation in the symmetric group Sk such 16 that jτ(l) = il for 1 ≤ l ≤ k. Let ηj1(t) := Bj1(t) + ∑j1 r=0Xr, and for j1 < l ≤ jk, let ηl(t) := Q(ηl−1(t), ∑l r=0Xr +Bl(t) + c t). Given times (t1, ..., tk) ∈ [0,∞)k, define ν(A1 × ...× Ak) (i1,t1),...,(ik,tk) := P(ηj1(tτ(1)) ∈ A1, ..., η jk(tτ(k)) ∈ Ajk), with P being the probability measure induced by the sequence of independent Brownian motions {Bi}i∈Z. In order to prove that these measures determine a process {ηi(t) : i ∈ Z, t ≥ 0} it is enough to check that the consistency conditions of Kolmogorov’s extension theorem are satisfied. We do this below. Let σ ∈ Sk. Note that the non-decreasing re-arrangements of (i1, ..., ik) and (iσ(1), ..., iσ(k)) are equal, and therefore, the probability measures ν(i1,t1),...,(ik,tk) and ν(iσ(1),tσ(1)),...,(iσ(k),tσ(k)) coincide. We need to verify that for ((i1, t1), ..., (ik, tk)) ∈ ( Z× [0,∞) )k , (ik+1, tk+1) ∈ Z× [0,∞) and A1, ..., Ak ∈ B(Rk) we have ν(A1, ..., Ak,R)(i1,t1),...,(ik,tk),(ik+1,tk+1) = ν(A1, ..., Ak)(i1,t1),...,(ik,tk). Let j1 ≤ ... ≤ jk ≤ jk+1 be the non-increasing reordering of i1, ..., ik+1. We need to consider two cases: when ik+1 > j1 and when ik+1 = j1. Case ik+1 > j1. Suppose ik+1 = jl, for l > 1. We set ν(A1 × ...× Ak × R)(i1,t1),...,(ik,tk),(ik+1,tk+1) = P(ηj1(tτ(1)) ∈ Aj1 , ..., η jl−1(tτ(l−1)) ∈ Ajl−1 , ηik+1(tτ(k+1)) ∈ R, ηjl+1(tτ(l+1)) ∈ Ajl+1 , ..., ηjk(tτ(k)) ∈ Ajk) = P(ηj1(tτ(1)) ∈ Aj1 , ..., η jl−1(tτ(l−1)) ∈ Ajl−1 , ηjl+1(tτ(l+1)) ∈ Ajl+1 , ..., ηjk(tτ(k))) = ν(A1 × ...× Ak)(i1,t1),...,(ik,tk) where the second equality follows from the consistency of the finite-dimensional distri- butions of the independent Brownian motions {Bj1 , ..., Bjk}, and the third equality is due to the fact that the string (i1, ..., ik) has (j1, ..., jl−1, jl+1, ..., jk) as its non-decreasing reordering. Note that this argument does not work in the case l = 1 because the processes ηi are defined in terms of ηj1 . 17 Case ik+1 = j1. In this case, due to the consistency of the finite-dimensional distributions of the inde- pendent Brownian motions, we have ν(A1, ..., Ak,R)(i1,t1),...,(ik,tk),(ik+1,tk+1) = P(ηik+1(tik+1 ) ∈ R, ηj2(tτ(2)) ∈ Aj2 , ..., η jk+1(tτ(k+1)) ∈ Ajk+1 ) = P(ηj2(tτ(2)) ∈ Aj2 , ..., η jk+1(tτ(k+1)) ∈ Ajk+1 ). By our version of Burke’s theorem 1 we know that ηj1+1 = Q ( ηj1 , j1+1 ∑ r=0 Xr +Bj1+1 + c t ) is distributed as ∑j1+1 r=0 Xr +W j1+1, where W j1+1 is a Brownian motion independent of {Bi : i > j1 + 1}. Applying this argument j2 − j1 times, we set that ηj2 has the same distribution as W j2 + ∑j2+1 r=0 Xr, where W j2 is a Brownian motion independent of {Bi : i > j2}. The result follows. ✷ By Kolmogorov’s extension theorem, we then have a process η = {ηi(t) : i ∈ Z, t ∈ R} such that the finite-dimensional distributions can be characterized as drifted Brownian motions interacting by exclusion in the front. For each fixed i, P i moves as an undrifted Brownian motion beginning at ηi(0), where {ηi(0)}i∈Z is a Poisson process on the line. We call this process the Totally Asymmetric Brownian Exclusion Process (TABEP). Some properties of the TABEP are: 1. The TABEP is selfsimilar with exponent of selfsimilarity 1 2 . 2. The Poisson process is an invariant distribution for the TABEP. The first property is inherited from the selfsimilarity of Brownian motion and the homothetic property of the reflective mapping. The second one can be obtained by weak convergence: because the product of Bernoulli random variables is invariant for the Totally Asymmetric Exclusion Process (TASEP) [Lig85], and hence the scaling of the TASEP used in the proof of Theorem 1 in different times leads to the same distribution of particles for the TABEP. 18 Finally, we define a multiclass TABEP. A Brownian motion beginning at x > 0 has probability p(x, T ) < 1 of not having hit 0 by time T > 0, for all values x and T . So for the TABEP, given a fixed interval [0, T ], there will be an infinite number of particles that do not hit the particle in front during [0, T ], and then it is possible to construct a multiclass TABEP using finite windows. Let L = {1, ..., k} the set of classes. We put ηi(t) for the position of the i-th particle and C i(t) ∈ L for its class at time t. Given a finite number of particles {ηi(t) : t ∈ [0, T ], 1 ≤ i ≤ n} such that η1 and ηn do not hit η−1 and ηn+1 respectively during [0, T ], we define the multiclass TABEP by letting the position of particles evolve as in the TABEP, and at each hitting time ηi(t) = ηi+1(t), we redefine the classes for the particles by C i(t) = min(C i(t−), Ci+1(t−)) and C i+1(t) = max(C i(t−), Ci(t−)). This dynamics defines a continuous model similar to the multiclass TASEP, see [FM07]. Some natural questions related to this model are: What is the asymptotic evolution of the multiclass TABEP? Which distributions are invariant for the multiclass TABEP? Are those distributions weak limits of the invariant distributions for the multiclass TASEP? We would be interested in taking the densitiy of particles to infinite and studying the resulting distribution of classes, in the saturated limiting model. Bibliography [Ana93] V. Anantharam. Uniqueness of stationary ergodic fixed point for a ·/M/K node. Ann. Appl. Probab., 3(1):154–172, 1993. [Asm03] S. Asmussen. Applied Probability and Queues. Springer, 2003. [Bil68] P. Billingsley. Convergence of Probability Measures. John Wiley & Sons, 1968. [Bur56] P. Burke. The output of a queuing system. Operations Research, 4(6):pp. 699–704, 1956. [DMO03] M. Draief, J. Mairesse, and N. O’Connell. Joint Burke’s theorem and RSK representation for a queue and a store. pages 69–82 (electronic), 2003. [FF94] P. A. Ferrari and L. R. G. Fontes. The net output process of a system with infinitely many queues. Ann. Appl. Probab., 4(4):1129–1144, 1994. [FM06] P. A. Ferrari and J. Martin. Multiclass processes, dual points and m/m/1 queues. Markov Processes and Related Fields, 2006. 19 [FM07] P. A. Ferrari and J. Martin. Stationary distributions of multi-type totally asymmetric exclusion processes. The Annals of Probability, 35(3):pp. 807–832, 2007. [Har90] M. Harrison. Brownian Motion and Stochastic Flow Systems. Krieger Pub Co, 1990. [HW90] M. Harrison and R. Williams. On the quasireversibility of a multiclass brownian service station. The Annals of Probability, 18(3), 1990. [Kal02] O. Kallenberg. Foundations of modern probability. Springer, 2002. [Lig85] T. Liggett. Interacting Particle Systems. Springer, 1985. [MP95] T. Mountford and B. Prabhakar. On the weak convergence of departures from an infinite series of ·/M/1 queues. Ann. Appl. Probab., 5(1):121–127, 1995. [MP10] J. Martin and B. Prabhakar. Fixed points for multiclass queues. Arxive: 1003.3024v1, 31, 2010. [OY01] N. O’Connell and M. Yor. Brownian analogues of Burke’s theorem. Stochastic Process. Appl., 96(2):285–304, 2001. [SN01] P. Salminen and I. Norros. On busy periods of the unbounded brownian storage. Queueing Systems, 39:317–333, 2001. [Whi02] W. Whitt. Stochastic Process Limits. Springer, 2002. 20 Chapter 2 Convergence of the Polynuclear Growth Model dynamics on the line In this chapter we prove the convergence of the Polynuclear growth model (PNG) dy- namics defined on the line to its stationary distribution. This chapter is organized as follows. In Section 2.1 we present an introduction to the PNG model and a related process: the Hammersley process. In Section 2.2 we prove the convergence to the stationary distribution of the PNG model. In Section 2.3 we introduce a reflection related to the PNG model, the Hammersley reflection. Finally, in Section 2.4, we present some related open problems. 2.1 Introduction We present in this section an introduction to both the Hammersley process and the PNG model and we explain how they are related. 2.1.1 Hammersley process The Hammersley process is an interacting particle system developed with the pourpose of solving a problem concerning random permutations: the Ulam’s problem. We next describe this motivation. Consider the group Sn of permutations of {1, ..., n}, where π ∈ Sn is written in the notation π = (x1, ..., xn), meaning that π(1) = x1, π(2) = x2, ..., π(n) = xn. 22 Given π ∈ Sn, let Ln = Ln(π) the length of a longest increasing subsequence of π. For instance, for the permutation (6 2 4 3 7 1 5), a maximal increasing subsequence is (2 4 7) (another one is (2 3 5)). Ulam’s problem consists in finding α(n) and c such that lim n→∞ Ln(π) α(n) = c, when the permutation π is chosen uniformly in Sn. One solution was proposed by Vershik and Kerov [VK77], and independently by Logan and Shepp [LS77], who proved that E(Ln)√ n → 2, (2.1) by means of combinatorial techniques. Another approach to the problem was proposed by Hammersley [Ham72]. Note that a random permutation of n elements can be constructed by the following procedure: Given fixed x > 0, t > 0, choose n uniform independent points in the rectangle [0, x] × [0, t]. Let x1 ≤ x2 ≤ ... ≤ xn and t1 ≤ t2 ≤ ... ≤ tn be the coordinates of these points, and pi ∈ Sn such that the points themselves are (x1, tπ(1)), ..., (xn, tπ(n)). This construction can be extended to the positive halfplane by using a space-time Poisson process N with intensity 1 in R× [0,∞). Let us call M(x, t) the number of points in [0, x]× [0, t], so that M(x, t) has distribution Poisson(xt). Consider all possible up-right paths joining (0, 0) and (x, t) going through marks of the process N , and let L(x, t) be the maximum number of marks employed by any such path. Let π be the permutation in SM(x,t) determined by these points. See Figure 2.1 for an illustration. It is easy to check that a path realizing the maximum L(x, t) corresponds to a longest increasing subsequence of π, so L(x, t) = LM(x,t)(π). Define g(t) := E[L(t, t)]. By considering paths from (0, 0) to (t + s, t + s) passing by (t, t), it can be shown that g is superadditive: that is, g(t+s) ≥ g(t)+g(s) for all s, t ≥ 0. By the subadditive ergodic thereom it follows that E[L(t, t)] t → c. This approach of studying the amount of marks attached to up-right paths is known as Last passage percolation (LPP), see [Mar06] for a review. Aldous and Diaconis [AD95] remarked that Hammersley’s solution involves an under- lying interacting particle system. Let us show how it arises. To fix ideas, let us work on 0 ≤ x ≤ X and 0 ≤ t ≤ T . Let t1 ≤ ... ≤ tM(x,t) be the second coordinates of the marks of N in [0, X] × [0, T ]. We consider a system of 23 (0,0) (x,0) (0,t) (x,t) 1 2 3 4 5 6 7 1 2 3 5 6 7 4 π = ( 6 2 4 3 7 1 5) ( 2 4 7 ) ( 2 3 5 ) M(x,t) = 7 L (x,t) = 3 Increasing subsequences: ( 2 4 5 ) ( 2 3 7 ) Figure 2.1: Last passage percolation particles with dynamics evolving as t grows. Here π is the permutation determined by the marks, defined in previous paragraph. At time 0, we begin with an empty configuration of particles, maintained till time t1. The first particle appears at time t1 at the place xπ−1(1) where (xπ−1(1), t1) ∈ N . For t1 ≤ t < t2 the configuration stays the same. At time t2, there are two possibilities: If the new mark (xπ−1(2), t2)) lies to the left of xπ−1(1), then the existing particle moves to xπ−1(2). Otherwise, a new particle appears at xπ−1(2). Given a configuration of particles at time t−k , we update the system at this time by moving the nearest existing particle at the right of xπ−1(k) to this position, if such particle exists, and otherwise we create a new particle at xπ−1(k). See Figure 2.2. This dynamics define the Hammersley process. This construction can be extended to R×[0,∞) for any initial configuration of particles, not only the empty one. Let us denote by H(·, t) the point process associated to config- uration at time t. In particular, when at time 0 we have the empty configuration then H(x, t) = L(x, t). On the other hand, if we start at time 0 with an arbitrary configuration H(·, 0), then we have H(x, t) = sup 0≤z≤x [H(z, 0) + L((z, 0), (x, t))], x, t ≥ 0, where, matching the previous definition of L(x, t), L((z, 0), (x, t)) := max{number of N −marks visited by P}, 24 (0,0) (x,t) 1 2 3 4 5 6 7 1 2 3 5 6 7 4 (x,0) 1 2 3 4 5 6 7 1 2 3 5 6 7 4 (0,t) Figure 2.2: Bijection between LPP and Hammersley process where the maximum is taken over all upright paths from (z, 0) to (x, t). Aldous and Diaconis studied some hidrodynamic limit of the Hammersley process to prove the known result of Equation 2.1 by more direct arguments that the ones given in [VK77] and [LS77]. Without any reference to LPP, we can informally describe the Hammersley process as follows: each particle at position r ∈ R waits an exponentially distributed time with rate given by the distance to the nearest particle to its left located at q < r, and then chooses a site to jump to uniformly in [q, r]. See Figure 2.3, where the graphical representation of Hammersley process is oriented in the usual way for an interacting particle system, that is not the same as in previous pictures (that corresponds to the canonical orientation in LPP). 25 t=0 t=T Figure 2.3: Graphical construction of Hammersley’s process. Aldous and Diaconis [AD95] showed that for any λ > 0, the rate λ Poisson process is an invariant measure for the Hammersley dynamics. 2.1.2 Polynuclear growth dynamics In this subsection, we introduce the Polynuclear growth model (PNG). We first we define the model formally and then we give a detailed construction in two different spaces of states: the droplet and the line. This introduction will follow closely Prahöfer and Spohn [PS00]. The PNG model is a mathematical description of a crystal growing layer by layer in a flat substrate through random deposition of particles. These particles nucleate on existing plateaus of the crystal, forming new islands. These islands spread at linear speed to their sides and, when two islands of same level meet, they coalesce. On the top of the levels, new islands emerge. The configuration of the model is codified by a height function h(x, t), (x, t), x ∈ R, t ≥ 0 the space-time coordinates. Given a nucleation event at (x0, t0), the corresponding island nucleates to increase the height to h0 = h(x0, t − 0 ) + 1. (2.2) We are also assuming that the linear speed at which islands spread is 1, and that nu- cleation events are random and independent. A nice graphic simulation is available on- line at http://www-wt.iam.uni-bonn.de/ ferrari/animations/AnimationRSK.html, in the webpage of Patrick Ferrari. 26 PNG droplet Before introducing the model, we give a definition that we will need later on in the chapter. Definition 4. For a point (x, t) ∈ R× [0,∞) we define • its light cone as V(x,t) = {(y, s) ∈ R× [0,∞) : |x− y| ≤ s− t}, • and its backward light cone as ←−V (x,t) = {(y, s) ∈ R× [0,∞) : |x− y| ≤ t− s}. Given two points X = (x, t), Y = (y, t′) in R × [0,∞), we will say that X ≤c Y in the light cone order if Y belong to VX . This defines a partial order. The PNG droplet is the PNG model under the assumption that the space where nucleation events take place is the light cone of the origin (0, 0): {(x, t) : −t ≤ x ≤ t}. This is a natural election for the PNG model: In order to determine the height h(x, t) it is enough to know the nucleation events in its backward light cone. Label those events as (xn, tn), with n ∈ N. By 2.2, let hn := h(xn, t − n ) + 1 n ∈ N. Then h(x, t) is obtained as the maximum over all hn for (xn, tn) occurring in the backward light cone: h(x, t) = max{hn : n ∈ N, |x− xn| < t− tn, }, with the rule that h(x, t) = 0 if the light cone is empty. We now describe the droplet growth starting from the initially flat substrate: A single island starts spreading from the origin and then further nucleations take place above this ground layer. In this case, h(x, t) is determined by the nucleation events inside the rectangle R(x, t) = {(x′, t′) ∈ R 2 : |x′| ≤ t′ and |x− x′| ≤ t− t′}. In light-like coordinates, u := (t′+x′) 2 , v := (t′−x′) 2 , we can write rectangle R(x, t) as [0, U ] × [0, V ] with U = (t+x) 2 , V = (t−x) 2 . The nucleation events in R(x, t) are Pois- son distributed with rate 1. We label them as (un, vn), n = 1, ..., N, with N distributed Poisson( t+x 2 · t−x 2 ), such that 0 ≤ u1 < ... < uN ≤ U . 27 (0,0) (x,t) 7 π ( 4 3 ) ( 7 5 ) = ( 6 2 4 3 7 1 5) ( 6 2 1 ) 1 2 3 4 5 6 7 1 2 3 5 6 4 Figure 2.4: PNG Droplet. Once again, if we label the v coordinates as 0 ≤ v1 ≤ ... ≤ V , the Poisson marks determine a permutation π by defining π(i) such that (ui, vπ(i)) is a mark. In order to distinguish nucleation events corresponding to different height levels, we par- tition (π(1), ..., π(N)) into decreasing subsequences according to the following procedure: for the first subsequence one starts with the first entry in the tuple and, going from left to right, one adds an entry to the subsequence if it is smaller than the last entry in this subsequence. Every used entry is marked as deleted. When the end of the tuple is reached, the first subsequence is completed. This procedure is repeated to obtain subsequences by using the undeleted entries of the original tuple. As a result, the permutation π is partitioned into decreasing subsequences. The nucle- ation events of each such subsequence are on the same height level and distinct subse- quences correspond to distinct heights. The space-time height lines, across which h(x′, t′) increases by one unit, are then constructed by connecting the nucleation events belonging to the same subsequence by a zigzag line, as depicted in Figure 2.4. In this example we have the permutation (6, 2, 4, 3, 7, 1, 5). The decreasing sub- sequences are (6, 2, 1), (4, 3), (7, 5). They define three height lines. For an arbitrary permutation π, h(x, t) equals the number of decreasing subsequences, which is precisely the length, l, of the longest increasing subsequence of π. To see this, take any increasing 28 subsequence of π. By construction every element of this subsequence belongs to a different height line. Then l ≤ h(x, t). The reverse inequality is obtained by noticing that a nucleation event (ui, vπ(i)) at level k+1 is necessarily situated in the forward light cone of at least one nucleation event (uj, vπ(j)) at level k, i.e. i > j and π(i) > π(j). We call (uj, vπ(j)) a predecessor of (ui, vπ(i)). Since there is at least one nucleation event in level h(x, t), successive selections of predecessors in consecutive levels result in an increasing subsequence of length h(x, t), therefore l ≥ h(x, t). Notice that this mapping corresponds to the one defined in Subsection 2.1.1: the paths of particles in the Hammersley process are exactly the space-time step lines of the PNG model, after performing a 45◦ rotation. This remark, first made by Prähofer and Spohn [PS00], establishes a connection between the two models. Figure 2.5 illustrates the map- ping. The PNG droplet is a growth model in the KPZ class, for an introduction to the relationship of this PNG model with the KPZ equation and the Tracy-Widom distribution see [PS00]. PNG on the line In this subsection we extend the definition of the PNG model in the droplet to a halfplane. The initial configuration on R is given by a signed point process A = {ai = (pos(ai), sign(ai))}i∈Z, such that (pos(ai), sign(ai)) ∈ R × {−1, 1}. There is also a rate 2 Poisson process N on R × [0,∞) (space-time). The marks of this process N are the nucleations events. Each particle ai moves at constant speed sign(ai), so position pos(ai) is changing at linear rate. At a given nucleation event (x0, t0) ∈ N , two new particles are generated simultaneously at the place x0: one travelling with speed +1 and the other with speed −1. In the instant where a particle with speed 1 hits another particle (of speed −1) both of them are annihilated whether these particles were part of the initial configuration or not. See Figure 2.6. By performing a 45o rotation, we may obtain a stationary version of the PNG process from a stationary version of Hammersley process in the plane. If we tag the particles in the Hammserley process, after the rotation, we obtain the lines of the PNG model (see Figure 2.5 in last subsection). Prähofer and Spohn proved in [PS04] that if A+ = {ai : sign(ai) = +1} and A− = {ai : sign(ai) = −1} are independent Poisson processes with intensity ρ+ and ρ− respectively, such that ρ+ρ− = 1, and we apply the PNG dynamics then, at any given time t, the set of alive particles A(t) = A+(t) ∪ A−(t) is distributed 29 t=0 t=T t=-T 1 2 3 4 5 6 t=0 t=-T t=T 3 3 3 3 3 3 3 3 34 4 4 4 4 5+ _ ___ _ _ _ _ _ + + + ++ Figure 2.5: Relationship between Hammersley and PNG processes. 30 t=0 t=T +++ + + +++ Figure 2.6: PNG model defined in the line. as the initial equally to A (with the same parameters as A+, A−). That is, the sum of two independent Poisson processes is invariant under the PNG dynamics. Notice that the distribution of this sum of Poisson processes is the law of the jump times of a biased simple random walk on the line which jumps one unit upwards at rate ρ+ and one unit downwards at rate ρ−. We will call to this law of a signed point process as the ring bells of a (simple) random walk with parameters ρ+ and ρ−, for simplicity. 2.2 Convergence of the PNG model on the line In this section we prove that any initial distribution converges undo the PNG dynamics to the stationary distribution. We apply a coupling technique similar to the one used by Mountford and Prabhakar [MP95] to prove that the · \M \1 queueing operator dynamics is convergent. Assume we start with two different configurations of a signed point process: a process A, distributed as the ring bells of a random walk with parameters ρ+, ρ− (ρ+ρ− = 1), and an independent ergodic marked point process E = E+ ∪ E− with the same rates. We will couple these processes by using a rate 2 Poisson process N to define the PNG dynamics. We thus obtain two signed processes At and Et, t ≥ 0. We will prove that as t grows to infinity the density of particles in At △ Et goes to 0. In other words, Theorem 4. Let E be a signed ergodic process on the line with rates ρ+, ρ− for + and − marks, such that ρ+ρ− = 1. Define Et as the signed process with initial configuration E obtained by running the PNG dynamics. Then Et converges weakly to the ring bells of a random walk with parameters ρ+ and ρ−. 31 First, we explain briefly the coloured coupling that we will use. At time 0 we define red particles as R = A+ ∪ E−, and blue particles as B = A− ∪ E+. The sign of each particle is conserved, so at time 0 we have two signed processes: the red one R = R+ ∪ R− and the blue one B = B+ ∪B−. Particles generated by nucleation events are yellow particles Yt = Y + t ∪ Y − t . The colours will represent the discrepancies between configurations At and Et, for each time t. We need to define some dynamics between coloured particles and describe the relationship between the coloured dynamics and the original processes At and Et. Each coloured particle moves with a speed equal to its sign. If a particle hits another particle of the same colour, nothing happens and both particles continue their paths (they cross each other). If a red particle hits a blue particle, both of them are annihilated. If a red or blue particle hits a yellow one, the yellow particle is annihilated and the red or blue changes its sign. If two yellow particles collide they annihilate each other. See Figure 2.7. It is easy to check that for each t ≥ 0, A+ t = R+ t , A − t = B− t and E+ t = B+ t , E − t = R− t , so the technique of coloured particles is just a handy way of seeing the particles. Notice that there is no creation of red or blue particles, only annihilation. The coupling of two particles from A and E corresponds to the annihilation of particles in R and B. So we must prove that the red and blue particles disappear as t goes to infinity in the coloured dynamics. Let us first show that space ergodicity is preserved under the dynamics. Lemma 5. Rt, Bt and Yt are ergodic for every 0 ≤ t <∞. Proof. Let us denote by Nt the restriction of N to R× [0, t]. For a fixed time t, we have that Rt = ft(A +, A−, E+, E−,Nt), where ft is a deterministic function. Note that the space shift-operation commutes with ft: If we denote by τc the space shift by c units, τc(x) := x+ c, we have that τc(Rt) = ft(τc(A +), τc(A −), τc(E +), τc(E −), τc(Nt)). Hence, the shift invariance of Rt is a consequence of the shift invariance of processes A+, A−, E+, E−,Nt. 32 t=0 t=T +++ + t=0 t=T +++ ++ + + + + + + + Figure 2.7: A simultaneous realization of two configurations using the same spatial marks and its colouring. 33 Since {(A+, A−), (E+, E−),Nt} is a family of independent ergodic processes, (A+, A−, E+, E−,Nt) is a jointly ergodic process. Since any shift-invariant function of Rt is a shift-invariant function of (A+, A−, E+, E−,Nt), it follows that the process Rt is ergodic. A similar argument works for the processes Bt and Yt. ✷ Proof of Theorem 4: The proof will proceed by contradiction. Let us assume that R and B never annihilate each other, so that the density of red particles which are never annihilated is a posi- tive random variable, denoted by dR(∞, ω). Such non-annihilating particles that never annihilate will be called ever-red and ever-blue particles, and denoted by ER and EB. By Lemma 5, the density of red particles at a fixed time t > 0, dR(t, ω), is deterministic: dR(t, ω) = dR(t) a.s.. By definition, dR(t, ω) is a non-increasing function of t, so we have that dR(∞, ω) = lim t→∞ dR(t, ω) = lim t→∞ dR(t) =: dER a.s., where the limit exists by the monotonicity and boundedness of {dR(t)}. Since red and blue particles cannot cross paths it is possible to define an order between ever-red and ever-blue particles. Procedure 1. We tag the particles to indicate an order. At time 0, the first red ever-red particle to the right of the origin will have tag 0, let us call x the position of that particle. Let lx be the nearest ever-blue particle to the left of x, and rx the nearest ever-blue particle to the right of x. All the ever-red particles in (x − pos(lx), x + pos(rx)) will have tag 0. Now, we tag the blue particle in pos(rx) as 1, and look for its nearest ever-red particle to the right which will have tag 2. The ever-blue particle lx will have tag −1 and the nearest ever-red particle to its left will have tag −2. All ever-blue particles between particles with tag 1 and 2 will have tag 1, and all ever-blue particles between particles with tags −1 and −2 will have tag −1. We do this inductively, with the result that ever-red particles get even tags, ever-blue particles get odd tags and the order between particles with different tags is preserved through the dynamics. See Figure 2.8. 34 2-2 0 1 3-3-4 1 2-1-2-2 -1 0 Figure 2.8: Relative order of ever-red and ever-blue particles. We will need the following lemmas that state some basic facts about ergodic process on the line. Lemma 6. Let A be an ergodic point process in the line with density 0 < dA <∞. 1. For c > 0, let Ā an ergodic subset of A with positive density dĀ. Let Āc := {a ∈ Ā : (pos(a)− c, pos(a) + c) ∩ A = {a} } Then dĀc ր dĀ as c goes to 0. 2. Let B be another ergodic process on the line with the same density dA. Tag the particles of A and B as we did in Procedure 1. Let à be an ergodic subset of A with positive density. For c > 0, let Ãc := {a ∈ à : ∃u ∈ à with pos(u) ∈ (pos(a), pos(a)+c) such that tag(u) > tag(a)}. Then dÃc ր dÃ, as c goes to ∞. Proof. 1. Note that 0 < c1 < c2 implies Āc2 ⊆ Āc1 . For m ≥ 1, i ∈ Z define Xi := #[i, i+ 1) ∩ Ā, Xm i := #[i, i+ 1) ∩ Ā 1 m . Note that Xm i ր Xi almost surely, because an ergodic point process with finite density does not have accumulation points. On the other hand, by the ergodic theorem, we have that dĀ 1 m = E(Xm 1 ), and then lim m→∞ dĀ 1 m = lim m→∞ E(Xm 1 ) = E( lim m→∞ Xm 1 ) = E(X1) = dĀ where the interchanging of limits is justified by the monotone convergence theorem, as Xm i ր Xi a.s. and dĀ <∞. 35 2. Once again, we take advantage of a monotonicity property: the inequality 0 < c1 < c2 implies Āc1 ⊆ Āc2 . For m ≥ 1, i ∈ Z define Xi := #[i, i+ 1) ∩ Ā Xm i := #[i, i+ 1) ∩ Ām. The process B has positive density so Xm i ր Xi almost surely. Since dĀ < ∞, by the ergodic theorem we get lim m→∞ dĀm = lim m→∞ E(Xm 1 ) = E( lim m→∞ Xm 1 ) = E(X1) = dĀ. ✷ Lemma 7. For all t ≥ 0, there exists δ > 0 such that following set has density larger than δ: Ct = { r ∈ ER : ∃u ∈ ER with pos(u) ∈ (pos(r), pos(r) + c1), tag(u) > tag(r), #Rt ∩ (pos(r)− c2, pos(r) + c2) = #Rt ∩ (pos(u)− c2, pos(u) + c2) = 1 } for some 0 < c2 < c1, where all these constants do not depend on t. Proof. Fix t > 0. By Lemma 6,1), we can choose c2 > 0 small enough such that the set Bt = { r ∈ ER : #Rt ∩ (pos(r)− c2, pos(r) + c2) = 1 } has density bigger than dER 2 . Then using Lemma 6,2), we can choose c1 > c2 big enough such that the set Ct = { r ∈ Bt : ∃u ∈ Bt, with pos(u) ∈ (pos(r), pos(r) + c1) such that tag(u) > tag(r) } has density bigger than dens(Bt) 2 > dER 4 . Let δ := dER 4 , and we are done. ✷ We are now ready to finish the proof of Theorem 4. We will show that if dR(t) > ǫ for all t ≥ 0, then there exist ∆ > 0 andK > 0, independent of t, such that dR(t)−dR(t+∆) > K. Fix t > 0. By Lemma 7 we know that Ct = { r ∈ ER : ∃u ∈ ER with pos(u) ∈ (pos(r), pos(r) + c1), tag(u) > tag(r), #Rt ∩ (pos(r)− c2, pos(r) + c2) = #Rt ∩ (pos(u)− c2, pos(u) + c2) = 1 } 36 has density larger than δ > 0, for some 0 < c2 < c1. Since Rt, Bt and Yt are ergodic point processes with finite density, for every r ∈ Ct there is a finite number of yellow particles in the interval (r, r + c1). For k ≥ 0, let Ckt := { r ∈ ER : ∃u ∈ ER with pos(u) ∈ (pos(r), pos(r) + c1), tag(u) > tag(r), #Rt ∩ (pos(r)− c2, pos(r) + c2) = #Rt ∩ (pos(u)− c2, pos(u) + c2) = 1, #Yt ∩ (pos(r), pos(r) + c1) ≤ k } . By the same argument used in the proof of Lemma 6, dens(Ckt ) ր dens(Ct) as k ր ∞, and we can choose k large enough so that Ckt has density bigger than δ 2 . Let r1 ∈ Ckt . We know that there exists at least one red particle r2 in (pos(r1), pos(r1)+ c1), such that R∩(pos(r2)−c2, pos(r2)+c2) = {r2} and pos(r2) = pos(r1)+d, with d ≤ c1, we fix such red particle r2. Hence, there are no other red particles in (pos(r1)−c2, pos(r1)+ c2), neither in (pos(r2) − c2, pos(r2) + c2). Define the event Er1 , by the simultaneous occurrence of the following events (see Figure 2.9): • In the isosceles triangle △L with base (pos(r1)− c2, pos(r1)) (at time t) and height on the time interval (t, t+ c2 2 ) there are exactly k+ 1 marks of N , and these marks are completely ordered in the light cone order (recall Definition 4 in the Subsection 2.1.2 ). • In the isosceles triangle △R with base (pos(r2), pos(r2) + c2) (at time t) and height on the time interval (t, t+ c2 2 ) there are exactly k+ 1 marks of N , and these marks are completely ordered in the light cone order. • Let denote by △C the isosceles triangle with base (pos(r1) − c2, pos(r2) + c2) (at time t) and height on the time interval (t, t + d+2c2 2 ). Then, there are no marks of N on △C \ (△L ∪△R). The third event has probability bounded by below by e− (c1+2c2) 2 4 while the first and the second ones have some positive probability depending only on c2, and they are all independent events depending only on location of the marks of N . Hence Er1 has some positive probability P(Er1) ≥ p(c1, c2) > 0, provided that r1 ∈ Ckt . Let us show that if r1 ∈ Ckt and Er1 occurs, there is a collision of a red and a blue particle. For instance, assume that there are no red particles in the configuration at time t in the interval (pos(r1), pos(r2)). Inside △C \ (△L∪△R) there are no marks, so the only 37 △△ △ L R C ∅ t t+ d 2 ____2c2+ pos(r1) pos(r2) I I I I I I c2 c2 c1 I I I t+ 2 ____2c d Figure 2.9: Event of coupling Er. particles that could interact with the red particles r1 and r2 and the blue particles between them, are the yellow particles that were already present at time t. Since there are at most k of these particles, we have at most k changes of direction for each red particle. Now, because triangles △L and △R contain k+ 1 marks each, and the particles yellow thereby created cannot interact (because they are ordered), every time one of the red particles r1 or r2 goes in the wrong direction (defined as the direction that increases distance between them), it eventually meets a yellow mark that corrects the direction. Note that we choose k + 1 instead of k in the definition of Er1 because the red particles r1, r2 could initially have the wrong directions. Then, in the absence of blue particles, particle r1 and r2 would have met before time t + d+2c2 2 . But we made sure there is at least one blue particle in between that annihilates one of the red particles before that time, see Figure 2.9. If we have more red particles in (pos(r1), pos(r2)), the statement still holds. Since the yel- low marks in △L and △R has bigger cardinality that all the particles in [pos(r1), pos(r2)], by the same argument all red particles will be trapped in △C (possible changing relative positions). By the existence of a blue particle, one red particle will be annihilated before time t+ d+2c2 2 . We hence arrive at the contradiction dR(t)− dR ( t+ d+ 2c2 2 ) ≥ δ 2 p(c1, c2) = K > 0, ∀t > 0 where the constant K does not depend on t. ✷ 38 2.3 Hammersley reflection In this section, we prove some extension of Theorem 4. We first define a new reflection operator, closely related to the particle paths in the Hammersley process, find its invariant measure and finally show some local convergence result. Definition 5. Let f : R→ R be a continuous function. Let N be a rate 2 Poisson process on A = {(x, t) ∈ R× R : t ≤ f(x)}. Define R = ⋃ ω∈N :Vω⊆A Vω, where Vω is the (forward) light cone of ω, (Definition 4). We define the Hammersley reflection of f as the boundary set ∂R, that can be parametrized as a real continuous function, and we denote that function by R(f), see Figure 2.10. f R(f) (x,t) (x,t+s) (x+y,t) (x+y,t+s) Figure 2.10: Hammersley reflection of a function f . 2.3.1 Stationary distribution under the Hammersley reflection A natural question is whether there exists an invariant distribution under this operation. That is, we look for a processX such that the increments of the reflected process R(X) are distributed as the increments of X. This is indeed the case, it follows from the following result proven by P. A. Ferrari [Fer96] (Theorem 10.2) stated for the continuous time, discrete state space Hammersley process, but the scaling used in the proof of Theorem 1 gives us the result for the continuous state space version (as already noted in [Fer96]). 39 Theorem 5. Let H be a stationary Hammersley process, with rate 1 marks N on R×[0, t) and initial distribution of particles Poisson(λ), λ > 0. Then the trajectory of a tagged particle Xx(·), Xx(0) = x, is compound Poisson, that is: Xx(t) =d x+ Nt ∑ i=1 Ei, Nt is a rate 1 Poisson process in R independent of the sequence of exponential(λ) {Ei}∞i=1 i.i.d. random variables. In the stationary regime, we can picture the paths of two neighbouring particles in the Hammersley process as the 45o rotation of a function f . This would be the trajectory of the leftmost particle, and the 45o rotation of its reflection R(f), associated to the trajectory of the rightmost particle of the pair. We can thus obtain the invariant distribution of the Hammersley reflection from Theorem 5. Corollary 1. An invariant distribution for the increments of a process, under the Ham- mersley reflection, is given by the increments of a process Y with a path given by a particle travelling at speed +1 or −1, and switching between these speeds at independent exponential( √ 2) intervals. 2.4 Open problems 2.4.1 Scaling In the stationary version of the Hammersley process, each particle follows a compound Poisson path. By scaling time and space (Euler scaling) we will obtain a surface, presum- ably a Brownian sheet. How can the convergence result of the Hammersley reflection can be translated to the dynamics of the scaled version of the process? 2.4.2 Multiclass version In [Fer04] P.L. Ferrari constructed a multi-layer version of the PNG model and analyzed asymptotics by considering an initial condition given by a flat substrate. This multi-layer PNG model is an analogue of the multi-line process for the Hammersley process and can be defined for arbitrary initial conditions. By the results of P.A. Ferrari and J. Martin [FM09], we know that the multi-line dynamics is isomorphic to the multiclass dynamics, so we would expect a similar relation for the multiclass PNG model. Is it possible to compute the stationary distribution for this multiclass version of the PNG model? 40 Bibliography [AD95] D. Aldous and P. Diaconis. Hammersley’s interacting particle process and longest increasing subsequences. Probab. Th. Rel. Fields, 103:199–213, 1995. [Fer96] P. A. Ferrari. Limit theorems for tagged particles. Markov Process. Related Fields, 2(1):17–40, 1996. [Fer04] P. L. Ferrari. Polynuclear growth on a flat substrate and edge scaling of goe eigenvalues. Communications in Mathematical Physics, 252(1-3):77–109, 2004. [FM09] P. A. Ferrari and J. Martin. Multiclass Hammersley-Aldous-Diaconis pro- cess and multiclass-customer queues. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):250–265, 2009. [Ham72] J. M. Hammersley. A few seedlings of research. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. Califor- nia, Berkeley, Calif., 1970/1971), Vol. I: Theory of statistics, pages 345–394. Univ. California Press, 1972. [LS77] B.F Logan and L.A Shepp. A variational problem for random young tableaux. Advances in Mathematics, 26(2):206 – 222, 1977. [Mar06] J. Martin. Last-passage percolation with general weight distribution. Markov Process. Related Fields, 12(2):273–299, 2006. [MP95] T. Mountford and B. Prabhakar. On the weak convergence of departures from an infinite series of ·/M/1 queues. Ann. Appl. Probab., 5(1):121–127, 1995. [PS00] M. Prähofer and H. Spohn. Statistical self-similarity of one-dimensional growth processes. Phys. A, 279(1-4):342–352, 2000. Statistical mechanics: from rigorous results to applications. [PS04] M. Prähofer and H. Spohn. Exact scaling functions for one-dimensional station- ary kpz growth. Journal of Statistical Physics, 115(1-2):255 – 279, 2004. [VK77] A.M. Vershik and S.V. Kerov. Asymptotics of the plancherel measure of the symmetric group and the limiting form of young tables. Soviet Math. Dokl., 18:527–531, 1977. Chapter 3 Reversible birth and death processes, Whittle networks, Insensibility and Bandwidth-sharing networks This chapter gives some preliminaries on stochastic networks and then introduces the mathematical definition of a bandwidth-sharing network. In Section 3.1 we give classical results about reversible birth and death processes on R N . This allows us to introduce the notion of a Whittle network and characterize its stationary measure in Section 3.2. After that, in Section 3.3, we study the concept of insensitivity in processor sharing queues and Whittle networks relating the stationary distribution of Markovian and non-Markovian models. Finally, in Section 3.4, we introduce the bandwidth-sharing network mathematical model, and we give some toy examples and commonly used specific models. We use some content of Jonckheere [Jon10]. 3.1 Reversible birth and death processes In this section we give a brief review of some results about birth and death processes on Z N + concerning reversibility and stationary distributions. Definition 6. Let X a state dependent birth and death process on Z N + with jump rates {q(x, y)}. We say that X is reversible if there exists a distribution π such that π(x)q(x, y) = π(y)q(y, x), ∀x, y ∈ Z N + . (3.1) Equation (3.1) is usually known as detailed balance equations. Note that if π is reversible with respect to the process X, then π is stationary for X. 42 This definition of reversibility corresponds indeed to the idea of a process being re- versible in time, that is, to have the same distribution for dynamics forwards or backwards in time: Theorem 6. Fix a time τ > 0 and consider the reverse time process Xτ t := Xτ−t. Then X is reversible if and only if Xτ t is ergodic and (Xτ−t1 , ..., Xτ−tn) = d (Xt1 , ..., Xtn), for all time sequences t1, ..., tn. This is a very classic result whose proof can be consulted in [Asm03], for instance. ✷ Now we derive a criterion for a process to be reversible depending only on its transition rates. This allows us to check if a process is reversible without calculating explicitly the stationary distribution. Theorem 7 (Kolmogorov criterion). The following statements are equivalent: 1. There exists a positive distribution π satisfying detailed balance equations (3.1) for the transition rates q. 2. For all x0, ..., xn ∈ Z N + with x0 = xn, we have that n ∏ i=1 q(xi−1, xi) = n ∏ i=1 q(xi, xi−1). (3.2) 3. For each path x0, x1, . . . , xn ∈ Z N + , such that xi communicates with xi+1 for all i, the quantity (defined for non-zero transitions) ∏n i=1 q(xi−1, xi) ∏n i=1 q(xi, xi−1) depends only on x0 and xn. Proof. [Kel79] We prove first that (1) implies (3.2). Since there exists π which satisfy Equations (3.1), we have that ∏n i=1 q(xi−1, xi)π(xi−1) = ∏n i=1 π(xi)q(xi, xi−1). Since x0 = xn, we can 43 cancel the π factors of both sides and we are done. For the rest of the proof, we do the following: Let γ = x0, ..., xn be a path with no zero transitions and define the quantity: Iγ(q) = ∏n i=1 q(xi−1, xi) ∏n i=1 q(xi, xi−1) . Note that this functional satisfies that • For two paths γ = x0, ..., xn, τ = xn, xn+1, ..., xn+k, and the composition path τ γ = x0, ..., xn+k, we have that Iτ γ(q) = Iγ(q)Iτ (q). • Given a path γ = x0, ..., xn define the inverse path γ−1 = xn, ..., x0. Then Iγ−1(q) = [Iγ(q)] −1. • For two different transitions q1, q2, it happens that Iγ(q1q2) = Iγ(q1)Iγ(q2). So, Theorem 7 is indeed a version of Morera’s vectorial calculus theorem: For a continuous function defined on a simply connected domain, it is equivalent to have integral equal to zero over any closed curve or that the value of the integral over any curve only depends on the integration limit points. We include the proof for completeness. We prove now that (2) implies (3). Let γ = x0, x1, ..., xn−1, xn, and τ = x0, y1, ..., yn−1, xn be two paths. Then by (2), for the closed curve τ−1γ we have 1 = Iτ−1γ(q) = Iτ−1(q)Iγ(q) = [Iτ (q)] −1Iγ(q), so in this case Iγ(q) depends only on x0 and xn. Let us check that (3) implies (2). For a closed curve C = x0, x1, ..., xn, xn = x0, let l be an index such that xl 6= x0. Define γ = x0, ..., xl and τ = xl, ..., xn. Then IC(q) = Iτ γ(q) = Iτ (q)Iγ(q) = Iγ−1(q)Iγ(q) = [Iγ(q)] −1Iγ(q) = 1, where the third equality is due to the assumption (3). Finally we prove that (3) implies (1). Fix x0 ∈ Z N + and define a measure π by π(x0) = 1, (3.3) π(x) = Ixx0 (q) x ∈ Z N + \ x0. (3.4) 44 Note that π satisfies (3.2), since Ixx0 (q) q(x, y) q(y, x) = Iyx0 (q) by choosing as representant to calculate Ixx0 some path from x0 to x, and for Iyx0 the same path plus the jump from x to y. ✷ Last part of the proof of Theorem 7, allow us to express easily the stationary measure of a reversible process in terms of its transitions. Theorem 8. If there exists a positive measure π satisfying the detailed balance equations (3.1) for q, an invariant measure is given by: π(x0) = 1 (3.5) π(x) = n ∏ i=1 q(xi−1, xi) q(xi, xi−1) , x ∈ Z N + \ x0, xn = x (3.6) ✷ 3.1.1 Fixed birth rates and state dependent death rates pro- cesses The steady analysis of many queuing networks boils down to find the stationary measure of some associated multidimensional birth and death process. In our case, we are interested in processes with fixed birth rates and state dependent death rates: q(x, x+ ei) = λi, i = 1, . . . , N, q(x, x− ei) = φi(x), i = 1, . . . , N. We can characterize the reversibility of these processes in terms of a function called the balance function. We use this function many times in the sequel. Proposition 1. The following statements are equivalent: 1. There exists π solution of the detailed balance equations (3.1). 2. The transitions φi(x) verify φi(x)φj(x− ei) = φj(x)φi(x− ej), ∀ i, j ∈ {1, . . . , N}, x ∈ Z N + . (3.7) 45 3. There exists a strictly positive function Φ, the balance function, such that the transitions φi(x) write φi(x) = Φ(x− ei) Φ(x) , ∀ i ∈ {1, . . . , N}, x ∈ Z N + . (3.8) Proof. First, note that (2) is equivalent to equations (3.2), and then equivalent to (1). If we choose the path x, x− ei, x− ei− ej, equation (3.2) is exactly (2), after cancelling λi and λj from both sides. And, for any path, we can derive (3.2) by applying (2) recursively and multiplying by the corresponding λ’s. We prove now that (2) and (3) are equivalent. Let x, x− ein , . . . , x− ein − ein−1 . . . x− ei2 , x − ein − ein−1 . . . x − ei1 = 0 be a direct path from state x to state 0, i.e., a path of length n, where n = ∑N i=1 xi. Then, property (2) implies that the expression Φ(x) := 1 φi1(x)φi2(x− ei1) . . . φin(x− ein−1 . . .− ei1) , (3.9) is independent of the considered direct path. In particular, the rates are uniquely characterized by the function Φ, and it satisfies (3.8). Conversely, if there exists a function Φ such that the rates φi(x) satisfy (3.8), it can be easily verified that these rates are balanced. ✷ We have an equivalent analytic characterization of such type of processes being re- versible. This is an analogue of the vectorial calculus result that states that a continuous function defined on a simply connected domain has antiderivative, if and only if, its inte- gral over any closed curve is zero. Definition 7. We say that a fixed birth rates and state dependent death rates process is discrete gradient if there exists a function P̃ : RN → R (called the discrete potential) such that for all x ∈ N N : log(φ(x)) = DP̃ (x) := (P̃ (x)− P̃ (x− ei))i=1,...,N . (3.10) Proposition 2. A fixed birth rates and state dependent death rates process is reversible if and only if it is discrete gradient. 46 Proof. Define the discrete potential P̃ as P̃ (x) := − log Φ(x), ∀x ∈ Z N + , (3.11) where Φ(x) is the balance function. Then the multiplicative property for the balance function (3.8) is transfered into the additive property for the discrete gradient (3.10). ✷ As a corollary of Theorem 8 and Equation 3.11, we can express the stationary measure of the process in terms of its potential. As a consequence, we are able to characterize the large deviations behavior of the stationary measure, in the case where the potential scales adequally: Corollary 2. The process X̃ associated with a reversible allocation with discrete potential P̃ is reversible (in the usual sense) and its stationary measure (when it exists) is: π(x) = Cλx exp(−P̃ (x)). Assume further that 1 n P̃ (nx)→ γ(x) as n→∞. Then lim n→∞ 1 n log π(nx) = − ( γ(x)− N ∑ i=1 xi log(λi) ) . ✷ 3.2 Whittle networks In this section we give the define processor sharing queues and processor sharing networks. After that, we study the important particular case of reversible processor sharing networks: the Whittle networks. We use results from Section 3.1 to characterize its stationary distribution. A processor sharing queue is a queue where the service capacity is equally shared be- tween all the clients present in a given time. If Q(t) denotes the number of clients and c(t) the capacity, at time t, hence any client is served at time t with a service rate c(t) Q(t) . We extend this notion to a network. Let us consider here an open queuing network of N nodes with routing of clients inside the network. At any node i, there are exogenous arrivals as a Poisson process of intensity νi. In all the following, we will focus on the process X(t) = (x1(t), ..., xN(t)) representing the number of clients at each node of a network. 47 Definition 8 (Processor-sharing networks). We call processor-sharing network to a net- work of processor-sharing nodes with state-dependent capacities. The dynamics of a pro- cessor sharing network with exponential service requirements can be characterized by the following principles: • Customer arrive to node j at rate νj. • Whenever the network is in state x, the time to the next movement of a single unit from node i to node j is exponentially distributed with rate pijφi(x) (pij represents the routing probability from node i to node j while φi(x) represents the capacity of the network at node i). • At node i, customers require exponential services of rate φi(x). After service com- pletation at node i, a costumer is routed to node j with probability pij and leaves the network with probability pi := 1−∑j 6=i pij. • The transition rates of the number of customers or units at each node are then given by: q(x, y) =          pjkφj(x) if y = x− ej + ek pjφj(x) if y = x− ej νj if y = x+ ej 0 otherwise Definition 9 (Whittle network). A Whittle network is a processor sharing network X (Definition 8) with the balance property: φi(x)φj(x− ei) = φj(x)φi(x− ej), i, j = 1, . . . , N, xi > 0, xj > 0. (3.12) We assume moreover that φi(x) > 0 if and only if xi > 0. The balance property is directly linked to the reversibility of the process representing the number of customers in the network (see Proposition 1). These networks are somehow the most general instances of tractable multiclass networks as the capacity (or speed) φi of node i may depend on the whole state of the system x = (x1, . . . , xN), where xi is the number of customers at node i. The particular case of networks where the service rate at each node depends only of the number of clients at this node, are called Jackson networks. We will relax the assumption of exponential services. An important property will arise for Whittle networks: if we have non-exponential services at each node but all other char- acteristics are preserved we will obtain the same stationary measure as in the exponential case. 48 3.2.1 Invariant measures for Whittle networks For simplicity, we focus thereafter on the case of open networks, that is, networks where every customer eventually leaves the system. However, this assumption is not necessary and the same analysis can be extended for closed or mixed networks. Theorem 9 (Invariant measure). Let X be an open Whittle network. Then its invariant measure is given by π(x) = Φ(x) N ∏ i=1 ρxi i , (3.13) where Φ is the balance function of the network. The effective arrival rate λi at node i is uniquely defined by the traffic equations: λi = νi + ∑ j 6=i λjpji, i = 1, . . . , N, and ρi = λi/µi, the traffic intensity at node i. Theorem 10. Let X be an open Whittle network. Define another Markov jump process X̃, called the adjoint process, by the following transitions: x 7→ x+ ei at rate λi, x 7→ x− ei at rate φi(x)1(xi > 0), The process X̃ is reversible and has the same stationary measure as X. Proof. We prove both theorems simultaneously. It follows from the results on Section 3.1, that the adjoint process X̃ is reversible. Hence its stationary measure, π, is given by Theorem 8. Then it is enough to verify the global balance equations for the original process X using the measure π. That is, to verify that for every x ∈ Z N + it happens ∑ j π(x− ej)νj + ∑ j π(x+ ej)pjφj(x+ ej) + ∑ j 6=k ∑ k π(x+ ej − ek)pjkφj(x+ ej − ek) = ∑ j π(x)νj + ∑ j π(x)pjφj(x) + ∑ j 6=k ∑ k π(x)pjkφj(x). (3.14) Let us call A1, A2, A3 the ordered summands in the lefthand side of 3.14, and B1, B2, B3 the ordered summands in the righthand side of 3.14. By the balance equations for X̃, we have λj π(x) = π(x+ ej)φj(x+ ej), (3.15) 49 which leads to ∑ j φj(x)π(x) = ∑ j π(x− ej)λj, = ∑ j π(x− ej) ( νj + ∑ k 6=j pkjλk ) , = ∑ j π(x− ej)νj + ∑ j ∑ k 6=j pkjφ(x− ej + ek)π(x− ej + ek). Since pj = 1 −∑k pjk, we have that ∑N i=1 φi(x)π(x) is equal to B2 + B3, so we have proved that B2 +B3 = A1 + A3. On the other hand, by summing the traffic equations we have that ∑ j νj = ∑ j λjpj. Hence: ∑ j νjπ(x) = ∑ j π(x)λjpj, = ∑ j pjφj(x+ ej)π(x+ ej), where we used 3.15 in the second equality. Then B1 = A2 and the result follows. ✷ A stochastic network is generally not Markovian, e.g. when the service requirements distributions are not exponentially distributed. We show in the next section how we can nevertheless use the Markovian analysis developed so far for Whittle networks to deal with more general cases. 3.3 Insensitivity To deal with non-Markovian networks can be a difficult task. However, if we construct a non-Markovian network by changing the Poisson service processes by general service processes but keeping the mean of the service times and keeping all the other features of the network, there are some cases when this new system shares the stationary distribution with the original Markovian system. In this section, we characterize the networks when this property holds in terms of Whittle networks, defined in Section 3.2. Definition 10. A network with Poisson arrivals is said to be insensitive when its sta- tionary distribution depends on the service time distribution only via its mean. 50 A key question is to characterize the rates (φj)j=1,...,N for which a PS network is a Whittle network for any distribution of services and hence to find a necessary and sufficient condition of insensitivity. To proceed with the analysis of this property, we first recall a basic result from renewal theory. 3.3.1 Residual times in renewal processes Let Nt = {Ti}∞i=0 a point process, i.e., T0 = 0, the sequence (Ti+1− Ti) is i.i.d., and let us assume that T1 − T0 has absolutely continuous distribution function θ and mean m. We want to compute the distribution of the remaining time to the next point of the point process starting from an arbitrary time t, i.e. the distribution of Rt = tNt+1 − t, that we will denote by θ̄ = θ̄(t). This can also be thought as the residual time until the next arrival seen by an observer arriving uniformly between two points of N . We have the following result about its distribution. Proposition 3. Given a stationary renewal point process Nt = {Ti}∞i=0, with the distri- bution of T1 − T0 denoted by ≡ θ, the distribution of the residual lifetime is θ̄(t) = 1− ∫∞ t (1− θ(s))ds m . Proof. A formal proof can be given using renewal theory (see [Asm03]). We give here a sketch of the proof based on the renewal equation. Given the stationarity of Nt, it is clear that the distribution of Rt does not depend on t. Using the stationarity we have that E(Nt+s) = E(Nt) + E(Ns) ∀ s, t ≥ 0 which implies that there exists a constant c such that E(Nt) = c t. Since this expectancy (the renewal function) satisfy the renewal equation, we have that c t = θ̄(t) + ∫ t 0 c(t− y)θ(dy), or θ̄(t) = c t− ∫ t 0 c(t− y)θ(dy). 51 Integrating by parts, ∫ t 0 c(t− y)θ(dy) = c (t− y)θ(y) ∣ ∣ ∣ t 0 + c ∫ t 0 θ(y)dy = c ∫ t 0 θ(y)dy, then we have that θ̄(t) = c ∫ t 0 (1− θ(y))dy. Since θ̄(∞) = 1, we deduce that 1 = c ∫ t 0 (1− θ(y))dy = cm, so we have that θ̄(t) = ∫ t 0 (1− θ(y))dy m = 1− ∫∞ t (1− θ(s))ds m . ✷ 3.3.2 Coupling construction for a processor sharing queue In this subsection we prove the insensitive property for a single node with a proces- sor sharing policy, using an explicit coupling based on the residual times of the customers. Consider a processor sharing queue with arrivals as a Poisson process with state depen- dent rate λ(n) and service rates φ(n), where n ≥ 0 is the number of clients in the queue. Customers have a generally distributed (absolutely continuous) service requirement with mean 1 and distribution Θ. Processor sharing means that the residual service time of each customer decreases with speed β(n) n , when there are n customers in the system. To keep a Markovian description of the system, it is now necessary to record the residual service times of each customer. The state space S is the product of N and the union of Rn +, for each n ∈ N (here the ordering of customers is irrelevant). We denote by Xt = {(nt, R i t)}nt i=1 the number of customers and their residual service times at time t. Note that X is not a Markov jump process but belongs to a wider class of Markov process, called as piece-wise deterministic Markov processes (see [DC99] for a definition). Let θ̄n be the product distribution on R n, where θ̄ is the distribution of the residual life time for a renewal point process with inter-arrival distribution θ (see Proposition 3). To have a distribution π on S, define θ̄π = ∑ n π(n)θ̄ n. Theorem 11 ([Zac07]). If the distribution π is solution of the detailed balanced equations with respect to the transitions λ(·) and φ(·), then µ̄π is invariant for Xt. 52 Proof. Suppose without lost of generality that θ has mean m = 1. Define θ̂n = θ̄n−1 × θ. We are going to couple Xt with a process X̂ which has the following dynamics: • when the workload of a customer is completed, it is immediately replaced by a new customer, having an independent workload with distribution θ. • there are no arrivals. For any distribution p, µ̄p is stationary for X̂. Let P and P̂ the transition kernels of both process and D the set of functions such that both kernels are continuous at t = 0. For f ∈ D we have: θ̄πPhf − θ̄πP̂hf = E θ̄πf(Xh)− E θ̄πf(X̂h) = h ∑ n π(n)[λ(n)(θ̂n+1f − θ̄nf) + φ(n)(θ̄n−1f − θ̂nf)] + o(h) (3.16) = h ∑ n [π(n)λ(n)− φ(n+ 1)π(n+ 1)](θ̂n+1f − θ̄nf) + o(h) = o(h). In equation (3.16), we have used that: • The service discipline is processor sharing, then all customers are symmetric (since they receive the same amount of the total service). • Given the symmetry of service, a completion of service for the original process occurs before time h with probability P ( min i=1,...,n θ̄i ≤ h β(n) n ) = 1− P ( θ̄i ≥ h β(n) n )n = 1− [ 1− ∫ h β(n) n 0 (1− θ(s))ds ]n , = h β(n) + o(h). where we know the distribution of θ̄i from Proposition 3. • Since the arrival is Poisson, there is no need to keep track of the time since the last arrival. An arrival occurs before h with probability α(n)h + o(h). When an arrival occurs, the new law of the residual times is changed into θ̂n+1 (keeping in mind that the order of the customers does not matter). 53 • The probability of more than one event (arrival or service completion) is of order o(h). The stationarity of θ̄π with respect to X̂ gives us that |θ̄πPhf − θ̄πf | = o(h), uniformly on D, and we conclude that θ̄π is stationary for X. ✷ 3.3.3 Insensitivity of processor sharing networks Bonald and Proutiere [BP02] gave a necessary and sufficient condition for a processor sharing network to be insensitive: Theorem 12. A processor sharing network with fixed arrival rates is insensitive if and only if it is a Whittle network. In other words, partial reversibility or reversibility of the adjoint process is a sufficient and necessary condition of insensitivity. Proof. The sufficiency of the theorem can be proved following the same approach as for a single PS queue (Theorem 11), combined with the detailed balance equations for the adjoint process. The second part of the proof, the necessary conditions, uses ideas from [BP02]. We use an induction of the number of classes. If N = 1, note that the process and the adjoint process coincide, once one has get rid of the loops, and both are reversible. Suppose the result is true for N − 1 classes. Assume for simplicity that there are no transitions for one node to itself. Consider a network of N classes and take the service requirements of node N to be: • 0, with probability 1− α, • 1/α, with probability α. 54 Remark that such a distribution has mean 1. Such network with these service requirements at node N is equivalent to a new network with: ν̃i = νi + (1− α)pNiνN , i = 1 . . . N − 1, p̃ij = pij + (1− α)piNpNi, i, j = 1 . . . N − 1, ν̃N = ανN , p̃iN = αpiN , i = 1 . . . N − 1, φ̃i(x) = φ(x), i = 1 . . . N − 1, φ̃N(x) = αφ(x). Insensitivity implies that the network has the same invariant measure for all α > 0. Letting α goes to zero, we obtain: ν̃i = νi + pNiνN , i = 1 . . . N − 1, p̃ij = pij + piNpNi, i, j = 1 . . . N − 1, ν̃N = 0, p̃iN = 0, i = 1 . . . N − 1, φ̃i(x) = φ(x), i = 1 . . . N − 1, φ̃N(x) = 0. The limiting balance equations are the balance equations of a N − 1 dimensional process. Using the induction assumption, the associated adjoint process is reversible. Note that the transitions q̄ of the adjoint process associated with the N −1 first queues are equal to the transitions of the adjoint process associated with the original N queues. Then for all states such that xN = yN , we have that π(x)q̄(x, y) = π(y)q̄(y, x). Since node N was chosen arbitrarily, the equality is valid for all states. ✷ 3.4 Bandwidth-sharing networks. Bandwidth-sharing networks describe the evolution of the number of flows (or calls) in a communication network where different classes of traffic compete for the bandwidth. They have become a standard modeling tool over the past decades for modeling 55 communication networks [BP03, MR02] and have been used in particular to represent the flow level dynamics of a wide range of wireline and wireless networks [BMPV06], generalizing more traditional voice traffic models [Kel79]. In this section we give its formal definition, some toy examples and specific models widely used. Finally we define gradient allocations and monotone networks, and give some examples. Next, we define mathematically a bandwidth-sharing network. Definition 11. A bandwidth-sharing network consists in • some finite set of nodes A, where each node a ∈ A has capacity Ca ≥ 0, • a set of N routes (or classes) through those nodes, where a route is a sequence of different nodes, • N independent arrival processes, • N independent service processes, • and a function φ : RN + → R N + , φ(x) = {φi(x)}Ni=1, that satisfies ∑ i route : a∈i φi(x) ≤ Ca ∀a ∈ A. That function is called a bandwidth-sharing allocation. Informally, the mechanism of the network is the following: Let us associate each arrival and service process to a route i and call them Ai and Si, respectively. Given the state of the network as the current number of clientes using each route of network x = (x1, . . . , xn), the state will increase to x + ei when an arrival event occurs at Ai or decrease to x − ei when a service event occurs at Si and xi > 0. In intervals where the state x is constant, each route i is using some constant capacity φi(x), as if a perfect fluid flow passes through all the nodes of the route (an idealization of packets transference). Indeed, these models boil down to a particular class of processor sharing networks with state-dependent service rates: they may depend on the number of flows within the same class, as well as on the numbers of flows in all the other classes. Assuming that class-i flows arrive subject to a Poisson process of intensity λi and require exponentially distributed service times of mean µi (the arrival processes of all classes being mutually independent), and in the absence of internal routing, the stochastic process 56 X = (X1, . . . , XN) describing the number of flows (or calls) in progress in the network is a state dependent multi-dimensional birth and death process with transition rates: q(x, x− ei) = µiφi(x), q(x, x+ ei) = λi, where x = (x1, . . . , xN) is the number of flows in each class of traffic. The service rates of the N traffic classes φ = (φi(·))Ni=1 encodes the particularities of the network resulting from the specific topology, technology, radio conditions, interference and multi-diversity effects and the packet protocols and congestion control mechanisms in use. 3.4.1 Some examples of bandwidth-sharing networks Consider the linear network represented in Figure 3.1 with four routes sharing three links. While the fourth route passes through all links, each of the routes 1, 2 and 3 only uses one of the links. This gives the following capacity constraints: φ4(x) + φ1(x) ≤ c1, φ4(x) + φ2(x) ≤ c2, φ4(x) + φ3(x) ≤ c3. Figure 3.1: Linear network. Another example is the tree communication network represented in Figure 3.2. We have two traffic routes, each passing through a dedicated link, followed by a common link. If each dedicated link has a capacity ci ≤ 1, i = 1, 2, and the common link has capacity 1, the flow on each route gets a capacity φi(x) that lies in the polyhedron C: φi(x) ≤ ci, i = 1, 2, 2 ∑ i=1 φi(x) ≤ 1. 57 Figure 3.2: Tree network. For examples modelling wireline networks, the vector φ(x) is usually assumed to belong for all x to a polyhedron describing the capacities constraints of each link that are used by the different routes. The wireless network is an example as well. In [LSD10], the rate region C of a 2-station network functioning under the 802.11e protocol is studied. The rate region is the set of achievable throughput vectors at the fine time scale (packet level). Their findings show that the rate region, (which exact expression depends in a complicated manner of the probabilities of transmitting) is generally not convex but is however log-convex. In the sequel, we always assume that C is log-convex and contains the set {η : ∑ ηi ≤ c} for some c > 0. This is not a restriction for applications. In general, like for these examples, the capacity constraints determine the space over which a network controller can choose a desired allocation function. 3.4.2 The α-fairness allocations Some specific bandwidth allocations have received a lot of attention in recent years. Mo and Walrand [MW00] introduced the following family of utility functions: Uα(x, η) = N ∑ i=1 xi η1−α i 1− α, α ∈ (0,∞) \ {1}, (3.17) U1(x, η) = N ∑ i=1 xi log(ηi), α = 1, (3.18) 58 where the allocation associated is defined by the optimization problem associated to a capacity set C as follows: φα(x) = argmax η∈C Uα(η, x). (3.19) The idea behind of this definition is that α is a parameter of “fairness”: the bigger α is, the more fair the allocation is. Consistently, α-fairness allocations include as special cases the Max-min fair allocation (Max-min) for α growing to infinity, the Max allocation when α goes to zero, the Proportional fair allocation (PF) when α = 1 (introduced originally by Kelly et. al. in [KMT98]) and the Potential delay minimization allocation (MinD) when α = 2, see [MR02]. These particular cases have different objectives: Max-min tries to maximize the minimum rate achieved by a flow, Max maximizes the total flow through the network, PF maximizes the total flow through the network but defining the value of a flow allocation φi(x) by log(φi(x)), and MinD minimizes the total potential delay, where the potential flow transfer time in a route is defined to be linearly proportional to the reciprocal of the rate allocation 1 φi(x) . A common feature for α positive and finite, is the search of a big current total flow while some degree of fairness is kept. An interesant characterization of the α allocations in terms of information divergence measures (some particular cases of Csiszár f -divergence) is given by [UK11]. This framework has been generalized to the weighted α-fair allocations, which provide flexibility to model different levels of fairness in the network. Specifically, the weighted proportional fair allocation η(x) for state vector x maximizes N ∑ i=1 wixi log(ηi), η ∈ C, where the weights wi are class-dependent control parameters. It has been argued in [KMT98] that a good approximation of current congestion control algorithms such as TCP (the Internet’s predominant Transfer Control Protocol) can be obtained by using the weighted proportional fair allocation, which solves an optimization problem for each vector x of instantaneous numbers of flows. 3.4.3 Gradient allocations. In the characterization of the large deviations of the stationary regime in Chapter 4, we rely on two properties of the allocation function φ playing a crucial role and being 59 intrinsically related: being a gradient allocation or a discrete gradient allocation (defined in Definition 7). Definition 12. A bandwidth allocation is called • gradient if there exists a function P : RN + → R (that we call a continuous potential) such that log(φ(x)) = ∇P (x), ∀x ∈ R N + \ {0}. • discrete gradient if there exists a function P̃ : RN → R (a discrete potential) such that log(φ(x)) = DP̃ (x) := (P̃ (x)− P̃ (x− ei))i=1,...,N ∀x ∈ N N , We show now one example of a gradient allocation. Recall that the proportional fair allocation is defined by the optimization problem associated to a capacity set C as follows: φPF (x) = argmax η∈C U1(η, x) = argmax η∈C 〈x, log(η)〉. (3.20) Following Massoulié [Mas07], observe that the proportional fair bandwidth allocation is gradient. Let δ∗A the support function of a bounded convex set A i.e.: δ∗A(x) = max η∈A 〈x, η〉. Proposition 4. Assume that the set C is log-convex, i.e., the set log(C) is convex, then log(φPF (x)) = ∇δ∗log(C)(x), ∀x ∈ R N + \ {0}. Proof. The function δ∗ is sub-differentiable because it is convex and finite (see [Roc70]) for all x ∈ R N + . The unicity of the sub-gradient comes from the strict concavity of the log function and implies the differentiability. ✷ We denote the Proportional fairness potential by P PF := δ∗log(C). By Section 3.2, we know that every Whittle network is a discrete gradient allocation. We show an important example of a gradient allocation: the Balanced fair allocation (BF) defined in [BP02] as the allocation ensuring the reversibility of the Markov process X and maximizing the probability of the network to be empty (among the ‘reversible’ allocations). We define formally the BF allocation: 60 Definition 13 (Balanced fair allocation). log(φBF (x)) = DP̃ (x), where the potential P̃ is recursively defined by: P̃ (x) = 0, P̃ (x) = max{a > 0 : P̃ (x− ei)− a ∈ log(C), ∀i = 1, . . . , N}. Since it is gradient, it allows a closed form expression for the stationary distribution of the numbers of flows in progress. In addition, the Balanced fair allocation gives a good approximation of the Proportional fair allocation while being easily evaluated, which is attractive for performance evaluation. See Bonald et. al. [BMPV06] for a comparison analysis of BF, Max-Min and PF allocations. 3.4.4 Monotone networks with general service time distribu- tions. In this section, we consider a processor sharing network (i.e. a set of processor sharing nodes) with generally distributed flow (or service) sizes. The dynamics of these networks are described for instance in [BP04, Zac07]. This means that a flow is served at node i with speed φi(Xt) Xi(t) . We need the notion of strong monotonicity introduced for instance in [BP04]. Definition 14. φ is strongly decreasing, if the function ψi(x) = { φi(x) xi if xi > 0 0 otherwise, is decreasing in xj for all j 6= i. In that case, we say that the network is monotone. The intuition of a network being monotone is that the allocation cannot increase the capacity of any route without decreasing the capacity per flow of another route. This is verified on all tree topologies and for many wireless networks instances. We recall from [BP04] the following proposition: Proposition 5. Let Xt and X̃t two processes associated with the allocations φ and φ̃ on the same set of routes. Suppose that φ is strongly decreasing, and that φi(x) xi ≥ φ̃i(x) xi for all x ∈ Z N + . Then, for all t and for all service time distribution we have that: Xt ≤st X̃t. 61 Proof. Remark that the processes Xt and X̃t are not Markov in general. However, we have a sample-path comparison between the processes by recalling the coupling construction of Subsection 3.3.2. For both allocations, we use the same arrival processes and record the residual service times of each flow through the network. Define the state space as S := ( N× ∞ ⋃ n=1 R n + )N , and the processes that saves the residual times by Yt := ( (ni t, {Ri,j t }n i t j=1) )N i=1 , Ỹt := ( (ñi t, {R̃i,j t }ñ i t j=1) )N i=1 , where ni t denotes the number of flows at route i and Ri,j t the residual time of j-th flow in the route i, at time t. Let us suppose that processes Xt and X̃t start at positions x ≤ y. Then, the rates at which each flow is served in the network verify φi(x) xi ≥ φi(y) yi ≥ φ̃i(y) yi , ∀i ∈ {1, ..., N}, (3.21) where the first inequality is due to the fact that φ is strongly decreasing. Then X0 has a smaller position than X̃0 with a bigger rate of services and the same coupled arrivals, so Yt(ω) ≤ Ỹt(ω) a.s. for 0 ≤ t < τ1, where τ1 is the next jumping time of X or X̃. The inequality is preserved for every finite t > 0 by induction over over the jumping times of X and X̃. This is a coupling construction (X, X̃) where Xt ≤ X̃t, and hence Xt ≤st X̃t. ✷ Bibliography [Asm03] S. Asmussen. Applied Probability and Queues. Springer, 2003. [BMPV06] T. Bonald, L. Massoulié, A. Proutière, and J. Virtamo. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Syst. Theory Appl., 53(1-2):65–84, 2006. 62 [BP02] T. Bonald and A. Proutière. Insensitivity in processor-sharing networks. Per- formance Evaluation, 49(14):193 – 209, 2002. [BP03] T. Bonald and A. Proutière. Insensitive bandwidth sharing in data networks. Queueing Syst. Theory Appl., 44(1):69–100, 2003. [BP04] T. Bonald and A. Proutière. On stochastic bounds for monotonic processor sharing networks. Queueing Syst. Theory Appl., 47(1/2):81–106, 2004. [DC99] F. Dufour and O. Costa. Stability of piecewise-deterministic Markov pro- cesses. SIAM J. Control Optim., 37(5):1483–1502 (electronic), 1999. [Jon10] M. Jonckheere. Introduction to Stochastic Networks. Lecture notes, course given at the Universidad de Buenos Aires, 2010. [Kel79] F. Kelly. Reversibility and Stochastic Networks. Wiley, 1979. [KMT98] F. Kelly, A. Maulloo, and D. Tan. Rate control for communication networks: Shadow prices, proportional fairness and stability. The Journal of the Opera- tional Research Society, 49(3):237–252, 1998. [LSD10] D. Leith, V. Subramanian, and K. Duffy. Log-convexity of rate region in 802.11e wlans. IEEE Communications Letters, 14(1):57–59, 2010. [Mas07] L. Massoulié. Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab., 17(3):809–839, 2007. [MR02] L. Massoulié and J. Roberts. Bandwidth sharing: objectives and algorithms. IEEE/ACM Trans. Netw., 10(3):320–328, 2002. [MW00] J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Trans. on Netw., 8(5):556–567, 2000. [Roc70] T. Rockafellar. Convex analysis, volume 28. Princeton landmarks in mathe- matics, 1970. [UK11] M. Uchida and J. Kurose. An information-theoretic characterization of weighted -proportional fairness in network resource allocation. Information Sciences, 181(18):4009 – 4023, 2011. [Zac07] S. Zachary. A note on insensitivity in stochastic networks. Journal of Applied Probability, 44(1):238–248, 2007. Chapter 4 Large deviations for Proportional Fairness allocation 4.1 Why to calculate large deviations for Propor- tional fairness allocation? 4.1.1 Insensitivity in telecommunication systems In 1917 an important problem concerning telephone exchanges was considered by Erlang on [Erl18] while he was working on the Copenhagen Telephone Company, [Sto07]. Let us suppose that we have K telephonic lines, telephonic calls that arrive at rate λ, and the duration time of each call is exponential(µ) distributed. Calls arriving while all lines are busy are lost. Let ρ := λ µ and EK(ρ) the fraction of calls that are lost in steady state. What is the value of EK(ρ)? We give the following the answer obtained by Erlang. We can model the number of busy lines as a one-dimensional birth and death process with positive rates of jumps given by q(x, x+ 1) = λi, for x = 0, 1, . . . K − 1, q(x, x− 1) = xµ for x = 1, . . . K. This system is usually known as the M \M \K queue, that is, the queue with Markovian arrival and service processes and K servers. On the other hand, let us consider the M \M \∞ queue, that is, the one-dimensional birth and death process with positive rates of jumps given by q(x, x+ 1) = λi, for x = 0, 1, . . . q(x, x− 1) = xµ for x = 1, 2, . . . . 64 It is straightforward to note that the M \M \ ∞ queue is reversible with respect to the Poisson distribution: π(x) = ρx e−ρ x! , x = 0, 1, ... by checking the Balance equations (Equation 3.1). The stationary distribution of the M \M \K queue, denoted by πK , can be obtained as the stationary distribution of an M \M \ ∞ queue conditionated to take values on {0, 1, ..., K}, see [Asm03] for the details. Then πK(x) = ρx x! 1 + ρ+ ...+ ρK K! , x = 0, 1, ..., K, and EK(ρ) correspond to the probability of having all lines occupied, EK(ρ) = ρK K! 1 + ρ+ ...+ ρK K! . (4.1) Equation 4.1 is usually known as Erlang’s B loss formula. Erlang’s B loss formula characterizes easily the probability of having a lost call, depend- ing only on the parameter ρ, usually known as the traffic intensity. It is an easy to apply formula, solved in practise by some recurrence equations depending on K. It was indeed applied short time after its publication in telephonic exchange systems, see [Sto07]. A very surprising fact is that the formula is a sharp aproximation to the performance of real systems. The approximation of the arrival process by a Poisson process when the population of clients is big enough, was already studied by Erlang in a previous work [Erl09]. However, assuming that the service time of a client has exponential distribution was not justified. The subyacent reason of the robustness of the formula is the insensitivity property of the system: the M \M \K is a Whittle network and then it is insensitive, by Theorem 12, so the formula depends on the distribution of the service time only by its traffic intensity. Since queueing systems with the insensitivity property have stationary distribution that can be estimated by simple statistics estimators, such property became a key prop- erty. For a wide class of modern and more complex telecommunication models, known as Kelly-Whittle networks, the insensitive property still holds (see [Bon07] for a survey of such models). However, there are models widely used in practise where the insensitivity property does not hold. Despite that, in this chapter we prove that a weak version of this property, called weak insensitivity, still holds in a general context. This includes the allocation of bandwidth-sharing capacity of the Internet network as a direct application. 65 4.1.2 The Proportional fairness election. In the general context, the selection of a specific bandwidth allocation is motivated by several properties of the resulting process X. Among those properties, the following ones are of particular interest: 1. maximal stability: one expects the bandwidth sharing mechanism to stabilize the system whenever it can be stabilized, 2. decentralized protocol: the bandwidth allocation can be implemented in the network using decentralized schemes, 3. insensitivity: when changing the traffic conditions1 and in particular the service time distribution (but keeping the mean flow size fixed), one could expect the stationary measure of X to remain the same, in which case the system and the bandwidth allocation are said to be insensitive, 4. weak insensitivity: the large deviations characteristics do not depend on the service time distribution, except for its mean and coincide with the large deviations of the most efficient insensitive allocation. Table 4.1 show which properties ares satisfied for the bandwidth sharing allocations introduced in Chapter 3: Max, Max-Min, PF, α-fair, and BF allocations. Maximum stability Decentralized protocol Insensitivity Max NO YES NO Max-Min YES YES NO PF YES YES NO α -fair YES YES NO BF YES ? YES Table 4.1: Properties of allocations Max is an inestable allocation while α-fair [BM01] and Max-min [dVLK99] allocations reach maximum stability (that is, to be positive recurrent for all λ in the interior of the capacity set). 1When the size distributions of the flows are not exponentially distributed, the process X is not Markov by itself anymore and the dynamics have to be defined using the residual service time. 66 By the characterization theorem of insensitive allocations as Whittle networks (Theo- rem 12), we know that except BF, all allocations fail to satisfy insensitivity (except on the case of very particular topologies). On the other hand, the BF allocation satisfies maximum stability and insensitive but it is not known whether it can be implemented with a decentralized protocol, [BMPV06]. This leaves us weak insensitivity as a central criterion for choosing a bandwidth sharing allocation. It was shown in [Mas07] that an appropriate modification of the proportional fair allocation, called modified proportional fair allocation (mPF), log(φmPF (x)) = DP PF (x), ( with P PF being the continuous potential associated with PF) coinciding asymptotically (point-wise) with PF, has the same large deviations characteristics as BF. On the other hand, it has been recently proven that an insensitive allocation being maximal stable, is asymptotically equivalent (point-wise) to PF [Wal11]. However, it remained as an open problem to prove that the large deviations character- istics of the stationary measure of the PF allocation itself coincide with those of mPF, and BF as it was conjectured in [Mas07]. The major difficulty of this problem is that the stationary measure of a network under the proportional fair allocation does not have a closed form in general, except in the very particular cases of symmetric hypergrids, see [Pro03]. Our main contribution consists in overcoming these difficulties for the specific processes we are studying. We first show that for Poisson arrivals and exponentially distributed flow sizes, the stationary distribution πPF of the number of flows associated with PF and the stationary distribution πmPF associated with the mPF allocation have the same large deviations characteristics. More precisely: Theorem 13. For all x ∈ Z N + : ∣ ∣ ∣ 1 n log ( πPF ({nx}↑) πmPF ({nx}↑) )∣ ∣ ∣ = O(n− 1 2 +ǫ), ∀ǫ > 0, where π({nx}↑) =∑k∈ZN + :k≥nx π(k). In the particular case that x ∈ N N the bound can be improved to O(n−1). By recalling the next result which established that BF and mPF share large deviations asymptotics, 67 Proposition 6. (Massoulié, 2007) lim n→∞ 1 n log πBF (nx) = N ∑ i=1 xi log(λi)− PmPF (x). we conclude that PF, BF and mPF share the large deviations rate function, in the case of Markovian services. As a consequence, we obtain the explicit tail asymptotics for PF allocation: Corollary 3. For all x ∈ Z N + : lim n→∞ 1 n log(πPF ({nx}↑)) = − N ∑ i=1 log (φi(x) λi ) . The proof of Theorem 13 is achieved by first proving the geometric ergodicity of both the mPF allocation and the PF allocation. For that purpose, we exhibit appropriate Lyapunov functions, relying on some structural results of PF described in [Mas07]. This then allows us to use simple martingale arguments. For monotone networks and generally distributed flow size, we give a more direct proof establishing that the large deviations characteristics are actually insensitive to the service time distribution. This shows that the proportional fair allocation indeed satisfy properties (1) and (2) and (4) at least on monotone topologies. 4.2 The Freidlin-Wentzell approach To understand the links between our results and the classical theory of large deviations for Markov processes, it is enlightening to recall the principles of the Freidlin and Wentzell [FW84] theory for birth and death processes on Z N , N ∈ N, with rates being Lipschitz and with bounded logarithms. Let Y n be a multi-dimensional birth and death process with transition rates: q (x n , x n − ei n ) = nφi (x n ) , q (x n , x n + ei n ) = nλi. 68 Suppose additionally that the death rates are 0-homogeneous, i.e. φ(az) = φ(z), ∀ z ∈ R N/n, a > 0. Define the logaritmic moment-generating of the increment of the process for z ∈ R N/n, y ∈ R N by Hn(z, y) := d dt Ez[exp〈y, Y n(t)− z〉]. Using the structure of the generator and the 0-homogeneity of the rates we have that Hn(z, y) = n ( ∑ i λi(e yi/n − 1) + φi(z)(e −yi/n − 1) ) . Then we obtain that Hn(z, y/n) = nH(z, y/n) with H(z, y) := 〈ey − 1, λ〉+ 〈e−y − 1, φ(z)〉. Now, define the Fenchel-Legendre L transform of H by L(x, y) := supθ∈RN 〈y, θ〉−H(x, θ), the action functional S : C[0, T ]→ R as ST (r) = { ∫ T 0 L(rs, ṙs)ds if r is absolutely continuous, ∞ otherwise, and the quasi-potential R by R(x) = min r,T,r(0)=0,r(T )=x ST (r, ṙ). The original results of Freidlin and Wentzell are stated for Lipschitz-continuous transi- tions (extended to R N): Theorem 14 (Freidlin and Wentzell, [FW84]). Assume that for each i, the function log φi(·) is bounded and Lipschitz continuous and that the function L is such that: lim |x−x̃|→0 |L(x, y)− L(x̃, y)| 1 + L(x, y) → 0, uniformly in x and x̃. Let πn the stationary measure of the birth and death processes Y n. Then, a large deviations principle holds for the family of probabilities πn(·) with rate function R(·). In the case of general multi-dimensional birth and death processes, it is difficult to solve the variational problem from which the quasi-potential R is defined. However, assuming that the rates are gradient greatly simplifies the expression of the quasi-potential: 69 Proposition 7. Assume that log(φ(x)) = ∇P (x), ∀ x ∈ Z N , for some differentiable function P : Rn → R. Then the quasi-potential of the birth and death process is equal to R(x) = −〈log(λ), x〉+ P (x). Proof. We first show that: R(x) = max xs:x0=0,xT=x ∫ T 0 〈ẋs, log ( λ φ(xs) ) 〉ds. The first simplification comes from the time homogeneity of the process. Using the Euler- Lagrange principle, combined with the time homogeneity (which implies that ∇xL = 0) the minimizing path satisfies the Beltrami identity: L− 〈y,∇yL〉 = 0. Now, observe that if θy = argmax〈y, θ〉 − H(x, θ), we obtain that ∇yL = θy and L − 〈y∇yL〉 = H(x, θy) = 0. Solving the last equation leads to θẋ = 1 2 log (φ(x) λ ) , which allows us to conclude since L(x, ẋ) = 〈ẋ,∇yL(x, ẋ)〉 = 〈ẋ, θẋ〉. The expression for the quasi-potential then follows from integration. ✷ We insist on the fact that this theory allows to prove the large deviations rate of the stationary measure of birth and death processes only for smooth allocations and does not provide a rate of convergence. As underlined for instance in [SW95], it is very demanding to extend these results to processes on state spaces with boundaries since the technical conditions of the classical theory are never fullfilled. (Remark that boundness of the logarithm is never verified for birth and death processes defined in the orthant. Moreover, the Lipschitz assumption is not verified in our case for most network topologies). 70 4.3 Large deviations for Markovian dynamics. Before proving Theorem 13, we illustrate it on a toy example. Example 1 (Single link). Consider first a single link shared by N classes. This corre- sponds to choosing C = {∑ ηi µi ≤ 1}, where the {µi} correspond to the mean flow sizes. In this case, the proportional fair allocation coincides with the balanced fairness allocation. Its service rates are given by: φi(x) = µi xi |x| . Note that the continuous and the discrete potential functions associated with the allocation φ do not coincide: δ∗log(C)(x) = N ∑ i=1 xi |x| log ( xi |x| ) , while the discrete potential is given by: P (x) = log (( |x| x1, . . . , xN )) . One can however prove using the Stirling formula that 1 n (P (nx)− δ∗log(C)(nx))→ 0, as n→∞. An extension of these formulae can be obtained for hypergrids topologies [BP03]. In this section, we call X the process associated with the PF allocation, denoted φ and corresponding to the continuous gradient of the potential P PF . We further denote by X̃ the process associated to the allocation φ̃ itself corresponding to the discrete gradient of P PF , i.e.: log(φ(x)) = ∇P PF (x), (4.2) log(φ̃(x)) = DP PF (x) = (P PF (x)− P PF (x− ei))i=1...N . (4.3) Structural properties of the PF allocation. From the structural representation of PF, we know that φ̃ is a perturbation of the original rates φ in the sense that for all xi > 0 (see Lemma 9 in [Mas07] ): ∣ ∣ log(φi(x))− log(φ̃i(x)) ∣ ∣ = ∣ ∣ log(φi(x))− (P PF (x)− P PF (x− ei)) ∣ ∣ ≤ 1 xi , ∀i. (4.4) 71 Geometric ergodicity. We first consider the dynamics corresponding to the Proportional fairness allocation. For a Markov jump process with countable state space E, rates of jump {q(x, y)} and a function F : E → R, define the drift of F as ∆F (x) := ∑ y∈E q(x, y)(F (y)− F (x)). Proposition 8 (Geometric ergodicity of X). Suppose λ ∈ int(C), then there exists a function G : RN + → R and constants K and γ > 0 such that for |x| > K: ∆G(x) ≤ −γG(x). Denote by πPF the stationary distribution of X, and P 0 t the distribution at time t of process X starting from zero. Hence: ∣ ∣ ∣ P 0 t (x)− πPF (x) ∣ ∣ ∣ ≤ K1e −K2t, for some constants K1, K2 > 0. Proof. The proof has two steps. We first construct a Lyapunov function with bounded drift. We then use this Lyapunov function to construct a new one verifying a geometric drift inequality. First step: let F (x) = ( ∑N i=1 x2 i λi )1/2. Observe that F is a norm in R N (hence is positive, 1− homogeneous, and diverges to infinity when |x| → ∞). Furthermore, it is C2 for all x 6= 0 and: ∂F (x) ∂xi = xi λiF (x) . Then, there exists K > 0 such that for |x| > K 1 |x| sup z=x,x±ei ∣ ∣ ∣ ∂2F (z) ∂2xi ∣ ∣ ∣ ≤ ǫ. Using that F is 1-homogeneous, this leads for |x| > K to: ∆F (x) ≡ N ∑ i=1 λi(F (x+ ei)− F (x)) + φi(x)(F (x− ei)− F (x)), ≤ 〈λ− φ(x),∇F (x)〉+ ǫ, = 〈 λ− φ(x), x F (x)λ 〉 + ǫ, = |x| F (x) 〈 λ− φ(x), x |x|λ 〉 + ǫ. 72 Using the definition of Proportional fairness (as the allocation maximizing U1(·, x) and the strict concavity of the log function), for all η ∈ C, N ∑ i=1 xi ηi (ηi − φi(x)) = 〈(∂U(x, η) ∂ηi ) , η − φ 〉 < 0, which implies that that there exists γ1 > 0 such that: 〈 λ− φ(x), x|x| 1 λ 〉 ≤ −γ1, which in turn implies (together with the fact that F is norm-like) that there exists γ2 > 0 such that ∆F (x) ≤ −γ2 for all |x| > K. Remark also that for all x, |∆F (x)| ≤ C. Second step: we now calculate the drift of G(x) := exp(δF (x)): ∆G(x) = N ∑ i=1 λi(e δF (x+ei) − eF (x)) + φi(x)(e δF (x−ei) − eδF (x)), = G(x) N ∑ i=1 λi(e δ(F (x+ei)−F (x)) − 1) + φi(x)(e δ(F (x−ei)−F (x)) − 1), ≤ G(x)(δ∆F (x) + C1δ 2 N ∑ i=1 exp(c|∆F (x)|) +O(δ3)), ≤ G(x)(−C2δ + C3δ 2) ≤ −γG(x). By a continuous time version of the results of [MT93], this implies that : |P 0(X(t) = x)− πPF (x)| ≤ K1 exp −K2t . ✷ We now deal with the dynamics of the modified proportional fair allocation. In the following proposition, we use the same functions F and G defined in the Proportional fairness case. Proposition 9 (Geometric ergodicity of X̃). Suppose λ ∈ int(C), then there exist con- stants K̃ and γ̃ > 0 such that for |x| > K̃: ∆G(x) ≤ −γ̃G(x). Denote by πmPF the stationary distribution of X, and P̃ 0 t the distribution at time t of process X̃ starting from zero. Hence: ∣ ∣ ∣ P̃ 0 t (x)− πmPF (x) ∣ ∣ ∣ ≤ K̃1e −K̃2t, for some constants K̃1, K̃2 > 0. 73 Proof. We proceed as previously. The only difference consists in proving that the perturbations of the rates are small enough to be negligible in the drift calculations. For |x| > K̃, using the bounds on the difference of φ and φ̃, we obtain that: ∣ ∣φi(x)− φ̃i(x) ∣ ∣ ≤ c0 ∣ ∣ log(φi(x))− log(φ̃i(x)) ∣ ∣ ≤ c0 xi , for xi > 0. Hence: ∆F (x) = N ∑ i=1 λi(F (x+ ei)− F (x)) + φ̃i(x)(F (x− ei)− F (x)), ≤ 〈λ− φ̃(x),∇F (x)〉+ ǫ, ≤ 〈 λ− φ(x), x F (x)λ 〉 + 〈 φ(x)− φ̃(x), x F (x)λ 〉 + ǫ, ≤ −γ1 + 〈 φ(x)− φ̃(x), x F (x)λ 〉 , ≤ −γ1 + c |x| . which gives (together with the fact that F is norm-like) that there exists γ2 > 0 such that ∆̃F (x) ≤ −γ2 for all |x| > K̃. Remark also that |∆̃F (x)| ≤ C. We can conclude exactly as in the previous proof. ✷ Before proving the main result of this section, we establish a useful lemma using the geometric ergodicity of the processes. Lemma 8. There exists C > 0 such that for tn = Cn, we have log ∣ ∣ ∣ P 0(Xtn ≥ nx) πPF ({nx}↑) ∣ ∣ ∣ ≤ C1 exp{−C2 n} for some C1, C2 > 0, where πPF ({k}↑) = ∑ j∈ZN + :≥k π PF (j). The analogue inequality is true for the process X̃. Proof. We need to bound from below the stationary probabilities of the process. This is easy since the rates are bounded. Let us define a process with the same arrival rates and the service rates equal to ϕ, the maximum of φi for all coordinates. It is clear that πPF ({nx}↑) ≥ K1 (λ ϕ )n , 74 for some constant K1 > 0. We have log ∣ ∣ ∣ P 0(Xtn ≥ nx) πPF ({nx}↑) ∣ ∣ ∣ ≤ ∣ ∣ ∣ 1− P 0(Xtn ≥ nx) πPF ({nx}↑) ∣ ∣ ∣ = ∣ ∣ ∣ P 0(Xtn ≥ nx)− πPF ({nx}↑) πPF ({nx}↑) ∣ ∣ ∣ ≤ K2e −K3tn πPF ({nx}↑) ≤ K2e −K3tn K1 ( λ ϕ )n = K2 K1 exp{−K3 tn + log (ϕ λ ) n} where first inequality comes by log(x) ≤ |1− x| for all x > 0, and the second one by the geometric ergodicity of X. We take C > 0 such that K3C > log ( ϕ λ ) . Note that the same argument remains valid for process X̃ taking its respective transition rates and stationary distribution. ✷ Change of measure and control of the martingale. To relate the distribution of X and X̃, we recall the Proposition B.6 513 of Shwartz and Weiss [SW95]: Proposition 10. Let Y i t i = 1, 2 be two multidimensional birth-death process in Z N + with step directions ej, bounded step rates {qij(x)}x∈ZN + and law P i. Assume that for all x and j, q1j (x) = 0 if and only if q2j (x) = 0. Then we can relate the distributions of the processes by dP 2 =MtdP 1 where Mt = exp ( ∫ t 0 N ∑ j=1 log (q2j (Xs−) q1j (Xs−) ) dN j s − ∫ t 0 N ∑ j=1 (q2j (Xs)− q1j (Xs))ds ) . Here {N j} denote a family of counting processes describing the jumps of the processes in the j-th direction and Mt is a càdlàg martingale. In our case, φi(x), φ̃i(x) are both positive whenever xi > 0, and 0 otherwise. All the rates of X and X̃ are bounded so we meet the conditions of the previous Proposition and we can write that dP̃ (ω) =MtdP (ω), with Mt = exp ( ∫ t 0 N ∑ j=1 1{Xs−>0} log ( φ̃j(Xs−) φj(Xs−) ) dN j s − ∫ t 0 N ∑ j=1 1{Xs>0}(φ̃j(Xs)− φj(Xs))ds ) , = N ∏ j=1 M j t , 75 and each of the factors M j is itself a martingale (with the obvious definition of M j). Remark 1. An important observation for the following is that the counting processes N j can be seen as thinning (according to Xs) of some Poisson processes N̂ j which are all independent. We denote by Ms,t the last expression with the integrals running from s to t, so Mt = M0,t. The change of measure formula is then E0[1{X̃t≥nx}] = E0[Mt1{Xt≥nx}]. We can now prove our main result. Proof of Theorem 13 : We consider first the case where xi > 0 for all i = 1 . . . , N . Define the sequence of stopping times: τ1 = 0, τi = inf{t > τi−1, X̃t ≥ nx}, for i even, i ≥ 2, τi = inf{t > τi−1, X̃t < nx}, for i odd, i ≥ 3. Observe that if X̃t ≥ nx, then necessarily, there exists k even (a.s. finite) such that τk ≤ t ≤ τk+1. Using the Markov property and the martingale property, we then have E0(Mt1{X̃t≥nx}) = E0 ∑ k even 1τk≤t<τk+1 Mt1{X̃t≥nx} = ∑ k even E01τk≤t<τk+1 M0,τkMτk,t1{X̃t≥nx}, = ∑ k even E0(E(1τk≤t<τk+1 M0,τkMτk,t1{X̃t≥nx}|F̃τk)) = ∑ k even E0(M0,τkE(1τk≤t<τk+1 Mτk,t1{X̃t≥nx}|X̃τk)), with {F̃k} being the natural filtration of process X̃. We define gk(t) = supy E(1τk≤t<τk+1 Mτk,t1{X̃t≥nx}|X̃τk = y), so E0(Mt1{X̃t≥nx}) ≤ ∑ k even gk(t)E 0(M0,τk) = ∑ k even gk(t). 76 Remark that on {X̃t ≥ nx} ∩ {τk ≤ t < τk+1} (k even) we have {X̃s ≥ nx : s ∈ [τk, t]}. Recall that x is such that xi > 0 for all i. Using the assumption on φ and φ̃: E0 ( 1τk≤t<τk+1 1{X̃t≥nx} exp ( ∫ t τk N ∑ j=1 1{X s−>0} log ( φ̃j(Xs−) φj(Xs−) ) dN j s − ∫ t τk N ∑ j=1 1{X s−>0}(φ̃j(Xs)− φj(Xs))ds )) ≤ E0 ( 1τk≤t<τk+1 exp { N ∑ j=1 C1 n (N j t + t) } 1{X̃t≥nx} ) , ≤ E0 ( 1τk≤t<τk+1 exp {C1N n (N̄t + t) } 1{X̃t≥nx} ) , where N̄t is a Poisson process with parameter λ̄ equal as the maximum of the parameters of the Poisson processes {N j t }Nj=1. Summing these inequalities and using Hölder’s inequality for p > 1: E0(Mt1{X̃t≥nx}) ≤ exp {C1Nt n } P 0(X̃t ≥ nx) p−1 p exp{λ̄t[eC1pN n − 1]} 1 p . We now choose tn = C2n such the result of Lemma 8 holds, and the sequence pn = n to obtain 1 n logP0(Xtn ≥ nx) ≤ C1NC2 n + λ̄C2(exp(C1N)− 1) n + n− 1 n2 logP0(X̃tn ≥ nx), 1 n log(πPF ({nx}↑)) + C3 n exp(−C4 n) ≤ O(n−1) + (n− 1 n ) 1 n log(πmPF ({nx}↑)) + C̃3(n− 1) n2 exp(−C̃4 n) So we have 1 n log(πPF ({nx}↑)) ≤ 1 n log(πmPF ({nx}↑)) +O(n−1). We also have the converse of this last inequality using the same arguments interchanging X and X̃. Assume now that xi > 0 for i ∈ U , while xi = 0 for i ∈ S, where U ,S ⊆ {1, ..., N}. If classes of U are independent of classes of S, the result is obvious from the case where x is strictly positive. Hence suppose that there exists some dependence between classes of U and S. We will use the following fact: Lemma 9. Given the definition of Proportional fairness, if class i ∈ S and class j ∈ U are not independent, then there exist K > 0 such that if yi ≤ nǫ and yj ≥ n for all j ∈ U , then: |φi(y)− φ̃i(y)| ≤ Kǫ. 77 Proof. If at least two classes are not independent, there exists a Lagrange multiplier α > 0 and some positive constants ci > 0 and cj (with at least one j with cj > 0) such that ∂U1(y, ηi) ∂ηi = xi ηi = αci, ∂U1(y, ηi) ∂ηj = xj ηj = αcj. Combined with the fact that there exists c > 0 such that 0 < c ≤∑N j=1 ηj ≤ C, we obtain that c̃ yi yi + ∑ j∈Ui yj ≤ φi(y) ≤ C̃ yi yi + ∑ j∈Ui yj , where Ui ⊂ U . Hence if yi ≤ nǫ and yj ≥ n for all j ∈ U φi(y) ≤ C̃ ǫ n 1 + n ≤ K̃ǫ. Using the control on the modified proportional fair allocation for xi ≥ 1: φ̃i(y) ≤ exp ( 1 yi ) φi(y) ≤ eφi(y) ≤ eK̃ǫ. ✷ Now we consider a finer classification of indexes in S. Let {ǫn} be a sequence such that ǫn goes to 0 as n grows, and {tn = C2n} where C2 > 0 is chosen to meet conditions of Lemma 8. For each n, define the sets Sn = {i ∈ S : Xi(tn) ≥ nǫn}, Sn = {i ∈ S : Xi(tn) < nǫn}. We look at the set of events: A = {Xi(tn) ≥ nxi, i ∈ UR, Xi(tn) ≥ nǫn, i ∈ Sn, Xi(tn) ≤ nǫn, i ∈ Sn}. Recall that ∣ ∣ ∣ log (φi(y) φ̃i(y) )∣ ∣ ∣ ≤ 1, and remark that on A ∈ A, using the previous lemma, the process counting the number of downwards jumps in direction j ∈ S which are not common for X and X̃ is dominated by a Poisson process N ǫn of intensity C5ǫn independent of N j, j ∈ S. Hence: E01τk≤t<τk+1 1AMτk,t ≤ E0 ( exp ( ∑ j∈U C1 n (N j t + t) + ∑ j∈Sn C1 nǫn (N j t + t) + ∑ j∈Sn [C5N ǫn t + (C6ǫn)t] ) 1τk≤t<τk+1 1A ) . 78 and, E0(Mt1A) ≤ E0 ( exp ( ∑ j∈U C1 n (N j t + t) + ∑ j∈Sn C1 nǫn (N j t + t) + ∑ j∈Sn [C5N ǫn t + (C6ǫn)t] ) 1A ) ≤ E0 ( exp ( |U|C1 n (N̄t + t) + |Sn|C1 nǫn (N̄t + t) + |Sn|[C5N ǫn t + C6ǫnt] ) 1A ) ≤ E0 ( exp {C1pN n (N̄t + t) }) |U| pN E0 ( exp {C1pN nǫn (N̄t + t) }) |Sn| pN E0 ( exp{pN [C5N ǫn t + C6ǫn t]} ) |Sn| pN P 0(X̃t ≥ nx) p−1 p , (4.5) where we used Hölder’s inequality for 1 = |U| pN + |Sn| pN + |Sn| pN + p−1 p . We now bound the speed of convergence, in the large deviations scale, of each of the three first factors on the right-hand side of inequality (4.5). Choosing tn = C2n, pn = C7 log n, ǫn = n− 1 2 , we have: 1 n logE0 ( exp {C1Npn n (N̄tn + tn) }) |U| Npn = 1 n log ( exp { |U|C1tn n } exp{λ̄tn[e C1Npn n − 1]} |U| Npn ) = |U|C1C2 n + |U|λ̄tn Nnpn [e C1Npn n − 1] = |U|C1C2 n + |U|λ̄C2 NC7 log n [e C1C7N logn n − 1] = O(n−1). We do similarly for the second factor: 1 n logE0 ( exp {C1Npn ǫnn (N̄tn + tn) }) |Sn| Npn = 1 n log ( exp { |Sn|C1tn ǫnn } exp{λ̄tn[e C1Npn ǫnn − 1]} |Sn| Npn ) = |Sn|C1C2 ǫnn + |Sn|λ̄tn Nnpn [e C1Npn ǫnn − 1] = |Sn|C1C2 ǫnn + |Sn|λ̄C2 NC7 log n [e C1C7N logn ǫnn − 1] = O((nǫn) −1) = O(n− 1 2 ). 79 Finally, for the third factor we have: 1 n logE0 ( exp{Npn[C5N ǫn tn + C6ǫn tn]} ) |Sn| Npn = 1 n log ( exp{C6|Sn|ǫntn} exp{ǫntn[eC5Npn − 1]} |Sn| Npn ) = C6ǫn |Sn|tn n + |Sn|ǫn tn Npnn [eC5Npn − 1] = C6C2|Sn|ǫn + C2|Sn|ǫn C7N log n [eC5C7N logn − 1] = C6C2|Sn|ǫn + C2|Sn|ǫn[nC5C7N − 1] C7N log n = O(ǫn) +O ( ǫnn ǫ log n ) = O(n− 1 2 +ǫ), where we chose C7 > 0 small enough such that C7C5N < ǫ, for any given ǫ > 0. Then, along the same lines as in the case where x has all entries positive, it follows 1 n log(πPF ({nx}↑)) ≤ 1 n log(πmPF ({nx}↑)) +O(n− 1 2 +ǫ) ∀ǫ > 0. We also have the converse of last inequality using the same arguments interchanging X and X̃. ✷ 4.4 Large deviations for monotone networks with general service time distributions. In this section, we consider a processor sharing network (i.e. a set of processor sharing nodes) with a Proportionally fair bandwidth allocation and generally distributed flow service times. This means that a flow is served at node i with speed φPF i (Xt) Xi(t) . The dynamics of these networks are described for instance in [BP04, Zac07]. We recall definitions from Section 3.4.4. We assume in this section that the network is monotone, see Definition 14. This is verified on all tree topologies for instance and for many wireless networks instances. In the proof of the following theorem, we use the monotonicity of the network to obtain stochastic comparisons. Recall Proposition 5 for the stochastic comparison, from 3.20 that we define P PF as P PF (x) = maxη∈log(C)〈η, x〉, and from Proposition 4 that log(φi(x)) = ∇P PF (x). Now define the discrete potential functions Ψ and Ψ by the recursive formula: Ψ(x) = − max i=1...N (Ψ(x− ei)− log(φi(x))), 80 Ψ(x) = − min i=1...N {Ψ(x− ei)− log(φi(x))}. We call supPF and infPF the reversible allocations associated with the discrete poten- tials Ψ and Ψ and define the rate function R(x) = 〈log(λ), x〉 − P (x). Let X and X the process associated with the discrete potentials Ψ and Ψ. Define further the invariant measures (not necessarily stationary) π and π of the pro- cesses X ≺ X ≺ X. Since we have constructed these processes from a discrete potential, we have that (see Proposition 2): π(x) = λx exp(−Ψ(x)), π(x) = λx exp(−Ψ(x)). We can now state the main result of this section. Theorem 15. Suppose the network monotone, i.e. φ is strongly monotone. If λ is in the interior of the capacity set C, then the allocations Proportional fairness, supPF and infPF are stable and admit the same large deviation characteristics with rate function R. More precisely: ∣ ∣ ∣ 1 n log(π(nx))− 1 n log(πPF (nx)) ∣ ∣ ∣ = O(log(n)n−1), ∣ ∣ ∣ 1 n log(π(nx))− 1 n log(πPF (nx)) ∣ ∣ ∣ = O(log(n)n−1). Proof. Given the definitions of the discrete potentials Ψ and Ψ, observe that there exists two paths P(x) and P(x) from 0 to x such that: Ψ(x) = − ∑ k:(ik,zk)∈P(x) log(φik(zk)), Ψ(x) = − ∑ k:(ik,zk)∈P(x) log(φik(zk)), where, with a slight abuse of notations, the indexes i(z) correspond to the indexes defined by the specific paths P(x) and P(x). Recall now that P is the potential associated with the proportional fair allocation, and since we can define this potential up to an additive constant, let us choose it such 81 that P (0) = 0. So, we can write that for any path P(x) going from 0 to x, P (x) = P (x)− P (0) =∑k:(ik,zk)∈P(x) DikP (zk). Choosing P(x) = P(x): |Ψ(nx)− P (nx)| = ∣ ∣ ∣ ∑ k:(ik,zk)∈P̄(nx) DikP (zk)− log(φik(zk) ∣ ∣ ∣ , ≤ ∑ k:(ik,zk)∈P̄(nx) |DikP (zk)− log(φik(zk)|. (4.6) Recalling from (4.4) that for xi ≥ 1: |P (x)− P (x− ei)− log(φi(x))| ≤ 1 xi , we can bound (4.6) by: |Ψ(nx)− P (nx)| ≤ ∑ (ik,zk)∈P̄(nx) 1 zik , ≤ C n ∑ i=1 1 i ≤ C log(n). (4.7) Similarly, |Ψ(nx)− P (nx)| ≤ C log(n). (4.8) Now observe that: 1 n log(π(nx)) = 〈log(λ), x〉 − 1 n Ψ(nx), 1 n log(π(nx)) = 〈log(λ), x〉 − 1 n Ψ(nx). Using (4.7) and (4.8) we obtain that 1 n log(π(nx)) = 1 n 〈log(λ), nx〉 − 1 n P (nx) +O(log(n)n−1), 1 n log(π(nx)) = 1 n 〈log(λ), nx〉 − 1 n P (nx) +O(log(n)n−1), and hence, by the 1-homogeneity of R, lim n→∞ 1 n log(π(nx)) = lim n→∞ 1 n log(π(nx)) = R(x). Assume λ is in the interior of the capacity set C. Using the definition of P , this implies that there exists a > 0 such that R(x) = 〈log(λ), x〉 − P (x) = 〈log(λ)− log(φ(x)), x〉 ≤ −a|x|, 82 which implies that the invariant measure π and π are summable. This hence proves that the stationary distributions of both processes X and X are well defined for Markovian dynamics while the reversibility condition (i.e. the balance property of the service rates) implies the insensitivity of the stationary distribution to the service time distribution [BP02, Zac07]. Therefore, for any service time distribution, the networks with allocation infPF and supPF admit the stationary distribution C1π and C2π where C1 and C2 are normalizing constants. By the assumption of monotonicity of the network, we obtain that: P (|X| ≥ n) ≥ P (|X| ≥ n) ≥ P (|X| ≥ n), (4.9) and by Cramér’s theorem we conclude: lim n→∞ 1 n logP (|X| ≥ n) = lim n→∞ 1 n logP (|X| = n). It has further been proven in [Mas07] that mPF and BF have R(x) as rate functions. ✷ We proved that the stationary measure of the number of flows in progress in a bandwidth sharing network functioning under the Proportional fair allocation shares the same large deviations characteristics with the stationary measure of the number of flows in progress of the same network under the Balanced fair allocation. This formalizes the idea that in long excursions Proportional fair allocation behaves similarly to the most efficient insensitive allocation. 4.5 Open problems 4.5.1 Large deviations for discriminatory Processor Sharing Let us examinate the simple context of a node with N rutes through it. In this case, Proportional fair allocation reduces to Processor sharing routine, defined in Section 3.2. Namely: φPS i (x) = xi ∑N j=1 xj , ∀i = 1, ..., N. We can generalize this allocation to the discriminatory Processor Sharing allocation (dPS), defined by φdPS i (x) = xi ∑N j=1 ωj xj , ∀i = 1, ..., N. for some fixed weights 0 < ωj < ∞, i = 1, ..., N . The main idea is to keep the sharing mechanism to allocate bandwidth while giving different preference to the routes. We are interested in to calculate the large deviations of the stationary distribution of a network under this sharing routine. 83 4.5.2 Large deviations approximations by reversible processes To find the large deviations asymptotics of Proportional fairness allocation in Markovian and stationary regime, our technique consisted in approximating our allocation by a re- versible allocation sharing the same behaviour asymptotically. Since reversible process are more manageable in terms of stationary distributions, it was possible to compute explicitly all the tail behaviour. Is that method possible for more general allocations? Bibliography [Asm03] S. Asmussen. Applied Probability and Queues. Springer, 2003. [BM01] T. Bonald and T. Massoulié. Impact of fairness on internet performance. In Proceedings of the ACM Sigmetrics, pages 82–91, 2001. [BMPV06] T. Bonald, L. Massoulié, A. Proutière, and J. Virtamo. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Syst. Theory Appl., 53(1-2):65–84, 2006. [Bon07] T. Bonald. Insensitive traffic models for communication networks. Discrete Event Dynamic Systems, 17(3):405–421, 2007. [BP02] T. Bonald and A. Proutière. Insensitivity in processor-sharing networks. Per- formance Evaluation, 49(14):193 – 209, 2002. [BP03] T. Bonald and A. Proutière. Insensitive bandwidth sharing in data networks. Queueing Syst. Theory Appl., 44(1):69–100, 2003. [BP04] T. Bonald and A. Proutière. On stochastic bounds for monotonic processor sharing networks. Queueing Syst. Theory Appl., 47(1/2):81–106, 2004. [dVLK99] G. de Veciana, T. Lee, and T. Konstantopoulos. Stability and performance analysis of networks supporting services with rate control - could the internet be unstable? INFOCOM, pages 802–810, 1999. [Erl09] K. Erlang. Sandsynlighetsregningog telefonsamtaler (in danish). Nytt tidsskrift for Matematik B, (20), 1909. [Erl18] K. Erlang. Solution of some problems in the theory of probabilities of signifi- cance in automatic telephone exchanges. The Post Office Electrical Engineers Journal, (10), 1918. 84 [FW84] M. Freidlin and A. Wentzell. Random perturbations of dynamical systems. Springer, 1984. [Mas07] L. Massoulié. Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab., 17(3):809–839, 2007. [MT93] S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, 1993. [Pro03] A. Proutiére. Insensibilité et bornes stochastiques dans les réseaux de file d’attente. Application à la modélisation des réseaux de télécommunications au niveau flot. PhD Thesis, École Polytechnique, 2003. [Sto07] K. Stordahl. The history behind the probability theory and the queuing theory. Telektronikk, (2):123–140, 2007. [SW95] A. Shwartz and A. Weiss. Large Deviations for performance analysis. Queues, communication and computing. Chapman & Hall, 1995. [Wal11] N. Walton. Insensitive, maximum stable allocations converge to proportional fairness. Queueing Systems, 68(1):51–60, 2011. [Zac07] S. Zachary. A note on insensitivity in stochastic networks. Journal of Applied Probability, 44(1):238–248, 2007. Bibliography [AD95] D. Aldous and P. Diaconis. Hammersley’s interacting particle process and longest increasing subsequences. Probab. Th. Rel. Fields, 103:199–213, 1995. [Ana93] V. Anantharam. Uniqueness of stationary ergodic fixed point for a ·/M/K node. Ann. Appl. Probab., 3(1):154–172, 1993. [Asm03] S. Asmussen. Applied Probability and Queues. Springer, 2003. [Bil68] P. Billingsley. Convergence of Probability Measures. John Wiley & Sons, 1968. [BM01] T. Bonald and T. Massoulié. Impact of fairness on internet performance. In Proceedings of the ACM Sigmetrics, pages 82–91, 2001. [BMPV06] T. Bonald, L. Massoulié, A. Proutière, and J. Virtamo. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Syst. Theory Appl., 53(1-2):65–84, 2006. [Bon07] T. Bonald. Insensitive traffic models for communication networks. Discrete Event Dynamic Systems, 17(3):405–421, 2007. [BP02] T. Bonald and A. Proutière. Insensitivity in processor-sharing networks. Per- formance Evaluation, 49(14):193 – 209, 2002. [BP03] T. Bonald and A. Proutière. Insensitive bandwidth sharing in data networks. Queueing Syst. Theory Appl., 44(1):69–100, 2003. [BP04] T. Bonald and A. Proutière. On stochastic bounds for monotonic processor sharing networks. Queueing Syst. Theory Appl., 47(1/2):81–106, 2004. [Bur56] P. Burke. The output of a queuing system. Operations Research, 4(6):pp. 699–704, 1956. [DC99] F. Dufour and O. Costa. Stability of piecewise-deterministic Markov pro- cesses. SIAM J. Control Optim., 37(5):1483–1502 (electronic), 1999. 86 [DMO03] M. Draief, J. Mairesse, and N. O’Connell. Joint Burke’s theorem and RSK representation for a queue and a store. pages 69–82 (electronic), 2003. [dVLK99] G. de Veciana, T. Lee, and T. Konstantopoulos. Stability and performance analysis of networks supporting services with rate control - could the internet be unstable? INFOCOM, pages 802–810, 1999. [Erl09] K. Erlang. Sandsynlighetsregningog telefonsamtaler (in danish). Nytt tidsskrift for Matematik B, (20), 1909. [Erl18] K. Erlang. Solution of some problems in the theory of probabilities of signifi- cance in automatic telephone exchanges. The Post Office Electrical Engineers Journal, (10), 1918. [Fer96] P. A. Ferrari. Limit theorems for tagged particles. Markov Process. Related Fields, 2(1):17–40, 1996. [Fer04] P. L. Ferrari. Polynuclear growth on a flat substrate and edge scaling of goe eigenvalues. Communications in Mathematical Physics, 252(1-3):77–109, 2004. [FF94] P. A. Ferrari and L. R. G. Fontes. The net output process of a system with infinitely many queues. Ann. Appl. Probab., 4(4):1129–1144, 1994. [FM06] P. A. Ferrari and J. Martin. Multiclass processes, dual points and m/m/1 queues. Markov Processes and Related Fields, 2006. [FM07] P. A. Ferrari and J. Martin. Stationary distributions of multi-type totally asymmetric exclusion processes. The Annals of Probability, 35(3):pp. 807– 832, 2007. [FM09] P. A. Ferrari and J. Martin. Multiclass Hammersley-Aldous-Diaconis process and multiclass-customer queues. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):250–265, 2009. [FW84] M. Freidlin and A. Wentzell. Random perturbations of dynamical systems. Springer, 1984. [Ham72] J. M. Hammersley. A few seedlings of research. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. Cali- fornia, Berkeley, Calif., 1970/1971), Vol. I: Theory of statistics, pages 345– 394. Univ. California Press, 1972. 87 [Har90] M. Harrison. Brownian Motion and Stochastic Flow Systems. Krieger Pub Co, 1990. [HW90] M. Harrison and R. Williams. On the quasireversibility of a multiclass brow- nian service station. The Annals of Probability, 18(3), 1990. [Jon10] M. Jonckheere. Introduction to Stochastic Networks. Lecture notes, course given at the Universidad de Buenos Aires, 2010. [Kal02] O. Kallenberg. Foundations of modern probability. Springer, 2002. [Kel79] F. Kelly. Reversibility and Stochastic Networks. Wiley, 1979. [KMT98] F. Kelly, A. Maulloo, and D. Tan. Rate control for communication networks: Shadow prices, proportional fairness and stability. The Journal of the Opera- tional Research Society, 49(3):237–252, 1998. [Lig85] T. Liggett. Interacting Particle Systems. Springer, 1985. [LS77] B.F Logan and L.A Shepp. A variational problem for random young tableaux. Advances in Mathematics, 26(2):206 – 222, 1977. [LSD10] D. Leith, V. Subramanian, and K. Duffy. Log-convexity of rate region in 802.11e wlans. IEEE Communications Letters, 14(1):57–59, 2010. [Mar06] J. Martin. Last-passage percolation with general weight distribution. Markov Process. Related Fields, 12(2):273–299, 2006. [Mas07] L. Massoulié. Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab., 17(3):809–839, 2007. [MP95] T. Mountford and B. Prabhakar. On the weak convergence of departures from an infinite series of ·/M/1 queues. Ann. Appl. Probab., 5(1):121–127, 1995. [MP10] J. Martin and B. Prabhakar. Fixed points for multiclass queues. Arxive: 1003.3024v1, 31, 2010. [MR02] L. Massoulié and J. Roberts. Bandwidth sharing: objectives and algorithms. IEEE/ACM Trans. Netw., 10(3):320–328, 2002. [MT93] S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, 1993. [MW00] J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Trans. on Netw., 8(5):556–567, 2000. 88 [OY01] N. O’Connell and M. Yor. Brownian analogues of Burke’s theorem. Stochastic Process. Appl., 96(2):285–304, 2001. [Pro03] A. Proutiére. Insensibilité et bornes stochastiques dans les réseaux de file d’attente. Application à la modélisation des réseaux de télécommunications au niveau flot. PhD Thesis, École Polytechnique, 2003. [PS00] M. Prähofer and H. Spohn. Statistical self-similarity of one-dimensional growth processes. Phys. A, 279(1-4):342–352, 2000. Statistical mechanics: from rigorous results to applications. [PS04] M. Prähofer and H. Spohn. Exact scaling functions for one-dimensional sta- tionary kpz growth. Journal of Statistical Physics, 115(1-2):255 – 279, 2004. [Roc70] T. Rockafellar. Convex analysis, volume 28. Princeton landmarks in mathe- matics, 1970. [SN01] P. Salminen and I. Norros. On busy periods of the unbounded brownian storage. Queueing Systems, 39:317–333, 2001. [Sto07] K. Stordahl. The history behind the probability theory and the queuing theory. Telektronikk, (2):123–140, 2007. [SW95] A. Shwartz and A. Weiss. Large Deviations for performance analysis. Queues, communication and computing. Chapman & Hall, 1995. [UK11] M. Uchida and J. Kurose. An information-theoretic characterization of weighted -proportional fairness in network resource allocation. Information Sciences, 181(18):4009 – 4023, 2011. [VK77] A.M. Vershik and S.V. Kerov. Asymptotics of the plancherel measure of the symmetric group and the limiting form of young tables. Soviet Math. Dokl., 18:527–531, 1977. [Wal11] N. Walton. Insensitive, maximum stable allocations converge to proportional fairness. Queueing Systems, 68(1):51–60, 2011. [Whi02] W. Whitt. Stochastic Process Limits. Springer, 2002. [Zac07] S. Zachary. A note on insensitivity in stochastic networks. Journal of Applied Probability, 44(1):238–248, 2007.