--- format: DocBook title: Anhang: Berechnung des Routingverlaufs einer einfachen IGP-Kopplung zur Veranschaulichung des counting-to-infinity Problems ... <article> <articleinfo> <title>Anhang: Berechnung des Routingverlaufs einer einfachen IGP-Kopplung zur Veranschaulichung des counting-to-infinity Problems</title> </articleinfo> <simpara>Dieses Dokument ist ein Anhang des Dokuments <ulink url="Fussgaengerzonenproblem">Fußgängerzonenproblem</ulink>. <simpara>Im Folgenden wird die Dynamik des Routings in einer IGP-Kopplung als eine Folge von Zustandstabellen veranschaulicht. In diesem Beispiel erfolgt eine Partitionierung der Router { S } und { A B C }, was zum Kreislauf einer von S stammenden Route führt. Wie man beim Vergleich der Zustände T=5 und T=8 sieht, entsteht ein counting-to-infinity Kreislauf, der bei jedem Durchgang die Metrik der Route um 3 erhöht.</simpara> <table> <tgroup cols="2"> <colspec align="left" /> <colspec align="left" /> <thead> <row> <entry> Notation </entry> </row> </thead> <tbody> <row> <entry> T=0, T=1, ... </entry> <entry> Nr. des Routingzyklus. Ein Routingszyklus umfasst den Transport einer Route durch eine IGP-Instanz und ihre Verarbeitung im Router. Das läuft in allen IGPs und Routern parallel ab, sodass zum "Zeitpunkt" T=n+1 im gesamten Diagramm der Folgezustand von T=n erreicht ist. </entry> </row> <row> <entry> S </entry> <entry> Quellrouter für den Präfix der betrachteten Route. Der Präfix wird nicht mitnotiert, da er sich nicht ändert. </entry> </row> <row> <entry> A, B, C </entry> <entry> Grenzrouter der betrachteten IGP-Kopplung. </entry> </row> <row> <entry> a, b, c, d </entry> <entry> IGP-Instanzen der betrachteten IGP-Kopplung. </entry> </row> <row> <entry> 1, 2, 3, ... </entry> <entry> Metrikwerte einer einfachen hop count Metrik. Diese Metrik wird global verwendet, d.h. gilt in allen betrachteten IGPs. </entry> </row> <row> <entry> A(a) <- S:1 </entry> <entry> Die Routingtabelle für das IGP a im Router A erhält aus dem IGP a eine Route für den betrachteten Präfix mit next hop S und Metrik 1. </entry> </row> <row> <entry> —————————<br /> B = A:2<C:3 </entry> <entry> Die zentrale Routingtabelle des Routers B enthält für den betrachteten Präfix eine Route über A mit Metrik 2, sowie eine Route über C mit Metrik 3. Tie-breaker bei gleicher Metrik ist die Router ID. "<" ist das Symbol der so entstehenden totalen Ordnungsrelation auf den Routen der zentralen Tabelle des Routers. </entry> </row> <row> <entry> => A:1 -> b </entry> <entry> Die Route zum betrachteten Präfix mit der Metrik 1 wird weiterhin vom Router A mit next hop self ins IGP b redistribuiert. </entry> </row> <row> <entry> => retract A:1 -> b </entry> <entry> Die Route zum betrachteten Präfix mit der Metrik 1 wird vom Router A aus dem IGP b zurückgezogen. </entry> </row> <row> <entry> => new B:3 -> b </entry> <entry> Die Route zum betrachteten Präfix mit der Metrik 1 wird vom Router B mit next hop self ins IGP b exportiert, wohin sie im vorigen Zyklus noch nicht exportiert wurde. </entry> </row> <row> <entry> ... * </entry> <entry> Dieser Eintrag wurde im aktuellen Routingzyklus verändert. </entry> </row> </tbody> </tgroup> </table> <informaltable> <tgroup cols="2"> <colspec align="center" /> <colspec align="center" /> <thead> <row> <entry> Ausgangssituation <br /> (T=0) </entry> <entry> A hat die direkte<br /> Route von S<br /> verloren<br /> (T=1) </entry> <entry> </entry> </row> </thead> <tbody> <row> <entry> S <br /> |a <br /> A <br /> b / \ c <br /> B—C <br /> d </entry> <entry> S<br /> a <br /> A <br /> b / \ c<br /> B—C<br /> d<br /> </entry> </row> </tbody> </tgroup> </informaltable> <table frame="all"> <tgroup cols="9", align='left'> <thead> <row> <entry> T=0 </entry> <entry> T=1 </entry> <entry> T=2 </entry> <entry> T=3 </entry> <entry> T=4 </entry> <entry> T=5 </entry> <entry> T=6 </entry> <entry> T=7 </entry> <entry> T=8 </entry> </row> </thead> <tbody> <row> <entry> A(a) <- S:1 <br /> A(b) <- <br /> A(c) <- <br /> ————————— <br /> A = S:1 </entry> <entry> A(a) <- * <br /> A(b) <- <br /> A(c) <- <br /> ————————— <br /> A= * </entry> <entry> A(a) <- <br /> A(b) <- <br /> A(c) <- <br /> ————————— <br /> A = </entry> <entry> A(a) <- <br /> A(b) <- B4 * <br /> A(c) <- C4 * <br /> ————————— <br /> A = B:4<C:4 * </entry> <entry> A(a) <- <br /> A(b) <- *<br /> A(c) <- *<br /> ————————— <br /> A = * </entry> <entry> A(a) <- <br /> A(b) <- <br /> A(c) <- <br /> ————————— <br /> A = </entry> <entry> A(a) <- <br /> A(b) <- B:7 *<br /> A(c) <- <br /> ————————— <br /> A = B:7 * </entry> <entry> A(a) <- <br /> A(b) <- *<br /> A(c) <- <br /> ————————— <br /> A = * </entry> <entry> A(a) <- <br /> A(b) <- <br /> A(c) <- <br /> ————————— <br /> A = </entry> </row> <row> <entry> => A:1 -> b <br /> => A:1 -> c </entry> <entry> => retract A:1 -> b * <br /> => retract A:1 -> c * </entry> <entry> </entry> <entry> => new A:4 -> c * </entry> <entry> => retract A:4 -> c * </entry> <entry> </entry> <entry> => new A:7 -> c * </entry> <entry> => retract A:7 -> c * </entry> <entry> </entry> </row> <row> <entry> </entry> </row> <row> <entry> B(b) <- A:2<br /> B(d) <- C:3<br /> ————————— <br /> B = A:2<C:3 </entry> <entry> B(b) <- A:2<br /> B(d) <- C:3<br /> ————————— <br /> B = A:2<C:3 </entry> <entry> B(b) <- *<br /> B(d) <- C:3<br /> ————————— <br /> B = C:3 * </entry> <entry> B(b) <- <br /> B(d) <- *<br /> ————————— <br /> B = </entry> <entry> B(b) <- <br /> B(d) <- <br /> ————————— <br /> B = </entry> <entry> B(b) <- <br /> B(d) <- C:6 *<br /> ————————— <br /> B = C:6 * </entry> <entry> B(b) <- <br /> B(d) <- *<br /> ————————— <br /> B = * </entry> <entry> B(b) <- <br /> B(d) <- <br /> ————————— <br /> B = </entry> <entry> B(b) <- <br /> B(d) <- C:9 *<br /> ————————— <br /> B = C:9 * </entry> </row> <row> <entry> => B:2 -> d </entry> <entry> => B:2 -> d </entry> <entry> => retract B:2 -> d * <br /> => new B:3 -> b </entry> <entry> => retract B:3 -> b </entry> <entry> </entry> <entry> => new B:6 -> b </entry> <entry> => retract B:6 -> b * </entry> <entry> </entry> <entry> => new B:9 -> b * </entry> </row> <row> <entry> </entry> </row> <row> <entry> C(c) <- A:2 <br /> C(d) <- B:3 <br /> ————————— <br /> C = A:2<B:3 </entry> <entry> C(c) <- A:2 <br /> C(d) <- B:3 <br /> ————————— <br /> C = A:2<B:3 </entry> <entry> C(c) <- * <br /> C(d) <- B:3 <br /> ————————— <br /> C = B:3 * </entry> <entry> C(c) <- <br /> C(d) <- *<br /> ————————— <br /> C = </entry> <entry> C(c) <-A:5 * <br /> C(d) <- *<br /> ————————— <br /> C = A:5 </entry> <entry> C(c) <- * <br /> C(d) <- <br /> ————————— <br /> C = * </entry> <entry> C(c) <- <br /> C(d) <- <br /> ————————— <br /> C = </entry> <entry> C(c) <- A:8 *<br /> C(d) <- <br /> ————————— <br /> C = A:8 </entry> <entry> C(c) <- *<br /> C(d) <- <br /> ————————— <br /> C = * </entry> </row> <row> <entry> => C:2 -> d </entry> <entry> => C:2 -> d </entry> <entry> => retract C:2 -> d * <br /> => new C:3 -> c * </entry> <entry> => retract C:3 -> c </entry> <entry> => new c:5 -> d * </entry> <entry> => retract C:5 -> d * </entry> <entry> </entry> <entry> => new C:8 -> d * </entry> <entry> => retract C:8 -> d * </entry> </row> </tbody> </tgroup> </informaltable> </article>