Telematik 1

Aus II-Wiki
Wechseln zu: Navigation, Suche

Praktikum

Inhaltsverzeichnis

Zusammenfassung

Vorgeplänkel

Daten, Informationen, Signale

  • Daten repräsentieren Fakten, Ideen, Modelle etc. in einer für Menschen und Maschinen verständlichen Form, z.B. Zeichen, Schrift oder Sprache.
  • Information ist das, was ein Mensch aus Daten gewinnen kann, indem er unter Kenntnis der Regeln des Entstehens der Daten den Sinn und Zweck der Daten interpretiert. Eine Maschine kann das nicht, daher spricht man bei der Datenübertragung auch nie von Informationsübertragung.
  • Signale repräsentieren das Modell "Daten" in der realen Welt durch zeitliche oder räumliche Veränderung physikalischer Größen wie Spannung, Strom, Wellenlänge etc.

Signalausbreitung auf einer Leitung

  • Ein Bit benötigt eine Ausbreitungsverzögerung dprop, um von Host A zu Host B zu gelangen. Dies hängt von der Geschwindigkeit des Signals auf der Leitung (z.B. v = 2/3 c) und der Länge der Leitung ab („wie schnell ist das Medium“).
  • Die Datenrate R gibt an, wie schnell der Sender die Bits auf die Leitung geben kann.
  • Die Übertragungszeit dtrans gibt an, wie viele Bits der Sender bezogen auf die Datenrate auf die Leitung geben kann.

Simplex/Duplex

  • Simplex: Nur einer sendet (Bsp. Radio).
  • Half Duplex: Beide senden abwechselnd aber nie gleichzeitig (also muss der eine warten bis der andere pferdsch is) – Problem, wenn man nur ein Kabel verwenden will: Wann weiß der eine wann der andere pferdsch is? Lösung: zB Methode TDD (time division duplex) – jeder kriegt ne gewisse Sendezeit und sendet dann – muss natürlich zu sendende Daten puffern, wenn er grad nich senden darf.
  • Full Duplex – jeder kann senden, zu jeder Zeit. Um Interferenzen bei Verwendung eines Kabels zu vermeiden, kann zB mit verschiedenen Frequenzen gesendet werden.

Netzwerkelemente

  • Switch: Kann eine direkte physikalische Verbindung zwischen den Kommunikationspartnern herstellen (also wirklich ne Leitung schalten, wie das Fräulein vom Amt), verschwendet dann aber Ressourcen bei Pausen.
  • Alternative: Möglichkeit des Packet Switching, also Daten in Pakete gliedern und diese halt vom Switch zu ihren Empfängern verteilen zu lassen – wie die Post (store and forward). Vorteil: Leitung wird nur dann genutzt, wenn sie auch gebraucht wird, aber unheimlicher Verwaltungsaufwand – wo beginnt ein Paket, wo hörts auf, an wen geht es, etc etc etc.

Multiplexing

  • Daten von den Sendern gehen zum Switch (Multiplexer). Der sendet das Zeug zusammen über ein einziges Kabel zu einem anderen Switch (Demultiplexer), der die Daten auf die Empfänger verteilt. So hat jedes Kommunikationspaar den Eindruck, die Leitung gehöre ihm allein und es kann einen kontinuierlichen Fluss an Daten senden. Vom viel komplizierteren System darunter, das die Daten verteilen muss, sieht es nichts.
  • Wie werden die Pakete auf der Leitung auseinander gehalten vom Demultiplexer? Sender kann verschiedene Möglichkeiten des Sendens nutzen: TDM (Zeit), FDM (Frequenz), CDM (Code) etc.
  • Was ist wenn Multiplexer nicht verfügbar? Dann hat man keinen, der den Datenfluss organisiert und verteilt, folglich muss das von den Teilnehmern selbst geregelt werden, die müssen sich auf dem gemeinsam genutzten Medium verständigen und sich nicht gegenseitig die Bandbreite klauen wie Thunderchild den AMW-lern in der Mensa– Medium Access nennt sich das dann (Bsp Klassenraum – Regel: Wenn der Kuchen spricht, haben die Krümel Sendepause)

Walk the LAN

  • Wie werden die Pakte im Netzwerk verteilt? Woher weiß der Router wohin er die Pakte senden muss? Was ist der beste Weg von A nach B?
  • Flooding: einfach alles an alle senden, das ist - Achtung Sarkasmus – sehr bandbreiteneffizient
  • Hot Potato Routing – einfach zufällig irgendwem die heiße Kartoffel zuwerfen, der wirft se dann gleich weiter
  • um das ein bissel intelligenter zu gestalten (kurze Wege, Schleifenfreiheit), muss der Router ständig etwas über die Struktur des Netzwerks lernen – er legt sich Routingtabellen an, indem er erstmal die Pakete beobachtet oder Infos mit anderen Routern tauscht
  • Um die Tabellen nicht riesig groß werden zu lassen: divide and conquer (Teile und Herrsche)

Fehler

  • Fehlerquellen: Konvertierung von Signalen zu Bits, Shared Medium Access, Packetverluste, Fehlleitung von Paketen, Speicher des Routers voll, Sebbl im Netzwerk, ....
  • benötigen Fehlerkontrolle, Flusskontrolle (Empfänger darf nich zuviel auf einmal empfangen) Staukontrolle (nicht zuviele Pakete ins Netzwerk reingeben)

Dienste, Protokolle, Schichten

Welche Dienste muss das Kommunikationssystem unterstützen, welche Regeln (Protokolle) sind dafür zu implementieren? Wie kann man das System in wohldefinierte Schichten unterteilen?

Schichten sind notwendig, da das Zusammenfassen aller Funktionen in einer Applikation schlicht unmöglich ist. Daher werden virtuelle Schichten eingeführt, die ihrerseits kleine Teilprobleme lösen, auf den Schichten unter ihnen aufbauen und diese ergänzen und den anderen Schichten über ihnen Schnittstellen zur Verfügung stellen, auf denen dann aufgebaut werden kann. Auch das ist eine Form von Divide and Conquer.

Dienste

Jede Schicht bietet also einen Dienst an, auf den über einen Standardisierten Service Access Point (SAP) zugegriffen werden kann. Dabei ist den anderen Schichten völlig Brust, wie dieser Dienst von statten geht. Er ist einfach da und man kann ihn nutzen ohne zu wissen wie er funktioniert.

Dienste haben gewisse Grundfunktionen (primitives). Zum Beispiel:

  • Request (REQ): Schicht um einen Dienst bitten
  • Indication (IND): Höhere Schichten darüber informieren, das jetzt was passiert
  • Response (RES): Höhere Schicht antwortet auf Indikation (indem zB Daten angenommen werden)
  • Confirmation (CONF): Der, der den Dienst ursprünglich in Anspruch nehmen wollte, wird nun über Erfolg oder Misserfolg informiert.

Das Ganze mal an Hand eines Telefongesprächs:

1.Sebbls Nummer wählen – REQ
2.Telefon nutzt das Netz und das Telefon klingelt bei Sebbl – IND
3.Sebbl nimmt das Telefon ab - RES
4.Sebbl meldet sich am Telefon mit erotischer stimme – CONF

Übertragung über das Netz

2 Möglichkeiten:

  • als eindeutig abgegrenzte Pakete (so machts IP)
  • als Bytestrom, den der Empfänger dann auseinanderfuddeln muss

An beide Möglichkeiten können verschiedene Ansprüche gestellt werden (nicht immer alles notwendig):

  • Daten müssen komplett ankommen
  • Korrektheit (WENN es ankommt, DANN ist es auch korrekt)
  • Daten werden in der Reihenfolge empfangen, in der sie gesendet wurden
  • Netzwerk soll sicher und verlässlich sein
  • Sender muss darüber informiert werden, wenn Daten angekommen sind (Acknowledge)

verbindungsloser vs. verbindungsorientierter Dienst

Verbindungsorientierte Dienste bauen vorm Datenaustausch erst eine Verbindung auf (CONNECT) und müssen auch in der Lage sein, auf eine Verbindung zu warten wie beim Freizeichen (LISTEN) und müssen diese nach getaner Arbeit wieder terminieren können (DISCONNECT). Außerdem müssen sie eingehende Verbindungen peilen (INCOMING_CONN) und diese annehmen können (ACCEPT). Beispiel: Telefongespräch

Verbindungslose Dienste brauchen diesen ganzen Schnickschnack nicht, da kann man eifnach so Dienste in Anspruch nehmen, ohne das da großartig Verbindungen vorher aufgebaut werden müssen. Beispiel: Post (muss Omma nich sagen, das ich ihr n Paket schicke und sie muss das bestätigen – ich kanns einfach als Überraschung schicken).

Protokolle

Protokolle sind in der Netzwerkwelt unabdingbar – sie geben die Regeln vor, nach denen sich die Maschinen zu verhalten haben. In Protokollen werden die grundlegenden Abläufe definiert und festgeschrieben. Wenn zB der Sender eine 1 mit „Strom fließt interpretiert, der Empfänger aber unter „Strom fließt“ eine 0 versteht“, dann funktioniert das Netzwerk genauso gut wie Sebbls .NET-Programme. Ich glaube demnächst werde ich mal das Opfer wechseln und jemand anders dumm machen, sonst haut mir der Sebbl noch aufs Maul.

Zurück zum Wesentlichen – Protokolle sind also als ein Set von Regeln zu verstehen, die den Service quasi implementieren. Da die höhere liegenden Schichten nicht direkt miteinander kommunizieren sondern sich dafür die unteren Schichten zu Eigen machen, müssen die höheren Schichten logischerweise dieselben Protokolle verwenden um sich verstehen zu können. Dafür ist möglicherweise das Anfügen eines Headers an die Daten notwendig.

Protokolle können folgende Aufgaben haben: Adressierung, Fragmentierung, Teilen von langen Paketen in kleinere, Fehlerkontrolle, Anordnen von Paketen, Flusskontrolle, Flood-Schutz bei langsamen Netzwerkelementen, Ressourcenmanagement, Komprimierung und Homer Simpson Mutter füttern (harte Aufgabe).

Protokolle sind also eine horizontale Beziehung zwischen 2 gleichen Schichten verschiedener Netzwerkteilnehmer.

Dienste hingegen sind vertikale Beziehungen der Schichten untereinander.

Schichten

Die einzelne Schicht kennt an sich nur die Schicht über und die Schicht unter sich und kann auch nur deren Schnittstellen nutzen bzw von der darüber liegenden Schicht benutzt werden. Dabei weiß die höhere Schicht nichts über die untere, die untere Schicht ist einfach da und funktioniert. Mehr muss man nicht wissen. Ich zitiere aus meinem Artikel zum Objekten und Klassen: „Das ist wie wenn Frauen Auto fahren: Sie wissen nicht, wie das Auto funktioniert aber bewegen können sie es trotzdem (zumindest so halbwegs).“

Die Daten wandern also von der höchsten Schicht des Senders immer weiter runter zur untersten physikalischen Schicht, werden dort übertragen und wandern dann am Empfänger alle Schichten wieder fein artig hoch. Das ist natürlich nicht sonderlich effizient (Redundanz, Kompetenzüberschneidungen), macht aber Verbesserungen, Wartung, Updates etc einer einzelnen Schicht extrem einfach.

ISO/OSI-Modell

Altbekannt, Bildchen gibbs im Netz. Nur nochmal ein kurzer Überblick über die Schichten:

  • Physical Layer: Sorgt für die physikalische Verbindung zwischen 2 Netzwerkteilnehmern. So richtig mit Strom, Spannung und so weiter. Dabei sind verschiedene Datenübertragungskanäle möglich, also nicht nur Kupferkabel sondern auch Glasfaser oder drahtlose Kanäle wie WLAN. Stellt außerdem sicher, dass die Bits in der richtigen Reihenfolge ankommen und kann unter Umständen Fehlerkontrolle enthalten.
  • Link Layer: Synchronisiert die Blöcke.
  • Network Layer: Sorgt sich um den Weg der Daten zum Ziel. Bereitet logische Wege der Daten vor, auch zu Subnetzwerken die sich sonstwo befinden können, Routing halt. Stellt Netzwerkadresse zur Verfügung.
  • Transport Layer: Sorgt für den endgültigen Transport der Daten, abhängig von der Netzwerkstruktur (verbindungsorientiert/verbindungslos/verlässlich/...)
  • Session Layer: Synchronisation und Austauschmanagement der Daten - wann darf wer wieviel und wie lange senden
  • Presentation Layer: präsentiert die Daten (Aufbereitung für Application Layer) - dafür wird der Syntax verändert, die Semantik bleibt jedoch erhalten. Der verwendete Syntax ist systemabhängig.
  • Application Layer: Direkte Schnittstelle zum Enduser, stellt diesem dann halt einfach zu nutzende Funktionen zur Verfügung >> Virtual Terminal

Kritikpunkte am ISO/OSI-Modell gibt es zuhauf: Zwar ist die grundlegende Idee der Unterteilung in Schichten auch heute noch gebräuchlich, aber für das Modell entwickelte Protokolle spielen heutzutage keine Rolle, dem Modell fehlt einfach die Martkakzeptanz. Es ist zu groß, zu komplex, es gibt Entwurfsfehler, die ersten Implementierungen waren grottenschlecht und der ganze bürokratische Muff von der ISO bekam der Sache auch nicht gut. Zusätzlich erschien es zu einem ungünstigen Zeitpunkt.

Welche Anforderungen muss ein Modell für das Internet erfüllen?

Das Internet Protocol Modell verbindet die 3 obersten Schichten von ISO/OSI zu einer „Internet Layer“. Die Anforderungen an das Internet sind vielfältig: Es muss jede Art von Daten aufnehmen können (Audio, Nachrichten, Pornos), muss mit verschiedenen Netzwerktechnologien und Clients zurechtkommen (PC, PDA, Handy, ....), muss robust sein, muss ständig erweiterbar sein ohne an Performance zu verlieren (Skalierbarkeit), etc.

Günstig hierfür ist eine Struktur mit einem „dummen“ Netzwerk aber sehr komplexen Endgeräten (Telefon is andersrum). So ist das Internet an sich robust, wenn ein Endgerät mal ausfällt is das ziemlich Brust. Außerdem werden so alle Pakete gleich behandelt (best effort Dienst) und Pakete können verloren gehen, verdoppelt werden etc – die Reihenfolge muss gleich garnicht stimmen. Dafür is das alles sehr billig und man kann schnell riesige Netze errichten. Die intelligenten, teuren Endsystem bügeln das schon aus (reorder usw.)

Das Ganze wird mit 2 Protokollen auf Basis der Transportschicht geregelt:

  • TCP – ein verlässlicher Bytestrom
  • UDP – unverlässlicher Datagrammdienst

Darunter ist der IP-Service (best-effort) auf Layer 2, darüber finden sich halt die bekannten Dienste wie zB HTTP, FTP, SMTP, DNS, etc.

Das Ganze nennt sich nun TCP/IP. Dazu existiert lustigerweise kein Modell, es ist aber das, was heutzutage in der Praxis verwendet wird. In der Vorlesung behandeln wir eine vereinfachte Variante von ISO/OSI, mit dem man auch TCP/IP erklären kann. Dazu wird der Applikationsschicht die Session-Layer und die Presentation-Layer, die eh kein Mensch kapiert hat, einverleibt. Somit gibt’s also nur 5 Schichten.

Zusammenfassung

  • Die Komplexität von großen Netzwerken fordert die Unterteilung in Schichten, um das Ganze handhabbar zu machen.
  • Jede dieser Schichten offeriert einen Dienst, nach oben hin werden die Dienste immer komplexer (und abstrakter), sie bauen auf den darunter liegenden Diensten auf und nutzen diese.
  • Gleiche Schichten in verschiedenen Teilnehmern nutzen Protokolle, um zu kooperieren – diese Schichten sind nicht miteinander verbunden und brauchen daher Standards/Regeln, die jeder kennt und achtet.
  • Protokolle sind also eine horizontale Beziehung zwischen 2 gleichen Schichten verschiedener Netzwerkteilnehmer. Dienste hingegen sind vertikale Beziehungen der Schichten untereinander.
  • Es gibt 2 bedeutende Referenzmodelle, die das Schichtensystem abstrahieren – ISO/OSI (bedeutendes Modell, keine praktisch Relevanz) und TCP/IP (kein Modell, praktisch relevant) – durch sie wird beschrieben, welche Dienste welche Schicht anbieten muss und wie die passenden Protokolle aussehen müssen

Physical Layer

