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 daukalarik
• 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.