Répartition des charges dans les groupes de serveurs

Doncel Vicente, Josu

LAAS-CNRS laborategiko doktoregaia Okzitaniako Tolosa, Frantzia

La distribution de la charge dans les systèmes informatiques actuels est devenue un sujet de grande importance. La complexité et la gigantesque de ces systèmes font que leur comportement ne peut être géré de manière centralisée. Par conséquent, nous présenterons un modèle décentralisé basé sur des routeurs égoïstes et, en utilisant la théorie du jeu, nous contrasterons votre comportement avec la solution optimale. Nous démontrerons que le modèle basé sur des routeurs égoïstes est très proche de la solution optimale. Enfin, nous indiquerons comment nos résultats peuvent être utilisés par des entreprises comme Google ou Facebook.
karga-banaketa-zerbitzari-multzoetan
Ed. -- --- ---- --------

Les réseaux de télécommunications ont considérablement augmenté au cours des dernières décennies. D'autre part, sa complexité augmente à mesure que de nouvelles technologies sont développées. Par conséquent, les réseaux de télécommunications ne peuvent pas être gérés de manière centralisée. Par exemple, Google est considéré comme ayant plus d'un million de serveurs répartis dans différents pays, ce qui démontre l'impossibilité d'une gestion centralisée. Nous pouvons donc affirmer que la gestion des systèmes informatiques repose sur des systèmes distribués. Par conséquent, de nombreux chercheurs travaillent actuellement sur cette question: Le comportement des systèmes distribués par rapport au système centralisé change beaucoup ?

Le modèle mathématique de distribution des charges est présenté dans des groupes de serveurs, répondant à la question du paragraphe précédent. Pour ce faire, nous comparerons deux modèles de distribution de charges: dans le modèle centralisé, d'une part, la distribution de toutes les commandes des clients se fait par un seul routeur; d'autre part, le modèle décentralisé est formé par plusieurs routeurs et chacun d'eux est responsable d'une partie de toutes les commandes.

Cette comparaison sera faite en pensant que les routeurs du modèle décentralisé sont égoïstes. Le routeur égoïste vise à réduire le temps de service des demandes qui lui parviennent. Chaque routeur égoïste a donc pour but de résoudre un problème d'optimisation différent. De plus, les caractéristiques de ces problèmes d'optimisation nous permettent de définir un jeu entre les routeurs eux-mêmes. En tenant compte des routeurs égoïstes, nous pouvons utiliser des résultats basés sur la théorie du jeu.

Mais qu'est-ce que la théorie du jeu? La théorie du jeu est le domaine des mathématiques qui vise à analyser les comportements stratégiques individuels. Le fait que les réseaux de télécommunications soient des systèmes distribués montre que la théorie du jeu est un bon modèle de conception et de recherche de systèmes informatiques, ce qui a fait que de nombreux chercheurs des réseaux de télécommunications se sont intéressés à la théorie du jeu ces dernières années.

Nous avons défini un jeu compétitif sur le modèle décentralisé de distribution de charges, dans lequel chaque routeur peut décider d'envoyer des charges à chaque serveur pour réduire le temps de service de ses demandes. La solution de jeu compétitive est appelée Nash Oreka. Dans notre modèle, Nash Oreka est la solution du jeu. Le coût de l'anarchie (CMI) est utilisé pour mesurer les performances distribuées des systèmes informatiques.

Le coût de l'anarchie est la division entre le pire comportement du Nash Balance et le comportement de la solution optimale. Plusieurs chercheurs ont étudié ces dernières années les CD de distribution de fret. Selon la littérature, le coût de l'anarchie a dans certains cas des valeurs énormes, de sorte que l'on peut conclure que le comportement entre le modèle centralisé et le modèle décentralisé peut être très différent. Nous avons démontré que le coût de l'anarchie n'est pas une mesure appropriée pour comparer le comportement du modèle centralisé et décentralisé de charge de balance. En fait, bien que la valeur du CMI soit élevée, nous verrons que les deux modèles présentent un comportement similaire.

Les caractéristiques d'un groupe de serveurs ont été maintenues fixes et tous les autres paramètres du système ont été modifiés, choisissant parmi eux la plupart des comportements des deux modèles, c'est-à-dire la valeur de l'inefficacité de ce groupe de serveurs. Si l'inefficacité d'un ensemble de serveurs est faible, il peut être conclu pour ce groupe de serveurs qu'il n'y a pas de différences de comportement entre les deux modèles.

Le pire des cas d'inefficacité se produit seulement à un point, dans les autres cas il est proche de la valeur 1.

On a calculé quand le pire des cas d'inefficacité se produit entre tous les groupes de serveurs, c'est-à-dire dans quels cas le coût de l'anarchie apparaît. Par conséquent, quand il y a un serveur rapide et la différence de vitesse entre le serveur rapide et l'inerte est énorme, nous avons obtenu la valeur du coût de l'anarchie. Dans tous les autres groupes de serveurs, il a été observé que la valeur de l'inefficacité est faible.

Nous savons que dans les gigantesques ensembles de serveurs la valeur du CMI est très élevée. En fonction du résultat obtenu, même si la valeur du CMI est très élevée, on constate que la valeur de l'inefficacité d'un ensemble de serveurs (c'est-à-dire la différence entre les comportements du modèle centralisé et décentralisé d'un ensemble de serveurs) est très faible dans tous les groupes de serveurs, sauf dans un seul cas.

Nous croyons que nos résultats ont une application pratique. Des entreprises comme Google, Facebook ou Amazon utilisent un grand nombre de serveurs pour servir leurs clients. Comme la solution centralisée n'est pas toujours implémentée, le modèle décentralisé basé sur des routeurs égoïstes est une bonne opportunité pour ces entreprises. Nos résultats indiquent que si Facebook et Google utilisent des routeurs égoïstes, leur comportement sera proche de la solution optimale du problème de distribution de fret.

Références

Doncel, J.; Jeûne, U.; Brun, O.; Prabhu, B.: "On the Efficiency of Non-Cooperative Load Balancing" Dans Proceedings of IFIP Networking, 2013.
Roughgarden, T.; Tardos, E.: "How bad is selfish routing? ". Journal of the ACM, 49 (2), (2002), 236-259.
Koutsoupias, E.; Papadimitriou, C.H. : Worst-case équilibré. STACS 1999.
Viv, M.; Roughgarden, T.: "The Price of Anarchy in an Exponential Multi-server". Operation Research Letters, 35 (2007) 421-426.
Jeûne, U.; Brun, O.; Prabhu, B.: Price of Anarcy in Non-Cooperative Load Balancing Games. Performance Evaluation, 68 (2011), 1312-1332.

Merci de votre remerciement. Merci

P. Auteurs Brun (LAAS-CNRS), B. Prabhu (LAAS-CNRS) et U. Ayesta (LAAS-CNRS et IKERBASQUE-UPV/EHU) remercie l'assistance technique fournie.

Babesleak
Eusko Jaurlaritzako Industria, Merkataritza eta Turismo Saila