Wie können Daten über ein physikalisches Medium transportiert werden?

Die Data Link Layer gibt dem Physical Layer einen Bitstrom weiter, also eine Folge von Bits, die korrekt sind und in richtiger Reihenfolge geliefert werden. Die Physical Layer muss das Zeusch jetzt übertragen – mit Bit-zu-Signal-Konvertierungsregeln (zB Bit=1: Strom fließt, Bit = 0: Ruhe aufm Leiter).

Fouriertheorem

Jede periodische Funktion lässt sich als Summe von sin und cos Schwingungen ausdrücken, deren Frequenzen ganzzahlige Vielfache einer Grundfrequenz f = 1/ T sind.

Auch unsere übertragenen Daten – die ja so aussehen wie eine zufällige Folge von Rechtecken (digitale 0 en und 1 en halt) - kann man Fourier-transformieren, wenn man annimmt, sie wiederholen sich unendlich offt –> Annahme, das Zeug sei periodisch.

Probleme bei der Übertragung

  • Der Empfänger empfängt womöglich ein völlig verrauschtes Signal - die Entscheidung, was gesendet wurde, kann schwierig werden.
  • Signale werden gedämpft, Teile der Leistung der Signale gehen verloren. Dämpfung a = PSender / PEmpfänger. Die Dämpfung hängt vom Material, von der Entfernung und von anderen Faktoren ab, angegeben wird sie allgemein in dB.
  • nicht alle Frequenzen gehen durch das Medium: Das Medium kann zB eine obere Grenzfrequenz haben.
  • die Dämpfung kann natürlich auch frequenzabhängig sein – manche Frequenzen werden kaum gedämpft, andere dagegen sehr stark.
  • Das Medium verzerrt die Signale, da sich einige Frequenzen schneller ausbreiten als andere – damit haben wir eine frequenzabhängige Phasenverschiebung am Ausgang
  • reale Medien sind verrauscht – Zum Signal wird ein zufälliges Rauschen addiert, zB AWGN – TKT lässt grüßen

Lösungsansätze

Der Empfänger tastet die empfangene Rechteckfolge ab, am besten genau in der Mitte eines Bits, weil da die Wahrscheinlichkeit am höchsten ist, das da die korrekte Amplitude liecht. Aber wo ist die Mitte des Bits? Nicht einfach zu finden bei Sinus-Schwingungen! Nicht genau erkennbar, ob 0 oder 1 gewendet wurde, wenn wir an der Amplitude abtasten – wir müssen also Schwellwerte einführen. (03-22). Unter threashold 1 ists 0, über threashold 2 ist es 1 und dazwischen isses nicht definiert.

Diesen Zwischenbereich darf man nicht zu groß und nicht zu klein wählen: – ist er zu groß, fallen mehr Punkte rein und man kann mehr Punkte nicht entscheiden, - ist er zu klein, ist die Wahrscheinlichkeit für eine Fehlentscheidung höher. Man kann bei sehr niedriger Bandbreite also nur noch die Zeit, die ein Bit braucht, so lange erhöhen, bis die Kurve definitiv über die entsprechende Schwelle gestiegen ist – dann reduziert sich aber die Datenrate. Daraus ergibt sich eine Gleichung für die Datenrate: maximum data rate = 2 B bits/s (B=Bandbreite)

Symbole

Wer sagt eigentlich, das wir nur 2 Bits unterscheiden können? Wie wärs zum Beispiel mit Signalen mit 4 verschiedenen Stufen? Dann hätten wir 4 Symbole, die wir mit 2 Bits darstellen können. So ein Symbol kann natürlich auch aus mehr Bits bestehen. Gemessen wird die Symbolrate in baud (die Datenrate hingegen in bits/s).

Wenn wir ein Symbol aus 2 Bits bauen ist die Symbolrate natürlich nur halb so groß wie die Datenrate.

Wenn wir ein Symbol aus 3 Bits bauen ist die Symbolrate natürlich nur 1/3 mal so groß wie die Datenrate.

Allgemein gilt (nach Nyquist): maximum data rate = 2 B log_2 V bits/s wobei V für die Anzahl der Symbole steht. Heißt das nicht, das ich eine unendlich hohe Datenrate erhalte, wenn ich nur genügend Symbollevels definiere? Ja, theoretisch schon – aber umso höher meine Symbollevelanzahl, umso näher liegend die ja zusammen und ich hab schon bei kleinem Rauschen schnell mal ne Fehlentscheidung – also eine sehr hohe Symbolfehlerrate. V hängt also vom Rauschpegel N ab – aber auch von der Signalstärke S, da ich ja bei stärkerem Signal auch größeres Rauschen haben kann. V = (1 + S/N)^1/2

Daraus folgt: maximum data rate = B log_2 (1 + S/N) bits/s

Takt

Logischerweise brauchen wir auch einen Takt, damit der Empfänger weiß, wann er das Signal auf seinen Wert abtasten soll. Die Synchronisation zwischen Sender und Empfänger ist notwendig. Wie soll er sonst wissen, ob man nun 10 oder 11 Einsen am Stück gesendet hat?

Man kann das Taktsignal extra übertragen, das kostet aber Material und eignet sich daher nur für kleine Entfernungen. Man könnte auch nur an bestimmten Punkten synchronisieren, muss dann aber mit Ungenauigkeiten rechnen. Am besten ist es, die Synchronisation direkt aus dem übertragenen Datensignal zu kriegen.

Das geht fast schon automatisch, wenn ich viele 0-1 Flanken (oder andersherum) hab – da is die Synchro einfach.

Wenn ich aber viele Nullen und Einsen hintereinander übertrage, verliere ich den Takt. Daher gibt’s die Manchester-Codierung (03-36) – da wird die 1 durch eine high-low Flanke und die 0 durch eine low-high Flanke repräsentiert. Problem: – ich brauche dafür natürlich die doppelte Bitrate, das ist natürlich sehr verschwenderisch.

Breitbandübertragung

Wie gesagt, im Basisband haben wir viele Probleme – die 0en und 1en gehen direkt aufs Kabel, sind quasi als Rechteckfunktionen zu vertsehen und brauchen daher im Frequenzbereich eine enorme Bandbreite. Hinzu kommen frequenzabhängige Phasenverschiebungen und Dämpfungen. Wie werden wir das los? Wir bemächtigen uns einer sinusförmigen Trägerschwingung mit einer einzigen (hohen) Frequenz. Womit wir wieder bei AM, PM und FM wären, die der Sinus-Schwingung Informationen '“aufdampfen“. Das auch digital, mit ASK, PSK und FSK. Beispiel für On-Off-Keying: 03-41 bzw. QPSK: 03-44.

Zusammenfassung

Physikal Layer

  • Der Physical Layer hat die Aufgabe, eine logische Bitfolge in ein physikalisches Signal (viele Möglichkeiten) zu verwandeln und über einen Kanal zu senden.
  • Es gibt viele lustige Probleme wie Rauschen, zu wenig Bandbreite usw.
  • Bits kann man in Symbole zusammenfassen
  • Modulation mit stufenförmigen Trägern bringt viele Vorteile

Link Layer

Die Link Layer haben die Aufgabe, den kontinuierlichen Bitstrom in Rahmen/Pakete zu verpacken, ihn also für darüberliegende Schichten lesbar zu machen. Dabei werden auch gleich Fehler gefunden und korrigiert – die physikalische Schicht garantiert ja für nix und einer muss die Fehler ja finden :) Dabei gibt’s viele Fragen – soll es ein zuverlässiger Dienst sein (also fehlerfreie in richtiger Reihenfolge Pakte liefern), soll er verbindungorientiert arbeiten, wie groß soll die Paketlänge sein (umso größer - umso größer ist die Paketfehlerwahrscheinlichkeit)?

Auch Flusskontrolle gehört zur Aufgabe der LL – wenn der Empfänger langsamer ist als der Sender, läuft der Pufferspeicher des Empfängers schnell voll und viele Daten gehen verloren, wenn der Sender nicht mal Pause macht.

Framing

Rahmen und Pakete sind dasselbe, aber auf Link-Layer-Ebene heißts eben Rahmen. Die Rahmengröße ist an das Übertragungsmedium anpassen – je besser das Medium, desto länger kann der Rahmen sein.

Ein großes Problem der Sache ist – wie erkennt der Empfänger aus einem kontinuierlichen Bitstrom, wo ein Rahmen anfängt und wo er wieder aufhört? Verschiedene Verfahren:

  • Character Counting (04-12): Rahmen bekommt einen Header, in dem drinsteht, wie lang der Rahmen ist. Einfacher gehts nicht – was aber wenn die Information im Header verloren geht oder beschädigt/verfälscht wird? Dann kommt hinten nur dünnes raus, wie bei Homer Simpson nach nem halben Bier!
  • Flag Bytes / Byte Stuffing: Das Flag-Byte zeigt Beginn und Ende eines Rahmens an. Problem: Was ist, wenn Flag-Byte in den Nutzdaten auftaucht, weil die Nutzdaten halt so aussehen? Nehmen wir mal an, das Flag Byte wäre 0 11 11 11 0. Wenn das nun in den Nutzdaten auftauchen würde, wäre der Rahmen und alle darauf folgenden unbrauchbar. Also werden Bytes in die Nutzdaten gestopft, das keine 6 Einsen hintereinander auftreten können – zB wird nach der 5ten 1 immer eine 0 gestopft. Der Empfänger weiß das und nimmt nach jeder 5ten 1 die 0 wieder raus. So tritt das Flag Byte niemals in den Nutzdaten auf.
  • Coding Violations: Frames kann mach auch abgrenzen, indem man Coding Regeln verletzt – zB. bei Manchester ein high-high oder low-low überträgt.

Fehlerkontrolle

  • wurde ein oder mehrere Bits gekippt bei der Übertragung?
  • sollen die LL die Fehler nur erkennen oder auch reparieren? beides, denn der Network-Layer will sich nicht mit Fehlern rumplagen

Möglich ist aber auch, das die Fehler nicht korrigiert werden – Der Rahmen wird dann einfach weggeschmissen.

Ebenso möglich ist eine Korrektur ohne Erkennung – versuchen, soviel wie möglich zu reparieren aber nicht dafür garantieren, das alles fehlerfrei ist, das muß dann halt die nächste Schicht wissen und sich darauf einstellen.

Wenn man korrigiert, gibt’s 2 Möglichkeiten:

  • Backward Error Correction – Fehler ausbügeln, nachdem sie passiert sind (durch neu senden zB)
  • Forward Error Correction – Fehler garnicht erst entstehen lassen, zB durch Redundanz in den zu übertragenden Daten

Egal wie sehr man sich anstrengt – die Fehlerwahrscheinlichkeit sinkt nie auf 0!

Wie kann man nun Fehler in einem Rahmen finden?

---Redundanz--- Redundanz ist für die Fehlererkennung unerlässlich. Ohne redundante Bits gibt es 2^m legale Rahmen der Länge m – der Empfänger kann nicht entscheiden, ob ein Rahmen falsch ist, weil es keine illegalen Rahmen gibt. Kippt ein Bit, wird aus einem gültigen Rahmen ein anderer gültiger Rahmen. Man muss also einige mögliche Rahmen als illegal erklären. Daher hängt man also ein paar Redundanzbits an (will m Datenbits behalten) und erklärt ein paar Kombinationen als illegal und hofft nun, dass wenn ein Bit kippt, aus einem legalen Rahmen ein illegaler Rahmen wird. Wie aber drückt man die Wahrscheinlichkeit nach unten, das auch bei Bitfehlern ein legaler Rahmen entsteht? Möglichkeiten:

  • Paritiy-Bit: Ein Parity-Bit wird so angehangen, das man eine gerade Anzahl von Einsen im Rahmen hat (oder halt gerade Anzahl von Nullen oder ungerade Anzahl von Einsen, wie mans halt definiert). Kippt ein Bit, kann man definitiv sagen, das der Rahmen falsch ist. Auch bei 3,5,7,.... Bits. Problem: - Kippt eine gerade Anzahl von Bits, kann man den Fehler nicht erkennen. Korrigieren kann man ihn in keinem Fall.
  • Checksums: Der Sender behandelt die Daten als Integer-Zahlen und addiert sie zusammen – dann wird das Ergebnis der Addition an den Rahmen angehängt und der Empfänger kann die Korrektheit des Rahmens prüfen. Wenn natürlich die Bits so bleede kippen das die Summe nach dem Fehler gleich bleibt, funzt das ooch nich (04-28).

---Hamming-Abstand---

Der Abstand d(x,y) wird definiert als die Anzahl der Einsen in x XOR y. Beispiel: 04-30. Die Hamming-Distanz ist nun D(s) = min{d(x,y)}, also der kleinste Abstand zwischen 2 Rahmen x und y wobei x !=y. S steht für sein Set legaler Rahmen (4-31).

  • Wenn die Hammingdistanz 1 ist, unterscheiden sich ein oder mehrere Rahmenpaare nur in einem Bit – Fehlererkennung oder gar Korrektur unmöglich.
  • Ist die Hamming-Distanz 2, führt ein Bitfehler grundsätzlich dazu, das der Rahmen illegal wird, weil alle legalen Rahmen sich in 2Bits unterscheiden. Korrektur? Fehlanzeige.
  • Ist die Hamming-Distanz 3 wird’s kompliziert. x und y sind legale Rahmen. u wird empfangen. Nehmen wir an, u hat den Abstand 1 zu x und den Abstand 2 zu y. Dann ist es wahrscheinlicher, das der empfangen Rahmen u ein x sein soll – wenns doch ein y war, bei dem sich 2 Bits gedreht haben, haben wirs verschlimmbessert.
  • allgemein: Um n Bitfehler zu finden, ist Hamming-Distanz von n+1 nötig. Um n Bitfehler zu korrigieren, Hamming-Distanz von 2n+1 nötig.


Cyclic Redundancy Check - CRC

CRC kommt mit wenigen Redundanzbits aus, ist zuverlässig und kann leicht in Hardware implementiert werden. Das Ganze basiert auf einer Interpretation des Bitstroms als Polynom – das i-te Bit ist Koeffizient der i-ten Potenz (wenns ein nulltes Bit gibt). Damit gibt’s nur Nullen und Einsen als Koeffizienten.

  • Also – ein Bitstrom, der n+1 Bits lang ist, enstpricht einem n-gradigem Polynom (weil b0*x^0)
  • Rechenregeln: Addition ohne Übertrag = Subtraktion ohne Übertrag = XOR. Weill man an einen Bitstring hinten k Nullen anhängen kann entspricht das der Multiplikation des Polynoms mit x^k – logisch, das Polyonom wird um k verschoben. Und guckt euch das Beispiel der Polynomdivision auf Seite 4.41 nochmal an. Interessant ist für uns der Rest der Polynomdivision.

Wie funktioniert der Spaß nun? Zuerst mal definieren wir uns ein Generatorpolynom G(x) g-ten Grades, das sowohl Sender als auch Empfänger bekannt ist – wir haben also g Redundanzbits. Die Nachricht M wird durch das Polynom M(x) repräsentiert.

1. Zuerst mal hängen wir an M(x) g Nullen dran – x^g * M(x) Beachte: Ein Polynom g-ten Grades repräsentiert eine (g+1)-steillge Bitfolge!!! Für g=11010 müsste man 4 Nullen anhängen, nicht 5. 2. Dann teilen wir x^g * M(x) durch G(x) und berechnen den Rest r(x). 3. jetzt machmer noch x^g * M(x) – r(x), das bewirkt, das die letzten g Nullen von x^g * M(x) durch den Wert r(x) ersetzt werden – Subtraktion ohne Übertrag = XOR.

Das Zeug – nennen wir es T(x) - übertragen wir jetzt zum Empfänger. Lustig ist nämlich, das T(x) jetzt ohne Rest durch G(x) teilbar sein muss. Gibt es Bitfehler, wird T(x) + E(x) empfangen.

Der Empfänger prüft jetzt das Empfangene indem er das Empfangene durch G(x) teilt. Wurde die Nachricht fehlerfrei übertragen, gibt’s keinen Rest. Gibt es einen Fehler E(x), so bleibt der Rest E(x)/G(x) nach der Division übrig – Fehler wurde gefunden und kann korrigiert werden.

Nur für den unwahrscheinlichen Fall, das E(x) / G(x) = 0 ist, erkennen wir den Fehler nicht. Damit das nicht passiert, musst G(x) möglichst intelligent gewählt werden. TCP zB verwendet CRC-32, also ein Polynom 32ten Grades – wenn da doch noch ein Fehler durchschlüpft, also wenn G(x) tatsächlich noch Teiler von E(x) sein sollte, wird das einfach ignoriert.

