Routningsalgoritmer används för att bestämma den bästa vägen för paket från källa till destination och är grunden för alla routingprotokoll . För att formulera routingalgoritmer betraktas nätverket som en graf. I det här fallet är routrarna noder och de fysiska linjerna mellan routrarna är kanterna på motsvarande graf. Varje kant av grafen tilldelas ett visst nummer - en kostnad som beror på linjens fysiska längd, dataöverföringshastigheten längs linjen eller kostnaden för linjen.
Routingalgoritmer kan delas in i:
ta hänsyn till linjens tillstånd
För- och nackdelar+ minskning av den genomsnittliga tiden som ett paket spenderar i nätverket
+ förmågan att dynamiskt anpassa sig till nätverkets tillstånd - det
är nödvändigt att ständigt räkna om routingtabellerna
adaptiv centraliserad algoritm
För- och nackdelar+RCC(Routing Control Center) har all information om nätverkets tillstånd, vilket gör att du kan fatta optimala beslut
+noder är undantagna från att räkna routingtabeller
-låg tillförlitlighet
-noder tar emot routingtabeller vid olika tidpunkter -trafikkoncentration
nära RCC
Noden extraherar information från mottagna paket.
För- och nackdelar+ ingen trafikstockning
- långsam anpassning till nätverksförhållanden (konvergenstid)
avståndsvektoralgoritm , länktillståndsdirigering
För- och nackdelar+ bättre anpassning
- överbelastningar
ta inte hänsyn till nätverkets nuvarande tillstånd, alla rutter beräknas innan nätverket används. De är i sin tur uppdelade i algoritmer som tar hänsyn till nätverkstopologin (spaning tree, flödesbaserad routing) och inte tar hänsyn till (flooding).
För- och nackdelar+enkelhet
+bra resultat med oförändrad topologi och belastning
-oförmåga att svara på förändringar
-låg hastighet i heterogena nätverk
( eng. adaptiv centraliserad routing )
BeskrivningDet finns ett så kallat Routing Control Center (RCC) i nätverket, som tar emot information från alla noder om deras närliggande noder, kölängd och linjebelastning. RCC:s funktioner inkluderar att samla in information, beräkna de bästa rutterna för varje nod, sammanställa routingtabeller och skicka dem till noder.
För- och nackdelar+RCC har all information och kan skapa "ideala" rutter
+noder är undantagna från behovet av att beräkna routingtabeller
-låg tillförlitlighet -omräkning av routingtabeller krävs
då och då
-felaktigt arbete med separerade nätverk
-IS tar emot information vid olika gånger -trafikkoncentration
nära RCC
Varje nod tar endast den nödvändiga informationen från de mottagna paketen. Således känner varje nod till avsändaren av paketen och antalet hopp som detta paket har passerat. Sedan görs en jämförelse med data i routingtabellen, och om det mottagna paketet har färre hopp, uppdateras tabellen.
För- och nackdelar+ enkel implementering
- problem vid ändring av topologi och belastning -
det finns inget utbyte av routingdata mellan noder
( Engelsk distansvektordirigering )
BeskrivningÄven känd som Distributed Bellman-Ford Routing eller Ford Fulkerson Algorithm. Denna algoritm är distribuerad, iterativ och asynkron. Det kan tänkas som: "Berätta för dina grannar hur världen ser ut." Varje värd upprätthåller en routingtabell med en post för varje router på subnätet. Tabellen är en vektor som innehåller 2 komponenter: den valda linjen och avståndet. Noden uppskattar avståndet (antal hopp, fördröjning eller kölängd) till varje granne och skickar det till sina grannar, som i sin tur gör detsamma. Som ett resultat av den mottagna informationen beräknar varje nod om routingtabellen. Används i RIP- routingprotokollet . Det användes först i ARPANET .
AlgoritmAnta att tabellen precis har mottagits från grannen X, där Xi är X:s gissning om hur lång tid det tar att komma till router i. Om en router vet att dataöverföringen till X tar m, så vet den också att den kan nå vilken router i som helst via X i X i +m.
För- och nackdelar+ självorganisering
+ relativt enkel implementering
- dålig konvergens ("konvergens")
- svårigheter vid utbyggnad av nätverket
När man använder algoritmen uppstår problem när en av noderna kopplas bort från nätverket - "Räkna till oändlighet"-problemet (räkna till oändlighet).
Förebyggande: Split Horizont Algorithm - "säg inte vad jag sa till dig"
Routing efter länkstatusengelsk Länkstatus routing
BeskrivningAlgoritm relaterad till adaptiva algoritmer och baserad på analys av länkarnas tillstånd. Det kan ses som: "Berätta för världen vilka dina grannar är." Till en början känner en nod bara till sina grannar och metriken för länkar som kopplar den till dem. I processen att utbyta information med angränsande noder, får noden information om nätverkstopologin, medan den endast utbyter information om de förändringar som har inträffat. Som ett resultat känner varje nod till hela nätverkstopologin. Den applicerades först på ARPANET 1979 och ersatte avståndsvektoralgoritmen. Skälen till övergången var:
( Engelsk sändningsdirigering )
unicast - 1:1
multicast - 1:n
broadcast - 1:* (1:alla)
Varje paket innehåller en lista över alla mål. Varje nod skapar för varje utgående anslutning en kopia av paketet, som endast innehåller adresserna till de noder som är nåbara via denna anslutning.
Multicastingengelsk multicast routing
Spanning Tree Algorithmengelsk Spanning Tree
BeskrivningSpännande träd: En graf som inte innehåller loopar. Spännträdet är känt för alla noder. I enlighet med detta skickar varje nod ut kopior av paketen
Vidarebefordran av väg bakåt (Flödande bakåtväg)Algoritmen är det enklaste och icke-adaptiva alternativet. Varje mottaget paket vidarebefordras på alla rader, förutom den genom vilken det togs emot. I det här fallet behöver bara avsändaren känna till hela spännträdet. Algoritm: Varje router känner till sökvägen den ska använda för unicast-paket. När ett paket tas emot kontrollerar det om paketet togs emot på den linje som normalt används för unicast-paket. Om ja, så vidarebefordras paketet på alla rader, förutom den genom vilken det togs emot. Annars tappas paketet.
Omvänd sökväg sändningTill skillnad från omvänd vägvidarebefordran, skickas paket endast över linjer som andra noder tar emot data på.
Denna algoritm beräknar den kortaste vägen från trädets rot till noderna. Poängen är att skapa ett gäng noder Q, för vilka den optimala rutten redan har bestämts. Operatören genererar routingtabeller som laddas när den initieras och som inte längre ändras. Baserat på Dijkstras algoritm .
AlgoritmKortaste avståndet från A till D
+ enkelhet
+ bra resultat med konstant nätverkstopologi och belastning
Denna algoritm är en av de icke-adaptiva algoritmerna. Det tar inte bara hänsyn till avståndet mellan routrar, utan även nätverksbelastningen. Användbar för att hitta en rutt för långa sträckor med stora förseningar i paketleverans
ExempelGivet diagram för kapacitet och trafikmatris
| linje | λi ( paket /sek) |
|---|---|
| AB | 3(AB) + 7(ABC) + 7(BAD) + 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öre Kristus | 7(ABC) + 3(BC) + 4(BCH) = 14 |
| VARA | 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 |
| VA | 5(ADEH)+ 9(DEH)+ 1(EHG)+ 2(EH) + 9(FDEH) = 26 |
| FG | 1(FG) = 1 |
| GH | 1(GH) + 1(EHG) + 5(CHG) = 7 |
| GD | 2(ADG) + 3(BADG) + 2(DG) = 7 |
| linje | λi ( paket /sek) | µCi (paket / sek) | T i (ms) |
|---|---|---|---|
| AB | 24 | femtio | 38,46 |
| AD | 23 | femtio | 37.04 |
| AF | 9 | 37,5 | 35.09 |
| före Kristus | fjorton | 25 | 90,91 |
| VARA | 3 | femtio | 21.28 |
| CE | femton | 75 | 16,67 |
| CH | 12 | femtio | 26.32 |
| DE | 40 | femtio | 100 |
| D.F. | 24 | 25 | 1000 |
| VA | 26 | femtio | 41,67 |
| FG | ett | 100 | 10.1 |
| GH | 7 | 62,5 | 18.02 |
| GD | 7 | 62,5 | 18.02 |
| linje | λi ( paket /sek) | µCi (paket / sek) | T i (ms) | Wi _ |
|---|---|---|---|---|
| AB | 24 | femtio | 38,46 | 0,117 |
| AD | 23 | femtio | 37.04 | 0,112 |
| AF | 9 | 37,5 | 35.09 | 0,044 |
| före Kristus | fjorton | 25 | 90,91 | 0,068 |
| VARA | 3 | femtio | 21.28 | 0,015 |
| CE | femton | 75 | 16,67 | 0,073 |
| CH | 12 | femtio | 26.32 | 0,059 |
| DE | 40 | femtio | 100 | 0,195 |
| D.F. | 24 | 25 | 1000 | 0,117 |
| VA | 26 | femtio | 41,67 | 0,127 |
| FG | ett | 100 | 10.1 | 0,005 |
| GH | 7 | 62,5 | 18.02 | 0,034 |
| GD | 7 | 62,5 | 18.02 | 0,034 |
Eftersom det resulterande värdet är för stort kan det reduceras genom att ersätta vägen med den största fördröjningen DF( Ti , max = 1000msec ) med sökvägen D->G->F
Det är den enklaste routingalgoritmen för att distribuera information över ett nätverk. När ett paket tas emot vidarebefordrar varje nod det till sina närliggande noder, förutom den som paketet kom ifrån.
Denna algoritm har låg effektivitet på grund av ökad nätverksbelastning.
För att förbättra effektiviteten av algoritmen används följande metoder:
Algoritmens huvudmål är att beräkna alternativa rutter och ruttkostnader. Kostnad är sannolikheten att använda en alternativ väg. Beroende på detta kommer en annan väg att användas varje gång, vilket kommer att leda till en minskning av antalet ej levererade paket. Att använda denna metod gör ett datornätverk mycket tillförlitligt. Metoden används oftast för mobila nätverk, där nätverkets status kan ändras ofta och vissa routrar kan misslyckas.
engelsk Hierarkisk routing Ennivå- eller hierarkiska algoritmer. Vissa routingalgoritmer fungerar i ett utrymme på en nivå, medan andra använder en routinghierarki. I ett enda lager routingsystem är alla routrar lika med varandra. I ett hierarkiskt routingsystem utgör vissa routrar det som utgör basen (basen) för routing. Till exempel de som är på höghastighetsmotorvägar. Paket från icke-kärnroutrar färdas till och genom kärnroutrar tills de når det gemensamma destinationsområdet. Från den tidpunkten reser de från den sista kärnroutern genom en eller flera icke-kärnroutrar till sin slutdestination. Routingsystem upprättar ofta logiska grupper av noder som kallas domäner eller områden. I hierarkiska system kan vissa routrar i en domän kommunicera med routrar i andra domäner, medan andra routrar i den domänen bara kan kommunicera med routrar inom sin egen domän. I mycket stora nätverk kan ytterligare hierarkiska nivåer finnas. Routrarna på den högsta hierarkiska nivån utgör routingbasen. Den största fördelen med hierarkisk routing är att den efterliknar de flesta företags organisation och därför stödjer deras trafikmönster mycket väl. Det mesta av ett företags nätverkstrafik är koncentrerad till dess domän, så routrar inom domänen behöver bara känna till andra routrar inom deras domän, så deras routningsalgoritmer kan förenklas. Följaktligen kan routinguppdateringstrafiken också reduceras, beroende på vilken routingalgoritm som används.