Grundlagen der Rechnernetze
Medienzugriffskontrolle
Übersicht• Multiplexing und Multiple‐Access• Dynamische Kanalzuweisung• Multiple‐Access‐Protokolle• Spread‐Spectrum• Orthogonal‐Frequency‐Division‐Multiplexing
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 2SS 2012
Multiplexing und Multiple‐Access
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 3SS 2012
Motivation
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Multiple‐Access‐Kanal
Generelles Problem in diesem VorlesungskapitelUnkontrollierter Medienzugriff führt zu Nachrichtenkollisionen
Mögliche Lösung: Multiplexing
Kapazität C bps
N Subkanäle mit Kapazitätjeweils C/N bps
Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012
Wie erreicht man eigentlich Multiplexing eines Kanals? ...
Multiplexer Demultiplexer
4SS 2012
Frequency‐Division‐Multiplexing (FDM)
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
To ZTo Z
(in frequency 1)(in frequency 2)
Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012, Andrew S. Tanenbaum, Computer Networks, 4th Edition, 20035SS 2012
FDM‐Implementation
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 6Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
FDM‐Implementation
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 7Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Time‐ und Space‐Division‐Multiplexing
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Time‐Division‐Multiplexing (TDM)
Space‐Division‐Multiplexing (SDM)
To Z
To Z
8Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012
SS 2012
To ZTo Z
TDM‐Implementation
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 9Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
TDM‐Implementation
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 10Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Code‐Division‐Multiplexing (CDM)
r1
r2
s1
s2
Zeit
Band
breite
Zeit
Band
breite
ZeitBa
ndbreite
11Grundlagen der Rechnernetze ‐ MedienzugriffskontrolleSS 2012
Multiplexing und Multiple‐Access• Auf der Physikalischen Schicht
– Multiplexing um eine Leitung für mehrere Übertragungen zugleich zu verwenden
– Beispiele: Kabel‐TV, Telefon
• Auf der Verbindungsschicht– Multiplexing um konkurrenten Zugriff auf ein geteiltes Medium zu kontrollieren
– Man spricht dann von Multiple‐Access– Also: FDMA, TDMA, CDMA, SDMA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 12SS 2012
Statisches Multiplexing• Auf der Physikalischen Schicht
– Medium wird in N Kanäle mit gleicher Bandbreite unterteilt
– Man spricht auch von statischem Multiplexing
• Multiplexing auf der Verbindungsschicht?• Möglichkeit 1: Jedem Kommunikationspaar wird einer der N Kanäle der der physikalischen Schicht zugeordnet
• Sinnvoll wenn Kanal fasst die Datenrate der Quelle Datenrate der Quelle sättigt immer den Kanal
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 13SS 2012
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 14
Problem Traffic‐Bursts• Datenverkehr mit Bursts bedeutet: große Differenz zwischen Spitzen‐ und Durchschnittsrate
• Eine Hausnummer in Computer‐Netzen: Spitzen‐versus Durchschnittsrate = 1000 : 1
Time
Source data rate
Meanrate
Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012SS 2012
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 15
Statisches Multiplexing und Traffic‐Bursts• Statisch aufgeteilte Ressourcen müssen entweder:
TimeSource data rate
Meanrate
Required rate
Groß genug sein, um auch die Spitzendatenrate unmittelbar bedienen zu können
! Ressourcenverschwendung, da die Linkkapazität im Mittel nicht ausgeschöpft wird
für den mittleren Fall dimensioniert sein, aber wir benötigen dann einen Puffer
! Was ist der Delay bis ein Paket übertragen werden kann?
Queues
Packets
New packetsMUX
Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012SS 2012
Delay‐Rechnung
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 16
Betrachte:• Kanal mit Kapazität C bps• Exponential verteilte Paket‐Ankunftsrate von Pakete/Sekunde• Exponential verteilte Paketlängen mit mittlerer Paketlänge von
1/ Bits/Frame
Was ist die mittlere Wartezeit T eines Pakets bei idealem Kanalzugriff mit einer zentralen globalen Warteschlange?
Was ist die mittlere Wartezeit TFDM von statischem FDM (andere Multiplexing‐Verfahren analog)?
SS 2012
Delay‐Rechnung an der Tafel
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 17SS 2012
Dynamische Kanalzuweisung
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 18SS 2012
Grundlagen der Rechnernetze - Medienzugriffskontrolle 19
Dynamische Kanalzuweisung• Statisches Multiplexing nicht geeignet für Verkehr mit Bursts– Wesentlicher Grund: Zeitweise ungenutzte Kanäle– Telefon oder TV hat keine Bursts: statisches Multiplexing sinnvoll
– Computer‐Netze hingegen haben Traffic‐Bursts: wir brauchen hier eine andere Form der Kanalzuweisung
• Alternative: Weise Kanal‐Ressourcen den Quellknoten zu, die aktuell Daten zu senden haben
SS 2012
Grundlagen der Rechnernetze - Medienzugriffskontrolle 20
Annahmen für folgende Protokolldefinitionen• Stationsmodell (oder Terminal‐model)
– N unabhängige Stationen teilen sich eine Ressource
• Single‐Channel‐Annahme– Ein einziger Kanal für alle Stationen– Keine weiteren Kanäle über die Kontrollsignale
kommuniziert werden können
• Kollisionsannahme– Zu jedem Zeitpunkt kann nur ein Paket erfolgreich
übertragen werden– Zwei oder mehr zeitlich überlappende Pakete kollidieren
und werden damit ungültig– (Ausnahmen bestätigen die Regel)
Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012SS 2012
Grundlagen der Rechnernetze - Medienzugriffskontrolle 21
Annahmen für folgende Protokolldefinitionen• Zeit‐Modell
– Kontinuierliche Zeit: Übertragungen können zu beliebigem Zeitpunkt beginnen
– Zeit‐Slots: Zeit wird in Slots eingeteilt; Übertragungen können nur zu Slot‐Startpunkten stattfinden. Jeder Slot kann ungenutzt, erfolgreich oder mit einer Kollision behaftet sein.
• Carrier‐Sensing– Stationen können bzw. können nicht
erkennen, ob der Kanal von einem anderen benutzt wird oder nicht
– Detektion kann immer mit Ungenauigkeiten behaftet sein (z.B., überhören einer laufenden Übertragung)
Time
Time
?
Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012SS 2012
Grundlagen der Rechnernetze - Medienzugriffskontrolle 22
Bewertungen der folgenden Protokolle• Wie bewertet man die Effizienz eines dynamischen
Medienzugriffs?– Intuition: es sollten soviele Pakete wie möglich so schnell wie möglich erfolgreich übertragen werden
• Bei hoher Last (viele Übertragungen pro Zeiteinheit): Durchsatz ist das entscheidende Maß – stelle sicher dass möglichst viele Pakete erfolgreich übertragen werden
• Bei geringer Last (wenige Übertragungsversuche pro Zeiteinheit):Delay ist das entscheidende Maß – stelle sicher dass Pakete nicht zu lange warten müssen
• Fairness: Wird jede Station gleich wie die anderen bedient?
SS 2012
23
Durchsatz über angebotener Last
Paketankünfte
Erfolgreiche Pakete (S)
Ein Paket pro Paketzeit
Ein Paket pro Paketzeit Reale MAC‐Protocolle
Ideales MAC‐Protocol
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Angebotene Last G = Anzahl der Pakete pro Paketübertragungszeit, die das Protokoll zur Abarbeitung erhält
SS 2012
Stochastisches Modell für die angebotene Last
Grundlagen der Rechnernetze - Medienzugriffskontrolle 24
Große Benutzerpopulation
Benutzer erzeugen unabhängig voneinander Pakete mit einer Gesamtrate von Paketen pro Zeiteinheit
Ankommende Pakete
SS 2012
Motivation des Poisson‐Prozesses
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 25SS 2012
Multiple‐Access‐ProtokolleALOHA und Slotted‐ALOHA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 26SS 2012
ALOHA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 27
Starte Übertragung wann immer ein Datenpaket vorliegtBildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Wann ist ALOHA sinnvoll?
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 28Bildquelle: Prof. Karl, Vorlesung Rechnernetze, WS 2011/2012
SS 2012
Performance von ALOHA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 29
Annahmen für die Analyse:• Dauer einer Paketübertragung sei konstant t.• Sehr große Benutzerpopulation• Gesamtpopulation erzeugt Pakete Poisson‐Verteilt mit einer
mittleren Paketrate von G Paketen pro Paketübertragungszeit t• (G beinhaltet neue Pakete und die Pakete die nochmal
übertragen werden müssen)
Was ist der Durchsatz S an Paketen pro Paketübertragungszeit?
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 30SS 2012
Verbesserung Slotted‐ALOHA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 31
Starte Übertragung wann immer ein Datenpaket vorliegtBeginne die Übertragung jedoch nur zu Beginn von festen Zeit‐Slots
Zeit
Zeit‐Slot
Paketankunft Paketübertragung
SS 2012
Performance von Slotted‐ALOHA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 32
Gleiche Annahmen für die Analyse:• Dauer einer Paketübertragung sei konstant t.• Sehr große Benutzerpopulation• Gesamtpopulation erzeugt Pakete Poisson‐Verteilt mit einer
mittleren Paketrate von G Paketen pro Paketübertragungszeit t• (G beinhaltet neue Pakete und die Pakete die nochmal
übertragen werden müssen)
Was ist der Durchsatz S an Paketen pro Paketübertragungszeit?
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 33SS 2012
Vergleich zwischen ALOHA und Slotted‐ALOHA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 34Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
1 G
S1
Das Ideal
SS 2012
Multiple‐Access‐ProtokolleCarrier‐Sense‐Multiple‐Access (CSMA)
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 35SS 2012
Carrier‐Sensing
• Diese Vorgehensweise nennt man Carrier‐Sense‐Multiple‐Access (CSMA)
• Frage: Kann man nach hören in den Kanal immer sicher sein, dass der Kanal frei ist?
• Frage: Was ist mit der Nachricht zu tun, wenn der Kanal nicht frei ist? Wann kann die Nachricht übertragen werden?
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 36
Höre in den Kanal
Kanal frei? ???
Start
Sende Paket
Ende
ja
nein
SS 2012
CSMA und Propagation‐Delay
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 37
Beispiel:21
Propagation‐Delay
SS 2012
Beispiel:
1‐Persistent‐CSMA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 38
Höre in den Kanal
Kanal frei?
Warte solange bis Kanal frei wird
Start
Sende Paket
Ende
Kollision?
ja
nein
nein
Warte zufällige Zeit
ja
1 2 3
SS 2012
Beispiel:
Nonpersistent‐CSMA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 39
Höre in den Kanal
Kanal frei?
Start
Sende Paket
Ende
Kollision?
ja
nein
nein
Warte zufällige Zeit
ja
1 2 3
SS 2012
Beispiel:
P‐Persistent‐CSMA
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 40
Höre in den Kanal
Kanal frei?
Start
Ende
Senden?(mit WK p)
ja
nein Warte einenZeit‐Slot
1 2 3
Warte einen Zeit‐Slot und dann
höre in den Kanal
Kanal frei?
nein
ja
Sende Paket
Kollision?
nein
ja Warte zufällige Zeit
ja
nein
SS 2012
Feststellen einer Kollision am Sender?
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 41
Beispiel:1 2
SS 2012
3
Durchsatz versus angebotene Last
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 42
Wir analysieren nur den einfachsten Fall: Nonpersistent‐CSMA
Annahmen:• Gesamtrate an Nachrichten (d.h. neue und reübertragene) sei G• Ankunftsrate der Nachrichten sei Poisson‐Verteilt
(das ist eine vereinfachende Annahme)• Propagation‐Delay sei a Zeiteinheiten• Eine Paketübertragung dauert 1 Zeiteinheit
Was ist der Durchsatz S über der angebotenen Last G?
Betrachte die Zufallsgrößen:• B = Länge einer „Busy‐Periode“• I = Länge einer „Idle‐Periode“• C = Länge eines „Busy‐Idle‐Zyklus“ 1 G
S1
Das Ideal
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 43SS 2012
Durchsatz von ALOHA und CSMA
Grundlagen der Rechnernetze - Medienzugriffskontrolle 44Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Beispiel:
CSMA mit Kollisionsdetektion: CSMA/CD
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 45
Start
Starte Paketübertragung
Ende
Kollisionderweil?
nein
ja
1 2 3
Stoppe Paketübertragung
1‐PersistentP‐PersistentNonpersistent
SS 2012
Binary‐Exponential‐Backoff
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 46
Wähle einen zufälligen Zeit‐Slot k in {0,...,N‐1} und starte Übertragung zum Slot k
Setze N auf 2*N
Kollision?
Mehr als 16 Versuche?
Bemerkung: dies sind die Parameter aus Ethernet.Die Länge eines Zeitslots wird auf 2*Maximum‐Propagation‐Delay festgelegt.
Setze maximale Anzahl Slots N auf 2
Ende
Teile höherer Schicht mit, dass Paket nicht ausstellbar
Start
nein
ja
ja
nein
LetztesFrame Nächstes Frame
Contention‐Periode
SS 2012
Quiz: warum 2*Propagation‐Delay?
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 47
1 2…Maximales Propagation‐Delay sei
Wie weit können Startzeitpunkte von zwei kollidierenden Nachrichten auseinander liegen?
Wie lange dauert es maximal bis alle die Kollision erkannt haben?
Also ist ab dem ersten Slot der Kanal einem Knoten sicher zugewiesen. Dann kann keine Kollision mehr stattfinden.
SS 2012
Betrachte ein sehr kurzes Paket und etwas längeres Paket:
Also: Paket sollte groß genug sein, damit Sender die Kollision erkennen kann. Es sei p der maximale Propagation‐Delay und d die Datenrate. Welche Größe g sollte das Paket mindestens haben?
CD erfordert Mindestpaketlänge
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 48
Sender 1
Sender 2
Empfänger 1
Multiple‐Access‐ProtokolleKollisionsfreie und Limited‐Contention Protokolle
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 49SS 2012
Bit‐Map‐Protokoll
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 50
Was ist Kanaleffizienz (Nutz‐Bits über insgesamt gesendete Bits)? N=Anzahl Slots; jeder Slot ein Bit; d=Anzahl Daten‐Bits pro GerätBei geringer Last:
Bei hoher Last:
• Wechsel zwischen Contention‐ und Frame‐Übertragungsphasen• Es gibt eine feste Anzahl N von Knoten• Jeder knoten hat eine eindeutige Nummer zwischen 0 und N‐1
Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003SS 2012
Binary‐Countdown
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 51
Binary‐Countdown am Beispiel
Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
Was ist die Kanaleffizienz (Nutz‐Bits über insgesamt gesendete Bits)?
Bei geringer Last:
Bei hoher Last:
Wenn die Bits am Anfang als Adresse des Absenders Teil der Nachricht sind:
SS 2012
Wie erreicht man Fairness bei Binary‐Countdown?
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 52
Problem: Knoten mit größeren Adresswerten werden bevorzugt.
Idee: Binary‐Countdown nach Prioritätswerten.
Beispiel:Knotenadressen: C H D A G B E FPrioritäten: 7 6 5 4 3 2 1 0
Wenn D erfolgreich gesendet hat, ändern sich Prioritäten wie folgtKnotenadressen: C H A G B E F DPrioritäten: 7 6 5 4 3 2 1 0
SS 2012
Limited‐Contention‐Protokolle
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 53
Protokolle mit Contention (z.B. ALOHA, CSMA)• geringe Latenz bei geringer Last aber• schlechte Kanaleffizienz bei hoher Last
Kollisionsfreie Protokolle (z.B. Binary Countdown)• hohe Latenz bei geringer Last aber• gute Kanaleffizienz bei hoher Last
Warum nicht ein Protokoll welches sich• bei geringer Last wie ein Protokoll mit Contention• und bei hoher Last wie ein kollisionsfreies Protokoll verhält?
Zunächst: Was ist der Einfluss der Anzahl k Stationen auf die Performance bei Protokollen mit Contention?
SS 2012
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 54
• Also: die Performance degradiert auch schon bei wenigen übertragenden Knoten recht schnell.
• Idee: Versuche alle Teilnehmer in kleine Gruppe einzuteilen.• Jede Gruppe kommt mal dran.• Contention findet nur innerhalb der Gruppe statt.
Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
Erfolgswahrscheinlichkeit einer Übertragung
SS 2012
Adaptive‐Tree‐Walk‐Protokoll
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 55Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Adaptive‐Tree‐Walk‐Protokoll
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 56Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
Level 1
Level 0
Level 2
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 57SS 2012
Multiple‐Access‐ProtokolleWireless‐LAN‐Probleme
SS 2012 58Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Ein ähnliches Problem; nur komplizierter…
S1 T1
S2
T2
Kollisionsdomäne
SS 2012 59Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
60
Das Hidden‐Terminal‐Problem
S1 T1 S2 T2
CSMA verhindert nicht, dass S2 sendet
Collision
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
61
Das Exposed‐Terminal‐Problem
S1T1 S2 T2
CSMA verhindert, dass S2 sendet
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Multiple‐Access‐ProtokolleVermeiden von Hidden‐ und Exposed‐ Terminal‐Problem
SS 2012 62Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
63
Busy Tones
Daten‐Frequenz
Busy‐Tone‐Frequenz
S1 T1 S2 T2Busy tonewährend des Empfangs
t1
t2
Andere Knoten sind währenddes Busy‐Tone‐Empfangsgeblockt
Daten‐übertragung
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
64
BT und das Hidden‐Terminal‐Problem
S1 T1 S2 T2
Busy‐Tone verhindert, dass S2 sendet
Busy Tone
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
65
BT und das Exposed‐Terminal‐Problem
S1T1 S2 T2
Busy‐Tone verhindert nicht, dass S2 sendet
Busy‐Tone
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Das Problem mit Busy‐Tones (1/2)
S1 T1 S2 T2
Daten‐ und Busy‐Tone‐Frequenz unterliegen unterschiedlichenFading‐ und Dämpfungscharakteristiken. Busy‐Tone kannmöglicherweise Kommunikationsnachbarn von T1 nicht erreichen.
Busy‐Tone
Collision
SS 2012 66Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
67
Das Problem mit Busy‐Tones (2/2)
S1T1 S2 T2
Busy‐Tone erreicht möglicherweise Knoten S2, welcherkein Kommunikationsnachbar ist.
Busy Tone
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
68
Eine bessere Lösung: CSMA & RTS/CTS
S1 T1
RTS
CTS
Data
NAV belegt dasMedium für dieKommunikations‐Dauer
Beachte CTS‐Antwortzeit
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
69
RTS/CTS und das HT‐Problem
S1 T1 S2 T2
CTS verhindert, dass S2 sendet
RTSCTS CTS
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
70
RTS/CTS und das ET‐Problem
S1T1 S2 T2
S2 hört CTS nicht und wird damit durch NAV nicht geblockt
RTSCTS
SS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
71
Quiz: wird das HT‐Problem immer verhindert?
S1 T1 S2T2
RTS
CTS
Data
Example 1: Data‐CTS Collision
RTS
CTS
Data
S1 T1 S2 T2
Example 2: Data‐Data CollisionSS 2012 Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle
Spread‐Spectrum
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 72SS 2012
Generelles Modell
• Generell: schmalbandiges Signal wird über breites Band ausgedehnt
• Wozu ist diese „Bandbreitenverschwendung“ gut?– Steigert Robustheit gegenüber schmalbandigen Störungen (z.B.
Jamming)– Mithören der Nachricht nur möglich, wenn der Spreading‐Code
bekannt ist– „Unabhängige“ Codes ermöglichen zeitgleiches übertragen mehrerer
solcher schmalbandiger Signale (also: CDM bzw. CDMA)
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 73Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Spread‐SpectrumFrequency‐Hopping‐Spread‐Spectrum (FHSS)
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 74SS 2012
FHSS Beispiel
• Spreading Code = 58371462• Nach 8 Intervallen wird der Code wiederholt
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 75Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Implementierung ‐ Sender
• Beispiel: BFSK‐Modulation der Daten• Was ist das Produkt p(t) der Eingabe und des „Chipping‐Signals“?• Bestimme p(t) und s(t) für das ite Bit• Bestimme Frequenz des Daten‐Signals s(t) für Datenbit +1 und ‐1
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 76Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
A Amplitude des Signals
f0 Basis‐Frequenz
fi Chipping‐Frequenz im iten Hop
bi ites‐Datenbit (+1 oder ‐1)
f Frequenz‐Separation
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 77SS 2012
Implementierung ‐ Empfänger
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 78Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
A Amplitude des Signals
f0 Basis‐Frequenz
fi Chipping‐Frequenz im iten Hop
bi ites‐Datenbit (+1 oder ‐1)
f Frequenz‐Separation
• Bestimme p(t) für das ite Bit• Bestimme das ursprüngliche Datensignal anhand desselben Chipping‐Signals
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 79SS 2012
FHSS mit MFSK
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 80
Erinnerung: was war MFSK?
Was ist das ite Signalelement?
Signalelement wird jede Tc Sekunden auf eine neue Hopping‐Frequenz moduliert.Wir unterscheiden:
fi fc + (2i‐1‐M)fdfc Carrier‐Frequenz
fd Differenz‐Frequenz
M Anzahl der verschiedenen Signalelemente = 2^L
L Anzahl Bits pro Signalelement
Ts Zeit für ein Signalelement
Slow‐Frequency‐Hop‐Spread‐Spectrum Tc ≥ TsFast‐Frequency‐Hop‐Spread‐Spectrum Tc < Ts
SS 2012
Slow‐Frequency‐Hop‐Spread‐Spectrum
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 81Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
M=4, L=2
SS 2012
Fast‐Frequency‐Hop‐Spread‐Spectrum
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 82Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
M=4, L=2
SS 2012
Spread‐SpectrumDirect‐Sequence‐Spread‐Spectrum (DSSS)
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 83SS 2012
DSSS Beispiel
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 84Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
DSSS auf Basis von BPSK: Sender
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 85Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
A Amplitudef_c Carrier‐Frequenzd(t) +1 für Bit 1 und ‐1 für Bit 0
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 86SS 2012
DSSS auf Basis von BPSK: Empfänger
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 87Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 88SS 2012
Beispiel
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 89Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Spread‐SpectrumCode‐Division‐Multiple‐Access (CDMA)
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 90SS 2012
CDMA Beispiel
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 91Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
User A, B und C senden gleichzeitig
1 ‐1 ‐1 1 ‐1 1
1 1 ‐1 ‐1 1 1
1 1 ‐1 1 1 ‐1
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 92SS 2012
Orthogonalität von Codes
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 93
Codes für zwei Knoten A und B mitSA(cB) = SB(cA) = 0
nennt man orthogonal.
Nicht so einfach solche Codes zu konstruieren.
Orthogonalität nicht zwingend notwendig. Es genügt:SX(CY) hat einen kleinen absoluten Wert für X != Y
Betrachte in vorigem Beispiel B und C...
SS 2012
Tafelbild
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 94SS 2012
Beispiel: CDMA auf Basis von DSSS und BPSK
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 95Bildquelle: William Stallings, „Data and Computer Communications“, Seventh Edition, 2004
SS 2012
Orthogonal‐Frequency‐Division‐Multiplexing
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 96SS 2012
Orthogonal‐Frequency‐Division‐Multiplexing
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 97
Verwendete Bandbreite?
Bit‐Rate pro Subcarrier?
Der wesentliche Vorteil:• Frequenzselektive Störungen
(Fading) betrifft nur wenige Bits (Fehlerkorrektur)
• Inter‐Symbol‐Interferenz signifikant reduziert. Was ist die Bit‐Zeit pro Kanal?
Bildquelle: William Stallings, „Data and Computer Communications“, Ninth Edition, 2011SS 2012
Was bedeutet Orthogonalität bei OFDM?
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 98Bildquelle: William Stallings, „Data and Computer Communications“, Ninth Edition, 2011
SS 2012
Orthogonal Frequency Division Multiple Access
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 99Bildquelle: William Stallings, „Data and Computer Communications“, Ninth Edition, 2011
SS 2012
Zusammenfassung und Literatur
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 100SS 2012
Zusammenfassung• MAC‐Schicht ist Teil der Verbindungsebene• Kategorien
– Kollisionsbehaftet– Kollisionsfrei– Limited‐Contention
• Es gibt nicht „Das MAC‐Protokoll“; hängt z.B. ab von– Häufigkeit von Zugriffen– Anzahl Nutzer– Beispiel: CSMA versus TDMA
• Hauptkriterien für die Güte eines MAC‐Protokolls– Durchsatz– Delay– Fairness
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 101SS 2012
Literatur[Stallings2011] William Stallings, „Data and Computer Communications“, Ninth Edition, 20118.1 Frequency Division Multiplexing8.2 Synchronous Time Division Multiplexing9 Spread Spectrum14.5 Fourth‐Generation Systems
[Tanenbaum2003] Andrew S. Tanenbaum, „Computer Networks“, Fourth Edition, 20034.1 The Channel Allocation Problem4.2.1 ALOHA4.2.2 Carrier Sense Multiple Access Protocols4.2.3 Collision‐Free Protocols4.2.4 Limited‐Contention Protocols4.6.2 Wireless LAN Protocols
Grundlagen der Rechnernetze ‐ Medienzugriffskontrolle 102SS 2012