Marsruutimine

Marsruutimine on võrguliikluse teekonna valimise toimingute jada võrgus, võrkude vahel või üle mitme võrgu. Marsruutimine toimub paljudes eri tüüpi võrkudes, sealhulgas kanalikommutatsioonvõrkudes, näiteks avalikes telefonivõrkudes (PSTN), ISDN ja arvutivõrkudes (nt Internet).

Pakettkommutatsioonvõrkudes on marsruutimine kõrgemal tasemel otsuste tegemine, mis suunab võrgupaketid nende allikast nende sihtkohta läbi võrgu sõlmede. Pakettide edastamine on adresseeritud võrgupakettide transportimine ühest võrguliidesest teise. Vahesõlmed on tavaliselt mitmesugused võrguriistvaraseadmed nagu ruuterid, sillad, lüüsid, tulemüürid või kohtvõrgu kommutaatorid/lülitid. Tavalised üldkasutatavad arvutid tegelevad ka pakettide edastamise ja suunamisega, hoolimata sellest, et neil tavaliselt puudub selleks spetsiaalne riistvara. Marsruutimisprotsess toimub tavaliselt marsruutimistabelite järgi, mis säilitavad marsruute võrgu eri sihtpunktidesse. Seega on marsruutimistabelite loomine marsruutimiskiiruse seisukohalt väga tähtis ning neid tabeleid hoitakse tavaliselt (ruuteri) mälus. Enamus marsruutimisalgoritme kasutab ainult üht võrgurada. Mitmerajaline marsruutimine lubab kasutada mitut alternatiivset teekonda korraga.

Marsruutimine, mõiste kitsas tähenduses vastandatakse sildamisega (mis eeldab, et sarnased võrguaadressid on võrgus üksteise lähedal). Struktureeritud aadressid võimaldavad kasutada ühte üldisemat marsruutimistabeli reeglit paljude seadmete jaoks. Suurtes võrkudes struktureeritud adresseerimine (marsruutimine) töötab tõhusamalt kui sildamine. Marsruutimisest on saanud dominantne adresseerimisviis vähemalt internetis, sildamist kasutatakse tavaliselt väiksemates võrkudes.

Marsruutimismeetodid

Marsruutimismeetodid
Ainuedastus
Leviedastus
Multiedastus
Suvaedastus
Geoedastus

Marsruutimismeetodid erinevad selle poolest, kuidas sõnumeid transporditakse:

• ainuedastus toimetab sõnumi ühte sõlme;
• leviedastus toimetab sõnumi võrgu kõikidesse seadmetesse;
• multiedastus toimetab sõnumi kõikidesse soovi avaldanud seadmetesse;
• suvaedastus toimetab sõnumi suvalisesse seadmesse, tavaliselt allika suhtes lähimasse;
• geoedastus toimetab sõnumi geograafilisele alale.

Ainuedastus on sõnumiedastuse kõige levinum vorm internetis. See artikkel keskendub neile.

Topololoogiline jaotus

Staatilise marsruutimise puhul väikesed võrgud võivad kasutada käsitsi kirjutatud marsruutimistabeleid. Suuremad võrgud omavad tavaliselt keerulist ehitust mis võib tihti muutuda mis tähendab, et käsitsi kirjutatud marsruutimistabelid on mittemõistlikud.

Dünaamiline marsruutimine üritab lahendada seda probleemi luues marsruutimistabeleid automaatselt, marsruutimisprotokollide alusel, lubades võrgul pea automaatselt vigu ja ummistusi vältida. Dünaamiline marsruutimine on interneti puhul levinuim. Dünaamilisteks marsruutimisprotokollideks on näiteks kaugusvektori marsruutimisprotokoll (RIP), Open Shortest Path First (OSPF) ja Enhanced Interior Gateway Routing Protocol (EIGRP).

Kaugusvektorite baasil algoritmid

