Sareen arteko komunikazioak bizkortzea: bide optimoa aurkitzen duten algoritmoak

CAF-Elhuyar Sariak 2017 - TESIAN OINARRITUTAKO ARTIKULUAREN SARIA

Doncel Vicente, Josu

Matematika Aplikatua eta Estatistika saileko irakaslea

EHU

Zabaldu:
Twitter
Facebook
Emaila

sareen-arteko-komunikazioak-bizkortzea-bide-optimo

1. Irudia: Esperimenturako aukeratutako 19 ordenagailuen kokalekua. Esperimentuaren emaitzaren arabera, ordenagailuen arteko komunikazioak ongi asko hobetu daitezke. Arg. Josu Doncel Vicente

Telekomunikazio-sare modernoetan, hainbat motatako gailuek (ordenagailuak, telefonoak eta tabletak, esate baterako) datu-paketeak bidaltzen dizkiote elkarri; hori egiten dutenean, komunikatu egiten direla esaten dugu. Sare horien erabiltzaileek kalitatezko zerbitzua eskatzen dute (Youtube-ko bideo bat etenik gabe ikustea edo mezu elektronikoak ahalik eta lasterren jasotzea, adibidez), eta kalitatezko zerbitzu hori beteko bada, garrantzitsua da paketeak sareko bide arinenetik, hau da, optimotik, bidaltzea. Bide optimoa aurkitzeko, hala ere, sare osoaren unean uneko egoera ezagutu behar da, eta hori, zoritxarrez, ezinezkoa da, ezin baitugu aurreikusi zenbat erabiltzaile izango diren sarean, ez eta zer zerbitzu eskatuko duten ere.

Artikulu honetan, Bide Optimoaren Aurkikuntza (BOA) deritzon eredu matematikoaren gainean hitz egingo dugu; izan ere, haren bidez, ordenagailu-multzoen arteko komunikazioak bizkortu daitezke. Funtsean, algoritmo optimoa aurkitzean datza, BOA problema modu optimoan ebazten duen algoritmoa aurkitzean, alegia. Algoritmo batek BOA problema modu optimoan ebazten du, baldin eta, sareari buruzko informazio minimoa eskatuz, bi ordenagailuren arteko bide optimoa aurkitzen badu.

BOA problema modu optimoan ebazten duten algoritmoak aztertuko ditugu. Ikusiko dugu badela optimotik gertu dagoen algoritmo bat, eta, halaber, algoritmo hori Google, Facebook edo Amazonen gisako enpresetako ordenagailu-multzoetan erabil daitekeela.

Pakete-bidalketak bizkortzea ordenagailu-multzoetan

BOA problemaren garrantzia erakusten duen esperimentu bat azalduko dugu jarraian. Munduan zehar banatuta dauden 19 ordenagailu aukeratu ditugu (ikusi 1. irudia). Ordenagailu bakoitzetik gainerako ordenagailuetara pakete bat bidali dugu, eta pakete-bidalketa bakoitzaren latentzia neurtu dugu, hau da, zenbat denbora behar izan duen paketeak sorrera-ordenagailutik xede-ordenagailura heltzeko. Paketea bi minututik bi minutura bidali dugu astebetez.

Esperimentuak agerian utzi du askotan kongestio-arazoak izaten direla bi ordenagailuren artean, eta, bidalketak bizkortze aldera, komeni dela paketeak bitarteko ordenagailu batetik igarotzea. Adibidez, esperimentuko neurketen arabera, pakete batek 100 ms behar ditu Irlandatik Kaliforniara joateko, 60 ms Irlandatik São Paulora joateko, eta 20 ms São Paulotik Kaliforniara joateko. Denbora horiei erreparatzen badiegu, erraz ikus dezakegu Irlandatik Kaliforniara doazen paketeak arinago heltzen direla São Paulotik igaroz (80 ms) Kaliforniara zuzenean bidaliz baino (100 ms). Kasu honetan, beraz, komeni da paketeak beste ordenagailu batzuetatik pasatzea, helmugara bizkorrago heltzeko.

BOA problemaren deskribapena

2. Irudia: Artikulu honen ideia nagusiaren azalpena. Bi nodoren artean kongestiorik badago, paketeak bitarteko nodo batetik pasatuz komunikazioa asko bizkortzen da. Arg. Josu Doncel Vicente

