Übung 4 - CCS Labs

Übungen zu „Rechnerkommunikation“
Wintersemester 2010/2011
Übung 4
Mykola Protsenko, Jürgen Eckert
PD. Dr.-Ing. Falko Dressler
Friedrich-Alexander
d h l
d Universität Erlangen-Nürnberg
l
b
Informatik 7 (Rechnernetze und Kommunikationssysteme)
Rechnerkommunikation, Übung 4
1
Übung 4: Stop-and-Wait, Go-Back-N, Selective Repeat
 UML-Statecharts
 Leistungsanalyse
 ohne Fehler:
- Stop-and-Wait
- Schiebefensterprotokolle (Go-Back-N, Selective Repeat)
 mit Fehler
- Selective Repeat
- Go-Back-N
Go Back N
Wichtige Begriffe:
 normierter Durchsatz (= Leitungsauslastung)
 Sequenznummernraum
Rechnerkommunikation, Übung 4
2
UML-Statecharts
 ein Statechart befindet sich immer in einem Zustand,
d schwarze
der
h
Punkt
k kennzeichnet
k
i h
den
d initialen
i i i l Zustand
d
 ein Zustandsübergang findet statt, wenn das Ereignis
ausgelöst wurde und die Bedingung erfüllt ist
 wenn ein Zustandsübergang stattfindet, wird die Aktion
durchgeführt
g
 zur Steigerung der Flexibilität gibt es auch Variablen
Ereignis[Bedingung]/Aktion
/Aktion
Zustand
1
Rechnerkommunikation, Übung 4
Zustand
2
3
UML-Statecharts
 Verzweigung
 Zustand
Zustand, in dem keine Zeit verbracht wird ((„Pseudozustand
Pseudozustand“))
 abgehende Zustandsübergänge werden mittels Bedingungen gewählt,
auslösende Ereignisse sind hier nicht möglich
[Bedingung1]/Aktion1
[[Bedingung2
g g ]/
]/Aktion2
Rechnerkommunikation, Übung 4
4
Stop-and-Wait
Sender
rdt_send(data)/
pkt=pkt(SQN,data,CRC);
udt_send(pkt);
udt_rcv(ACK)
startt_ttimer
sta
e
[biterror(ACK) 
SQN(ACK)SQN)]/
/SQN=1
wait for
d t
data
udt_rcv(ACK)/
Empfänger
wait for
ACK
udt_rcv(pkt)
[¬biterror(pkt)  SQN(pkt)=SQN]/
data=extractdata(pkt);
rdt rcv(data);
rdt_rcv(data);
ACK=ACK(SQN,CRC);
udt_send(ACK);
SQN++
timeout/
udt_send(pkt);
start_timer
udt_rcv(ACK)
[¬biterror(ACK)  SQN(ACK)=SQN]/
stop_timer;
SQN++
wait for
packet
/SQN=1;
ACK=ACK(0,CRC)
udt_rcv(pkt)
[biterror(pkt) v SQN(pkt)SQN]/
udt_send(ACK)
Rechnerkommunikation, Übung 4
5
Leistungsanalyse:
g
y
Stop-and-Wait
p
 Vernachlässigung der ACK-Sendezeit
ACK Sendezeit
und Bearbeitungszeiten
(sinnvolle vereinfachende Annahme
für diese Berechnungen)
 p
pro Zeit gesendete
g
Bits: Durchsatz 
L/R
2D
L/R
2D
L
L / R  2D
…
 Stop-and-Wait ohne Fehler
 normiert durch die Bitrate (gut für Vergleich bei verschiedenen Bitraten):
normierter Durchsatz  S 
L
1
1
1
 

L / R  2D R 1  2RD / L 1  2a
wobei a = Kanalpuffergröße in Paketen
Paketen, d.h.,
dh a
S
1
1 2a
1
Rechnerkommunikation, Übung 4
RD
D

L
L /R
 schlechter Durchsatz
