2. The Link-state Database: Organization and Calculations (Link-State-Datenbank: Organisation und Berechnungen)
Dieses Kapitel beschreibt die Organisationsstruktur der OSPF-Link-State-Datenbank und wie diese Datenbank zur Berechnung der Routing-Tabelle verwendet wird.
Kapitelübersicht (Chapter Overview)
Dieses Kapitel behandelt folgende Hauptthemen:
- Darstellungsmethoden für Router und Netzwerke
- Konstruktion des Shortest-Path-Trees
- Verwendung externer Routing-Informationen
- Implementierung von Equal-Cost-Multipath
2.1 Representation of Routers and Networks (Darstellung von Routern und Netzwerken)
Kernkonzepte (Core Concepts)
Graphentheoretische Darstellung (Graph Representation)
- Das autonome System wird als gerichteter Graph modelliert (AS modeled as directed graph)
- Knoten (Vertices): Router und Netzwerke
- Kanten (Edges): Router-Interfaces
- Kosten (Cost): Gewicht jeder Kante
Router-Darstellung (Router Representation)
- Router-ID: 32-Bit eindeutige Kennung
- Interface-Liste: mit Netzwerken verbundene Interfaces
- Nachbarschaftsbeziehungen: Verbindungen zu benachbarten Routern
- Link-Status: Statusinformationen für jedes Interface
Netzwerktypen (Network Types)
| Netzwerktyp | Englisch | Merkmale | Beispiele |
|---|---|---|---|
| Punkt-zu-Punkt | Point-to-Point | Verbindet zwei Router | T1-Leitung, PPP |
| Broadcast | Broadcast | Multi-Access, Broadcast-Unterstützung | Ethernet, Token Ring |
| NBMA | Non-Broadcast Multi-Access | Multi-Access, kein Broadcast | Frame Relay, X.25 |
| Punkt-zu-Multipunkt | Point-to-MultiPoint | Als Sammlung von Punkt-zu-Punkt-Links behandelt | Partiell vermaschtes Frame Relay |
2.1.1 Representation of Non-broadcast Networks (Darstellung von Non-Broadcast-Netzwerken)
NBMA-Netzwerk-Eigenschaften (NBMA Network Characteristics)
- Keine Unterstützung für Link-Layer-Broadcast oder Multicast
- Manuelle Neighbor-Konfiguration erforderlich
- Wahl eines Designated Routers (DR) und Backup Designated Routers (BDR) erforderlich
- Vollvermaschte Konnektivität oder Punkt-zu-Multipunkt-Modus erforderlich
Konfigurationsanforderungen (Configuration Requirements)
- Neighbor-Listen-Konfiguration
- DR-Prioritätseinstellung
- Hello- und Dead-Intervalle
- Polling-Intervall (Poll Interval)
2.1.2 An Example Link-state Database (Beispiel einer Link-State-Datenbank)
Dieser Abschnitt zeigt anhand eines konkreten Beispiels die Struktur und den Inhalt der Link-State-Datenbank.
Beispiel-Netzwerktopologie (Example Network Topology)
- Mehrere miteinander verbundene Router
- Verschiedene Netzwerktypen
- Area-Aufteilung
- Virtuelle Links
LSA-Typen (LSA Types)
| LSA-Typ | Name | Beschreibung | Flooding-Bereich |
|---|---|---|---|
| Type 1 | Router-LSA | Router-Link-Status | Innerhalb der Area |
| Type 2 | Network-LSA | Netzwerk-Link-Status | Innerhalb der Area |
| Type 3 | Summary-LSA (Netzwerk) | Inter-Area-Netzwerkrouten | Einzelne Area |
| Type 4 | Summary-LSA (ASBR) | ASBR-Routen | Einzelne Area |
| Type 5 | AS-external-LSA | Externe Routen | Gesamtes AS |
2.2 The Shortest-path Tree (Shortest-Path-Tree)
Dijkstra-Algorithmus (Dijkstra's Algorithm)
Algorithmus-Schritte (Algorithm Steps)
- Initialisierung: Sich selbst als Wurzelknoten setzen
- Kandidatenliste: Liste der zu verarbeitenden Knoten pflegen
- Knoten mit minimalen Kosten auswählen
- Neighbor-Kosten aktualisieren
- Wiederholen bis alle Knoten verarbeitet sind
Kostenberechnung (Cost Calculation)
- Interface-Kosten: basierend auf Bandbreite oder manueller Konfiguration
- Pfadkosten: Summe aller Interface-Kosten entlang des Pfades
- Standard-Kostenformel:
Kosten = Referenzbandbreite / Interface-Bandbreite
Tree-Konstruktion (Tree Construction)
- Wurzelknoten: der Router, der die Berechnung durchführt
- Innere Knoten: Router und Netzwerke innerhalb des AS
- Blattknoten: externe Routen (AS-external-LSA)
Schlüsselbegriffe (Key Terms)
| Begriff | Englisch | Definition |
|---|---|---|
| SPF-Baum | SPF Tree | Shortest-Path-Tree mit Router als Wurzel |
| Kandidatenliste | Candidate List | Knoten, die dem Baum hinzugefügt werden sollen |
| Elternknoten | Parent | Vorgängerknoten im Baum |
| Entfernung | Distance | Kosten von der Wurzel zum Knoten |
| Next Hop | Next Hop | Erster Router zum Erreichen des Ziels |
2.3 Use of External Routing Information (Verwendung externer Routing-Informationen)
Externe Routentypen (External Route Types)
Type 1 externe Route (Type 1 External)
- Kosten = interne Kosten + externe Kosten
- Vergleichbare Metrik
- Anwendbar auf IGPs innerhalb desselben AS
Type 2 externe Route (Type 2 External)
- Kosten = externe Kosten (interne Kosten nur zum Tie-Breaking)
- Nicht vergleichbare Metrik
- Anwendbar auf EGPs verschiedener AS
- OSPF-Standardtyp
ASBR (Autonomous System Boundary Router)
ASBR-Rolle (ASBR Role)
- Führt externe Routen in OSPF ein
- Erzeugt AS-external-LSAs
- Kann jeder OSPF-Router sein
- Über Type 4 Summary-LSA angekündigt
Routen-Redistribution (Route Redistribution)
- Routen von anderen Protokollen importieren
- Externen Routentyp festlegen
- Route Tag konfigurieren (Route Tag)
- Weiterleitungsadresse festlegen (Forwarding Address)
2.4 Equal-cost Multipath (Equal-Cost-Multipath)
ECMP-Konzept (ECMP Concept)
Grundprinzipien (Basic Principles)
- Mehrere gleichwertige Pfade zum selben Ziel
- Pfadkosten vollständig identisch
- Traffic auf mehrere Pfade verteilt
- Verbesserte Bandbreitennutzung und Redundanz
Implementierungsmethoden (Implementation Methods)
| Methode | Beschreibung | Vorteile | Nachteile |
|---|---|---|---|
| Paketweises Round-Robin | Per-packet round-robin | Einfach | Kann Unordnung verursachen |
| Flow-basierte Verteilung | Per-flow distribution | Erhält Reihenfolge | Benötigt Flow-Identifikation |
| Hash-basiert | Hash-based | Effizient, deterministisch | Kann unausgeglichen sein |
Konfigurationsparameter (Configuration Parameters)
- Maximale Pfadanzahl: Maximale ECMP-Pfade, die das System unterstützt
- Load-Balancing-Algorithmus: Auswahl der Traffic-Verteilungsmethode
- Kostenschwelle: Zulässiger Kostenunterschiedsbereich
Routing-Tabelleneinträge (Routing Table Entries)
Multipath-Darstellung (Multipath Representation)
- Einzelnes Zielpräfix
- Multiple Next-Hop-Interfaces
- Identische Routenkosten
- Identischer Routentyp
Technische Zusammenfassung (Technical Summary)
Wichtige Datenstrukturen (Key Data Structures)
- Link-State-Datenbank (LSDB): Speichert alle LSAs
- SPF-Baum: Shortest-Path-Tree-Struktur
- Routing-Tabelle: Finale Weiterleitungstabelle
- Neighbor-Tabelle: Informationen über benachbarte Router
Wichtige Algorithmen (Important Algorithms)
- Dijkstra SPF: Berechnung des kürzesten Pfades
- LSA-Flooding: Verteilung von Link-State-Informationen
- Routenberechnung: Generierung der Routing-Tabelle aus SPF-Baum
- ECMP-Auswahl: Multipath-Load-Balancing
Performance-Überlegungen (Performance Considerations)
- SPF-Berechnungskomplexität: O(N log N)
- Datenbankgröße: Einfluss auf Speichernutzung
- Konvergenzzeit: Von Topologieänderung bis Routenaktualisierung
- Skalierbarkeit: Area-Aufteilung für große Netzwerke
Referenzen (References)
- Vollständiger Text: RFC 2328 Section 2
- Dijkstra-Algorithmus: E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs"
Hinweis (Note): Dieses Dokument basiert auf der offiziellen Spezifikation RFC 2328. Für vollständige technische Details, Algorithmus-Pseudocode und normative Sprache konsultieren Sie bitte das Originaldokument.