Reparto de cargas en grupos de servidores

2014/06/01 Doncel Vicente, Josu - LAAS-CNRS laborategiko doktoregaia Okzitaniako Tolosa, Frantzia Iturria: Elhuyar aldizkaria

• Matematika

Las redes de telecomunicaciones han aumentado considerablemente en las últimas décadas. Por otro lado, su complejidad aumenta a medida que se desarrollan nuevas tecnologías. Por ello, las redes de telecomunicaciones no pueden ser gestionadas de forma centralizada. Por ejemplo, se considera que Google tiene más de un millón de servidores distribuidos por diferentes países, lo que demuestra la imposibilidad de una gestión centralizada. Por tanto, podemos afirmar que la gestión de los sistemas informáticos se basa en sistemas distribuidos. Por ello, en la actualidad muchos investigadores están trabajando en torno a esta cuestión: ¿cambia mucho el comportamiento de los sistemas distribuidos respecto al sistema centralizado?

Se presenta el modelo matemático de distribución de cargas en grupos de servidores, dando respuesta a la pregunta del párrafo anterior. Para ello, compararemos dos modelos de distribución de cargas: en el modelo centralizado, por un lado, la distribución de todos los pedidos de los clientes se realiza por un solo router; por otro lado, el modelo descentralizado está formado por varios routers y cada uno de ellos se encarga de una parte de todos los pedidos.

Esta comparación la haremos pensando que los routers del modelo descentralizado son egoístas. El router egoísta tiene como objetivo reducir el tiempo de servicio de las solicitudes que le llegan. Por tanto, cada router egoísta tiene como objetivo resolver un problema de optimización diferente. Además, las características de estos problemas de optimización nos permiten definir un juego entre los propios routers. Es decir, teniendo en cuenta los routers egoístas podemos utilizar resultados basados en la teoría del juego.

¿Pero qué es la teoría del juego? La teoría del juego es el campo de las matemáticas que tiene como objetivo el análisis de comportamientos estratégicos individuales. El hecho de que las redes de telecomunicaciones sean sistemas distribuidos pone de manifiesto que la teoría del juego es un buen modelo de diseño e investigación de sistemas informáticos, lo que ha hecho que muchos investigadores de las redes de telecomunicaciones se hayan interesado en la teoría del juego en los últimos años.

Nosotros hemos definido un juego competitivo en el modelo descentralizado de distribución de cargas, en el que cada router puede decidir el envío de cargas a cada servidor para reducir el tiempo de servicio de sus peticiones. La solución de juego competitivo se denomina Nash Oreka. En nuestro modelo, Nash Oreka es la solución del juego. Para medir el rendimiento distribuido de los sistemas informáticos se utiliza el coste de la anarquía (CMI).

El coste de la anarquía es la división entre el peor comportamiento del Nash Equilibrio y el comportamiento de la solución óptima. Varios investigadores han investigado en los últimos años los CD de distribución de cargas. Según la literatura, el coste de la anarquía tiene en algunos casos unos valores enormes, por lo que se puede concluir que el comportamiento entre el modelo centralizado y el descentralizado puede ser muy diferente. Nosotros hemos demostrado que el coste de la anarquía no es una medida adecuada para comparar el comportamiento del modelo centralizado y descentralizado de carga de balanza. De hecho, aunque el valor del CMI es alto, veremos que ambos modelos presentan un comportamiento similar.

Se han mantenido fijas las características de un grupo de servidores y se han modificado todos los demás parámetros del sistema, eligiendo entre ellos la mayor parte de los comportamientos de ambos modelos, es decir, el valor de la ineficiencia de este grupo de servidores. Si se demuestra que la ineficacia de un conjunto de servidores es baja, se puede concluir para este grupo de servidores que no existen diferencias de comportamiento entre ambos modelos.

El peor de los casos de ineficiencia se produce únicamente en un punto, en los demás casos se encuentra próximo al valor 1.

Se ha calculado cuándo se produce el peor de los casos de ineficiencia entre todos los grupos de servidores, es decir, en qué casos aparece el coste de la anarquía. Por tanto, cuando hay un servidor rápido y la diferencia de velocidades entre el servidor rápido y el inerte es enorme, hemos obtenido el valor del coste de la anarquía. En todos los demás grupos de servidores se ha observado que el valor de la ineficiencia es bajo.

Sabemos que en los gigantescos conjuntos de servidores el valor del CMI es muy alto. En función del resultado obtenido, a pesar de que el valor del CMI es muy elevado, se observa que el valor de la ineficacia de un conjunto de servidores (es decir, la diferencia entre los comportamientos del modelo centralizado y descentralizado de un conjunto de servidores) es muy bajo en todos los grupos de servidores, salvo en un solo caso.

Creemos que nuestros resultados tienen una aplicación práctica. Empresas como Google, Facebook o Amazon utilizan un gran número de servidores para dar servicio a sus clientes. Dado que la solución centralizada no es siempre implementable, el modelo descentralizado basado en routers egoístas es una buena oportunidad para estas empresas. Nuestros resultados indican que si Facebook y Google utilizan routers egoístas, su comportamiento será cercano a la solución óptima del problema de distribución de cargas.

Referencias

Agradecimiento

P. Autores Brun (LAAS-CNRS), B. Prabhu (LAAS-CNRS) y U. Ayesta (LAAS-CNRS e IKERBASQUE-UPV/EHU) agradece la asistencia técnica prestada.