HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Algorithmen des
Internets
Sommersemester 2005
25.04.2005
3. Vorlesung
Christian Schindelhauer
[email protected]
HEINZ NIXDORF INSTITUT
Überblick
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Das Internet: Einführung und Überblick
• Mathematische Grundlagen
• IP: Routing im Internet
Heute
– Forwarding, Dijkstra, Distance Vector, Link State Intra-AS: RIP, OSPF,
Inter-AS: BGP, Min-Cut Max-Flow-Theorem, Nash-Equilibrium, Preis der
Anarchie
– Alternativen zu IP
• Virtual Circuits, Wormhole, Hot-potato
Heute
• Flussalgorithmen, Ford-Fulkerson
• Oblivious Routing
• TCP: Das Transport-Protokoll des Internets
• Die Struktur des World Wide Web und des Internets
• Suche im Web
• Web-Caching im Internet
• Peer-to-peer-Netzwerke
• Angriffe auf das Internet
Algorithmen des Internets 2005-03
2
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Circuit Switching oder Packet Switching
• Circuit Switching
– Etablierung einer Verbindung zwischen lokalen Benutzern durch
Schaltstellen
• mit expliziter Zuordnung von realen Schaltkreisen
• oder expliziter Zuordnung von virtuellen Ressourcen, z.B. Slots
– Quality of Service einfach (außer bei)
• Leitungsaufbau
• Leitungsdauer
– Problem
• Statische Zuordnung
• Ineffiziente Ausnutzung des Kommunikationsmedium bei dynamischer Last
– Anwendung
• Telefon
• Telegraf
• Funkverbindung
Algorithmen des Internets 2005-03
3
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Circuit Switching oder Packet Switching
• Packet Switching
– Grundprinzip von IP
• Daten werden in Pakete aufgeteilt und mit Absender/Ziel-Information
unabhängig versandt
– Problem: Quality of Service
• Die Qualität der Verbindung hängt von einzelnen Paketen ab
• Entweder Zwischenspeichern oder Paketverlust
– Vorteil:
• Effiziente Ausnutzung des Mediums bei dynamischer Last
• Resümee
– Packet Switching hat Circuit Switching in praktisch allen Anwendungen
abgelöst
– Grund:
• Effiziente Ausnutzung des Mediums
Algorithmen des Internets 2005-03
4
HEINZ NIXDORF INSTITUT
Hot Potato Routing
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Ursprünglich: Folgender Algorithmus
– Falls Puffer voll ist und Paket kommt herein
• sende Paket zurück
– Sonst
• Leite ein Paket aus dem Puffer an nächsten Router
• Falls Paket zurückkommt
 Leite Paket an irgendeinen Nachbarn weiter
