Dual diffus uppdateringsalgoritm

Innan du börjar läsa den här artikeln rekommenderar vi dig att bekanta dig med materialet om beräkningen av vägen enligt Bellman-Ford-algoritmen.

Diffusionsuppdateringsalgoritmen (diffusionsuppdateringsalgoritm -dual) är en av de två algoritmerna som diskuteras här ursprungligen avsedda för implementering i ett distribuerat nätverk. Det är unikt genom att det också tar bort information om uppnåbarhet och topologi som finns i algoritmens sista automat. Andra algoritmer som diskuteras här ger upphov till information efter eget gottfinnande, och inte överväga denna aspekt av algoritmens arbete inom själva algoritmen.

År 1993 genomfördes Bellman-Ford och Dijkstra som distribuerade algoritmer i flera routingprotokoll. Erfarenheten som uppnåtts till följd av dessa tidiga implementeringar och implementeringar ledde till "andra vågen" av forskning och reflektion över problemet med routing i nätverksomkopplingsnät, vilket ledde till utseendet på banvektorn och dubbla.

Sedan Dual är utformad som en distribuerad algoritm är det bäst att beskriva sitt arbete på nätverket. För detta ändamål används figurerna 8 och 9. Förklara dubbla, kommer detta exempel att spåras i en ström av tre destinationer, och sedan bearbetas ändringar i tillgänglighetstillståndet för samma destinationsposter. I det första exemplet kommer fallet att övervägas när det finns en alternativ väg, men det finns ingen nedströms granne, den andra kommer att överväga ärendet när det finns en alternativ väg och nedströms granne.

I figur 8 studera D från synvinkel A:

1. A lär sig två sätt att d:

1. A kommer inte att känna igen vägen genom B, eftersom B använder A som dess efterträdare:
2. A Jämför de tillgängliga banorna och väljer den kortaste vägen utan slingor:
3. A kontrollerar de återstående banorna för att avgöra om det finns någon av dem nedströms grannar:

A Känner detta eftersom C tillkännager vägen till D med sin lokala metriska lika med 3.

A upprätthåller en lokal metrisk C i sitt topologibord.

Följaktligen vet A. Det lokala värdet i C och det lokala värdet i A.

1. 3 (kostnad i c) = 3 (kostnad i a), så denna rutt kan vara slinga, därför uppfyller C inte villkoret för genomförbarhet. C är inte märkt som nedströms grannar.

Nedströms grannar i Dual kallas möjliga efterträdare. Antag att kanalen [A, H] inte fungerar. Dual lita inte på periodiska uppdateringar, så A kan inte bara vänta på en annan uppdatering med tillförlitlig information. Snarare måste ett aktivt följa en alternativ väg. Således är detta en diffus detekteringsprocess av en alternativ väg. Om kanalen [A, H] inte fungerar, med tanke på endast D:

1. A kontrollerar ditt lokala tabell för eventuella efterträdare (nedströms grannar).
2. Det finns inga möjliga efterträdare, så en måste hitta en alternativ väg utan loopar till d (om den existerar).
3. A skickar en förfrågan till varje granne för att avgöra om det finns någon alternativ väg utan loopar till D.
4. I C:
5. I B:
6. A får dessa svar:

I figur 9 flyttades destinationen (d) objektet med H till E. Detta kommer att användas i det andra exemplet.

I det här exemplet finns det en möjlig efterträdare (nedströms granne).

Studie D Från synvinkel A:

1. A lär sig två sätt att d:
2. A kommer inte att känna igen något sätt genom B:
3. A Jämför de tillgängliga banorna och väljer den kortaste vägen utan slingor:
4. A kontrollerar de återstående banorna för att avgöra om det finns någon av dem nedströms grannar:

Om kanalen [A, C] inte fungerar, med tanke på A:

1. A kontrollerar sitt bord med lokal topologi för en eventuell efterträdare.
2. Eventuell efterträdare existerar genom H.
3. En växlar sitt lokala bord på H som det bästa sättet.
4. A skickar en uppdatering till sina grannar och noterar att dess kostnad för prestation D har ändrats från 3 till 4.

Som du kan se, bearbeta när det finns en möjlig efterträdare, mycket snabbare och lättare än utan det. I nätverk där routingsprotokollet utnyttjades med användning av dubbla (i synnerhet EIGRP), kommer ett av de viktigaste designmålen att begränsa volymen av eventuella förfrågningar som genereras i avsaknad av en eventuell efterträdare. Förfrågningsområdet är den viktigaste avgörande faktorn hur dubbelalgoritmen snabbt är avslutad och därför hur snabbt nätverket konvergerar.

Figur 10 visar den grundläggande färdiga dubbla maskinen.

Saker som ingår i vägen blir värre (nedbrytning av rutten) kan vara:

• Misslyckande av den anslutna kanalen eller grannen
• Hämta en uppdatering för en rutt med en högre metrisk
• Få en fråga från den nuvarande efterträdaren
• Få en ny väg från en granne
• En ny granne hittades, liksom rutter genom vilka det kan få
• Få alla förfrågningar skickade till grannar när rutten förvärras