Upload
hoangcong
View
212
Download
0
Embed Size (px)
Citation preview
P‐Persistent‐CSMABeispiel:
Höre in den Kanal
Start
1 2 3
Kanal frei?
nein Warte einenZeit Slotfrei?
Senden?
ja
Zeit‐Slot
Warte einen Zeit‐l d d
nein(mit WK p) Slot und dann
höre in den Kanal
nein
ja
Kanal frei?
Sende Paketja
nein
Kollision?ja Warte zufällige
Zeit
nein
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 40Ende
nein
SS 2012
Quiz: Feststellen einer Kollision?Beispiel:
1 2 3
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 41SS 2012
Durchsatz versus angebotene LastWir analysieren nur den einfachsten Fall: Nonpersistent‐CSMA
A hAnnahmen:• Gesamtrate an Nachrichten (d.h. neue und reübertragene) sei G• Ankunftsrate der Nachrichten sei Poisson‐VerteiltAnkunftsrate der Nachrichten sei Poisson Verteilt
(das ist eine vereinfachende Annahme)• Propagation‐Delay sei a Zeiteinheiten• Eine Paketübertragung dauert 1 Zeiteinheit
W i t d D h t S üb di b t L t G?Was ist der Durchsatz S über die angebotene Last G?
Betrachte die Zufallsgrößen: S Das IdealBetrachte die Zufallsgrößen:• B = Länge einer „Busy‐Periode“• I = Länge einer „Idle‐Periode“
S1
Das Ideal
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 42
• C = Länge eines „Busy‐Idle‐Zyklus“ 1 G
SS 2012
Durchsatz von ALOHA und CSMA
Grundlagen der Rechnernetze - Medienzugriffskontrolle 44Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
CSMA mit Kollisionsdetektion: CSMA/CDBeispiel:
Start1 2 3
1‐PersistentP‐PersistentP PersistentNonpersistent
Starte Paketübertragung
Kollisionderweil?
ja Stoppe Paketübertragung
Ende
nein
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 45SS 2012
Binary‐Exponential‐Backoff
Setze maximale Anzahl Slots N auf 2
Start
LetztesNächstes Frame
Contention‐Periode
Wähle einen zufälligen Zeit‐Slot k in {0,...,N‐1} und starte
Slots N auf 2 FrameNächstes Frame
{ , , }Übertragung zum Slot k
neinKollision?
nein
ja
Setze N auf 2*N,wenn N<1024
Mehr als 16 Versuche?
Bemerkung: dies sind die Parameter aus Ethernet.Die Länge eines Zeitslotsja
nein
Die Länge eines Zeitslots wird auf 2*Maximum‐Propagation‐Delay
Teile höherer Schicht mit, dass Paket nicht ausstellbar
ja
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 46
Propagation Delay festgelegt.Ende
SS 2012
Quiz: warum 2*Propagation‐Delay?
1 2…Maximales Propagation‐Delay sei
1 2
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 erstem Slot der Kanal einem Knoten sicher i D k k i K lli i h t ttfi d
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 47
zugewiesen. Dann kann keine Kollision mehr stattfinden.
SS 2012
CD erfordert MindestpaketlängeBetrachte ein sehr kurzes Paket und etwas längeres Paket:
Sender 1Sender 1
Empfänger 1
Also: Paket sollte groß genug sein, damit Sender die Kollision
Sender 2
g g g ,erkennen kann. Es sei p der maximale Propagation‐Delay und d die Datenrate. Welche Größe g sollte das Paket mindestens haben?
SS 2012 Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 48
Multiple‐Access‐Protokollell f d d k llKollisionsfreie und Limited‐Contention Protokolle
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 49SS 2012
Bit‐Map‐Protokoll• 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• Jeder knoten hat eine eindeutige Nummer zwischen 0 und N‐1
Was ist Kanaleffizienz (Nutz‐Bits über insgesamt gesendete Bits)?Was ist Kanaleffizienz (Nutz Bits über insgesamt gesendete Bits)? N=Anzahl Slots; jeder Slot ein Bit; d=Anzahl Daten‐BitsBei geringer Last:
Bei hoher Last:
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 50Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Binary‐CountdownBinary‐Countdown am Beispiel Was ist Kanaleffizienz (Nutz‐
Bits über insgesamt gesendete Bits)?
Bei geringer Last:Bei geringer Last:
Bei hoher Last:
Wenn die Bits am Anfang als Adresse des Absenders Teil derAdresse des Absenders Teil der Nachricht sind:
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 51Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Wie erreicht man Fairness bei Binary‐Countdown?P bl K t it öß Ad t d b tProblem: Knoten mit größeren Adresswerten werden bevorzugt.
Idee: Binary‐Countdown nach PrioritätswertenIdee: 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 D A G B E FKnotenadressen: C H D A G B E FPrioritäten: 7 6 5 4 3 2 1 0
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 52SS 2012
Limited‐Contention‐ProtokolleP t k ll it C t ti ( B ALOHA CSMA)Protokolle mit Contention (z.B. ALOHA, CSMA)• Geringe Latenz bei geringer Last aber• schlechte Kanaleffizienz bei hoher Lastschlechte 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 Contentionbei 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?
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 53SS 2012
Erfolgswahrscheinlichkeit einer Übertragung
• Also: die Performance degradiert auch schon bei wenigen übertragenden Knoten recht schnell.g
• Idee: Versuche alle Teilnehmer in kleine Gruppe einzuteilen.• Jede Gruppe kommt mal dran.
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 54
• Contention findet nur innerhalb der Gruppe statt.Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Adaptive‐Tree‐Walk‐Protokoll
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 55Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012
Adaptive‐Tree‐Walk‐ProtokollLevel 0
Level 1
Level 2Level 2
Grundlagen der Rechnernetze ‐Medienzugriffskontrolle 56Bildquelle: Andrew S. Tanenbaum, Computer Networks, 4th Edition, 2003
SS 2012