u
a für
ü große
go a
(Kanal kann nicht gefüllt werden)
6
Übung 4.1
 Betrachten Sie eine Halbduplex-Punkt-zu-Punkt-Verbindung,
für die das Stop-and-Wait-Verfahren
Stop and Wait Verfahren eingesetzt wird
wird.
 Was g
geschieht mit der Leitungsauslastung
g
g (=
( normierter Durchsatz S),
),
wenn die Größe der Nachrichten (Objekte) erhöht wird? Die anderen
Parameter, inkl. der Paketgröße, sollen nicht verändert werden.
 Welche Auswirkung auf die Auslastung der Leitung kann man beobachten,
wenn die Anzahl der Pakete bei konstanter Nachrichtengröße erhöht wird?
 Welche Auswirkung auf die Auslastung der Leitung hat eine Vergrößerung
der Pakete?
Rechnerkommunikation, Übung 4
7
Übung 4.2
 Ein Kanal hat
 eine Datenrate von 4
4,0
0 kbps und
 eine Ausbreitungsverzögerung von 20 ms.
Für welchen Bereich von Paketgrößen
g
hat das Stop-andp
Wait-Verfahren eine Effizienz von mindestens 50%?
Rechnerkommunikation, Übung 4
8
Stop-and-Wait
 Sequenznummerraum
 die Repräsentation der Sequenznummern ist endlich:
ein Feld mit n Bits ermöglicht m = 2n Sequenznummern
 Wiederverwendung durch zyklisches Durchlaufen
 für Stop-and-Wait:
ein Bit ist zur Darstellung von 2 Sequenznummern ausreichend: 0 und 1
 Stop-and–Wait mit 0 und 1 als Sequenznummern heißt auch
Alternating-Bit-Protokoll
Rechnerkommunikation, Übung 4
9
Übung 4.3
 Warum werden beim Alternating-Bit-Protokoll keine
speziellen NAK0
NAK0- und NAK1
NAK1-Nachrichten
Nachrichten benötigt?
 zur Erklärung:
NAK: No Acknowledgment / Negative Acknowledgment
- zur Ablehnung übertragener Daten ab, z.B. bei fehlerhaftem Empfang
- bei NAK
NAK-Empfang
Empfang kann Sender entsprechende Pakete nochmals
übertragen
Rechnerkommunikation, Übung 4
10
Leistungsanalyse: Schiebefensterprotokolle
 Schiebefensterprotokolle ohne Fehler
 für Fenstergröße mit W Paketen der Länge L
 Fall 1: das Fenster ist nicht groß genug um zu senden,
bis ACK zurückkommt
Sender
W L L
  2D
R
R
WL/R
W=2
Empfänger
L/R
2D
ACK
- Bedingung:
L / R  2D
W
 1  2a
L/R
ACK
- normierter Durchsatz:
S
W L
1
W
 
L / R  2D R 1  2a
Rechnerkommunikation, Übung 4
11
Leistungsanalyse: Schiebefensterprotokolle
 Schiebefensterprotokolle ohne Fehler
 Fall 2: das Fenster ist g
groß genug
g
g um zu senden,, bis ACK zurückkommt:
W L L
  2D
R
R
- Bedingung:
L / R  2D
W 
 1  2a
L /R
- normierter Durchsatz:
W L 1
S
 1
W L /R R
WL/R
Sender
W=3
Empfänger
L/R
2D
ACK
ACK
 Zusammenfassung:
 1
S W
1  2a
Rechnerkommunikation, Übung 4
W  1  2a
W  1  2a
12
Übung 4.4
 Auf einer Satellitenverbindung mit
 1
1,0
0 Mbps und
 270 ms Verzögerung
sollen Pakete
 der Größe 1000 Bits
eingesetzt werden.
 Wie hoch ist die maximale Auslastung der Verbindung bei




