Reititys

Wikipedia
Loikkaa: valikkoon, hakuun

Reititysmallit

Reitityksellä tarkoitetaan algoritmista reitin valitsemista. Reititysalgoritmi on se tiedonsiirtoprotokollan 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).

  • Reititystaulukoiden päivitykset voidaan saada:
    • paikallisesti (operaattori muuttaa taulukkoa)
    • viereisiltä asemilta
    • miltä tahansa reitittimeltä

Tietoliikenneverkossa reititystä hoitavaa laitetta kutsutaan reitittimeksi.

Lyhimmän polun reititys[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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:

  • Hyppyjen lkm
    • lukua pienennetään joka hypyllä ja kun luku on 0, paketti hylätään
  • Sekvenssinumerointi
    • jos paketti on tullut jo jostakin portista, se hylätään
  • Selektiivinen tulva
    • paketti lähetetään vain niistä porteista, jotka johtavat oikeaan suuntaan

Etäisyysvektorireititys[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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ä.