Para se të filloni të lexoni këtë artikull, ne ju këshillojmë që të njiheni me materialin për llogaritjen e rrugës sipas algoritmit të Bellman - Ford.
Algoritmi i përditësimit të difuzionit (algoritmi i shpërndarë i përditësimit) është një nga dy algoritmet e diskutuara këtu të destinuara fillimisht për zbatim në një rrjet të shpërndarë. Është unike në atë që gjithashtu heq informacionin për arritjen dhe topologjinë e përfshirë në automatikën përfundimtare të algoritmit. Algoritme të tjera të diskutuara këtu lënë heqjen e informacionit në diskrecionin e zbatimit të protokollit dhe nuk e konsiderojnë këtë aspekt të punës së algoritmit brenda vetë algoritmit.
Deri në vitin 1993, Bellman-Ford dhe Dijkstra u zbatuan si algoritme të shpërndara në disa protokolle të rutimit. Përvoja e fituar si rezultat i këtyre implementimeve dhe vendosjeve të hershme çoi në "valën e dytë" të hulumtimit dhe reflektimit mbi problemin e drejtimit në rrjetet e kalimit të rrjetit, gjë që çoi në shfaqjen e vektorit të rrugës dhe të dyfishtë.
Meqenëse dual është projektuar si një algoritëm i shpërndarë, është më mirë të përshkruhet puna e tij në rrjet. Për këtë qëllim, shifrat 8 dhe 9 janë përdorur. Për të shpjeguar të dyfishtë, ky shembull do të gjurmohet në një rrjedhë të tre destinacioneve, dhe pastaj ndryshimet përpunohen në gjendjen e disponueshmërisë për të njëjtat sende të destinacionit. Në shembullin e parë, rasti do të konsiderohet kur ka një rrugë alternative, por nuk ka fqinj të rrymës, e dyta do ta konsiderojë rastin kur ka një rrugë alternative dhe fqinjë të rrymës.
Në figurën 8, studimi d nga pikëpamja A:
- Një mëson dy mënyra për të d:
- A nuk do ta njohë rrugën përmes B, sepse b përdor një si pasardhësin e saj:
- A krahason shtigjet e disponueshme dhe përzgjedh rrugën më të shkurtër pa sythe:
- Një kontrollon shtigjet e mbetura për të përcaktuar nëse ka ndonjë prej tyre fqinjët e rrymës:
A e di këtë sepse c njofton rrugën për të d me metrikën e saj lokale të barabartë me 3.
A mban një metrikë lokale C në tryezën e tij të topologjisë.
Rrjedhimisht, a di vlerën lokale në C dhe vlerën lokale në A.
- 3 (kostoja në c) = 3 (kosto në a), kështu që kjo rrugë mund të jetë lak, prandaj, c nuk e plotëson gjendjen e fizibilitetit. C nuk është etiketuar si fqinjët e rrymës.
Fqinjët e rrymës në të dyfishtë quhen pasardhës të mundshëm. Supozoni se kanali [A, H] nuk funksionon. Dual nuk mbështetet në përditësimet periodike, kështu që një nuk mund të presë vetëm për një përditësim tjetër me informacion të besueshëm. Përkundrazi, një duhet të ndjekë në mënyrë aktive një rrugë alternative. Kështu, kjo është një proces zbulimi i shpërndarë i një rruge alternative. Nëse kanali [a, h] nuk punon, duke pasur parasysh vetëm D:
- Një kontrollon tabelën tuaj lokale për pasardhësit e mundshëm (fqinjët e rrymës).
- Nuk ka pasardhës të mundshëm, kështu që një duhet të gjejë një rrugë alternative pa sythe për të d (nëse ekziston).
- A dërgon një kërkesë për secilin fqinj për të përcaktuar nëse ka ndonjë rrugë alternative pa sythe për D.
- Në C:
- Në b:
- A merr këto përgjigje:
Në figurën 9, artikulli i destinacionit (d) u zhvendos me H në E. Kjo do të përdoret në shembullin e dytë.
Në këtë shembull, ekziston një pasardhës i mundshëm (fqinj në drejtim të rrymës).
Studimi D Nga pikëpamja A:
- Një mëson dy mënyra për të d:
- A nuk do të njohë asnjë mënyrë përmes B:
- A krahason shtigjet e disponueshme dhe përzgjedh rrugën më të shkurtër pa sythe:
- Një kontrollon shtigjet e mbetura për të përcaktuar nëse ka ndonjë prej tyre fqinjët e rrymës:
Nëse kanali [a, c] nuk funksionon, thjesht duke pasur parasysh një:
- A kontrollon tabelën e saj të topologjisë lokale për një pasardhës të mundshëm.
- Pasardhësi i mundshëm ekziston përmes H.
- Një kalon tryezën e saj lokale në H si mënyra më e mirë.
- A dërgon një përditësim për fqinjët e saj, duke vënë në dukje se kostoja e saj e arritjeve D ka ndryshuar nga 3 në 4.
Siç mund ta shihni, përpunoni kur ka një pasardhës të mundshëm, shumë më të shpejtë dhe më të lehtë se pa të. Në rrjetet ku protokolli i rutimit u vendos duke përdorur dyfish (në veçanti, EIGRP), një nga objektivat kryesore të dizajnit do të kufizojë volumin e çdo kërkese të gjeneruar në mungesë të një pasuesi të mundshëm. Zona e kërkesës është faktori kryesor përcaktues se si algoritmi i dyfishtë është kompletuar shpejt dhe, prandaj, sa shpejt rrjeti konverton.
Figura 10 tregon makinën bazë të dyfishtë të dyfishtë.
Gjërat e përfshira në rrugë bëhet më keq (degradimi i rrugës) mund të jetë:
- Dështimi i kanalit ose fqinjit të lidhur
- Marrja e një përditësimi për një rrugë me një metrikë më të lartë
- Duke marrë një pyetje nga pasardhësi aktual
- Marrja e një rruge të re nga një fqinj
- U gjet një fqinj i ri, si dhe rrugët me të cilat mund të merrni
- Marrja e të gjitha kërkesave të dërguara për fqinjët kur rruga përkeqësohet