Backward error correction

Wenn der Empfänger einen Fehler feststellt, kann der Rahmen natürlich nicht einfach so zur nächsten Schicht weitergeleitet werden – reparieren oder wegschmeißen (und dann neu anfordern). Fürs Reparieren braucht man aber viele redundante Informationen im Rahmen (forward error Zeusch). Backward-Protokolle laufen unter dem Namen ARQ – Automatic Repeat Request (schigge mir das Bageed nochäma neu zuuu!).

Wie weiß der Sender, das ein Paket nicht ankam? Der Empfänger könnte zB ACKS schicken. Nur... Dann weiß der Sender immer noch nicht, welches Paket nicht ankam. Und was ist, wenn ACKS verloren gehen?

  • Send 'n Wait: Der Sender könnte zB mit dem Senden eines neuen Paketes warten, bis das alte beim Empfänger ankam und es ein ACK dafür gab. Kommt das ACK nicht, wird das Paket nach einem Timeout neu gesendet. Da haben wir gleich noch Flusskontrolle mit drin. Problem ist nur – was ist wenn ein ACK verloren geht? Dann wird das selbe Paket nochmal gesendet. Der Empfänger weiß aber nicht, ob das das alte Paket ist oder ein neues, das zufällig die gleiche Information tragen muss.
  • Alternating Bit Protocol: Was dagegen tun? Den Paketen Sequenznummern geben und diese in einem Header mit übertragen – und die ACKs müssen diese Sequenznummern auch enthalten. Damit kriegt das ACK eine zusätzliche Bedeutung – er erlaubt dem Sender nun auch, das neue Paket zu senden und bestätigt nicht nur den Empfang des alten. Das Ganze heißt dann Alternating Bit Protocol, weil die Pakete jeweils abwechselnd mit 0 oder 1 identifiziert werden. (4-60). Aber ist das Alternating Bit Protocol auch effizient? Wenn ein Paket über die Leitung geht, braucht es ja eine Zeit d_prop um drüben zu sein. Wenn der E dann das ACK zurückschickt, ist das ja auch lange unterwegs. Das bedeutet, die Leitung bleibt lange unnutzbar für Daten. (4-61).


  • Sliding Windows:

Was tun – klar, mehrere Pakete hintereinander senden, noch bevor die ACKs fürs vorige Paket kamen. Dann reicht aber das Alternating Bit nicht mehr aus, um die Pakete eindeutig zu identifizieren – ein größerer Adressraum ist von Nöten. Und Full Duplex braucht man ooch noch. Geben wir der Sache mal einen n-wertigen Adresseraum mit 2^n möglichen Adressen (von denen vll ein paar verboten sind). S und E einigen sich auf ein bestimmtes Set von Paketnummern, die in einer bestimmten Zeit übertragen werden dürfen – der Sender sendet also Pakete und der Empfänger nimmt nur Pakete an, deren Nummer im Set steht. Die Anzahl der Nummern und damit auch die Anzahl der Pakete die in einem bestimmten Zeitraum gesendet werden dürfen, ist die Fenstergröße. Die Fenstergröße an S und E kann auch unterschiedlich sein – Flusskontrolle.

  • Go Back N: Geht nun ein Rahmen durch einen Fehler verloren, zB weil er nicht durch die CRC Prüfung kam, gibt’s ein Problem – dadurch das die Paketnummern eine bestimmte Reihenfolge haben, schmeißt der Empfänger alle Pakete, die ihn nach dem fehlerhaften Paket erreichen, weg. Der Sender aber kriegt davon erstmal nix mit, er sendet fröhlich weiter seine Pakete – nur die ACKs dafür bleiben aus. Das merkt der Sender auch irgendwann nach einem Timeout-Intervall. Aber bis dahin wurden viele Ressourcen auf der Leitung verschwendet. Der Sender geht also um n Schritte zurück, zum letzten Paket, dessen Übertragung geklappt hat und setzt von dort aus die Übertragung fort.
  • Selective Reject: Schade natürlich, das bei Go-Back-N so viele eigentlich intakte Pakete weggeschmissen wurden – wäre es nicht besser, der E würde die Pakete erstmal cachen? Das macht Selective Reject – es speichert die Pakete nach einem Fehler, sendet aber erstmal immer das ACK des letzten korrekt empfangenen Pakets vor dem Fehler, damit der S merkt das es einen Fehler gab. Liefert der Sender nun das fehlende Paket nach, sind darauf folgende Pakete bereits im Speicher und können über ACKs bestätigt werden. (4-67).
  • Piggybacking: Wenn beide Teilnehmer full duplex unterstützen und Daten hin und her senden, muss man Daten und ACKs ja nicht trennen – Die ACKs werden in den Daten mitgeschickt.

Zu Effizienz der Geschichten bitte mal die paar Seiten ab 04-70 lesen, das sind Grafiken und Formeln, da habsch jetzt keen Bock...

Zusammenfassung

  • Am meisten hat die LL mit Fehlern zu tun – entweder bei der Synchronisation (in Rahmen packen) oder bei der Übertragung (Fehlererkennung/-Reparatur)
  • Einige Fehlererkennungsprotokolle implantieren gleich die Flusskontrolle mit
  • manche Fehlererkennungsmechanismen beeinflussen die Performance kräftig – gute Wahl treffen
  • Verbundungsaufbau und -abbau müssen noch behandelt werden – S und E müssen sich ja vorm Datenübertragen über einiges einigen, zB Windows Size, Paketsequenznummern usw
  • Homer Simpson müffelt. [Anm. von Homer J.: "Deine Mutter ...."]

Medium Access Control

Wie teilt man sich ein Medium mit vielen Teilnehmern, so das es performant bleibt? Wenn sich zB auf ner Cocktailpaty zuviele Leute unterhalten, versteht keiner mehr was – genauso ist das beim Netzwerk, wenn ein E gleichzeitig 2 oder mehr Signale empfängt, gibts Interferenz.

Daher gibts Multiple Acces Protocols, die den Zugriff auf ein shared Medium regeln.

Statisches Multiplexing

Modell: Gruppe von Sendern, auf der anderen Seite der Leitung Grupep von Empfängern – Multiplexer empfängt gleichzeitig die Pakete der Sender, gibt sie auf die Leitung, Demultiplexer verteilt Pakete an Empfänger. Dabei kriegen die Pakete entweder gewisse Sendezeiten oder gewisse Frequenzen auf der Leitung.

Das is aber Mist, wenn man lange idlet und dann mal irgendwann 10 Minuten hohen Traffic erzeugt, weil man ja feste Zeiten zugewiesen kriegt, und diese lange nicht nutzt (idle) aber dann, wenn man Traffic braucht, kriegt man keinen – das muss dynamischer werden, mit Prioritäten und dem ganzen Kram.

Dynamic Channel Allocation

  • Teilen sich Stationen einen Kanal, dann können sei nur über diesen kommunzieren – is der tot is alles scheiße
  • Auf einem Kanal kann es zu Kollision von Paketen kommen, wenn diese „frontal zusammenstoßen“
  • Man müsste Stationen anzeigen, das der Kanal belegt ist
  • Wie verteilt man die Ressource fair? - Wichtig ist, soviele Pakete wie möglich so schnell wie möglich zu transferieren, trotzdem muss für viele Situationen noch genügend Durchsatz für die Einzelstation verfügbar sein und die das Delay darf nicht zu groß werden

Wir utnerscheiden nun verschiedene Protokolltypen an Hand eines wichtigen Merkmales – lassen sie Kollisionen zu oder nicht? (Protokolle, die Kollisionen zulassen, heißen auch Contention-Protokolle, contention = Streit, Auseinandersetzung)

Collision based Protocols

  • ALOHA:

Rede einfach, wenns dir grad passt – das einfachste Protokoll. Vorteile sind, das es einfach zu implementieren ist und das keine Kommunikation zwischen den Teilnehmern nötig ist (also zB müssen sich die Sender zum Satelliten nicht untereinander verständigen). Nachteil ist – Kollisionen kommen definitiv vor. Und – der Sender weiß nicht, ob sein Paket angekommen ist, denn auch die ACKs können kollidieren.

Performance von ALOHA: Verträgt unendlich viele Stationen, die alle unabhängig von einander und gleichartig arbeiten (u.i.v.). Ein Paket wird entweder von einem Paket zerstört, das vor ihm rausging und auf dem Medium ist oder von einem Paket, das nach ihm rausgeht, bevor es am E angekommen ist – das entspricht einem Intervall von 2 d_Trans. Auf 5-22 wird berechnet, das ALOHA gerade mal 20% Durchsatz erreichen kann. Das ist alles andere als schnell. Das Problem is, das ein Paket soo lange Zeit verwundbar ist. Man kann jetzt noch Zeitpunkte (time slots) einführen, bei denen Pakete gesendet werden dürfen (und nur dann), das verbessert die Sache nochmal, bringts aber auch nicht wirklich (slotted ALOHA)

  • Carrier Sense Multpiple Access (CSMA):

Besser man hört erstmal zu bevor man losbrabbelt – also das Medium erstmal abhören, obs auch wirklich frei ist. Nur... Wenn das Medium belegt ist, wann bin ich dran? Wann versuch ichs wieder? Wenn ich sofort, nachdem das Medium wieder frei ist sende (persistentes CSMA), is das sehr ungedugldig, denn wenn das mehrere machen, gibbs Kollisionen. Also wartet man einfach ne zufällige Zeit (nicht persistentes CSMA), bis man es nochnal versucht. Einfach nicht so gierig sein, Rücksicht auf die anderen nehmen – nicht dauernd den Kanal überwachen. Problem: Es gibt Fälle, da wartet man, obwohl man nicht warten muss, das is natürlich Verschwendung...

Persistentes und nicht-peristentes CSMA kann man kombinieren zum p-peristenten CSMA: Einteilung in Zeitintervalle. Wenn Kanal idle ist, dann mit Wahrscheinlichkeit p senden, mit Wahrsch. 1-p aufs nächste Intervall warten. Umso kleiner p, umso weniger Kollisionen – aber umso länger muss ich warten, bis ich mal was senden kann (die scheiße hier!) Hinzu kommt, das, wenn einer sendet, das ein anderer Sender nicht sofort mitkriegt und dann vll auch in den vermeintlich leeren Channel sendet – Kollision!

CSMA/CD: (Kollisionsdetektion) Wenn man nun Kollisionen entdecken könnte auf dem Medium würde man viel Zeit sparen, weil man nicht ewig auf Timeouts warten müsste – man könnte alsbald wieder neu senden. Ethernet arbeitet mit CSMA/CD. Der Sender hört einfach das Material ab – wenn das Empfangene sich von dem, was gerade gesendet hat, unterschiedet, gabs ne Kollision, dann... ja, was dann?

Man kann natürlich nicht sofort wieder neu senden, dann gibts ja gleich wieder ne Kollision. Stattdessen baut der Sender ein sogenanntes Contention Window auf. Dieses besteht aus k Intervallen. Jedes Intervall verkörpert dabei einen zustand, in dem die Leitung frei ist. Der Sender wählt dann zufällig einen der k Slots aus. Wie wählt man k? Umso kleiner, umso größer ist die Wahrscheinlichkeit, dass erneut gesendet wird, aber umso höher ist das Kollisionsrisiko. Man machts von den angeschlossene Teilnehmern abhängig – hat man wenig Teilnehmer, kann k kleine sein. k kann man auch immer schön dynamisch anpassen, je nachdem wie viele Teilnehmer angeschlossen sind bzw wie viel Last sie erzeugen – man siehts ja an der Zahl der Kollisionen, ob k zu klein ist. Dabei verdoppelt bzw halbiert man die Fenstergöße oder addiert/subtrahiert immer ne Konstante oder... es gibt da viele Spielarten ^^

Kollisosionfreie Protokolle

Einfachstes Beispiel – TDMA. Jeder Netzwerkteilnehmer kriegt ein festes Zeitintervall zum senden. Naja, wir wissen ja – unfair, Ilden verschwendet Bandbreite usw.

  • Bit-Map Protokoll

Wir vergeben die Zeitslots nur an die, die wirklich senden wollen. Die können sich melden und kriegen von einem Master einen Token, wie in der Schulklasse halt. Oder der Token wandert immer im Kreis (könnte dann aber auch verloren gehen).

Bit Map machts so – es gibt Contention Slots, das sind kurze Zeitintveralle die ein Sender für sich reservieren kann. Damit meldet er sich, das er ein Paket senden will. Das kann er tun, nachdem alle contention slots durchgelaufen sind. Bei wenig Daten ist das n bissel blöd, weil es ja ein wenig dauert bis die contention slots durchgelaufen sind, das gibt ein Delay. Bei ordentlich Traffic bewährt sich das Protokoll aber mit wenig Wartezeit und guten Durchsatz.

limited contention protocols

Man möchte eine kurze Wartezeit bei wenig Traffic und einen guten Durchsatz bei viel Traffic – gibts da ne gute Lösung? Man muss die contentions slots irgendwie dynamischer handeln, so das man bei wenig Last nicht warten muss, bis alle contentsion slots aller Teilnehmer durchgelaufen sind.

  • Adaptive Tree Walk:

Wurde von den Ebenen eines Baumes inspiriert (05-44). Auf dem hächsten Level gibts nur einen Slot, den alle Knoten sich teilen (wenig Last). Gibts Kollisionen, dh entsteht zuviel Last, wird die Anzahl der Slots verdoppelt, so lange, bis das Netz wieder ohne Kollisionen arbeitet. Bei wenig Last dann halt wieder die Anzahl der Slots halbieren.

Ethernet

Ethernet (IEEE 802.3) ist bekanntlich die am meisten verwendete Kabelnetzwerktechnologie. Sie ist vor allem billig und geht bis 10 Gbit/s. Heutige Netzwerke sind meist sternförmig aufgebaut, dh alle Knoten führen zu einem zentralen Element (Hub, Switch). Ringförmig ginge auch, wer erinnert sich nicht an das gute alte BNC-Netzwerk auf der ersten Garagen-LAN? Ich glaube Homer Simpson, der durfte nie mitspielen ^^

Ethernet ist ein unzuverlässiger verbindungsloser Dienst – Es wird also keine Verbidnung vorm Senden aufgebaut und der Empfänger sendet auch keine ACKS, der Datagramstrom kann Lücken haben die dann von höheren Layern gefüllt werden müssen. Allgmemein wird die Manchester Codierung verwendet (+/- 0,85V) mit der Option auf Codeverletzung – zum Synchronisieren zB.

Paketaufteilung auf 05-52. Wenn Rahmen fehlerhaft sind und durchs CRC fallen, werden sie einfach weggeworfen.

Ethernet verwendet CSMA/CD mit binary exponential backoff. Das heißt:

  • carrier sense (Adapter hört die Leitung ab, sendet nicht wenn jmd anderes sendet)
  • collision detection: Der sender bricht seine Übertragung ab, wenn er merkt, das jemand parallel mit ihm sendet
  • random access: Bevor der Sender es nochmal versucht, wartet er eine zufällige Zeit.

Im Detail:

Adapter empfängt Datagramm von der Netzwerkschicht, Wenn der channel idle ist, wird gesendet, wenn nicht, wird gewartet bis der Channel idle ist und dann sofort gesendet. Wenn der Frame durchgeht, ohne das der Sender eine andere parallele Übertragung bemerkt hat, gitl der frame als erfolgreich übertragen. Wenn jemand anderes sendet, wird die Übertragung abgebrochen und ein jam signal (Störsignal) wird an alle Stationen im Netz gesendet. Danach wird die exponential backoff Technik angewndet: Dabei hängt die zufällige Wartezeit von der Last des Netzes ab. Der Adapter wartet K*512 Bitzeiten mit K € {0,1,2,...,2^m -1}. Bei der ersten Kollision ist K entweder 0 oder 1(2^1 Möglichkeiten). Bei der zweiten Kollision ist K € {0,1,2,3} – also 2^2 Möglichkeiten. Bei der n-ten Kollsion gibts 2^n Möglichkeiten für k (also 0 bis 1023). Eine Bitzeit ist bei 10 Mbit Ethernet 1 µs, für K=1023 wartet der Adapter also satte 50 ms.

Effizienz: Schwer auszurechnen. Es gilt die Formel auf (5-56)

Ethernet is also viel besser als ALOHA, trotzdem einfach und billig.

