4.ROUTING ALGORITMI

Routing algoritmi su u stvari softwearski programi zaduženi da odlučuju kojim će se putem rutati paketi po mreži. Odluka se donosi za svaki novi paket koji je pristigao do routera u slučaju conectionless veze, ili prilikom uspostavljanja veze ako se radi o conection-oriented vezi .

Postoje dvije osnovne grupe routing algoritama :

1. Neadaptivni algoritmi - ova skupina algoritama ne temelji svoje odluke o tome kojim će putem prosljeđivati pakete na temelju trenutnog stanja u mreži, več su ti putevi pri samom inicijaliziranju mreže fiksno određeni na temelju analiza provedenih za samu mrežu (static routing) .
2. Adaptivni algoritmi – u ovom slučaju algoritmi za donešenje odluka se prilagođavaju trenutnom stanju u mreži tako da se svakih nekoliko ms ispituje stanje mreže . Na temelju tih ispitivanja routeri osvježavaju svoje prijašnje stanje i na taj način u svakom trenutku sadrže rute koje su najoptimalnije (dynamic routing). Mjere za optimalan put mogu biti različite: fizička udaljenost, kašnjenje, broj hopova i sl.).

4.1. Algoritam najkračeg puta ( Shortest Path Routing )

Prvo čemo pokazati jedan od algoritama koji se koriste vrlo često, relativno je jednostavan i spada u grupu neadaptivnih algoritama. Ideja je da se konstruira graf podmreže u kojem će točke predstavljati routere u mreži, a grane koje ih spajaju predstavljati će komunikacijske linije među njima. Recimo još samo da točke u grafu mogu biti potencijalne i stalne. Potencijalne su sve one koje se ispituju i koje će eventualno biti uključene u konačni put, dok su stalne sve one za koje je zaključeno da spadaju u najkrači moguči put te su kao takve več odabrane kao dio toga puta.

Postupak najkračeg puta biti će objašnjen na primjeru koji je prikazan na slici. Pretpostavimo topologiju mreže kao što je prikazano na slici, i pretpostavimo da želimo odrediti najkrači put od točke A do D. Stalne točke su na slici označene ispunjenim kružičem.

Postupak počinje tako da se točka A proglasi stalnom, što je prikazano ispunjenim kružičem. Nakon toga ispituju se sve točke u njenoj okolini, i označavaju se sa dvije labele: udaljenosču do te točke od koje se mjeri udaljenost i koja je to točka. U početku postupka sve točke imaju labelu udaljenosti označenu kao beskonačnu (na slikama označeno kao -). Nakon što su sve okolne (potencijalne) točke označene, ona sa najmanjom labelom udaljenosti proglašava se stalnom i time je uključena u dio konačno konstruiranog puta (ovdje je to točka B). Nadalje se ispituju na identičan način sve točke u okolini točke B i određuje se sljedeča stalna točka koja je najbliža točki B (točka E). Očito je da če na ovaj način biti konstruiran najkrači put do odredišne točke ovisno o kriteriju prema kojem je konstruiran graf mreže. Zgodno je primjetiti da će uvijek biti pronađen upravo najkrači put, čak i ako se u nekom trenutku možda krene pogrešnim putem. Kako to?

Možemo primjetiti da kada se ispituju potencijane točke u okolini zadnje točke koja je prihvačena kao stalna, promatra se njihova trenutna labela udaljenosti. Ukoliko je ta labela manja od sume labela udaljenosti na točki oko koje ispitujemo i udaljenosti do te točke to znači da smo pronašli krači put te se stoga labela te točke prenumerira na novu vrijednost. Za bolje razumijevanje biti će dovoljno pažljivo promotriti svaki korak u primjeru na slici gdje se ovo sve može jasno uočiti. Na kraju možemo na temelju točaka koje su obilježene kao stalne rekonstruirati konačni put, koji je ujedno inajkrači moguči.

Slika 1. Prvih pet koraka u traženju najkračeg puta od A do D.