Algorithmen des Internets Sommersemester 2005 18.04.2005 2. Vorlesung

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Algorithmen desInternets

Sommersemester 200518.04.2005

2. Vorlesung

Christian [email protected]

Algorithmen des Internets 2005-02


Algorithmen und KomplexitätChristian Schindelhauer

2

Heute

Überblick

•Das Internet: Einführung und Überblick

•Mathematische Grundlagen

•IP: Routing im Internet

– Packet Forwarding

– Dijkstra und Min-Cut Max-Flow-Theorem

– Distance Vector und Link State

– Intra-AS: RIP, OSPF, Hierarchisches OSPF, IGRP

– Inter-AS: BGP

– Der Preis der Anarchie: Nash-Equilibrium - Optimum

•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




3

Routing-Tabelle und Paket-Weiterleitung

•IP-Routing-Tabelle

– enthält für Ziel (Destination) die Adresse des nächsten Rechners (Gateway)

– Destination kann einen Rechner oder ganze Sub-nets beschreiben

– Zusätzlich wird ein Default-Gateway angegeben

•Packet Forwarding

– früher Packet Routing genannt

– IP-Paket (datagram) enthält Start-IP-Adresse und Ziel-IP-Adresse

• Ist Ziel-IP-Adresse = eigene Rechneradresse dann Nachricht ausgeliefert

• Ist Ziel-IP-Adresse in Routing-Tabelle dann leite Paket zum angegeben Gateway

• Ist Ziel-IP-Subnetz in Routing-Tabelle dann leite Paket zum angegeben Gateway

• Ansonsten leite zum Default-Gateway




4

Probleme in der Paket-Weiterleitung

•IP-Paket (datagram) enthält unter anderen

– TTL (Time-to-Live): Anzahl der Hops

– Start-IP-Adresse

– Ziel-IP-Adresse

•Behandlung eines Pakets

– Verringere TTL (Time to Live) um 1

– Falls TTL ≠ 0 dann Packet-Forwarding aufgrund der Routing-Tabelle

– Falls TTL = 0 oder bei Problemen in Packet-Forwarding:

• Lösche Paket

• Falls Paket ist kein ICMP-Paket dann

Sende ICMP-Paket mit

Start= aktuelle IP-Adresse und

Ziel = alte Start-IP-Adresse




5

ICMP, Ping und Traceroute

•ICMP (Internet Control Message Protocol)

– zumeist bei Packet Forwarding Problemen

– ermöglicht aber auch auch Analyse der Routing:

•Ping

– Spezielle ICMP-Nachricht: “ICMP Echo Request”

– Empfänger antwortet mit “ICMP Echo Reply”

•Traceroute

– Sendet Paket an Ziel-Rechner

• mit TTL 1,2,3,...

• mit ungültiger Port-Nummer (> 30.000)

– Sammelt ICMP-Pakete wieder ein

• ICMP mit TTL-Fehler ergibt Router-Adresse

• ICMP mit “Port unreachable” hat Ziel erreicht




6

Statisches und Dynamisches Routing

•Forwarding:

– Weiterleiten von Paketen

•Routing:

– Erstellen Routen, d.h.

• Erstellen der Routing-Tabelle

•Statisches Routing

– Tabelle wird manuell erstellt

– sinnvoll für kleine und stabile LANs

•Dynamisches Routing

– Tabellen werden durch Routing-Algorithmus erstellt

– Zentraler Algorithmus, z.B. Link State

• Einer/jeder kennt alle Information, muss diese erfahren

– Dezentraler Algorithmus, z.B. Distance Vector

• arbeitet lokal in jedem Router

• verbreitet lokale Information im Netzwerk




7

Das Kürzeste-Wege-Problem

•Gegeben:

– Ein gerichteter Graph G=(V,E)

– Startknoten

– mit Kantengewichtungen

•Definiere Gewicht des kürzesten Pfades

– δ(u,v) = minimales Gewicht w(p) eines Pfades p von u nach v

– w(p) = Summe aller Kantengewichte w(e) der Kanten e des Pfades

•Gesucht:

– Die kürzesten Wege vom Startknoten s zu allen Knoten in G

• also jeweils ein Pfad mit den geringsten Gewicht zu jedem anderen Knoten

•Lösungsmenge:

– wird beschrieben durch einen Baum mit Wurzel s

– Jeder Knoten zeigt in Richtung der Wurzel




8

Kürzeste Wege mit Edsger Wybe Dijkstra

•Theorem

