Límites fluidos y problemas de load balancing

Resumen: Muchas aplicaciones utilizan grandes cantidades de servidores alojados en la nube. Los usuarios de una aplicación generan tareas que deben ser distribuidas y ejecutadas por los servidores a medida que llegan al sistema. Un problema de load balancing consiste en determinar cómo deben distribuirse las tareas entre los servidores para minimizar el tiempo promedio que las tareas permanecen pendientes. Estos problemas son desafiantes porque muchas veces deben resolverse con información parcial y respetando restricciones de compatibilidad entre tareas y servidores.

En la práctica, los tiempos entre arribos y de ejecución de las tareas son aleatorios, por lo que el vector que describe la cantidad de tareas en cada servidor es un proceso estocástico. Para simplificar el análisis, se asume que estos tiempos tienen distribución exponencial y se obtiene una cadena de Markov de tiempo continuo. Resultados clásicos sobre load balancing se basan en obtener el límite fluido de este proceso cuando la cantidad de servidores y la tasa de arribos de las tareas tienden a infinito proporcionalmente. Este límite es una ley de grandes números funcional que permite aproximar el comportamiento del proceso por la solución de un sistema infinito de ecuaciones diferenciales. Cuando existen restricciones de compatibilidad no siempre es posible probar límites fluidos y por lo tanto debe recurrirse a otras técnicas.

La charla intentará ser autocontenida y hará énfasis en la intuición por encima de los detalles técnicos. En primer lugar, hablaremos brevemente sobre cadenas de Markov de tiempo continuo y un par de modelos básicos de teoría de colas. Luego, presentaremos algunos resultados clásicos sobre load balancing basados en límites fluidos. Por último, hablaremos de load balancing con restricciones de compatibilidad dadas por un grafo.