Reititysalgoritmeja käytetään määrittämään pakettien paras reitti lähteestä kohteeseen, ja ne ovat minkä tahansa reititysprotokollan perusta . Reititysalgoritmien muodostamiseksi verkkoa pidetään graafina. Tässä tapauksessa reitittimet ovat solmuja, ja reitittimien väliset fyysiset viivat ovat vastaavan graafin reunoja. Jokaiselle kaavion reunalle on määritetty tietty numero - hinta, joka riippuu viivan fyysisestä pituudesta, tiedonsiirron nopeudesta viivalla tai viivan hinnasta.
Reititysalgoritmit voidaan jakaa:
ottaa huomioon linjan tilan
Plussat ja miinukset+ paketin verkossa viettämän keskimääräisen ajan pieneneminen
+ kyky mukautua dynaamisesti verkon tilaan -
on tarpeen laskea jatkuvasti uudelleen reititystaulukoita
adaptiivinen keskitetty algoritmi
Plussat ja miinukset
+ RCC :llä (
Routing Control Center) on kaikki
tiedot verkon tilasta, mikä mahdollistaa optimaalisen
päätöksenteon
Solmu poimii tiedot vastaanotetuista paketeista.
Plussat ja miinukset+ ei ruuhkaa
- hidas mukautuminen verkko-olosuhteisiin (konvergenssiaika)
etäisyysvektorialgoritmi , linkin tilan reititys
Plussat ja miinukset+ parempi sopeutuminen
- ylikuormitukset
Älä ota huomioon verkon nykyistä tilaa, kaikki reitit lasketaan ennen verkon käyttöä. Ne puolestaan on jaettu algoritmeihin, jotka ottavat huomioon verkon topologian (virittävä puu, virtauspohjainen reititys) ja eivät ota huomioon (tulva).
Plussat ja miinukset+yksinkertaisuus
+hyviä tuloksia muuttumattomalla topologialla ja kuormalla
-kyvyttömyys reagoida muutoksiin
-matala nopeus heterogeenisissä verkoissa
( eng. adaptiivinen keskitetty reititys )
KuvausVerkossa on ns. Routing Control Center (RCC), joka vastaanottaa kaikilta solmuilta tietoja niiden viereisistä solmuista, jonon pituudesta ja linjakuormasta. RCC:n toimintoihin kuuluu tiedon kerääminen, kullekin solmulle parhaiden reittien laskeminen, reititystaulukoiden laatiminen ja lähettäminen solmuille.
Plussat ja miinukset+RCC:llä on kaikki tiedot ja se voi luoda "ihanteellisia" reittejä
+solmut on vapautettu reititystaulukoiden laskemistarpeesta
-heikko luotettavuus -reititystaulukoiden uudelleenlaskentaa vaaditaan
ajoittain
-virheellinen työskentely erotettujen verkkojen kanssa
-IS vastaanottaa tietoa eri paikoista kertaa -liikenteen keskittyminen
RCC:n lähellä
Jokainen solmu ottaa vain tarpeelliset tiedot vastaanotetuista paketeista. Siten jokainen solmu tietää pakettien lähettäjän ja tämän paketin ohittamien hyppyjen määrän . Sitten tehdään vertailu reititystaulukon tietoihin, ja jos vastaanotetussa paketissa on vähemmän hyppyjä, taulukko päivitetään.
Plussat ja miinukset+ toteutuksen helppous
- ongelmia topologian ja kuorman muuttamisessa -
solmujen välillä ei tapahdu reititystietojen vaihtoa
( Englanninkielinen etäisyysvektori reititys )
KuvausTunnetaan myös nimellä Distributed Bellman-Ford Routing tai Ford Fulkerson Algorithm. Tämä algoritmi on hajautettu, iteratiivinen ja asynkroninen. Sitä voidaan ajatella seuraavasti: "Kerro naapureillesi, miltä maailma näyttää." Jokainen isäntä ylläpitää reititystaulukkoa, jossa on yksi merkintä jokaiselle aliverkon reitittimelle. Taulukko on vektori , joka sisältää 2 komponenttia: valitun suoran ja etäisyyden. Solmu arvioi etäisyyden (hyppyjen lukumäärän, viiveen tai jonon pituuden) jokaiseen naapuriin ja lähettää sen naapureilleen, jotka puolestaan tekevät samoin. Vastaanotetun tiedon seurauksena jokainen solmu laskee reititystaulukon uudelleen. Käytetään RIP -reititysprotokollassa . Sitä käytettiin ensimmäisen kerran ARPANETissa .
AlgoritmiOletetaan, että taulukko on juuri saatu naapuri X:ltä, jossa Xi on X:n arvaus siitä, kuinka kauan kestää päästä reitittimeen i. Jos reititin tietää, että tiedonsiirto X:ään kestää m, niin se tietää myös, että se voi tavoittaa minkä tahansa reitittimen i X:n kautta X i +m:ssä.
Plussat ja miinukset+ itseorganisaatio
+ suhteellisen yksinkertainen toteutus
- huono konvergenssi ("konvergenssi")
- vaikeuksia verkon laajentamisessa
Algoritmia käytettäessä ongelmia syntyy, kun yksi solmuista on irrotettu verkosta - "Count to Infinity" -ongelma (count to infinity).
Ennaltaehkäisy: Split Horizont -algoritmi - "älä kerro minulle, mitä sanoin sinulle"
Reititys linkin tilan mukaanEnglanti Linkkitilan reititys
KuvausAlgoritmi, joka liittyy adaptiivisiin algoritmeihin ja perustuu linkkien tilan analyysiin. Sitä voidaan ajatella seuraavasti: "Kerro maailmalle, keitä naapurisi ovat." Aluksi solmu tuntee vain naapurinsa ja sen niihin yhdistävien linkkien metriikan. Vaihdettaessa tietoja naapurisolmujen kanssa solmu vastaanottaa tietoa verkon topologiasta samalla kun se vaihtaa tietoja vain tapahtuneista muutoksista. Tämän seurauksena jokainen solmu tuntee koko verkon topologian. Sitä sovellettiin ensimmäisen kerran ARPANETiin vuonna 1979 ja se korvasi etäisyysvektorialgoritmin. Siirron syyt olivat:
( Englanninkielinen lähetysreititys )
yksilähetys - 1:1
monilähetys - 1:n
lähetys - 1:* (1:kaikki)
Jokainen paketti sisältää luettelon kaikista kohteista. Jokainen solmu luo kullekin lähtevälle yhteydelle kopion paketista, joka sisältää vain niiden solmujen osoitteet, jotka ovat tavoitettavissa tämän yhteyden kautta.
MulticastingEnglanti monilähetysreititys
Spanning Tree AlgorithmEnglanti ylittävä puu
KuvausVirtaava puu: Graafi, joka ei sisällä silmukoita. Virittävä puu on kaikkien solmujen tiedossa. Tämän mukaisesti jokainen solmu lähettää kopiot paketeista
Paluupolun edelleenlähetys (käänteisen polun tulva)Algoritmi on yksinkertaisin ja ei-adaptiivinen vaihtoehto. Jokainen vastaanotettu paketti välitetään edelleen kaikilla linjoilla paitsi sitä, jonka kautta se vastaanotettiin. Tässä tapauksessa vain lähettäjän tarvitsee tietää koko virittävä puu. Algoritmi: Jokainen reititin tietää polun, jota sen tulee käyttää yksittäislähetyspaketteihin. Kun paketti vastaanotetaan, se tarkistaa, onko paketti vastaanotettu linjalla, jota tavallisesti käytetään yksittäislähetyspaketteihin. Jos kyllä, niin paketti välitetään edelleen kaikilla linjoilla, paitsi sillä, jonka kautta se vastaanotettiin. Muuten paketti pudotetaan.
Käänteinen polkulähetysToisin kuin käänteisen polun edelleenlähetys, paketit lähetetään vain linjoilla, joilla muut solmut vastaanottavat tietoja.
Tämä algoritmi laskee lyhimmän polun puun juuresta solmuihin. Tarkoituksena on luoda joukko solmuja Q, joille optimaalinen reitti on jo määritetty. Operaattori luo reititystaulukoita, jotka ladataan, kun se alustetaan ja joita ei enää muokata. Perustuu Dijkstran algoritmiin .
AlgoritmiLyhin etäisyys A:sta D:hen
+ yksinkertaisuus
+ hyvät tulokset jatkuvalla verkkotopologialla ja kuormalla
Tämä algoritmi on yksi ei-adaptiivisista algoritmeista. Se ottaa huomioon reitittimien välisen etäisyyden lisäksi myös verkon kuormituksen. Hyödyllinen reitin löytämiseen pitkille matkoille, joissa pakettien toimituksessa on pitkiä viiveitä
EsimerkkiAnnettu kaavio kapasiteetille ja liikennematriisille
| linja | λi ( pakettia /sek) |
|---|---|
| AB | 3 (AB) + 7 (ABC) + 7 (BAD) + 4 (BAF) + 3 (BADG) =24 |
| ILMOITUS | 4 (AD) + 2 (ADE) + 2 (ADG) + 5 (ADEH) + 7 (BAD) + 3 (BADG) = 23 |
| AF | 5(AF) + 4(BAF) = 9 |
| eKr | 7(ABC) + 3(BC) + 4(BCH) = 14 |
| OLLA | 3(BE) = 3 |
| CE | 7 (CED) + 5 (CE) + 3 (CEDF) = 15 |
| CH | 4 (BCH) + 5 (CHG) + 3 (CH) = 12 |
| DE | 2 (ADE) + 5 (ADEH) + 7 (CED) + 3 (CEDF) + 2 (DE) + 9 (DEH) + 3 (EDF) + 9 (FDEH) = 40 |
| D.F. | 3(CEDF)+9(DF)+3(EDF)+9(FDEH) = 24 |
| EH | 5(ADEH)+ 9(DEH)+ 1(EHG)+ 2(EH) + 9(FDEH) = 26 |
| FG | 1(FG) = 1 |
| GH | 1 (GH) + 1 (EHG) + 5 (CHG) = 7 |
| DG | 2(ADG) + 3(BADG) + 2(DG) = 7 |
| linja | λi ( pakettia /sek) | µCi (paketteja / s) | T i (msek) |
|---|---|---|---|
| AB | 24 | viisikymmentä | 38.46 |
| ILMOITUS | 23 | viisikymmentä | 37.04 |
| AF | 9 | 37.5 | 35.09 |
| eKr | neljätoista | 25 | 90,91 |
| OLLA | 3 | viisikymmentä | 21.28 |
| CE | viisitoista | 75 | 16.67 |
| CH | 12 | viisikymmentä | 26.32 |
| DE | 40 | viisikymmentä | 100 |
| D.F. | 24 | 25 | 1000 |
| EH | 26 | viisikymmentä | 41,67 |
| FG | yksi | 100 | 10.1 |
| GH | 7 | 62.5 | 18.02 |
| DG | 7 | 62.5 | 18.02 |
| linja | λi ( pakettia /sek) | µCi (paketteja / s) | T i (msek) | Wi_ _ |
|---|---|---|---|---|
| AB | 24 | viisikymmentä | 38.46 | 0,117 |
| ILMOITUS | 23 | viisikymmentä | 37.04 | 0,112 |
| AF | 9 | 37.5 | 35.09 | 0,044 |
| eKr | neljätoista | 25 | 90,91 | 0,068 |
| OLLA | 3 | viisikymmentä | 21.28 | 0,015 |
| CE | viisitoista | 75 | 16.67 | 0,073 |
| CH | 12 | viisikymmentä | 26.32 | 0,059 |
| DE | 40 | viisikymmentä | 100 | 0,195 |
| D.F. | 24 | 25 | 1000 | 0,117 |
| EH | 26 | viisikymmentä | 41,67 | 0,127 |
| FG | yksi | 100 | 10.1 | 0,005 |
| GH | 7 | 62.5 | 18.02 | 0,034 |
| DG | 7 | 62.5 | 18.02 | 0,034 |
Koska saatu arvo on liian suuri, sitä voidaan pienentää korvaamalla polku, jolla on suurin viive DF( Ti , max = 1000ms ) polulla D->G->F
Se on yksinkertaisin reititysalgoritmi tiedon jakamiseen verkon yli. Kun paketti vastaanotetaan, jokainen solmu välittää sen naapurisolmuilleen, paitsi sille, josta paketti tuli.
Tällä algoritmilla on alhainen tehokkuus lisääntyneen verkon kuormituksen vuoksi.
Algoritmin tehokkuuden parantamiseksi käytetään seuraavia menetelmiä:
Algoritmin päätavoitteena on laskea vaihtoehtoiset reitit ja reittikustannukset. Kustannukset ovat vaihtoehtoisen reitin käytön todennäköisyys. Tästä riippuen joka kerta käytetään eri reittiä, mikä johtaa toimittamattomien pakettien määrän vähenemiseen. Tämän menetelmän käyttö tekee tietokoneverkosta erittäin luotettavan. Menetelmää käytetään useimmiten matkaviestinverkoissa, joissa verkon tila saattaa muuttua usein ja joissakin reitittimissä voi olla vikaa.
Englanti Hierarkkinen reititys Yksitasoiset tai hierarkkiset algoritmit. Jotkut reititysalgoritmit toimivat yhden tason avaruudessa, kun taas toiset käyttävät reitityshierarkiaa. Yksikerroksisessa reititysjärjestelmässä kaikki reitittimet ovat keskenään samanarvoisia. Hierarkkisessa reititysjärjestelmässä jotkin reitittimet muodostavat reitityksen perustan (kannan). Esimerkiksi ne, jotka ovat nopeilla moottoriteillä. Muiden kuin ydinreitittimien paketit kulkevat ydinreitittimille ja niiden kautta, kunnes ne saavuttavat yhteisen kohdealueen. Siitä lähtien he matkustavat viimeisestä ydinreitittimestä yhden tai useamman ei-ydinreitittimen kautta lopulliseen määränpäähänsä. Reititysjärjestelmät muodostavat usein loogisia solmuryhmiä, joita kutsutaan toimialueiksi tai alueiksi. Hierarkkisissa järjestelmissä jotkin toimialueen reitittimet voivat kommunikoida muiden toimialueiden reitittimien kanssa, kun taas muut kyseisen toimialueen reitittimet voivat viestiä vain oman toimialueensa reitittimien kanssa. Erittäin suurissa verkoissa voi olla hierarkkisia lisätasoja. Hierarkkisen korkeimman tason reitittimet muodostavat reitityskannan. Hierarkkisen reitityksen tärkein etu on, että se jäljittelee useimpien yritysten organisaatiota ja tukee siten niiden liikennemalleja erittäin hyvin. Suurin osa yrityksen verkkoliikenteestä on keskittynyt sen toimialueelle, joten verkkotunnuksen sisäisten reitittimien tarvitsee vain tietää muista toimialueensa reitittimistä, jotta niiden reititysalgoritmit voidaan yksinkertaistaa. Vastaavasti reitityspäivitysliikennettä voidaan myös vähentää käytetystä reititysalgoritmista riippuen.