Dual Diffuse oppdateringsalgoritme

Før du begynner å lese denne artikkelen, anbefaler vi deg å gjøre deg kjent med materialet om beregningen av banen i henhold til Bellman-Ford-algoritmen.

Diffusjonsoppdateringsalgoritmen (diffusjonsoppdateringsalgoritmen -dual) er en av de to algoritmene som diskuteres her opprinnelig beregnet for implementering i et distribuert nettverk. Det er unikt fordi det også fjerner informasjon om oppnåelighet og topologi som finnes i algoritmenes endelige automata. Andre algoritmer som diskuteres her, la fjerningen av informasjonen etter implementeringen av implementeringen av protokollen, og ikke vurdere dette aspektet av algoritmenes arbeid innenfor algoritmen selv.

I 1993 ble Bellman-Ford og Dijkstra implementert som distribuerte algoritmer i flere rutingsprotokoller. Opplevelsen som er oppnådd som følge av disse tidlige implementeringene og distribusjonene førte til den "andre bølgen" for forskning og refleksjon om problemet med ruting i nettverksbytte nettverk, som førte til utseendet på banen vektor og dobbelt.

Siden dual er utformet som en distribuert algoritme, er det best å beskrive sitt arbeid på nettverket. For dette formål benyttes figurene 8 og 9. For å forklare dual, vil dette eksemplet bli sporet i en strøm av tre destinasjoner, og endringer behandles i tilgjengelighetstilstanden for de samme destinasjonselementene. I det første eksempelet vil saken bli vurdert når det er en alternativ sti, men det er ingen nedstrøms nabo, den andre vil vurdere saken når det er en alternativ sti og nedstrøms nabo.

I figur 8, studere D fra synspunktet A:

1. En lærer to måter å D:

1. A vil ikke gjenkjenne banen gjennom B, fordi B bruker en etterfølger:
2. En sammenligner de tilgjengelige banene og velger den korteste banen uten løkker:
3. En sjekker de resterende banene for å avgjøre om det er noen av dem nedstrøms naboer:

En vet dette fordi C kunngjør ruten til D med sin lokale metriske lik 3.

A opprettholder en lokal metrisk c i topologibordet.

Følgelig vet en den lokale verdien i C og den lokale verdien i A.

1. 3 (Kostnad i C) = 3 (Kostnad i A), så denne ruten kan være sløyfe, derfor tilfredsstiller C ikke tilstanden til muligheten. C er ikke merket som nedstrøms naboer.

Nedstrøms naboer i Dual kalles mulige etterfølgere. Anta at kanalen [a, h] ikke virker. Dual stoler ikke på periodiske oppdateringer, så en kan ikke bare vente på en annen oppdatering med pålitelig informasjon. Snarere må en aktivt følge en alternativ sti. Dermed er dette en diffus deteksjonsprosess av en alternativ bane. Hvis kanalen [A, H] ikke virker, vurderer bare D:

1. En sjekker ditt lokale bord for mulige etterfølgere (nedstrøms naboer).
2. Det er ingen mulige etterfølgere, så en må finne en alternativ sti uten løkker til D (hvis den eksisterer).
3. En sender en forespørsel til hver nabo for å avgjøre om det er noen alternativ sti uten løkker til D.
4. I c:
5. I B:
6. En får disse svarene:

I figur 9 ble destinasjonsdelen (D) flyttet med H til E. Dette vil bli brukt i det andre eksemplet.

I dette eksemplet er det en mulig etterfølger (nedstrøms nabo).

Studer D fra synspunktet A:

1. En lærer to måter å D:
2. A vil ikke gjenkjenne noen vei gjennom B:
3. En sammenligner de tilgjengelige banene og velger den korteste banen uten løkker:
4. En sjekker de resterende banene for å avgjøre om det er noen av dem nedstrøms naboer:

Hvis kanalen [A, C] ikke virker, bare vurderer A:

1. En sjekker sin tabell med lokal topologi for en mulig etterfølger.
2. Mulig etterfølger eksisterer gjennom H.
3. En bytter sitt lokale bord på H som den beste måten.
4. A sender en oppdatering til naboene, og bemerker at kostnaden for prestasjon D har endret seg fra 3 til 4.

Som du kan se, behandler når det er en mulig etterfølger, mye raskere og enklere enn uten det. I nettverk hvor rutingsprotokollen ble distribuert ved hjelp av dual (spesielt EIGRP), vil et av de viktigste designmålene begrense volumet av eventuelle forespørsler som genereres i fravær av en mulig etterfølger. Forespørselsområdet er den viktigste avgjørende faktoren hvordan den doble algoritmen er raskt fullført, og dermed hvor raskt nettverket konvergerer.

Figur 10 viser den grunnleggende ferdige dual maskinen.

Ting inkludert i ruten blir verre (nedbrytning av ruten) kan være:

• Feil i den tilkoblede kanalen eller naboen
• Oppnå en oppdatering for en rute med en høyere metrisk
• Få en forespørsel fra den nåværende etterfølgeren
• Få en ny rute fra en nabo
• En ny nabo ble funnet, så vel som ruter som den kan få
• Få alle forespørsler sendt til naboer når ruten forverres