Karga-banaketa zerbitzari-multzoetan

Doncel Vicente, Josu

LAAS-CNRS laborategiko doktoregaia Okzitaniako Tolosa, Frantzia

Gaur egungo sistema informatikoetan karga nola banatu garrantzi handiko gai bilakatu da. Sistema horiek oso konplexuak eta erraldoiak direnez, ez dago haien portaera era zentralizatuan kudeatzerik. Hori dela eta, bideratzaile berekoietan oinarritutako eredu deszentralizatua aurkeztuko dugu, eta, joko-teoria erabiliz, haren portaera soluzio optimoarekin alderatuko dugu. Frogatuko dugu bideratzaile berekoietan oinarritutako eredua soluzio optimotik oso gertu dagoela. Bukatzeko, adieraziko dugu nola erabil dezaketen gure emaitza zenbait enpresak, hala nola Google-k eta Facebook-ek.
karga-banaketa-zerbitzari-multzoetan
Arg. -

Telekomunikazio-sareak asko handitu dira azken hamarkadetan. Bestetik, haien konplexutasuna areagotzen ari da teknologia berriak garatzen ari diren neurrian. Hori dela eta, telekomunikazio-sareak ezin dira kudeatu era zentralizatuan. Adibidez, uste da Google-k milioi bat zerbitzari baino gehiago dituela hainbat herrialdetan banatuta, eta horrelakoetan argi dago kudeaketa zentralizatua ezinezkoa dela. Beraz, baiezta dezakegu sistema informatikoen kudeaketa sistema banatuetan oinarritzen dela. Horregatik, ikertzaile asko galdera honen inguruan lan egiten ari dira gaur egun: asko aldatzen da sistema banatuen portaera sistema zentralizatuarekin konparatuz?

Zerbitzari-multzoetan egiten den karga-banaketaren eredu matematikoa aurkeztuko dugu, eta aurreko paragrafoko galderari erantzuna emango diogu. Horretarako, karga-banaketaren bi eredu alderatuko ditugu: eredu zentralizatuan, batetik, bideratzaile bakar batek egiten du bezeroen eskaera guztien banaketa; eredu deszentralizatua, bestetik, zenbait bideratzailez osaturik dago, eta bideratzaile bakoitzak eskaera guztien zati batez arduratzen da.

Eredu deszentralizatuko bideratzaileak berekoiak direla pentsatuz egingo dugu konparaketa hori. Bideratzaile berekoiak berari heltzen zaizkion eskaeren zerbitzu-denbora gutxitzea du helburu. Beraz, bideratzaile berekoi bakoitzak optimizazio- arazo ezberdin bat ebaztea du helburu. Gainera, optimizazio-arazo horien ezaugarriek aukera ematen digute bideratzaile berekoien artean joko bat definitzeko. Hau da, bideratzaile berekoiak kontuan hartuz, joko-teorian oinarritutako emaitzak erabil ditzakegu.

Baina zer da joko-teoria? Banakoen portaera estrategikoen analisia helburu duen matematikaren arloa da joko-teoria. Telekomunikazio-sareak sistema banatuak izanik, argi ikusten da sistema informatikoak diseinatu eta ikertzeko eredu egokia dela joko-teoria, eta, hori dela medio, telekomunikazio-sareetako ikertzaile asko joko-teorian interesatu dira azken urteotan.

Guk joko lehiakor bat definitu dugu karga-banaketaren eredu deszentralizatuan, non bideratzaile bakoitzak zerbitzari bakoitzari zenbat karga bidali erabaki baitezake haren eskaeren zerbitzu-denbora gutxitzeko. Joko lehiakorren soluzioari Nash Oreka deritzo. Gure ereduan, Nash Oreka jokoaren soluzioa den estrategia da. Sistema informatikoek era banatuan duten errendimendua neurtzeko anarkiaren kostua (AK) erabiltzen da.