Netzwerkelemente:

  • Hub: Ein Hub ist dumm. Wenn er einen Frame von einem Adapter kriegt, schickt er ihn an alle anderen weiter. Stumpfsinnige elektrische Zusammenschaltung. Er kann nichts puffern, er verhindert keine Kollisionen, im Gegenteil.
  • Switch: Ein Switch ist viel komplexer. Wenn er einen Frame empfängt, kann er ihn puffern und ihn auslesen, also er weiß wo der Frame hin soll und er weiß wie er ihn zum Ziel schicken kann. In einer Sterntopologie kommt es damit logischerweise auch nicht mehr zu Kollisionen und man kann auf das Performance-raubende CSMA/CD verzichten. Wenn an den Switch auf einem incoming-port mehrere Rechner angeschlossen sind, so wird aus diesen Rechner eine collision domain – also innerhalb dieser Rechner kann es noch zu Kollisionen kommen aber nicht zwischen verschiedenen collision domains.

Ein weiterer Vorteil des Switch ist, das er auch gleichzeitig mehrere 100 Mbit/s Connections verwalten kann, das heißt das die Performance des Netzwerks nicht unbedingt von der Anzahl der Knoten abhängt (beim Hub müssen sich die Knoten die Bandbreite teilen).

Fast Ethernet

Ethernet war ja eigenltich auf 10 Mbit/s ausgelegt. Es wurde aber zu Fast Ethernet verbessert, das bekanntlich 100 oder gar 1000 MBit/s Bandbreite liefert. Dabei sind die Protokolle untereinander kompatibel – man hat einfach die Bitzeit verkürzt. Damit ergeben sich allerdings Komplikationen, was die Kabellänge angeht, so das zB CAT5 Kabel, die ja bis zu 100 m lang sein dürfen, nicht mehr mit Manchseter arbeiten sondern mit 4B/5B.

Außerdem ist beim fast Ethernet jedes Kabel mit genau 2 Netzwerkelementen verbunden, das heiß´t jeder Rechner ist genau mit einem Hub/Switch/anderen rechner verbunden. So gibt es auch keine collision domains mehr und damit auch keinerlei Kollisionen, wenn man einen Switch verwendet. Und man kann full-duplex senden. Verwendet man einen Hub, ist das nich ganz so einfach – dann sind nur Kabellängen bis 25m möglich, man kann auch nur half-duplex senden. Daher kauft man eigentlich nur noch Switches, die sind ja auch nich so teuer.

Zusammenfassung

  • ausgeklügelte MAC Protokolle sind wichtig für die Performance des Netzwerks
  • 3 Hauptkategorien: Kollision, limitierte Kollision, Kollisionsfrei
  • MAC-Protokoll muss Gleichgewicht zwischen Durchsatz, Wartezeit und Fairness finden – es gibt da nicht wirklich DIE optimale Lösung
  • Beispiel: Ethernet – wichtig: Keep it simple!

Internetworking

Also.. wir können bis jetzt schonmal zwischen Knoten kommunizieren, die irgendwie am selben Medium hängen. Toll. Homer Simpson seine Lichtanalage funktioniert auch und wir sind glücklich. Was aber, wenn wir über den Tellerrand hinaus blicken wollen? Wie verbinden wir verschiedene Netzwerke? Dazu, liebe Kinder, erzählt euch der Onkel jetzt mal die Geschichte von Routern, Bridges und Gateways. Es war einmal eine einsame Bridge, bis eines Tages ein Gateway... So Schluss jetzt, wieder ernsthaft:

LAN Interconnection

Wie verbinde ich mehrere LANs? Fangen wir beim Ethernet an. Wenn ich ein LAN mit zu vielen Knoten ausstatte, verliert es arg an Performance und das CSMA/CD pfeifft aus dem letzten Loch wie Sebbl nach einer Runde laufen aufm Sportplatz, wenn zuviele Kollisionen auftreten. Außerdem kann jeder zuhören/die Leitung abhören.

Also brauchen wir viele kleine LANs, die wir miteinander verbinden wollen. Und – vielleicht wollen wir auch mal verschiedene LANs miteinander verbinden, zB ein Ethernet mit einem Token Ring?

Gut, also wir brauchen dafür natürlich Geräte, die das machen. Aber in welcher Schicht setzen wir das an? Es gibt da verschiedene Möglichkeiten – Übersicht siehe 06-06.

Physical Layer Interconnects

  • Repeater Einfachste Option. Einfach ein dummer Signalverstärker, der nicht sieht was er da verstärkt – es interessiert ihn auch nicht. Er verhindert nur die Abschwächung des Signals.
  • Hub: Auch nich viel intelligenter. Viele Kabel gehen rein, viele Kabel kommen raus. Der Hub empfängt ein Paket von einem Kabel und gibt dieses auf alle anderen Kabel. Einfach eine elektrische Verbindung. Der Hub weiß nicht, wo das Paket hin soll und es interessiert ihn auch nicht. Daher erkennt er keine Kollisionen und verhindert damit auch keine.

Die Lösungen auf der physikalischen Schicht sind nicht zufriedenstellend. Man muss die Pakete auslesen können, man muss auf Lastsituationen reagieren können.

Data-Link-Layer interconnects

Der Switch kann die Pakete speichern und auslesen - er weiß wo sie hin wollen und kann sie zum Ziel leiten, also aufs richtige Kabel geben. So gibts keine collision domains. Problem ist natürlich – der Switch muss sich im Netzwerk auskennen, muss wissen über welches Kabel er welchen Teilnehmer erreicht – Routing.

Dazu benutzt der Switch eine Switchtabelle, in der so Sachen wie MAC Adresse, Interface, Zeitstempel usw drin stehen (Zeitstempel für Timeouts, wenn Rechner down oder vom Netz). Die Tabelle füllt er durch zuhören – wenn er ein Paket von A empfängt, weiß er ja, wos herkommt und über welches Kabel er A erreichen kann. Das nennt sich backward learning.

Wenn der Switch nun einen Frame kriegt, dessen Zieladresse er kennt, schaut er, ob Dest-Adress == Source adress. Dann wirft er den Frame weg, weil das Ziel den Frame schon erhalten hat. Andernfalls leitet der Switch den Frame weiter. Kennt der Switch die Zieladresse des Frames nicht, floodet er (schickt den Frame an alle).

Eine Bridge kann nicht nur einzelne Terminals verbinden wie ein Switch, sie kann ganze Netzwerke verbinden (zB Token Ring mit Ethernet). Auch die Bridge untersucht eingehende Pakete und schaut, wo sie hin wollen – die Bridge verbindet nun aber einzelne collision domains untereinander. Für einen Switch in einem der Netzwerke ist eine Bridge nichts weiter als ein Terminal. So wird ein ganzes Netzwerk auf einen einzigen Terminal abgebildet.

Eine Bridge verfügt natürlich auch über so eine Tabelle, in der alle Adressen drin stehen. Aber – reicht das backward learing, wie es der Switch macht, aus? Eigentlich schon. Beispiele mit lustigen Bildchen auf 6-18. Entweder die Bridge leitet das Paket intelligent weiter, wenn sie die Zieladresse kennt. Oder sie leitet das Paket an alle weiter (außer zurück zum Sender) wenn sie die Zieladresse nicht kennt. Oder sie verwirft das Paket, wenns unwichtig ist – zB wenn Empfänger und Sender im gleichen Netzwerk sind, dann muss das Paket nicht an andere Netzwerke rausgehen.

Problem des backward leraings: Wenn man 2 Bridges verwendet, kann das Paket im Kreis laufen (6-20). B1 floodet, Paket zu B2. B2 floodet, Packet zu B1. Usw. Solche Schleifen müssen verhindert werden! Lösungen:

  • Merken, welche Pakete ich bereits weitergeleitet habe, kommt so ein Paket nochmal, einfach wegwerfen. Dazu müssen die Pakete aber eindeutig unterscheidbar sein – zB mit Quellenadresse, Zieladresse und Sequenznummer. Das gibt natürlich Overhead... Auch ist es zeitaufwändig, ständig den Status jedes Paketes zu überprüfen und es braucht Speicher, um sich zu merken, welche Pakete schon da waren.
  • Spanning Trees: Netzwerk als Graph aufmalen: Bridges sind die Kanten und LANs sind die die Knoten im Graph. So kann man redundante Brücken, die die Loops verursachen, finden und eliminieren, indem man ein Baumdiagramm (spanning tree) daraus macht.

Heutzutage wird zwischen Switch und Bridges nicht mehr unterschieden, fast jeder Switch verfügt über einen Uplink, der es möglich macht, ein weiteres Netzwerk anzuschließen.

Higher Layer interconnects

  • Router: Wenn man außerhalb von Netzwerken kommunizieren will, reichen die einfachen, flachen Adressen der MAC-Schicht nicht mehr aus. Da muss eine komplexere Struktur her. Das machen die Router und Gateways, die im nächsten Kapitel behandelt werden. So kann man dann auch logische Netzwerke von den physikalischen Netzwerken unabhängig machen – wenn man zB ein Labor in den USA und eines in Ilmenau hat, sind das 2 physikalische Netzwerke, die über das Internet verbunden sind. Man kann nun aber aus den beiden kleinen Netzwerken ein logisches, großes Netzwerk machen, was durchaus Sinn macht.

Zusammenfassung

  • einfache LANs riechen für komplexe Strukturen nicht aus
  • Interconnection der LANs notwendig: Hub/Repeater auf der physikalischen Schicht, Bridges und Switches auf der Data-Link-Layer, Router auf der Netzwerkschicht und Gateways auf höheren Schichten
  • Probleme: Pakete können Schleifen durchlaufen, simple Adressen skalieren nicht (komplexere Adressräume benötigt)

Network Layer

Wir wissen nun also, das wir große Netzwerke nicht einfach durch zusammenschalten kleiner LANs erreichen können, das skaliert nicht mit. Wenn wir große Netzwerke bauen, müssen wir intelligente Routenführung mit effizienten Routingtabellen (bessere Adresstruktur).

Wenn wir ein Netzwerk mit vielen Millionen Knoten haben, gibts Rountingprobleme zu lösen, die wir bis jetzt noch nicht hatten. ZB ist Flooden hier keine gute Idee, der Spanning Tree Algorithmus ist hier aber ein guter Start: Wenn wir einmal einen Ästepfad zum Ziel kennen, gehen wir den auch, wenn der Knoten tot ist, zerfällt der Baum in 2 Bäume. Es gibt dabei 2 Arten der wegewahl:

  • Forwarding: Pakete einfach weiterleiten. Genauso. wie wenn ich auf Reisen gehe und nicht vorher plane wos langgeht sondern ich entscheide an jeder Kreuzung neu, wohin ich fahre.
  • Routing: Route für Paket planen – und zwar intelligent. Das ist, wenn ich in Urlaub fahre, und mir vorher genau angucke, welche Straße ich nehmen muss und an welcher Abfahrt ich welche Nutte ins Auto einsteigen lasse.

Wie findet man etwas in der Routing Table? Zuerst sucht man den Hostnamen, dann die Netzwerkadresse und dann einen Default-Eintrag (welcher eine Liste von Einträgen mit gleichem next-hop zusammenfasst)

Verbindungsaufbau bei verbindungsorientierten Diensten: Bevor Daten transferiert werden können, wird eine Verbindung aufgebaut zwischen S und E – die Router dazwischen errichten einen Status für diese virtuelle Verbindung. Auf der Netzwerkschicht entsteht dabei eine Verbindung zwischen 2 Hosts, auf der Transportschicht zwischen 2 Prozessen – im Internet gibts nur letzteres (logischerweise).

Welches Protokoll kümmert sich denn nun eigentlich um den Transport der Datagramme von Sender zu Empfänger? 2 Ansätze:

  • individual datagrams: Jedes Datengramm einzeln behandeln (das wird dann garantiert in zB 40 msec geliefert)
  • Fluss von Datagrammen: Muss diese in Reihenfolge liefern und sich um den Zeitabstand dazwischen kümmern, Zwischenstationen brauchen Zustände dafür

Virtual Circuit vs. Datagram-Networks

  • VC-Netzwerke bieten einen verbindungsorientierten Dienst auf Netzwerk-Schicht-Ebene

(beides Host-zu-Host)

VC verhält sich son bissel wie Telefongespräche – erst anrufen, E muss Anruf annehmen bevor Daten ausgetauscht werden können. Jedes Paket enthält einen VC identifier (nicht zu verwexeln mit der dest host adress). Jeder Router, der auf dem Pfad liegt, hält einen bestimmten Status für die Verbindung aufrecht, damit einer bestimmten Verbindung bestimmte Bandbreite oder bestimmte Puffergrößen zugewiesen werden können. Damit besteht ein VC aus einem Pfad von source nach dest, VC-Nummern für jeden Link auf dem Pfad und bestimmten Einträgen in der Forwarding-Tabellen der Router auf dem Pfad. Dabei wird die VC-Nummer des Pakets nach jedem Link geändert – die neue VC-Nummer kommt aus der Forwarding-Table des jeweiligen Routers. Dort werden auch die alten VC-Nummern gespeichert, somit lässt sich der Weg zurückverfolgen. Bei VC geht jedes Paket denselben Weg, nämlich den, mit dem die Verbindung eingerichtet wurde.

Beispiel für VC-Netze – ATM, X25, etc. Zeichnet sich durch einfache Endgeräte aus, das Netz dazwischen ist aber saukompliziert. die Komplexitätä steckt also im Netzwerk. Dafür gibts ein striktes Timing (Telefongespräch halt, da darf nix zu spät kommen).

  • Datagrammnetzwerke bieten einen verbindungslosen Dienst auf Netzwerk-Schicht-Ebene

In Datzagramm-Netzwerken kann jedes Paket einen anderen Weg gehen – wie im Internet (nur ist es im Netz nicht soo chaotisch). Es gibt keinen Verbindungsaufbau oder sowas, keinen Status im Router, die Pakete werden einfach nach ihrer Destination Host Adress weitergeleitet.

Hier ist das Netz sehr einfach, aber die Komplexität steckt in den Endgeräten – die müssen nämlich die Unzulänglichkeiten des Netzes (kein Timing, Fehler, etc) ausbügeln

Dann mal bitte einen Blick auf 07-22 zum, Thema „Adressen in Forwarding Tabellen“ werfen, das tippsch hier nich ab, ich bin doch nich bleede!

Wie sieht so'n Router eigentlich von innen aus?

Ein Router macht hauptsächlich 2 Sachen neben dumm in der Ecke stehen und Kabel aus sich rausgucken lassen: Er betreibt ein Routing Protokoll um Daten sicher und effizient ans Ziel zu bringen und er forwarded Datagramme vom eingehenden zum ausgehenden Link. Er guckt sich an wo das datagramm hinwill, sucht den entsprechenden Eintrag in der Routing Tabelle und ab gehter der Peter (Übereinstimmungen mit Namen von lebenden Personen sind rein zufällig und nicht beabsichtigt). Wenn dabei Stau entsteht, weil der Router zuviele Pakete kriegt und sie nicht so schnell abarbeiten kann (wie Sebbl mit seiner Pornofilmsammlung) wird das Zeusch eben gequeued.

3 verschiedene Verfahren – Bilder auf 7-27:

  • Switching via Memory: Das machen zB PCs, die als Router eingesetzt werden so – incoming Paket wird in den systemspeicher kopiert, ausgewertet und wieder rausgeben – Bandbreite ist eigentlich nur vom FSB des Rechner begrenzt
  • Switching via Bus: Router hat nen internen Bus, den sich alle incoming Pakete teilen müssen
  • Switching via Interconnection Network (crossbar): Busbandbreitenlimitation aufhaben, indem über eine Matrix geswitcht wird, so wie beim ROM-Speicher (Bild angucken)

Daten rausgeben: Zuerst mal puffern, wenn der Router die Daten schneller verarbeitet als er sie auf die Leitung geben kann. Der Buffer kann natürlich auch volllaufen (wie ne Kuh im Wasser), wenn viele Datagramme auf diesen Buffer gegeben werden, dann gibts nicht nur Delay sondern auch Verluste.

Ein lustiges Ding ist auch das Head-Of-Line Blocking – wenn ein Paket, das im Incoming-Buffer steckt, nicht mehr weiterkann, weil sein Ziel-Outgoing Buffer voll ist, können die Pakete danach auch nicht weiter, auch wenn ihre Outgoing-Buffers leer sind – wie wenn man an der Kreuzung steht, gerade aus fahren will aber vor einem steht ein Linksabbieger der den Gegenverkehr beachten muss.

