Telematik 1: Unterschied zwischen den Versionen
JayKay (Diskussion | Beiträge) |
JayKay (Diskussion | Beiträge) |
||
Zeile 312: | Zeile 312: | ||
*'''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. | *'''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) | + | *'''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,d ie Leitung bleibt lange unnutzbar für Daten. (4-61). |
− | 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,d ie Leitung bleibt lange unnutzbar für Daten. (4-61). | ||
Zeile 328: | Zeile 327: | ||
Zu Effizienz der Geschichten bitte mal die paar Seiten ab 04-70 lesen, das sind Grafiken und Formeln, da habsch jetzt keen Bock... | 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 | *Am meisten hat die LL mit Fehlern zu tun – entweder bei der Synchronisation (in Rahmen packen) oder bei der Übertragung (Fehlererkennung/-Reparatur |
Version vom 29. Juni 2006, 12:53 Uhr
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 wirftse 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
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 macht den Porno aus und nimmt das Telefon ab - RES
4.Sebbl meldet sich am Telefon mit erotischer stimme – CONF
Übertragung über das Netz
2 Möglichkeiten:
- als wohl-abgegrenzte Pakete (so machts UDP)
- als Bytestrom, den der Empfänger dann auseinanderfuddeln muss (so machts TCP)
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 Herrn Jägers 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 Schichten 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 aknn schnell riesige Netze errichten. Die intelligenten, teuren Endsystem bügelt 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. Ind er 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 kopperieren – 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 weite,r 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 0en und 1en halt) - kann man Fourier-transformieren, wenn man annimmt, sie wiederholen sich unendlich hofft –> 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 geht 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 euch 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 ie 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. Synchronisation zwischen Sender und Empfänger 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
- 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 hat 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 Herrn Jäger 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 auftauacht, 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?
- soll LL die Fehler nur erkennen oder auch reparieren? beides, 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 mus 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. Ach 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 Interpration des Bitstroms als Polynom – das i-te Bit ist Koeffizient der i-ten Potenz. 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. Weill man an einen Bitstring hinten k Nullen an hängen 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) 2. Dann teilen wir x^g * M(x) durch G8x) 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 – nenne 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 duuu!).
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,d ie 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).
- Piggybagging: 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
- Vermögensaufbau 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
Klausur
Anmeldung
Zusätzlich zur Anmeldung an der Fak, muss noch eine eMail an die Klausurveranstalter geschickt werden. Zwecks Mateial- und Raumplanung. (Addresse ict noch nicht bekannt, wird aus der Telemati News stehen).
Material
Es darf nichts verwendet werden. Kein Script, keine Bücher, keine Aufzeichnungen.