Antaŭ ol vi komencas legi ĉi tiun artikolon, ni konsilas vin konatiĝi kun la materialo pri la kalkulo de la vojo laŭ la Bellman-Ford-algoritmo.
La disvastiga ĝisdatiga algoritmo (difuzanta ĝisdatiga algoritmo -dal) estas unu el la du algoritmoj diskutitaj ĉi tie origine celitaj por efektivigo en distribuita reto. Estas unika, ke ĝi ankaŭ forigas informojn pri atingebleco kaj topologio enhavita en la finaj aŭtomatoj de la algoritmo. Aliaj algoritmoj diskutitaj ĉi tie lasas la forigon de informoj laŭ la bontrovo de la efektivigo de la protokolo, kaj ne konsideras ĉi tiun aspekton de la laboro de la algoritmo ene de la algoritmo mem.
Antaŭ 1993, Bellman-Ford kaj Dijkstra estis efektivigitaj kiel distribuitaj algoritmoj en pluraj eniraj protokoloj. La sperto akirita kiel rezulto de ĉi tiuj fruaj efektivigoj kaj deplojoj kondukis al la "dua ondo" de esplorado kaj pripensado pri la problemo de enrutado en retaj ŝaltantaj retoj, kiuj kondukis al la apero de la Vetkvanto kaj Duobla.
Ĉar duobla estas desegnita kiel distribuita algoritmo, estas plej bone priskribi lian laboron en la reto. Por ĉi tiu celo, la ciferoj 8 kaj 9 estas uzataj. Por klarigi duoblan, ĉi tiu ekzemplo estos spurita en fluo de tri cellokoj, kaj tiam ŝanĝoj estas prilaboritaj en la havebleco-ŝtato por la samaj celaj eroj. En la unua ekzemplo, la kazo estos konsiderata kiam ekzistas alternativa vojo, sed ne ekzistas laŭflua najbaro, la dua konsideros la kazon kiam estas alternativa vojo kaj laŭflua najbaro.
En Figuro 8, studo D de la vidpunkto A:
- Lernas du manierojn al D:
- A ne rekonos la vojon tra B, ĉar B uzas kiel sian posteulon:
- Komparas la disponeblajn vojojn kaj elektas la plej mallongan vojon sen bukloj:
- Kontrolas la ceterajn vojojn por determini ĉu estas iuj el ili laŭflue najbaroj:
Ĝi scias ĉi tion ĉar C anoncas la itineron al D kun lia loka metriko egala al 3.
A konservas lokan metrikon C en sia topologia tablo.
Konsekvence, ĝi konas la lokan valoron en C kaj la loka valoro en A.
- 3 (Kosto en c) = 3 (kosto en a), do ĉi tiu vojo eble estas buklo, do, C ne kontentigas la kondiĉon de farebleco. C ne estas etikedita kiel laŭflue najbaroj.
Laŭfluaj najbaroj en duobla estas nomataj eblaj posteuloj. Supozu, ke la kanalo [a, H] ne funkcias. Duobla ne dependas de periodaj ĝisdatigoj, do a ne povas nur atendi alian ĝisdatigon kun fidinda informo. Prefere, A devas aktive sekvi alternativan vojon. Tiel, ĉi tio estas difusa detekta procezo de alternativa vojo. Se la kanalo [a, h] ne funkcias, konsiderante nur D:
- Kontrolas vian lokan tablon por eblaj posteuloj (laŭflue najbaroj).
- Ne estas eblaj posteuloj, do devas trovi alternativan vojon sen bukloj al D (se ĝi ekzistas).
- Sendas peton al ĉiu najbaro por determini ĉu ekzistas iu ajn alternativa vojo sen cikloj al D.
- En C:
- En B:
- A ricevas ĉi tiujn respondojn:
En Figuro 9, la celloko (D) ero estis movita kun H al E. Ĉi tio estos uzata en la dua ekzemplo.
En ĉi tiu ekzemplo, ekzistas ebla posteulo (laŭflue najbaro).
Studo D de la vidpunkto A:
- Lernas du manierojn al D:
- A ne rekonos ian vojon tra b:
- Komparas la disponeblajn vojojn kaj elektas la plej mallongan vojon sen bukloj:
- Kontrolas la ceterajn vojojn por determini ĉu estas iuj el ili laŭflue najbaroj:
Se la kanalo [a, C] ne funkcias, simple konsiderante:
- Kontrolo ĝia tablo de loka topologio por ebla posteulo.
- Ebla posteulo ekzistas tra H.
- Ŝanĝas ĝian lokan tablon laŭ H kiel la plej bona maniero.
- Ĝi sendas ĝisdatigon al liaj najbaroj, notante ke lia kosto de atingo D ŝanĝis de 3 al 4.
Kiel vi povas vidi, prilaborado kiam ekzistas ebla posteulo, multe pli rapida kaj pli facila ol sen ĝi. En retoj, kie la Routing-protokolo estis deplojita per duobla (precipe, EIGRP), unu el la ĉefaj projektaj celoj limigos la volumenon de iuj petoj generitaj en la foresto de ebla posteulo. La peto-areo estas la ĉefa determinanta faktoro, kiel la duobla algoritmo estas rapide kompletigita kaj, do, kiel rapide la reto konverĝas.
Figuro 10 montras la bazan finitan duoblan maŝinon.
Aĵoj inkluzivitaj en la itinero plimalbonigas (degradación de la itinero) povas esti:
- Fiasko de la koneksa kanalo aŭ najbaro
- Akirante ĝisdatigon por itinero kun pli alta metriko
- Akiri demandon de la nuna posteulo
- Akiri novan itineron de najbaro
- Nova najbaro estis trovita, same kiel itineroj per kiuj ĝi povas akiri
- Akiri ĉiujn petojn senditaj al najbaroj kiam la vojo plimalbonigas
