Algoritmi za usmerjanje morajo zadostiti naslednjim kriterijem:
- Izbira optimalne poti: na podlagi parametrov, ki jih določi upravljalec
omrežja, morajo usmerjevalniki v omrežju določiti optimalno pot, po
kateri bo
posamezen paket potoval. To je vsekakor najbolj zahtevna in pomembna naloga.
- Enostavnost: algoritem za izmenjavo informacij med usmerjevalniki naj bo
najbolj enostaven (da ne obremenjuje procesne moči usmerjevalnikov) in naj povzroča kar
najmanj
prometa (ki predstavlja nekoristen promet na prenosni poti med
usmerjevalniki).
- Robustnost: algoritmi morajo delovati zanesljivo v vseh pogojih, v katerih se
lahko znajde omrežje.
- Hitra konvergenca algoritma za usmerjanje: pri določanju optimalne poti
sodeljujejo vsi usmerjevalniki. Ko pride v omrežju do izpada katere od komponent omrežja
(modemska zveza, vmesnik na usmerjevalniku, usmerjevalnik,...), morajo vsi usmerjevalniki
dobiti informacijo o tem dogodku in na novo izračunati optimalno pot. V prime
ru, da je algoritem konvergira prepočasi, lahko pride do kroženja
paketov.
- Fleksibilnost: algoritem se mora hitro in na ustrezen način prilagoditi
spremembam v omrežju. Te spremembe so lahko npr.: sprememba prepustnosti in zakasnitve na
določeni povezavi.
Vrste algoritmov za usmerjanje:
statični in dinamični algoritmi
- statični algoritmi so neprilagodljivi, saj se spremenijo le s posegom upravljalca
omrežja in se uporabljajo v enostavnejših omrežjih, ki se le malo spreminjajo
- dinamični algoritmi se sami prilagajajo razmeram v omrežju
centralizirani in distribuirani algoritmi
- centralizirani algoritmi: izbira optimalne poti se računa v centralni napravi, ki
periodično zbira informacije od vseh usmerjevalnikov, izračuna optimalne poti in jim
pošlje tabelo optimalnih poti. Prednost je v tem, da se usmerjevalnikom ni potrebno
ukvarjati z računanjem optimalne poti, poleg tega pa je zagotovljeno, da obstaja le en
izračun optimalne poti. Slabosti pa so, da je celotno omrežje odvisno od izpada ene
naprave, da mora b
iti prepustnost omrežja do te
naprave velika in da usmerjevalniki, ki so v dreveseni topologiji bližje, prej dobijo
novo informacijo o optimalni poteh kot usmerjevalniki, ki so daleč. To lahko v posameznih
primerih povzroči kroženje paketov.
algoritmi, ki dopuščajo eno ali več poti:
- nekateri algoritmi dopuščajo več vzporednih poti po
katerih potujejo paketi med dvema končnima točkama. Ti algoritmi so bolj zahtevni.
Njihova prednost je v tem, da zagotavljajo boljšo prepustnost omrežja in redundanco.
enonivojski in hierarhični algoritmi:
- pri enonivojskih algoritmih vsi usmerjevalniki izmenjujejo
informacijo med seboj.
- pri hierarhičnih algoritmih poteka izmenjava
informacijetako, da imajo nekatere naprave prednost pred ostalimi.
kdo izbere celotno prenosno pot:
- v določenih starejših sistemih je bila izbira prenosne
poti prepuščena postaji, ki je želela poslati sporočilo, medtem ko se danes skoraj
izključno uporablja način, pri katerem je izbira poti prepuščena usmerjevalnikom
izmenjava usmerjevalnih tabel:
- usmerjevalnik pošlje vsem ostalim usmerjevalnikom v
omrežju le tisti del tabele za usmerjanje (link state algoritmi), ki se nanaša le na stanje lastnih povezav. Prednost je
v tem, da težje pride do zank. Slabost pa je, da se pošilja velika količina
informacije, so bolj kompleksni za izračunavanje (potrebna večja procesna moč in več
spomina) in so tako dražji s stališča implementacije. Primeri usmerjevalnih protokolov,
ki uporabljajo ta algoritem: OSPF, IS – IS, DecNet faza V.
- usmerjevalnik pošlje celotno tabelo za usmerjanje le sosednjim usmerjevalnikom (distance
vector algoritmi). Primeri usmerjevalnih protokolov, ki uporabljajo ta algoritem: RIP,
IGRP, DecNet faza IV, RTMP.
Omenili smo, da so algoritmi za usmerjanje namenjeni računanju
optimalne poti. Spoznali smo, katerim kriterijem morajo algoritmi zadostiti in si
pogledali v katerih bistvenih značilnostih se algoritmi med seboj razlikujejo.
Kako pa je s kriteriji na podlagi katerih naj algoritmi računajo
optimalno pot? Skušali bomo odgovoriti na vprašanje, kako algoritem ve, da je določena
pot boljša od druge. Novejši alogritmi navadno kombinirajo med seboj več kriterijev iz
spodnjega seznama:
- Zanesljivost vsake omrežne povezave: določene povezave večkrat izpadejo kot druge. Za
ocenitev zanesljivosti se lahko uporabijo tudi drugi kriteriji. Kriterije navadno vnese
upravljalec omrežja.
- Zakasnitev je eden od najbolj pogosto uporabljanih kriterijev in je odvisna od
prepustnosti povezav, zasedenosti omrežja, nastavitev usmerjevalnikov (npr. prioriteta za
določen tip prometa) in fizične razdalje.
- Prepustnost: večja prepustnost ni zadostno zagotovilo, da bo ta pot optimalna, saj je
potrebno upoštevati še zasedenost povezav.
- Obremenjenost usmerjevalnika: uporabimo lahko kriterije kot so npr. razpoložljiva
in/ali največ
ja zmogljivost CPU, število paketov na sekundo in podobno
MTU: upoštevati je potrebno največjo velikost paketov (Maximum Transfer Unit), ki bodo potovali čez posamezne omrežne povezave. Omejitev
Etherneta 1,5 kB, FDDI-ja 4 kB, medtem ko je pri Token Ringu praktično neomejena.
Strošek posamezne povezave: kot primer naj navedemo, da se bo podjetje, ki želi
poslovati z nizkimi stroški, raje odločilo za uporabo ene od privatnih povezav, čeprav
ima možnost uporabe javnih povezav z manjšo zakasnitvijo.