Zusammenfassung Vernetzte Systeme

Aus VISki
Wechseln zu: Navigation, Suche

Ziel dieser Zusammenfassung: All denjenigen welche die Vorlesung besucht (oder Slides studiert) haben, helfen, sich an alle Details und Zusammenhänge zu erinnern

  • Die behandelten Konzepte kurz und präzise erläutern und übersichtlich darstellen
  • Die wichtigsten Eigenschaften von Konzepten / Protokollen auflisten
  • Die Begriffe (Buzz-Words) wichtiger Konzepte / Protokolle auflisten und kurz beschreiben, damit man sich an die Begriffe erinnern kann
  • Überblick vermitteln (Wo gehört was hin? Wie hängt was zusammen? Worin unterscheiden sich die Konzepte?)


Nicht Ziel dieser Zusammenfassung: Jemandem der keine Ahnung vom Stoff der Vorlesung hat diesen verständlich machen

  • Die Konzepte, Protokolle ins Detail erklären (Dies ist Aufgabe der Vorlesung/Slides)
  • Viele Beispiele auflisten
  • Prüfungsfragen als Beispiele (Besser das getestete Wissen in die Zusammenfassung integrieren)
  • Nicht vorlesungsbezogenes Wissen vermitteln (Dies ist eine Zusammenfassung der Vorlesung. Eine Auswahl von all dem was es zu wissen gibt. Wer mehr will darf jeder Zeit Wikipedia verlinken)


Inhaltsverzeichnis

Mathematische Grundlagen

Dieser Abschnitt enthält Mathematische Grundlagen, welche nicht in anderen Vorlesungen behandelt wurden oder für die eine andere Betrachtung notwendig ist. Für Mathematische Grundlagen, welche behandelt wurden, siehe Zusammenfassungen der entsprechenden Vorlesungen. (Bitte keine mathematischen Grundlagen erklären, die anderswo schon erklärt sind... keine Redundanzen!)

Insbesondere:

Verteilungen

Exponentialverteilung

| | | | |

Gutes Modell für:

  • Ausführungszeiten von Tasks
  • Zwischenankunftszeiten von Anfragen

Eigenschaften

  • Gedächtnislosigkeit
  • Falls unabhängig, dann ist .

Poissonverteilung

Diskrete Verteilung.

| | | |

Gutes Modell für:

  • Anzahl der Anfragen in einem Intervall
  • Anzahl der Tasks, die in einem Intervall abgearbeitet werden können

Eigenschaften

  • Reproduktivität: Falls und und unabhängig, dann ist .

Zusammenhang

Bei einem Poisson-Prozess mit Rate ist der Abstand zwischen einzelnen Ereignissen Exponentialverteilt mit Parameter .

Theorie

Warteschlangentheorie

Kendall-Notation:

  • X = Verteilung der Zwischenankunftszeiten
  • Y = Verteilung der reinen Bearbeitungszeiten
  • m = Anzahl Server
  • Werte für X,Y:
    • D: feste Dauer
    • M: exponentialverteilt
    • G: beliebig


Grössen

  • ... Zeit im System (= Zeit in der Warteschlange + Zeit für den Service)
  • ... Anzahl Jobs im System
  • ... Zeit fuer den Service
  • ... Zeit in der Warteschlange
  • ... Durchschnittliche Ankunftsrate
  • ... Durchsatz (Throughput)


Abhängigkeiten

  • : Durchschnittliche Service Zeit


Little's Law


M/M/1

Ankunft: , Bearbeitung: , Verkehrsdichte: . Hat eine stationäre Verteilung falls : .

