Útválasztási algoritmusokat használnak a csomagok legjobb útvonalának meghatározására a forrástól a célig, és ezek minden útválasztási protokoll alapját képezik . Az útválasztási algoritmusok megfogalmazásához a hálózatot gráfnak tekintjük. Ebben az esetben az útválasztók csomópontok, a forgalomirányítók közötti fizikai vonalak pedig a megfelelő gráf élei. A grafikon minden éléhez hozzá van rendelve egy bizonyos szám – ez a költség a vonal fizikai hosszától, a vonal mentén történő adatátvitel sebességétől vagy a vonal költségétől függ.
Az útválasztási algoritmusok a következőkre oszthatók:
vegye figyelembe a vonal állapotát
Előnyök és hátrányok+ egy csomag által a hálózatban töltött átlagos idő csökkenése
+ a hálózat állapotához való dinamikus alkalmazkodás képessége -
folyamatosan újra kell számolni az útválasztási táblákat
adaptív központosított algoritmus
Előnyök és hátrányok+RCC (Routing Control Center) rendelkezik minden információval a hálózat állapotáról, ami lehetővé teszi az optimális döntések meghozatalát
+a csomópontok mentesülnek az útválasztási táblázatok számlálása alól
-alacsony megbízhatóság -a csomópontok
különböző időpontokban fogadják az útválasztási táblázatokat -forgalomkoncentráció az
RCC közelében
A csomópont információkat nyer ki a fogadott csomagokból.
Előnyök és hátrányok+ nincs torlódás
- lassú alkalmazkodás a hálózati feltételekhez (konvergencia idő)
távolságvektor algoritmus , link állapot útválasztás
Előnyök és hátrányok+ jobb alkalmazkodás
- túlterhelések
ne vegye figyelembe a hálózat aktuális állapotát, az összes útvonalat a hálózat használata előtt kiszámítja. Ezek viszont olyan algoritmusokra oszlanak, amelyek figyelembe veszik a hálózati topológiát (feszítő fa, áramlás alapú útválasztás), és nem veszik figyelembe (elárasztás).
Előnyök és hátrányok+egyszerűség
+jó eredmények változatlan topológiával és terhelés mellett
-nem tud reagálni a változásokra -alacsony
sebesség heterogén hálózatokban
( angol adaptív központosított útválasztás )
LeírásA hálózatban található egy úgynevezett Routing Control Center (RCC), amely minden csomóponttól információt kap a szomszédos csomópontjairól, a sor hosszáról és a vonalterhelésről. Az RCC funkciói közé tartozik az információgyűjtés, a legjobb útvonalak kiszámítása az egyes csomópontokhoz, az útválasztási táblák összeállítása és elküldése a csomópontokhoz.
Előnyök és hátrányok+Az RCC minden információval rendelkezik és "ideális" útvonalakat tud létrehozni
+a csomópontok mentesülnek az útválasztási táblák kiszámításának szükségessége alól
-alacsony
megbízhatóság -időnként újra kell számítani az útválasztási táblákat -nem megfelelő
munka szétválasztott hálózatokkal
-az IS különböző címeken fogad információkat alkalommal - forgalomkoncentráció
az RCC közelében
Minden csomópont csak a szükséges információkat veszi át a kapott csomagokból. Így minden csomópont ismeri a csomagok feladóját és a csomag által áthaladt ugrások számát. Ezután történik az összehasonlítás az útválasztási tábla adataival, és ha a fogadott csomagnak kevesebb ugrása van, akkor a tábla frissül.
Előnyök és hátrányok+ egyszerű megvalósítás
- problémák a topológia és a terhelés megváltoztatásakor -
nincs útválasztási adatok cseréje a csomópontok között
( angol távolságvektoros routing )
LeírásMás néven Distributed Bellman-Ford Routing vagy Ford Fulkerson Algorithm. Ez az algoritmus elosztott, iteratív és aszinkron. Ezt így lehet elképzelni: "Mondd el a szomszédaidnak, hogy néz ki a világ." Minden gazdagép fenntart egy útválasztási táblát egy bejegyzéssel az alhálózat minden útválasztójához. A táblázat egy vektor , amely 2 komponenst tartalmaz: a kiválasztott vonalat és a távolságot. A csomópont megbecsüli a távolságot (ugrások száma, késleltetés vagy sor hossza) minden szomszédhoz, és elküldi a szomszédoknak, akik viszont ugyanezt teszik. A kapott információ eredményeként minden csomópont újraszámítja az útválasztási táblát. A RIP útválasztási protokollban használatos . Először az ARPANET -ben használták .
AlgoritmusTegyük fel, hogy a táblázatot éppen most kaptuk meg X szomszédtól, ahol Xi Xi tippje arra vonatkozóan, hogy mennyi idő alatt jut el az i útválasztóhoz. Ha egy router tudja, hogy az X-re történő adatátvitel m időt vesz igénybe, akkor azt is tudja, hogy az X i +m-ben lévő X-en keresztül bármely i routert elérheti.
Előnyök és hátrányok+ önszerveződés
+ viszonylag egyszerű megvalósítás
- gyenge konvergencia ("konvergencia")
- nehézségek a hálózat bővítésekor
Az algoritmus használatakor problémák merülnek fel, ha az egyik csomópont le van választva a hálózatról - a "Számlál a végtelenig" probléma (számlál a végtelenig).
Megelőzés: Split Horizont Algoritmus – "ne mondd el, amit mondtam"
Útválasztás link állapot szerintangol Linkállapot-útválasztás
LeírásAz adaptív algoritmusokhoz kapcsolódó és a linkek állapotának elemzésén alapuló algoritmus. Ezt így lehet elképzelni: "Mondd el a világnak, hogy kik a szomszédaid." Egy csomópont először csak a szomszédait és a hozzájuk kapcsolódó hivatkozások metrikáját ismeri. A szomszédos csomópontokkal való információcsere során a csomópont információkat kap a hálózati topológiáról, miközben csak a bekövetkezett változásokról cserél információt. Ennek eredményeként minden csomópont ismeri a teljes hálózati topológiát. Először 1979-ben alkalmazták az ARPANET -re , és felváltotta a távolságvektor algoritmust. Az átállás okai a következők voltak:
( angol adás útválasztás )
unicast - 1:1
multicast - 1:n
broadcast - 1:* (1:all)
Minden csomag tartalmaz egy listát az összes célról. Minden csomópont minden kimenő kapcsolathoz létrehoz egy másolatot a csomagról, amely csak azon csomópontok címét tartalmazza, amelyek ezen a kapcsolaton keresztül elérhetők.
Multicastingangol multicast útválasztás
Spanning Tree Algorithmangol feszítőfának
LeírásFeszítőfa: olyan gráf, amely nem tartalmaz ciklusokat. A feszítőfát minden csomópont ismeri. Ennek megfelelően minden csomópont kiküldi a csomagok másolatait
Fordított út továbbítás (Reverse path elárasztás)Az algoritmus a legegyszerűbb és nem adaptív lehetőség. Minden fogadott csomag az összes vonalon továbbítódik, kivéve azt, amelyen keresztül fogadták. Ebben az esetben csak a küldőnek kell ismernie a teljes átívelő fát. Algoritmus: Minden útválasztó ismeri az útvonalat, amelyet az unicast csomagokhoz kell használnia. Csomag vételekor ellenőrzi, hogy a csomag érkezett-e azon a vonalon, amelyet általában az unicast csomagokhoz használnak. Ha igen, akkor a csomagot minden vonalon továbbítja, kivéve azon, amelyen keresztül fogadta. Ellenkező esetben a csomag eldobásra kerül.
Fordított útvonalú adásA visszirányú továbbítással ellentétben a csomagok csak olyan vonalakon kerülnek elküldésre, amelyeken más csomópontok adatokat fogadnak.
Ez az algoritmus kiszámítja a legrövidebb utat a fa gyökerétől a csomópontokig. A lényeg, hogy hozzunk létre egy csomó Q csomópontot, amelyhez az optimális útvonalat már meghatároztuk. Az operátor útválasztási táblákat állít elő, amelyek az inicializáláskor betöltődnek, és már nem módosítják őket. Dijkstra algoritmusa alapján .
AlgoritmusA legrövidebb távolság A-tól D-ig
+ egyszerűség
+ jó eredmények állandó hálózati topológia és terhelés mellett
Ez az algoritmus a nem adaptív algoritmusok közé tartozik. Nemcsak az útválasztók közötti távolságot veszi figyelembe, hanem a hálózat terhelését is. Hasznos útvonal keresése nagy távolságokra a csomagok kézbesítésének nagy késéseivel
PéldaAdott grafikon a kapacitás és a forgalom mátrixához
| vonal | λi ( csomagok /sec) |
|---|---|
| AB | 3 (AB) + 7 (ABC) + 7 (BAD) + 4 (BAF) + 3 (BADG) =24 |
| HIRDETÉS | 4 (AD) + 2 (ADE) + 2 (ADG) + 5 (ADEH) + 7 (BAD) + 3 (BADG) = 23 |
| AF | 5(AF) + 4(BAF) = 9 |
| időszámításunk előtt | 7(ABC) + 3(BC) + 4(BCH) = 14 |
| LENNI | 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 |
| vonal | λi ( csomagok /sec) | µCi (csomag / mp) | T i (msec) |
|---|---|---|---|
| AB | 24 | ötven | 38.46 |
| HIRDETÉS | 23 | ötven | 37.04 |
| AF | 9 | 37.5 | 35.09 |
| időszámításunk előtt | tizennégy | 25 | 90,91 |
| LENNI | 3 | ötven | 21.28 |
| CE | tizenöt | 75 | 16.67 |
| CH | 12 | ötven | 26.32 |
| DE | 40 | ötven | 100 |
| D.F. | 24 | 25 | 1000 |
| EH | 26 | ötven | 41.67 |
| FG | egy | 100 | 10.1 |
| GH | 7 | 62.5 | 18.02 |
| DG | 7 | 62.5 | 18.02 |
| vonal | λi ( csomagok /sec) | µCi (csomag / mp) | T i (msec) | Wi _ |
|---|---|---|---|---|
| AB | 24 | ötven | 38.46 | 0,117 |
| HIRDETÉS | 23 | ötven | 37.04 | 0,112 |
| AF | 9 | 37.5 | 35.09 | 0,044 |
| időszámításunk előtt | tizennégy | 25 | 90,91 | 0,068 |
| LENNI | 3 | ötven | 21.28 | 0,015 |
| CE | tizenöt | 75 | 16.67 | 0,073 |
| CH | 12 | ötven | 26.32 | 0,059 |
| DE | 40 | ötven | 100 | 0,195 |
| D.F. | 24 | 25 | 1000 | 0,117 |
| EH | 26 | ötven | 41.67 | 0,127 |
| FG | egy | 100 | 10.1 | 0,005 |
| GH | 7 | 62.5 | 18.02 | 0,034 |
| DG | 7 | 62.5 | 18.02 | 0,034 |
Mivel a kapott érték túl nagy, csökkenthető, ha a legnagyobb késleltetésű DF( T i, max = 1000msec ) útvonalat a D->G->F útvonalra cseréljük.
Ez a legegyszerűbb útválasztási algoritmus az információk hálózaton keresztüli elosztására. Amikor egy csomag érkezik, minden csomópont továbbítja azt a szomszédos csomópontokhoz, kivéve azt, amelyiktől a csomag érkezett.
Ennek az algoritmusnak a hatékonysága alacsony a megnövekedett hálózati terhelés miatt.
Az algoritmus hatékonyságának javítása érdekében a következő módszereket alkalmazzuk:
Az algoritmus fő célja alternatív útvonalak és útvonalköltségek kiszámítása. A költség egy alternatív útvonal használatának valószínűsége. Ettől függően minden alkalommal más útvonalat használnak, ami a kézbesítetlen csomagok számának csökkenéséhez vezet. Ezzel a módszerrel a számítógépes hálózat nagyon megbízhatóvá válik. A módszert leggyakrabban mobilhálózatoknál alkalmazzák, ahol a hálózat állapota gyakran változhat, és egyes útválasztók meghibásodhatnak.
angol Hierarchikus útválasztás Egyszintű vagy hierarchikus algoritmusok. Egyes útválasztási algoritmusok egyetlen szintű térben működnek, míg mások útválasztási hierarchiát használnak. Az egyrétegű útválasztási rendszerben az összes útválasztó egyenlő egymással. Egy hierarchikus útválasztási rendszerben egyes útválasztók alkotják az útválasztás alapját (alapját). Például azokat, amelyek nagy sebességű autópályákon vannak. A nem alapvető útválasztóktól érkező csomagok az alapvető útválasztókhoz és azon keresztül haladnak, amíg el nem érik a közös célterületet. Ettől kezdve az utolsó magroutertől egy vagy több nem magrouteren keresztül jutnak el végső úticéljukig. Az útválasztási rendszerek gyakran logikai csomópontcsoportokat hoznak létre, amelyeket tartományoknak vagy területeknek neveznek. A hierarchikus rendszerekben egy tartomány egyes útválasztói kommunikálhatnak más tartományok útválasztóival, míg az adott tartományban lévő többi útválasztó csak a saját tartományukon belüli útválasztókkal kommunikálhat. Nagyon nagy hálózatokban további hierarchikus szintek létezhetnek. A legmagasabb hierarchikus szinten lévő útválasztók alkotják az útválasztási bázist. A hierarchikus útválasztás fő előnye, hogy a legtöbb vállalat szervezetét utánozza, ezért nagyon jól támogatja a forgalmi mintákat. Egy vállalat hálózati forgalmának nagy része a tartományán belül összpontosul, így a tartományon belüli útválasztóknak csak a tartományukon belüli többi útválasztóról kell tudniuk, így az útválasztási algoritmusaik leegyszerűsíthetők. Ennek megfelelően az útválasztási frissítési forgalom is csökkenthető, az alkalmazott útválasztási algoritmustól függően.