Rechnernetze / Kommunikationssysteme

Routing

Routing ist im Wesentlichen ein graphentheoretisches Problem, das Finden des Weges mit den geringsten Kosten zwischen je zwei Knoten (Nodes). Netzwerke werden in der Regel als gerichtete bzw. ungerichtete gewichtete Graphen mit ausschließlich nichtnegativen Kantengewichten (Edges) angenommen, G = (N, E, w).

Für die Ermittlung des kürzesten Weges wird in der Regel eines der beiden Verfahren angewendet:

Vergleich der Verfahren:

Merkmal Distanzvektor Linkstate
Netzwerkansicht Lokal Global
Algorithmus verteilter Bellman-Ford Dijkstra
Konvergenz langsam schnell
Informationsaustausch Routing-Tabellen mit Nachbarn Link-Zustände mit allen Knoten
Routing-Schleifen anfällig weniger anfällig
negative Kantengew. möglich nicht optimal
Ressourcenbedarf niedrig hoch (CPU+Speicher)
Datenmenge niedriger höher
Beispiel RIP OSPF, IS-IS
Anwendung kleine Netze komplexere Netze

Aufgaben Routing

  1. Welche Metriken kommen für das Routing prinzipiell in Frage?
  2. Was sagt die Bellman-Ford-Gleichung aus und wie funktioniert Distanzvektor-Routing prinzipiell?
  3. Was besagt das Count-to-Infinity-Problem?
  4. Was bedeutet Split Horizon beim RIP-Protokoll?
  5. Wie funktioniert der Dijkstra-Algorithmus? Lösen Sie dazu die Aufgabe aus der Vermittlungsschicht.
  6. Was ist der Unterschied zwischen einem globalem Routing-Algorithmus und einem dezentralem Routing-Algorithmus?
  7. Was sind autonome Systeme und welchen Vorteil bieten diese für das Routing?
  8. Was bedeutet Supernetting?
  9. Wie funktioniert das Routing mittels BGP?
  10. Welche Informationen werden zwischen 2 BGP-Peers ausgetauscht?
  11. Was sagen die Begriffe Provider, Tier 1-3, Kunden, Peers, Uplinks aus?
  12. Lesen Sie den Abschnitt “Netze, Bälle, Datenströme – oder wie die Fußball-WM ins X-WiN kam” aus DFN-Mitteilungen 95. Diskutieren Sie die aus der beschriebenen Entwicklung des Peerings entstehenden Probleme. Im Dokument DFN-Mitteilungen 97 gibt es eine Grafik des Peerings des DFN.
  13. Ermitteln Sie die Verbindung zwischen Ihrem Internetprovider und dem Netz der HTW Dresden. Nutzen Sie dazu traceroute -A zur Anzeige der benutzten autonomen Systeme. Den physischen Ort der IP können Sie über z.B. über Link ermitteln oder Sie nutzen Open Visual Traceroute. Versuchen Sie, einen Zusammenhang zum o.g. Peerings des DFNs herzustellen.

Distanzvektor-Routing (Bellman-Ford-Algorithmus)

Schritte:

  1. Initialisierung (Entfernung zu allen anderen Knoten unendlich)
  2. Informationsaustausch zwischen direkten Nachbarn
  3. Aktualisierung: \((D_{x}(y) = \min (D_{x}(y), c(x,v) + D_{v}(y) )\)
  4. Konvergenz (Wiederholung bis keine Änderung mehr eintritt)

Aufgabe: Berechnen Sie die Routingtabelle für Knoten a nach einer Initialisierung im abgebildeten Netzwerk, wenn dieser folgende Nachrichten erhält:

6-Knoten

Linkstate-Routing (Dijkstra-Algorithmus)

BGP

Fakultativ

  1. Lesen Sie den Artikel über Routing im Internet Link.
  2. Informieren Sie sich bei BGP Routing Infos über den Stand der Routing-Tabellen.
  3. Geschichte des Internets in Deutschland Internet.

Lösungen:

  1. Durchsatz, Entfernung, Hop-Count, Preis, …
  2. Kürzester Weg ist das Minimum über alle möglichen Wege
  3. schlechte Nachrichten verbreiten sich u.U. nur langsam
  4. liefere keine gelernte Information zurück
  5. Dijkstra
  6. Global vs Dezentral
  7. AS verkürzen Routingtabelle
  8. Zusammenfassung von Routen
  9. BGP

Distanzvektor

b=2, c=4 (d), d=1, e=2 (d), f=4 (d)

Linkstate

6-Knoten

10-Knoten

Knoten Next Hop Kosten
E C 11
D G 6
F G 7
J G 5
H G 7
I C 6

Literatur

Letzte Änderung: 24. November 2025 15:59