IP: Internet Protocol

Das IP legt Regel fast, wie die Adressen auszusehen haben, wie das Datagramm auszusehen hat, wie mit Paketen umgegangen wird etc. Aufbau eines IP-Pakets auf 7-36. Die Time to Live bezieht sich auf die Anzahl der Hops, die das Paket machen darf – wird an jedem Router dekrementiert. Protokoll gibt an, ob TCP oder UDP oder sonstwas.

Paar Worte zur Fragmentierung: Kommt zustande wenn die Länge eines Pakets auf Link-Layer Ebene kürzer ist als die Länge eines Pakets auf Netzwer-Layer-Ebene. Gibt natürlich Overhead, weil zu allen Fragmenten jeweils ein Header mitgeschickt werden muss. Wird ein Paket fragmentiert, so gibt es einige Informationen, die benötigt werden, um es wieder zusammenzusetzen – das geschieht ausschließlich beim endgültigen Empfänger. Zuerst mal gibts ein Flag, das anzeigt, ob es fragmentiert ist, dann ein Fragment Offset, das angibt, wo das Paket im Originalframe stand und eine identification number, die verschiedene Fragmente zu einem Originalframe zuordnet. Beispiel: 7-40

  • Wie adressiert IPv4?

Wir wissen, das jedes Gerät eine global eindeutige MAC-Adresse hat. Warum brauchen wir noch andere Adressen? Weil nicht jeder Router Millionen Einträge speichern und ständig durchsuchen kann. Man braucht also ein hierarchisches Schema, das die tatsächliche Struktur der Netze wiedergibt – Adressen relativ zu höheren Gruppen also zB: Subnetz1:Subnetz2_von_Subnetz1:Subnetz_3_von_Subnetz_2_von_Subnetz_1:....:Geräte-ID

Dabei sollte darauf geachtet werden, das ein Unterschied zwischen physikalischer, geographischer Nähe und logischer Nähe gemacht wird!

Angucken: IP-Adressklassen auf 7-46

Klasse A ist für große Organisationen die viele Rechner haben. Klasse C für kleine Netze mit wenig Rechnern, dafür eben viele dieser Netze. Alle können aber nur eine Level2-Hierarchie herstellen, man kann aber den Host-Bereich noch in weitere Subnetze unterteilen. Adressen mit 127.x.x.x sind loopbacks – siehe die Bitchchecker-Story ^^ Die ersten Bits von IP-Adressen werden für die Subnetze vergeben, die letzten für den Rechner an sich. Dabei kann ein Rechner mehrere NICs haben, jeder kriegt ne eigene IP. Ein Subnetz bezeichnet alle Rechner mit gleicher Subnetzadresse, die untereinander kommunizieren können, ohne den Router dafür zu beanspruchen.

Die bereits gezeigt Einteilung in Klasse A,B,C,D,E (classful adressing) sind verschwenderisch mit Adressräumen – einem Klasse B-Netz stehen zB 65.000 Hostadressen zur Verfügung, auch wenn es nur 1.000 davon nutzt – dann sind 64000 Adressen verschwendet. Daher verwendet man CIDR – Classless InterDomain Routing. Die Subnetzadresse kann hier beliebig lang gestaltet werden udn wird der IP-Adresse angehangen – zB 213.5.15.489/23 – die ersten 23 Bits stehen da für das Subnetz. Die Subnetzgrößen können sich also nur verdoppeln – 256,512,1024,...

Der ISP kauft nun einen bestimmten Adressbereich und vergeben dann aus diesem Bereich wiederum kleinere Bereiche an die Endkunden. Wie das genau aussieht schreibsch jetz nich, draußen sinds 30°C und England spielt gerade gegen Portugal im Viertelfinale. Guckt euch den Dreck gefälligst selber an – 7-56. Das Ganze erlaubt sehr effizientes Routing der Daten. so hat zB ganz Europa einen bestimmten Adressbereich – das heißt, der Router, der in den USA steht, braucht für ganz Europa nur einen Eintrag zu führen. Das Ganze überwacht die ICANN.

Der Host kriegt seine IP übrigens „hard-coded“ vom Sysadmin (Systemsteuerung > Netzwerk > TCP/IP> IP-Adresse) oder vom DHCP-Server – Dynamic Host Configuration Protocol

  • NAT – Network Address Translation

Idee – ein Subnet erhält nur eine IP-Adresse nach außen hin, so braucht man keinen großen IP-Bereich vom ISP kaufen. Außerdem kann man die Adressen in seinem kleinen Netzwerk ändern, ohne das jemand von außen was davon mitkriegt – genauso kann man den ISP ändern, ohne das jedem PC sagen zu müssen. Und man kann von außen nicht direkt auf die Rechner im Subnetz zugreifen – Hackergeschützt ^^ Wie aber peilt der NAT-Router, welchem Rechner im Subnetz nun ein Paket aus dem Internet gehört? Es gibt eine NAT-Tabelle, in der jede Kombination aus (NAT IP / Port #) mit jeder (IP / Port #) drinstehen.

Geht ein Paket raus, wird dessen Quell-IP durch eine NAAT-IP ersetzt und es kriegt einen neuen Port. Kommt ein Paket rein, wird die NAT-IP durch die richtige Ziel-IP ersetzt und auch der richtige Port wieder eingesetzt. Der Router muss halt genau wissen, welche (eindeutige) Kombination aus NAT IP und Port er welchem Rechner im Subnetz zugeordnet hat. Wers nich gerallt hat: 7-63.

Da wir 16 Bit Port-Adressen haben, sind 60000 mögliche Verbindungen mit nur einer IP-Adresse möglich. NAT vergewaltigt aber so ein bissel das ganze Netzwerk-Konzept mit Ende-zu-Ende Verbindung und der Idee, das Router nur bis zur Layer 3 gehen – da lieber sollte man die IP-Adressenknappheit mit IPv6 lösen... Naja...

  • ARP – Address Resolution Protocol: Wenn der Router ein Paket empfängt und die IP-Adresse keiner MAC-Adresse in seinem Netz zuordnen kann, was macht er dann? Rumschrein – Wem gehört die IP 'so-und-so'? (Senden eines Paketes mit MAC-Dest FF-FF-FF-FF-FF-FF, alle kriegen das dann). Empfänger antwortet dann mit seiner MAC-Adresse. Der Router kann Des Empfänger's MAC nun in seiner ARP-Tabelle speichern.
  • Routing to Another LAN: Bsp 7-67
  • ICMP – Internet Control Message Protocol: Wird von Hosts und Routern verwendet, um sich über Netzwerkspezifische Dinge zu verständigen – also zB „Dest. A nicht mehr verfügbar“ oder Einigung über Protokolle, Ports etc.
  • IPv6: Da der 32 Bit Adressraum von Ipv4 bald erschöpft ist, wird der auf 128 Bit angehoben. Außerdem gibts dann 40 Byte Header, die auch die QoS verbessern sollen. Und Fragmentierung solls auch nimmer geben. Checksum wurde auch gestrichen, um Rechenzeit bei jedem Hop zu sparen. Und am ICMP wurde auch geschraubt (ICMPv6) – neu zB „Packet too big“

Da nicht das ganze Inet an einem Tag umgestellt werden kann, sondern nur Teile, werden in der Übergangszeit die IPv6 Pakete noch einen Ipv4 Header kriegen.

Routing Algorithmen

Dient dazu, den effizientesten Weg eines Pakets durch das Netzwerk zu finden.

  • verbindungsorientiert: Routing Algorithmus nur beim verbindungsaufbau
  • verbindungslos: entweder für jedes Paket einzeln oder die Forwarding-Tabellen der Routerwerden periodisch aufgefrischt

Dabei wird eine Metrik eingeführt – die Kosten. Das kann für die Anzahl der Hops stehen, für die €-Kosten der Benutzung der Leitung (vom ISP zB), für Delay etc. Dementsrechend ist der kürzeste Weg nicht unbedingt der mit den wenigsten Hops oder den wenigsten zurückgelegten Metern – sondern das bezieht sich auf die jeweilige Kostenmetrik.

Man unterscheidet nun 2 Typen von Routing-Algorithmen:

  • nichtadaptive Routingalgorithmen: Basieren ihre Wegewahl nicht auf den aktuellen Netzwerkzustand (zB Flooding)
  • adaptive Routingalgorithmen: Basieren ihre Wegewahl auf den aktuellen Netzwerkzustand (zB Distance Vector)
  • Flooding: Jedes Paket wird in alle Richtungen versandt – außer in die, aus der es kam – haben dann x doppelte Pakete im Netzwerk. Die reduzieren mit:

a) Hop-Counter im Header – jedes Paket darf nur so und so viele Hops machen, wenn der Counter =0: wegschmeißen. Idelerweise ist der Hop Counter mit der Länge des optimalen Wegs initialisiert worden b) Sequenznummern vergeben – damit können Pakete, dessen Sequenznummern schonmal durch sind, weggeschmissen werden Bei militärischen Einsätzen ganz gut – Da gibts viiieeele Router und wenn einer zerstört wird, lebt das Paket noch weiter. Oder bei Ad-Hoc Netzwerken, wo die Zahl der User immer schwankt. Oder bei Updates von vielen Systemen gleichzeitig

Adaptive Routing-Algorithmen

Die nicht-adaptiven Routingalgorithmen versagen, wenn das Netz unausgeglichenen und ständig wechselnden Traffic hat. Das Netz muss sich solchen Situationen anpassen können. Dafür gibts ja die adaptiven Routingalgorithmen:

  • Zentralisiert: Ein zentraler Router, dessen Routingtabelle vom Traffic abhängt. Jeder Router im Netz lässt dem zentralen Router Infos zukommen und dieser errechnet daraus die optimale Route. Diese Routen werden dann ausgetauscht.
  • Isolated Adaptive Routing: basiert auf lokalen Infos des Routers, kein Austausch mit anderen Routern. Bsp: Hot Potato Routing – das Paket einfach so schnell wie möglich loswerden – also an den Ausgabeport mit der kleinsten Queue. Noch n Bsp: Backward Learning: Die Pakete beinhalten dest und source Adresse und einen Hop Counter – aus diesen Daten kann das anfänglich dumme Netzwerk Daten über seine Topologie sammeln. Am Anfang gibts zB Hot Potato. Ein Router stellt zB fest, das ein Paket mit Hop Count von 1 von seinem direkten Nachbarn kommt. Hop Count n – Source ist n Hops weit weg. So lernt das Netzwerk immer besser – muss aber auch mal periodisch alles vergessen, um tote Links zu erkennen.
  • Distributed Adaptive Routing: Router tauschen sich ständig aus und passen dahingehend ihre Routingtabellen an. So kann ein Pfad mit geringen Kosten durch den Routerdschungel gefunden werden – Router kennt seine Nachbarn und Kosten dahin. Static:Routers brauchen lange für ne Änderung. Dynamic:Änderung geht ficks

Distance Vector

  • iterativ: geht so lange, bis keine Knoten mehr Infos austauschen
  • asynchron: Knoten müssen Infos nich immer zu bestimmter Zeit austauschen, die machen das, wennse Bock haben
  • distributed: Jeder Knoten kommuniziert nur mit seinem direkten Nachbarn – nicht mit allen anderen Knoten im Netz
  • jeder Knoten hat seine eigene Distance Table – Zeilen für alle Ziele, Spalten für alle direkten Nachbarn

Dazu mal das Zeug auf 7-92 ff. angucken, da kommt viel mit Formeln, das machsch jetzt nicht. Außerdem spielt gerade Frankreich-Brasilien. Das Beispiel dort reicht eigentlich, um das Prinzip des Verfahren zu verstehen. Die Tabelle ist übrigens korrekt, für den Fall das einige zweifeln. Warum steht zB für D^E(B,A) eine 7 in der Tabelle, wo man eine 8 erwarten könnte? Tja, weil die Kosten von A nach B 7 betragen (hätte man also insgesamt 8) – das ist so teuer, das man lieber wieder aussen rum geht: Also E > A >E >D >C>B = 7. Die Distance Table kann zu einer kompakteren Routingtable umgeformt werden, wenn man die uwnichtigen, teuren Wege weglässt.

Sollten sich nun die Kosten zu einem Knoten ändern, informiert dieser Knoten seine Nachbarn darüber. diese berechnen ihre Routingtabelle neu und informieren ggf. ihre Nachbarn usw. - nur informieren, wenn sich wirklich ein Weg zu einem Ziel verbilligt.

Link State Routing und Dijkstra-Algorithmus

Die Kosten zu allen Knoten sind hier jedem bekannt, jeder Router hat die gleichen Informationen durch Broadcasten. Somit kann ein Router den Weg durch das ganze Netzwerk selber berechnen – das geht mit Dijkstra:

Hierbei starte ich mit einer Initialmenge N, die ein Set von Quellknoten s enthält. Bei jedem Schritt füge ich nun einen weiteren Knoten v hinzu und berechne mit meinem wissen den kürzesten Weg dahin. Das heißt, ich guck in mein bekanntes Set von Knoten und suche aus diesem bekannten Set den Weg mit geringsten Kosten zum neuen Knoten v. Dann gehört v zu N. Jetzt muss ich nur noch die Kosten zu allen Nachbarn, die noch nicht in N drin sind, nochmal neu berechnen, denn durch den neuen Knoten könnte sich ja ein Weg verbilligt haben.

In der Routing-Tabelle steht dann für einen Knoten v zwei Einträge: d(v) (also die Kosten dahin) und p(v) (welchen Knoten muss ich zuletzt passieren, bevor ich bei v bin – predecessor)

Ist v jetzt also der neue Knoten, w ein Knoten der bereits in N ist und d(w) der bisher günstigste Weg zu w. Wenn jetzt d(v) + c(v,w) < d(w) so wird d(w) = d(v) + c(v,w). Also – wenn es günstiger ist, w über v zu erreichen, dann mach ich das auch. c(x,y) steht für die Kosten zwischen c und y. Dijkstra merkt sich ja auch immer den letzten Knoten, der auf dem Weg passiert werden muss: p(w)=v

d(v) ist also der kürzeste weg zu v – vorerst. Wenn ein neuer Knoten reinkommt, könntes dann ja einen noch kürzeren geben. Also ist d(v), so lange der Algorithmus noch nicht terminiert ist, immer eine Schätzung. Das Beispiel zu Dijkstra ist sehr hilfreich: 7-108 ff. Danach kommt ooch noch dieser illustre Korrektheitsbeweis, durchlesen kann man sich den ja mal. Dijkstra bietet eine Komplexität von O=n², was bei dichten Netzen sehr gut ist – bei weniger dicht besiedelten gibts bessere Verfahren.

Zurück zum Link State Routing: Jeder Router berechnet die Kosten zwischen sich und den angrenzenden Routern, packt diese Infos in ein Paket und flooded das durchs ganze Netzwerk (mit Sequenznummern, damit die Pakete weggeworfen werden, wenn ein Router sie bereits gesehen hat). Wenn ein Router alle Pakete aller anderen Router empfangen hat, kann er die Topologie des Netzwerks berechnen und damit auch den kürzesten Weg zu einem beliebigen Ziel X.

Der Bellman-Ford-Algorithmus: Dijkstra berechnet den kürzesten Weg nur für Kosten, die positiv sind – 0 geht auch noch. Bellman-Ford geht weiter, hier sind auch negative Kosten der Links möglich. Man muss hier nur aufpassen, das man keine Runden mit negativen Gewichten läuft, denn so sind Kosten von -Unendlich möglich – das Perpetuum Mobile hat Herr Effpunkt aber noch nicht erfunden, das kommt erst in 5 Jahren.

Bellman-Ford ist die Basis für das Distance-Vector Verfahren. Der Hauptunterschied zwischen Dijkstra und Bellman ist, das Dijkstra in jedem Schritt einen neuen Knoten hinzufügt und seine Nachbarn durchrechnet auf Kosten – die Knoten, die schon in N sind, nimmt es als optimal an und lässt sie so wie sie sind. Bei Bellman ist das anders, da werden in jedem Schritt alle Knoten durch gerechnet.

Zum Algorithmus auf 7-123, der negative cycle check: Ich teste, ob ich über u noch schneller zu v komme. das habe ich in der Schleife vorher aber auch schon getan und d(v) so angepasst, das ich über u zu v komme. Warum prüfe ich das jetzt nochmal? Naja, wenn der Weg schon über u zu v führt und ich bei der zweiten Prüfung nochmal eine Verbilligung feststellen kann, ist was faul – denn wenn ich zehnmal prüfe wirds zehnmal billiger usw – also muss hier so ein Perpetuum-mobile-Kreis vorliegen, der irgendwann in Kosten von -Unendlich endet.