• Hot Potato Routing im Internet Protokoll
– ist eine Intra-AS/Inter-AS-Forwarding-Politik
– Ein Paket wird so schnell wie möglich ans fremde AS übergeben
• nächster möglicher Gateway
– Fremdem Netzwerk wird der Verkehr aufgebürdet
• Gegenteil: Cold-Potato-Routing
– Das AS hält das Paket so lange wie möglich
• kürzester Gesamtweg auch durch weitesten Gateway
• Kann auch Advertisement-Strategie bezeichnen
– um Verkehr frühestmöglich (Cold Potato)
– oder möglichst spät (Hot Potato) über ein Gateway anzuziehen
Algorithmen des Internets 2005-03
5
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Wegewahl
• Oblivious Routing (Unbeirrtes Routing)
– Deterministische Wegewahl
• Nachrichten zwischen zwei Knoten benutzen immer den gleichen Weg
• z.B. Internet Protokoll (bevorzugt kürzeste Wege)
– Randomisierte Wegewahl
• Eine feste Wahrscheinlichkeitsverteilung bestimmt den nächsten Knoten
• Verkehr kann im Netzwerk verteilt werden (Valiants Trick)
• Adaptive Wegewahl
– Blockierte oder versperrte Wege können umgangen werden
– Möglichkeit der Lastanpassung
– Wie passt man die Last an
• Welches ist die beste Strategie???
Algorithmen des Internets 2005-03
6
HEINZ NIXDORF INSTITUT
Adaptive Wegewahl durch Modellierung
als Flussproblem
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Gegeben
– ein ungerichteter Graph mit Kapazitäten auf den Kanten
• Einfach-Fluss-Modell (Single-Commodity: Ein Gebrauchsgut)
– Für Quellen und Senken ist der Fluss gegeben
• Mehrfach-Fluss-Modell (Multi-Commodity: Mehrere Artikel)
– Verschiedene Ströme mit unterschiedlichen Quellen und Senken
– Die Flüsse teilen sich die Kapazität
– Minimiere den maximalen Flusslast (Congestion)
• Routing im Internet wird durch ein
– dynamisches Mehrfach-Fluss-Problem beschrieben
• Die Beschreibung durch ein Fluss-Problem optimiert den Durchsatz
– und nicht etwa die maximale Sprungweite D (Dilation)
– Routing-Zeit ist mindestens D+C: Dilation + Congestion
Algorithmen des Internets 2005-03
7
HEINZ NIXDORF INSTITUT
Congestion-Minimierung im EinfachFlussproblems
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Gegeben:
– Gerichteter Graph G mit Kantenkapazitäten w(e)≥0
– Seien s und t verschiedene Knoten
– mit gegebenem Fluss
• Flüsse
– Ein Fluss weist jeder Kante eine Zahl f(e) zu mit f(e) ≥ 0
– Für alle Knoten x gilt
• wobei I(x):= eingehenden Kanten und O(x) := ausgehenden Kanten
– Der Fluss steht für die erwartete Anzahl von Paketen auf einer Kante
• Ziel
– Minimiere Congestion:
Algorithmen des Internets 2005-03
8
HEINZ NIXDORF INSTITUT
Das statische Einfach-Fluss-Problem
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Fakt
– Die Congestion-Minimierung im Einfach-Flussproblem ist äquivalent zum
Flussproblem (aus der letzten Vorlesun).
• Siehe auch Min-Flow-Max-Cut-Problem
• Beides kann gelöst werden durch
– lineare Optimierung
• Simplex-Algorithmus
 Für natürliche Eingaben effizient
 Im worst-case exponentielle Laufzeit
• Ellipsoid-Methode
 Polynomielle Laufzeit aber immer noch ineffizient
