Bideratze-algoritmo

Bideo hau Ikusgela proiektuaren parte da. Bideoak dituzten artikulu guztiak ikus ditzakezu hemen klik eginez gero.

Algoritmoa zer den eta nola eragiten digun ulertzeko bideoa.

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

Erreferentziak

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

Kanpo estekak

Datuak: Q22725
Multimedia: Routing / Q22725