Repartiment de càrregues en grups de servidors

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

• Matematika

Les xarxes de telecomunicacions han augmentat considerablement en les últimes dècades. D'altra banda, la seva complexitat augmenta a mesura que es desenvolupen noves tecnologies. Per això, les xarxes de telecomunicacions no poden ser gestionades de forma centralitzada. Per exemple, es considera que Google té més d'un milió de servidors distribuïts per diferents països, la qual cosa demostra la impossibilitat d'una gestió centralitzada. Per tant, podem afirmar que la gestió dels sistemes informàtics es basa en sistemes distribuïts. Per això, en l'actualitat molts investigadors estan treballant entorn d'aquesta qüestió: canvia molt el comportament dels sistemes distribuïts respecte al sistema centralitzat?

Es presenta el model matemàtic de distribució de càrregues en grups de servidors, donant resposta a la pregunta del paràgraf anterior. Per a això, compararem dos models de distribució de càrregues: en el model centralitzat, d'una banda, la distribució de totes les comandes dels clients es realitza per un sol encaminador; d'altra banda, el model descentralitzat està format per diversos encaminadors i cadascun d'ells s'encarrega d'una part de totes les comandes.

Aquesta comparació la farem pensant que els encaminadors del model descentralitzat són egoistes. L'encaminador egoista té com a objectiu reduir el temps de servei de les sol·licituds que li arriben. Per tant, cada encaminador egoista té com a objectiu resoldre un problema d'optimització diferent. A més, les característiques d'aquests problemes d'optimització ens permeten definir un joc entre els propis encaminadors. És a dir, tenint en compte els encaminadors egoistes podem utilitzar resultats basats en la teoria del joc.

Però què és la teoria del joc? La teoria del joc és el camp de les matemàtiques que té com a objectiu l'anàlisi de comportaments estratègics individuals. El fet que les xarxes de telecomunicacions siguin sistemes distribuïts posa de manifest que la teoria del joc és un bon model de disseny i recerca de sistemes informàtics, la qual cosa ha fet que molts investigadors de les xarxes de telecomunicacions s'hagin interessat en la teoria del joc en els últims anys.

Nosaltres hem definit un joc competitiu en el model descentralitzat de distribució de càrregues, en el qual cada encaminador pot decidir l'enviament de càrregues a cada servidor per a reduir el temps de servei de les seves peticions. La solució de joc competitiu es denomina Nash Oreka. En el nostre model, Nash Oreka és la solució del joc. Per a mesurar el rendiment distribuït dels sistemes informàtics s'utilitza el cost de l'anarquia (CMI).

El cost de l'anarquia és la divisió entre el pitjor comportament del Nash Equilibri i el comportament de la solució òptima. Diversos investigadors han investigat en els últims anys els CD de distribució de càrregues. Segons la literatura, el cost de l'anarquia té en alguns casos uns valors enormes, per la qual cosa es pot concloure que el comportament entre el model centralitzat i el descentralitzat pot ser molt diferent. Nosaltres hem demostrat que el cost de l'anarquia no és una mesura adequada per a comparar el comportament del model centralitzat i descentralitzat de càrrega de balança. De fet, encara que el valor del CMI és alt, veurem que tots dos models presenten un comportament similar.

S'han mantingut fixes les característiques d'un grup de servidors i s'han modificat tots els altres paràmetres del sistema, triant entre ells la major part dels comportaments de tots dos models, és a dir, el valor de la ineficiència d'aquest grup de servidors. Si es demostra que la ineficàcia d'un conjunt de servidors és baixa, es pot concloure per a aquest grup de servidors que no existeixen diferències de comportament entre tots dos models.

El pitjor dels casos d'ineficiència es produeix únicament en un punt, en els altres casos es troba pròxim al valor 1.

S'ha calculat quan es produeix el pitjor dels casos d'ineficiència entre tots els grups de servidors, és a dir, en quins casos apareix el cost de l'anarquia. Per tant, quan hi ha un servidor ràpid i la diferència de velocitats entre el servidor ràpid i l'inert és enorme, hem obtingut el valor del cost de l'anarquia. En tots els altres grups de servidors s'ha observat que el valor de la ineficiència és baix.

Sabem que en els gegantescos conjunts de servidors el valor del CMI és molt alt. En funció del resultat obtingut, a pesar que el valor del CMI és molt elevat, s'observa que el valor de la ineficàcia d'un conjunt de servidors (és a dir, la diferència entre els comportaments del model centralitzat i descentralitzat d'un conjunt de servidors) és molt baix en tots els grups de servidors, excepte en un sol cas.

Creiem que els nostres resultats tenen una aplicació pràctica. Empreses com Google, Facebook o Amazon utilitzen un gran nombre de servidors per a donar servei als seus clients. Atès que la solució centralitzada no és sempre implementable, el model descentralitzat basat en encaminadors egoistes és una bona oportunitat per a aquestes empreses. Els nostres resultats indiquen que si Facebook i Google utilitzen encaminadors egoistes, el seu comportament serà pròxim a la solució òptima del problema de distribució de càrregues.

Referències

Agraïment

P. Autors Brun (LAAS-CNRS), B. Prabhu (LAAS-CNRS) i O. Ayesta (LAAS-CNRS i IKERBASQUE-UPV/EHU) agraeix l'assistència tècnica prestada.