Stop-and-Wait-Flusskontrolle?
Schiebefenster Flusskontrolle mit einer Fenstergröße von 7 Paketen?
Schiebefenster-Flusskontrolle
Schiebefenster-Flusskontrolle mit einer Fenstergröße von 127 Paketen?
Schiebefenster-Flusskontrolle mit einer Fenstergröße von 255 Paketen?
Rechnerkommunikation, Übung 4
13
Übung 4.5
 Die Abbildung unten stellt drei Hosts dar.
Pakete werden bei Host A erzeugt und über B nach C versendet.
B ti
Bestimmen
Si
Sie die
di minimale
i i l Übertragungsrate
Üb t
t zwischen
i h B und
d C,
C
bei der die Puffer bei Knoten B nicht überlaufen, wenn folgende
Voraussetzungen gelten:
Die Datenrate zwischen A und B beträgt 100 kbps.
Die spezifische Ausbreitungsverzögerung beträgt 10 µs/km bei beiden Verbindungen.
Die Leitungen unterstützen Vollduplex-Betrieb.
Alle Datenpakete sind 1000 Bits groß
groß. ACK-Pakete
ACK Pakete haben eine vernachlässigbare
Größe.
 Zwischen Host A und B wird ein Schiebefensterprotokoll mit einer Fenstergröße von
3 Paketen verwendet.
 Zwischen Host B und C wird Stop-and-Wait verwendet.
 Es treten keine Fehler auf.
2000 km
500 km




A
B
C
 Tipp:
Damit die Puffer bei B nicht überlaufen
überlaufen, muss bei Host B die Anzahl der in einem
langen Intervall ankommenden Pakete gleich der Anzahl der abgehenden Pakete sein.
Rechnerkommunikation, Übung 4
14
Selective Repeat
 informelle Beschreibung des Protokolls
 Verhalten des Senders
1. wenn Daten zum Senden und Platz im Fenster:



sende Paket
starte Timer für dieses Paket
inkrementiere nextSQN
2. wenn ein ACK ohne Bitfehler und mit SQN im Fenster zurückkommt:


markiere das Paket mit SQN als bestätigt
schiebe das Fenster bis zur nächsten Lücke
3. wenn
3
e de
der Timeout
eout für
ü das Paket
a et mitt SQ
SQN ab
abläuft:
äu t


sende dieses Paket erneut
starte den Timer für dieses Paket erneut
nextSQN
Sendeseite: 1 2 3 4 5 6 7 8
Rechnerkommunikation, Übung 4
base
base+W-1
15
Selective Repeat
 informelle Beschreibung des Protokolls
 Verhalten des Empfängers
1. wenn Paket ohne Bitfehler und mit SQN im Fenster ankommt:
•
•
•
sende ACK mit dieser SQN
puffere das Paket
schiebe das Fenster bis zur nächsten Lücke
2. wenn Paket mit SQN aus vorigem Fenster ankommt:
•
sende das ACK hierfür erneut
Empfängerseite:
1 2 3 4 5 6 7 8
base
Rechnerkommunikation, Übung 4
base+W-1
16
Übung 4.6
 Nehmen Sie an, dass ein Selective-Repeat-Schema mit
W 4 zur Übertragung benutzt wird
W=4
wird.
Veranschaulichen Sie anhand eines Beispiels, dass
S
Sequenznummern
mit
it 3 Bits
Bit genügen.
ü
Rechnerkommunikation, Übung 4
17
Übung 4.7
 Knoten tauschen Pakete
 von fester Größe L Bits
auf einem Kanal mit
 Datenrate von R bps,
 Ausbreitungsgeschwindigkeit c und
 einer Länge l
aus.
 Bestimmen Sie eine Formel für die minimale Größe des
Sequenznummernfeldes (Anzahl der benötigten Bits) in
Abhä i k i von R, l,
Abhängigkeit
l c und
d L, bei
b i der
d die
di maximale
i l
Auslastung der Verbindung berücksichtigt wird.
 Dazu können Sie annehmen,
annehmen dass
 ACK-Pakete eine vernachlässigbare Größe besitzen und
 die Verarbeitung in den Knoten unmittelbar geschieht