Kaugusvektorite algoritmid kasutavad Bellmani-Fordi algoritmi. See lähenemisviis omistab igale ühendusele võrgus mingi "kulu". Seadmed seejärel saadavad infot kasutades kõige madalama hinnaga teekonda.

Sellised algoritmid töötavad väga lihtsalt. Kui seade alles alustab siis teab see ainult enda lähedalolevaid seadmeid ja otsest "kulu" nendega ühendumiseks. (See informatsioon – sihtkohtade nimekiri, kulu teisteni ja järgmine hüpe, et sihtkohani jõuda – ongi põhimõtteliselt see, millest marsruutimistabel koosneb) Iga seade saadab perioodiliselt igale enda naabrile hinnangu kogu kulust iga teise seadmeni millest see teab. Naaberseadmed seejärel võrdlevad seda informatsiooni eksisteeriva informatsiooniga ning lisavad kasuliku enda tabelitesse. Mingiks hetkeks on võrgu iga seadme jaoks teada milline tee on parim.

Kui mõni seade kaob võrgust siis kõik teised seadmed, mis kasutasid seda kui järgmist hüpet kustutavad vastava rea enda marsruutimistabelist ja loovad uue. Need seadmed jagavad uuendatud tabelit ka kõigi lähedalasuvate seadmetega. Lõpuks on kõikidel seadmetel võrgus taas parim teekond iga teise seadmeni, vähemalt nendeni milleni ikka veel kontakteeruda saab.

Link-state-algoritmid

Graaf võrgust on fundamentaalne osa, mida link-state-algoritmide korral kasutatakse. Sellise graafi koostamiseks peab iga lüli võrgus leviedastama informatsiooni enda ühendustest teistega teistele võrgus. Iga lüli koostab seejärel kõige väiksemate "kuludega" teekondade tabeli kasutades levinud lühima tee algoritme, näiteks Dijkstra algoritmi. Tulemuseks on puukujuline graaf, mille alguseks on algusseade, lisaks on iga tee ühest seadmest teise kasutatud algoritmi järgi parim. See graaf seejärel muudetakse marsruutimistabeliks.

Optimeeritud link-state-algoritmid

Link-state-marsruutimisalgoritmi, mida kasutatakse mobiilse ad-hoc võrgu tarbeks, rahvusvaheline tähis on OLSR (optimized link-state routing protocol). OLSR on proaktiivne kasutades "Hello" ja "Topology Control" sõnumeid, et avastada ja levitada link-state-informatsiooni läbi mobiilse ad-hoc võrgu. Kasutades hello sõnumeid, leiab iga sõlmpunkt informatsiooni kahe hüppe kaugusel olevate naabrite kohta ja valib välja teatud hulga multipoint relay-sid (MPRe). MPRid eristavad OLSRi teistest link-state-protokollidest.

Teekonnavalik

Teekonnavalik hõlmab teekondade mingisuguse kindlate võrgundusandmete kasutamist, et ennustada või valida parim teekond.

Võrgunduses arvutatakse mainitud võrgundusnäitaja marsruutimisalgoritmiga ja see võib sisaldada komponentidena näiteks ribalaiust, latentsust, hüpete arvu, teekonna kulu, koormust, MTU-d (maksimaalne edastatav andmeühik), stabiilsust jne. Marsruutimistabel hoiab endas ainult parimaid võimalikke teekondi kui samal ajal link-state või topoloogilised andmebaasid hoiustavad kõike muud informatsiooni.

Marsruutimisanalüütika

Kuna internet ja IP võrgud on äris missioonikriitilised, on kasvamas huvi tööriistade ja muu tehnika vastu mis lubab hoida silma peal marsruutimise omadustel. Vale või vigane marsruutimine põhjustab sageli soovimatut võimsuskadu, flapping-ut ja/või võrgu mittetöötamist. Marsruutimise jälgimiseks kasutatakse marsruutimisanalüütikatööriistu ja -tehnikaid.