4.5. LINK STATE ROUTING ALGORITAM

Drugi od algoritama iz skupine dinamičkih algoritama zove se link state routing algoritam. Za razliku od prethodno opisanog algoritma, ovaj je otišao još jedan korak naprijed, te svoje odluke ne bazira samo na temelju vremena kašnjenja već dodatno uzima u obzir i kapacitet komunikacijskih linija . Na slici je dana topologija mreže uz koju je vezan primjer algoritma.

Slika 7. Topologija mreže za primjer ovog algoritma.

Ideja i sam postupak samog algoritma može se rastaviti u pet dijelova :

1 Faza. Na samom početku kada se mreža prvi puta podigne svaki od routera ima zadatak da sazna tko su mu njegovi prvi susjedi. Oni to čine tako da jednostavno na sve svoje izlazne linije pošalju specijalne HELLO pakete i čekaju povratnu informaciju od svakog od susjeda. Kada susjedni router primi jedan takav paket on odmah šalje povratni paket kojim se identificira onome tko ga je prozvao.

2 Faza. Ovaj algoritam zahtjeva da svaki od routera zna točno ili bar približno procjenu koliko je kašnjenje do svakog od njegovih susjeda. To saznaju na sličan način kao i u prethodnom algoritmu, tako da svim susjedima šalju specijalne ECHO pakete, i čekaju dok ne prime odgovor. Na temelju proteklog vremena oni sanaju koliko iznosi to kašnjenje, i pamte ga. Za još točniju procjenu može se poslati više test paketa jedan za drugim i onda uzeti srednju vrijednost svih izmjerenih veličina.

3 Faza. U sljedečem koraku svaki od routera ima zadatak da konstruira pakete na temelju primljenih podataka. Svaki od paketa u svome zaglavlju sadrži identifikaciju pošiljaoca, redni broj , i podatak o "starosti" paketa. To nije veliki problem samo je pitanje koliko često je potrebno konstruirati te pakete. Oblik tih paketa prikazan je na sljedečoj slici.

Slika 8. Link state paketi

4 Faza. U ovoj fazi se ovako konstruirani paketi distribuiraju po cijeloj mreži . Za distribuciju paketa koristi se statički flooding algoritam opisan u točki 4.2. Za kontrolu i ograničavanje beskonačnog lutanja paketa po mreži, što je jedan od ključnih problema ovog algoritma svaki paket sadrži redni broj koji se povečava za jedan za svaki novi konstruirani paket.

Na temelju tog broja svaki router kada primi paket donosi odluku da li će se paket dalje proslijediti ili odbaciti ovisno o tome da li je već prije bio viđen ili ne. Ukoliko je redni broj primljenog paketa manji od rednog broja paketa koji je posljedni prosljeđen novi paket je jednostavno odbačen.

Do problema može doči ukoliko neki od routera iz nekog razloga ispadne iz mreže, jer će u tom slučaju izgubiti korak u pračenju paketa koj je dotad "vidio". Poteškoče također mogu nastati ukoliko se krivo protumači redni broj jednog od primljenog paketa, jer to može prouzročiti krivo tumačenje buduče pristiglih paketa. Ovi problemi se rješavaju tako da svaki paket sadrži polje age (starost), koje se smanjuje svake sekunde, i pri svakom prolasku preko nekog od routera. Kada ovo polje dođe do vrijednosti nula, paket se odbacuje. Za smanjenje mogučnosti pogreške svi link state paketi se potrđuju. U tablici se može vidjeti primjer kako izgleda interna struktura u routeru B nakon primitka određenih link state paketa. Tablica također sadrži dvije grupe po tri zastavice, za svaku izlaznu liniju po jedna. Te zastavice sadrže informacije koje pakete i na koje linije treba proslijediti, a koje potvrditi.

Slika 9. Interni spremnik za router B (konstruiran na temelju primljenih paketa)

5 Faza. U posljednoj fazi kada je router akumulirao ovakav set link state paketa ,on uz pomoč nekih od prije opisanih algoritama (npr. algoritam najkračeg puta) računa optimalne puteve do pojedinih destinacija, i takve podatke interno pohranjuje. Nedostatak ovog algoritma je potreba za velikim memorijskim prostorom po routeru. Svaki od routera mora sadržavati veličinu memorije proporcionalnu broju routera u cijeloj mreži, što za velik broj radnih stanica može postati problem. Drugi problem može se javiti ako dođe do pogrešaka prilikom prosljeđivanja ili primanja paketa, jer se tada stvara kriva slika podmreže, a samim time i cijeli niz nivih problema.