Jetzt kommt noch der lustige Korrektheitsbeweis auf 7-125.

Verlgeich zwischen Distance Vector und Link State:

  • Nachrichtenkomplexitiät: Bei LS müssen sich alle Router untereinander austauschen, bei DV nur die direkten Nachbarn – LS hat da also O(n*E), wobei n = Anz. Knoten, E= Anz. Kanten
  • Konvergenzgeschwindigkeit: LS: O(n²) benötigt O(n*E) Nachrichten, kann oszillieren, bei DV variiert die Konvergenzzeit, es kann Routingschleifen geben und es gibt das Count-To-Infinity-Problem
  • Robustheit – was passiert, wenn ein Router falsche Linkkosten propagiert?: LS: Jeder Knoten berechnet seine eigene Tabelle – der Fehler wirkt sich nur lokal aus. DV: Da jeder Knoten die Tabelle anderer Knoten nutzt, verteilt sich der Fehler über das ganze Netz.

Hierarchisches Routing

Bisher haben wir angenommen, alle Router seien gleich und das Netzwerk sei flach – is natürlich n bissel anders. Man kann nicht alle 600 Millionen Rechner in seiner Routingtabelle führen. Das Internet besteht aus vielen Netzwerken, in denen jeder Admin das Routing selber in die Hand nehmen will, vll mit verschiedenen Algorithmen. Wir fassen nun Router in verschiedenen Regionen zu Autonomen Systemen (AS) zusammen – Router im gleichen AS haben auch das gleiche Protokoll (Intra-AS), Routers in versch. AS können auch versch. Protokolle haben. Wie kommunizieren die AS untereinander? Mit sog. „Gateway-Routern“ (Inter-AS-Routing untereinander). Grafik 7-132.

Damit ist klar, das das Inter-AS Routing irgendwie durch einen Standard für alle gleich sein muss, damit alle AS im Internet kommunzieren können. Das Intra-AS kann der jeweilige Admin dann selber bestimmen, der Gateway Router „übersetzt“ ja quasi von Internet ins interne Netzwerk. So kann auch ein performantes internes Netzwerk entstehen, obwohl es nach außen hin vielleicht langsam ist (policy). Die Teilnehmer im Inneren des Netzwerkes müssen nicht alle Adressen des Internets kennen, die müssen nur wissen, über welchen Gateway-Router sie wohin im Netz gelangen können – die Forwarding Tables werden daher auch schön klein. Das ist genauso wie wenn ich von Ilmenau nach München will – ich muss nicht wissen, wie ich genau da hinkomme, es reicht mir, wenn ich weiß welche Straße ich aus Ilmenau raus nehmen muss. Das setzt natürlich voraus, das die Gateway Router in ihrem kleinen Netzwerk propagieren, welche anderen AS sie erreichen. Daher haben auch die internen Router, die keine direkte Verbindung zum Netz haben, sowohl Intra-AS-Protokoll als auch Inter-AS-Protokoll haben müssen – sie wissen vom Inter-AS welchen Gateway sie nach draußen nehmen sollen und über Intra-AS wie sie am günstigsten zu diesem Gateway kommen.

Man klassifiziert die AS nun an Hand der Anzahl ihrer Gateway-Router, die das AS mit dem Internet verbinden – ein kleines Firmennetzwerk hat zB nur einen Uplink zum Netz, ein etwas größeres hat vielleicht 2. Dieses etwas größere könnte dann routen, dh es könnte Verbindungen weiterleiten – will das aber nicht. Bsp Gartentür: Ich hab 2 Gartentüren, meine Nachbarn könnten dann meinen Garten als Durchgang benutzen – das willsch aber nicht. Die, die das wollen, sind die ISPs, die haben viele Uplinks zum Netz, die kriegen dann aber auch Geld dafür – das nennt sich dann Transit AS.

Routing im Internet

In den Intra-AS spielen 3 Routingverfahren eine Rolle:

  • Routing Information Protocol (RIP) – Distance Vector
  • Open Shortest Path First (OSPF) – Link State
  • proprietäres Cisco-Ding: Interior Gateway Routing Protocol (IGRP)

Im Inter-AS hat man sich weltweit auf das Border Gateway Protocol (BGP) geeinigt.

RIP:

Distanzvektorverfahren mit Metrik = Anzahl der hops (maximal 15). Alle Router senden aller 30 Sekunden Nachrichten (adveristments, UDP-Pakete) zu ihren Nachbarn und teilen mit, wohin sie routen können – das ist eigentlich nicht nötig, es würde reichen was zu sagen, wenn sich was geändert hat - aber so merkt man, wenn ein Router stirbt. Bsp: 7-143. Wenn man 180 s nix mehr hört von nem Router, wird er für tot erklärt. Das schickt man in nem Ad weiter, die anderen Router berechnen ihre Tabellen neu und schicken ggf, wenn sich was geändert hat, auch wieder Ads weiter. So verbreiten sich tote Links sehr schnell im Netzwerk.

OSPF:

Link State – dh, alle Router kennen die Topologie des Netzwerks und verwenden Dijkstra zum Berechnen des besten Wegs. Die Adveritsments werden an alle gefloodet, es sind IP-Pakete (also unter TCP/UDP). Es sind viele Pfade mit gleichen Kosten erlaubt, RIP kann immer nur einen. Außerdem kann OSPF auch Kosten an den Links verwalten, das kann RIP ooch nich.

Das hierarchische OSPF ist kompliziert aufgebaut, mit verschiedenen Routertypen – zB gibts da Area Border Routers, die alle Infos aus ihrem Gebiet sammeln und an andere Area Border Routers weitergeben. Oder die Boundary Routers, die verschiedene AS miteinander verbinden.

BGP':

Wenden wir uns dem Inter-AS Protokoll zu. Das ist der Standard im Internet. BGP vermittelt jedem AS, welche Rechner/Subnetze es in anderen AS erreichen kann. Das muss dann jeder Router in so einem AS wissen. Somit kann erst ein Subnetz seine Existenz ins Internet hinausschreien - „Hallo, hier bin ich! Hiiieeer! Hier unten!!!“ Außerdem errechnet BGP noch, welche Wege denn nun kostengünstig sind.

Also unterhalten sich die Gateway Router (stellvertretend für ihre AS) über BGP-Sessions (TCP-basiert) und tauschen Informationen aus. Wenn ein AS sagt - „Über mich erreichst du Sebbl“, verpflichten sich das AS, alles, was zu Sebbl geht, anzunehmen – (in diesem Beispiel kann das AS Urlaub nehmen ^^).

