Reititys

Reitityksellä tarkoitetaan algoritmista reitin valitsemista. Reititysalgoritmi on perinteisesti se tiedonsiirron protokollapinon verkkokerroksen osa, joka päättää, mihin ulostuloihin sisään tulevat datapaketit lähetetään. Tietoliikenne ohjataan kulkemaan tietoliikenneverkossa reittiä, joka kuluttaa vähiten joitakin resursseja. Näihin resursseihin voi kuulua esimerkiksi palvelun hinta, mutta kaikkein yleisimmin pyritään ohjaamaan liikenne ajallisesti lyhintä reittiä perille. Reititysalgoritmeilla on kaksi reititystapaa: staattinen reititys ja dynaaminen reititys. Staattisessa reitityksessä reitit on ennalta määrätty ja ne tulevat käyttöön, kun reititin käynnistetään. Reitittimen toimiessa reittejä ei päivitetä. Dynaamisessa reitityksessä reititystaulukot muuttuvat topologian ja liikennemäärien muuttuessa. Vaikka topologiassa tai liikennemäärissä ei tapahtuisikaan muutosta, päivitetään reititystaulukoita jatkuvasti tietyin aikavälein. Eri reititysmalleja ovat jokulähetys (anycast), ryhmälähetys (multicast), täsmälähetys (unicast) ja yleislähetys (broadcast).
Tietoliikenneverkossa reititystä hoitavaa laitetta kutsutaan reitittimeksi.
Protokollat.
Protokollat voidaan jakaa reititysprotokolliin, jotka hoitavat reitityksen, sekä reititettäviin protokolliin, joiden tieto kapseloidaan.
Reititettävä protokolla on tietoliikenneprotokolla, joka kuljettaa käyttäjän dataa. Reititettävä protokolla sijaitsee OSI-mallin kolmannella kerroksella, verkkokerroksella. Reititettävää protokollaa ei tule sekoittaa reititysprotokollaan, joka määrittelee reittejä reitittimien välillä. Näitä reittejä pitkin kulkee reititettävien protokollien liikenne.
Esimerkkejä reititysprotokollista ovat:
Esimerkkejä reititettävistä protokollista ovat:
Lyhimmän polun reititys.
Lyhimmän polun reititys (shortest path routing). Kyseisessä mallissa algoritmi laskee lyhimmän reitin kaikkiin muihin reitittimiin. Perusteena voi olla esimerkiksi reitittimien välinen etäisyys ja tarvittavien hyppyjen lukumäärä.
Flooding.
Flooding (eng. flood = tulva) tarkoittaa sitä, että jokainen sisään tuleva paketti lähetetään kaikkiin portteihin, mistä seuraa suuri määrä ylimääräistä verkkoliikennettä. Jotta liikennettä saataisiin vähennettyä, käytetään muun muassa seuraavanlaisia mekanismeja:
Etäisyysvektorireititys.
Etäisyysvektorireititys on yksi eniten käytetyistä reititysalgoritmeista. Mallissa jokaisella reitittimellä on taulukko, josta ilmenee lyhin tunnettu etäisyys jokaiseen kohteeseen. Taulukosta ilmenee myös portti, jota käyttäen lyhyin reitti saavutetaan. Reititin määrittää itse etäisyyden naapureihinsa. Reititystaulukoiden päivitys tapahtuu määräajoin. Päivitetyksessä vierekkäiset reitittimet lähettävät toisilleen omat taulukkonsa, joiden perusteella kukin laskee omat etäisyytensä toisiin. Mallin heikkouksia on sen hidas reagointikyky esimerkiksi reitittimen verkosta poistumiseen.
Linkkitilareititys.
Linkkitilareititys käyttää edellä esiteltyjen tekniikoiden yhdistelmää, jonka ansiosta se saavuttaa paremman tehokkuuden kuin eri tekniikat yksinään. Linkkitilareitityksessä jokainen reititin etsii ja mittaa etäisyyden viereisiin reitittimiin, jonka jälkeen tiedoista luodaan paketti, jossa reititin kertoo kaiken tietonsa. Kyseinen paketti lähetetään kaikille muille reitittimille. Tämän jälkeen reititin voi laskea lyhimmän reitin kaikkiin reitittimiin.
Hierarkkinen reititys.
Hierarkkisen reitityksen on tarkoitus poistaa ongelma joka syntyy, kun verkot kasvavat suuriksi, ja tulee mahdottomaksi laskea etäisyys kaikkiin muihin reitittimiin. Hierarkkisessa reitityksessä reitittimet jaetaan toimialueisiin ja reitittimet tuntevat vain oman toimialueensa muut reitittimet ja linjat, jotka johtavat muihin toimialueisiin. Verkon koon kasvaessa hierarkian monitasoisuus kasvaa. Kamoun ja Kleinrockin mukaan optimaalinen hierarkiatasojen määrä N-reitittimen verkossa on ln N. Vastaavasti reititystaulukkoon tarvitaan tällöin e*ln N riviä.
Kehitteillä oleva rekursiivinen verkkoarkkitehtuuri, RINA, perustuu hierarkkiseen reititykseen. Perinteisissä verkkomalleissa jokaisella kerroksella on omat tehtävänsä, verkkokerroksen hoitaessa reititystä. RINA taas rakentuu identtisistä kerroksista, joista jokainen hoitaa oman reitityksensä.