– Dijkstras Kürzeste-Wege-Algorithmus kann mittels eines Fibonacci Heap mit Laufzeit Θ(|E| + |V| log |V|) implementiert werden.




9

Dijkstra: Beispiel




10

Bellman-Ford

•Bei negativen Kantengewichten versagt Dijkstras Algorithmus

•Bellman-Ford

– löst dies in Laufzeit O(|V| |E|).




11

Link-State Protocol

•Link State Router

– tauschen Information mittels Link State Packets (LSP) aus

– Jeder verwendet einen zentralen Kürzeste-Wege-Algorithmus

•LSP enthält

– ID des LSP erzeugenden Knotens

– Kosten diese Knotens zu jedem direkten Nachbar

– Sequenznr. (SEQNO)

– TTL-Feld für dieses Feld (time to live)

•Verlässliches Fluten (Reliable Flooding)

– Die aktuellen LSP jedes Knoten werden gespeichert

– Weiterleitung der LSP zu allen Nachbarn

• bis auf den Knoten der diese ausgeliefert hat

– Periodisches Erzeugen neuer LSPs

• mit steigender SEQNOs

– Verringern der TTL bei jedem Weiterleiten




12

Distance Vector Routing Protocol

•Distance Table Datenstruktur

– Jeder Knoten besitzt eine

– Spalte für jedes mögliches Ziel

– Spalte für jeden direkte Nachbarn

•Verteilter Algorithmus

– Jeder Knoten kommuniziert nur mit seinem Nachbarn

•Asynchroner Betrieb

– Knoten müssen nicht Informationen austauschen in einer Runde

•Selbstterminierend

– läuft bis die Knoten keine Information mehr austauschen




13

Das “Count to Infinity” - Problem

•Gute Nachrichten verbreiten sich schnell

– Neue Verbindung wird schnell veröffentlicht

•Schlechte Nachrichten verbreiten sich langsam

– Verbindung fällt aus

– Nachbarn erhöhen wechselseitig ihre Entfernung

– “Count to Infinity”-Problem




14

Die Grenzen des flachen Routing

•Link State Routing

– benötigt O(g n) Einträge für n Router mit maximale Grad g

– Jeder Knoten muss an jedem anderen seine Informationen senden

•Distance Vector

– benötigt O(g n) Einträge

– kann Schleifen einrichten

– Konvergenzzeit steigt mit Netzwerkgröße

•Im Internet gibt es mehr als 106 Router

– damit sind diese so genannten flachen Verfahren nicht einsetzbar

•Lösung:

– Hierarchisches Routing




15

AS, Intra-AS und Inter-AS

•Autonomous Systems (AS)

– liefert ein zwei Schichten-modell des Routing im Internet

– Beispiele for AS:

• uni-paderborn.de

•Intra-AS-Routing

– ist Routing innerhalb der AS

– z.B. RIP, OSPF, IGRP, ...

•Inter-AS-Routing

– Übergabepunkte sind Gateways

– ist vollkommen dezentrales Routing

– Jeder kann seine Optimierungskriterien vorgeben

– z.B. EGP (früher), BGP




16

Intra-AS: RIP (Routing Information Protocol)

•Distance Vector Algorithmus

– Distanzmetrik = Hop-Anzahl

•Distanzvektoren

– werden alle 30s durch Response-Nachricht (advertisement) ausgetauscht

•Für jedes Advertisement

– Für bis zu 25 Zielnetze werden Routen veröffentlicht per UDP

•Falls kein Advertisement nach 180s empfangen wurde

– Routen über Nachbarn werden für ungültig erklärt

– Neue Advertisments werden zu den Nachbarn geschickt

– Diese antworten mit auch mit neuen Advertisements

• falls die Tabellen sich ändern

– Rückverbindungen werden unterdrückt um Ping-pong-Schleifen zu verhindern (poison reverse) gegen Count to Infinity-Problem

• Unendliche Distanz = 16 Hops




17

Intra-ASOSPF (Open Shortest Path First)

•“open” = öffentlich verfügbar

•Link-State-Algorithmus

– LS Paket-Verbreitung

– Topologie wird in jedem Knoten abgebildet

– Routenberechnung mit Dijkstras Algorithmus

•OSPF-Advertisment

– per TCP, erhöht Sicherheit (security)

– werden in die gesamte AS geflutet

– Mehre Wege gleicher Kosten möglich




18

Intra-AS: Hierarchisches OSPF

•Für große Netzwerke zwei Ebenen:

