Routing
Routing ist im Wesentlichen ein graphentheoretisches Problem, das Finden des Weges mit den geringsten Kosten zwischen je zwei Knoten (Nodes). Netzwerke werden in der Regel als gerichtete bzw. ungerichtete gewichtete Graphen mit ausschließlich nichtnegativen Kantengewichten (Edges) angenommen, G = (N, E, w).
Für die Ermittlung des kürzesten Weges wird in der Regel eines der beiden Verfahren angewendet:
- (verteilter) Bellman-Ford-Algorithmus
- Dijkstra-Algorithmus (Klasse der Greedy-Algorithmen)
Vergleich der Verfahren:
| Merkmal | Distanzvektor | Linkstate |
|---|---|---|
| Netzwerkansicht | Lokal | Global |
| Algorithmus | verteilter Bellman-Ford | Dijkstra |
| Konvergenz | langsam | schnell |
| Informationsaustausch | Routing-Tabellen mit Nachbarn | Link-Zustände mit allen Knoten |
| Routing-Schleifen | anfällig | weniger anfällig |
| negative Kantengew. | möglich | nicht optimal |
| Ressourcenbedarf | niedrig | hoch (CPU+Speicher) |
| Datenmenge | niedriger | höher |
| Beispiel | RIP | OSPF, IS-IS |
| Anwendung | kleine Netze | komplexere Netze |
Aufgaben Routing
- Welche Metriken kommen für das Routing prinzipiell in Frage?
- Was sagt die Bellman-Ford-Gleichung aus und wie funktioniert Distanzvektor-Routing prinzipiell?
- Was besagt das Count-to-Infinity-Problem?
- Was bedeutet Split Horizon beim RIP-Protokoll?
- Wie funktioniert der Dijkstra-Algorithmus? Lösen Sie dazu die Aufgabe aus der Vermittlungsschicht.
- Was ist der Unterschied zwischen einem globalem Routing-Algorithmus und einem dezentralem Routing-Algorithmus?
- Was sind autonome Systeme und welchen Vorteil bieten diese für das Routing?
- Was bedeutet Supernetting?
- Wie funktioniert das Routing mittels BGP?
- Welche Informationen werden zwischen 2 BGP-Peers ausgetauscht?
- Was sagen die Begriffe Provider, Tier 1-3, Kunden, Peers, Uplinks aus?
- Lesen Sie den Abschnitt “Netze, Bälle, Datenströme – oder wie die Fußball-WM ins X-WiN kam” aus DFN-Mitteilungen 95. Diskutieren Sie die aus der beschriebenen Entwicklung des Peerings entstehenden Probleme. Im Dokument DFN-Mitteilungen 97 gibt es eine Grafik des Peerings des DFN.
- Ermitteln Sie die Verbindung zwischen Ihrem Internetprovider und dem Netz der HTW Dresden. Nutzen Sie dazu
traceroute -Azur Anzeige der benutzten autonomen Systeme. Den physischen Ort der IP können Sie über z.B. über Link ermitteln oder Sie nutzen Open Visual Traceroute. Versuchen Sie, einen Zusammenhang zum o.g. Peerings des DFNs herzustellen.
Distanzvektor-Routing (Bellman-Ford-Algorithmus)
Schritte:
- Initialisierung (Entfernung zu allen anderen Knoten unendlich)
- Informationsaustausch zwischen direkten Nachbarn
- Aktualisierung: \((D_{x}(y) = \min (D_{x}(y), c(x,v) + D_{v}(y) )\)
- Konvergenz (Wiederholung bis keine Änderung mehr eintritt)
Aufgabe: Berechnen Sie die Routingtabelle für Knoten a nach einer Initialisierung im abgebildeten Netzwerk, wenn dieser folgende Nachrichten erhält:
- von b: (c=3, d=2, e=3, f=5)
- von d: (b=2, c=3, e=1, f=3)
Linkstate-Routing (Dijkstra-Algorithmus)
- Bestimmen Sie mittels Dijkstra-Algorithmus den kürzesten Weg von B nach F im abgebildeten Netzwerk.
- Erzeugen Sie eine Routing-Tabelle für Knoten B mit Hilfe der ermittelten Wege.
BGP
- Bekanntmachung der Existenz eines Subnetzes dem Rest des Internets
- Austausch von kompletter Routing-Tabellen mit Pfad (Liste von AS-Nummern) zum Ziel
- Entscheidungsfindung anhand der Attribute: AS-Path-Länge, Lokale Präferenz, Next-Hop
- Policy-Steuerung
Fakultativ
- Lesen Sie den Artikel über Routing im Internet Link.
- Informieren Sie sich bei BGP Routing Infos über den Stand der Routing-Tabellen.
- Geschichte des Internets in Deutschland Internet.
- Bestimmen Sie mittels Dijkstra-Algorithmus den kürzesten Weg von B nach E im abgebildeten Netzwerk.
- Erzeugen Sie eine Routing-Tabelle für Knoten B mit Hilfe der ermittelten Wege.
Literatur
- Peterson and Davie: Computer Networks, Chapter Routing
- Software-Defined Networks
- Cerf and Kahn: A Protocol for Packet Network Intercommunication
- Brander and Mankin: The Recommendation for the IP Next Generation Protocol
- Paper SSSP
Letzte Änderung: 08. December 2025 11:18