Voordat u dit artikel begint te lezen, raden wij u aan u vertrouwd te maken met het materiaal over de berekening van het pad volgens de Bellman - Ford-algoritme.
Het diffusie-update-algoritme (diffuserende update-algoritme -dual) is een van de twee die hier die hier zijn bestemd voor implementatie in een gedistribueerd netwerk besproeid. Het is uniek omdat het ook informatie verwijdert over haalbaarheid en topologie die is opgenomen in de definitieve automaten van het algoritme. Andere algoritmen die hier worden besproken, laten het verwijderen van informatie over de discretie van de uitvoering van het protocol en beschouwt dit aspect van het algoritme in het algoritme zelf niet.
Tegen 1993 werden Bellman-Ford en Dijkstra geïmplementeerd als gedistribueerde algoritmen in verschillende routeringsprotocollen. De ervaring die is opgedaan als gevolg van deze vroege implementaties en implementaties leidden tot de "tweede golf" van onderzoek en reflectie over het probleem van routing in netwerkschakelnetwerken, wat leidde tot het uiterlijk van de padvector en dual.
Omdat dual is ontworpen als een gedistribueerd algoritme, is het het beste om zijn werk aan het netwerk te beschrijven. Voor dit doel worden figuren 8 en 9 gebruikt. Om Dual uit te leggen, wordt dit voorbeeld getraceerd in een stroom van drie bestemmingen en vervolgens worden wijzigingen verwerkt in de beschikbaarheidstoestand voor dezelfde bestemmingsitems. In het eerste voorbeeld zal de zaak worden overwogen wanneer er een alternatief pad is, maar er is geen downstream-buur, de tweede zal de zaak overwegen wanneer er een alternatief pad en stroomafwaartse buurman is.
In figuur 8, studeer d vanuit het oogpunt A:
- A Leert twee manieren om D:
- A herkent het pad niet via B, omdat B A als volgt gebruikt:
- A vergelijkt de beschikbare paden en selecteert het kortste pad zonder loops:
- A controleert de resterende paden om te bepalen of er een van hen stroomafwaartse buren zijn:
A weet dit omdat C de route aankondigt met zijn lokale metriek gelijk aan 3.
A handhaaft een lokale metrische C in zijn topologietabel.
Bijgevolg kent A de lokale waarde in C en de lokale waarde in A.
- 3 (Kosten in C) = 3 (kosten in A), dus deze route kan lus zijn, daarom voldoet C niet aan de toestand van haalbaarheid. C is niet geëtiketteerd als stroomafwaartse buren.
Downstream-buren in Dual worden mogelijke opvolgers genoemd. Stel dat het kanaal [A, H] niet werkt. Dual vertrouwt niet op periodieke updates, dus een kan niet alleen wachten op een andere update met betrouwbare informatie. In plaats daarvan moet een alternatief pad actief volgen. Dit is dus een diffuse detectieproces van een alternatief pad. Als het kanaal [A, H] niet werkt, gezien alleen D:
- A controleert uw lokale tabel voor mogelijke opvolgers (stroomafwaartse buren).
- Er zijn geen mogelijke opvolgers, dus een moet een alternatief pad vinden zonder loops naar D (als het bestaat).
- A stuurt een verzoek naar elke buurman om te bepalen of er een alternatief pad is zonder loops naar D.
- In c:
- In b:
- A krijgt deze antwoorden:
In figuur 9 werd het item van de bestemming (d) verplaatst met H tot E. Dit zal in het tweede voorbeeld worden gebruikt.
In dit voorbeeld is er een mogelijke opvolger (stroomafwaartse buur).
Studie D vanuit het oogpunt A:
- A Leert twee manieren om D:
- A zal geen enkele manier herkennen via B:
- A vergelijkt de beschikbare paden en selecteert het kortste pad zonder loops:
- A controleert de resterende paden om te bepalen of er een van hen stroomafwaartse buren zijn:
Als het kanaal [A, C] niet werkt, gezien een:
- A controleert zijn tabel met lokale topologie voor een mogelijke opvolger.
- Mogelijke opvolger bestaat via H.
- Een schakelt zijn lokale tafel op H als de beste manier.
- A stuurt een update naar zijn buren, waarvan de kosten van prestatie D zijn veranderd van 3 tot 4.
Zoals je kunt zien, verwerkt wanneer er een mogelijke opvolger is, veel sneller en gemakkelijker dan zonder. In netwerken waarbij het routeringprotocol werd ingezet met behulp van DUAL (in het bijzonder Eigrp), zal een van de belangrijkste ontwerpdoelstellingen het volume van eventuele verzoeken beperken die zijn gegenereerd in de afwezigheid van een mogelijke opvolger. Het verzoekgebied is de belangrijkste bepalende factor hoe het dubbele algoritme snel is voltooid en daarom, hoe snel het netwerk convergeert.
Figuur 10 toont de basisafgewerkte dubbele machine.
Dingen die in de route zijn opgenomen, worden erger (degradatie van de route) misschien:
- Falen van het aangesloten kanaal of de buurman
- Het verkrijgen van een update voor een route met een hogere metriek
- Een query krijgen van de huidige opvolger
- Een nieuwe route van een buurman krijgen
- Een nieuwe buur werd gevonden, evenals routes waarmee het kan krijgen
- Alle verzoeken die naar buren worden gestuurd toen de route verslechtert
