Limit theorems for continuous time Markov chains and applications to large scale queueing systems

Abstract

This thesis discusses limit theorems for density dependent families of continuoustime Markov chains and their application to the stochastic analysis of large scalecloud computing environments and data centers. On the purely theoretical side, wereview the classic functional strong law of large numbers and central limit theoremdue to Kurtz, which characterize the asymptotic behavior of density dependentfamilies in terms of their drift. In the case of the central limit theorem we provide extensions in two directions: to consider small order perturbations in the transitionrates of the family and non-differentiable drifts. The classic theorems and the latterextensions are used to study the dynamic right sizing of capacity in large scalecloud environments and data centers, aimed at the adjustment of this capacity toan uncertain workload. Under a central queue scheme and Markovian assumptions,we design a policy that eliminates queueing almost completely, at the expense of aslight over-provisioning; ifρthe traffic intensity, then the over-provisioning scales as O(√ρ) whenρ→∞. In this sense our policy automatically adjusts the system’scapacity according to the well-known square root staffing rule.

En esta tesis se estudian teoremas límite para familias de cadenas de Markov de tiempo continuo, así como su aplicación al análisis estocástico de ambientes tipo cloud y data centers. En un comienzo se presentan resultados clásicos debidos a Kurtz, que caracterizan el comportamiento asintóico de estas familias a partir desu drift; a saber, una ley fuerte de grandes números y un teorema central del límite, ambos funcionales. En el último caso obtenemos extensiones en dos direcciones: considerando perturbaciones de pequeño orden en las tasas de transición de la familia y drifts no diferenciables. Los teoremas clásicos y las extensiones anteriores seemplean para estudiar el ajuste dinámico de la capacidad de cómputo de ambientes tipo cloud y data centers de gran escala, orientado a ajustar la capacidad de cómputo a una demanda incierta. Utilizando un esquema de cola centralizada y bajo hipótesis Markovianas, diseñamos una política que evita el encolado de tareas a expensas de un pequeño sobre dimensionamiento de la capacidad de cómputo; si ρ is la intensidad de tráfico, entonces la capacidad ociosa escala como O(√ρ) cuandoρ→ ∞. Eneste sentido nuestra política ajusta automáticamente la capacidad de cómputo del sistema según el conocido criterio de la raíz cuadrada.