Netze	Material historische Beispiele Einstieg Grundbegriffe Netzhardware Universal-Empfänger Raw-Transceiver mini-Sender mini-Empfänger miniEthernet Transceiver Fehlererkennung Fehlerbehandlung Bus Rahmen Medium Access Control Routing Schichtenmodell Sockets Dienste im Internet Filius Real-Experimente Sicherheit Codes Programme Hardware Protokolle Glossar Bautipps Modem Lehrplan Unterricht Pfad: Startseite / Fächer / Informatik / Netze / Routing
Autor: mk 19.10.2007 12:10 11279	Routing

Routing-Problem 1

Wie kommt ein Paket (Rahmen) vom Rechner x zum Rechner y?

Antwort im lokalen Netz

Rechner x adressiert sein Paket mit y und schickt es im lokalen Netz los.

• 1.Fall

  Rechner y ist im gleichen lokalen Netz, liest sowieso alle Rahmen mit und greift sich 'sein Paket' heraus

• 2.Fall

  Rechner y ist nicht im gleichen lokalen Netz. Ein 'Gateway-Rechner' kennt alle möglichen Empfänger im lokalen Netz und weiß daher, wenn eine Adresse 'nicht zustellbar' ist. Er fühlt sich für das Paket verantwortlich und leitet es 'geeignet' weiter.

Routing-Problem 2

Wie kommt ein Paket vom Gateway-Rechner gx von x zum Gateway-Rechner gy von y?

Antwort

Der 'Router' A hat eine Tabelle, in der steht welcher Nachbar-Router geeignet wäre, das Paket zu y zu bringen. Er leitet das Paket an diesen Nachbarn weiter. Jeder Router hat eine Routing-Tabelle, so dass das Paket schließlich bei gy und dann bei y ankommt.
Das Bild von Christian Seise zeigt den prinzipiellen Weg aus dem HSG-Netz in ein Netz in New York. Natürlich besteht das 'richtige' Internet aus ein paar mehr Routern als im Beispiel gezeigt. Das Bild von Patrice Schwedler zeigt die Routing-Tabellen.

Routing-Problem 3

Wie stellen die Router ihre Routing-Tabellen auf?

(falsche) Antwort

Wenn eine 'Zentrale' eine Gesamtsicht (Karte des Internet) der Router hätte, so könnten z.B. über heuristische Suche die kürzesten Wege bestimmt werden, die Routing-Tabellen erstellt werden und über 'flooding' allen Routern bekannt gemacht werden.

Warum ist obige Antwort unrealistisch?

Wir spielen Router!

Material

• Graph des Routernetzes mit Kosten, nur der Spielleiter kennt diesen Graphen
• Schilder für Routername, Zettel mit Nachbarnamen und Kosten mit Büroklammern angeheftet
• Formulare für Routing-Tabellen, jeder Router braucht ca. 5?
• Formulare für Kopien (ohne Next-Hop) der Routing-Tabellen, Bedarf pro Router ca. 15?

Spielverlauf

1. Zunächst bereiten wir für jeden Router ein Schild mit seinem Namen vor. Außerdem ist an dem Schild vermerkt, mit welchen Nachbarroutern zu welchen Kosten er verbunden ist.
2. Dann legen wir für jeden Router eine Routing-Tabelle nach folgendem Muster an:

   Routing-Tabelle Nr __ des Routers __
   
   Ziel        Next-Hop      Kosten
   --------------------------------
   
   

   Ziel ist dabei die Adresse des eventuell weit entfernt liegenden Ziels. Next-Hop ist die Adresse eines unmittelbaren Nachbarn. Kosten können Verzögerungszeiten o.Ä. oder einfach die Anzahl der notwendigen Hops sein.
3. Die unmittelbaren Nachbarn können sofort eingetragen werden, etwa im Beispiel:

   Routing-Tabelle Nr 1 des Routers A
   
   Ziel        Next-Hop      Kosten
   --------------------------------
    B           B             2
    C           C             1
   

