Algoritmii de rutare sunt utilizați pentru a determina cea mai bună cale pentru pachete de la sursă la destinație și sunt baza oricărui protocol de rutare . Pentru a formula algoritmi de rutare, rețeaua este considerată ca un grafic. În acest caz, routerele sunt noduri, iar liniile fizice dintre routere sunt marginile graficului corespunzător. Fiecărei margini a graficului i se atribuie un anumit număr - un cost care depinde de lungimea fizică a liniei, viteza de transfer de date de-a lungul liniei sau costul liniei.
Algoritmii de rutare pot fi împărțiți în:
luați în considerare starea liniei
Avantaje și dezavantaje+ scăderea timpului mediu petrecut de un pachet în rețea
+ capacitatea de a se adapta dinamic la starea rețelei -
este necesar să se recalculeze constant tabelele de rutare
algoritm centralizat adaptiv
Avantaje și dezavantaje+RCC(Routing Control Center) are toate informațiile despre starea rețelei, ceea ce vă permite să luați decizii optime
+nodurile sunt scutite de la numărarea tabelelor de rutare
-fiabilitate
scăzută -nodurile primesc tabele de rutare la momente diferite -concentrarea traficului
lângă RCC
Nodul extrage informații din pachetele primite.
Avantaje și dezavantaje+ fără aglomerație
- adaptare lentă la condițiile rețelei (timp de convergență)
algoritm de vector de distanță , rutare a stării legăturii
Avantaje și dezavantaje+ adaptare mai bună
- supraîncărcări
nu țineți cont de starea actuală a rețelei, toate rutele sunt calculate înainte de a utiliza rețeaua. Aceștia, la rândul lor, sunt împărțiți în algoritmi care iau în considerare topologia rețelei (spanning tree, flow based routing) și nu iau în considerare (flooding).
Avantaje și dezavantaje+simplitate
+rezultate bune cu topologie și încărcare neschimbate
-incapacitate de a răspunde la schimbări -viteză scăzută
în rețele eterogene
( ing. rutare centralizată adaptivă )
DescriereÎn rețea există un așa-numit Centru de control de rutare (RCC), care primește informații de la toate nodurile despre nodurile învecinate, lungimea cozii și încărcarea liniei. Funcțiile RCC includ colectarea de informații, calcularea celor mai bune rute pentru fiecare nod, compilarea tabelelor de rutare și trimiterea lor către noduri.
Avantaje și dezavantaje+RCC are toate informațiile și poate crea rute „ideale”
+nodurile sunt scutite de necesitatea calculării tabelelor de rutare
-fiabilitate scăzută -recalcularea tabelelor de rutare este necesară
din când în când
-lucrare incorectă cu rețele separate
-IS primește informații la diferite ori -concentrarea traficului
lângă RCC
Fiecare nod preia doar informațiile necesare din pachetele primite. Astfel, fiecare nod cunoaște expeditorul pachetelor și numărul de hopuri pe care le-a trecut acest pachet. Apoi există o comparație cu datele din tabelul de rutare, iar dacă pachetul primit are mai puține hopuri, atunci tabelul este actualizat.
Avantaje și dezavantaje+ ușurință în implementare
- probleme la schimbarea topologiei și încărcării -
nu există schimb de date de rutare între noduri
( rutare vectorială la distanță în engleză )
DescriereDe asemenea, cunoscut sub numele de Distributed Bellman-Ford Routing sau Ford Fulkerson Algorithm. Acest algoritm este distribuit, iterativ și asincron. Poate fi gândit ca: „Spune-le vecinilor tăi cum arată lumea”. Fiecare gazdă menține un tabel de rutare cu o intrare pentru fiecare router de pe subrețea. Tabelul este un vector care conține 2 componente: linia selectată și distanța. Nodul estimează distanța (numărul de sărituri, întârziere sau lungimea cozii) până la fiecare vecin și o trimite vecinilor săi, care la rândul lor fac același lucru. Ca urmare a informațiilor primite, fiecare nod recalculează tabelul de rutare. Folosit în protocolul de rutare RIP . A fost folosit pentru prima dată în ARPANET .
AlgoritmSă presupunem că tabelul tocmai a fost primit de la vecinul X, unde Xi este estimarea lui X despre cât timp durează pentru a ajunge la routerul i. Dacă un router știe că transferul de date către X ia m, atunci știe și că poate ajunge la orice router i prin X în X i +m.
Avantaje și dezavantaje+ auto-organizare
+ implementare relativ simplă
- convergență slabă ("convergență")
- dificultăți la extinderea rețelei
La utilizarea algoritmului, problemele apar atunci când unul dintre noduri este deconectat de la rețea - problema „Numără până la infinit” (numărează până la infinit).
Prevenire: Algoritmul Split Horizont - „nu-mi spune ce ți-am spus”
Rutare în funcție de starea legăturiiEngleză Rutarea stării legăturii
DescriereAlgoritm legat de algoritmi adaptativi și bazat pe analiza stării legăturilor. Poate fi gândit ca: „Spune lumii cine sunt vecinii tăi”. La început, un nod își cunoaște doar vecinii și metrica legăturilor care îl conectează la aceștia. În procesul de schimb de informații cu nodurile învecinate, nodul primește informații despre topologia rețelei, în timp ce schimbă doar informații despre modificările care au avut loc. Ca rezultat, fiecare nod cunoaște întreaga topologie a rețelei. A fost aplicat pentru prima dată la ARPANET în 1979 și a înlocuit algoritmul vector de distanță. Motivele tranziției au fost:
( difuzare în limba engleză )
unicast - 1:1
multicast - 1:n
difuzare - 1:* (1:toate)
Fiecare pachet conține o listă a tuturor țintelor. Fiecare nod creează pentru fiecare conexiune de ieșire o copie a pachetului, care conține doar adresele acelor noduri care sunt accesibile prin această conexiune.
MulticastingEngleză rutare multicast
Algoritmul Spanning TreeEngleză copac spanning
DescriereSpanning Tree: Un grafic care nu conține bucle. Arborele spanning este cunoscut de toate nodurile. În conformitate cu aceasta, fiecare nod trimite copii ale pachetelor
Redirecționare cale inversă (Inundare cale inversă)Algoritmul este cea mai simplă și neadaptativă opțiune. Fiecare pachet primit este transmis pe toate liniile, cu excepția celei prin care a fost primit. În acest caz, doar expeditorul trebuie să cunoască întregul arbore de acoperire. Algoritm: Fiecare router știe calea pe care ar trebui să o folosească pentru pachetele unicast. Când un pachet este primit, acesta verifică dacă pachetul a fost primit pe linia utilizată în mod normal pentru pachetele unicast. Dacă da, atunci pachetul este redirecționat pe toate liniile, cu excepția celei prin care a fost primit. În caz contrar, pachetul este abandonat.
Difuzare cale inversăSpre deosebire de redirecționarea cale inversă, pachetele sunt trimise doar pe liniile pe care alte noduri primesc date.
Acest algoritm calculează calea cea mai scurtă de la rădăcina arborelui la noduri. Ideea este de a crea o grămadă de noduri Q, pentru care ruta optimă a fost deja determinată. Operatorul generează tabele de rutare care sunt încărcate când este inițializat și nu mai sunt modificate. Bazat pe algoritmul lui Dijkstra .
AlgoritmCea mai scurtă distanță de la A la D
+ simplitate
+ rezultate bune cu topologia și încărcarea rețelei constante
Acest algoritm este unul dintre algoritmii neadaptativi. Ia în considerare nu numai distanța dintre routere, ci și sarcina rețelei. Util pentru găsirea unei rute pe distanțe lungi cu întârzieri mari în livrarea pachetelor
ExempluGraficul dat pentru capacitatea și matricea de trafic
| linia | λi ( pachete /sec) |
|---|---|
| AB | 3(AB) + 7(ABC) + 7(BAD) + 4(BAF) + 3(BADG) =24 |
| ANUNȚ | 4(AD) + 2(ADE) + 2(ADG) + 5(ADEH) + 7(RAU) + 3(BADG) = 23 |
| AF | 5(AF) + 4(BAF) = 9 |
| î.Hr | 7(ABC) + 3(BC) + 4(BCH) = 14 |
| FI | 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 |
| linia | λi ( pachete /sec) | µCi (pachete / sec) | Ti ( msec) |
|---|---|---|---|
| AB | 24 | cincizeci | 38,46 |
| ANUNȚ | 23 | cincizeci | 37.04 |
| AF | 9 | 37,5 | 35.09 |
| î.Hr | paisprezece | 25 | 90,91 |
| FI | 3 | cincizeci | 21.28 |
| CE | cincisprezece | 75 | 16.67 |
| CH | 12 | cincizeci | 26.32 |
| DE | 40 | cincizeci | 100 |
| D.F. | 24 | 25 | 1000 |
| EH | 26 | cincizeci | 41,67 |
| FG | unu | 100 | 10.1 |
| GH | 7 | 62,5 | 18.02 |
| DG | 7 | 62,5 | 18.02 |
| linia | λi ( pachete /sec) | µCi (pachete / sec) | Ti ( msec) | Wi _ |
|---|---|---|---|---|
| AB | 24 | cincizeci | 38,46 | 0,117 |
| ANUNȚ | 23 | cincizeci | 37.04 | 0,112 |
| AF | 9 | 37,5 | 35.09 | 0,044 |
| î.Hr | paisprezece | 25 | 90,91 | 0,068 |
| FI | 3 | cincizeci | 21.28 | 0,015 |
| CE | cincisprezece | 75 | 16.67 | 0,073 |
| CH | 12 | cincizeci | 26.32 | 0,059 |
| DE | 40 | cincizeci | 100 | 0,195 |
| D.F. | 24 | 25 | 1000 | 0,117 |
| EH | 26 | cincizeci | 41,67 | 0,127 |
| FG | unu | 100 | 10.1 | 0,005 |
| GH | 7 | 62,5 | 18.02 | 0,034 |
| DG | 7 | 62,5 | 18.02 | 0,034 |
Deoarece valoarea rezultată este prea mare, aceasta poate fi redusă prin înlocuirea căii cu cea mai mare întârziere DF( Ti , max = 1000 msec ) cu calea D->G->F
Este cel mai simplu algoritm de rutare pentru distribuirea informațiilor într-o rețea. Când un pachet este primit, fiecare nod îl transmite către nodurile învecinate, cu excepția celui de la care provine pachetul.
Acest algoritm are o eficiență scăzută datorită încărcării crescute a rețelei.
Pentru a îmbunătăți eficiența algoritmului, sunt utilizate următoarele metode:
Scopul principal al algoritmului este de a calcula rute alternative și costurile rutei. Costul este probabilitatea de a utiliza o rută alternativă. În funcție de aceasta, se va folosi de fiecare dată o rută diferită, ceea ce va duce la scăderea numărului de pachete nelivrate. Utilizarea acestei metode face ca o rețea de computere să fie foarte fiabilă. Metoda este folosită cel mai adesea pentru rețelele mobile, unde starea rețelei se poate schimba frecvent și unele routere pot eșua.
Engleză Rutare ierarhică Algoritmi de un singur nivel sau ierarhici. Unii algoritmi de rutare operează într-un spațiu de un singur nivel, în timp ce alții folosesc o ierarhie de rutare. Într-un sistem de rutare cu un singur strat, toate routerele sunt egale între ele. Într-un sistem de rutare ierarhic, unele routere formează ceea ce constituie baza (baza) de rutare. De exemplu, cele care se află pe autostrăzile de mare viteză. Pachetele de la routerele non-core călătoresc către și prin routerele de bază până când ajung în zona de destinație comună. Din acel moment, ei călătoresc de la ultimul router principal prin unul sau mai multe routere non-core până la destinația lor finală. Sistemele de rutare stabilesc adesea grupuri logice de noduri numite domenii sau zone. În sistemele ierarhice, unele routere dintr-un domeniu pot comunica cu routere din alte domenii, în timp ce alte routere din acel domeniu pot comunica doar cu routere din propriul domeniu. În rețelele foarte mari, pot exista niveluri ierarhice suplimentare. Routerele de la cel mai înalt nivel ierarhic formează baza de rutare. Principalul avantaj al rutare ierarhică este că imită organizarea majorității companiilor și, prin urmare, le susține foarte bine tiparele de trafic. Majoritatea traficului de rețea al unei companii este concentrat în domeniul său, astfel încât routerele intra-domeniu trebuie să știe doar despre alte routere din domeniul lor, astfel încât algoritmii lor de rutare pot fi simplificați. În consecință, traficul de actualizare de rutare poate fi, de asemenea, redus, în funcție de algoritmul de rutare utilizat.