View
196
Download
4
Category
Preview:
Citation preview
Institut für Kommunikationstechnikwww.ikt.uni-hannover.de
VerkehrstheorieWartesysteme (Übung)
Kapitel 4.4
Netze und ProtokolleDipl.-Wirtsch.-Ing. Kim Bartke
(2)
Verlustsysteme / Wartesysteme (1)
Nachrichtensysteme können in Verlustsysteme und Wartesysteme unterteilt werden.Erläutern Sie die Begriffe und geben Sie Beispiele!
(3)
Verlustsysteme / Wartesysteme (2)
Verlustsystemein einfallender Belegungswunsch wird sofort bearbeitet, wenn die Ressourcen dafür zur Verfügung stehen. Sind alle Ressourcen belegt, wird der Belegungswunsch abgewiesen, er geht zu Verlust.Beispiel: Fernsprechnetz
Wartesystemein einfallender Bearbeitungswunsch wird in eine Warteschlange geschrieben und bearbeitet, sobald freie Ressourcen dafür zur Verfügung stehen. Ein Verlust tritt auf, wenn alle Warteplätze in der Warteschlange belegt sind und ein weiterer Bearbeitungswunsch eintrifft.Beispiel: Daten-Endgeräte (paketorientiert), Hotline eines Call-Centers mit Warteplätzen
(4)
Charakteristische Qualitätsparameter (1)
Was sind die typischen Qualitätsparameter für ein Verlustsystem bzw. ein Wartesystem?
(5)
Charakteristische Qualitätsparameter (2)
VerlustsystemVerlust (Blockierungswahrscheinlichkeit), d.h. derAnteil der Anforderungen, der nicht vom System bearbeitet werden kann
Wartesystemtheoretisches (reines) Wartesystem
Wahrscheinlichkeit für eine Wartezeit > Tmittlere Wartezeit
realen Wartesystems (Warte-Verlust-System)wie theoretisches WartesystemVerlustwahrscheinlichkeit (Paketverlust)
(6)
Markov-Ketten (1)
Welcher Verteilung folgen die Aufenthaltsdauern in einem Zustand in einer Markov-Kette?
Die Aufenthaltsdauern folgen einer Exponentialverteilung.
Welche besondere Eigenschaft hat der Markov-Prozess?Der Markov-Prozess zeichnet sich durch seine Gedächtnislosigkeit aus.
Was sind Geburts- und Sterbeprozesse und in welcher Beziehung stehen sie zu Markov-Prozessen?
Der Zustand k kann nur von seinem Vorgänger k-1 oder Nachfolger k+1 erreicht werden.Der Zustand k kann nur zu seinem Vorgänger k-1 oder Nachfolger k+1 verlassen werden.
(7)
Markov-Ketten (2)
Die Übergangswahrscheinlichkeiten können zustandsabhängig seinGeburts- und Sterbeprozesse sind Spezialfälle von Markov-Prozessen.
k-1 k k+1
kkP ,1− 1, +kkP
kkP ,1+1, −kkP
(8)
k Tv= ⋅λ
Die mittlere Einfallrate von Bedienwünschen
Die mittlere Verweildauer in der Warteschlange
Der mittlere Füllgrad einer Warteschlange
Little’s Law
!!!Wichtig!!! Alle Werte sind Durchschnittswerte !!!Wichtig!!!
Der Satz von Little gilt für beliebige Ankunfts- und Bedienprozesse!
Nennen und erläutern Sie Little‘s Law!Little’s Law lautet
(9)
M/M/1-Systeme
Pakete der mittleren Länge 1500 Byte kommen im Mittel alle 0.2 Sekunden in der Warteschlange eines Routers an. Wie hoch ist die Ankunftsrate?
Ankunftsrate λ = 5 Pakete / Sekunde
Wie hoch ist die Auslastung bei einer Bedienrate von36 Kbps?
Auslastung (ρ) = Ankunftsrate (λ) / Bedienrate (µ)µ = 3 Pakete / Sekundeρ = 5 [Pakete/Sek] / 3 [Pakete/Sek] = 1.67
Was für Folgen hat diese Auslastung für das System?Die Länge der Warteschlange steigt ins Unendliche.Das System wird instabil.
(10)
M/M/1-Systeme
09.911
100
11101
1110
91.01110
5.55
8*150066000
51
2
2
≈=−
⎟⎠⎞
⎜⎝⎛
=
≈====
−==
Q
Q
N
WN
μλρ
ρρλ
Wie groß muss die Bedienrate mindestens sein, um das vorherige Problem zu umgehen?
Die Auslastung muss < 1 sein, daher gilt:Bedienrate > Ankunftsrate µ > 5 Pakete/Sek
Wie groß ist die Anzahl der Pakete in der Warteschlange im Mittel bei einer Bedienrate von 66 kbps?
(11)
M/M/1-Systeme
Zur Verringerung der Wartezeit soll in einem M/M/1-System die Bedienrate eines Kanals, auf dem Datenpakete der mittleren Größe von 1500 Byte übertragen werden, von ursprünglich 66 kbps so verändert werden, dass die mittlere Wartezeit um 20% reduziert wird. Ankommende Pakete treten mit einem mittleren Abstand von 0.2s in das Wartesystem ein.
Welche Bedienrate muss gewählt werden?
(12)
M/M/1-Systeme
sTW
bpsByteL
Ank 2.0?66000
1500
1
1
=Δ===
μ
12
2
*8.0?
WW ==μ
Ausgangssituation
1
1
2 1
Pakete5Sek
10 0.9111
20W 1.81s11
16W 0.8*W 1.45s11
λ=
ρ = ≈
ρ= = ≈μ−λ
= = ≈
Berechnung
(13)
M/M/1-Systeme
22
Q2 22
2
22
80N W 7.2711 1
0.89
67350bps
ρ=λ = ≈ =
−ρρ ≈
λμ = ≈
ρ
Es muss folglich eine Erhöhung der Übertragungsrate um 1.35 Kbps durchgeführt werden.
Berechnung (Fortsetzung)
(14)
M/M/m-Systeme
Was ist ein M/M/m-System?
Bei einem M/M/m-System sind die Zwischenankunftszeiten und die Bearbeitungszeiten exponentialverteilt (M = Markov-Prozess).
Das System besitzt m Bedieneinheiten.
Das System besitzt unendlich viele Warteplätze.
(15)
M/M/m-Systeme
Zum Zeitpunkt t = 0 kommt ein Paket an einem M/M/4-System Router an. Alle Ausgangsinterfaces sind belegt und n = 19 weitere Pakete befinden sich im Wartesystem. Die Übertragung der Pakete erfolgt entsprechend der Ankunftsreihenfolge. Außerdem gilt, dass ab dem Zeitpunkt t = 0 keine weiteren Pakete in das System eintreten. Die Übertragungszeiten seien exponentialverteilt mit µ = 2.5 Pakete/Sekunde.
Bestimmen Sie die Zeit, die das letzte Paket wartet!Bestimmen Sie die erforderliche Zeit bis das System "leer" ist, ausgehend von t = 0!
(16)
M/M/m-Systeme
ssm
ts 1.0101
5.2*411
====μ
Für den Fall, dass alle m Interfaces des Routers belegt sind, gilt für die Zeit zwischen den Abfertigungszeitpunkten:
smnW etletztesPak 2
5.2*41191=
+=
+=
μ
Das letzte Paket muss so lange warten, bis n+1 Abfertigungen erfolgt sind:
(17)
M/M/m-Systeme
sT
mmnT
Systemleer
Systemleer
83.26
175.2*1
15.2*2
15.2*3
15.2*4
15.2*41191...11
≈=Δ
+++++
=++++
=Δμμμ
m-1 m m+10 1 2
λτ
μτ 2μτ (m-1)μτ
λτ λτ λτ λτ
mμτ mμτ
mnpmpmnpnp
nn
nn
≥=<=
−
−
1
1
μλμλ
Die Summe der Wartezeit des letzten Paketes und der Bedienzeit sämtlicher Pakete bestimmt sich durch:
(18)
Geschafft…
Gibt es noch Fragen?
Recommended