Algoritmul de actualizare difuză dublă

Înainte de a începe să citiți acest articol, vă sfătuim să vă familiarizați cu materialul despre calculul căii în funcție de algoritmul Bellman - Ford.

Algoritmul de actualizare de difuzie (difuzând algoritmul de actualizare -dual) este unul dintre cei doi algoritmi discutați aici inițial destinat implementării într-o rețea distribuită. Este unic prin faptul că elimină, de asemenea, informații despre realizabilitatea și topologia conținute în automata finală a algoritmului. Alți algoritmi au discutat aici lăsând îndepărtarea informațiilor la discreția de implementare a protocolului și nu ia în considerare acest aspect al activității algoritmului în cadrul algoritmului în sine.

Până în 1993, Belman-Ford și Dijkstra au fost implementate ca algoritmi distribuiți în mai multe protocoale de rutare. Experiența câștigată ca urmare a acestor implementări și implementări precoce au condus la "a doua val" de cercetare și reflecție asupra problemei de rutare în rețelele de comutare a rețelei, ceea ce a dus la apariția vectorului de cale și a dualului.

Deoarece dual este conceput ca algoritm distribuit, este mai bine să descriem lucrarea sa în rețea. În acest scop, figurile 8 și 9 sunt utilizate. Pentru a explica dual, acest exemplu va fi urmărit într-un curent de trei destinații, iar apoi modificările sunt procesate în starea de disponibilitate pentru aceleași elemente de destinație. În primul exemplu, cazul va fi luat în considerare atunci când există o cale alternativă, dar nu există un vecin în aval, al doilea va lua în considerare cazul atunci când există o cale alternativă și un vecin din aval.

În figura 8, studiul D din punctul de vedere al:

1. A învață două moduri de D:

1. A nu va recunoaște calea prin b, deoarece B folosește a ca succesor:
2. A Comparați căile disponibile și selectează cea mai scurtă cale fără bucle:
3. A verifică căile rămase pentru a determina dacă există oricare dintre ei în aval vecini:

A știe acest lucru deoarece C anunță calea către D cu metrica sa locală egală cu 3.

A Menține o metrică locală C în tabelul său de topologie.

În consecință, A cunoaște valoarea locală în C și valoarea locală din A.

1. 3 (Costul în c) = 3 (costul din A), astfel încât acest traseu poate fi buclă, prin urmare, C nu îndeplinește starea fezabilității. C nu este etichetat ca vecini din aval.

Vecinii din aval în dual se numesc potențiali succesori. Să presupunem că canalul [A, H] nu funcționează. DUAL nu se bazează pe actualizări periodice, deci A nu poate aștepta doar o altă actualizare cu informații fiabile. Mai degrabă, trebuie să urmeze în mod activ o cale alternativă. Astfel, acesta este un proces de detectare difuză a unei căi alternative. Dacă canalul [A, H] nu funcționează, având în vedere numai D:

1. O verifică tabelul local pentru posibile succesori (vecinii din aval).
2. Nu există posibili succesori, deci trebuie să găsească o cale alternativă fără bucle pentru D (dacă există).
3. A trimite o cerere fiecărui vecin pentru a determina dacă există o cale alternativă fără bucle la D.
4. În C:
5. În B:
6. A primește aceste răspunsuri:

În figura 9, elementul de destinație (d) a fost mutat cu H la E. Aceasta va fi utilizată în al doilea exemplu.

În acest exemplu, există un posibil succesor (vecinul din aval).

Studiul D din punctul de vedere al:

1. A învață două moduri de D:
2. A nu va recunoaște nici o cale prin B:
3. A Comparați căile disponibile și selectează cea mai scurtă cale fără bucle:
4. A verifică căile rămase pentru a determina dacă există oricare dintre ei în aval vecini:

Dacă canalul [A, C] nu funcționează, luați în considerare pur și simplu:

1. O verifică tabelul de topologie locală pentru un posibil succesor.
2. Posibile succesor există prin H.
3. A comută masa locală pe H ca fiind cea mai bună cale.
4. A trimite o actualizare a vecinilor săi, menționând că costul său de realizare D sa schimbat de la 3 la 4.

După cum puteți vedea, procesarea atunci când există un posibil succesor, mult mai rapid și mai ușor decât fără ea. În rețelele în care protocolul de rutare a fost desfășurat prin utilizarea dublă (în special, EIGRP), unul dintre principalele obiective de proiectare va limita volumul oricăror cereri generate în absența unui posibil succesor. Zona de solicitare este principalul factor determinant Cum se completează rapid algoritmul dublu și, prin urmare, cât de repede converge rețeaua.

Figura 10 prezintă mașina dublă terminată de bază.

Lucrurile incluse în traseu se înrăutățește (degradarea traseului) pot fi:

• Eșecul canalului sau al vecinului conectat
• Obținerea unei actualizări pentru un traseu cu o metrică mai mare
• Obținerea unei interogări de la actualul succesor
• Obținerea unui nou traseu de la un vecin
• Un nou vecin a fost găsit, precum și rutele prin care se poate obține
• Obținerea tuturor cererilor trimise vecinilor atunci când traseul se înrăutățește