Algoritmi

Postoji više različitih algoritama za pronalaženje najboljeg puta između dva čvora povezanog grafa.

Dijkstrin algoritam

Zbog svojstava da je brzina prijenosa obrnuto proporcionalna intenzitetu prometa u mreži, za najbrži put treba odabrati onaj kod kojeg je suma intenziteta prometa u pojedinim granama najmanja. Problem je dakle jednak problemu najkraćeg puta ako intenzitete prometa shvatimo kao udaljenosti.

Općenito problem najkraćeg puta bavi se problematikom prijenosa informacije ili energije od ishodišta do odredišta ili između neka druga dva čvora u mreži. Postoji nekoliko metoda koje rješavaju problem najkraćeg puta, između kojih će izbor ovisiti o karakteristikama mreže.

Za razliku od nekih drugih metoda koje ne podržavaju petlju ovdje to nije ograničenje, jedino ograničenje jest da udaljenosti na granama moraju biti pozitivne. Postupak teče ovako:

Formiraju se dva skupa uređenih parova S i T. Svaki uređeni par sastoji se od oznake čvora ci i udaljenosti ui od tog čvora do ishodišta. U koraku inicijalizacije, u skup S stavlja se ishodište, dok se svakom čvoru iz T pridružuje direktna udaljenost od ishodišta, ili neizmjerno ako ne postoji grana koja spaja taj čvor s ishodištem. U skup S prebacuje se element iz T s najmanjom udaljenošću ui. Ako se uspostavi da je za neki čvor iz T udaljenost od ishodišta preko prebačenog čvora manja od njegove dotad izračunate udaljenosti, udaljenost se modificira. Postupak se ponavlja dok ima elemenata u T.

Postupak se može opisati algoritamski:

Bellman-Ford algoritam

Označimo s D(i,j) udaljenost i-tog čvora od j-tog čvora, a s d(i,j) udaljenost od čvora i do čvora j. Dinamički program koji koristimo je:

Najbolji put započinje u čvoru i i ide preko susjednih čvorova k za koje je udaljenost najmanja. Druga jednadžba se obično ograničava samo na one k koji odgovaraju susjedima čvora i. Jednostavno objašnjenje je da svaki čvor traži susjeda koji je najbliži traženom odredištu.

RIP i problem višestrukog horizonta

RIP (Routing Information Protocol) spada u klasu algoritama koji se temelje na vektorima udaljenosti (distance vector algoritam). Nazivaju se još i Ford-Fulkerson ili Bellman-Ford algoritmi. Za potpuni opis RIP-a pogledajte rfc1058.

Protokol je zamišljen za mreže umjerene veličine u kojma je najdulji put sadrži manje od 16 čvorova. Ovo ograničenje proizlazi iz činjenice da se protokol oslanja na "brojanje do beskonačnosti" (u ovom slučaju 16) za rješavanje nekih situacija, prvenstveno problema petlji i promjena topologija mreže.

Problem s promjenom topologije mreže uzrokovan je time što najprije susjedni čvorovi uoče promjenu, dok ostali čvorovi u mreži još pamte staru topologiju. Nakon što su susjedni čvorovi uočili promjenu, čvorovi koji su vezani na njih će biti obaviješteni o promjeni, ali svi ostali čvorovi još pamte staru topologiju. Za svaki čvor u mreži možemo reći da ima svoj vlastiti horizont, tj. pamti neku topologiju mreže koja ne mora odgovarati stvarnom stanju. Problem se rješava uvođenjem "beskonačnosti", točnije, odabiremo neku udaljenost koja je veća od najveće udaljenosti koju možemo očekivati u nekoj mreži (za RIP je odabrano 16). Svi putovi koji su veći od 16 su neispravni i kao takvi se ne koriste. Za beskonačnost je poželjno odabrati što manji broj zbog ubrzavanja trajanja prijelaznog stanja uzrokovanog promjenom topologije mreže. Naime, ako određeni čvor postane nedostupan, prvi susjed postavlja udaljenost na 16 (beskonačno) i time označuje neispravnost puta. Čvorovi koji će sljedeći saznati za promjenu topologije izmjenjuju informacije međusobno i s prvim susjedom. Označimo ih s A i B. Za čvor A može se dogoditi sljedeća situacija: Informacija o neispravnosti puta preko prvog susjeda je primljena prva i udaljenost je postavljena na 16. Čvor B je poslao informaciju o svom putu do nedostupne mreže prije nego što je primio obavijest od prvog susjeda, i čvor A sada mijenja put do nedostupne mreže tako da vodi preko B. No primijetimo da je udaljenost tog puta sada veća nego što je bila prije. Dakle, može se uspostaviti petlja međusobnih prijevara, ali se ukupna udaljenost svaki put povećava, što konačno dovodi do udaljenosti 16 (brojanje do beskonačnosti) i točnog označavanja puta kao neispravnog.

Zbog ubrzanja ovih prijelaznih pojava koriste se dvije jednostavne metode koje onemogućuju prevare u petlji između dva susjedna čvora. To su jednostavni razdvojeni horizont (simple split horizon) i razdvojeni horizont s beskonačnim povratom (split horizon with poisoned reverse). Kod jednostavnog razdvojenog horizonta čvor A izostavlja putove koje je naučio od B u informacijama koje šalje čvoru B, a kod razdvojenog horizonta s beskonačnim povratom čvoru B se vraća informacija o putovima naučenim od njega ali s udaljenostima postavljenim na beskonačnu vrijednost. Druga metoda se može koristiti i kada se informacije šalju svim čvorovima (brodacast), a ne samo jednom.

Literatura

Kalpić, D., Mornar V. Operacijska Istraživanja. DRIP 19, Biblioteka informacijsko društvo. Zeus, Zagreb, 1996.

C. Hedrick. Routing Information Protocol. Network Working Group. Request for Comments: 1058. 1988.

Natrag na mrežu...

Dokumentacija i kod...