Bideratze-algoritmo

Bideratze-algoritmoa datu-pakete bidezko komunikazio batean pakete bakoitzak zein ibilbide izan behar duen erabakitzeko prozedura.

Mailakatutako komunikazioan (ikus OSI), sare-mailaren funtziorik nagusia bideratzea da. Datu-paketeek zein irteera-lerrotik joan behar duten, bideratze-algoritmoak erabakitzen du. Alegiazko zirkuituak eta datagrama sareak bideratze prozedura desberdinak erabiltzen dituzte.
Bideratze-algoritmoak bideratzaileak erabiltzen dituzte edo bideratzaile funtzioak dituen software edo hardware gailuak.

 Ezaugarriak 
Bideratze-algoritmo baten ezaugarri desiragarriak:
 Zuzentasuna. Makina guztiak berdintsu tratatu
 Sinpletasuna. Kudeatze erraza
 Egonkortasuna eta Sendotasuna. Denboran zehar egindako aldaketen aurrean edota hutsegiteak egon arren eraginkortasuna mantentzea
 Optimotasuna.
 Adabegi bat adabegi biren arteko ibilbiderik onenaren parte bada, bitarteko adabegitik helburu adabegirako bideak ere ibilbidea optimoa izango da.
 Optimotasun eta zuzentasun helburuen artean oreka lortzea dago auziaren iltzea

Bideratze-algoritmoak bi taldetan sailka daitezke:

 Moldagaitzak edo Estatikoak
 Moldagarriak edo Dinamikoak

 Bideratze estatikoa 

Algoritmo estatikoek ez dituzte kontuan hartzen ez sarearen datu-trafikoa ez eta beraren topologia. Algoritmo estatikoen artean bi aztertuko ditugu: Uholde-algoritmoa (Flooding) eta Sare trafikoaren batezbesteko algoritmoa (Flow-Based)

 Uholde-algoritmoa 
 Datu-paketeak konektatutako linea guztietatik bideratzen ditu.
 Adabegi batek aurretik prozesatzeko pakete bat (errepikatua) jasotzen badu berriz ez du igorriko, baztertu baizik.
 Pakete errepikatu ugari sortzen ditu. Hau ekiditeko, pakete bakoitzari jauzi-kontadore jartzen zaio goiburuan.
 Sarearen erorketaren aurrean oso sendoa da.

 Fluxuan oinarritutako bideratzea (Flow based) 
 Sareko datu-trafikoaren irizpidea jarraituz bideratzen du.
 Itxaron-ilaren teorian oinarritzen da.
 Sarearen topologia zehatza, hots, komunikazio lotura (adabegi) bakoitzaren ahalmen zehatza eta sareko trafikoaren batezbestekoa jakitea ezinbestekoa du. Atzerapen gutxiko ibilbidea zein den jakin daiteke datu hauekin.
 Sareko topologia edo nodoen arteko trafikoan aldaketak egongo balira, ibilbide guztiak berriz birkalkulatuko behar lirateke.

 Bideratze dinamikoa 

Sareko topologiaren eta sare trafikoaren uneko datuen arabera, algoritmo dinamikoek euren bideratze-taulak egokitzen dituzte.
Algoritmo dinamiko erabilienen artean distantzia-bektoreko bideratzea (distance vector routing) eta lotura egoerako bideratzea (link state routing) daude.

 Distantzia-bektoreko bideratzea 
 Helburu (helbide) posible bakoitzarentzako, ezagutzen den denboraren araberako biderik laburrena bideratze-taulan gordetzen du.
 Noizbehinka aldameneko nodoekin informazioa elkar trukatu ondoren bideratze-taulak eguneratzen dira.
 Bideratzaile bakoitzak bideratze-taula bat mantentzen du, non sareko nodo bakoitzeko errenkada bat daukan.
 Nodo bat funtzionatzeari uzten dionean, taulak eguneratzeko oso geldoa da.
 ARPANETek distantzia bektoreko algoritmoa erabiltzen zuen, baina sarearen aldaketen eta hedapenen ondorioz loturen egoerako bideratze algoritmorengatik ordeztu zuten. Honek, linearen banda zabalera aintzat hartzen baitu, aurrekoak ez bezala.

 Loturen egoerako bideratzea 
Bideratzaile bakoitzak burutu beharreko eginkizunen artean daude:

 Zeintzuk diren bere ondoko nodoak eta bere helbideak gorde.
 Ondoko nodo bakoitzera atzerapen denbora neurtu.
 Aurreko informazio berriarekin pakete bat eraiki.
 Bideratzaile guztiei pakete hau bidali, uholde metodoaren bidez.
 Bideratzaile bakoitzarentzako biderik laburrena kalkulatu, sareko nodo guztietatik jasotako taulak kontuan hartuz.

 Bideratze-protokoloak 
Bideratze algoritmoaren araberako protokoloak sortu dira. Hona hemen ezagunenak:

 OSPF (Open Short Path First) barne-pasabideko bideratze-protokoloa. Lotura-egoeran oinarritutako algoritmoa erabiltzen du.

 BGP (Border Gateway Protocol) kanpo-pasabideko bideratze-protokoloa. Distantzia bektorean oinarritutako algoritmoa erabiltzen du.

 Ikus, gainera 
 Bideratzaile
 Bideratze-protokolo
 Bideratze-taula
 Kongestio

 Erreferentziak 
 Andrew S. Tanenbaum, Konputagailu-sareak (3. ed 2002), EHU ed.
 Andrew S. Tanenbaum, Computer Networks (4. ed 2003), Prentice Hall.

 Kanpo estekak 

Kategoria:Sare protokoloak
*
Kategoria:Interneten arkitektura
Kategoria:Algoritmoak