(d.h. keine Zeit benötigt).
Rechnerkommunikation, Übung 4
18
Leistungsanalyse:
g
y
Schiebefensterprotokolle
p
 Selective Repeat mit Fehlern
 Annahme: unabhängige Fehler mit Wahrscheinlichkeit p
 N = E[Sendeversuche] = 1/(1-p)
 de
der Durchsatz
u c sat im fehlerfreien
e e e e Fall
a muss
uss du
durch
c N gete
geteiltt werden:
e de
1
1

W  1  2a
N 1 /(1  p)  1  p
S
W
W
W(1  p)



W  1  2a
N  (1  2a) 1 /(1  p)  (1  2a)
1  2a
 1  p
S   W(1  p)
 1  2a
Rechnerkommunikation, Übung 4
W  1  2a
W  1  2a
19
Leistungsanalyse:
g
y
Schiebefensterprotokolle
p
 Go-back-N mit Fehlern
 jeder
j
Fehler erfordert eine Sendewiederholung
g von K Paketen
 Annahme: im Fehlerfall ist das Fenster gefüllt und alle Pakete des
Fensters müssen erneut gesendet werden, dann:
1  2a W  1  2a
K
W  1  2a
 W
 wenn das fehlerhafte Paket i-mal gesendet wird, müssen insgesamt
1+(i-1)K = (1-K)+Ki Pakete gesendet werden
 N

 ((1  K )  Ki)  p
i1
i1

 (1  p)  (1  K )(1  p) p
i1
i1

 K (1  p) i  pi1
i1

1
1
  i
 (1  K )(1  p) p  K (1  p)  p   (1  K )(1  p)
 K (1  p)
1p
(1  p)2
i 0
 i0 
K
1  p  Kp
1K 

1p
1p

Rechnerkommunikation, Übung 4
i
20
Leistungsanalyse:
g
y
Schiebefensterprotokolle
p
1  p  Kp 1  p  (1  2a)p 1  2ap

 1  p 
1 p
1 p
 mit K erhalten wir: N  
1  p  Kp 1  p  Wp


 1  p
1 p
W  1  2a
W  1  2a
 Division des Durchsatzes ohne Fehler durch N ergibt:
1p
1

N 1  2ap
S
W
W(1  p)


N  (1  2a) (1  p  Wp)  (1  2a)
 1p
1  2ap
S
W(1  p)

(1  p  Wp)  (1  2a)
Rechnerkommunikation, Übung 4
W  1  2a
W  1  2a
W  1  2a
W  1  2a
21
Leistungsanalyse:
g
y
Schiebefensterprotokolle
p
 normierter Durchsatz von Go-Back-N und Selective Repeat als Funktion
von a,
a p = 10-11:
Rechnerkommunikation, Übung 4
22
Aufgabe - Übung 4.8
 Ein Webserver empfängt üblicherweise relative kleine
Nachrichten (Requests) von den Clients
Clients, überträgt aber
möglicherweise sehr große Objekte als Antwort an die
Cli t
Clients.
 Welches ARQ-Protokoll (Automatic Repeat Request),
d h Selective
d.h.,
S l ti Repeat
R
t oder
d Go-back-N,
G b k N würde
ü d besonders
b
d
populäre Webserver am wenigsten belasten? Warum?
Rechnerkommunikation, Übung 4
23
Aufgabe - Übung 4.9
 Zeichnen Sie die Leitungsauslastung (= normierter
Durchsatz S) als Funktion der Fehlerwahrscheinlichkeit p
für folgende Fehlerkontrollmechanismen.





Stop-and-Wait
Go-back-N mit W = 7
Go-back-N mit W = 127
Selective Repeat mit W = 7
Selective Repeat mit W = 127
Orientieren Sie sich dazu an dem vorigen Graph.
 Nehmen Sie für die Kanalpuffergröße a folgende Werte an:
 0.1
 1
 10
Welche Technik ist für die jeweiligen Werte von a die beste?
Rechnerkommunikation, Übung 4
24