4. Jeder Router fertigt nun Teil-Kopien seiner Tabelle für seine unmittelbaren Nachbarn an. So fertigen z.B. die Router B und C anfänglich folgende Kopien an:

   Kopie der Routing-Tabelle Nr 1 des Routers B       Kopie der Routing-Tabelle Nr 1 des Routers C
   
   Ziel        Kosten                                 Ziel        Kosten
   ---------------------                              ---------------------
    A           2                                      A           1
    C           2                                      B           2
    D           1                                      D           3
                                                       E           2
   

5. Jeder Router schickt seinen unmittelbaren Nachbarn die Kopien seiner Tabelle.
6. Jeder Router wertet die empfangenen Informationen aus. So wird z.B. der Router A die Tabelle des Routers B folgendermaßen interpretieren:
   • nach A zu Kosten 2 --> uninteressant, A bin ich selber
   • nach C zu Kosten 2 --> uninteressant, nach C komme ich laut meiner Tabelle zu Kosten 1
   • nach D zu Kosten 1 --> interessant, ich kann also nach D via B zu Kosten 2+1 = 3 kommen --> Eintrag in Tabelle
   Nachdem auch die Kopie der Tabelle des Routers C verarbeitet ist, sieht die Tabelle von A dann so aus:

   Routing-Tabelle Nr 1 des Routers A
   
   Ziel        Next-Hop      Kosten
   --------------------------------
    B           B             2
    C           C             1
    D           B             3
    E           C             3
   

7. Schleifenbeginn:
   Jeder Router stellt fest, wer zur Zeit seine Nachbarn sind. Es ist ja denkbar, dass Routen weggebrochen oder neu hinzugekommen sind.
8. Jeder Router fertigt für jeden Nachbarn eine Kopie seiner Tabelle an.
9. Jeder Router sendet - auf das Kommando des Spielleiters - diese Kopien an seine Nachbarn.
10. Jeder Router baut sich eine neue Tabelle auf. Dazu trägt er zuerst seine Nachbarn ein. Dann verarbeitet er alle erhaltenen Kopien.
11. Schleifenende:
    Jetzt beginnt die Schleife von vorne!

Benutzen des Router-Netzes

Natürlich wird man nach der Stabilisierung der Routingtabellen einige 'Pakete' durch das Netz transportieren. Die Ziel- und Absender-Adressen könnten durch Klebezettel realisiert werden.

Simulationsprogramm zu RIP

Mit einem Simulations-Programm zum Routing-Information-Protocol kann man zunächst die Ergebnisse des Spiels überprüfen. Im Weiteren kann man die Auswirkungen von dynamischen Veränderungen anhand geeigneter Graphen im Routernetz studieren. Insbesondere kann das Count-To-Infinity-Problem an einem geeigneten Graphen veranschaulicht werden.
routing1.zip, Routing1_exe.zip

Aufgabe

Gib folgendes Netz in das Simulationsprogramm ein und simuliere RIP.

Entferne Routen und füge welche hinzu. Lösche insbesondere auch mal die Routen A-E und E-F, sodass E vom Netz unerreichbar wird. Wie reagiert der Algorithmus?

Eine reale Routing-Tabelle

Mit dem Kommando netstat -r bekommt man auf Windows- und Linux-Rechnern die lokale Routing-Tabelle angezeigt.

Das IP-Adress-System

IP-Adresse - wikipedia

Wieviele Hops sind es von Kaiserslautern nach Washington?

Mit dem Kommando tracert (traceroute) kann man auf Windows-Rechner eine Route verfolgen. Es gibt im Internet auch - kommerzielle - grafische Routenverfolger wie z.B. visualroute.visualware.com

Material

• Routing-Information-Protocol - wikipedia
• Rechenberg/Pomberger, Informatik-Handbuch, Distanzvektorverfahren, S.402
• Tanenbaum, Computernetzwerke, 3.Auflage, Distance-Vector-Routing, S.384
• Routing bei wikipedia
• Simulation of RIP and DVMRP Authors: Didier Gutacker and Robert Denda
• FH Coburg
• irvtool - An Internet Routing Visualization Tool
• Routing-Tabellen im Internet werden zu groß - Heise News-Ticker
• Der Erlrouter von Joern Engmann für Rainer Sokoll

lokal