Blatt 4

UNIVERSITÄT ULM
Fakultät für Informatik
Verteilte Systeme
Prof. Dr. Peter Schulthess
Moritz Wende
Dr. Andreas Kassler
Andreas Schorr
hEXQJ]XU9RUOHVXQJ5HFKQHUQHW]H
Abgabe am Dienstag, 07.01.2003 in der Übung
$XIJDEH(IIL]LHQ]YRQ6WRSDQG:DLW3XQNW
Ein Kanal besitzt eine Datenrate von 64kbps und eine Signallaufzeit von 20ms. Für welche Paketgrößen ergibt sich
eine Effizienz des Stop-and-Wait Protokolls von mindestens 50%? (Die Länge der Acknowledgements sei
vernachlässigbar und es treten keine Paketfehler auf.)
$XIJDEH+'/&3XQNWH
Sie wollen Daten über einen 1,5mbps Kommunikationskanal zum Mond übertragen und verwenden dabei das
HDLC Protokoll. HDLC kann im Go-Back-N oder Selective-Reject Modus betrieben werden. Die
Sequenznummern werden modulo 8 hochgezählt. Welches ist in den beiden Modi jeweils die kleinstmögliche
Paketgröße L, um eine ununterbrochene Übertragung zu garantieren? (Die Entfernung von der Erde zum Mond
beträgt 375.000km, und die Lichtgeschwindigkeit beträgt 3*108m/ sec.)
$XIJDEHhEHUWUDJXQJYRQ$XGLRVWU|PHQ3XQNWH
Sie wollen eine Sequenz von Paketen fester Größe, welche Audiodaten enthalten, über ein Netzwerk übertragen.
Genau alle 10 ms wird ein solches Paket erzeugt und abgeschickt. Die ersten 10 Pakete kommen mit folgenden
End-zu-End Delays beim Empfänger an: 45ms, 50ms, 53ms, 46ms, 30ms, 40ms, 46ms, 49ms, 55ms und 51ms.
Beim Empfänger sollen die Daten nach einem konstanten End-zu-End Delay von 75ms verarbeitet und auf dem
Lautsprecher ausgegeben werden.
a) Geben Sie die Reihenfolge an, in der die Pakete beim Empfänger ankommen. Geben Sie für jedes der
ersten 10 Pakete an, wie lange es verzögert werden muss, um den konstanten End-zu-End Delay von
75ms zu garantieren.
b) Skizzieren Sie, wie viele Pakete sich im Puffer beim Empfänger in Abhängigkeit von der Zeit t
befinden.
$XIJDEH$543URWRNROOH3XQNWH
Aufgrund der Komplexität von Selective Reject ARQ wird es selten eingesetzt. Betrachten wir die Unterschiede
zwischen lokalen Netzen (LANs) mit typischerweise 10 mbps Geschwindigkeit und optischen Netzen mit
typischerweise 1 Gbps, wie sie im Moment in den Backbones eingesetzt werden. In dieser Aufgabe soll analysiert
werden, ob sich die Komplexität von Selective Reject in einem Gigabit Netzwerk lohnt. Die Effekte von Go-backN im Vergleich zu Selective Reject ARQs auf die Performance in dieser Umgebung soll betrachtet werden. Dazu
analysieren wir 3 Fälle.
)DOO Ein Ethernet Netzwerk wird installiert zwischen zwei Knoten, die sich 3 km voneinander entfernt
befinden. Betrachten Sie ein „billiges“ Ethernet mit einer Geschwindigkeit von 10 mbps im Vergleich zu einem mit
einer Geschwindigkeit von 100 mbps (1 mbps = 1.000.000 bps). Der Overhead für Ethernet betrage 24
Bytes/ Paket. Die Größe der Acknowledgements betrage 16 Bytes.
)DOO In USA hat Sprint ein Glasfasernetzwerk installiert, welches mit 500 mbps und mit 1 gbps betrieben
werden kann. Betrachten Sie 2 Rechner, die 3000 km voneinander entfernt sind. Der Overhead für dieses
Hochgeschwindigkeitsnetz ist 24 Bytes/ Paket. Die Größe der Acknowledgements betrage 16 Bytes.
)DOO In einer Großstadt wird ein ISDN Netzwerk mit 64 kbps installiert. Die maximale Punkt-zu-Punkt
Entfernung betrage 10 km. Das ISDN kann auch mit 128 kbps betrieben werden. Der Overhead für ISDN betrage
24 Bytes/ Paket. Die Größe der Acknowledgements betrage 16 Bytes.
Folgende Annahmen seien getroffen:
• Die Ausbreitungsgeschwindigkeit im Medium sei 2x108 m/s
• Die Wahrscheinlichkeit eines einzelnen Bitfehlers sei 3 = 10-6 .
• ACKs und NACKs werden immer korrekt empfangen.
•
Es gelten folgende Beziehungen, wobei die Laufzeit von ACKs nicht berücksichtigt ist. a =
w=Fenstergröße, p= Paketfehlerwahrscheinlichkeit.
U(Stop And Wait, p) =
3523
,
75$163
1− S
1 + 2D
Z(1 − S)
(2D + 1)(1 − S + ZS )
Z(1 − S )
U(SelectiveReject, p, w) =
( 2D + 1)
U(Go - Back - N - ARQ, p, w) =
a) Leiten Sie die Formeln der Effizienz für Stop-And-Wait ARQ, Go-Back-N-ARQ und Selective Reject unter
Berücksichtigung der Übertragungszeit von ACKs her. Dabei gehen Sie wie in der Vorlesung von
p= Paketfehlerwahrscheinlichkeit aus.
b) Verwenden Sie jetzt Excel, Matlab oder ein anderes Tool Ihrer Wahl um die Fälle 1, 2 und 3 zu simulieren,
basierend auf folgenden Angaben:
a. Für Stop And Wait: Bestimmen und Zeichnen Sie die Effizienz als Funktion der Paketgröße, in dem
Sie die Paketgröße von 500 bits bis 12.000 bits (1500 bytes) variieren. Dies ergibt insgesamt 3 Graphen
(pro Fall 1 Graph), wobei jeder Graph 2 Kurven enthält.
b. Für Go-Back-N: Bei fixer Paketgröße von 500 bits bzw. 1500 Bytes, bestimmen und zeichnen Sie die
Effizienz als eine Funktion der Fenstergröße, die zwischen 7 und 127 variiert. Dies ergibt 2 Graphen
(einen für 500 bits und einen für 1500 Bytes) mit je 6 Kurven (3 Fälle zu je 2 Varianten).
c. Für Selective Reject: Bei fixer Paketgröße von 500 bits bzw. 1500 Bytes, bestimmen und zeichnen Sie
die Effizienz als eine Funktion der Fenstergröße, die zwischen 7 und 127 variiert. Dies ergibt 2
Graphen (einen für 500 bits und einen für 1500 Bytes) mit je 6 Kurven (3 Fälle zu je 2 Varianten).
Verwenden Sie die Ergebnisse aus b) um folgende Fragen zu beantworten.
c) Plotten Sie Durchsatz (Effizienz * Max_Data_Rate) versus Paketgröße für jedes ARQ Schema. Wie verhält sich
der Durchsatz mit zunehmender Paketgröße?
d) Was ist der maximale Durchsatz für jedes ARQ Protokoll für jeden Fall? Für welche Paketgröße wurde dies
erzielt?
e) Was für einen Zusammenhang vermuten Sie zwischen Fenstergröße, Durchsatz und Paketgröße?