Aurreko ataleko esperimentuaren emaitza aintzat hartuz, argi dago ordenagailu-sistemetako komunikazioak hobetu egin daitezkeela, bide zuzenean kongestiorik izanez gero paketeak bitarteko ordenagailuetatik pasaraziz. Sistema horretan paketeak bide arinetik, hau da, bide optimotik pasatzeko, ordea, ordenagailu guztien arteko latentzia kalkulatu behar da, eta, aintzat hartuta n ordenagailuko sistema batean egin beharreko neurketa-kopurua n² ordenakoa dela, n handia bada, ezinezkoa izan liteke hainbeste latentzia kalkulatzea. Beraz, bide optimoa zein den jakitea lortu behar dugu, baina sare osoaren latentziak kalkulatu beharrik gabe.

Jo dezagun sistemako ordenagailu-multzoa n erpineko grafo bat dela, zeinaren erpinak ordenagailuak baitira, eta ertzak ordenagailuen arteko bideak (Internet protokoloak ezarritakoak, hain zuzen). Grafo hori osoa da (alegia, edozein erpinetatik edozein erpinetara, beti ertz bat dago), eta ez-orientatua (A eta B erpinen arteko latentzia eta B eta A erpinen artekoa berdinak dira). Sarean, ertzen balioak (ordenagailuen arteko latentziak) ezezagunak dira, eta haien balioak jakitea ezinbestekoa da bide optimoa zein den jakiteko. Ertz baten balioa jakiteko, kontsulta bat egiten da, eta horrek kostua du. Horiek horrela, BOA problema era optimoan ebazten duten algoritmoek batetik bi erpinen arteko bide optimoa aurkitu behar dute, eta, bestetik, ahalik eta kontsulta gutxien egin behar dituzte hori lortzeko, kostua txikia izan dadin.

BOA problema ebazten duten algoritmoak

3. Irudia: (S, T ) ertza besterik kontsultatzen ez duen algoritmoa. Arg. Josu Doncel Vicente

BOA problema ebazten duen algoritmoak bide optimoa aurkitu arte kontsultatzen ditu grafoaren ertzen balioak. Demagun, esaterako, bost erpineko grafo oso batean S eta T erpinen arteko bide arinena aurkitu nahi dugula, ahalik eta kontsulta gutxien eginez (adibide honetan, beraz, bide optimoa bide arinena da). Algoritmoak, lehenik, S eta T erpinen arteko ertzaren balioa, hau da, (S, T) ertzaren balioa kontsultatzen du. Ertz hori besterik kontsultatu ezean, algoritmoak ez daki benetan hori denentz bide arinena: (S, A) ertzaren eta (A, T) ertzaren balioak, adibidez, ez ditu kontsultatu, eta baliteke bide arinena A erpinetik igarotzea. Ez du, beraz, BOA problema ebatzi, eta, horregatik, kontsultak egiten jarraitu behar du bide optimoa aurkitzeko.

4. Irudia: Bide optimoa aurkitzeko bederatzi kontsulta egiten duen algoritmoa. Arg. Josu Doncel Vicente

BOA problema ebazten duen algoritmo bat 4. irudian irudikaturik dago. Algoritmo horrek, (S, T) ertza ez ezik, beste 8 ertz ere kontsultatzen ditu, eta, behin bide arinena aurkitzen duenean, ez du kontsulta gehiago egiten. Kontsultatutako ertzen balioak aintzat hartuta, bide arinena (S, A, T) bidea da, hau da, S, A eta T erpinetatik pasatzen dena; izan ere, (S, A) eta (A, T) ertzen balioa 6 denez, bide arinenaren balioa 12 da, eta S erpinetik T erpinera doazen gainerako bide guztiek balio handiagoa duen ertzen bat dute; beraz, bide laburrenak baino balio handiagoak dituzte.

Algoritmo hori, hala ere, BOA problema ebazteko baliagarria den arren, ez da, agian, algoritmo optimoa; izan ere, beste algoritmo batek zazpi ertzen balioak soilik kontsultatuz lor dezake bide arinena aurkitzea (5. irudian). Hala bada, BOA problema era optimoan ebazteko, zazpi kontsultako algoritmoa baliatu behar da.

BOA problema ebazten duen algoritmo bat optimotik gertu dagoen jakiteko, kontsulta-arrazoia erabiltzen da. Algoritmo baten kontsulta-arrazoia zatiketa bat da: algoritmo horrek egindako kontsulta-kopurua zati algoritmo optimoaren kontsulta-kopurua. Adibidez, 4. irudian agertzen den algoritmoaren kontsulta-arrazoia 9/7 da, algoritmoak bederatzi ertzen balioak kontsultatzen dituelako BOA problema ebazteko, eta algoritmo optimoak, ordea, zazpi; algoritmo bat ez da optimoa haren kontsulta-arrazoia bat baino handiagoa bada.

Algoritmo optimoaren bila

5. Irudia: BLA problema era optimoan ebaz- ten duen algoritmoa. Bide laburrena aurkitzeko, zazpi kontsulta egiten ditu. Arg. Josu Doncel Vicente

