Karga-banaketa zerbitzari-multzoetan

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

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.