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?