Repartición de cargas en grupos de servidores

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

• Matematika

As redes de telecomunicacións aumentaron considerablemente nas últimas décadas. Doutra banda, a súa complexidade aumenta a medida que se desenvolven novas tecnoloxías. Por iso, as redes de telecomunicacións non poden ser xestionadas de forma centralizada. Por exemplo, considérase que Google ten máis dun millón de servidores distribuídos por diferentes países, o que demostra a imposibilidade dunha xestión centralizada. Por tanto, podemos afirmar que a xestión dos sistemas informáticos baséase en sistemas distribuídos. Por iso, na actualidade moitos investigadores están a traballar ao redor desta cuestión: cambia moito o comportamento dos sistemas distribuídos respecto ao sistema centralizado?

Preséntase o modelo matemático de distribución de cargas en grupos de servidores, dando resposta á pregunta do parágrafo anterior. Paira iso, compararemos dous modelos de distribución de cargas: no modelo centralizado, por unha banda, a distribución de todos os pedidos dos clientes realízase por un só router; doutra banda, o modelo descentralizado está formado por varios routers e cada un deles encárgase dunha parte de todos os pedidos.

Esta comparación farémola pensando que os routers do modelo descentralizado son egoístas. O router egoísta ten como obxectivo reducir o tempo de servizo das solicitudes que lle chegan. Por tanto, cada router egoísta ten como obxectivo resolver un problema de optimización diferente. Ademais, as características destes problemas de optimización permítennos definir un xogo entre os propios routers. É dicir, tendo en conta os routers egoístas podemos utilizar resultados baseados na teoría do xogo.

Pero que é a teoría do xogo? A teoría do xogo é o campo das matemáticas que ten como obxectivo a análise de comportamentos estratéxicos individuais. O feito de que as redes de telecomunicacións sexan sistemas distribuídos pon de manifesto que a teoría do xogo é un bo modelo de deseño e investigación de sistemas informáticos, o que fixo que moitos investigadores das redes de telecomunicacións interesáronse na teoría do xogo nos últimos anos.

Nós definimos un xogo competitivo no modelo descentralizado de distribución de cargas, no que cada router pode decidir o envío de cargas a cada servidor paira reducir o tempo de servizo das súas peticións. A solución de xogo competitivo denomínase Nash Oreka. No noso modelo, Nash Oreka é a solución do xogo. Paira medir o rendemento distribuído dos sistemas informáticos utilízase o custo da anarquía (CMI).

O custo da anarquía é a división entre o peor comportamento do Nash Equilibrio e o comportamento da solución óptima. Varios investigadores investigaron nos últimos anos o CD de distribución de cargas. Segundo a literatura, o custo da anarquía ten nalgúns casos uns valores enormes, polo que se pode concluír que o comportamento entre o modelo centralizado e o descentralizado pode ser moi diferente. Nós demostramos que o custo da anarquía non é una medida adecuada paira comparar o comportamento do modelo centralizado e descentralizado de carga de balanza. De feito, aínda que o valor do CMI é alto, veremos que ambos os modelos presentan un comportamento similar.

Mantivéronse fixas as características dun grupo de servidores e modificáronse todos os demais parámetros do sistema, elixindo entre eles a maior parte dos comportamentos de ambos os modelos, é dicir, o valor da ineficiencia deste grupo de servidores. Se se demostra que a ineficacia dun conxunto de servidores é baixa, pódese concluír paira este grupo de servidores que non existen diferenzas de comportamento entre ambos os modelos.

O peor dos casos de ineficiencia prodúcese unicamente nun punto, nos demais casos atópase próximo ao valor 1.

Calculouse cando se produce o peor dos casos de ineficiencia entre todos os grupos de servidores, é dicir, en que casos aparece o custo da anarquía. Por tanto , cando hai un servidor rápido e a diferenza de velocidades entre o servidor rápido e o inerte é enorme, obtivemos o valor do custo da anarquía. En todos os demais grupos de servidores observouse que o valor da ineficiencia é baixo.

Sabemos que nos xigantescos conxuntos de servidores o valor do CMI é moi alto. En función do resultado obtido, a pesar de que o valor do CMI é moi elevado, obsérvase que o valor da ineficacia dun conxunto de servidores (é dicir, a diferenza entre os comportamentos do modelo centralizado e descentralizado dun conxunto de servidores) é moi baixo en todos os grupos de servidores, salvo nun só caso.

Creemos que os nosos resultados teñen una aplicación práctica. Empresas como Google, Facebook ou Amazon utilizan un gran número de servidores paira dar servizo aos seus clientes. Dado que a solución centralizada non é sempre implementable, o modelo descentralizado baseado en routers egoístas é una boa oportunidade paira estas empresas. Os nosos resultados indican que si Facebook e Google utilizan routers egoístas, o seu comportamento será próximo á solución óptima do problema de distribución de cargas.

Referencias

Agradecemento

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