Nash Orekaren portaerarik okerrenaren eta soluzio optimoaren portaeraren arteko zatiketa da anarkiaren kostua . Zenbait ikerlarik karga-banaketaren AK ikertu dute azken urteotan. Literaturan esandakoaren arabera, anarkiaren kostua k balio erraldoiak ditu zenbait kasutan eta, hortaz, ondoriozta daiteke eredu zentralizatuaren eta deszentralizatuaren arteko portaera oso ezberdina izan daitekeela. Guk frogatu dugu anarkiaren kostua ez dela neurri egokia balantza-kargako eredu zentralizatuaren eta deszentralizatuaren arteko portaera alderatzeko. Izan ere, AKren balioa handia bada ere, ikusiko dugu bi ereduek antzeko portaera dutela.

Zerbitzari-multzo baten ezaugarriak finko mantendu ditugu eta sistemaren beste parametro guztiak aldatu ditugu, eta, haien artean, bi ereduen portaeren alderik handiena aukeratu dugu, hau da, zerbitzari-multzo horren eraginkortasunik eza ren balioa topatu dugu. Hala bada, zerbitzari-multzo baten eraginkortasunik eza txikia dela frogatuz gero, bi ereduen portaeren ezberdintasunik eza ondoriozta dezakegu zerbitzari-multzo horrentzat.

Eraginkortasunik ezaren kasurik okerrena puntu batean baino ez da gertatzen; beste kasuetan 1 baliotik gertu dago.

Zerbitzari-multzo guztien artean eraginkortasunik eza ren kasurik okerrena noiz gertatzen den kalkulatu dugu, hots, zein kasutan ageri den anarkiaren kostua . Hortaz, zerbitzari bizkor bat dagoenean, eta zerbitzari bizkorraren eta geldoaren arteko abiaduren aldea erraldoia denean, anarkiaren kostua ren balioa lortu dugu. Beste zerbitzari-multzo guztietan, berriz, ikusi dugu eraginkortasunik eza ren balioa txikia dela.

Jakin badakigu zerbitzari-multzo erraldoietan AKren balioa oso handia dela. Lortutako emaitzaren arabera, AKren balioa oso handia izanda ere, ikusi dugu zerbitzari-multzo baten eraginkortasunik eza ren balioa (hau da, zerbitzari-multzo baten eredu zentralizatuaren eta deszentralizatuaren portaeren arteko aldea) oso txikia dela zerbitzari-multzo guztietan, kasu bakar batean izan ezik.

Uste dugu gure emaitzek aplikazio praktikoa dutela. Google, Facebook, Amazon eta horiek bezalako enpresek zerbitzari-kopuru handiak erabiltzen dituzte beren bezeroei zerbitzua emateko. Soluzio zentralizatua ez denez beti inplementagarria, bideratzaile berekoietan oinarritutako eredu deszentralizatua aukera ona da enpresa horientzat. Gure emaitzen arabera, Facebook-ek eta Google-k bideratzaile berekoiak erabiltzen badituzte, karga-banaketaren arazoaren soluzio optimotik gertu dagoen portaera izango dute.

Erreferentziak

Doncel, J.; Ayesta, U.; Brun, O.; Prabhu, B.: "On the Efficiency of Non-Cooperative Load Balancing" In 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 equilibria. STACS 1999.
Haviv, M.; Roughgarden, T.: "The Price of Anarchy in an Exponential Multi-server". Operation Research Letters, 35 (2007) 421-426.
Ayesta, U.; Brun, O.; Prabhu, B.: "Price of Anarcy in Non-Cooperative Load Balancing Games". Performance Evaluation, 68 (2011), 1312-1332.

Esker ona

Egileak O. Brun-ek (LAAS-CNRS), B. Prabhu-k (LAAS-CNRS) eta U. Ayesta-k (LAAS-CNRS eta IKERBASQUE-UPV/EHU) emandako laguntza teknikoa eskertzen du.

Idatzi zuk zeuk Gai librean atalean

Gai librean aritzeko, bidali zure artikulua aldizkaria@elhuyar.eus helbidera
Hauek dira Gai librean atalean Idazteko arauak

Babesleak
Eusko Jaurlaritzako Industria, Merkataritza eta Turismo Saila