Ikusi dugu aurreko ataleko adibiderako badagoela algoritmo optimo bat, hots, kontsulta-kopuru minimoa eginez bide optimoa aurkitzen duen algoritmo bat, eta horrek bidea eman diezaguke ondorioztatzeko algoritmo hori optimoa dela edozein grafo osorentzat. Gure analisien arabera, ordea, ondorio hori ustela da. Izan ere, guk frogatu dugu ez dagoela ezein algoritmorik n erpineko grafo oso guztientzat optimoa denik. Alegia, algoritmo baten kontsulta-arrazoia, grafo batean, 1 izan daiteke (hau da, era optimoan ebazten du algoritmoak BOA problema) eta beste batean, berriz, haren kontsulta-arrazoia 1+ 0.25*n – 0.125*n² da; alegia, bat baino hertsiki handiagoa da.

Gure helburua da n erpineko grafo oso orotan BOA problema modurik onenean ebazten duen algoritmo bat aurkitzea. Gure ikerketan, BOA problema ebazten duen algoritmo bat asmatu dugu. Guk frogatu dugu algoritmo horrek gehien jota 2n – 1 kontsulta behar duela BOA problema ebazteko, eta algoritmo optimoak, aldiz, n baino ez. Horrek esan nahi du haren kontsulta-arrazoia 2 -1/n dela grafo guztietan, hau da, 2tik behekoa, grafo teorian ezagunak diren beste algoritmo batzuena baino txikiagoa.

Algoritmoaren deskribapena:

Biz D = {s,t}, u₁= s eta u₂ = t

Bide optimoa aurkitu ezean,

Kontsultatu (u₁, v) eta (v, u₂), non v ez dagoen D multzoan.

Eguneratu u1: D-ko erpin guztietatik s erpinera bide arinena duena.

Eguneratu u2: D-ko erpin guztietatik t erpinera bide arinena duena.

Gehitu u₁ eta u₂ erpinak D multzora.

Saiatu bide optimoa aurkitzen.

Alegia, grafo-teoriako algoritmo batzuk ere aztertu ditugu n erpineko edozein grafo osotan, eta, algoritmo horien kontsulta-arrazoia, gure analisien arabera, n ordenakoa izatera hel daiteke: muturreko kasu batzuetan, grafo-teoriako algoritmook ertz guztien balioa kontsultatu behar dute, hau da, n² ertz. Algoritmo optimoak, aldiz, n ertz kontsultatzen du bide optimoa aurkitzeko. Beraz, haien kontsulta-arrazoia n ordenakoa da, alegia, gure optimotik gertu dagoen gure algoritmoarena baino askoz handiagoa, zeina, esan bezala, 2tik beherakoa baita.

Emaitzak inplementatzen: Google, Facebook eta Amazon

Gure ikerketaren emaitzak, gure ustez, telekomunikazio-sare modernoen komunikazioak hobetzeko erabil daitezke. Google, Facebook, Amazon eta haien gisako enpresek ordenagailu-multzo handiak erabiltzen dituzte bezeroei zerbitzua emateko (adibidez, Googlek, ustez, milioi bat zerbitzari baino gehiago ditu, hainbat herrialdetan banatuak).

Enpresa horien bezeroek kalitatezko zerbitzua eskatzen dute; horregatik, enpresa horientzat oso garrantzitsua da komunikazio bizkorrak gauzatzea. Hori lortzeko, ezinbestekoa dute sarearen bide optimoa zein den jakitea. Gure ustez, aurkeztu dugun algoritmoa erabiliz, aukera izango dute sarearen egoera modu arrazoizko batean ezagutzeko. Izan ere, algoritmo hori tarteko dela, optimotik gertu dago, kasurik txarrenean ere, sarearen egoera jakiteko egin behar den ahalegina.

Bibliografia

[1] I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension
and provably ecient shortest path algorithms. Journal of the ACM, 63(5):41:1{41:26, Dec.
2016.
[2] A. Gibbons. Algorithmic graph theory. Cambridge University Press, 1985.
[3] M. Harchol-Balter. Performance Modeling and Design of Computer Systems. Cambridge
University Press, 2013.
[4] P. G. Harrison and N. M. Patel. Performance Modelling of Communication Networks and
Computer Architectures. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA,
1st edition, 1992.
[5] S. E. Schaeer et al. Algorithms for nonuniform networks. Helsinki University of Technology,
2006.
[6] C. Szepesvari. Shortest path discovery problems: A framework, algorithms and experimental
results. In AAAI, pages 550{555, 2004.
[7] M. Van Steen. Graph theory and complex networks: An introduction. Amsterdam, 2010.