View
106
Download
0
Category
Preview:
Citation preview
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und Komplexität
Algorithmen desInternets
Sommersemester 200511.04.2005
1. Vorlesung
Christian Schindelhauerschindel@upb.de
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
2
Überblick
•Organisation
– Termine
– Unterlagen
– Prüfung
– Übung, Literatur und Sprechstunde
•Das Internet: Einführung und Überblick
– TCP/IP, Das Web
•Mathematische Grundlagen
•IP: Routing im Internet
•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
Jetzt
Heute
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Termine
•Vorlesung
– jeden Montag 16-18 Uhr (c.t.), Raum F0.530
•Übung
– Gruppe A: Mo 15-16, FU.116 (Stefan Rührup)
– Gruppe B: Mo 18-19, F0.530 (Christian Schindelhauer)
• Start: Mo, 18.04.1005
– Übungsblätter online verfügbar ab dem Dienstag vor der Übung
•Anmeldung
– zur Übung
• im Verlauf dieser Woche über StudInfo
– zum Vorrechnen
• spätestens am Freitag vor der Übung (online über StudInfo)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Unterlagen
•Webseite der Veranstaltung– http://wwwcs.uni-paderborn.de/cs/ag-madh/WWW/Teaching/2005SS/internetALG/
– enthält alle vorlesungs- und übungsrelevanten Themen,
•Vorlesungsfolien
– online zur Veranstaltung als Powerpoint und PDF-Dokument
•Skript
– erscheint innerhalb einer Woche als PDF-Dokument
– ist Grundlage der Prüfung
•Übungsaufgaben
– erscheinen online am Dienstag auf der Web-Seite
– sind Grundlage der Prüfung
•Lösungen für die Übungsaufgaben
– gibt es nicht (von uns)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
5
Prüfung(en)
•Es gibt zwei Prüfungen:
– schriftliche Prüfung am 30.05.2005
• Vier Aufgaben über den ersten Teil in 60 Minuten
• Bei aktiver Beteiligung an der Übung (≥1 Aufgabe(n) gelöst)
Bewertung der besten drei der vier Aufgaben
– mündliche Prüfung am 25.06.2005 oder 29.08.2005
• Dauer 25 Minuten (für DPO 4 und Master-Studiengang Informatik)
• Bei Bestehen der ersten Prüfung:
Prüfung über den zweiten Teil der Vorlesung
• Sonst (oder falls gewünscht):
Prüfung über die gesamte Vorlesung
• Fall keine aktive Beteiligung an der Übung (≥2 Aufgaben gelöst)
Lösen einer Aufgabe eine Stunde vor der Prüfung
•“Aktive Beteiligung”
– Aufgabe vorrechnen (Reservierung online möglich)
– Schriftliche Abgabe und Testat
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
Übung, Literatur und Sprechstunde
•Übung
– Zweck
• Beantwortung von Fragen zur Vorlesung
• Präsentation (und Testierung) studentischer Lösungen
– Aufgabenstellungen
• hauptsächlich aus dem Gebiet der Algorithmen und Mathematik
– Einteilung (über StudInfo{flex})
• Gruppe A: Stefan Rührup, Mo 15-16 Uhr, FU.116
• Gruppe B: Christian Schindelhauer, Mo 18-19 Uhr, F0.530
•Literatur
– W. Richard Stevens, TCP/IP Illustrated
• Volume I, Addison-Wesley, 1996 (ergänzend)
– Weitere Literatur wird bekannt gegeben
•Sprechstunde
– nach Vereinbarung (schindel@upb.de, Tel.: 05251-60-6692)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
7
Überblick
•Organisation
– Termine
– Unterlagen
– Prüfung
– Übung, Literatur und Sprechstunde
•Das Internet: Einführung und Überblick
– TCP/IP, Das Web
•Mathematische Grundlagen
•IP: Routing im Internet
•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
Jetzt
Heute
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
8
Das Internet
•ist das weltweite, offene WAN (wide area network)
•ist systemunabhängig
•verbindet LANs (local area networks)
•hat keine zentrale Kontrolle
•ist nicht das World Wide Web (WWW)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
9
Die Geschichte des Internets
•1961: Packet Switching Theory
– Leonard Kleinrock, MIT, “Information Flow in Communication Nets”
•1962: Konzept des “Galactic Network”
– J.C.R. Licklider and W. Clark, MIT, “On-Line Man Computer Communication”
•1965: Erster Vorläufer des Internet
– Analoge Modem-Verbindung zwischen zwei Rechnern in den USA
– Zwischen MIT Lincoln Lab (Calif., USA) und ARPA (Mass., USA)
•1967: Konzept des “ARPANET”
– Entwurfspapier von Larry Roberts
•1969: Erster Knoten im “ARPANET”
– an der UCLA (Los Angelos)
– Ende 1969: vier Rechner verbunde
Originaldiagramme des “Ur-Internets”
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
10
Netzwerke offen für alle Architekturen
•Konzepte von Robert Kahn (DARPA 1972)
– Jedes (lokale) Netzwerk ist autonom
• arbeitet für sich
• muss nicht gesondert konfiguriert werden für das WAN
– Kommunikation nach “best effort”
• schafft es ein Paket nicht zum Ziel, wird es gelöscht
• es wird von der Anwendung wohl wieder verschickt weden
– Black Box Ansatz für Verbindungen
• Black Boxes später umgetauft in Gateways und Routers
• Paketinformation werden nicht aufbewahrt
• keine Flußkontrolle
– Keine globale Kontrolle
•Das sind die Grundprinzipen des Internet
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
11
TCP: Flusskontrolle
•Aus der Kooperation zwischen Vint Cerf und Robert Kahn (1973)
– ergaben sich folgende grundlegende Ansätze
•Kommunikation zwischen Prozessen auf Rechnern sind Byte-Ströme
•Flusskontrolle durch
– gleitende Fenster (sliding windows)
– Bestätigungen (acknowledgments)
•Parameter der Flusskontrolle werden zwischen Quelle und Ziel ausgehandelt
– Anfangs war dies unspezifiert
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
12
Die Schichtung des InternetsTCP/IP-Layer
Anwendung Application Telnet, FTP, HTTP, SMTP (E-Mail), ...
Transport TransportTCP (Transmission Control Protocol)
UDP (User Datagram Protocol)
Netzwerk Network
IP (Internet Protocol)+ ICMP (Internet Control Message Protocol)+ IGMP (Internet Group Management Protoccol)
Verbindung Link LAN (z.B. Ethernet, Token Ring etc.)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
13
Beispiel der Schichtung
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
14
Anwendungsschicht(application layer)
•Anwendungen (z.B WWW, E-Mail, Telnet, FTP) erzeugen Kommunikationsverbindungen zwischen zwei Rechnern im Netzwerk
•Anforderungen an Kommunikation:
– Verbindungen sind bidirektional (oftmals Client-Server)
– Datenmenge kann variieren
– Die gegenläufigen Datenströme sind meist abhängig
– Fehlerfreie Übermittlung der Datenströme wird vorausgesetzt
– Kein Abbruch bei Verbindungspausen
•Kommunikation wird auf Transportschicht delegiert
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
15
•TCP (transmission control protocol)
– Erzeugt zuverlässigen Datenfluß zwischen zwei Rechnern
– Unterteilt Datenströme aus Anwendungsschicht in Pakete
– Gegenseite schickt Empfangsbestätigungen (Acknowledgments)
•UDP (user datagram protocol)
– Einfacher unzuverlässiger Dienst zum Versand von einzelnen Päckchen
– Wandelt Eingabe in ein Datagramm um
– Anwendungsschicht bestimmt Paketgröße
•Versand durch Netzwerkschicht
•Kein Routing: End-to-End-Protokolle
Transportschicht(transport layer)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
16
TCP (I)
•TCP ist ein verbindungsorientierter, zuverlässiger Dienst für bidirektionale Byteströme
•TCP ist verbindungsorientiert
– Zwei Parteien identifiziert durch Socket: IP-Adresse und Port(TCP-Verbindung eindeutig identifiziert durch Socketpaar)
– Kein Broadcast oder Multicast
– Verbindungsaufbau und Ende notwendig
– Solange Verbindung nicht (ordentlich) beendet, ist Verbindung noch aktiv
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
17
TCP (II)
•TCP ist ein verbindungsorientierter, zuverlässiger Dienst für bidirektionale Byteströme
•TCP ist zuverlässig
– Jedes Datenpaket wird bestätigt (acknowledgment)
– Erneutes Senden von unbestätigten Datenpakete
– Checksum für TCP-Header und Daten
– TCP nummeriert Pakete und sortiert beim Empfänger
– Löscht duplizierte Pakete
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
18
TCP (III)
•TCP ist ein verbindungsorientierter, zuverlässiger Dienst für bidirektionale Byteströme
•TCP ist ein Dienst für bidirektionale Byteströme
– Daten sind zwei gegenläufige Folgen aus einzelnen Bytes (=8 Bits)
– Inhalt wird nicht interpretiert
– Zeitverhalten der Datenfolgen kann verändert werden
– Versucht zeitnahe Auslieferung jedes einzelnen Datenbytes
– Versucht Übertragungsmedium effizient zu nutzen
• = wenig Pakete
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
19
•IP (Internet Protocol) + Hilfsprotokolle
– ICMP (Internet Control Management Protocol)
– IGMP (Internet Group Management Protocol)
– Ermöglicht Verbund von (lokalen) Netzwerken
– IP ist ein unzuverlässiger verbindungsloser Datagrammauslieferungsdienst
•Datagramm besteht aus Anwendungsdaten und Header:
• Absender, Zieladresse
• TOS-Feld (type of service)
• TTL-Feld (time to live)
• ... (z.B. Paketlänge, Checksum für Header)
Netzwerkschicht (I)(network layer)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
20
IPv4-Header (RFC 791)
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| IHL |Type of Service| Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identification |Flags| Fragment Offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time to Live | Protocol | Header Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Options | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
•Version: 4 = IPv4
– IHL: Headerlänge in 32 Bit-Wörter (>5)
– Type of Service
–
•Checksum (nur für IP-Header)
– Time to Live:
• maximale Anzahl Hops
•Protocol, identifiziert passendes Protokoll
– Z.B. TCP, UDP, ICMP, IGMP
•Source and destination IP-address
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
21
Netzwerkschicht (II)(network layer)
•IP ist ein Datagrammauslieferungsdienst
– Soweit möglich direkte Übergabe von Sender zu Empfänger
– Sonst: Hop-Routing über Router
•IP ist unzuverlässig
– Fehlerbehandlung:
• Falls Problem beim Routing:
Lösche Datagramm
Schicke Fehlermeldung durch ICMP an Absender
• Falls Problem beim Routing von ICMP-Fehlermeldung
Lösche Fehlermeldungspaket
– Keine Redundanz vorgesehen
– TTL-Feld begrenzt Anzahl der Hops eines Datagramms
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
22
IP-Adressen und Domain Name System (DNS)
•IP-Adressen
– Jedes Interface in einem Netzwerk hat weltweit eindeutige IP-Adresse
– 32 Bits unterteilt in Net-ID und Host-ID
– Net-ID vergeben durch Internet Network Information Center
– Host-ID durch lokale Netzwerkadministration
•Domain Name System (DNS)
– Ersetzt IP-Adressen wie z.B. 131.234.22.29 durch Namen wie z.B. stargate.uni-paderborn.de und umgekehrt
– Verteilte robuste Datenbank
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
23
Routing im Internet durch IP
•Routing-Prinzip für Datagramm im Router:
– Falls Ziel = eigene ID, dann Übergabe an Transportschicht
– Ansonsten falls Ziel-Netz = lokales Netz, dann verschicke Datagramm direkt an Zielrechner
– Ansonsten suche gemäß Ziel-IP-Adresse den nächsten Router aus lokaler Routingtabelle und sende Datagramm zum nächsten Router
•Unterhalt von Routingtabellen
– manuell (LAN)
– oder automatisch durch
• RIP (Routing Information Protocol),
• OSPF (Open Shortest Path First)
• ...
– siehe nächste Woche
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
24
Verbindungsschicht(link layer)
•Schnittstelle zu lokalem Netzwerk
– wie z.B. Ethernet, oder Token Ring
•Umwandlung von IP-Adressen in lokale Netzwerkadressen durch
– ARP (Address Resolution Protocol)
– RARP (Reverse Address Resolution Protocol)
•Evtl. Unterteilung der Datagramme in noch kleinere Pakete
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
25
Beispiel zum Zusammenspiel
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
26
Datenkapselung
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
27
Das World Wide Web
•Hypertext-Konzept
– Vorläufer: Xanada, Ted Nelson, Vannevar Bush
•Entstand 1989 als Projekt am CERN (Genf)
– Hypertext-System von Tim Berners-Lee
•Standards
– HTTP (Hypertext Transfer Protocol)
• Information Anfordern von Web-Server durch Web-Browser
– HTML (Hyptertext Markup Language)
• Dokumentbeschreibungssprache
– URL (Uniform Resource Locator)
• Eindeutige Adresse einer Ressource für Hyperlinks
•Spätere Standards
– Cascading Style Sheets (CSS)
– JavaScript,
– Hypertext Transfer Protocol Secure (HTTPS)
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
28
Überblick
•Organisation
– Termine
– Unterlagen
– Prüfung
– Übung, Literatur und Sprechstunde
•Das Internet: Einführung und Überblick
– TCP/IP, Das Web
•Mathematische Grundlagen
•IP: Routing im Internet
•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
Jetzt
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
29
Grundlagen
Aus diesen Teilbereichen werden allgemeine Grundlagen vorausgesetzt:
•Algebra
•Analysis
•Kombinatorik
•Wahrscheinlichkeitstheorie
•Algorithmen
•Graphtheorie
Typische Lücken (die in Prüfungen negativ auffielen) werden hier jetzt kurz aufgeführt.
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
30
•Gesetze des Logarithmus, z.B.
•Potenzgesetze
Algebra
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
31
•Geometrische Reihe
•Polynomielle Reihen
Summen
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
32
•Formale Logik
– Prädikatenlogik
– Quantoren
• z.B.
– DeMorgansche Regel
•Wahrscheinlichkeitstheorie
– Wahrscheinlichkeiten
– Erwartungswert
– Varianz
– Markov-Ungleichung
– Chebyshev-Ungleichung
Logik und Wahrscheinlichkeitstheorie
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
33
Wahrscheinlichkeitstheorie
•Diskrete Wahrscheinlichkeitsverteilungen
– Gleichverteilung für n Werte
– Binomialverteilung
– Poisson-Verteilung, für ein λ
• Grenzwert der Binomialverteilung
– Geometrische Verteilung
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
34
Asymptotik
•ae: Fast immer
– almost everywhere
•io: Unendlich häufig
– infinetly often
•O, o, Θ, Ω, ω-Notation
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
35
Nützliche (Un)-Gleichungen
•Exponentialfunktion
•Eulersche Zahl
•Stirlingsche Formel
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
36
Graphtheorie
•Definition:
– ungerichteter Graph
– gerichteter Graph
•Graphalgorithmen
– Tiefensuche
– Breitensuche
•Grapheigenschaften
– schwache/starke Zusammenhangskomponenten
– Eingrad, Ausgrad, Durchmesser
– Cliquen
•Spezielle Graphen
– Vollständiger Graph
– Bipartite Graphen
– Bäume
Algorithmen des Internets 2005-01
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und KomplexitätChristian Schindelhauer
37
Algorithmen
•Sortier-Algorithmen
– Bucket-Sort, Quick-Sort, Heap-Sort, Radix-Sort
•Hash-Tabellen
•Binäre Suche
•Suchbäume
– Skiplisten
– höhenbalancierte/gewichtsbalancierte Bäume
•Komplexitätsklassen P und NP
38
HEINZ NIXDORF INSTITUTUniversität Paderborn
Algorithmen und Komplexität
Vielen Dank!
Ende der 1. Vorlesung
Nächste Vorlesung: Mo. 18.04.2005Nächste Übung: Mo. 18.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: schindel@upb.dehttp://www.upb.de/cs/schindel.html
Recommended