In der letzten Lektion haben wir gesehen, dass Router Pakete an andere Router weiterleiten, wenn sie das Zielnetzwerk nicht kennen. Aber wie findet ein Paket den besten Weg durch ein Netzwerk mit vielen Routern? Das ist die Aufgabe von Routing-Algorithmen.

Das Internet als Graph

Das Internet besteht aus tausenden von Routern, die miteinander verbunden sind. Man kann dieses Netzwerk als Graphen darstellen:

• Knoten sind die Router
• Kanten sind die Verbindungen zwischen Routern
• Kantengewichte sind die “Kosten” einer Verbindung (z.B. Latenz in Millisekunden)

In diesem Beispiel sind A bis E Router. Die Zahlen auf den Kanten geben die “Kosten” an – je tiefer, desto besser. Das könnte die Latenz in Millisekunden sein oder eine andere Metrik.

Frage: Was ist der kürzeste Weg von A nach E?

Der Dijkstra-Algorithmus

Edsger Dijkstra entwickelte 1956 einen Algorithmus, der systematisch den kürzesten Weg von einem Startknoten zu allen anderen Knoten findet. Der Algorithmus ist elegant und wird heute noch in Navigationssystemen und Routing-Protokollen verwendet.

So funktioniert Dijkstra

1. Initialisierung: Setze die Distanz zum Startknoten auf 0, alle anderen auf ∞ (unendlich).
2. Wähle den unbesuchten Knoten mit der kleinsten Distanz.
3. Aktualisiere die Distanzen aller Nachbarn: Wenn der Weg über den aktuellen Knoten kürzer ist, übernimm die neue Distanz.
4. Markiere den aktuellen Knoten als besucht.
5. Wiederhole ab Schritt 2, bis alle Knoten besucht sind.

Beispiel: Kürzester Weg von A nach E

Wir führen den Algorithmus Schritt für Schritt durch:

Schritt 0 – Initialisierung:

Schritt 1 – Besuche A (kleinste Distanz: 0):

Nachbarn von A: B (Kosten 4), C (Kosten 2)

• Distanz zu B: min(∞, 0+4) = 4
• Distanz zu C: min(∞, 0+2) = 2

Schritt 2 – Besuche C (kleinste unbesuchte Distanz: 2):

Nachbarn von C: D (Kosten 1), E (Kosten 5)

• Distanz zu D: min(∞, 2+1) = 3
• Distanz zu E: min(∞, 2+5) = 7

Schritt 3 – Besuche D (kleinste unbesuchte Distanz: 3):

Nachbarn von D: B (Kosten 3), E (Kosten 2)

• Distanz zu B: min(4, 3+3) = 4 (keine Verbesserung)
• Distanz zu E: min(7, 3+2) = 5 (Verbesserung!)

Schritt 4 – Besuche B (kleinste unbesuchte Distanz: 4):

Nachbar von B: D (bereits besucht)

• Keine Aktualisierungen nötig.

Schritt 5 – Besuche E (kleinste unbesuchte Distanz: 5):

Alle Knoten besucht – fertig!

Ergebnis: Der kürzeste Weg von A nach E hat Kosten 5. Den Weg rekonstruieren wir über die Vorgänger: E ← D ← C ← A, also A → C → D → E.

Routing im Internet

Im echten Internet verwenden Router Protokolle wie OSPF (Open Shortest Path First), die auf Dijkstra basieren. Die Router tauschen dabei kontinuierlich Informationen über ihre Nachbarn und die Verbindungskosten aus. So kann jeder Router eine “Karte” des Netzwerks aufbauen und den besten Weg berechnen.

Die “Kosten” einer Verbindung können verschiedene Faktoren berücksichtigen:

• Latenz (Verzögerung in Millisekunden)
• Bandbreite (je mehr Kapazität, desto besser)
• Auslastung (überlastete Verbindungen vermeiden)
• Zuverlässigkeit (stabile Verbindungen bevorzugen)

Übungsaufgaben

Aufgabe 1: Dijkstra von Hand

Führen Sie den Dijkstra-Algorithmus für folgendes Netzwerk durch. Startknoten ist S, Ziel ist Z.

a) Füllen Sie die Tabelle aus. b) Was ist der kürzeste Weg von S nach Z und welche Kosten hat er?

Aufgabe 2: Alternative Wege

Im folgenden Netzwerk fällt die Verbindung zwischen C und E aus.

a) Was war der kürzeste Weg von A nach F, bevor die Verbindung ausfiel? b) Was ist der kürzeste Weg jetzt?

Aufgabe 3: Routing-Tabelle

Ein Router R ist direkt mit drei Netzwerken verbunden und hat folgende Routing-Tabelle:

Wohin leitet Router R Pakete mit folgenden Ziel-IPs weiter?

a) 10.0.1.100 b) 192.168.1.50 c) 8.8.8.8