🌐 Netzwerk-Paketrouting

Wie findet der Dijkstra-Algorithmus tatsächlich den kürzesten Weg?

Der Dijkstra-Algorithmus hält eine Menge vorläufiger Distanzen vom Startpunkt, initialisiert auf unendlich außer dem Startpunkt selbst (null), und zieht wiederholt den unbesuchten Knoten mit der kleinsten vorläufigen Distanz aus einer Prioritätswarteschlange. Er "relaxiert" jede Kante dieses Knotens — wenn der Weg über ihn einen kürzeren Weg zu einem Nachbarn ergibt, wird die Distanz des Nachbarn aktualisiert. Sobald jeder erreichbare Knoten besucht wurde, sind die vorläufigen Distanzen optimal, und der kürzeste Weg zu jedem Ziel kann durch Rückverfolgen der Vorgängerzeiger abgelesen werden.

Was ist OSPF und wie nutzt es Dijkstra?

OSPF (Open Shortest Path First) ist ein Link-State-Interior-Gateway-Protokoll, das innerhalb eines einzelnen administrativen Netzwerks verwendet wird. Jeder Router flutet Link-State-Advertisements, die seine direkt verbundenen Links und deren Kosten beschreiben; sobald sich alle Router auf dieselbe Link-State-Datenbank einigen, führt jeder unabhängig den Dijkstra-Algorithmus, verwurzelt bei sich selbst, aus, um den kürzesten Weg zu jedem anderen Router zu berechnen. Da jeder Router denselben Eingabegraphen und denselben deterministischen Algorithmus verwendet, konvergieren alle auf konsistente, schleifenfreie Routen.

Wie unterscheidet sich BGP grundlegend von OSPF?

BGP (Border Gateway Protocol) ist ein Pfadvektor-Protokoll, das zwischen autonomen Systemen läuft — separate Netzwerke unter unterschiedlicher administrativer Kontrolle, wie zum Beispiel verschiedene ISPs. Ein BGP-Router berechnet keine kürzesten Wege über eine gemeinsame Topologie; er lernt nur die spezifischen Pfade, die seine Nachbarn ankündigen, und wählt einen davon mittels eines Richtlinien-Entscheidungsprozesses (lokale Präferenz, AS-Pfadlänge, Herkunft und andere Attribute) statt reiner Kostenminimierung. Dies erlaubt einem ISP, eine kommerziell günstigere, aber längere Route einer billigeren vorzuziehen, was ein reiner Kürzeste-Wege-Algorithmus nicht ausdrücken kann.

Warum dauert die Routing-Konvergenz nach einem Ausfall eine gewisse Zeit?

Wenn eine Verbindung oder ein Router ausfällt, müssen die benachbarten Router den Ausfall erkennen, neue Link-State-Advertisements generieren (oder BGP-Routen zurückziehen), diese Information im Netzwerk fluten, und jeder Router muss seinen Kürzeste-Wege-Baum neu berechnen, bevor der Verkehr die neuen Routen sicher nutzen kann. Dieser Erkennen-Fluten-Neuberechnen-Zyklus ist nicht sofort — die OSPF-Konvergenz liegt typischerweise unter einer Sekunde bis wenige Sekunden, während die BGP-Konvergenz über das globale Internet Zehnersekunden bis Minuten dauern kann, weil sich Updates Hop für Hop zwischen autonomen Systemen ausbreiten. Diese Lücke zu minimieren ist ein echtes, laufendes Forschungsgebiet der Netzwerktechnik.

Was passiert mit Paketen, die unterwegs sind, wenn eine Verbindung ausfällt?

Pakete, die bereits einer ausgefallenen Verbindung zugewiesen wurden, werden einfach verworfen — Routing-Protokolle haben keine Möglichkeit, ein Paket mitten im Flug zurückzurufen. Neue Pakete, die während des Konvergenzfensters ins Netzwerk eintreten, können weiterhin entlang veralteter Routen weitergeleitet werden, bis sich der aktualisierte Kürzeste-Wege-Baum ausbreitet, was vorübergehende Schleifen oder schwarze Löcher verursachen kann. Erst wenn die Routing-Tabelle jedes Routers die neue Topologie widerspiegelt, folgt der Verkehr zuverlässig der neu berechneten Route.