– Ford-Fulkerson-Algorithmus
Algorithmen des Internets 2005-03
9
HEINZ NIXDORF INSTITUT
Formulierung als Lineares
Optimierungsproblem
• Betrachte Variablen f
e
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
und Hilfsvariable h
– mit den Randbedingungen
Minimiere
– Minimiere: Variable h
Algorithmen des Internets 2005-03
10
HEINZ NIXDORF INSTITUT
Congestion-Minimierung als Lineares
Optimierungsproblem?
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Problemgröße:
– linear in der Anzahl der Kanten
– zu aufwändig für globale Netzwerke
• Problemstellung ist abhängig von der Eingabe
– insbesondere der Anzahl Kanten
• Lösungsmethoden
– können nicht verteilt berechnet werden
– Zentrale Steuerung möglich
• Problem: Netzwerkinformation sammeln, verteilen
• Empfindlich gegen Angriffe
• Lösungsalgorithmen
– Nachfolger des Simplex-Algorithmus mittlerweile effizienter
• aber immer noch im worst-case nicht polynomiell
– Ellipsoid-Methode liefert Ergebnis in Polynomialzeit
• jedoch in der Praxis immer noch zu langsam
Algorithmen des Internets 2005-03
11
HEINZ NIXDORF INSTITUT
Ford-Fulkerson-Methode
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Löst Maximales (Einfach-) Flussproblem
– äquivalent zum Minimum Congestion Problem
• Ford-Fulkerson-Methode(G,s,t)
– Setze Anfangsflüsse auf f(e) = 0 für alle Kanten e
– Solange es noch einen Pfad p mit Restkapazitäten r>0 gibt
•
Für alle Kanten (u,v) ∈ G des Pfads p: f(e) ← f(e) + r
•
Für alle Kanten (u,v) mit (v,u) ∈ G des Pfads p: f(e) ← f(e) - r
– Resultierender Flus ist optimal
• Ein Pfad p mit Restkapazität r für den Fluss f, Start s, Ziel t, Kapazität w(e) ist
– ein Pfad p von s nach t, so dass für alle Kanten (u,v) des Pfads p
– entweder (u,v) ∈ G und
– oder (v,u) ∈ G und
• Gibt es keinen Pfad mit positiver Restkapazität, ist der Fluss maximal
– folgt aus dem Max-Flow-Min-Cut-Theorem
Algorithmen des Internets 2005-03
12
HEINZ NIXDORF INSTITUT
Beispiel: Ford-Fulkerson-Methode
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Algorithmen des Internets 2005-03
13
HEINZ NIXDORF INSTITUT
Mehrfach-Fluss-Probleme
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Gegeben:
– Gerichteter Graph G mit n Knoten und Kantenkapazitäten w(e)≥0
– Bedarfsmatrix: d: V × V → ℝ+
• Flüsse
– Mehrere Flüsse Zahl für u∈V, e∈E: f(u,e) ≥ 0 und
– Der Bedarf wird gedeckt:
– Jeder Fluss ist für sich konsistent:
• Ziel
• wobei I(x):= eingehenden Kanten und O(x) := ausgehenden Kanten
– Minimiere Congestion:
Algorithmen des Internets 2005-03
14
HEINZ NIXDORF INSTITUT
Beispiel: Mehrfach-Fluss-Problem
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Hier:
– Kürzeste-WegeRouting
• Beobachtung:
– Mehrfach-FlussProbleme lassen
sich als lineare
Optimierungsprobleme
beschreiben
Algorithmen des Internets 2005-03
15
HEINZ NIXDORF INSTITUT
Oblivious Routing: Valiants Trick im
zwei-dimensionalen Torus
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Valiants Trick im zweidimensionalen Torus mit n Knoten
– für eine beliebige Permutation π von jedem Knoten u nach π(u)
• Für Routing:
– Sende Nachricht von A zufälligem Knoten R im Gitter
– Sende Nachricht von R nach Ziel B
• Erwartete Last
– ist im jeden Knoten
• Bestes Routing
– unter Berücksichtigung der Permutation p
– hat für bestimmte Permutationen mindestens die Last
• folgt aus Satz von Borodin/Hopcroft
• Damit ist das Oblivious Routing nur um einen konstanten Faktor
schlechter als ein adaptives Routing
– für Permutationen im Torus
Algorithmen des Internets 2005-03
16
HEINZ NIXDORF INSTITUT
Darstellung von Valiants Trick im Torus
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Algorithmen des Internets 2005-03
17
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Beweis der erwarteten Last
• Weg zu zufälligen Knoten:
– Gemäß Wahrscheinlichkeitsverteilung, so das die Wahrscheinlichkeit eine
Kante im Abstand d für einen gegebenen Knoten zu benutzen ist
– Der maximale Abstand im Torus ist
– Damit ist die erwartete Anzahl von Nachrichten über eine Kante
• Die Analyse für den Rückweg ist analog
• Für bestes Routing betrachte Partition V = A ⋃ B durch das
– mit
Kanten zwischen A und B
– Wähle Permutation mit für alle u∈A: π(u)∈B und u∈B: π(u)∈A
– Der Fluss über den Schnitt ist dann mindestens n
• verteilt auf
Kanten ⇒ Auf einer Kante ist mindestens Last:
Algorithmen des Internets 2005-03
18
HEINZ NIXDORF INSTITUT
On-line Algorithmen für CongestionMinimierung
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• On-line-Algorithmus:
– Ein Algorithmus ist k-kompetitiv,
• falls die Congestion höchstens k-mal schlechter ist als die optimale Lösung für jede
einzelne Instanz (Graph, Gewichte, Bedarf)
• Unterschied zu Valiants Trick:
– Worst case war
, best case war 1
– Valiants Routing Trick immer erwartungsgemäß
• ist daher nicht O(1)-kompetitiv
• J. Aspens, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts [1993]:
– Zentraler O(log n)-kompetitiver Algorithmus
– Algorithmus ist optimal bezüglich kompetitven Faktor
– Benötigt Netzwerklast als Zusatzinformation
• B. Awerbuch and Y. Azar [1994]
– Verteilter O(log n)-kompetitiver Algorithmus
– Zustand des Netzwerks muss dem Algorithmus bekannt sein
• Kommt man ohne Kenntnis der momentanen Netzwerklast aus?
Algorithmen des Internets 2005-03
19
HEINZ NIXDORF INSTITUT
Der Satz von Harald Räcke
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
• Theorem [Räcke 2002]
,
– In jedem ungerichteten Netzwerk gibt es ein Oblivious Routing,
das höchstens den Faktor O(log3 n) schlechter ist als das beste
Routing für beliebigen Bedarf.
• Konstruktion:
– Zerlege Netzwerkknoten in hierarchisch in Baumstruktur,
• so dass der Zusammenhalt der Knoten in Teilbäumen untereinander
größer ist als die Verbindung zu Bruderteilbäume
• Tiefe des Baumes ist logarithmisch beschränkt
• Problem: Diese Baumzerlegung war seiner Zeit nicht effizient
berechenbar
– Löse ein (statisches) Mehrfach-Flussproblem zwischen den
Teilbäume
– Optimaler Bedarf belastet hauptsächlich Kanten zwischen
Bruderteilbäumen
• welcher vom Mehrfach-Flussproblem modelliert wird
Algorithmen des Internets 2005-03
20
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Oblivious Routing in polynomieller Zeit
• Theorem [Azar, Cohen, Fiat, Kaplan, Räcke, 2003]
– In jedem Netzwerk kann ein mit O(log3 n)-kompetitives Oblivious Routing
in polynomieller Zeit berechnet werden.
• Fortschritt
– Jetzt kann man die Baumzerlegung in polynomieller Zeit berechnen
– Damit könnte (rein theoretisch) auch im Internet diese Technik verwendet
werden
• Nachteile
– Es ist bis heute kein Netzwerk bekannt, indem dieses Oblivious Routing
weniger Last produziert als das kürzeste Wege Routing.
– Berechnung zwar polynomiell, aber immer noch aufwändig
Algorithmen des Internets 2005-03
21
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Christian Schindelhauer
Lastoptimierung: IP versus Alternativen
• Circuit Switching:
– Internet ist zu dynamisch; Resourcen werden vergeudet
• Mehrfach-Fluss-Modellierung
– Nur für statische Flüsse
– Ford-Fulkerson ist zentraler Algorithmus für Einfachfluss
– Lineare Optimierung nicht als verteilte Lösung einsetzbar
• Oblivious Routing:
– bis jetzt nur für statische Netzwerke einsetzbar
– Berechnung zu aufwändig und nur zentral möglich
– höchstens 1,5-2,4 Faktor schlechter als Internet Routing
• Zustand Internet 2005
– Congestion (Netzwerklast)
• nicht auf dem Internet-Backbone (hier nur 25% Auslastung)
• sondern auf Anbindung der Benutzer (Analog-Modem, ISDN, DSL)
Algorithmen des Internets 2005-03
22
HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität
Vielen Dank!
Ende der 3. Vorlesung
Nächste Vorlesung:
Mo. 02.05.2005
Nächste Übung: Mo. 02.05.2005
Heinz Nixdorf Institut
& Institut für Informatik
Universität Paderborn
Fürstenallee 11
33102 Paderborn
Tel.: 0 52 51/60 66 92
Fax: 0 52 51/62 64 82
E-Mail: [email protected]
http://www.upb.de/cs/schindel.html
23

AlgInt-03-2005-17 - Universität Paderborn