(Little's Law)


M/M/m

Folgendes sieht etwas zu kompliziert aus, um relevant für die Prüfung zu sein...

Verkehrsdichte: . Hat eine stationäre Verteilung falls :

. Bsp: m=2 (?)

.

CRC-Code (Cyclic Redundancy Check)

Idee: Fülle EDC (Error Detecting Code) - Feld so, dass mod wobei r = Grad(G(x))

ToDo:
Ganzer Abschnitt überarbeiten!!
Alle momentan zu editierenden Einträge werden hier gesammelt.


  • : Daten
  • : Error Detecting Code
  • : Generator-Polynom
ToDo:
Engl field ist deutsch körper odeR?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Die binären Koeffizienten bi formen ein Körper (engl field)

  • "+": XOR
  • "*": AND


Polynome formen ein Ring

  • (R,+) ist eine ablesche Gruppe
  • (R,x) ist ein assoziatives Set (Set in auf deutsch?)
  • Distributivität: a x (b + c) = (a x b) + (a x c)

Bestimmen von EDC

EDC = mod G(x) über GF(2) wobei r = Grad(G(x))

EDC Überprüfen

mod über GF(2) wobei r = Grad(G(x))
ToDo:
Genauer beschreiben. Stimmt das soweit?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Eigenschaften

  • G(x) von Grad r kann
    • alle single bit errors erkennen, wenn G(x) zwei oder mehr Koeffizienten hat
    • alle bursty erros (k-bit aufeinanderfolgende geflipte Bits) mit , wenn G(x) den Summand 1 hat
    • Any error with probability


Netzwerk Protokolle

Grundbegriffe

Bandwith
Durchsatz, bits / Sekunde
Loss
Wieviele Daten gehen verloren?
Latency / Delay
Wie lange geht es, bis ein gesendetes Bit beim Empfänger ankommt
Jitter
Varianz des Delays
Binary protocol
todo
Stateful protocol
todo
Definition: Stateless protocol

A stateless protocol is one that does not maintain a relationship between requests. Each request is unrelated to any previous requests

Advantages

  • Host doesn't have to remember all the clients (no memory needed)
  • Simple


Disadvantages

  • No session information (In HTTP this is tackled by cookies)
  • No user authentication (In HTTP this is tackled by the "WWW authenticate:" option)


Definition: Soft sate protocol

A soft state protocol is a stateful protocol whose session information expires

Example

  • ARP


Definition: Persistent protocol

todo

Layering

Um mit dem komplexen System der Datenübertragung umzugehen, wurde das ganze modularisiert, wobei ein Modul als Layer bezeichnet wird. Jeder Layer übernimmt dabei eine spezifische Aufgabe und baut dabei auf dem darunter liegenden Layer auf. Vom Layer darüber ist er jedoch unabhängig.


Vorteile

  • Einfachere Wartung
  • Einfachere Betrachtung
  • Kann nach oben beliebig erweitert werden


In Verbindung mit Layern sind drei Konzepte von Bedeutung:

  • Service: Was tut der Layer?
  • Interface: Definiert Schnittstellen für den höheren Layer
  • Protocol: Wie der Layer seinen Service erfüllt. Dies ist seine eigene Angelegenheit

TCP/IP Referenz Modell

 ----------------
| Application    |  FTP, SMTP, HTTP: Anwendungen
 ----------------
| Transport      |  TCP, UDP: Transfer der Daten von Host zu Host
 ----------------
| Network        |  IP, ICMP, DHCP; NAT, routing protocols: Routing der Datagramme von Sender zu Empfänger
 ----------------
| Link           |  PPE, Ethernet: Daten Transfer zwischen benachbarten Netzwerk Elementen
 ----------------
| Physical       |  Bits in der Leitung
 ----------------


In jeder Stufe des Modells werden die Daten anders bezeichnet:

  • Application: message
  • Transport: segment
  • Network: datagram
  • Link: frame

ISO/OSI Referenz Modell

ToDo:
Presentation und Session genauer beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.
 ----------------
| Application    |  FTP, SMTP, HTTP: Anwendungen
 ----------------
| Presentation   |  Syntax und Semantik der übertragenen Daten
 ----------------
| Session        |  Long-Term transport, such as checkpointing
 ----------------
| Transport      |  TCP, UDP: Transfer der Daten von Host zu Host
 ----------------
| Network        |  IP, ICMP, DHCP; NAT, routing protocols: Routing der Datagramme von Sender zu Empfänger
 ----------------
| Data Link      |  PPE, Ethernet: Daten Transfer zwischen benachbarten Netzwerk Elementen
 ----------------
| Physical       |  Bits in der Leitung
 ----------------

Application Layer

Service
Datentransfer zwischen zwei spezifischen Programmen (z.B Webserver und Webbrowser)

Übersicht Protokolle

Protocol Purpose Properties
HTTP (HyperText Transfer Protocol) todo
  • Port: 80
  • Stateless
  • Non-binary
  • Protocol in transport-layer: TCP
FTP (File Transfer Protocol) todo
  • Port: 21
  • Stateful
  • Non-binary
  • Protocol in transport-layer: TCP
SMTP (Simple Mail Transfer Protocol) Send and forward emails (to receive emails imap and pop3 is used)
  • Port: 25
  • Stateful
  • Non-binary
  • Protocol in transport-layer: TCP
POP3 (Post Office Protocol) Download emails from a server
  • Port: 110
  • Stateful
  • Non-binary
  • Protocol in transport-layer: TCP
DNS (Domain Name System) Mapping of domain-names to IP-addresses
  • Port: 53
  • Stateless
  • Binary
  • Protocol in transport-layer: TCP or UDP (normaly UDP due to efficency)
DHCP (Dynamic Host Configuration Protocol) Dynamische Zuweisung von IP-Adressen zu Geräten in einem Netzwerk
  • Port: 67 / 86
  • Stateless
  • Binary
  • Protocol in transport-layer: UDP
Telnet (Telecommunication Network) todo
  • Port: 23
  • Stateful
  • Non-binary
  • Protocol in transport-layer: TCP
SSH (Secure Shell) todo
  • Port: 22
  • Stateful
  • Binary (?)
  • Protocol in transport-layer: TCP

http://de.wikipedia.org/wiki/Port_(Protokoll)

HTTP Protokoll (HyperText Transfer Protocol)

  • Stateless: Keine Erinnerungen an frühere Verbindungen
  • Persistent (seit HTTP 1.1): Mit einer Verbindung können mehrer Abfragen gemacht werden
  • Protocol in transport-layer: TCP

HTTP 1.0

  • non-persistent: Eine Verbindung, eine Anfrage
  • 2 RTTs (round-trip-time)

HTTP 1.1

  • persistent: Eine Verbindung, mehrere Anfragen
  • weniger als 2 RTTs (round-trip-time)

Example session

Client

GET /directory/page.html HTTP/1.0
Host: www.servername.com
User-agent: Mozilla/4.0
Accept-language: de


Server

HTTP/1.1 200 OK
Date: T...
Server: ..
Connection: ..
Content-Type: text/html; charset=iso-8859-1
Last-Modified:..
Content-Length:

<html><head>....

FTP Protokoll (File Transfer Protocol)

  • The File Transfer Protocol uses two TCP connections. One to send commands and another to send the data.
  • There are two modus:
    • Active-mode: Server opens data connection to client
    • Passive-mode: Client opens data connection to server (For this, client needs to send PASV command in advance to switch the modus and receive the ports)


Some commands

USER <name>           User <name> would like to login
PASS <password>       Password of the user is <password>
PASV                  Switches to passive-mode
RETR <filename>       Request the file <filename>


Example session

Server: 220 Welcome to the FTP Server
Client: USER foo
Server: 331 Password required for foo.
Client: PASS bar
Server: 230 User foo logged in.
Client: PASV
Server: 227 Entering Passive Mode (84,75,18,19,57,240)


Properties

  • Port: 21
  • Non-binary
  • Stateful
  • Protocol in transport-layer: TCP
  • Out of band control: Separate Verbindungen für Daten und Befehle

DNS Protokoll (Domain Name System)

Maps domain-names to IP-addresses


Eigenschaften

  • Port: 53
  • Binary
  • Stateless
  • Protocol in transport-layer: TCP or UDP (normaly UDP due to efficency)


Vulnerability

  • DNS-Spoofing: If its possible to change entries of a DNS server, the mapping of domain-names to IP-addresses can be changed. In this way users get to see the wrong website for instance


DHCP (Dynamic Host Configuration Protocol)

Dynamische Zuweisung von IP-Adressen zu Geräten in einem Netzwerk


Protokoll-Skizze

  1. Host connecting to network: "DHCP discover" message
  2. DHCP server: "DHCP offer" message offering IP-Address
  3. Host connection to network: "DHCP request" message
  4. DHCP server: "DHCP ack" message


Eigenschaften

  • Port: 67 / 86
  • Stateless
  • Binary
  • Protocol in transport-layer: UDP

Transport Layer

(Transportschicht)

Service
Datentransfer zwischen beliebigen Prozessen


Pipelining

Pipelining ist ein Konzept zur Performance Verbesserung. Anstatt nur ein Packet zu senden und auf die Empfangsbestätigung (ACK) zu warten (Stop and Wait), bevor man das nächste Packet schickt, sendet man mehrere aufeinanderfolgende Packete. Dadurch wird die Bandbreite wesentlich besser ausgenutzt.

Konzepte zur Behandlung von verlorenen Packeten beim Pipelining (Diese werden als ARQ (Automatic Repeat Request) bezeichnet):

  • Go-Back-N: Geht ein Packet verloren, wird das Packet und stets alle darauf folgenden Packete (auch wenn schon einmal erfolgreich übertragen) noch einmal übertragen sobald ein Timeout auftritt
  • Selective Repeat: Es werden nur die Packete erneut übertragen, die nicht beim Sender angekommen sind (oder zulange gebraucht haben)


Definition: Sliding-Window

Ein sliding-window ist eine Intervall aus allen Sequenznummern. Der Sender ist nur erlaubt, Pakete in diesem Intervall zu senden. Der Empfänger erwartet nur Pakete, welche in seinem Intervall (sliding-window) liegen. Sender und Empfänger haben im allgemeinen nicht das selbe sliding-window!


Satz: Sliding-window-size

Für ein Sender mit sliding-window-size M und ein Empfänger mit sliding-window-size N muss gelten, damit zuverlässige Kommunikation möglich ist


Go-Back-N

  • Geht ein Packet verloren, wird das Packet und stets alle darauf folgenden Packete (auch wenn schon einmal erfolgreich übertragen) noch einmal übertragen sobald ein Timeout auftritt
    • Cumulative ACK: Es wird immer das empfangene Packet mit höchster Sequenznummer, welches in-order ist, geacked. Nicht das empfangene Packet selbst
    • Der Empfänger hat keinen Buffer: Packete die in falscher Reihenfolge ankommen werden verworfen
ToDo:
Algorithmus genauer beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Selective Repeat

  • Selective Repeat: Es werden nur die Packete erneut übertragen, die nicht beim Sender angekommen sind (oder zulange gebraucht haben)
    • Jedes Packete wird einzeln geacked
Sender A                                                                  Sender B
--------                                                                  --------
Sliding-windows-size M                                                    Sliding-window-size N

Sending pkt n                                    -- pkt #n -->            Receiving pkt n
  IF unsent(pkt n) AND                                                      Send ACK(n) AND Buffer pkt IF n IN [rcvbase, rcvbase + N - 1]
     n IN [sendbase, sendbase + M - 1]                                      Send ACK(n) IF n IN [rcvbase - M, rcvbase - 1]

Receiving ACK(n)                                 <-- ACK(n) --              otherwise ignore
  Mark pkt as recv IF n                                                  
     IN [sendbase, sendbase + M - 1]                                         
  IF n == sendbase THEN
     move sliding window
       sendbase := min(unackd pkt number)

Timeout ACK(n)
  Resend pkt n AND restart timer n

TCP Flow Control

Definition: Flow-control

Sender won't overrun receiver's buffers by transmitting too much data too fast


  • Empfänger: Teilt dem Sender sein gewünschtes receive-window mit (Repräsentiert den verfügbaren Platz im Buffer)
    • Dazu wird in TCP das RecvWindow-Feld im TCP-Header verwendet
  • Sender: Ist angehalten, die Datenmenge, welche gesendet aber noch nicht geacked wurde, unter dem im RcecvWindow-Feld des Empfängers spezifizierten Wert zu halten


Bemerkung

  • Nicht zu verwechseln mit congestion control!

TCP Congestion Control

Definition: Congestion

Too many sources sending too much data too fast for network to handle

Slow start

  • Für jedes erfolgreich gesendete (und empfangene) Paket wird das congestion-window vergrössert
  • Erreicht das congestion-window ein treshold, wird in den congestion-avoidance-Modus gewechselt


Algorithmus

:start //Start here
Congwin := 1 //Initialization 

:slow-start
 DO { 
  FOR (each segment ACKed)
    Congwin++
} UNTIL (loss event OR CongWin > threshold)
IF CongWin > threshold THEN GOTO congestion-avoidance
IF loss event THEN GOTO start                              //Simmt diese Zeile?


Eigenschaften

  • Exponentielles Wachstum des congestion-window

Congestion avoidance

ToDo:
Funktionsweise kurz beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Algorithmus

:congestion-avoidance
ASSERT (Congwin > threshold)
DO {
  w := Congwin
  every w segments ACKed:
     Congwin++
} UNTIL (loss event)
threshold := Congwin/2
Congwin := 1
GOTO slow-start


Eigenschaften

  • Langsames Wachstum des congestion-window

Fairness

Max-Min-Fairness

Definition: Max-Min-Fair

A set of flows is max-min fair if and only if no flow can be increased without decreasing a smaller or equal flow.

Algorithmus

  • Sei ci die Kapazität der Ressource i (z.B Router, Link)
  • Sei ki die Anzahl Flows durch die Ressource i
  1. Finde den Flaschenhals i (Ressource) für welchen die Kapazität geteilt durch die Anzahl Flows minimal ist. Also für den minimal ist
  2. Setze die Rate jedes Flows welcher die Ressource i benutzt gleich
  3. Blende alle ki Flows aus und reduziere die Kapazitäten der vorhandenen Ressourcen um das bereits beanspruchte
  4. Wenn noch nicht fertig, bei 1 neu beginnen

Proportional-Fairness

Definition: Proportional-Fair

Allocation of rates is proportional fair iff for any feasible allocation we have


Satz: Proportional-Fair

There exists one unique proportional fair allocation. It is obtained by maximizing over the set of feasible allocations, where is the rate of a single flow j


Algorithmus (funktioniert nur in Spezialfällen?)

  • Sei ci die Kapazität der Ressource i (z.B Router, Link)
  • Sei ki die Anzahl Flows durch die Ressource i
  • Sei rj die Rate des j-ten Flows
  • Sei J die Anzahl Flows
  1. Stelle für jede Ressource i die Gleichung auf: für alle Flows j welche die Ressource i benutzen
  2. Definiere die Funktion
  3. Substituiere in J die rj so, dass J nur noch von einer Variable abhängig ist
  4. Maximiere J

TCP Protokoll (Transmission Control Protocol)

Das TCP Protokoll ist ein Verbindungsbasiertes Protokoll

  • Handshaking: setup der Verbindung
  • Reliable: Verlust von Daten wird erkannt
  • In-order-byte Stream: Daten kommen in der selben Reihenfolge an wie sie gesendet wurden
  • Flow control: Es wird nur soviel gesendet, wie der Empfänger empfangen kann
  • Congestion control: Bei überlastetem Netzwerk wird weniger gesendet
    • Slow Start: Starte mit kleinem Window-Size und vergrössere dieses exponentiell
    • Congestion Avoidance: Beginne wieder mit kleiner Window-Size wenn zuviele Packete verloren gingen
  • ARQ: Go-Back-N:

Anwendungsbeispiele sind HTTP, FTP, Telnet, SMTP

UDP Protokoll (User Datagram Protocol)

Das UDP Protokoll ist ein Verbindungsloses Protokoll

  • Unreliable: Daten können beim Empfänger nicht ankommen ohne dass dies der Sender bemerkt
  • No Flow control
  • No congestion control


Anwendungsbereich

  • Fault-tolerant, time-critical applications: For example video streaming, Internet Telefonie.
    • In der Praxis wird jedoch auf für diese Gebiete meist TCP eingesetzt, da UDP Probleme mit Firewalls bereiten kann

Netzwerk-Layer

(Vermittlungsschicht)

Service
Datentransfer zwischen Systemen (z.B Computern)


Übersicht Protokolle

ToDo:
Stimmt diese Zuteilung in etwa? vollständig?
Alle momentan zu editierenden Einträge werden hier gesammelt.
Protocol Purpose Properties
Datentransfer
IPv4 (Internet Protocol) todo
IPv6 (Internet Protocol) todo
Organisation von Netzwerken
ICMP (Internet Control Message Protocol) todo
NAT (Network Address Translation) todo
Intra-AS Routing (IGP = Interior Gateway Protocols)
RIP (Routing Information Protocol) todo
  • Routing: Distance-Vector Algorithm
OSPF (Open Shortest Path First) todo
  • Routing: Link-State Algorithm
IGRP (Interior Gateway Routing Protocol) todo
  • Routing: Distance-Vector Algorithm
Inter-AS routing
BGP (Border Gateway Protocol) todo
  • Routing: Path-Vector Algorithm

Circuit Switching

ToDo:
Gehört das nicht in die Link Layer Schicht?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Bei dieser Art von Netzwerken wird die Bandbreite fix unterteilt und jeder Benutzer erhält einen festen Teil der Bandbreite.

  • Unterteilungsmöglichkeiten der Bandbreite
    • FDMA: Unterteilung des gesamten Frequenzbereichs in kleinere Einheiten. Jeder User erhält einen eigenen Frequenzbereich
    • TDMA: Unterteilung der Zeit: Jeder User erhält eine bestimmte Zeit zum Übertragen, danach sind die anderen an der Reihe
  • Dedicated resouce: Nicht benutze Resourcen werden nicht verteilt sondern sind "idle"


Eigenschaften:

  • Garantierte Performance (dafür jedoch geringere), da jeder Benutzer fix zugewiesene Bandbreite
  • Call Setup benötigt
  • Anzahl Benutzer beschränkt: Eine zu grosse Unterteilung der Bandbreite erlaubt keine sinnvolle Kommunikation

Packet Switching

Bei dieser Art von Netzwerken wird keine Zuweisung von Bandbreite vorgenommen. Jeder Benutzer hat zu jedem Zeitpunkt die Möglichkeit Daten zu senden.

  • Packete: Die zu sendenden Daten werden in kleinere Einheiten (Packete) unterteilt
  • Rescource Sharing: Packete werden mit der ganzen Bandbreite übertragen
  • Soll mehr gesendet werden als möglich, werden die Packete in eine Warteschlange gestellt


Eigenschaften

  • Resource contention (engl Streit um die Resource): Die zu übertragenden Daten können die verfügbare Kapazität überschreiten
  • Congestion
    • Packete werden gequeued, wenn sie nicht sofort gesendet werden können
    • Warten auf die Benutzung des link (? )
  • Store-and-forward: Packete werden von Hop zu Hop übertragen. Der jeweilig nächste Hop beginnt erst mit weiterleiten, wenn das ganze Paket angekommen ist.
  • Grosse Anzahl Benutzer mögich: Jedoch nur unter der Annahme, dass User nicht dauernd die ganze Bandbreite benutzen (? Bessere Formulierung)
  • Grösserer Delay als bei Circuits
  • Grosser overhead infolge der Header für jedes einzelne Packet


Anwendungsbeispiele

  • Dominante Technik im Internet


Packet switching networks lassen sich bezüglich des Routings weiter unterteilen un virtual circuit networks und datagram networks.

Datagram Network

  • Ziel Adresse des Packets bestimmt nächsten Hop
  • Die Route muss nicht für alle Packete die selbe sein, sondern kann während einer Session ändern


Virtual Circuit Network

  • Jedes Packet trägt einen Tag (virtual circuit ID)
  • Tag bestimmt nächsten Hop
  • Fixer Pfad für alle Packete während der Session
  • Pfad wird bei call setup festgelegt


Delay in Packet Switch Networks

Der gesamte Delay setzt sich zusammen aus

  1. Nodal processing
    • Auf Bitfehler prüfen
    • Output Link bestimmen
  2. Queuing
    • Zeitdauer in der Warteschlange bis der Link sendet
    • Congestion Level des Routers
  3. Transmission delay
    • Zeit die für das senden des Datenvolumens benötigt wird
      • L = packet length (bits)
      • R = link bandwith (bps)
      • Zeit zum Senden der Daten = L / R [b / (b/s) = s]
  4. Propagation delay
    • Verzögerung durch die physikalische Übertragung
      • d = Länge des physikalischen Link (Leitungslänge)
      • s = Ausbreitungsgeschwindigkeit im Leiter (ca 2 x 10^8 m/s)
      • Übertragungsverzögerung = d /s

Routing

Routing befasst sich mit dem Problem, wie Packete einen möglichst optimalen Weg an den gewünschten Zielort finden

Link-State-Algorithmus

Die Routing Tabelle wird mittels Dijkstra berechnet. Es wird also das ganze Netzwerk betrachtet und alle kürzesten Pfade berechnet

  • Einsatzbereich: Routen ändern sich nur langsam
  • Umgebung: Gesamte Topologie bekannt
  • Robustheit: Berechnungsfehler für Kosten beeinflussen Kosten-Berechnungen anderer Router nicht
  • Komplexität: O(m + n log n) wobei m links, n nodes
  • Probleme:
    • Gesamte Netztopologie muss bekannt sein, was bei sich ändernden Netzen aufwändig/teuer ist (?)

Distance-Vector-Algorithmus

Zur Bestimmung der eigenen Routing-Tabelle werden die Routing-Tabellen direkten Nachbarn herangezogen

  • Einsatzbereich: Routen ändern sich schnell
  • Umgebung: Nur benachbarte Router bekannt
  • Robustheit: Berechnungsfehler für Kosten propagieren sich durch das gesamte Netzwerk
  • Komplexität:
  • Probleme:
    • Count-to-infinity problem
    • Fehlerhafter Router kann falsche Pfadkosten propagieren

Path-Vector-Algorithmus

  • Ähnlich zu Distance-Vector-Algorithmus
  • Speichert zustätzlich den kürzesten Pfad zu den Richtungen ab
ToDo:
Genauer beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.


IP (Internet Protocol)

Aufgabe

  • Transport eines Packetes zu einem bestimmten Host


Typical problems

  • Loops: To avoid having a IP packet routed in a loop the TTL (Time to live) field gets decremented every hop until it is zero 0 and therefore gets dropped


Properties of IP-addresses

  • hierachical


IPv4

  • Header-Size: variable. ca 20 Bytes
  • Fragmentation: erlaubt
  • IP-Adressen: 32 Bits
ToDo:
Genauere Beschreibung
Alle momentan zu editierenden Einträge werden hier gesammelt.


IPv6

  • Header-Size: fixe 40 Bytes
  • Fragmentation: nicht erlaubt
  • IP-Adressen: 64 Bits
  • Rückwärtskompatibilität durch
    • Dual Stack: IPv6 nach Bedarf auf dem Router in IPv4 übersetzen, wenn das Gegenüber kein IPv6 spricht (führt zu Informationsverlust)
    • Tunneling: IPv6 Paket als Payload in IPv4 transportieren (führt wahrscheinlich zu Fragmentation)
ToDo:
Genauere Beschreibung
Alle momentan zu editierenden Einträge werden hier gesammelt.

Unterschied IPv4 und IPv6

  • IPv6 unterstützt Fragmentation nicht mehr (zur Performance-Verbesserung)
  • IPv6 hat keine Header-Checksum mehr (zur Performance-Verbesserung: TTL ändert sich laufend was eine neue Berechnung der Header-Checksum verlangt)
  • Neu fixe Header-Size von 40 Bytes

IP-Packet fragmentation

ToDo:
IP Fragmentation fertig beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Gegenmassnahmen

  • PMTU (Path-MTU) Discovery: Ein Paket mit maximaler Grösse und dem Flag für DF (Don't fragment) gesetzt wird gesandt. Hat ein Link eine zu kleine MTU wird das Paket verworfen und ein ICMP Error mit der maximalen MTU zurückgeschickt.


CIDR (Classless InterDomain Routing)

ToDo:
Netmask, Netzwerkadressierung, etc beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

ICMP (Internet Control Message Protocol)

Aufgabe

  • Kommunikation zwischen Hosts, Routers und Gateways
    • Error-Reporting: Nicht erreichbarer Host, Netzwerk, Port, Protokoll
    • Echo request/reply

Eigenschaften

  • ICMP Nachricht wird in IP Datagramm übertragen


NAT (Network Address Translation)

Aufgabe

  • Adressübersetzung zwischen internem Netzwerk und externem Netzwerk (Internet)
    • Das interne Netzwerk besteht aus vielen Hosts (viele IP-Adressen), wird gegenüber dem externen Netwerk jedoch als nur 1 Host (1 IP-Adresse) dargestellt (= Masquerading)
    • Bei ausgehenden Packeten wird die IP und der Source-Port ausgewechselt. Der neue Source Ports ist somit stellvertretend für die original IP und original Port und wird gespeichert. Ankommende TCP-Packete können so anhand des Dest-Ports wieder der lokalen IP und dem original Port zugeordnet werden


Eigenschaften

  • Bis zu simultanen Verbindungen
  • Alle Geräte hinter dem NAT werden gegen aussen mit einer einzigen IP repräsentiert


Vorteile

  • Kann IP Adressen von Geräten beliebig ändern
  • Geräte gegen aussen nicht direkt adressbar von aussen (Sicherheit)


Nachteil

  • Keine Server hinter dem NAT
  • Peer-to-Peer Anwendungen müssen den NAT speziell berücksichtigen

RIP (Routing Information Protocol)

Aufgabe

  • Routen von Packeten innerhalb eines Netzwerkes

Eigenschaften

  • Typ: Intra-AS routing
  • Routing: Distance-Vector Algorithm


ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

OSPF (Open Shortest Path First)

Aufgabe

  • Routen von Packeten innerhalb eines Netzwerkes

Eigenschaften

  • Typ: Intra-AS routing
  • Routing: Link-State Algorithm


ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

BGP (Border Gateway Protocol)

Aufgabe

  • Routen von Packeten zwischen Netzwerken

Eigenschaften

  • Typ: Inter-AS routing
  • Routing: Path-Vector Algorithm
  • Sonstiges: de-facto Internet-Standard
ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Link-Layer

(Sicherungsschicht)

Der Link-Layer wird weiter unterteilt

 ------------------------------
| LLC (Logical Link Control)   |  HDLC                      // Stimmen die Protokoll Beispiele?
 ------------------------------
| MAC (Media Access Control)   |  ALOHA, CSMA/CD, Token-Ring, Token-Bus
 ------------------------------
ToDo:
Service: Stimmt das?
Alle momentan zu editierenden Einträge werden hier gesammelt.
Service Logical Link Control
Aufbereitung der Daten zur Übertragung sowie Error-Detection/Correction


Service Media Access Control
Regelt wie sich mehrere Rechner ein gemeinsam verwendetes physikalisches Übertragungsmedium teilen


Logical Link Control Layer (LLC)

ToDo:
beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.


Beinhaltet die Protokolle

  • Broadcast-links (Mehrere Geräte an einem Link)
    • ARP
  • Point-to-Point Data Link Control protocols (Point-to-Point DLC protocols)
    • HDLC : High level data link control
    • PPP : Point-to-Point Protocol

Media Access Control Layer (MAC)

Kontrolliert den Zugang zu einem gemeinsamen Übertragungsmedium


Beinhaltet die Protokolle

  • CSMA, CSMA/CA, CSMA/CD
  • ALOAH, etc
  • Token-Ring, Token-Bus


MAC-Adresse

A MAC address is a 48 bit unique adapter identifier


Properties

  • Flat address space

Übersicht Protokolle

ToDo:
Tabelle ausfüllen
Alle momentan zu editierenden Einträge werden hier gesammelt.
Protocol Purpose Properties
Heading
Protocol name description
  • todo

Definitionen

Definition: Full-duplex

Nodes at both ends of a link can transmit simultaneously

Example: Two-lane road, Ethernet


Definition: Half-duplex

Nodes at both ends of a link can transmit, but never at the same time

Example: Railroad-track, ALOAH


Definition: Simplex

Only one node can transmit

Example: One-way street

Framing

ToDo:
Stimmt das?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Um den Anfang und das Ende von Datagrammen (Netzwerk-Layer) kennzeichnen zu können, wird das Datagramm mit einem Header und einem Trailer versehen. Man spricht dann von einem Frame anstatt einem Datagramm. Da der Link Layer auf Bit / Byte ebene operiert, ist dies nicht wie auf höheren Ebenen durch Size-Felder umsetzbar


Möglichkeiten dies umzusetzen sind

  • Bit-Stuffing: z.B 6 aufeinanderfolgende 1 signalisieren Anfang / Ende eines Frames
  • Byte-Stuffing: Verwendung von Kontroll-Zeichen

Bit-Stuffing

Um zu verhindern, das festgelegte Bitfolgen die als Steuerzeichen fungieren sollen, in den Daten selbst vorkommen, werden zusätzliche Bits eingefügt (=Bit-Stuffing)


Wird als Steuerzeichen z.B 111111 festgelegt (6 mal 1) wird wie folgt vorgegangen

  • Sender: Wann immer eine Serie von 5 aufeinander folgende 1 in den Daten auftritt, wird nach dem 5ten 1 eine 0 eingefügt
  • Empfänger
    • Wann immer eine Serie von 5 aufeinander folgende 1 gefolgt von einer 0 empfangen wird, muss die 0 entfernt werden
    • Wann immer eine Serie von 6 aufeinander folgenden 1 empfangen wird, handelt es sich um ein Steuerzeichen


Beispiel

Steuerzeichen: 01111110 (0, 6 x 1, 0) 

Zu senden:                    011100111111100111110
Bit-Stuffed:                  01110011111011001111100
Mit Steuerzeichen:    0111111001110011111011001111100

Byte-Stuffing

Um zu verhindern, das festgelegte Zeichen (=Byte) die als Steuerzeichen fungieren sollen, in den Daten selbst vorkommen, wird ein zusätzliches Zeichen (Escape Zeichen) eingefügt (=Byte-Stuffing)


Wird als Steuerzeichen z.B 'A' festgelegt wird wie folgt vorgegangen

  • Man definiert ein Escape Zeichen: z.B 'E'
  • Sender
    • Wann immer 'A' in den Daten auftritt, wird ein 'E' vor das 'A' gesetzt. Also 'A' -> 'EA'
    • Wann immer 'E' in den Daten auftritt, wird ein 'E' vor das 'E' gesetzt. Also 'E' -> 'EE'
  • Empfänger
    • Wann immer 'EA' empfangen wird, wird dies durch 'A' ersetzt
    • Wann immer 'EE' empfangen wird, wird dies durch 'E' ersetzt
    • Wann immer 'A' ohne führendes 'E' empfangen wird, ist dies ein Steuerzeichen
    • Wann immer 'E' ohne ein folgendes Steuerzeichen empfangen wird, trat ein Übertragungsfehler auf


Beispiel

Steuerzeichen: E
Escapezeichen: O

Zu senden:           OEH, HALLO ERICH!
Byte-Stuffed:        O0OEH, HALLOO OERICH!
Mit Steuerzeichen    O0OEH, HAELLOO OERICH!

Teilen eines Übertragungsmediums

Um ein Übertragungsmedium zu teilen gibt es folgende Möglichkeiten

ToDo:
Multiplexing???? Korrekter Überbegriff für FDM, TDM, CDM
Alle momentan zu editierenden Einträge werden hier gesammelt.


  • Multiplexing: z.B FDM, TDM, CDM, etc
  • Kontrollierter Zugriff: z.B Token-Ring, etc
  • Konkurrierender Zugriff: z.B ALOHA, CSMA, CSMA/CD, etc
ToDo:
Ist Token-Ring nicht eine Form von TDM? Worin untescheidet sich dies?
Alle momentan zu editierenden Einträge werden hier gesammelt.
ToDo:
Ist das FDM, TDM, CDM Zeugs nicht eine Ebene tiefer?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Multiple Access Link

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Frequency Division Multiplexing (FDM)

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Analogie: Leute an einer Cocktailparty unterhalten sich in verschiedenen Tonlagen

Time Division Multiplexing (TDM)

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Analogie: Leute lassen sich gegenseitig ausreden. Es spricht immer nur genau einer

Time/Frequency Division Multiplexing

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.


Code Division Multiplexing (CDM)

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Analogie: Leute an einer Cocktailparty unterhalten sich in verschiedenen Sprachen



Address Resolution Protocol (ARP)

  • LLC Protokoll (????)
ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Properties

  • Soft sate protocol

Vulnerabilitry

  • ARP-Spoofing: Sending a faked (spoofed) ARP message to the ethernet LAN with the aim that the router believes that your MAC address is associated with a particular IP (not yours)

Point-to-Point Protokoll (PPP)

  • LLC Protokoll (???)
  • Basiert auf HDLC


Properties

  • Error detection, no correction
  • Framing with byte stuffing

ALOHA

  • MAC Protokoll
ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Demand Assigned Multiple Access (DAMA)

  • MAC Protokoll
ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Carrier Sense Multiple Access (CSMA)

  • Random Access MAC Protocol
  • Family: Backoff protocols

Carrier Sense Multiple Access Collison Avoidance (CSMA/CA)

  • MAC Protokoll
  • Erweiterung von CSMA


Eigenschaften

  • Connectionless
  • Unreliable
  • Carrier sense: Only send if no one other is sending
  • Collision avoidance: Via binary exponential back-off
  • Random access: Before attempting a retransmission wait a random time
  • Fehlerdetektion: CRC


Anwendung

  • Wireless


http://de.wikipedia.org/wiki/CSMA/CA

Carrier Sense Multiple Access Collison Detection (CSMA/CD)

  • MAC Protokoll
  • Erweiterung von CSMA


Eigenschaften

  • Connectionless
  • Unreliable
  • Carrier sense: Only send if no one other is sending
  • Collision detection: Abort (after jamming with 48 Bit for safety reason) if a collision occurs
  • Random access: Before attempting a retransmission wait a random time
  • Exponential backoff: Adapt retransmission to network load


http://de.wikipedia.org/wiki/CSMA/CD

Netzwerkprogrammierung in Java

TCP

Client

import java.io.*;
import java.net.*;

class TCPClient {
   public static void main(String argv[]) throws Exception
   {
      String answer;
      Socket clientSocket = new Socket("hostname", 1234);
      DataOutputStream outToServer = new DataOutputStream(clientSocket.getOutputStream()); 
      BufferedReader inFromServer = new BufferedReader(new InputStreamReader(clientSocket.getInputStream()));
      outToServer.writeBytes('hello');
      answer = inFromServer.readLine();
      System.out.println("FROM SERVER: " + answer);
      clientSocket.close();
   }
}

Server

import java.io.*;
import java.net.*;

class TCPServer {
   public static void main(String argv[]) throws Exception
   {
      String in_message;
      String my_answer;
      ServerSocket welcomeSocket = new ServerSocket(1234);
      while(true) {
         Socket connectionSocket = welcomeSocket.accept();
         BufferedReader inFromClient = new BufferedReader(new InputStreamReader(connectionSocket.getInputStream()));
         DataOutputStream outToClient = new DataOutputStream(connectionSocket.getOutputStream());
         in_message = inFromClient.readLine();
         my_answer = in_message.toUpperCase();
         outToClient.writeBytes(my_answer);
      }
   }
}

Links