Routingalgoritmer bruges til at bestemme den bedste vej for pakker fra kilde til destination og er grundlaget for enhver routingprotokol . For at formulere routingalgoritmer betragtes netværket som en graf. I dette tilfælde er routerne noder, og de fysiske linjer mellem routerne er kanterne på den tilsvarende graf. Hver kant af grafen tildeles et bestemt nummer - en omkostning, der afhænger af linjens fysiske længde, dataoverførselshastigheden langs linjen eller omkostningerne ved linjen.
Routing algoritmer kan opdeles i:
tage højde for strækningens tilstand
Fordele og ulemper+ fald i den gennemsnitlige tid brugt af en pakke i netværket
+ evnen til dynamisk at tilpasse sig netværkets tilstand - det
er nødvendigt konstant at genberegne routingtabellerne
adaptiv centraliseret algoritme
Fordele og ulemper+RCC(Routing Control Center) har al information om netværkets tilstand, hvilket giver dig mulighed for at træffe optimale beslutninger
+knudepunkter er undtaget fra at tælle routingtabeller -lav
pålidelighed
-knudepunkter modtager routingtabeller på forskellige tidspunkter -trafikkoncentration
nær RCC
Noden udtrækker information fra modtagne pakker.
Fordele og ulemper+ ingen overbelastning
- langsom tilpasning til netværksforhold (konvergenstid)
distance vektor algoritme , link tilstand routing
Fordele og ulemper+ bedre tilpasning
- overbelastninger
ikke tage højde for netværkets aktuelle tilstand, alle ruter beregnes inden brug af netværket. De er til gengæld opdelt i algoritmer, der tager højde for netværkstopologien (spændingstræ, flowbaseret routing) og ikke tager højde for (oversvømmelse).
Fordele og ulemper+ enkelhed
+ gode resultater med uændret topologi og belastning
- manglende evne til at reagere på ændringer -
lav hastighed i heterogene netværk
( eng. adaptiv centraliseret routing )
BeskrivelseDer er et såkaldt Routing Control Center (RCC) i netværket, som modtager information fra alle noder om deres naboknudepunkter, kølængde og linjebelastning. RCC's funktioner omfatter indsamling af information, beregning af de bedste ruter for hver knude, kompilering af routingtabeller og afsendelse af dem til knudepunkter.
Fordele og ulemper+RCC har alle informationerne og kan skabe "ideelle" ruter
+noder er undtaget fra behovet for at beregne routingtabeller
-lav pålidelighed -genberegning af routingtabeller er påkrævet
fra tid til anden
-forkert arbejde med adskilte netværk
-IS modtager information på forskellige gange -trafikkoncentration
nær RCC
Hver node tager kun den nødvendige information fra de modtagne pakker. Hver node kender således afsenderen af pakkerne og antallet af hop , som denne pakke har passeret. Så er der en sammenligning med dataene i routingtabellen, og hvis den modtagne pakke har færre hop, så opdateres tabellen.
Fordele og ulemper+ nem implementering
- problemer ved ændring af topologi og belastning -
der er ingen udveksling af routingdata mellem noder
( Engelsk distance vektor routing )
BeskrivelseOgså kendt som Distributed Bellman-Ford Routing eller Ford Fulkerson Algorithm. Denne algoritme er distribueret, iterativ og asynkron. Det kan opfattes som: "Fortæl dine naboer, hvordan verden ser ud." Hver vært vedligeholder en routingtabel med én indgang for hver router på undernettet. Tabellen er en vektor, der indeholder 2 komponenter: den valgte linje og afstanden. Noden estimerer afstanden (antal hop, forsinkelse eller kølængde) til hver nabo og sender den til sine naboer, som igen gør det samme. Som et resultat af den modtagne information genberegner hver knude routingtabellen. Anvendes i RIP -routingprotokollen . Det blev først brugt i ARPANET .
AlgoritmeAntag, at bordet lige er modtaget fra nabo X, hvor Xi er X's gæt på, hvor lang tid det tager at komme til router i. Hvis en router ved, at dataoverførslen til X tager m, så ved den også, at den kan nå enhver router i via X i X i +m.
Fordele og ulemper+ selvorganisering
+ relativt simpel implementering
- dårlig konvergens ("konvergens")
- vanskeligheder ved at udvide netværket
Ved brug af algoritmen opstår der problemer, når en af knudepunkterne afbrydes fra netværket - "Count to Infinity"-problemet (tæl til uendeligt).
Forebyggelse: Split Horizont Algorithm - "fortæl mig ikke, hvad jeg fortalte dig"
Routing efter linktilstandengelsk Link tilstand routing
BeskrivelseAlgoritme relateret til adaptive algoritmer og baseret på analysen af tilstanden af links. Det kan opfattes som: "Fortæl verden, hvem dine naboer er." Først kender en node kun sine naboer og metrikken for links, der forbinder den med dem. I processen med at udveksle information med tilstødende noder, modtager noden information om netværkstopologien, mens den kun udveksler information om de ændringer, der er sket. Som et resultat kender hver knude hele netværkstopologien. Den blev først anvendt på ARPANET i 1979 og erstattede afstandsvektoralgoritmen. Årsagerne til overgangen var:
( Engelsk broadcast routing )
unicast - 1:1
multicast - 1:n
udsendelse - 1:* (1:alle)
Hver pakke indeholder en liste over alle mål. Hver knude opretter for hver udgående forbindelse en kopi af pakken, som kun indeholder adresserne på de knudepunkter, der er tilgængelige via denne forbindelse.
Multicastingengelsk multicast routing
Spanning Tree Algorithmengelsk spændende træ
BeskrivelseSpanning tree: En graf, der ikke indeholder loops. Det spændende træ er kendt af alle noder. I overensstemmelse hermed udsender hver node kopier af pakkerne
Omvendt sti-videresendelse (Omvendt sti-oversvømmelse)Algoritmen er den enkleste og ikke-adaptive mulighed. Hver modtaget pakke videresendes på alle linjer, undtagen den, hvorigennem den blev modtaget. I dette tilfælde er det kun afsenderen, der skal kende hele spændingstræet. Algoritme: Hver router kender stien, den skal bruge til unicast-pakker. Når en pakke modtages, tjekker den, om pakken blev modtaget på den linje, der normalt bruges til unicast-pakker. Hvis ja, så videresendes pakken på alle linjer, undtagen den, hvorigennem den blev modtaget. Ellers tabes pakken.
Omvendt sti-udsendelseI modsætning til Reverse path forwarding sendes pakker kun over linjer, som andre noder modtager data på.
Denne algoritme beregner den korteste vej fra træets rod til noderne. Pointen er at skabe en flok knudepunkter Q, for hvilke den optimale rute allerede er fastlagt. Operatøren genererer routingtabeller, der indlæses, når den initialiseres, og som ikke længere ændres. Baseret på Dijkstras algoritme .
AlgoritmeKorteste afstand fra A til D
+ enkelhed
+ gode resultater med konstant netværkstopologi og belastning
Denne algoritme er en af de ikke-adaptive algoritmer. Det tager ikke kun højde for afstanden mellem routere, men også netværksbelastningen. Nyttigt til at finde en rute til lange afstande med lange forsinkelser i pakkelevering
EksempelGivet graf for kapacitet og trafikmatrix
| linje | λi ( pakker /sek.) |
|---|---|
| AB | 3(AB) + 7(ABC) + 7(DÅRLIG) + 4(BAF) + 3(BADG) =24 |
| AD | 4(AD) + 2(ADE) + 2(ADG) + 5(ADEH) + 7(BAD) + 3(BADG) = 23 |
| AF | 5(AF) + 4(BAF) = 9 |
| f.Kr | 7(ABC) + 3(BC) + 4(BCH) = 14 |
| VÆRE | 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 |
| linje | λi ( pakker /sek.) | µCi (pakker / sek.) | T i (msec) |
|---|---|---|---|
| AB | 24 | halvtreds | 38,46 |
| AD | 23 | halvtreds | 37,04 |
| AF | 9 | 37,5 | 35,09 |
| f.Kr | fjorten | 25 | 90,91 |
| VÆRE | 3 | halvtreds | 21.28 |
| CE | femten | 75 | 16,67 |
| CH | 12 | halvtreds | 26.32 |
| DE | 40 | halvtreds | 100 |
| D.F. | 24 | 25 | 1000 |
| EH | 26 | halvtreds | 41,67 |
| FG | en | 100 | 10.1 |
| GH | 7 | 62,5 | 18.02 |
| DG | 7 | 62,5 | 18.02 |
| linje | λi ( pakker /sek.) | µCi (pakker / sek.) | T i (msec) | Wi _ |
|---|---|---|---|---|
| AB | 24 | halvtreds | 38,46 | 0,117 |
| AD | 23 | halvtreds | 37,04 | 0,112 |
| AF | 9 | 37,5 | 35,09 | 0,044 |
| f.Kr | fjorten | 25 | 90,91 | 0,068 |
| VÆRE | 3 | halvtreds | 21.28 | 0,015 |
| CE | femten | 75 | 16,67 | 0,073 |
| CH | 12 | halvtreds | 26.32 | 0,059 |
| DE | 40 | halvtreds | 100 | 0,195 |
| D.F. | 24 | 25 | 1000 | 0,117 |
| EH | 26 | halvtreds | 41,67 | 0,127 |
| FG | en | 100 | 10.1 | 0,005 |
| GH | 7 | 62,5 | 18.02 | 0,034 |
| DG | 7 | 62,5 | 18.02 | 0,034 |
Da den resulterende værdi er for stor, kan den reduceres ved at erstatte stien med den største forsinkelse DF( Ti , max = 1000msec ) med stien D->G->F
Det er den enkleste routingalgoritme til at distribuere information over et netværk. Når en pakke modtages, sender hver node den videre til dens naboknudepunkter, undtagen den, hvorfra pakken kom.
Denne algoritme har lav effektivitet på grund af øget netværksbelastning.
For at forbedre effektiviteten af algoritmen anvendes følgende metoder:
Hovedmålet med algoritmen er at beregne alternative ruter og ruteomkostninger. Omkostninger er sandsynligheden for at bruge en alternativ rute. Afhængigt af dette vil en anden rute blive brugt hver gang, hvilket vil føre til et fald i antallet af ikke-leverede pakker. Brug af denne metode gør et computernetværk meget pålideligt. Metoden bruges oftest til mobilnetværk, hvor netværkstilstanden kan ændre sig hyppigt, og nogle routere kan fejle.
engelsk Hierarkisk routing Enkeltniveau eller hierarkiske algoritmer. Nogle routingalgoritmer fungerer på et enkelt niveaurum, mens andre bruger et routinghierarki. I et enkeltlags routingsystem er alle routere ens med hinanden. I et hierarkisk routingsystem udgør nogle routere det, der udgør grundlaget (basen) for routing. For eksempel dem, der er på højhastighedsmotorveje. Pakker fra ikke-kerneroutere rejser til og gennem kerneroutere, indtil de når det fælles destinationsområde. Fra det tidspunkt rejser de fra den sidste kernerouter gennem en eller flere ikke-kerneroutere til deres endelige destination. Routingsystemer etablerer ofte logiske grupper af noder kaldet domæner eller områder. I hierarkiske systemer kan nogle routere i et domæne kommunikere med routere i andre domæner, mens andre routere i det domæne kun kan kommunikere med routere inden for deres eget domæne. I meget store netværk kan der eksistere yderligere hierarkiske niveauer. Routerne på det højeste hierarkiske niveau danner routingbasen. Den største fordel ved hierarkisk routing er, at den efterligner de fleste virksomheders organisation og derfor understøtter deres trafikmønstre meget godt. Det meste af en virksomheds netværkstrafik er koncentreret inden for dens domæne, så intra-domæne-routere behøver kun at vide om andre routere inden for deres domæne, så deres routing-algoritmer kan forenkles. Følgelig kan routingopdateringstrafikken også reduceres afhængigt af den anvendte routingalgoritme.