Man unterscheidet da zwischen internen und externen BGP-Sitzungen – intern erzählt der Gateway eigenen AS, was durch ihn erreicht wird ('Hier Kinners, wenn ihr nach London telefonieren wollt, dann über mich') und extern heißt, zwei Gateways tauschen sich aus – zB kann ein Gateway einem anderen sagen, das er Verbidnugnen weiterroutet ('ich hab hier nen heißen Draht nach Paris, wenn du willst, kann ich alle Anfragen aus deinem AS über mein AS nach Paris weiterleiten, das kostet aber). BSP: 7-155.

In so einem BGP-Paket steht der prefix drin (Adresse) und die Route dahin – also durch welche AS geht es und man gibt den nächsten Router im AS an. Also wenn ich durch AS67, AS17 und dann zu AS30 will, muss ich wissen, an welchen Router in AS67 ich mich wenden soll.

Ein Router muss so ein Ad nicht annehmen, wenn er nicht will – das kommt auf die policy an – will ich mit meinem AS routen oder nicht, will ich, das Leute durch meinen Garten trampeln (7-159)? Genauso muss ich auch nicht werben – wenn ich ISP bin muss ich Leuten, die nicht meine Kunden sind, auch nicht sagen, wohin ich routen könnte. Ein Router kann auch mehrere verfügbare Routen mitgeteilt bekommen – dann muss er sich entscheiden – wo kostets am wenigsten, wie weit ist der next-hop entfernt, womöglich hot potato.

Zusammenfassung

  • Welche Dienste muss das Netzwrk bieten?
  • Wie siehts in einem Router aus
  • Homer Simpson müffelt immer noch [Anm. von Homer J.: "Deine Oma....."] [Anm. von Bart S.: Ja, die müffelt noch mehr]
  • IPv4, IPv6
  • Routing in großen Netzwerken ist allein mit guten Routingalgorithmen nicht zu machen, wir brauchen dazu noch hierarchisches Routing
  • Internet Routingprotkolle – RIP, OSPF, BGP
  • Netzwerkstruktur muss auf die Adressenstruktur projiziert werden, sonst gibts zuviel Overhead (Adressraumvereschwendung)

Transport Layer

So, letzte Runde. Der Onkel erzählt euch jetzt was über die Transportschicht - also über Adressierung, Verbindungskontrolle, Flusskontrolle, Staukontrolle, UDP, TCP udn über Homer Simpsons Mutter.

Die Netzwerkschicht stellte logische Verbindungen zwischen 2 Hosts her – die Transportschicht stellt logische Verbindungen zwischen 2 Applikationen her. Dafür benötigt sie bestimmte Dienste. So muss sie zB die Nachrichten der Applikationsschicht in Segmente für die Netzwerkschicht zerlegen und diese natürlich auf Empfängerseite wieder zusammensetzen. So können mehrere Awnedungsprozesse gleichzeitig zwischen 2 Hosts kommunizieren.

Verschiedene Anwendungen haben verschiedene Transportprotokolle zur Auswahl, am populärsten sind wohl UDP und TCP. TCP ist verbindungsorientiert, hat Stau- und Flusskontrolle und die Daten kommen in richtiger Reihenfolge an. UDP hat nichts von alledem – verbindungsloser Datagrammdienst, keine Reihenfolge, best effort – nur ne kleine Erweiterung von IP.

Transportprotokolle sind nur in den Endsystemen implementiert – das Netzwerk weiß garnicht, was TCP ist. So kann man problemlos neue Transportprotkolle auf alten Netzwerken laufen lassen.

Adressierung und Multiplexing

Muss nun mehrere Anwendungen auf einem Rechner unterscheiden – dazu müssen diese mit dem Transportprotokoll kommunizieren können – das geht über einen SAP (=Socket). Darüber werden die Anwendungen, deren IP ja immer gleich ist (gleicher Host) über so genannte Portnummern unterschieden. Diese werden dynamisch vergeben, es gibt aber auch Festlegungen für bestimmte Sachen wie zB FTP (Port 21) oder HTTP (Port 80).

Multiplexing: Der Sender (Host) muss nun die Daten von vielen Sockets sammeln, Header generieren und diese an die Netzwerkschicht über eine Schnittstelle geben – also muss er die ganzen Daten multiplexen. Der Empfänger empfängt nun viele Pakete (IP Datagramme), die er der richtigen Anwendung an Hand des Ports, der im Paketheader steht, zuordnen muss – das ist Demultiplexing. Von welchem Port kommts (welche App sendet) und welchen Zielport hats (Ziel-App) – daher ist es wichtig, das zu jedem Zeitpunkt ein Port von genau einer Anwendung verwendet wird. Wozu muss der Empfänger die Quellportnummer iwssen? Für die Antwort! Denn wenn ich dem Sender antworte, muss auch der Sender diese Antwort dem richtigen Prozess zuordnen können.

Bei UDP (verbindungslos) wird ein Paket eindeutig mit seiner dest IP und seinem dest Port identifiziert. Daten von verschiedenen Sendern mit gleichem Ziel werden beliebig gemischt an den Zielprozess gegeben (Bsp: 8-11, einfach ^^).

Wenn wir verbindungsorientiert arbeiten, mit TCP zB, muss ich ja erst ne Verbindung aufbauen. Die Zuordnung wird aus dem 4-Tupel dest IP, dest port, source IP und source Port gewährleistet. Damit kann zB der Empfänger auch die richtige Reihenfolge rekonstruieren – und so können auch mehrere TCP-Sockets mit gleichem Port auf dem Webserver laufen, weil diese ja durch die Source IP bzw den Source Port unterschieden werden können. ZB tagesschau.de – der Server kann mehrere Verbindungen auf Port 80 gleichzeitig laufen haben. Genauso können natürlich auch, wenn 30 Rechner mit dem Server verbunden sind, 2 Rechner zufällig den gleichen Source Port senden – der Server unterscheidet sie dann an ihrer IP. Büld auf 8-14.

Verbindungskontrolle

Jetzt dreht sichs nur noch um verbindungsorientierte Dienste. Da gibt es 3 Phasen der Verbindung: Aufbau, Datenaustausch und Abbau. Für jede Phase gibt es verschiedene Diensprimitive. Auf Transportschichtebene halt T-Connect, T-Data, T-Disconnect, auf Netzwerkschichtebene halt N-Connect, N-Data, N-Disconnect. Das heißt auch, das eine Logische horizontale Kommunikation gleicher Schichten zwischen den einzelnen Hosts stattfindet, die natürlich physikalisch erst beim Sender durch alle Schichten runter geht und beim Empfänger wieder durch alle Schichten hoch – vertikal.

  • T-Connect

hat 4 Phasen: Request (Anfrage vom S), Indication (E merkt, Sender will was), Response (E antwortet S), Confirmation (S weiß, das E geantwortet hat). Schöne Grafik auf 8-19.

  • T-Data

Immer unbestätigt – Sender gibt Request, als Parameter die Nutzdaten. Empfänger erhält Indication und kann abweisen oder annehmen.

  • T-Disconnect

Bestätigt oder Unbestätigt möglich. Wenn ich abrupt abbaue, kann es sein, das einige Daten, die noch auf der Leitung sind, verloren gehen. Ich kann T-Disconnect auch benutzen, um eingehen Connection-Requests abzuweisen. Parameter: Grund, Transportinstanz hat keine Ressourcen mehr, Fehler, Nutzer hat keine Lust mehr, keine Antwort mehr von anderer Seite. Wenn einer der Nutzer abbricht, sendet er einen T-Disconnect-REQ und die Gegenseite bekommt einen T-Disconnect-IND. Wenn das Netzwerk abbricht, kriegen beide einen T-Disconnect-IND. Zustandsdiagramm auf 8-23.

Was passiert bei Fehlern? Wenn zB ein CR (Connection Request) verloren geht, brauch ich irgendwie einen Timeout-Mechanismus, damit ich mitkriege, das mein CR verloren ging. Wenn ich 2 CRs sende, weil die Antwort auf das erste CR so lange brauchte, das ich ungeduldig geworden bin, und ein zweites CR sendete, muss ich verhindern, das 2 Verbindungen aufgebaut werden.

Kompliziert wirds, wenn das CC (Confirmation) verloren geht – dann glaubt der, der das CC gesendet hat, es wäre angekommen und sendet schon Daten – der der das CR gekriegt hat und auf sein CC wartet, kriegt plötzlich Daten und weiß nich wieso – brauchen also noch ne Art ACK oder der CR-Sender schickt gleich Daten. (3-Wege-Handshake, 8-25). Wenn jetzt natürlich Duplikationen oder Verluste hat, brauch ich wieder Sequenznummern. Sender muss Frage beantworten, die Empfänger stellt. 8-25 und 8-26 angucken.

Möglich ist auch, das nach einem Disconnect-REQ nochmal ein Disconnect-Confirmation folgen kann, damit der, der das REQ sendete, weiß, das die Verbindung wirklich von beiden als abgebrochen erkannt wird.

Problem beim Verbindungsabbau: Wenn noch Daten unterwegs sind, können die verloren gehen – daher Verbindung geordnet abbauen. TCP akzeptiert einen Verbindungabbau nur, wenn alle gesendeten Daten durch ACKs bestätigt wurden. Also müssen beide Partner dem Abbau zustimmen – wenn ich mit Sebbl telefoniere, lege ich auch nicht einfach auf, wenn Sebbl grad labert – ich widerstehe dem Drang und haltes aus ^^. Das führt uns aber zum 2 Armeen-Problem, denn wie kann ich wissen, das mein Gesprächspartner weiß, das ich weiß, das er weiß, ... das wir uns nix merh zu sagen haben?

  • 2-Armeen-Problem: Eine Armee im Tal, die andere Armee geteilt, links und recht über dem Tal. Die obere, geteilte Armee ist nur erfolgreich, wenn beide gleichzeitg losstürmen. Um sich zu koordinieren, müssen sie Boten schicken – durch das Tal. Dort könne sie natürlich „verloren gehen“. Unmöglich.

Man löst das wieder mit einem 3-Wege-Handshake – einer sendet DR und startet nen Timer. Der andere sendet daraufhin auch ein DR und startet auch nen Timer. Wenn der eine dann das DR vom anderen empfangen hat, sendet er ein ACK. Kam das ACK beim anderen an, wir die Verbindung abgebaut. Was passieren kann, wenn da wieder was verloren geht, zeigt 8-33 anschaulich.

Flusskontrolle

Was passiert, wenn ein schneller Sender einen langsamen Empfänger überlastet? Daten gehen meist durch viel verschiedene Netze mit verschiedenen Kapazitäten und verschiedenen Lastsituationen. Nich jeder hat FeM, nich wahr Oli? *duck* Es gibt natürlich auch die Möglichkeit, das das Netz eigentlich schnell genug ist, aber der Empfänger ist zu lahm – seine Queue ist voll (kriegt grad viele Pakete) oder es ist Sebbls „Rechner“ (also ein arschlangsames Endsystem). Sein Puffer läuft über und Daten gehen verloren. Wie wenn Mutti immer mehr Kekse schickt, irgendwann kannsch die nimmer essen. Die Flusskontrolle muss das verhindern. Man kann da schon in der Link Layer ansetzen, geht aber auch in höheren Schichten. In der Transport-Schicht is das saukompliziert – das Netzwerk ist ja auch ein Speicher. Noch bevor ich Mutti sagen kann, da sich keine Kekse mehr will, hat die vll schon wieder welche abgeschickt – ich muss also mit meinem Puffer haushalten. Außerdem muss ich auf Transportschichtebene viele Anwendungen mit unterschiedlichen Paketlängen beobachten, das wird arg kompliziert. Je mehr Puffer ich als Empfänger hab, desto mehr Pakete kannsch aufnehmen. Wenn der Platz zuende geht, muss der E den S darauf hinweisen („ich hab noch so und so viel Platz“), S daraufhin seine Sendegeschwindigkeit drosseln. Der Sender kann aber auch Pufferplatz reservieren („ich brauch noch 4 kByte, dann binsch pferdsch“).

  • Einfachste Möglichkeit: E sagt „Stop“, wenner nich mehr kann. Wenns weiter gehen kann, sagt der E „Continue“. In der zeit, in der Stop-Signal unterwegs is, sendet der Sender noch fröhlich weiter, also rechtzeitig Stop sagen!
  • Implizite Flusskontrolle – wenn der E einfach keine ACKs verschickt, kann der Fluss auch stark gebremst werden – so wird die Fehlerkontrolle als Flusskontrolle vergewaltigt, der Sender kann nicht wissen obs Paket verloren ging oder ob der E einfach kein ACK gesendet hat.
  • Credit Based Flow Control: Dem Sender explizit sagen, wieviel ich gerade noch brauchen kann. Ich gebe dem Sender Kredit. Wenn S keinen Kredit mehr hat, musser warten bis ich ihm wieder welchen gebe. Da brauchsch natürlich wieder ne Fehlerkontrolle für die Kreditnachrichten. Alternativen: Absoluter Kredit: „hab noch Platz für 5 Pakete“ - Problem: Wenn Sender diese Nachricht erreicht, ist Zeit vergangen und ich hab vll nur noch Platz für 2 Pakete. Oder: Credit window (siehe Sliding window): Kredit relativ zu bestätigtem Paket geben: „Paket 1 bis 5 bekommen (ACK), akzeptiere noch 3 weitere (PERMIT)“. Bsp: 8-45/46 (Video!). Die 46 zeigt den Fall einer Blockierung (deadlock). Wenn ein ACK verloren geht, kann der Sender das Paket wiederholen. Geht ein Kredit verloren, tja... Pech.

Staukontrolle

Gegen die Überlast im Netzwerk. Heimnetzwerk mit 100 Mbit/s am DSL 2000 Anschluss – ich kann nicht mehr als 2 Mbit/s aus meinem 100 Mbit/s Netzwerk auf die DSL-Leitung geben, hier kommts also zu Stau im DSL-Router. Dann krieg ich nichmal die 2 Mbit durch, nein, die Rate sinkt sogar enorm, wenn Stau is. Und Sebbl knüpft sich dann das Seil, weil die Pornos nich mehr durch die Leitung kommen.

  • Szenario 1: 2 Sender, 2 Empfänger – beide senden mit maximal C/2 Kapazität durch einen idealen Router. Allerdings steigt das Delay exponentiell an – der Puffer hat unendliche Speicherkapazität, die zu bearbeitende Queue wird also immer länger und ein Paket, das kommt, braucht immer länger um durch den Router zu kommen.
  • Szenario 2: Unendlich großen Puffer durch endlichen Puffer ersetzen. Entweder ich sende nur, wenn Router noch Platz hat. Habsch ne recht hohe Rate. Wenn Überlast, gehen Daten verloren, die werden neu gesendet. Hier übertragen wir nur wirklich verloren gegangene Pakete neu – dann geht die Rate noch halbwegs. Real werden auch die Pakete neu übertragen, die n Timeout gekriegt haben – die aber noch leben und im Stau stehen. Das neu Übertragen dieser Pakete is natürlich dumm, die sind ja noch garnicht verloren. Dann bricht die Datenrate ein.
  • Szenario 3: 4 Sender, mehrere Router, Pfade über mehrere Hops, Neuübertragung bei Timeouts, also auch von Paketen, die noch garnicht verloren sind. Dann bricht der Output bei steigendem Input völlig weg und geht auf Null – alles steht weil fast alles weggeschmissen wird. Die Bandbreiteressourcen werden komplett für Pakete verbraten, die garnicht ankommen, weilse weggeworfen werden. Wie beim Mensch-Ärgere-Dich-Nicht, wenn das Hütchen erst kurz vorm Loch rausfliegt (hm da fallen mir perverse Sachen ein.... Egal).

Müssen wir also in den Griff kriegen, vor allem diese Schneeballeffekte: Netz überlastet > Daten gehen verloren > verlässliche Transportprotokolle schicken Daten nochmal > Stau wird schlimmer.

Wir machmer das? Wir passen die Senderaten der aktuellen Netzwerkkapazität an. Hängt also von allen Routern, sendern, Empfängern, deren Last etc ab – globales Problem (Flusskontrolle geht nur S und E was an, ist ein lokales Problem). Daher ist das schwierig zu handhaben, auch weil die verschiedenen Schichten untereinander ineragieren... An welcher Stelle klemmts denn gerade?

Wir wollen so viele Pakete wie möglich in möglichst kurzer Zeit ausliefern – dabei das Netzwerk aber nicht zum Kollaps bringen. Und alle fair an der Bandbreite beteiligen, wobei „fair“ nicht unbedingt „gleich“ heißen muss, denn ein Videostream braucht doch eine klein wenig höhere Bandbreite als zB ein IRC-Quiz mit einem zotteligen blauen Eggdrop. Da sich die Verbindungkosten aus Paketanzahl * Pfadlänge zusammensetzen, sind auch Knoten, die weiter weg vom Uplink sind, die Knoten, die mehr Traffic aufm Netz erzeugen. Staukontrolle kann mit 2 verschiedenen Mechanismusoptionen realisiert werden:

  • Open-Loop: Staukontrolle nur während des Systemdesigns, kann während nicht mehr verändert werden – Unterschieden wird hier, ob die Quelle den Stau bekämpft (zB Buffer schneller freischaufeln) oder der Sender (langsamer senden)
  • Closed-Loop: Während der Laufzeit wir über Feedbacks die Staukontrolle der Lastsituation angepasst – dabei gibt es 2 Möglichkeiten, die Feedbacks zu realisieren: Explizit, das heißt, das der Router oder Host, so sichs grad staut, den Sender explizit über diesen Stau informiert. Oder Implizit: Der Sender peilt das von selber, aufgrund der Verhaltensweise des Netzwerks, das Stau entstanden ist (zB durch fehlende ACKs)

Was kann man gegen Stau tun?

  • Netzkapazität erhöhen, mit zusätzlichen Routern, Links, etc. - geht natürlich nich schnell genug und is nich praktikabel ^^
  • Ressourcen reservieren – Leute müssen bei einem übergeordneten Entscheider anfragen, wieviel Ressourcen sie haben wollen und der entscheidet, ob die Ressourcen noch da sind und wer wieviel davon kriegt – Geht nicht bei Ringtopologien und gleichwertigen Netzen (kein übergeordneter Entscheider) und es gibt kaum Feedback aus dem Netzwerk, is nah an Open Loop.
  • Mehr ins Detail gehen – auch während einer bestehenden Verbindung überprüfen, ob genug Bandbreite noch da is oder nich – brauche umfangreiche Feedbacks während der Verbidnung, obsch zuviel reingebe oder halt nich – Closed Loop.

Wer soll agieren? Wer sammelt die Infos übers Netzwerk?

  • Router/Host: Es agieren die, wo die Daten durchlaufen, gesendet, empfangen werden
  • Fensterbasiert/Ratenbasiert: Wieviele Bytes/Fesnter darf ein Sender schicken?

Gibt noch mehr Möglichkeiten, zB Kreditbasiert, is aber nicht wirklich verbreitet.

Was kann der Router machen? Wenn der Buffer voll is, werden Pakete weggeschmissen – aber welche?

  • entweder das neu ankommende Paket, da die alten Pakete wichtiger sind (zB bei Go-Back-N, weil, wenn ein altes Paket nicht ankommt, alle neueren eh vom E verworfen werden) – das nennt sich dann drop-tail-queue.
  • oder alte Pakete, die schon lange in der Queue sind – die sind vielleicht eh schon zu spät dran (zB Sprache)

So oder so, wenn ein Paket verloren ist, ist das ein Feedback für den Nutzer – denn hauptsächlich gehen Pakete durch volle Puffer verloren, also is grad irgendwo Stau. Also wird die Last gesenkt. Das trifft zwar auf Kabelnetzwerke zu, aber keineswegs auf Wireless-Netzwerke. In Open-Loop-Staukontroll-Netzwerken sollte ein Pufferüberlauf eh nie passieren, sonst war die Ressourcenaufteilung miserabel.

Wie kann man vollen Puffern vorbeugen?

Is der Puffer einmal voll, isses eh zu spät. Also – Profilaxe! Bauen wir doch in den Puffer einen Schwellwert ein, einen „gelben Bereich“ - wird dieser überschritten, wirds langsam kritisch und man kann dann schon anfangen vorzubeugen, ohne das der Puffer sofort überläuft. Warning State! Wenn ein Router einmal im Warnzustand ist:

  • sendet er Drosselpakete an den Sender „ruuuuhig Brauner“ - aber in einem bereits überlasteten Netzwerk noch mehr Pakete zu erzeugen is auch nich grad schlau... Und – wann kriegt der Sender das denn mit? Kann ziemlich lange dauern...
  • packt in die ausgehenden Pakete ein Warning Bit, in der Hoffnung, der Empfänger sendet dieses Warning Bit in seinem ACK wider dem Sender und der Sender peilt, das im Netzwerk Stau is
  • fängt schonmal an, Pakete wegzuwerfen, dann fehlen dem Sender ja die ACKs dafür – das erspart vielleicht viel mehr Paketen später den Tod. Umso voller der Puffer wird, umso mehr Pakete werden gekillt. Nennt sich Random Early Detection.

Was macht der Sender, wenn er mitkriegt, das Stau ensteht / entstanden ist?

  • Rate senken, zB um konstanten Faktor – wie und wann aber wieder steigern?
  • congestion windows verkleinern – aber um wieviel? Wie dann wieder erhöhen?

Wird am Beispiel TCP genauer erläutert.

Transportprotokolle im Internet

UDP

Das User Datagram Protcol ist eine kleine Erweiterung des IP-Protkolls, ein verbindungsloser best effort Dienst. Pakete können verloren gehen und um die Reihenfolge kümmert sich gleich garkeiner – von Fehlerkontrolle oder gar Staukontrolle hat UDP auch noch nix gehört (keine Fehlerkontrolle, keine Neuübetragungen, keine Staukontrolle nötig). UDP wird zB bei Multimediastreams verwendet, wo ein paar verlorene Pakete nix ausmachen, aber sehr sensibel auf einbrechende Datenrate reagiert. Die Fehlerkontrolle wird dann dem Application Layer auferlegt. Im Header stehen Source- und Dest-Port, die Paketlänge und ne Checksum, dann kommen die Daten. (IP-Adressen stehen ja dann im IP-Header drin). Zur Checksum: Sender betrachtet Inhalt des Pakets als 16 Bit Ganzzahlen, addiert die alle auf und schreibt die Summe in das Checksummenfeld rein. Der E kann das also leicht checken.

Einer-Komplement: Übertrag der Summe aufs letzte Bit addieren, das Ergebnis dann invertieren.

TCP als Beispiel eines Transportschichtprotkolls

TCP arbeitet point-to-point, also von einem Sender zu einem Empfänger. Der Dienst ist ein verbindungsorientierter, verlässlicher, reihenfolgegetreuer Bytestrom, es ist pipelined (also die Fluss- und Staukontrolle legen die Fenstergröße fest). Beim Verbindungsaufbau gibts Handshakes, es fließen also Kontrollnachrichten, die die Einzelheiten der Verbindung abklären. MSS ist die maximale Segmentgröße – wie groß darf eine PDU maximal sein?

Im Header von TCP gibts die gewohnte Quellportnummer und Zielportnummer und – für den zuverlässigen Datentransfer – Sequenznummern. Es gibt drei wichtige Flags im Header: R (Reset), S (Syn) , F (Fin) – die deklarieren PDUs als Verbindungaufbau-PDUs. Recieve Windows gibt an, wieviele Bytes man noch empfangen will (ab dem zuletzt bestätigten Byte).

  • Sequenznummern:

TCP zählt keine Pakete sondern Bytes. Hat das erste Paket 100 Bytes, geht das zweite Paket mit Sequenznummer 101 weiter. Das ACK für das erste Paket bestätigt ja, was schon empfangen wurde – bei TCP sagt es aber auch noch, was erwartet wird. Auf das Paket mit 100 Bytes würde also ein ACK 101 folgen – Habe bis zu Byte 100 alles erhalten, schicke mir 101. Wenn ein ACK verloren geht, ist es daher kein Problem – kommt irgendwann ein ACK 103, schließt das das ACK101 mit ein (kumulativ). Als Sequenznummer eines Pakets dient immer die Nummer des ersten Bytes im Datenfeld. Einfaches Telnet-Beispiel auf 8-75.

Was passiert nun, wenn ein Datenpaket verloren geht? Werden die Pakete danach angenommen oder arbeitet TCP mit reinem Go-Back-N? Nicht spezifiziert, hängt von der Implementierung ab.

Zuverlässiger Datentransfer braucht natürlich Timeouts – nur so kann der Sender merken, das etwas verloren ging. Wie setze ich aber den Timeout-Wert? Eins ist klar – größer als die Roundtrip-Zeit auf jeden Fall, denn sonst übertrage ich das Paket schon neu, obwohl es noch unterwegs und noch garnicht verloren ist. Also auf jeden Fall größer als RTT. Aber auch nicht viel länger, sonst dauerts zu lang, bis das Paket neu gesendet wird. Nur – die RTT variiert im Netzwerk stark, denn ich hab ja point-to-point und gehe manchmal einen langen Weg zum Empfänger über viele Router mit vielen Warteschlangen, manchmal steht der Empfänger aber auch gleich neben mir. Ich muss die RTT also irgendwie samplen (messen) – und zwar mehrmals, das mussch dann mitteln, dann habsch nen akzeptablen Schätzwert (glätten):

EstimatedRTT_neu = (1 – a)*EstimatedRTT_alt + a*SampleRTT

mit beliebigen a, zB a=0,125. Um jetzt den Timeout-Wert zu erhalten, addieren wir halt noch eine Marge auf unsere EstimatedRTT drauf. Schwankt die RTT stark, will ich eien große Marge,s chwankt sie nicht, will ich möglichst nah an die RTT rankommen (kleine Marge). Das muss ich auch die Abweichung sampeln.

DevRTT_neu = (1 – ß)*DevRTT_alt + ß*|SampleRTT- EstimatedRTT|

mit zB ß = 0,25. Mein Timeout ergibt sich dann zu:

Timeout = EstimatedRTT + 4*DevRTT

Verbindungsmanagement

TCP-Verbindungen lassen sich in aktiv (will selber verbinden) und passiv (bin bereit, mit jemandem zu sprechen (listen)) gliedern.

  • Aktiver Modus: Man fordert eine TCP-Verbindung zu einem bestimmten Host (identifiziert durch IP und Port) an – zB im Web surfen
  • Passiver Modus: zB Webserver – der kommt ja nich, und sagt, „guck dir meine Webseiten an“ - der wartet bis ich von selber gucken will.

Eine Anwendung informiert TCP, das sie bereit ist, eine Verbindung einzugehen (entweder alles was kommt, oder auf einem bestimmten Socket). TCP-Verbindungen werden ohne weiteres Einmischen durch die Anwendung eingegangen, sowas wie T-Connect-Response gibbs hier nich. Es können mehrere Anwendungen auf dem gleichen Sender-Empfänger-Paar miteinander kommunizieren, sie werden durch ihre Port-Nr unterschieden – eine TCP-Verbindung wird eindeutig durch das 4-Tupel aus Dest-IP, Sorce-IP, Dest-Port und Source-Port – ein Webserver kann also mehrere Port 80 Connections offen haben, unterschieden werden diese eindeutig durch die Source-IPs der Hosts (weil ja 2 Hosts zufällig mit der gleichen Port-Nr auf den Webserver zugreifen könnten).

3-Wege-Handshake: Der Client sendet ein TCP-SYN, was die initiale Sequenznummer beinhaltet (keine Daten). Der Server antwortet mit einem SYNACK (mit seiner initialen Sequenznummer) und räumt schonmal auf – allockiert also Speicher. Oder, wenn der Server nich will, brichter hier sofort ab und der Ofen is aus. Der Client kriegt das SYNACK und antwortet wiederum mit einem ACK, welches bereits Daten enthalten kann.

Datentransfer mit Piggybagging, das heißt, Daten und ACKs in einem Paket.

Verbindung schließen: Der Client schließt die Sockets und sendet ein TCP-FIN – der Server sendet ein ACK zurück. Jetzt wird aber noch gewartet, bis der andere die Verbindung auch zumachen will – also bis der Server seinerseits ein FIN sendet. Der Client bestätigt dieses FIN mit einem ACK und geht in einen Wartezustand. Die Verbindung ist terminiert, wenn der Server das ACK erhält. Für den Fall, das ACKs oder FINs verloren gehn, gibts jeweils Timeouts. Warum so kompliziert? Damit Daten, die irgendwo im Netz rumgondeln, noch ankommen, bevor die Verbindung abbricht.

Büldsche und paar Diagramme auf 8-86 ff.

Verlässlicher Datenaustausch

TCP basiert auf dem unverlässlichen IP – muss also daraus was verlässliches zaubern. TCP versendet dazu mehrere Segmente gleichzeitig (Pipelining) und kumulative ACKs – haben also Go-Back-N. TCP verwendet nicht für jedes Paket einen Timeout, es kommt mit einem einzigen aus. Dieser Timer gibt an, wann das älteste, noch nicht bestätigte Paket überfällig ist. Läuft der Timer aus, wird eben dieses älteste, noch nicht bestätigte Paket nochmal gesendet und der Timer neu gesetzt. Aber nicht nur Timeouts lösen Retransmissions aus – auch, wenn der Empfänger immer wieder die gleichen ACKs sendet, weiß der Sender, das Pakete auf der Strecke geblieben sind. Also muss sich der Sender auch noch merken, was bereits vom E bestätigt wurde. Wenn der Timer neu gesetzt wird, dann haben natürlich die Pakete, die vor dem Neu-Setzen schon unterwegs waren, mehr Zeit. Beispiel: Timer = 1 Minute ist gerade ausgelaufen. Ein Paket ist bereits 40s unterwegs. Timer neu setzen, wieder auf 1 Minute – das Paket, das unterwegs ist, hat insgesamt 1:40 Minuten Zeit.

Wenn der Sender Daten von Anwendung empfängt, muss er daraus ein Paket bauen und dieses mit der Sequenznummer versehen, die der E erwartet. Die Sequenznummer ist die Nummer des ersten Bytes im Bytestrom. Wenn noch kein Timer läuft, wird über die Formel oben ein TimeOutInterval berechnet und der Timer gestartet.

Paar hübsche Bsp auf 8-94, wens interessiert, is aber billig.

Wenn der Empfänger nun Pakete mit Sequenznummern kriegt, die größer sidn, als die, die er erwartet, muss dazwischen wohl was verloren gegangen sein. Pures Go-Back-N schreibt vor, alle Pakete wegzuwerfen, die nach einem verlorenen Paket kommen. Das ist natürlich sinnlose Ressourcenverwschwendung. Bei TCP teilt der Empfänger dem Sender sofort mit, wenn er ein Paket mit höherer Seq-# gekriegt hat als die, die er erwartet, indem er ihm nochmal ein ACK schickt, wo er dem S sagt, was er als nächstes erwartet. So kriegt der Sender irgendwann 3 duplizierte ACKS und sieht daran, das was verloren gegangen ist – weiß aber auch, das nach dem Verlust nochwas angekommen ist. Kommt dann dass Paket irgendwann an, kann der Empfänger die bereits erhaltenen Pakete richtig zuordnen und die Lücke schließen – das allerdings muss auf Anwendungsebene implementiert werden. Das Neu-Senden nach duplizierten ACKs geht viel schneller, als wenn man auf den Timeout warten würde – Fast-Retransmit.

Flusskontrolle

Schneller Sender darf langsamen Empfänger nicht überlasten. Daher gibts Puffer beim E – aber auch beim S. Grafik auf 8-99 anschauen. Auf dem Bild gibts im E sogar ne Lücke, die erst wieder durch n Fast-Retransmit geschlossen werden muss. Der E muss also den Speicherplatz zwischen dem letzten Byte, das die Anwendung gelesen hat, und dem letzten Byte, das empfangen wurde, bereitstellen:

(NextByteExpected-1) -LastByteRead ist belegt.

FreeBuffer = Gesamtpuffergröße - (NextByteExpected-1) -LastByteRead.

Dies kann der E dem S auch mitteilen: „Du horsche ma du Ohrschloch, du gannsd mir nur noch so unn so viel Beids schiggn“ - das ist also die Größe des „Advertised Window“, mehr als dieses Advertised Window darf der S dann nicht ins Netz geben.

LastByteSent – LastByteAcked <= Advertised Window

TCP tritt sich durch ACKs selbst in den Arsch – wenn was durch ACKs bestätigt wird, ist ja anscheinend noch Platz im Netzwerk, da kann man noch was reingeben. Wenn das ACK aber nur für ein Byte war und ichsofort wieder sende – also auch nur ein Byte – dann is das dumm, weil ich ja jedes Byte in einen 40 Byte Header packe – sinnloser Overhead (silly window syndrome). Lieber noch ein bissel warten, paar Daten sammeln und dann erst schicken. Aber wieviel? Das beschreibt Nagle's Algorithmus. Der sagt im Prinzip nur aus, das man die Advertised Window – Größe voll ausnutzen sollte – aber nur wenn noch Daten unterwegs sind. Sender hält Daten nur im Puffer zurück, wenn noch unbestätigte Pakete unterwegs sind – wenn nicht, werden sofort kleine Pakete gesendet. Wenn ich per Telnet nämlich nur ein „Enter“ sende, käme das sonst nie an.

Staukontrolle

Schnelle Sender dürfen Netzwerk nicht überlasten. TCP erkennt an verlorenen Paketen (fehlenden ACKs), das es dem Netzwerk schlecht geht. Warum die Pakete weg sind, ist TCP wurscht, TCP macht generell Stau verantwortlich – egal obs wirklich der Stau oder zB ein Bitfehler im Paket oder auch ein übervorsichtiger Router (random early drop) war – oder wenn einfach das ACK verloren ging. Das ist auch nicht blöd – in verdrahteten Netzen kommen Bitfehler sooo selten vor, da liegt wirklich fast immer am Stau wenn ein Paket verloren geht. Im WLAN (oder an Sebbls Pentium 4) sieht die ganze Sache aber ganz anders aus. Das ACK dient also nicht nur als Bestätigung dafür, das beim E was ankam – es dient auch als Erlaubnis dafür, neue Daten ins Netzwerk reinzugeben – self-clocking-effect (TCP hält sich selber auf Trapp, tritt sich selber in Arsch).

Wenns zur Stauannahme kommt, wird eine fensterbasierte Staukonrollte gemacht, also mit congestion window. Also zusätzlich zur Begrenzung, die der Empfänger dem Sender auferlegt (Flusskontrolle) legt sich der Sender selber nochmal ne Beschränkung auf – nur soviel, wie wir glauben, das das Netzwerk noch verkraftet.

LastByteSent – LastByteAcked <= Congestion Window (zusätzlich immer Flusskontrolle: LastByteSent – LastByteAcked <= Advertised Window)

Wenn ein ACK zurückkommt, wollen wir gierig sein udn wollen etwas mehr haben – also die Congestion Window Größe erhöhen. Mal schauen ob das Netz das auch noch verkraftet.

Wenn das ACK ausbleibt, war sich wohl zu gierig - Congestion Window Größe senken – und zwar schnell und drastisch um 50% (wobei ein Minimum von einem Paket immer gesendet werden darf) – wir senken also multiplikativ. Das ist natürlich ne Überreaktion, wenns gar keinen Stau gab, sondern das Paket zB durch Bitfehler verloren ging. Wir müssen dann natürlich auch irgendwie wieder größer werden. Aber is der Stau auch wirklich schon weg? Lieber erstmal ein bissel erhöhen – nur additiv. Wenn alles in einer RTT ankam, sende ich in der nächsten RTT erstmal nur 1 Paket mehr – 8-107. Ich sende sogar schon während einer RTT immer ein bissel mehr für jedes ACK was ankommt – soviel, das ich nach einer RTT ein ganzes Paket mehr gesendet hab.

Increment = MSS * ( MSS / Congestion Window) mit MSS = maximale Segmentgröße

Das Ganze nennt sich AIMD – additiver increase, multiplikativer decrease. Solange additiv addieren, bis es einmal schiefgeht, dann bricht die Congestion Window Größe sofort ein – Sägezahn, 8-109. Das is aber noch vereinfacht – es gibt da noch was:

Bisherige Methode gut, wenn ich an der Kapazitätsgrenze arbeite – war ich zu gierig, kriege ich eins auf die Finger, aber ich taste mich wieder ran und bleibe immer in der Nähe der Kapazitätsgrenze. Aber – beginnt die Verbindung neu (kleines Congestion Window), dauert es durch das lahme Addieren eeeewig bis ich das Netz mal auslaste. Das muss beim Initialisieren der Verbindung schneller gehen, indem ich das Congestion Window jede RTT verdopple (= für jedes ACK ein Paket mehr senden) – ist also multiplikatives Increase (8-110). Das nennt sich Slow Start (obwohl es eigentlich schnell ist, der Name ist aber historisch begründet, es ist langsam im Vergleich zu anderen, gierigeren Verfahren). Damit hab ich natürlich schnell die Netzwerkkapazität erreicht, verursache ein Fehler, TCP halbiert das Congestion Window und ich bin wieder bei meinem AIMD-Sägezahn – also nix mehr mit multiplikativen increase, das gibts wirklich nur nach dem Verbindungsaufbau.

Es bleibt noch ein kleines Problem – Packet Bursts. Nehmen wir an, ich übertrage 8 Pakete und möchte für jedes ACK ein weiteres Paket senden. Nun gehen aber alle 8 ACKs verloren. Nach dem Timeout am Sender wird nochmal ein Paket gesendet, dafür kommt das ACK jetzt an. Aber – bei TCP sind ACK kumulativ, dh. alle bisher empfangenen Pakete werden bestätigt – die ganzen 8 auf einmal. Der Sender würde nun also sauviele Pakete auf einmal rausschicken – das ist ein Burst, der das Netz völlig überlasten kann (wenn das alle machen ^^). Das würden wir gerne glätten. Wir machen das bei Timeout also so: Wir reduzieren das Congestion Window auf 1 und machen wieder Slow Start – wie beim Verbindungsaufbau. Wir wissen auch noch unsere letzte Congestion Window Größe (bei der was schief ging) – bis zu deren Hälfte können wir uns aber problemlos rantasten (das ist der Congestion threashold). Also gibts bis dahin Slow Start, danach wir wieder additiv erhört (wie im normalen Betrieb). Exponentiell wachsen bis zum Congestion threashold, danach linear wachsen. Grafik auf 8-114. Das der Threashol aber immer aus der Hälfte der alten Congestion Window Größe bestimmt wird, kann es, bei vielen Timeouts, lange dauern, bis man den Threashold wieder angehoben hat – und daher dauert es lange, bis man wieder mit ordentlichem Durchsatz senden kann. URL eingeben – dauert ewig, nix passiert. Dann abbrechen, neu laden – auf einmal gehts sauschnell. Daran liegts.

  • Ist das Congestion Window unterm threashold, wird Slow Start angewandt.
  • Ist das Congestion Window überm threashold, wird linear erhöht.
  • wenn duplizierte ACKs auftreten: Fast Retransmit, Threashold wird zu Congestion Window/2 und Congestion Window wird zum (neuen) Threashold – so das kein Slow Start mehr angewandt wird – Grund: ein Paket verloren ist nicht so schlimm, das müssenwer nicht gleich radikal alles nierdermachen
  • wenn Timeout auftritt: Threashold wird zu Congestion Window/2 und Congestion Window wird zu 1 MSS

Performance

Welchen Durchsatz erzielt TCP denn noch trotz Fluss- und Staukontrolle (als Funktion der Fenstergröße W und RTT)? Wir ignorieren dafür erstmal Slow Start.

  • Durchsatz = W / RTT wenn keine Verluste auftreten. Nach Verlust: W := W/2, Durchsatz .= Durchsatz/2. Mittelwert: Durchsatz = 0,75 * W / RTT.
  • Fariness: TCP ist fair, jede Verbdinung kriegt die gleiche Bandbreite an einem Flaschenhals. Wenn eine Anwendung allerdings 9 TCP-Verbdinungen aufmacht, eine andere aber nur eine, bekommt natürlich die eine Anwendung auch 90% der Ressourcen. Das liegt aber nich wirklich an TCP sondern is die Schuld der Applikationsschicht ^^
  • Delay: Wie lange dauert es, bis ich ne Webseite aufm Rechner sehe?

Wir ignorieren dafür mal Datenverlust und Stau – Aber: Delay ist abhängig von Slow Start, Verbindungsaufbau udn vor allem der zeit, die die Daten durch das große Netzwerk wandern usw. Wir haben nen Link mit Datenrate R, S = MSS, O ist die Objektgröße. Das Zeusch am besten im Video angucken. 8-126 ff.

HTTP

  • nicht persistent: eine Verbindung pro Objekt (pro Bild, pro HTML-Seite etc.)
  • persistent: eine Verbindung für alle Objekte – Verbindungsaufbauzeit sparen
  • nicht persistentes HTTP mit X parallelen Verbindungen: brauchsch ja wohl nix zu sagen, nech?“

Zusammenfassung

  • Prinzipien hinter den Transportschichtdiensten: Adressierung, (De-)Multiplexing, Verbindungskontrolle, Flusskontrolle, Staukontrolle
  • Implementationen im Internet: UDP und TCP
  • TCP im Detail: die 3 wichtigen Kontrollfunktionen in einem sliding-window Protokoll vereint:

- Fehlerkontrolle (mit Sequenznummern, ACKs und Retransmissions) - Flusskontrolle - Staukontrolle (verlangsamen des Senders wenn Pakete / ACKs verloren gehen)

  • ich hab keine Lust mehr, es ist auch schon halb 12 – Feierabend, Bier off.

So liebe Kinder – Der Onkel hat euch jetzt also stundenlang vom Märchen der Postboten und keksebackenden Muttis erzählt. Jetzt ist der Onkel aber müde und möchte sich betrinken und sich dann vielleicht in einem Anfall von Depression am Audimax erhängen. Also geht ihr jetzt mal schön ins Bett während der Onkel schonmal die Pornozeitschrift rasuholt.

Klausur

Anmeldung

Zusätzlich zur Anmeldung an der Fak, muss noch eine eMail an die Klausurveranstalter geschickt werden. Zwecks Mateial- und Raumplanung. Nähere Infos gibts hier.

Material

Es darf nichts verwendet werden. Kein Script, keine Bücher, keine Aufzeichnungen.