Směrovací algoritmy se používají k určení nejlepší cesty pro pakety od zdroje k cíli a jsou základem jakéhokoli směrovacího protokolu . Pro formulování směrovacích algoritmů je síť považována za graf. V tomto případě jsou směrovače uzly a fyzické čáry mezi směrovači jsou okraje odpovídajícího grafu. Každé hraně grafu je přiřazeno určité číslo – cena, která závisí na fyzické délce linky, rychlosti přenosu dat po lince nebo ceně linky.
Směrovací algoritmy lze rozdělit na:
vzít v úvahu stav linky
Klady a zápory+ snížení průměrné doby strávené paketem v síti
+ schopnost dynamicky se přizpůsobovat stavu sítě -
je nutné neustále přepočítávat směrovací tabulky
adaptivní centralizovaný algoritmus
Klady a zápory+RCC(Routing Control Center) má všechny informace o stavu sítě, což vám umožňuje přijímat optimální rozhodnutí
+uzly jsou osvobozeny od počítání směrovacích tabulek -nízká
spolehlivost
-uzly dostávají směrovací tabulky v různých časech -koncentrace provozu
poblíž RCC
Uzel extrahuje informace z přijatých paketů.
Klady a zápory+ žádné přetížení
- pomalé přizpůsobení podmínkám sítě (doba konvergence)
vektorový algoritmus vzdálenosti , směrování stavu spoje
Klady a zápory+ lepší přizpůsobení
- přetížení
nezohledňují aktuální stav sítě, všechny trasy se počítají před použitím sítě. Ty jsou zase rozděleny do algoritmů, které berou v úvahu topologii sítě (spanning tree, flow based routing) a neberou v úvahu (flooding).
Klady a zápory+jednoduchost
+dobré výsledky při nezměněné topologii a zatížení
-neschopnost reagovat na změny
-nízká rychlost v heterogenních sítích
adaptivní centralizované směrování _
PopisV síti funguje tzv. Routing Control Center (RCC), které od všech uzlů přijímá informace o jejich sousedních uzlech, délce fronty a zatížení linky. Funkce RCC zahrnují shromažďování informací, výpočet nejlepších tras pro každý uzel, sestavování směrovacích tabulek a jejich odesílání do uzlů.
Klady a zápory+RCC má všechny informace a může vytvářet "ideální" trasy
+uzly jsou osvobozeny od nutnosti počítat směrovací tabulky
-nízká spolehlivost -čas
od času je vyžadován přepočet směrovacích tabulek
-chybná práce s oddělenými sítěmi -IS
přijímá informace na různých místech krát -koncentrace dopravy v
blízkosti RCC
Každý uzel si z přijatých paketů bere pouze potřebné informace. Každý uzel tedy zná odesílatele paketů a počet přeskoků , kterými tento paket prošel. Poté dojde k porovnání s daty ve směrovací tabulce a pokud má přijatý paket méně přeskoků, pak se tabulka aktualizuje.
Klady a zápory+ jednoduchost implementace
- problémy při změně topologie a zátěže -
nedochází k výměně směrovacích dat mezi uzly
( anglicky distanční vektorové směrování )
PopisTaké známý jako Distributed Bellman-Ford Routing nebo Ford Fulkerson Algorithm. Tento algoritmus je distribuovaný, iterativní a asynchronní. Lze si to představit jako: "Řekněte svým sousedům, jak vypadá svět." Každý hostitel udržuje směrovací tabulku s jednou položkou pro každý směrovač v podsíti. Tabulka je vektor obsahující 2 složky: vybranou čáru a vzdálenost. Uzel odhadne vzdálenost (počet skoků, zpoždění nebo délku fronty) ke každému sousedovi a pošle ji svým sousedům, kteří zase udělají totéž. V důsledku přijatých informací každý uzel přepočítá směrovací tabulku. Používá se ve směrovacím protokolu RIP . Poprvé byl použit v ARPANETu .
AlgoritmusPředpokládejme, že tabulka byla právě přijata od souseda X, kde Xi je odhad X o tom, jak dlouho trvá dostat se k routeru i. Pokud router ví, že přenos dat do X trvá m, pak také ví, že může dosáhnout jakéhokoli routeru i přes X v X i + m.
Klady a zápory+ samoorganizace
+ relativně jednoduchá implementace
- špatná konvergence ("konvergence")
- potíže při rozšiřování sítě
Při použití algoritmu nastávají problémy, když je jeden z uzlů odpojen od sítě - problém "Count to Infinity" (počítat do nekonečna).
Prevence: Algoritmus Split Horizont – „neříkej mi, co jsem ti řekl“
Směrování podle stavu odkazuAngličtina Směrování stavu propojení
PopisAlgoritmus související s adaptivními algoritmy a založený na analýze stavu vazeb. Lze si to představit jako: "Řekněte světu, kdo jsou vaši sousedé." Zpočátku zná uzel pouze své sousedy a metriku odkazů, které jej k nim spojují. V procesu výměny informací se sousedními uzly přijímá uzel informace o topologii sítě, přičemž si vyměňuje pouze informace o změnách, ke kterým došlo. Výsledkem je, že každý uzel zná celou topologii sítě. Poprvé byl aplikován na ARPANET v roce 1979 a nahradil algoritmus vektoru vzdálenosti. Důvody přechodu byly:
( anglické směrování vysílání )
unicast - 1:1
multicast - 1:n
vysílání - 1:* (1:vše)
Každý balíček obsahuje seznam všech cílů. Každý uzel vytvoří pro každé odchozí spojení kopii paketu, která obsahuje pouze adresy těch uzlů, které jsou prostřednictvím tohoto spojení dosažitelné.
MulticastingAngličtina vícesměrové směrování
Spanning Tree AlgorithmAngličtina kostra
PopisSpanning tree: Graf, který neobsahuje smyčky. Kostra je známa všem uzlům. V souladu s tím každý uzel odesílá kopie paketů
Reverse path forwarding (Reverse path flooding)Algoritmus je nejjednodušší a neadaptivní varianta. Každý přijatý paket je přeposlán na všechny linky kromě té, přes kterou byl přijat. V tomto případě pouze odesílatel potřebuje znát celý kostru. Algoritmus: Každý router zná cestu, kterou by měl použít pro unicast pakety. Když je paket přijat, zkontroluje, zda byl přijat na lince běžně používané pro unicast pakety. Pokud ano, pak je paket předán na všech linkách kromě té, přes kterou byl přijat. V opačném případě je paket zahozen.
Vysílání zpětné cestyNa rozdíl od předávání zpětné cesty jsou pakety odesílány pouze po linkách, na kterých ostatní uzly přijímají data.
Tento algoritmus vypočítá nejkratší cestu z kořene stromu do uzlů. Jde o to vytvořit hromadu uzlů Q, pro které již byla určena optimální trasa. Operátor generuje směrovací tabulky, které se načtou při inicializaci a již se neupravují. Založeno na Dijkstrově algoritmu .
AlgoritmusNejkratší vzdálenost z A do D
+ jednoduchost
+ dobré výsledky při konstantní topologii sítě a zatížení
Tento algoritmus patří mezi neadaptivní algoritmy. Bere v úvahu nejen vzdálenost mezi routery, ale také zatížení sítě. Užitečné pro nalezení trasy na dlouhé vzdálenosti s velkým zpožděním v doručení paketů
PříkladDaný graf pro matici kapacity a provozu
| čára | λi ( balíčky /s) |
|---|---|
| AB | 3(AB) + 7(ABC) + 7(BAD) + 4(BAF) + 3(BADG) =24 |
| INZERÁT | 4 (AD) + 2 (ADE) + 2 (ADG) + 5 (ADEH) + 7 (BAD) + 3 (BADG) = 23 |
| AF | 5(AF) + 4(BAF) = 9 |
| před naším letopočtem | 7(ABC) + 3(BC) + 4(BCH) = 14 |
| BÝT | 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 |
| čára | λi ( balíčky /s) | µCi (balíčky / s) | T i (ms) |
|---|---|---|---|
| AB | 24 | padesáti | 38,46 |
| INZERÁT | 23 | padesáti | 37.04 |
| AF | 9 | 37,5 | 35.09 |
| před naším letopočtem | čtrnáct | 25 | 90,91 |
| BÝT | 3 | padesáti | 21.28 |
| CE | patnáct | 75 | 16,67 |
| CH | 12 | padesáti | 26.32 |
| DE | 40 | padesáti | 100 |
| D.F. | 24 | 25 | 1000 |
| EH | 26 | padesáti | 41,67 |
| FG | jeden | 100 | 10.1 |
| GH | 7 | 62,5 | 18.02 |
| DG | 7 | 62,5 | 18.02 |
| čára | λi ( balíčky /s) | µCi (balíčky / s) | T i (ms) | Wi _ |
|---|---|---|---|---|
| AB | 24 | padesáti | 38,46 | 0,117 |
| INZERÁT | 23 | padesáti | 37.04 | 0,112 |
| AF | 9 | 37,5 | 35.09 | 0,044 |
| před naším letopočtem | čtrnáct | 25 | 90,91 | 0,068 |
| BÝT | 3 | padesáti | 21.28 | 0,015 |
| CE | patnáct | 75 | 16,67 | 0,073 |
| CH | 12 | padesáti | 26.32 | 0,059 |
| DE | 40 | padesáti | 100 | 0,195 |
| D.F. | 24 | 25 | 1000 | 0,117 |
| EH | 26 | padesáti | 41,67 | 0,127 |
| FG | jeden | 100 | 10.1 | 0,005 |
| GH | 7 | 62,5 | 18.02 | 0,034 |
| DG | 7 | 62,5 | 18.02 | 0,034 |
Protože je výsledná hodnota příliš velká, lze ji snížit nahrazením cesty s největším zpožděním DF( T i, max = 1000 msec ) cestou D->G->F
Je to nejjednodušší směrovací algoritmus pro distribuci informací po síti. Když je paket přijat, každý uzel jej předá svým sousedním uzlům, kromě toho, ze kterého paket přišel.
Tento algoritmus má nízkou účinnost kvůli zvýšenému zatížení sítě.
Pro zlepšení účinnosti algoritmu se používají následující metody:
Hlavním cílem algoritmu je vypočítat alternativní trasy a náklady na trasu. Cena je pravděpodobnost použití alternativní trasy. V závislosti na tom bude pokaždé použita jiná cesta, což povede ke snížení počtu nedoručených paketů. Použití této metody činí počítačovou síť velmi spolehlivou. Metoda se nejčastěji používá pro mobilní sítě, kde se stav sítě může často měnit a některé routery mohou selhat.
Angličtina Hierarchické směrování Jednoúrovňové nebo hierarchické algoritmy. Některé směrovací algoritmy pracují v prostoru jedné úrovně, zatímco jiné používají hierarchii směrování. V jednovrstvém směrovacím systému jsou si všechny směrovače navzájem rovny. V hierarchickém směrovacím systému tvoří některé směrovače to, co tvoří základ (základnu) směrování. Například ty, které jsou na rychlostních dálnicích. Pakety z jiných než jádrových směrovačů putují do a skrz hlavní směrovače, dokud nedosáhnou společné cílové oblasti. Od tohoto okamžiku cestují od posledního základního směrovače přes jeden nebo více vedlejších směrovačů do svého konečného cíle. Směrovací systémy často vytvářejí logické skupiny uzlů nazývané domény nebo oblasti. V hierarchických systémech mohou některé směrovače v doméně komunikovat se směrovači v jiných doménách, zatímco jiné směrovače v této doméně mohou komunikovat pouze se směrovači v rámci své vlastní domény. Ve velmi rozsáhlých sítích mohou existovat další hierarchické úrovně. Směrovače na nejvyšší hierarchické úrovni tvoří směrovací základnu. Hlavní výhodou hierarchického směrování je, že napodobuje organizaci většiny společností, a proto velmi dobře podporuje jejich dopravní vzorce. Většina firemního síťového provozu je soustředěna v její doméně, takže směrovače v rámci domény potřebují vědět pouze o jiných směrovačích ve své doméně, takže jejich směrovací algoritmy lze zjednodušit. V souladu s tím může být provoz aktualizace směrování také snížen v závislosti na použitém směrovacím algoritmu.