Link state smerovacie algoritmy

Obsah

Úvod
LSA algoritmus
Dijkstrov algoritmus
Zoznam literatúry

Úvod

Link state algoritmy(ďalej LSA) sú pomenovaním pre globálne smerovacie algoritmy. Pri globálnom smerovaní má každý smerovač kompletnú informáciu o všetkých smerovačoch v sieti a stave zaťaťenia v sieti. Smerovače zasielajú informácie len o priamo pripojených linkách a neposielajú celú smerovaciu tabuľku. Vhodné sú najmä pre veľké prostredia, ktoré sa často menia. Využívajú sa hlavne v smerovacích protokoloch používaných v IP sieťach.

LSA algoritmus

Pri LSA, každý smerovač vykonáva nasledujúce kroky:

Identifikácia smerovačov, ktoré sú k nim fyzicky pripojené a získanie ich IP adries. Keď smerovač začne pracovať, pošle do siete "HELLO" pakety. Každý smerovač, ktorý obdrží tento paket, odpovie so správou, ktorá obsahuje jeho jedinečný identifikátor ( v IP sieťach IP adresu).
Smerovač meria ďalej čas oneskorenia (prípadne iné dôležité parametre siete ako priemerné zaťaženie) paketov od susedných smerovačov. Dosiahne to tak, že rozpošle do siete echo pakety pre všetkých susedov. Každý sused, ktorý obdrží takýto paket, odošle ako odpoveď echo reply packet. Čas medzi odoslaním echo paketu a prijatím reply paketu vydelí smerovač dvomi a tak odhadne oneskorenie. Tento čas však okrem času potrebného na prenos obsahuje aj čas potrebný na spracovanie paketu a odoslanie odpovede.
Vysielanie informácie obsiahnutej v smerovači iným smerovačom a zároveň prijatie informácií od týchto smerovačov. V tomto kroku si smerovače teda navzájom vymenia informácie a získajú tak prehľad o štruktúre a stave siete. Toto sa deje pomocou záplavového algoritmu, multicastovým vysielaním alebo broadcastovým vysielaním. Toto závisí od konkrétneho smerovacieho protokolu. Informácie si navzájom vymieňajú tzv. link-state paketmi (LSP). Tieto pakety majú nasledovnú štruktúru:
- ID smerovača
- ID jedného zo susedných smerovačov
- váha linky medzi nimi
- sekvenčné číslo
- TTL - time to live
Ak smerovač obdrží LSP, pokúsi sa ho uložiť vo svojej LSP databáze. Ak takýto LSP už v databáze existuje, nevykoná nič. Inak ho uloží do databázy a jeho kópiu rozošle všetkým svojim susedom, okrem toho, ktorý bol zdrojom tohto paketu. Tieto pakety môžu byť posielané periodicky, pri zmene stavu liniek alebo pri kombinácii predošlého.
Nasleduje výpočet najlepšej cesty medzi dvomi uzlami siete. Na tento výpočet sa používa najčastejšie Dijkstrov algoritmus (obr. 1) najkratšej cesty. V tomto algoritme smerovač na základe informácií, ktoré zozbieral, zostaví graf danej siete. V tomto grafe sú znázornené umiestnenia smerovačov a ich vzájomné prepojenia. Každé toto spojenie je ohodnotené váhou. Táto váha môže byť funkciou oneskorenia na danej linke, priemerného zaťaženia alebo môže označovať počet hopov medzi uzlami siete. Ak sa medzi počiatočným a cieľovým uzlom nachádza 2 a viac možných ciest, smerovač pomocou tohto algoritmu určí cestu s najmenšou váhou.

Dijkstrov algoritmus

Pri výpočte najkratšej cesty postupuje Dijkstrov algoritmus nasledovne:

V grafe siete, ktorý vytvoril smerovač si určí zdrojový a cieľový uzol. Označme si ich U₁ a U₂. Z tohto grafu je následne zostrojená tzv. "matica susedov". Súradnice v tejto matici určujú váhu medzi zodpovedajúcimi uzlami. Napríklad [i, j] určuje váhu linky medzi U_i a U_j. Ak medzi týmito uzlami neexistuje priame spojenie, váha spojenia v tejto matici nadobudne hodnotu nekonečna.
Smerovač si vytvorí záznamy stavov (status record set) pre každý uzol v sieti. Každý záznam obsahuje 3 polia:
- Pole predchodcu - obsahuje predchádzajúci uzol
- Pole dĺžky - obsahuje súčet váh od zdrojového uzla až po tento uzol
- Pole návestia - obsahuje stav uzla. Každý uzol môže nadobúdať jeden z dvoch možných stavov: "permanentný" alebo "pokusný."
Smerovač inicializuje parametre týchto záznamov pre všetky uzly a nastaví ich dĺžku na nekonečno a ich návestie na "pokusný".
Smerovač nastaví T-uzol. V našom prípade, ak U₁ je zdrojový T-uzol, smerovač nastaví jeho návestie na "permanentný". Toto návestie sa už nezmení.
Smerovač upraví všetky záznamy pre všetky uzly s návestím "pokusný", ktoré sú priamo spojené s týmto T-uzlom.
Smerovač ďalej prezrie všetky uzly s návestím "pokusný" a vyberie ten, ktorého spojenie s U₁ má najmenšiu váhu. Tento uzol sa potom stane ďalším T-uzlom.
Ak tento uzol nie je cieľový uzol U₂, smerovač sa vráti do bodu 5.
Ak tento uzol je cieľový uzol U₂, smerovač vyberie jeho predchádzajúci uzol zo záznamov a takto pokračuje, kým sa nedostane naspäť do U₁. Takto dostane zoznam uzlov, ktoré určujú najlepšiu cestu z U₁ do U₂.

Tento algoritmus je znázornený aj v animovanej prezentácii tu.

Zoznam literatúry