wiki/Technik/Routing/Fussgaengerzonenproblem-Anhang-A.page

---
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) &lt;- 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&lt;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. "&lt;" 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 />
   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 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) &lt;- S:1 <br />
          A(b) &lt;- <br />
          A(c) &lt;- <br />
          —————————  <br />
          A = S:1
        </entry>
        <entry>
          A(a) &lt;- * <br />
          A(b) &lt;- <br />
          A(c) &lt;- <br />
          —————————  <br />
          A=      *
        </entry>
        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- <br />
          A(c) &lt;- <br />
          —————————  <br />
          A =
        </entry>
        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- B4 * <br />
          A(c) &lt;- C4 * <br />
          —————————  <br />
          A = B:4&lt;C:4 *
        </entry>

        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- *<br />
          A(c) &lt;- *<br />
          —————————  <br />
          A = *
        </entry>
        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- <br />
          A(c) &lt;- <br />
          —————————  <br />
          A =
        </entry>

        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- B:7 *<br />
          A(c) &lt;- <br />
          —————————  <br />
          A = B:7 *
        </entry>
        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- *<br />
          A(c) &lt;- <br />
          —————————  <br />
          A = *
        </entry>
        <entry>
          A(a) &lt;- <br />
          A(b) &lt;- <br />
          A(c) &lt;- <br />
          —————————  <br />
          A =
        </entry>
      </row>
      <row>
        <entry>
          =&gt; A:1 -&gt; b <br />
          =&gt; A:1 -&gt; c
        </entry>
        <entry>
          =&gt; retract A:1 -&gt; b * <br />
          =&gt; retract A:1 -&gt; c *
        </entry>
        <entry>
        </entry>
        <entry>
          =&gt; new A:4 -&gt; c *
        </entry>
        <entry>
          =&gt; retract A:4 -&gt; c *
        </entry>
        <entry>
        </entry>
        <entry>
          =&gt; new A:7 -&gt; c *
        </entry>
        <entry>
          =&gt; retract A:7 -&gt; c *
        </entry>
        <entry>
        </entry>
      </row>
      <row>
        <entry>
        </entry>
      </row>
      <row>
        <entry>
          B(b) &lt;- A:2<br />
          B(d) &lt;- C:3<br />
          —————————  <br />
          B = A:2&lt;C:3
        </entry>
        <entry>
          B(b) &lt;- A:2<br />
          B(d) &lt;- C:3<br />
          —————————  <br />
          B = A:2&lt;C:3
        </entry>
        <entry>
          B(b) &lt;- *<br />
          B(d) &lt;- C:3<br />
          —————————  <br />
          B = C:3 *
        </entry>
        <entry>
          B(b) &lt;- <br />
          B(d) &lt;- *<br />
          —————————  <br />
          B = 
        </entry>
        <entry>
        B(b) &lt;- <br />
          B(d) &lt;- <br />
          —————————  <br />
          B = 
        </entry>
        <entry>
          B(b) &lt;- <br />
          B(d) &lt;- C:6 *<br />
          —————————  <br />
          B = C:6 *
        </entry>
        <entry>
          B(b) &lt;- <br />
          B(d) &lt;- *<br />
          —————————  <br />
          B = *
        </entry>
        <entry>
          B(b) &lt;- <br />
          B(d) &lt;- <br />
          —————————  <br />
          B = 
        </entry>
        <entry>
          B(b) &lt;- <br />
          B(d) &lt;- C:9 *<br />
          —————————  <br />
          B = C:9 *
        </entry>
      </row>
      
      
      <row>
        <entry>
          =&gt; B:2 -&gt; d
        </entry>
        <entry>
          =&gt; B:2 -&gt; d
        </entry>
        <entry>
          =&gt; retract B:2 -&gt; d * <br />
 	  =&gt; new B:3 -&gt; b
        </entry>
        <entry>
          =&gt; retract B:3 -&gt; b
        </entry>
        <entry>
        </entry>
        <entry>
          =&gt; new B:6 -&gt; b
        </entry>
        <entry>
          =&gt; retract B:6 -&gt; b *
        </entry>
        <entry>
        </entry>
        <entry>
          =&gt; new B:9 -&gt; b *
        </entry>
      </row>
      <row>
        <entry>
        </entry>     
      </row>
      <row>
        <entry>
          C(c) &lt;- A:2 <br />
          C(d) &lt;- B:3 <br />
          —————————  <br />
          C = A:2&lt;B:3
        </entry>
        <entry>
          C(c) &lt;- A:2 <br />
          C(d) &lt;- B:3 <br />
          —————————  <br />
          C = A:2&lt;B:3
        </entry>
        <entry>
          C(c) &lt;- * <br />
          C(d) &lt;- B:3 <br />
          —————————  <br />
          C = B:3 *
        </entry>
        <entry>
          C(c) &lt;- <br />
          C(d) &lt;- *<br />
          —————————  <br />
          C = 
        </entry>
        <entry>
          C(c) &lt;-A:5 * <br />
          C(d) &lt;- *<br />
          —————————  <br />
          C = A:5
        </entry>
        <entry>
          C(c) &lt;- * <br />
          C(d) &lt;- <br />
          —————————  <br />
          C = *
        </entry>
        <entry>
          C(c) &lt;- <br />
          C(d) &lt;- <br />
          —————————  <br />
          C = 
        </entry>
        <entry>
          C(c) &lt;- A:8 *<br />
          C(d) &lt;- <br />
          —————————  <br />
          C = A:8
        </entry>
        <entry>
          C(c) &lt;- *<br />
          C(d) &lt;- <br />
          —————————  <br />
          C = *
        </entry>
      </row>
      <row>
        <entry>
          =&gt; C:2 -&gt; d
        </entry>
        <entry>
          =&gt; C:2 -&gt; d
        </entry>
        <entry>
          =&gt; retract C:2 -&gt; d * <br />
          =&gt; new C:3 -&gt; c *
        </entry>
        <entry>
          =&gt; retract C:3 -&gt; c
        </entry>
        <entry>
          =&gt; new c:5 -&gt; d *
        </entry>
        <entry>
          =&gt; retract C:5 -&gt; d *
        </entry>
        <entry>
        </entry>
        <entry>
          =&gt; new C:8 -&gt; d *
        </entry>
        <entry>
          =&gt; retract C:8 -&gt; d *
        </entry>
      </row>
      
    </tbody>
  </tgroup>
</informaltable>

</article>