Zum Hauptinhalt springen

14. Routing Table Calculation (Routing-Tabellen-Berechnung)

Dieses Kapitel beschreibt die Routing-Tabellen-Berechnung mit dem Dijkstra-SPF-Algorithmus.

14.1 Dijkstra-Algorithmus-Übersicht​

Ziel​

  • Kürzesten-Pfad-Baum (SPF Tree) aufbauen
  • Wurzel: Berechnender Router
  • Kantengewichte: Link-Kosten

Datenstrukturen​

  • Kandidatenliste: Zu verarbeitende Knoten
  • SPF-Baum: Verarbeitete Knoten
  • Routing-Tabelle: Finale Routen

14.2 Algorithmus-Schritte​

Phase 1: Initialisierung​

  • Wurzelknoten (selbst) zu SPF-Baum hinzufügen
  • Distanz = 0

Phase 2: SPF-Baum-Aufbau​

WHILE Kandidatenliste nicht leer:
    1. Knoten V mit minimaler Distanz wählen
    2. V zu SPF-Baum hinzufügen
    3. Für jeden Nachbar W von V:
       - Distanz berechnen
       - Kandidatenliste aktualisieren

Äquivalente Pfade (ECMP)​

  • Mehrere Pfade mit gleichen Kosten
  • Alle äquivalenten Pfade behalten

14.3 Routen-Berechnungsphasen​

Intra-Area-Routen​

  • Aus SPF-Baum generiert
  • Höchste Priorität

Inter-Area-Routen​

  • Aus Type-3-LSAs berechnet
  • Mittlere Priorität

Externe Routen (External)​

  • Aus Type-5-LSAs berechnet
  • Type 1: Kosten = intern + extern
  • Type 2: Kosten = nur extern (Standard)

14.4 Routen-Auswahlpriorität​

  1. Intra-Area-Routen
  2. Inter-Area-Routen
  3. Type-1-externe Routen
  4. Type-2-externe Routen

Berechnungs-Trigger​

Neuberechnung erforderlich bei​

  • LSDB-Änderung
  • Interface-Statusänderung
  • Adjacency-Statusänderung

Optimierungen​

  • Verzögerte Berechnung
  • Inkrementelles SPF (iSPF)

Technische Punkte​

Algorithmische Komplexität​

  • Standard-Implementierung: O(N²)
  • Optimierte Implementierung: O((E + N) log N)

Implementierungspunkte​

  • Effiziente Priority-Queue
  • Schnelle LSDB-Suche
  • Korrekte ECMP-Verarbeitung

Referenzen (References)