26
(c) R. Wismüller, Univ. Siegen 2
Zusammenfassung: Protokollhierarchie
Schichten, Protokolle und Dienste
ISO-OSI Referenzmodell
7 Schichten: Bitübertragung, Sicherung, Vermittlung, Transport, Sitzung, Darstellung, Anwendung
Internet Protokollarchitektur
Netzwerk, IP, TCP/UDP, Anwendung
(Effiziente Implementierung von Protokollen)
(c) R. Wismüller, Univ. Siegen 3
3. Direktverbindungsnetze
(c) R. Wismüller, Univ. Siegen 4
3. Direktverbindungsnetze
Inhalt
Hardware-Bausteine: Knoten und Verbindungsleitungen
Modulation
Codierung
Framing
Fehlererkennung und Fehlerkorrektur
Peterson, Kap. 2.1 – 2.4
(c) R. Wismüller, Univ. Siegen 5
3.1. Hardwarebausteine
Netzwerkadapter: Bindegliedzwichen CPU/Speicher und Netzwerk-Link
OSI: 1
E/A Bus
zum Netzwerk
CPU
Speicher
Netzwerk-adapter
Cache
Aufbau eines Knotens
(c) R. Wismüller, Univ. Siegen 6
3.1. Hardwarebausteine …Verbindungs„leitungen”
Übertragen Signale als elektromagnetische WellenTypische Attribute:
Frequenz- bzw. Wellenlängenbereich (Bandbreite)Dämpfung (max. Kabellänge)Richtung des Datenflusses
• Simplex: nur in eine Richtung• Vollduplex: in beide Richtungen, gleichzeitig• Halbduplex: in beide Richtungen, abwechselnd
Grundlegende Arten:KupferkabelGlasfaserkabel (Lichtwellenleiter)Drahtlose Verbindung (Funk, IR)
(c) R. Wismüller, Univ. Siegen 7
3.1. Hardwarebausteine …
KupferkabelAufbau eines Koaxialkabels:
Hohe Bandbreite, geringe Dämpfung, teuerBasisband-Kabel (digitale Übertragung, 1 Kanal, <500m)
Beispiele: Ethernet 10Base5, 10Base2Breitband-Kabel (analoge Übertragung, mehrere Kanäle, mehrere km)
Beispiel: Fernsehkabel
(c) R. Wismüller, Univ. Siegen 8
3.1. Hardwarebausteine …
KupferkabelVerdrillte Kabel (Twisted Pair)
Geringe Kosten, relativ gute BandbreiteBeispiel: Ethernet 10BaseT, 100BaseT
geschirmt ungeschirmt
(c) R. Wismüller, Univ. Siegen 9
3.1. Hardwarebausteine …
Glasfaserkabel
Führung von Lichtwellen durch TotalreflexionBandbreite im Bereich Gb/s, Länge im Bereich km Varianten:
MultimodenfaserEinmodenfaser
• hohe Bandbreite, teuer (Laserdioden)
(c) R. Wismüller, Univ. Siegen 10
Zur Übertragung müssen Binärdaten in analoge elektrische Signale (Wellen) umgesetzt werden
Umsetzung in zwei Schritten:
Modulation:
Variation von Frequenz, Amplitude und/oder Phase einerWelleZur Überlagerung der (Träger-)Welle mit dem Nutzsignal
z.B. bei Funk, Modem, Breitbandkabel, …
Digital-signal
3.2. Modulation
Binär-daten
Analog-SignalKodierung Modulation
OSI: 1
(c) R. Wismüller, Univ. Siegen 11
3.2. Modulation …
Digitalsignal
Amplituden-modulation(AM)
Frequenz-modulation(FM)
Phasen-modulation(PM)
(c) R. Wismüller, Univ. Siegen 12
3.3. Codierung
Übertragung eines Bitstroms zwischen zwei Knoten:
Einfachste Codierung:
Non-Return to Zero (NRZ): “1” = high, “0” = low
Probleme:
Festlegung der Schwelle zwischen high und lowSynchronisation: “Grenze” zwischen zwei Bits?
Modulation/Demodulation
Signal
BitstromKnoten KnotenAdapter Adapter
OSI: 1
(c) R. Wismüller, Univ. Siegen 13
3.3. Codierung …
Abhilfe: Codierungen mit Taktwiederherstellung
Bits
Manchester
NRZI
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0
NRZ
Takt
NRZI: Non-Return to Zero Inverted
(c) R. Wismüller, Univ. Siegen 14
3.3. Codierung …
Manchester-CodierungBitstrom wird mit Taktsignal EXOR-verknüpftAnwendung z.B. bei 10 MBit EthernetProblem:
Baudrate (Rate, mit der sich das Signal ändert) ist doppelt so hoch wie die BitrateVerschwendet Bandbreite
NRZISignal wird bei jedem 1-Bit invertiertProblem: keine Taktwiederherstellung bei aufeinander-folgenden Nullen möglich
(c) R. Wismüller, Univ. Siegen 15
3.3. Codierung …
4B/5B-Codierung4 Datenbits werden auf 5-Bit Codeworte so abgebildet, daß nie mehr als 3 aufeinanderfolgende Nullen über-tragen werden müssen
jedes der 5-Bit Codeworte hat• höchstens eine Null am Anfang• höchstens zwei Nullen am Ende
Übertragung der Codeworte mit NRZIOverhead nur noch 20%
Bei schnellen Netzen (z.B. Fast Ethernet, GBit-Ethernet) oder auch schnellen Modems werden noch effizientere Codierungsverfahren eingesetzt
(c) R. Wismüller, Univ. Siegen 16
3.4. Framing
Wir betrachten nun die Übertragung von Datenblöcken (hier: Frames) zwischen Rechnern:
Zentrale Aufgabe:
Erkennung, wo ein Frame im Bitstrom anfängt und wo er aufhörtFramegrenzen müssen im Bitstrom erkennbar sein
OSI: 2
Frames
BitstromKnoten
AKnoten
BAdapter Adapter
(c) R. Wismüller, Univ. Siegen 17
3.4. Framing …
Byte-Count MethodeFrame-Header enthält Länge des DatenteilsBeispiel: Frame im DDCMP-Protokoll, DECNET:
Problem: was passiert, wenn Byte-Count fehlerhaft übertragen wird?
Frame-Ende wird nicht korrekt erkanntSYN-Zeichen am Beginn jedes Frames, um (wahr-scheinlichen!) Anfang der Folgeframes zu finden
Verwendet u.a. bei Ethernet
Header Body
8 8 4214 168
CRCCount
(c) R. Wismüller, Univ. Siegen 18
3.4. Framing …
Sentinel-MethodeFrame-Ende wird durch spezielles Zeichen markiertBeispiel: Frame im BISYNC-Protokoll (IBM):
Problem: Das ETX-Zeichen kann auch im Datenteil (Body) vorkommenLösung: Byte-Stuffing
Ersetze ETX im Datenteil durch DLE ETXErsetze DLE im Datenteil durch DLE DLE
Verwendet u.a. bei PPP
Header Body
8 8 8 8 168
CRCSTX
ETX
(c) R. Wismüller, Univ. Siegen 19
3.4. Framing …
Bit-StuffingWie bei Sentinel-Methode wird Frame-Ende markiert
hier aber durch spezielle BitzequenzEindeutigkeit durch Einfügen von Bits sichergestellt
Beispiel (HDLC-Protokoll):Anfangs- und Endesequenz ist 0 1 1 1 1 1 1 0nach 5 aufeinanderfolgenden 1-Bits wird vom Sender ein 0-Bit eingeschobenwenn Empfänger 5 aufeinanderfolgende 1-Bits gelesen hat:
• nächstes Bit = 0: ignorieren, da eingeschoben• nächstes Bit = 1: sollte Endemarkierung sein
(prüfe, ob die 0 folgt; falls nicht: Fehler)
(c) R. Wismüller, Univ. Siegen 20
3.4. Framing …
Taktbasiertes FramingBeispiel: SONET-Standard für optische Netzwerke
Frames haben feste Länge (810 Byte)Frame-Anfang mit speziellem Bitmuster markiertKein Bit- bzw. Byte-Stuffing: Bitmuster kann auch im Datenteil des Frames vorkommen
Wenn der Empfänger alle 810 Byte das Bitmuster findet, ist er korrekt synchronisiert …
Framing durch spezielle CodierungenAnfang und Ende durch Codeworte markiert, die sonst nicht vorkommen (z.B. bei 4B/5B-Codierung)
(c) R. Wismüller, Univ. Siegen 21
3.5. Fehlererkennung und –korrektur
Ziel: Übertragungsfehler in Frames erkennen bzw. korrigieren
Fehlerbehandlung kommt später (Kap. 3.7)
Vorgehensweise: Hinzufügen von Redundanzbits (Prüfbits)zu jedem Frame
Theoretischer Hintergrund: Hamming-DistanzHamming-Distanz d = Minimale Anzahl von Bits, in denen sich zwei Worte eines Codes unterscheidend ≥ f + 1 ⇒ f Einzelbitfehler erkennbard ≥ 2 f + 1 ⇒ f Einzelbitfehler korrigierbar
Beispiel: Paritätsbit führt zu d = 2
OSI: 2
(c) R. Wismüller, Univ. Siegen 22
3.5. Fehlererkennung und –korrektur …
Zweidimensionale ParitätErweiterung der einfachen ParitätBeispiel: 6 Worte á 7 BitErkennt alle 1, 2, 3 sowie die meisten 4-Bit-FehlerErlaubt auch die Korrektur von 1-Bit-Fehlern
1011110 1
1101001 0
0101001 1
1011111 0
0110100 1
0001110 1
1111011 0
Paritäts-bits
Paritäts-byte
Daten
(c) R. Wismüller, Univ. Siegen 23
3.5. Fehlererkennung und –korrektur …
CRC (Cyclic Redundancy Check)
Ziel: hohe Warscheinlichkeit der Fehlererkennung mit möglichst wenig PrüfbitsBasis des CRC-Verfahrens: Polynomdivision mit Modulo-2-Arithmetik (d.h. Add./Subtr. entspricht EXOR)Idee:
Jede Nachricht M kann als Polynom M(x) aufgefaßtwerden, z.B.
• M = 1 0 0 1 1 0 1 0 (Bits 7, 4, 3, 1 sind 1)• M(x) = x7 + x4 + x3 + x1
Wähle Generatorpolynom C(x) vom Grad kErweitere M um k Prüfbits zu Nachricht P, so daßP(x) ohne Rest durch C(x) teilbar ist
(c) R. Wismüller, Univ. Siegen 24
3.5. Fehlererkennung und –korrektur …
CRC …
Beispiel zur PolynomdivisionNachricht M: 100110103 PrüfbitsGenerator C: 1101
Divisionsrest R wird an die Nachricht M angefügtVersendete Nachricht P: 10011010101Diese Nachricht ist durch den Generator ohne Rest teilbar:
Generator
Nachricht;um 3 Bit erweitert
100110100001101
Rest1101101
1001
1000
1101
11011011110111001101
1000
R(x) = M(x) mod C(x) ⇒ (M(x) – R(x)) mod C(x) = 0
(c) R. Wismüller, Univ. Siegen 25
3.5. Fehlererkennung und –korrektur …
CRC …
Wahl des Generatorpolynoms?So, daß möglichst viele Fehler erkannt werden!Beispiel für ein übliches CRC-Polynom:
• CRC-16: x16 + x15 + x2 + 1CRC-16 erkennt:
• alle Ein- und Zweibitfehler• alle Fehler mit ungerader Bitanzahl• alle Fehlerbündel mit Länge ≤ 16 Bit
Gründe für den Einsatz von CRC:Gute Fehlererkennung Sehr effizient in Hardware realisierbar
(c) R. Wismüller, Univ. Siegen 26
Zusammenfassung
Hardware: Knoten, Leitungen (Kupfer, Glasfaser, Funk)
Codierung und Modulation
Umsetzen des Bitstroms in ein elektrisches SignalWichtig: Taktwiederherstellung
Framing:
Erkennung des Anfangs / Endes eines Datenblocks
Fehlererkennung und –korrektur
Nächste Vorlesung:Sicherung der Übertragung: Sliding Window ProtokolleMedienzugriffssteuerung (MAC), Ethernet
