Lernziele

• Sie verstehen, wie Router den besten Weg für Pakete durch ein Netzwerk finden.
• Sie können den Dijkstra-Algorithmus an einem einfachen Netzwerk von Hand durchführen.
• Sie können einen interaktiven Visualizer nutzen, um eigene Netze zu testen.

Das Wichtigste zuerst: das Internet als Graph

In der letzten Lektion haben wir gesehen, dass ein Router ein Paket an einen Nachbarrouter weiterleitet, wenn er das Ziel nicht direkt kennt. Aber wie findet ein Paket über viele Router hinweg den besten Weg? Das ist die Aufgabe von Routing-Algorithmen.

Dazu stellt man das Netz als Graphen dar:

• Knoten = die Router
• Kanten = die Verbindungen
• Kantengewichte = die «Kosten» einer Verbindung (z.B. Latenz in Millisekunden — je tiefer, desto besser)

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

Lösung

• A → B → D → E: $4 + 3 + 2 = 9$
• A → C → D → E: $2 + 1 + 2 = 5$
• A → C → E: $2 + 5 = 7$

Der kürzeste Weg ist A → C → D → E mit Kosten 5.

Von Hand bei fünf Knoten noch machbar — aber bei tausenden Routern braucht es einen systematischen Algorithmus.

Der Dijkstra-Algorithmus

Edsger Dijkstra entwickelte 1956 einen Algorithmus, der vom Startknoten aus den kürzesten Weg zu allen anderen Knoten findet. Er steckt heute in Navis und in Routing-Protokollen.

Er nutzt eine Prioritätswarteschlange: Knoten sind nach ihrer bisher bekannten Gesamtdistanz vom Start sortiert, der mit der kleinsten Distanz kommt zuerst dran.

1. Initialisierung: Distanz zum Start = 0, alle anderen = ∞. Start in die Warteschlange.
2. Entnimm den Knoten mit der kleinsten Distanz.
3. Prüfe alle Nachbarn: neue Distanz = aktuelle Distanz + Kantengewicht. Ist sie kleiner als die bisherige, aktualisiere sie.
4. Markiere den aktuellen Knoten als besucht.
5. Wiederhole ab Schritt 2, bis das Ziel besucht ist (oder die Warteschlange leer ist).

Schritt für Schritt: A nach E

Farben: grün = besucht, blau = in Queue, orange = aktuell

Schritt 0 — Initialisierung:

Schritt 1 — Besuche A (Distanz 0). Nachbarn: B (0+4=4), C (0+2=2).

Schritt 2 — Besuche C (Distanz 2). Nachbarn: D (2+1=3), E (2+5=7).

Schritt 3 — Besuche D (Distanz 3). Nachbarn: B (3+3=6, keine Verbesserung), E (3+2=5, besser!).

Schritt 4 — Besuche B (Distanz 4). Nachbar D ist schon besucht — keine Änderung.

Schritt 5 — Besuche E (Distanz 5). Ziel erreicht!

Ergebnis: kürzester Weg mit Kosten 5. Über die Vorgänger rückwärts: E ← D ← C ← A, also A → C → D → E.

Routing im echten Internet

Router nutzen Protokolle wie OSPF (Open Shortest Path First), die auf Dijkstra basieren. Sie tauschen laufend Infos über Nachbarn und Verbindungskosten aus, sodass jeder Router eine «Karte» des Netzes hat. Die «Kosten» können Latenz, Bandbreite, Auslastung oder Zuverlässigkeit abbilden.

🐍 Jetzt sind Sie dran

Übung 1: Dijkstra selbst erleben (einfach)

Bauen Sie sich unten ein eigenes Internet mit 6–9 Routern. Sagen Sie vor jedem Schritt voraus, welcher Knoten als Nächstes besucht wird — und prüfen Sie dann mit dem Visualizer.

Bedienung: Knoten anklicken = Start (roter Rand). Ctrl+Klick = Ziel. Knoten ziehen = verschieben. Dann Play oder schrittweise vorgehen. Der PQ-Button sortiert die Tabelle nach Priority Queue.

Übung 2: Alternative Wege bei Ausfall (mittel)

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

a) Was war der kürzeste Weg von A nach F vor dem Ausfall?
b) Was ist er jetzt?

Lösung

a) A → C → E → F: $1 + 2 + 1 = 4$.b) Ohne C–E: A → B → D → E → F: $2 + 5 + 2 + 1 = 10$ (besser als A → B → D → F mit 11). Kürzester Weg jetzt: A → B → D → E → F mit Kosten 10.

CIDR-Schreibweise

Die Schreibweise /24 ist eine Kurzform für eine Subnetmaske. Die Zahl gibt an, wie viele Bits zum Netzwerkteil gehören:

• /24 = 3 Bytes = 255.255.255.0
• /16 = 2 Bytes = 255.255.0.0
• /8 = 1 Byte = 255.0.0.0

Übung 3: Routing-Tabelle lesen (schwer)

Ein Router R hat diese Routing-Tabelle:

Zielnetzwerk	Nächster Hop	Kosten
10.0.1.0/24	direkt	0
10.0.2.0/24	direkt	0
10.0.3.0/24	direkt	0
192.168.1.0/24	10.0.1.5	3
192.168.2.0/24	10.0.2.10	5
0.0.0.0/0 (Standard)	10.0.3.1	–

Wohin leitet R weiter? a) 10.0.1.100 b) 192.168.1.50 c) 8.8.8.8

Lösung

a) im Netz 10.0.1.0/24 → direkt zugestellt.b) im Netz 192.168.1.0/24 → Weiterleitung an 10.0.1.5.c) in keinem bekannten Netz → Standardroute an 10.0.3.1.

Und wenn die Router nicht zur selben Firma gehören?

OSPF und Dijkstra funktionieren gut, solange alle Router zur gleichen Organisation gehören und offen Informationen austauschen. Aber das Internet besteht aus tausenden unabhängigen Netzwerken — was, wenn ein Paket von der Swisscom zu Google muss? Niemand verrät der Konkurrenz freiwillig seine interne Netzkarte. Wie das trotzdem zusammenspielt, sehen Sie in der nächsten Lektion: Das echte Internet.