Bideratze-algoritmo

Wikipedia(e)tik

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.

Eduki-taula

[aldatu] 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

[aldatu] 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)

[aldatu] 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

[aldatu] 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

[aldatu] 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.

[aldatu] 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.

[aldatu] 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

[aldatu] 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.


[aldatu] Ikus, gainera

[aldatu] Erreferentziak