– Lokales Gebiet und Rückrad (backbone)

• Lokal: Link-state advertisement

• Jeder Knoten berechnet nur Richtung zu den Netzen in anderen lokalen Gebieten

•Local Area Border Router:

– Fassen die Distanzen in das eigene lokale Gebiet zusammen

– Bieten diese den anderen Area Border Routern an (per Advertisement)

•Backbone Routers

– verwenden OSPF beschränkt auf das Rückrad (backbone)

•Boundary Routers:

– verbinden zu anderen AS




19

Intra-AS: IGRP (Interior Gateway Routing Protocol)

•CISCO-Protokoll, Nachfolger von RIP (1980er)

•Distance-Vector-Protokoll, wie RIP

– Hold time

– Split Horizon

– Poison Reverse

•Verschiedene Kostenmetriken

– Delay, Bandwidth, Reliability, Load etc.

•Verwendet TCP für den Austausch von Routing Updates




20

Inter-AS: BGP (Border Gateway Protocol)

•Ist faktisch der Standard

•Path-Vector-Protocol

– ähnlich wie Distance Vector Protocol

– jeder Border Gateway teilt all seinen Nachbarn (peers) den gesamten Pfad (Folge von ASen) zum Ziel mit (advertisement)

– per TCP

•Falls Gateway X den Pfad zum Peer-Gateway W sendet

– dann kann W den Pfad wählen oder auch nicht

– Optimierungskriterien:

• Kosten, Politik, etc.

– Falls W den Pfad von X wählt, dann publiziert er

• Path(W,Z) = (W, Path (X,Z))

•Anmerkung

– X kann den eingehenden Verkehr kontrollieren durch senden von Advertisements.




21

Optimales Routing: Max-Flow

•Gegeben:

– Gerichteter Graph G mit Kantenkapazitäten w(e)≥0

– Seien s und t verschiedene Knoten

– G ist ein Netzwerk aus Röhren

•Flüsse

– Ein Fluß weist jeder Kante eine Zahl f(e) zu mit 0 ≤ f(e) ≤ w(e)

– Für alle Knoten x gilt

• wobei I(x):= eingehenden Kanten und O(x) := ausgehenden Kanten

– “Was reingeht muss auch rausgehen”

•Ziel:

– So viel wie möglich von s nach t pumpen

– der maximale Fluss von s nach t,

• d.h. maximiere




22

Max-Flow-Min-Cut Theorem

•Ein Schnitt C in G zwischen s und t

– ist eine Menge Kanten, so dass jeder gerichtete Pfad von s nach t wenigstens eine der Kanten in C beinhalten muss

– Die Kapazität des Schnitts C ist die Summe aller Kantenkapazitäten

•Max-Flow-Min-Cut Theorem [Feinstein, Shannon; Ford, Fulkerson, Shannon 1956]

– Der maximale Fluss ist gleich der Kapazität des minimalen Schnitts.

•Berechnung des maximalen Flusses

– durch Lösen des Linearen Programms

• Simplex-Methode/Ellipsoid-Methode

– Ford-Fulkerson-Methode für ganze Zahlen

• implementiert durch den Edmonds-Karp-Algorithmus




23

Routing als Spiel

•Das BGP-Spiel [Papadimitriou, “Algorithms, Games and the Internet”, STOC 2001]

– Gegeben:

• Ungerichteter Graph mit n Knoten

• Symmetrische n × n Verkehrsmatrix F

• Sei ci die Kapazität eines Knoten i

– Dies ergibt ein Multi-Commodity-Flow-Problem im Graphen, d.h.

• es gibt verschiedene Flüsse, die nicht austauschbar sind

• deren Summe aber den Kapazitäten entsprechen müssen

•Bestimmte Knoten spielen in Koalitionen

– Jeder Knoten kann Verbindungen zu Nachbarn veröffentlichen (oder nicht)

•Ziel (jedes Knoten):

– Optimiere den eigenen Verkehrsdurchsatz

• das sind Pakete von Knoten der eigenen Koalition

• evtl. durch die Minimierung des fremden Verkehrs




24

Nash-Equilibrium

•Gegeben ein Spiel

– mit n Spielern und n Strategien für jeden Spieler

– xi sei die Strategie für Spieler i aus einer Menge Si

– ui(x1, x2, ..., xn) sei der Gewinn von Spieler i

• eine Funktion aus den Einzelstrategien

•Ein Nash-Equilibrium ist ein Kombination von Strategien x1, ..., xn

