Bideratze-algoritmo

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

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 aldatu

• 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) aldatu

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

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 aldatu

• 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 aldatu

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

• Bideratzaile
• Bideratze-protokolo
• Bideratze-taula
• Kongestio

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