Datenkommunikation II
Teil 2:Das OSI-Referenzmodell
Die OSI-Schichten
1 - Bitübertragungsschicht• Aktivierung und Deaktivierung einer physikalischen Verbindung• Übertragung der Rohdaten über einen Kommunikationskanal• Garantierte Einhaltung der Bit-Reihenfolge
2 - Sicherungsschicht• gesicherte Übertragung von Daten zwischen Rechnern• Fehlersicherung, Flußkontrolle• Medium Access Control3 - Vermittlungsschicht• Aufbau, Abbau und Betrieb von Verbindungen• Adressierung und Routing
4 - Transportschicht• netzunabhängige, sichere Ende-zu-Ende-Kommunikation• Fehlererkennung und -behebung• Multiplexing von Verbindungen
5 - Sitzungsschicht• Steuerung und Synchronisation von Dialogen
6 - Darstellungsschicht• Festlegung einer gemeinsamen Syntax• Datenkomprimierung• Verschlüsselung
7 - Anwendungsschicht• Vielzahl von Netzinformationsdiensten:
• Filetransfer• eMail• Jobtransfer• ...
Die OSI-Schichten
Festlegung der Parameter einer Verbindung→ mechanische→ elektrische und elektronische→ funktionale und prozedurale
Genauer gesagt:→ Stecker, Leitungen, ...→ wie werden die Bits dargestellt (Leitungscode, Spannung, etc.)→ Übertragungsrate→ Steuerung des Bitaustausches→ bitserielle oder bitparallele Übertragung→ synchrone oder asynchrone Übertragung→ simplex-, halbduplex- oder vollduplex-Verbindung
Es gibt keine ISO „Physical Layer Protocol Specification“!
Schicht 1
Codierung der Informationen
Codierungsvarianten:
• Quellcodierung
• Leitungscodierung
• Kanalcodierung
Umwandlung analoger in digitale Signale→ Sprachcodierung:
1. Abtastung der analogen Signale2. Amplitudenquantisierung der Abtastwerte3. Codierung der quantisierten Abtastwerte
Abtasttheorem (Nyquist):Abtastrate ≥ 2 * Grenzfrequenz des UrsprungssignalsTelefon Grenzfrequenz 3,4 kHz ! Abtastrate 8000 Hz
Zweck: sinnvolle Darstellung der zu übertragenden Information
Physikalische Darstellung von DigitalsignalenDarstellung der zu übertragenden Daten in Codewörtern, die den Eigenschaften des Übertragungs-kanals angepaßt sind (Redundanz).→ Sicherung gegen Übertragungs-
fehler durch fehlererkennende bzw. -korrigierende Codes
Leitungscodierung
Kanalcodierung
Quellcodierung
Information
Leitungscodierung
Kanalcodierung
Quellcodierung
Information
Sender Empfänger
physikalischeÜbertragung
Effektiver: ADPCM• Adaptive Differential PCM• nicht der absolute Abtastwert
wird codiert, sondern die Differenz zum vorherigen Wert
⇒ weniger Bits pro Abtastung(Anwendung z.B. im Mobilfunk)
Pulscodemodulation ( PCM ) + 4 + 3
+ 2 + 1 - 1
- 2 - 3 - 4
Qua
ntis
ieru
ngsb
erei
ch
Intervall-nummer
Binär-code
111
110
101
100
000
001
010
011
Zeit Abtast-zeitpunkte
T
Pulscode
Ursprungssignal rekonstruiertes Signal
Abtastfehler
1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1
Quellcodierung: PCM
Leitungscodes
Wie sollen digitale Signale elektrische repräsentiert werden?
Anforderungen
• Möglichst hohe Widerstandsfähigkeit gegen Dämpfung
• Effizienz: möglichst hohe Übertragungsraten durch Codewörter
binärer Code: +5V / 0V ? 1 Bit
ternärer Code: +5 V / 0V / -5V ?
quaternärer Code: 4 Zustände 2 Bit
• Gleichstromfreiheit
• positive und negative Signale treten ungefähr gleich oft auf
• Taktrückgewinnung beim Empfänger (Synchronisation)
Information Information+
Pseudo-Zufallsfolge
+Sender Empfänger
Pseudozufallsfolge
„0“ und „1“ gleich häufig
Sender und Empfänger vereinbaren
• Ein Verfahren
• Einen Startwert x0
• Zwei Konstanten a und b
Erzeugen von Pseudozufallszahlen z.B. wie folgt: x0 Startwert
xi+1:= a* xi +b mod 2
NRZ: Non-Return-to-Zero
Codierung: 0 ⇒ 0V1 ⇒ +5V
Besser ist also: 0 ⇒ -5V1 ⇒ +5V
0 1 0 1 0 1 0 1 0 1 0 1 0
Eigenschaft: (bei langen Folgen gleicher Signale)• keine Gleichstromfreiheit• keine Taktrückgewinnung
(dies schafft Gleichstromfreiheit, falls 0 und 1 im Mittel gleich häufig auftreten)
sonst: Scrambling
Differential-NRZ- & RZ-Code
Differential-NRZ-Code0 ⇒ kein Polaritätswechsel1 ⇒ Polaritätswechsel
Nachteile:• keine Gleichstromfreiheit und Taktrückgewinnung bei 0-Folgen
RZ-Code0 ⇒ 0V1 ⇒ Wechsel von +5V nach 0V
Nachteile hier:• doppelte Taktrate (in der Taktmitte Flankenwechsel)
⌫ es wird nur die Hälfte der Übertragungskapazität genutzt(50% Effizienz)
• keine Gleichstromfreiheit• Taktrückgewinnung nur bei "1"en
AMI-Code (Alternate Mark Inversion)
Ternärer Code mit Codeelementen +, 0, -0 ⇒ 01 ⇒ alternierend + / - (in Abhängigkeit von der Darstellung der letzten “1”)
Vorteile• Gleichstromfreiheit• Taktübertragung bei "1"-Folgen
Nachteile• keine Taktübertragung bei "0"-Folgen• ternäre Symbole (d.h. Nutzung der Übertragungskapazität zu 2/3)
Zur automatischen Synchronisierung wird bei jedem Codeelement der Takt mit übertragen. Grundlage ist der RZ-Code (Polaritätswechsel in der Mitte des Codeelements)
0 ⇒ +/-
1 ⇒ -/+
Vorteile• vollständig selbsttaktend und gleichstromfrei• Ende der Übertragung leicht erkennbar
Nachteil• Kapazität wird nur zur Hälfte genutzt
Einsatz• Die Manchester-Codierung wird bei Ethernet eingesetzt
„hoch“ +5 Volt
„niedrig“ -5 Volt
„niedrig“ -5 Volt
„hoch“ +5 Volt
Manchester-Code
Neben dem garantierten Flankenwechsel in der Mitte des Codeelements findet genau dann zu Beginn des Codeelements ein Flankenwechsel statt, wenn eine Null übertragen werden soll.
0 ⇒ Polaritätswechsel am Anfang des Signalelements1 ⇒ kein Polaritätswechsel am Anfang
Vorteile:• Gleichstromfreiheit• vollständig selbsttaktend• Ende der Übertragung leicht erkennbar
Nachteil:• Die Kapazität wird nur zur Hälfte genutzt
0 0 0
1 1 1
Differential-Manchester-Code
5V
0VNRZ
0 1 0 1 1 0 0 1
5V
0V
Diff.NRZ
5V
0VRZ
+5V
0V
-5V
AMI
Codeverletzung
z.B. zur Rahmenerkennung
Beispiele für Leitungscodes
0 1 0 1 1 0 0 1
+5V
0V
-5V
Diff.
Man-chester
Codeverletzung
z.B. zur Rahmenerkennung
Man-chester
+5V
0V
-5V
Beispiele für Leitungscodes
Nachteil des Manchester-Codes:→ 50% Effizienz, d.h. 1B/2B- Code (ein Bit auf zwei Bit)
Eine Verbesserung stellt der 4B/5B-Code dar:
→ vier Bit werden in fünf Bit kodiert: 80% Effizienz→ z.B. bei FDDI (Fiber Distributed Data Interface, 100 Mb/s
Hochleistungsring)
Arbeitsweise:→ Pegelwechsel bei 1, kein Pegelwechsel bei 0→ Kodierung von hexadezimalen Zeichen: 0, 1, ..., 9, A, B, ..., F (4 Bit)
in 5 Bit, so daß lange Nullenblöcke vermieden werden.→ Auswahl der günstigsten 16 der möglichen 32 Codewörter
(maximal 3 Nullen in Folge)→ Weitere 5 Bit-Kombinationen für Steuerinformationen→ Erweiterbar auf 1000B/1001B-Codes?
4B/5B-Code
D e c im a l D a ta T ra n sm itte d S ym b o l A ss ig n m e n t
0 0 0 0 0 0 0 0 0 0 Q u ie t -lin e s ta te (s ta tu s )1 0 0 0 1 0 0 0 0 1 In va lid2 0 0 1 0 0 0 0 1 0 In va lid3 0 0 1 1 0 0 0 1 1 In va lid4 0 1 0 0 0 0 1 0 0 H a lt -lin e s ta te (s ta tu s )5 0 1 0 1 0 0 1 0 1 In va lid6 0 1 1 0 0 0 1 1 0 In va lid7 0 1 1 1 0 0 1 1 1 R -R e se t ( lo g ic a l 0 )-co n tro l (c o n tro l)8 1 0 0 0 0 1 0 0 0 In va lid9 1 0 0 1 0 1 0 0 1 D a ta
1 0 1 0 1 0 0 1 0 1 0 D a ta1 1 1 0 1 1 0 1 0 1 1 D a ta1 2 1 1 0 0 0 1 1 0 0 In va lid1 3 1 1 0 1 0 1 1 0 1 T -E n d in g d e lim ite r (co n tro l)1 4 1 1 1 0 0 1 1 1 0 D a ta1 5 1 1 1 1 0 1 1 1 1 D a ta1 6 1 0 0 0 0 In va lid1 7 1 0 0 0 1 K -s ta rtin g d e lim ite r (co n tro l)1 8 1 0 0 1 0 D a ta1 9 1 0 0 1 1 D a ta2 0 1 0 1 0 0 D a ta2 1 1 0 1 0 1 D a ta2 2 1 0 1 1 0 D a ta2 3 1 0 1 1 1 D a ta2 4 1 1 0 0 0 J -s ta rtin g d e lim ite r (co n tro l)2 5 1 1 0 0 1 S - se t (lo g ica l 1 ) - c o n tro l (co n tro l)2 6 1 1 0 1 0 D a ta2 7 1 1 0 1 1 D a ta2 8 1 1 1 0 0 D a ta2 9 1 1 1 0 1 D a ta3 0 1 1 1 1 0 D a ta3 1 1 1 1 1 1 Id le -lin e s ta te (s ta tu s )
Worst case: 11100|01110
3Nullen
4B/5B-Codetabelle (FDDI)
Synchrone und asynchrone Übertragung
Synchrone Übertragung• fester (gleicher) Zeittakt bei Sender und Empfänger• Synchronisierung zu Beginn eines Blocks• eindeutige Anfangs- und Endflaggen (bestimmte Bitmuster)• Taktübertragung durch separate Taktleitung oder selbsttaktenden Code
Vorteile: + effizient, höhere Übertragungsraten sind möglichNachteil: – aufwendig
Synchronisation zwischen Sender und Empfänger zur Erkennung von Bits, Bytes, Worten, ...
Asynchrone Übertragung• kein gemeinsamer Zeittakt zwischen Sender und Empfänger• Synchronisierung durch Startbit, Stoppbit(s)
Nachteile: – Synchronisierung nur für wenige Bits– maximale Datenrate gering (Verlust an Übertragungskapazität)– Abstand zwischen Bytes beliebig
Vorteile: + einfach+ Abstand zwischen Zeichen beliebig
Betriebsarten: simplex, halbduplex & vollduplex
Simplex• Übertragung nur in eine Richtung• Verteilung von Informationen (Rundfunk, Fernsehen)• In der Datenkommunikation unüblich
Halbduplex• Bidirektional betreibbares Übertragungsmedium• Übertragung der Kommunikationspartner erfolgt wechselseitig• Kommunikationspartner müssen sich einigen, wer senden darf
Vollduplex• zeitgleiche Übertragung in beide Richtungen• realisierbar durch:
• zwei Leitungen• eine Leitung mit zwei Kanälen• gleichzeitiges Senden mit Filterung
S E
Sendeeinrichtung Empfangseinrichtung
Leitung
E
E
S
S
S E
SE
‚eingleisige Bahnstrecke‘
Schicht 2
• Logical Link Control (Schicht 2b)→ Einteilung der zu sendenden Daten in Rahmen (Frames)→ Bereitstellung einer (möglichst) fehlerfreien Übertragung
zwischen benachbarten Knoten (Dienst für Schicht 3) durch:→ Erkennung (und Behebung) von Übertragungsfehlern
(fehlererkennende und -korrigierende Codes)→ Flußkontrolle→ Pufferspeicher
• Medium Access Control (Schicht 2a)→ Regelung des Zugriffs auf den Kommunikationskanal
(nicht nötig bei Broadcast-Netzen)
Sicherungsschicht: teilt sich in zwei Aufgabenbereiche
Schicht 2
Logical Link Control
Rahmenerstellung
• Einteilung einer Nachricht in Einheiten (einfachere Übertragung)
• Kennzeichnung der Einheiten:
Header TrailerDaten
Kontrollinformationen (Adressen, Rahmennummern, ...)
Fehlerprüfung(Prüfsumme zum Rahmen)
(physikalische) Kennzeichnung des Rahmens durch:
• Anfangs- und Endflaggen
• Anfangsflagge und Länge
• Codeverletzungen
Nächste Aufgabe:
Erkennung und Korrektur
von Übertragungsfehlern
FCS = Frame Check Sequence
Fehlererkennende und -korrigierende Codes
Parity BitZählt die Anzahl der ‘1‘enSender: 10 111 001 PB: 1Empfänger: 00 101 000 PB: 0
FehlerkorrekturÜbertragung von Redundanzen:
• Länge der Übertragung n Bit (2n mögliche Binärfolgen)• Nachrichtenlänge m (<n) Bit (2m zulässige Codewörter)• k Prüfbits (k = n - m)
• Lege um jede Nachricht eine „Sphäre“ von Codewörtern• Hammingabstand d:
Anzahl der Stellen, an denen sich zwei Wörter unterscheiden
• Dann: d ≥ 2 t + 1 ⇒ Code ist t-Fehler-korrigierendd ≥ 2 t ⇒ Code ist t-Fehler-erkennend
1-Bit Fehler werden erkannt
2-Bit Fehler werden nicht erkannt
Korrekturen sind nicht möglich!
Variante: Längs- und Querparität
Hamming-Code
"Minimaler" Code
Idee: Eindeutige Darstellung jeder natürlichen Zahldurch Summe von 2er-Potenzen
In einem Codewortw = z1, . . . , zn
stehen die Prüfbits genau an den k Positionen, deren Index eine 2er-Potenz ist, an den restlichen m = n-k Positionen stehen die Datenbits.
Jedes Prüfbit ist ein Paritätsbit für alle Stellen, deren Darstellung gerade die Position des Prüfbits enthält.
Beispiel
ASCII Codewort
C 1100011 11111000011
O 1101111 10101011111
D 1100100 11111001100
E 1100101 00111000101
11 = 1 + 2 +8
Prüfstelle 2 prüft Datenbits 3, 6, 7, 10, 11
Empfänger:
• überprüft Paritätsbits
• addiert ggfls. Indizes der fehlerhaften Prüfstellen
→→→→ Index des fehlerhaften Datenbits
→→→→ 1-Bit-Fehler können eindeutig identifiziert und korrigiert werden
(m=7)
Bits 1,2, 4, 8 sind Redundanzbits
Hamming-Code
(n=11, k=4)
ASCII CodewordH 1001000A 1100001M 1101101M 1101101I 1101001N 1101110G 1100111
1 2 3 4 5 6 7 8 9 10 11
0 0 1 1 0 0 1 0 0 0 0
1 0 1 1 1 0 0 1 0 0 1
1 1 1 0 1 0 1 0 1 0 1
1 1 1 0 1 0 1 0 1 0 1
Prüfbit 1 : Datenbits 3, 5, 7, 9, 11 3 = 1 + 2
Prüfbit 2 : Datenbits 3, 6, 7, 10, 11 5 = 1 + 4
Prüfbit 4 : Datenbits 5, 6, 7 6 = 2 + 4
Prüfbit 8 : Datenbits 9, 10, 11 7 = 1 + 2 +4
9 = 1 + 8
10 = 2 + 8
11 = 1 + 2 + 8
Problem bei Hamming-Code: Mehrbitfehler werden in der Regel falsch korrigiert
Hamming-Code
Schwächen:• 2-Bit-Fehler werden nicht korrigiert (oder falsch korrigiert!)• 3-Bit-Fehler werden nicht erkannt• ...
a) Bit 4 und Bit 11 invertiert→→→→ Prüfbits 1, 2, 4, 8 falsch→→→→ Bit 15 soll korrigiert werden, existiert nicht
b) Bit 2 und Bit 4 invertiert→→→→ Prüfbits 2, 4 falsch→→→→ Bit 6 wird fälschlicherweise als inkorrekt erkannt
c) Bits 1, 8, 9 invertiert→→→→ alle Prüfbits korrekt→→→→ kein Fehler wird erkannt
Hamming-Code
Beispiel:1100101x6......x1x0
=x6+ x5 +x2+1
Fehlererkennung mit zyklischen Codes
Ein Code heisst zyklisch, wenn mit jedem Codewort auch das zyklisch (links oder rechts) geshiftete Wort wieder ein Codewort ist.
Beispiel: Ist 1011010 ein Codewort, dann auch 0101101, 1010110, usw.
Idee: Sender und Empfänger vereinbaren ein Generatorpolynom G(x).
Der Sender interpretiert einen Datenblock als Polynom und ergänzt ihn mit Hilfe von G(x) um "redundante" Bits.(Redundanz = Rest bei Division der Zeichenfolge durch G(x))
Der Empfänger erhält bei korrekter Übertragung nach der Division durch G(x) den Rest 0
CRC: Cyclic Redundancy Checksum
B e i s p i e l :z u ü b e r t r a g e n : 1 0 1 1 1 0 0 1
G e n e r a t o r p o l y n o m : x 4 + x + 1
1 0 1 1 1 0 0 1 | 0 0 0 0 : 1 0 0 1 1 = 1 0 1 0 0 1 1 11 0 0 1 1
1 0 0 0 01 0 0 1 1
1 1 1 0 01 0 0 1 1
1 1 1 1 01 0 0 1 1
1 1 0 1 01 0 0 1 1
1 0 0 1 R ( x ) = x 3 + 1 C R C : 1 0 0 1
1 0 1 1 1 0 0 1 | 1 0 0 1 : 1 0 0 1 1 = 1 0 1 0 0 1 1 11 0 0 1 1
1 0 0 0 01 0 0 1 1
1 1 1 1 01 0 0 1 1
1 1 0 1 01 0 0 1 1
1 0 0 1 11 0 0 1 1
0 ⇒ Ü b e r t r a g m a l k o r r e k t
Fehlererkennung mit zyklischen Codes
Sender
Empfänger
10111001| 1001↑ ↑ ↑ Fehlermuster↑ ↑ ↑ Fehlermuster
AEmpfänger:
00101001| 0001 : 10011 = 0010111010011
11110100111101010011
1001010011
11 ⇒ Übertragungsfehler
A
B
Fehlererkennung mit zyklischen Codes
BEmpfänger:
00111011|0001 : 10011 = 0011111110011
1110110011
1110010011
111101001111010100111001110011
0 ⇒ Übertragungsfehler nicht erkannt!
Fehlererkennung mit zyklischen Codes
CRC: Fehlererkennung
Gebräuchliche 16-Bit-Generatorpolynome:CRC-16 G(x) = x16 + x15 + x2 +1CRC-CCITT G(x) = x16 + x12 + x5 +1Ethernet: 32-Bit-Generatorpolynom
Fehlererkennung:• alle Einzelbitfehler• alle Doppelbitfehler• alle Dreibitfehler• alle Fehlermuster mit ungerader Bitfehleranzahl• alle Fehlerbüschel mit 16 oder weniger Bits• 99,997% aller 17-Bit-Fehlerbüschel• 99,998% aller Fehlerbüschel mit Länge ≥ 18 Bit• Restfehlerrate < 0,5* 10-5 Blockfehlerrate (ursprünglich)
CRC: Fehlerkorrektur
In Ausnahmefällen sind durch CRC Fehler korrigierbar.Beispiel: ATM (Asynchroner Transfer Mode)
• Nachrichtenslots fester Länge • 5 Byte Header + 48 Byte "Daten"• davon das letzte als Checksum für den Header• Generatorpolynom G(x) = x8 + x2 + x +1
⇒ Damit ist ein 1-Bit-Fehler sogar korrigierbar, denn:es gibt 40 mögliche Ein-Bit Fehler und die führen auf 40 Nicht-Null-Reste.
Korrektur wird nicht eingesetzt bei• HDLC (16-Bit-Polynom)• Ethernet (32-Bit-Polynom)Grund: zu viele Fehlermöglichkeiten:Ein Ethernetpaket hat eine Länge zwischen 64 und 1512 Byte.
Fehlersicherung bei Protokollen
Unterscheidung zwischen Fehlerkorrektur und -erkennung
Fehlererkennung: ARQ (Automatic Repeat Request)• Einführung einer Flußkontrolle• Nummerierung der zu sendenden Blöcke• FCS hinzufügen• Quittierung von Blöcken• Wiederholung fehlerhaft übertragener Blöcke• sehr sicher, nicht absolut sicher, denn Quittungenkönnen verloren gehen.
Fehlerkorrektur: FEC (Forward Error Correction)• Verwendung fehlerkorrigierender Codes• Feedback vom Empfänger zum Sender ist nicht erforderlich
Sender
Empfänger
1
1
2
F
2
2
3
3
N
ACK ACK
Tim
e-ou
t
Der Sender überträgt einen Datenblock und wartet,bis eine Quittung eintrifft oder ein Time-Out eintritt
Bei fehlerhaftem Block erfolgt eine Wiederholung,sonst wird der nächste Block gesendet
Nachteil: große Idle-Zeiten
Send-and-Wait
ACK: Acknowledgement, d.h. ‚alles ok‘
Isarithmische (gleichzahlige) Flußkontrolle
• Gesamtes Netz erhält n „Credits“ (Token)• Nachricht darf Netz nur betreten, wenn ein Credit verfügbar ist• Nach Ankunft wird Credit wieder freigegeben
Globale Überlastung wird verhindert
Creditverluste sind schwer feststellbar / behebbar
lokale Überlastungen sind trotzdem möglich
Credits sind manchmal an der falscher Stelle (Analogie: Taxen im Stadtgebiet)
Flußkontrollmechanismen
Fenstersteuerung (Window Mechanism)• Verbindung zwischen Quelle Q und Ziel Z erhält maximal W Senderechte
W=Fenstergröße.• Nachrichten werden fortlaufend nummeriert (0, 1, 2, ..., MODULUS-1, 0, ...);
(wobei W < Modulus).• Sender darf bis zu W fortlaufend nummerierte Nachrichten verschicken,
ohne eine Quittung für die erste erhalten zu haben.• Empfänger bestätigt durch Quittungen (ACK).• Sender rückt Fenster vor, sobald ACK eintrifft.
Nachrichten und ACKs können verloren gehen, unerkennbarsein oder zu spät kommen
Sende- und Empfangsgeschwindigkeit werden angepaßt
zu schnelle Sender werden gebremst
Flußkontrollmechanismen
Fenstermechanismus: Go-Back-N
Der Sender überträgt kontinuierlich Datenblöcke. Der Empfänger antwortet:
• ACKj: alles bis Block j ist in Ordnung
• REJj/NACKj: bis Block j-1 ist alles in Ordnung, Block j ist fehlerhaft
Bei einem NACKj muß der Sender alle Blöcke ab j wiederholen
Vorteil: der Empfänger braucht nur einen einzigen Pufferplatz
Beispiel für W=5; MODULUS = 8
0 1 2 3 4 5 2 3 4 5 6Quelle
Ziel
Übertragungsablauf
REJ2ACK0 ACK2
SREJj ⇒ nur Block Nr. j wird noch einmal gesendet
Weniger Wiederholungen, dadurch mehr Durchsatz
Höherer Aufwand bei Sender und Empfänger
Nebenbedingungen• REJ und SREJ darf nicht wiederholt werden (für dasselbe Paket),
bei nochmaligem Verlust
• Ein zusätzliches SREJ darf nicht gegeben werden, so lange ein altes noch in Bearbeitung ist
• Wenn ein REJ verlorengeht oder wiederholt werden müsste, ist eine Timeout-Regelung erforderlich
Erweiterung: Selective Reject
• Zu großes Timeout impliziert langes Warten auf Wiederholungen
• Zu kleines Timeout führt zu Duplikaten, wenn Nachrichten doch noch verspätet eintreffen
Problem:Bei langen Übertragungsstrecken wird der Sender durch Reject oder Selective Reject sehr oft blockiert
Beispiel:• Satellitenstrecken haben Roundtripzeit von 0,6 Sekunden,
d.h. bei W=5 wäre die Strecke weitestgehend leer
Timeout-Einstellungen
• Niedrigere Kapazität pro Leitung• Deutlich größeres Fenster (z.B. W = 128)
Lösungen
• Go-Back-N führt dazu, daß sehr viele Sendungen wiederholt werden
Erneutes Problem
• Selective Repeat (SREPEAT) mit unbegrenztem Fester verschickt• SREPEAT (j1, j2, ..., jk) ⇒ bis Nachricht j1-1 ist alles in Ordnung
⇒ Nachrichten j1 bis jk werden wiederholt• Variante: Intervalle korrekt erhaltener Paketnummern angeben;
fehlende Nummern werden dadurch automatisch neu angefordert.
Ausweg
Selective Repeat
Kriterium FEC ARQOverhead(Redundanz)
groß(7/8-, 3/4-, 1/2-Code)
gering, aber:fehlerhafte Blöcke müssenwiederholt werden
Zeitaufwand gering(per Hardware, on-the-fly)
gering fürPrüfsummenberechnung (perHardware), aber: Wiederholungsehr zeitaufwendig
Echtzeiteignung ja neinQualität derFehlerkorrektur
nicht alle werden erkannt (fast) alle Fehler werden erkanntund korrigiert
Anwendungen Sprache/Audio, Video,Daten, Graphik
Daten, Graphik
zusätzlicheFunktionalität
z.T. Erkennung nichtkorrigierbarer Fehler
Flusskontrolle
Vergleich FEC - ARQ
Auch möglich: Kombination von FEC und ARQ:
Wenn FEC versagt, wird ARQ eingesetzt.
Beispiel-Protokoll
Schicht 2
Rahmenkennung:eindeutige Anfangs- und Endflaggen"01111110"
→→→→ Flagge darf niemals innerhalb eines Rahmens vorkommen
→→→→ Abhilfe: Bitstuffing (Bitstopfen)Sender fügt nach jeweils fünf Einsen eine Null ein.Der Empfänger entfernt sie wieder.
Varianten:
X.25 LAPB
ISDNLAPD
(Link Access Procedure in Balanced Mode)
(Link Access Procedure for D-Channels)
High Level Data Link Control(HDLC)
Bitstuffing: Sender: 11111111
111110111
Empfänger: 111110111
11111111
01111110 01111110Address Control FCSData8 168 8(16) 8≥0
Im Idle-Zustand werden "1"en gesendet→→→→ Empfänger erkennt eine Sendung an der ersten "0"
• bitorientierte, synchrone Datenübertragung• Vollduplex-Betrieb
• Rahmennummern• Flusskontrolle• FCS: CCITT-Generatorpolynom g(x) = x16 + x12 + x5 + 1
→→→→ Quittungen können mit einem Informationsrahmen in Gegenrichtung"huckepack" verschickt werden (Piggybacking)
BitsHeader TrailerDaten
FlagFlag
HDLC-Rahmen
I-Rahmen
S-Rahmen
U-Rahmen
PFS S N(R)
PFN(S) N(R)
PFM M M M M11
1 0
0Information
Supervisory
Unnumbered
Sendefolgenummer Empfangsfolgenummer
Poll/FinalN(S) Sendefolgenummer
N(R) Empfangsfolgenummer (Block N(R) wird als nächster erwartet - alle Blocks bis N(R)-1 quittiert)
Kontrollbyte (Control)
N r. Typ Befehlsnam eC - Feld
1 2 3 4 5 6 7 8
1 I (D atenfram e)I 0 N (S) P N (R )
2.1 R R 1 0 0 0 N (R )(Receive Ready)
2.2(R eceive not Ready)
R N R 1 0 1 0
P/F
P/F N (R )
2.3 REJ 1 0 0 1 P/F N (R )(R eject)
2.4 SRE J 1 0 1 1 P/F N (R )(Selective Reject)
S
3.1(Set A synchronous
Balanced M ode)
SA B M 1 1 1 1 P 1 0 0
3.2 D ISC(Disconnect)
1 1 0 0 P 0 1 0
3.3 U A 1 1 0 0 F 1 1 0
3.4(Com m and Reject)
CM D R 1 1 1 0 F 0 0 1
(U nnum beredA cknow ledgem ent)
3.5 FR M R(Fram e R eject)
1 1 1 0 F 0 0 1
3.6 (D isconnect M ode)D M 1 1 1 1 F 0 0 0
U
Vorübergehend nicht empfangsbereit, quittiert bis N(R)-1 in Gegenrichtung
Negative Quittung für N(R), bis N(R)-1 alles quittiert. Der Sender soll alle Rahmen ab N(R) wiederholen.
Negative Quittung selektiv für N(R), quittieren bis N(R)-1
Verbindungsaufbau
Bestätigung (z.B.für Verbindungsaufbau)
empfangender Rahmen/Kommando nicht in Ordnung (ungültiger Rahmen, falsche Rahmennummer ...
Sendet Rahmen n(S) und quittiert bis N(R) -1 in Gegenrichtung
empfangsbereit, quittiert bis N(R) -1 in Gegenrichtung
Ankündigung des Verbindungsabbaus
Verbindungsabbau
HDLC-Rahmentypen
01
2
34
5
6
7
01
2
34
5
6
7
Flußkontrolle: Sliding Window-Verfahren
2 Rahmen gesendet (0,1) (noch 3 frei)
5 Rahmen gesendet (0,1,2,3,4)
(Fenster voll ausgelastet )
→ auf Quittung warten
N(R) = 0
N(R) = 0
Beispiel: Fenstergröße W = 5
HDLC: Flußkontrolle
Folgenummern haben 3 Bit: 23 = 8 Folgenummern (0,..7)Sei nun Fenstergröße W = 8. A sendet Rahmen an B.B hat zuletzt Rahmen 2 quittiert (ACK N(R) = 3 an A gesendet)
B hat quittiert 0 1 2A sendet 8 Rahmen, ohne daß eine Quittung von B eingeht
A hat gesendet 0 1 2 3 4 5 6 7 0 1 2Es kommt eine Quittung ACK N(R) = 3 an.
Fall 1: B hat empfangen 0 1 2Fall 2: B hat empfangen 0 1 2 3 4 5 6 7 0 1 2
A weiß nicht, ob bei B Fall 1 oder 2 vorliegt: die Quittung ist nicht eindeutig!
⇒ W ≤≤≤≤ 7 ⇒ lange Signallaufzeit, niedrige Übertragungsraten
Abhilfe: Extended Numbering Mode mit zusätzlichem Control-Byte (2*4 Bits)
⇒ je 7 Bit pro Richtung, Fenstergröße W ≤ 127
Maximale Fenstergröße bei HDLC
Schicht 2
Medium Access Control
Nutzer 1Nutzer 2Nutzer 3
Medium Access Control (MAC)
Regelung des konkurrierenden Zugriffs mehrerer Nutzerauf ein gemeinsames Medium
Einfachste Verfahren: feste Zuweisung einer begrenzten Kapazität• Time Division Multiple Access (TDMA)
• Frequency Division Multiple Access (FDMA)
1 1 1 12 2 23 3 3 3 3 3
Jeder Nutzer bekommt fürfeste Zeit-Slots die gesamteÜbertragungskapazität(Basisband-Übertragung)
Jeder Nutzer bekommt fürdie gesamte Zeit einen festenAnteil der Übertragungskapazität(einen Frequenzbereich)(Breitband-Übertragung)
• 802.1 Higher Layer Interface (HILI)
• 802.2 Logical Link Control (LLC)
• 802.3 CSMA/CD („Ethernet“)
• 802.4 Token Bus
• 802.5 Token Ring
• 802.6 Metropolitan Area Network (MAN): unter anderem
DQDB (Distributed Queues Dual Bus)
• 802.7 Broadband Technical Advisory Group (BBTAG)
• 802.8 Fiber Optic Technical Advisory Group (FOTAG)
• 802.9 Intergrated Services LAN (ISLAN) Interface
• 802.10 Standard for Interoperable LAN Security (SILS)
• 802.11 Wireless LAN (WLAN)
• 802.12 Demand Priority
• 802.14 Cable-TV Based Broadband Communication Network
IEEE 802.xMAC- und Bitübertragung
MAC - Reservierungsverfahren
Reservierungsverfahren
zweiphasiger Ablauf:
• Reservierungsphase (Reservierung mit Wunschlänge)
• Übertragungsphase
Vorteil: sehr effiziente Nutzung der KapazitätNachteil: zweiphasiges Verfahren - benötigt eine gewisse Vorlaufzeit
Benötigt wird eine Master-Station, die zyklisch alle anderen Stationenabfragt, ob sie Daten übertragen wollen. Wenn ja, teilt die Master-Stationdas Senderecht zu.
MAC - Token-Verfahren
Einführung eines Tokens (bestimmte Bitfolge)
• Der Besitz des Tokens berechtigt zum Senden
• Das Token wird zyklisch weitergegeben
→ besonders für Ringe geeignet
→ Token-Ring (4/16/100Mbit/s)
Eigenschaften:
• garantierter Zugriff, keine Kollisionen
• sehr gute Ausnutzung der Netzkapazität, hohe Effizienz
• fair, garantierte Antwortzeiten
• möglich: multiple tokens
• aber: aufwendig und teuer
Weitergabe des Tokens
Station
1
2
3
t
A
B
MAC - ungesteuerte VerfahrenVerfahren hat den Namen ALOHA• auf den hawaiianischen Inseln entwickelt• weit entfernt liegende Stationen über Satellit verbinden• extrem einfach, keine Abstimmung:
• Stationen senden völlig unkoordiniert • bei Kollision Wiederholung nach zufälliger Zeit• Problem: da der Verkehr über einen Satelliten läuft, hört ein Sender
erst nach sehr langer Zeit, ob die Übertragung geglückt ist.
(dadurch keine garantierten Antwortzeiten, geringer Durchsatz)
T Konfliktperiodet
MAC - ungesteuerte Verfahren
Verbesserung: Slotted ALOHA
• Die Übertragungszeit wird in Zeitscheiben eingeteilt
• Die Übertragung eines Blocks startet zu Beginn einer Zeitscheibe
→ weniger Kollisionen
• Aber: die Stationen müssen synchronisiert sein!
Vermeidung von Kollisionen durch Einführung von Slots
Durchsatz als Funktion des Gesammtverkehrs
0
0,05
0,1
0,15
0,2
0,25
0,3
0,35
0,4
0 0,5 1 1,5 2 2,5 3
Gesamtverkehr G
Dur
chsa
tz S
pure Aloha slotted Aloha
e*2
1
368,01 =e
Leistungsfähigkeit der Varianten
MAC - teilgesteuerte Verfahren
Carrier Sense Multiple Access (CSMA)
• Prinzip:
→ höre vor der Übertragung das Medium ab
→ sende nur, falls das Medium frei ist
S1
Nachricht von S1
1. Station S1 sendet
Ausdehnung des Signals auf dem MediumS2
2. Station S2 will ebenfalls senden, merkt aber, daß bereits eine Übertragung stattfindet.
S1
Nachricht von S1
1. Station S1 sendet
Ausdehnung des Signals auf dem MediumS2
2. Station S2 will ebenfalls senden und denkt, das Medium wäre frei.
Problem bei CSMA
Problem: die Nachricht, die S1 sendet, breitet sich mit endlicher Geschwindigkeit auf dem Medium aus. Daher kann es sein, daß S2 denkt, das Medium wäre frei, obwohl S1 schon mit der Sendung begonnen hat. Beide Nachrichten überlagern sich auf dem Medium und werden unbrauchbar.
Nachricht von S2
Nachricht breitet sich auch in Gegenrichtung aus
Carrier Sense Multiple Access with Collision Detection (CSMA/CD)
• Prinzip:
→ wie CSMA
→ zusätzlich: breche die Übertragung ab, wenn eine Kollision auftritt
Carrier Sense Multiple Accesswith Collision Detection
S1S2
Maximale Ende-zu-Ende-Laufzeit
Zeit
S1 sendet
S2 sendet
S2 entdeckt den Konflikt und stopptS1 entdeckt den Konflikt und
weiß, daß die Sendung wiederholt werden muß.
Nachrichtenformat bei CSMA/CD
Präambel SFD DA SA Length Data Padding FCS
1: 7 Byte SynchronisationJedes Byte beinhaltet 10101010
2: 1 Byte Start Frame DelimiterMarkierung des Rahmenbeginnsdurch das Byte 10101011
3: 6 Byte Destination Address
4: 6 Byte Source Address
5: 2 Byte LengthAngabe der Länge des Datenfelds (zulässiger Bereich: 0 - 1500 Byte)
1 2 3 4 5 6 7 8
6: ≥ 0 Byte Daten
7: ≥ 0 Byte Padding
Auffüllen des Rahmens auf mindestens
64 Byte (Kleinere Fragmente werden
im Netz verworfen, zusätzlich nötig zurKollisionsvermeidung)
8: 4 Byte Frame Check Sequence
Verwendung eines zyklischen Codes
Auflösung von Sende-Konflikten
Verschiedene Kategorien
Nonpersistent (Beispiel: ALOHA):
• warte nach einem Konflikt mit einer zufälligen Wartezeit aus
einem vorgegebenen Intervall bis zu einer Neuübertragung
• Problem: möglicherweise ineffiziente Nutzung des Mediums
1-persistent
• Idee: es ist sehr unwahrscheinlich, daß während einer laufenden
Übertragung 2 oder mehr neue Nachrichten anfallen.
• Starte den nächsten Sendeversuch so bald wie möglich, also sobald der
Kanal frei ist bzw. nach einem Konflikt abgebrochen wurde.
• Problem: Folgekonflikte!
p-persistent:• bei dieser Variante sollen Konflikte zwischen gleichzeitig wartenden
Nachrichten vermieden werden• bei einem freien Kanal wird nur mit Wahrscheinlichkeit p gesendet• im Konfliktfall benötigt die Nachricht im Mittel 1/p Versuche• Wie wählt man p? p groß = hohes Risiko für Folgekonflikte
p klein = lange Wartezeitenp=0 nicht möglich, p=1 = 1-persistent
CarrierSense
frei
belegt
senden
Konflikt
warten bis frei würfle eine Zahl z ∈ [0,1]
Ende
Start
sendenz ≤ p
Konflikt
klappt
klappt
z > p
Auflösung von Sende-Konflikten
Start Carrier Sense
Warten bis frei„würfle“ (gleichverteilt)
eine ganze Zahlx ∈ [1,2i]
Sendeversuch imx-ten folgenden
Minislot Konflikt
i = i+1
ErfolgEnde
Ethernet: Binary ExponentialBackoff
Idee: um einen gleichzeitigen Zugriff zu vermeiden, wird wie bei dernonpersistenten Methode eine zufällige Wartezeit aus einem vorgegebenenIntervall gezogen. Das Intervall wird klein gehalten, um große Wartezeitenzu vermeiden. Tritt allerdings ein Konflikt auf, kommt es sehr wahrscheinlichzu einem Folgekonflikt. Daher wird das Intervall vor dem nächsten Versuchvergrößert, um mehr Spielraum für alle sendenden Parteien zu schaffen