– so dass für alle Spiele i und für alle Strategien x’i ≠ xi gilt

• ui(x1, x2, ..., xi, ... , xn) ≥ ui(x1, x2, ..., x’i, ... , xn)

•Theorem (John Nash, 1950)

– Es gibt immer ein solches Nash-Equilibrium, wenn die Mengen Si konvex sind.

•Eine Menge S ist konvex,

– falls für alle x,y S für alle i [0,1] gilt: i x+ (1-i) y S∈ ∈ ∈

– Daraus folgt:

• Randomisierte Strategien sind konvex.




25

Beispiel: Das Nash-Equilibrium von Papier, Schere, Stein

•Zwei Spieler

– Strategien:

• Si={Papier, Schere, Stein}

– Gewinnfunktion gemäß Matrix

•Das diskrete Spiel hat kein reines Nash-Equilibrium

– d.h.wenn jeder einmalig eine Entscheidung, dann gibt es für jedenimmer eine bessere Lösung

•Es gibt ein gemischtes Nash-Equilibrium

– Wähle gleich wahrscheinlich eine der drei Möglichkeiten

0 -1 1

1 0 -1

-1 1 0




26

Der Preis der Anarchie

•Ein Spiel über mehrere Runden konvergiert gegen das Nash-Equilibrium

– falls alle Akteure egoistisch handeln,

– falls das Spiel in den selben Rahmenbedingungen bleibt,

• d.h. Bewertung bleibt gleich

– und falls das Spiel überhaupt konvergiert

•Das Nash-Equilibrium muss aber nicht global die beste Lösung darstellen,

– da nur jeder einzelne seine Kosten optimiert hat

– Es kann sogar sein, dass jeder einzelne besser da stehen kann,

• wenn sie nicht im Nash-Equilibrium sind

• Beispiel: Gefangenen-Dilemma

•Der Preis der Anarchie:

– Die Differenz zwischen der besten Lösung und dem Nash-Equilibrium




27

Der Preis der Anarchie im Gefangenendilemma

•Zwei Verdächtige werden unabhängig verhört

– Sie können jeweils gestehen oder leugnen

•Falls beide leugnen:

– jeweils 1 Jahre Haft

•Falls beide gestehen:

– jeweils 2 Jahre Haft

•Falls einer gesteht und der andere leugnet:

– Für den Zeugen: Freispruch

– Für den Anderen: 3 Jahre Haft

•Analyse:

– Nash-Equilibrium: Beide Gestehen - Jeder 2 Jahre

– Optimal: Beide Leugnen - Jeder 1 Jahr

•Preis der Anarchie:

– 1 Jahr für jeden!!!

Wir waren es!

Ich weiß von nichts!




28

Beispiel: Das Paradoxon von Braess

•Gegen ein Fluss-Netzwerk mit

– konstanten Kosten (1/2)

– flussabhängigen Kosten (x)

•Gesucht ein Fluss von S nach T

– und das Nash-Equilibrium zwischen den Flüssen aller möglicher Teilpfade

•Braess Paradoxon:

– Durch Einfügen einer Kante kann sich der erreichbare Fluss im Nash-Equilibrium verkleinern

– Dadurch steigt der Preis der Anarchie




29

Zusammenfassung

•Paketweiterleitung im Internet folgt einem einfachen Schema

– Die Routing-Tabelle bestimmt den Weg

•Die Wegewahl heißt Routing

– Es gibt zwei Arten des Routing

•Intra-AS

– RIP, OSPF, Hier. OSPF, etc. sind innerhalb einer AS

– berechnen kürzeste Wege durch Weitergabe von Advertisement

• mit Dijkstra

• oder durch die Verbreitung der Information - Distance Vector

•Inter-AS

– BGP-Standard läßt Freiraum für ein Spiel zwischen den ASen:

• Advertisements können verändert werden

•Das Nash-Equilibrium

– beschreibt eine Lösung, falls alle egoistisch handeln

– ist nicht unbeding optimal: Die Differenz ist der Preis der Anarchie

30


Algorithmen und Komplexität

Vielen Dank!

Ende der 2. Vorlesung

Nächste Vorlesung: Mo. 25.04.2005Nächste Übung: Mo. 25.04.2005

Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn

Tel.: 0 52 51/60 66 92Fax: 0 52 51/62 64 82E-Mail: [email protected]://www.upb.de/cs/schindel.html

Documents

Algorithmen des Internets Sommersemester 2005 18.04.2005 2. Vorlesung