[8] Nu P 04 3

© UNI Hannover, Institut für Allgemeine Nachrichtentechnik

Institut für Kommunikationstechnikwww.ikt.uni-hannover.de

VerkehrstheorieWartesysteme

Kapitel 4.3

Netze und ProtokolleDr.-Ing. Jan Steuer


(2)

Inhalt

EinführungLittle‘s LawMarkov-KettenM/M/1-SystemM/M/m-System (Wartesystem)Warteschlangennetze


(3)

Problemstellung

Dimensionierung von Nachrichtennetzenneue Netze

Schätzung der Angebotsparameter, Definition der Qualitätsparameter, Ermittlung der Kosten; Design des Netzes, Struktur, Wegewahl , Berechnung der Kanalzahlen

existierende NetzeMessung der Angebotsparameter, der realen Qualitätsparameter, Prüfung der Meßwerte gegen die Planwerte (Soll-/Ist-Vergleich), Anpassung der NetzstrukturAngebotsparameter: Verteilung (Mittelwert, Varianz)

Qualitätsparameter: Verlust, Wartezeiten, (Mittelwert, Varianz)Netzstruktur, Redundanz

Die Verkehrstheorie ist die mathematische Beschreibung des Teilnehmerverhaltens mit der Hilfe der Statistik. Häufig sind die Quellen des Fernsprechverkehrs die Fernsprechteilnehmer, die Quellen können aber auch Einrichtungen des Netzes, wie Register, Mailsysteme oder andere sein. Durch die Versuche, miteinander in Verbindung zu treten, und durch die Gespräche erzeugen sie den Verkehr. Ihr Verhalten, d. h., zu welchen Zeitpunkten und wie oft sie solche Versuche unternehmen, wie lange sie dabei und während der Gespräche die Vermittlungseinrichtungen in Anspruch nehmen, gibt dem Verkehr hauptsächlich seine Eigenschaften. Mit diesen ,,ursprünglichen” Eigenschaften und deren Beeinflussung durch die vermittlungstechnischen Einrichtungen befaßt sich die Verkehrstheorie; diese gibt der Vermittlungstechnik die Möglichkeit, ihre Anlagen dem Verkehr entsprechend wirtschaftlich zu dimensionieren.Ziel ist es die Ressourcen (Vermittlungssysteme, Übertragungssysteme, Supportsysteme) so zu dimensionieren, daßdie Kosten minimal sind bei gegebenen Qualitätsparametern. Die Qualitätsparameter, die mittels der Verkehrstheorie bestimmt werden sind:

der Verlust in der Hauptverkehrsstunde (Mittelwert, Varianz)die Wartezeit in der Hauptverkehrsstunde (Mittelwert, Varianz)

Die Behandlung von existierenden Netzen und Systemen ist einfacher als die Dimensionierung von neuen Einrichtungen, da in den vorhandenen Systemen das Verhalten der Quellen direkt gemessen werden kann, während für neue Systeme die Eigenschaften der Quellen aufgrund von Erfahrungswerten festgelegt werden müssen. Um von den Erfahrungswerten zu den realen, im Einzelfall vorhandenen Werten zu kommen, sind häufig mehrere Iterationen erforderlich.

Die Netzoptimierung wird vom Quellenverhalten, von der Netzstruktur, einschließlich geographischer Gegebenheiten, und den Forderungen aus der Sicherheit des Betriebes (Redundanz) beeinflußt.


(4)

Schätzung oder Messung der zu optimierenden

Parameter

Optimierungs-kriterium

erfüllt?

ja

Struktur eines Festnetzesfestlegen (Knotenzahl,

Bündelzahl, Leitweglenkung)

nein

Zielfunktionberechnen

Ende

Netzoptimierung

Die Netzoptimierung ist ein iterativer Prozeß, der durchaus mehrere Monate benötigen kann, bevor er in ein Gleichgewicht kommt. Das System oder Netz wird ausgehend von der ersten Schätzung aufgebaut und bezüglich seiner Leistungsfähigkeit nachgemessen. Anschließend erfolgt mit den dann gemessenen Quellendaten eine neue Berechnung des Netzes und daraus resultierend eine korrigierte Zusammenschaltung. Am Anfang einer Netznutzung kann sich auch das Quellverhalten noch stark ändern, so daß die Korrekturen mehrfach vorgenommen werden müssen. Auch bei einem Netz im Gleichgewichtszustand empfiehlt sich die periodische Kontrolle der Quellparameter, um sich an Änderungen anzupassen. Die Kontrollen können beispielsweise jährlich erfolgen.Bei der Beschaffung der Systeme ist darauf zu achten, daß die Netzelemente über Meßhilfen zur Erfassung ihrer Verkehrsdaten verfügen.


(5)

1

N

2

A

Y

n

t

N A YR

Verlustsystem

Abweisen von Anforderungen, falls keine Bedienstation frei istQualitätsparameter

VerlustwahrscheinlichkeitBeispiele: ISDN, POTS

Merkmale eines VerlustsystemsAbweisen von Anforderungen, falls keine Bedieneinheit frei istQualitätsparameter: Verlust (Blockierungswahrscheinlichkeit), d. h. derAnteil der Anforderungen, die nicht vom System bearbeitet werden kannBeispiele

ISDN (diensteintegrierendes digitales Netz)analoges Telefonnetz (POTS, plain old telephony Service)


(6)

Qualitätsparameter:- Wartewahrscheinlichkeit > T- mittlere Wartezeit- Verlustwahrscheinlichkeit

Anwendung:X.25, ATM, Lokale Netze

A, λ Y Y

M Warteplätze

Warteschlange

N Bedieneinheiten (μ)

z. B. Leitungen, Kanäle

μλρ =

Verkehrsintensität oder Ausnutzung:

Wartesystem

λ Einfallrate für Bearbeitungswünscheµ Bearbeitungsrate

Merkmale eines theoretischen (reinen) Wartesystemskeine Abweisung von Anforderungen, sondern Speicherung in einer Warteschlangeunendliche Länge der WarteschlangeQualitätsparameter :

Wartewahrscheinlichkeitmittlere WartezeitWahrscheinlichkeit für eine Wartezeit > T

Merkmale eines realen Wartesystems (Warte-Verlust-System)keine Abweisung von Anforderungen, sondern Speicherung in einer Warteschlangeendliche Länge der Warteschlange, die als Speicher realisiert werden kannQualitätsparameter:

siehe theoretisches Wartesystemzusätzlich Blockierungswahrscheinlichkeit

BeispieleX.25 (z. B. in Form des Datex-P-Dienstes der Telekom AG)Asynchroner Transfer Modus (ATM)Lokale Netze (LAN)

Verkehrsintensität oder Ausnutzungwichtige Größe zur Berechnung der SystemeStabilitätskriterium: l<m oder r<1 (instabil für l→m) (s. Schwartz, S. 21ff)


(7)

Ankünfte

Arrivals

Warteschlange

Queue Server

Bedieneinheit Ausgangabgehend

Outputleaving

Wir sprechen allgemein von „Kunden“ im System. Beispiele:

• Schlange an der Kasse im Supermarkt• Zu- und Abfluss in einem Gasspeicher• Zu- und Abfluss in einem Wasserturm• Anfragen an einen Dateiserver (Computernetz)• Bedienen von Jobs in einem Multitasking-Computer• Pakete in einem Datenkommunikationssystem• Anrufe in einem Sprachkommunikationssystem (z.B. auch Callcenter)

Systemmodell

Consider the simplest model of a queue, as depicted in Fig. 2— 1. To keep the discussion concrete, the queue in this case is shown handling packets of data. These packets could also be calls queuing up for service in a circuit-switched system. More generally, in the queuing literaturejargon, they would be ,,customers” queuing up for service. The packets arrive randomly, at an average rate of l packets/time (we shall use units of packets/sec most often). They queue up for service in the buffer shown and are then served, following some specified service discipline, at an average rate of µ packets/time. In the example of Fig. 2— 1, only a single server is shown. More generally, multiple servers may be available, in which case more than one packet may be in service at any one time.The concept of a server is of course well known to all of us from innumerable waits at the supermarket, bank, movie house, automobile toll booth, and so forth. In the context of a data network, the server is the transmission facility— an outgoing link, line, or trunk (all three terms will be used interchangeably in the material following) that transmits data at a prescribed digital rate of C data units/time. Most frequently, the data units are given in terms of bits or characters, and one talks of a transmission rate or link capacity C in units of bits/sec or characters/sec. A transmission link handling 1000-bit packets and transmitting at a rate of C= 2400 bps, for example, would be capable of transmitting at a rate of µ = 2.4 packets/sec. More generally, if the average packet length in bits is 1/µ‘ bits, and is given in units of bits/packet, µ = µ´C packets/sec is the transmission capacity in units of packets/sec. (For circuit-switched calls, the ,, customer”would be a call; 1 arrivals/sec represents the average call arrival rate, or the number of calls/sec handled on the average. The parameter 1/µ, in units of sec/call, is called the average call holding time.)lt is apparent that as the packet arrival rate l approaches the packet rate capacity µ, the queue will start to build up. For a finite buffer (the situation in real life), the queue will eventually saturate at its maximum value as l exceeds m and continues to increase. If the buffer is filled, all further packets (customers) are blocked on arrival. We shall demonstrate this phenomenon quantitatively later in this chapter. If for simplicity the buffer is assumed to be infinite (an assumption we shall make often to simplify analysis), the queue becomes unstable as l > µ. We will show that l <µ to ensure stability in this case of a single server queue. In particular, we shall find the parameter r = l/µ playing a critical role in queueinganalysis. This parameter is often called the link utilization or traffic intensity. Note that it is defined as the ratio of loadon the system to capacity of the system. For a single-server queue, as p approaches and exceeds one, the region of congestion is encountered, time delays begin to increase rapidly, and packets arriving are blocked more often.To quantify the discussion of time delay, blocking performance, and packet throughput (the actual number of packets/time that get through the system), and their connection with both µ (the packet rate capacity) and the size of the buffer in Fig. 2— 1, one needs a more detailed model of the queueing system. Specifically, those performance parameters among others will be shown to depend on the probabilities of state of the queue. The state is in turn defined to be the number of packets on the queue (including the one in service if the queue is nonempty)


(8)

Quelle

ZeitAnkunftszeiten

Bedienzeiten

Zwischenankunftszeit und Bedienzeit sind Zufallsgrößendurch ihre Verteilungen eindeutig festgelegt

mittlere Zwischenankunftszeit: mittlere Ankunftsrate:

mittlere Bedienzeit: mittlere Bedienrate:

Für diese Vorlesung werden grundsätzlich exponentiell verteilte Zeiten angenommen! ( Gedächtnislosigkeit)

t1 t2 t3 t4

tb1 tb2 tb3 tb4

atat1

=λ

btbt1

=μ

Zwischenankunftszeiten

ta12 ta23 ta34

Ankunftszeiten und Bedienzeiten


(9)

Die Poissonverteilung kann aus der Exponentialverteilung abgeleitet werden.

Definition: Sind beliebige Ereignisse voneinander unabhängig und gleichverteilt und gibt die Zufallsvariable X die Anzahl der Ereignisse im Intervall t an, dann ist X poissonverteilt.

Mittelwert

und Varianz σ λ2 = ⋅ t

tk

k ektpkXP ⋅−⋅

⋅=== λλ

!)()(

μ λ= ⋅ t

λ: Rate, mit der die Ereignisse eintreten

Poissonverteilung

Eine Zufallsgröße heißt poissonverteilt, wenn sie die abzählbar unendlich vielen möglichen Werte k= 0, 1, 2, ... mit den Wahrscheinlichkeiten

annimmt. (s. Bronstein, S. 663 oder s. Papoulis , S. 56f)

...,1,0,!)()( =⋅=== − ke

ktpkXP t

k

kλλ


(10)

Leistungsgrößen

Ziel der Modellbildung ist die Ermittlung von Leistungsgrößen:

• Zustandswahrscheinlichkeit p(k)• Auslastung ρ• Durchsatz γ• Antwortzeit Tv• Warteschlangenlänge N• Füllung k


(11)

Inhalt



(12)

Durchschnittliche Anzahl Kunden im System

Die Fragestellung ist, wie viele Kunden sich „im Durchschnitt“ oder „typischerweise“ im System befinden.Dazu dient der Satz von Little

Ankünfte

Arrivals

Warteschlange

Queue Server

Bedieneinheit Ausgangabgehend

Outputleaving


(13)

Ableitung von Little‘s Law

Wir nehmen an, dass wir das System vom Zeitpunkt t = 0 bis in die unendliche Zukunft betrachten und die Zahl der Kunden im System beobachten. Definitionen:

N(t) = Anzahl Kunden im System zur Zeit ta(t) = Anzahl Kunden, die im Zeitraum [0,t] eingetroffen sindTi = Zeit, die der i-te Kunde im System verbringt

Dann ist die typische Anzahl Kunden im System beobachtet bis zur Zeit t:

∫=t

dNt

tN0

)(1)( ττ

Wir nehmen an, dass existiert )(lim tNNt ∞→

=

Ähnlich behandeln wir die Anzahl Kunden und die Verweilzeit im System:

)(lim)(

)(

)(lim)()(

)(

0 tTTta

TtT

tttat

t

ta

i i

t

∞→

=

∞→

==

==

∑ damit und

damit und λλλ


(14)

k Tv= ⋅λ

Die mittlere Einfallrate von Bedienwünschen

Die mittlere Verweildauer in der Warteschlange

Der mittlere Füllgrad einer Warteschlange

Little’s Law

Allgemein gültige Gesetzmäßigkeit der Bedientheorie, erstmals von Little bewiesenLittle’s Law lautet

!!!Wichtig!!! Alle Werte sind Durchschnittswerte !!!Wichtig!!!

Der Satz von Little gilt für beliebige Ankunfts- und Bedienprozesse!


(15)

Inhalt



(16)

Markov-Ketten

Beschreibt einen zeitdiskreten oder zeitkontinuierlichen stochastischen Prozess, der positive Integerzahlen annehmen kannDie Aufenthaltsdauer in Zustand i ist exponentiell verteilt (im zeitkontinuierlichen Fall)Wenn der Prozess in Zustand i ist, gibt es eine feste Wahrscheinlichkeit Pij dafür, dass er als nächstes im Zustand j ist.

∑=∑ =i

ijijj

ij PppP und 1

20P

n-1 n0 1 2

01P

10P

12P

21P

nnP )1( −

)1( −nnP

02P

2 nP

Die Aufenthaltsdauer im zeitkontinuierlichen Fall ist durch die Exponentialverteilung gegeben (Der Aufenthalt kann auch so interpretiert werden, dass nach einer Ankunft das System im Zustand k ist und die Zeit bis zur nächsten Ankunft/dem nächsten Verlassen des Zustands exponentiell verteilt ist).

Im zeitdiskreten Fall ist es so, dass in jedem Zeitintervall δt die Wahrscheinlichkeit dafür, dass ein Kunde im Zustand i aus Zustand j ankommt oder den Zustand i in den Zustand k verlässt, gegeben ist durch Pji, bzw. durch Pik. Wenn die Wahrscheinlichkeiten unabhängig sind, entsprechen die Aufenthaltsdauern in den Zuständen einer Exponentialverteilung (siehe Herleitung Poisson-Prozess).


(17)

Eigenschaften von Markov-Ketten

Nicht-reduzierbare Markov-Kette: Man kann in endlichen Schritten von jedem Zustand in jeden anderen Zustand übergehenReguläre Markov-Kette: Endliche Anzahl Zustandsübergänge in jedem endlichen ZeitintervallAperiodische Markov-Kette: Es gibt keinen Zustand, der nur nach gleichen Perioden wieder erreicht werden kann

existiert, ist stationär und

unabhängig vom Anfangsszustand i(d.h. man kann eine Wahrscheinlichkeitsverteilung berechnen, bei der es egal ist, wann man auf den Prozess schaut“)

{ }iXjtXPptj ===

∞→)0(|))(lim

Hier ist wieder die Gedächtnislosigkeit der Verweildauer in einem Zustand wichtig. Der Markov-Prozess ist der einzige gedächtnislose stochastische Prozess. Dies bedeutet, dass man nicht darauf achten muß, wie lange der gerade in Bedienung befindliche Kunde bereits bedient wird, da die restliche Bedienzeit immer die gleiche statistische Verteilung hat, unabhängig vom Zeitpunkt des Draufschauens. Wir werden bei M/G/1-Systemen sehen, dass dort diese Voraussetzung nicht gilt und damit die mathematische Lösung des Problems ungleich schwerer ist.

Die Existenz einer Wahrscheinlichkeitsdichte ist eindeutig, wenn sie existiert. Dann spricht man von einer stationären Verteilung. Wenn sie nicht existiert, sinde alle pj = 0 und die Markov-Kett hat keine Stationäre Wahrscheinlichkeitsdichte. Ein Beispiel für eine Markov-Kette ohne stationäre Dichte ist der Poisson-Prozess nach Folie 35 (Lassen Sie dazu t ∞ gehen!). Allerdings ist die Markov-Kette zum Poisson-Prozess auch nicht nicht-reduzierbar, da man nicht von jedem Zustand in jeden anderen Zustand gelangen kann. Wir werden später Markov-Ketten kennen lernen, bei denen eine stationäre Wahrscheinlichkeitsdichte existiert.


(18)

Geburts-Sterbeprozess

Der Zustand k kann nur vom Vorgänger k-1 und Nachfolger k+1 erreicht werden und der Zustand k kann nur zum Vorgänger k-1 und Nachfolger k+1 verlassen werden Die Übergangswahrscheinlichkeiten können zustandsabhängig sein

k-1 k k+1

kkP ,1− 1, +kkP

kkP ,1+1, −kkP


(19)

Detaillierte Gleichgewichtsgleichungen

Für Geburts-Sterbeprozesse muss im stationären Fall die Übergangsraten von Zustand k in den Zustand k+1 gleich der Übergangsrate von Zustand k+1 in Zustand k sein. Die Gleichgewichtsgleichung dazu ist:

Die detaillierten Gleichgewichtsgleichungen sind ein Spezialfall der globalen Gleichgewichtsgleichungen, gelten aber nicht für jede Markov-Kette. Wenn sie jedoch gelten, dann erleichtern sie die Berechnung der stationären Wahrscheinlichkeitsdichte enorm.

kkkkkk PpPp ,111, +++ =

k-1 k k+1

kkP ,1− 1, +kkP

kkP ,1+1, −kkP


(20)

Inhalt



(21)

Kendall-Notation für Wartesysteme

A|B|m|nA:= Verteilung der ZwischenankunftszeitenB:= Verteilung der Bearbeitungszeitenm:= Anzahl der Bedieneinheitenn := Anzahl der Warteplätze

Parameter für A,BM:= exponentielle Verteilung (Markov)E:= r-stufige ErlangverteilungH:= r-stufige hyperexponentielle VerteilungD:= deterministischG:= allgemeine Verteilung

Beispiel: M|D|4|10

Interpretation des Beispiels M|D|4|10exponentielle Verteilung der ZwischenankunftszeitenDeterministische Bearbeitungszeitenvier Bedieneinheitenzehn Warteplätze

AnmerkungAls Erweiterung der Kendall’schen Notation wird oft die Abfertigungsstrategie mit angegebenA | B | m | n - Warteschlagendisziplin , z. B. : M | M | 1 | 1 - FCFS


(22)

Zustandsübergänge in der M/M/1-Queue

War

tesc

hla n

genb

e leg

ung

Zeitt t+Δt

n

n+1

n-1

Wir wollen zum Zeitpunkt t+ Δt den Zustand „n Plätze in der Warteschlangebelegt“ erreichen. Wir postulieren, dass nur jeweils ein Vorgang zur Zeit bei den Quellen und den Bedieneinheiten passierenkann. Aus dieser Überlegung ergibt sich das nebenstehende Diagramm.

Erkenntnis: es sind nur Übergänge in benachbarte Zustände möglich!

12n

Unbegrenzte Warteschlange

λn-1

n+1

μBedieneinheit

Von n+1 nach n gelangen wir durch Freiwerden der Bedieneinheit und Nachrücken eines Auftrages aus der Warteschlange. Wir gehen davon aus. Dass die Bedieneinheit immer sofort nach dem Freiwerden einen neuen Auftrag übernehmen kann und wird.Von n nach n gelangen wir durch Einfallen eines neuen Bearbeitungswunsches und gleichzeitiges Feiwerden der Bedieneinheit.Von n-1 nach n gelangen wir durch alleiniges Einfallen eines neuen Bearbeitungswunsches.


(23)

Detaillierte Gleichgewichtsgleichungen der M/M/1-Queue

n-1 n n+10 1 2

λτ λτ λτ λτ

μτ μτ μτ μτ

μτλτ 1+= nn ppDie detaillierte Gleichgewichtsgleichung lautet:

Im Grenzübergang τ→0: μλ 1+= nn pp

Mit ρ = λ /μ:

nn pp ⋅=+ ρ1


(24)

Ableitung der Wahrscheinlichkeitsdichte der M/M/1-Queue

0pp nn ρ=

Durch Induktion ergibt sich:

Nun brauchen wir nur noch p0 zu bestimmen. Dazu nehmen wir die Summe aller Wahrscheinlichkeiten, die sich zu 1 summieren müssen:

)1(

11

1

0

0

00

0

ρρ

ρρ

ρ

−=⇒

−=⇒−

=∑=∑=∞

=

∞

=

nn

n

n

nn

p

p

ppp

pn ist die Wahrscheinlichkeit dafür, dass n Kunden im System sind. Damit ist auch die Wahrscheinlichkeitsdichte des M/M/1-Prozesses gegeben!


(25)

Durchschnittliche Zahl Kunden im System

Die Durchschnittliche Anzahl Kunden im System, N, ist gegeben durch:

λμλ

ρρ

ρρρ

ρρρρ

ρρ

ρρρρρ

ρρ

−=

−=

−−=⎟⎟

⎠

⎞⎜⎜⎝

⎛−∂

∂−

=⎟⎠⎞

⎜⎝⎛

∑∂∂

−=∑ ⋅−

=∑ −⋅=∑ ⋅==

∞

=

∞

=

−

∞

=

∞

=∞→

1

)1(1)1(

11)1(

)1()1(

)1()}({lim

2

00

1

00

n

n

n

n

n

n

nnt

n

npntNEN

Es handelt sich um eine Erwartungswertbildung, d.h. der allgemein gültigen Vorschrift zur Berechnung des Durchschnittswertes.


(26)

Graph für N im M/M/1-System

Es ist sinnvoll, ρ als Nutzungsfaktor des Systems zu betrachten, d.h. ρ ist gleich dem Langzeit-Anteil, während dessen die Bedieneinheit belegt ist. Damit ist auch klar, dass ρ = 1 - p0 (also gleich der Wahrscheinlichkeit, dass mindestens ein Kunde im System ist).

0

5

10

15

20

0 0.2 0.4 0.6 0.8 1

Dur

chsc

hn. A

nz. N

rho


(27)

Durchschnittliche Wartedauer

Die Durchschnittliche Aufenthaltsdauer im System T ist gegeben durch (Little‘s Theorem):

λμρλρ

λ −=

−==

1)1(

NT

Die Durchschnittliche Wartedauer in der Schlange W ist gegeben durch (Little‘s Theorem):

λμρ

μλμμ −=−

−=−=

111TW

Schließlich ist die durchschnittliche Anzahl Kunden in der Schlange NQ:

ρρλ−

==1

2WNQ


(28)

Inhalt



(29)

M/M/m system description

Ankünfte

Arrivals

Warteschlange

Queue

m Servers

m Bedieneinheiten

Ausgangabgehend

Outputleaving

:

Whenever a customer arrives in the system, he is• Queued when all servers are busy• Passed on to the next available server when at the head of queue or when at least

one server is free upon arrival

Infinite length!

λ

μ

μ

μ

The system is such that a single queue with infinite length is connected to m servers. When a customer arrives in the system and at least one server is busy, he is forwarded to an arbitrary free server. If all servers are busy, the customer is queued and has to wait , until it is at the head of the queue and a server becomes free. The customer, then, is routed to this free server.

The M/M/m-system, therefore, is identical to the M/M/1-system, except that m servers are available. In particular, the number of places in queue is unlimited.

The mean arrival rate of customers into the system is denoted by λ and each server has a mean service rate of μ. Both, arrival and service processes, are Poisson.


(30)

The M/M/m Markov chain

m-1 m m+10 1 2

λτ

μτ 2μτ (m-1)μτ

λτ λτ λτ λτ

mμτ mμτ

mnpmpmnpnp

nn

nn

≥=<=

−

−

1

1

μλμλ

⇒

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≥

<

=

mnm

mp

mnn

mp

pnm

n

n

;!

;!)(

0

0

ρ

ρ

1 where <=μ

λρm

Now that we have the Markov chain, we need to search for the detailed balance equations. The solution can be found by iteration, as in the case of the M/M/1-System:

The part for n>m is analogous

0

021

1

!)(get we

)(with

!)1(

:for

pn

mp

mmm

pn

pnn

pn

p

pnpmn

n

n

nn

n

nn

nn

n

n

nnn

nn

ρ

ρμλ

μλρ

μλρ

μλ

μλ

μλ

μλ

μλ

=

=⇒=⇒=

==⎟⎟⎠

⎞⎜⎜⎝

⎛−

==

=≤

−−

−

Κ


(31)

Solution for M/M/m systemDetermination of p0

11

0

11

10

01

100

01

00

0

)1(!)(

!)(

1!)(

!)(1

1!)(

!)(

!!)(1

−−

=

−∞

=−

−

=

∞

= −

−

=

∞

=

−

=

∞

=

⎥⎥⎦

⎤

⎢⎢⎣

⎡

−+∑=

⎥⎥⎦

⎤

⎢⎢⎣

⎡∑+∑+=⇔

∑+∑+

=∑+∑==∑

ρρρ

ρρ

ρρ

ρρ

mm

nm

mmm

nmp

pmm

mpn

mp

pm

mpn

mp

mm

n

n

mn mn

nm

n

n

mn mn

nm

n

nmn

nmm

n

n

nn

Some explanations for the last step in the slide above:

The sum can be solved to:

And the final result is:

Note that the calculation of p0 is necessary to compute the probabilities for all other states of the system. This computation requires somewhat more effort compared to an M/M/1-system. However, with given parameters, it can be done easily with a small computer programm. All subsequent computations are straight forward and simple.

ρρ

ρρ

ρρρρ

−=

−−

−−

=∑−∑=∑−

=

∞

=

∞

= 111

111

00

mmm

n

n

n

n

mn

n

∑=∑ ⎟⎠⎞

⎜⎝⎛=∑

∞

=

∞

=−

∞

=− mn

nm

mn m

n

mn mn

n

mm

mmmm

mmm ρρρ

!!11

!)(

)1(!)(1

!)(

ρρρ−

=∑∞

=− m

mmm

m m

mn mn

n


(32)

M/M/m delay situation

What is critical is the probability to find all servers busy, i.e. the case when an arrivingcustomer has to wait in queue:

)1(!)(

!)(

!}Queueing{

0

00

ρρ

ρρρ

−=

∑=∑=∑==∞

=

−∞

=

∞

=

mmp

P

mmp

mmp

pPP

m

Q

mn

mnm

mn

nm

mnnQ

This is known as the Erlang-C formula (or Erlang‘s delay formula).• Often used in telephone systems (call center example, manual exchange office)• Used to estimate the probability to find e.g. all operators in a call center busy.• The customer remains in queue, i.e. it continously tries to get a free server.

The danish mathematician A.K. Erlang was the foremost pioneer of queueing theory. The Erlang delay formula above is named after him to honour his merits in queueing theory.


(33)

Comparison of M/M/m and M/M/1 systems

Note that

represents the expected number found in queue by an arriving customer conditioned on thefact that all servers are busy. It is independent of the number of servers for a given ρ=λ/(mμ)!Hence, as long as customers are waiting in queue, the queue size of the M/M/m systems behaves identically as in an M/M/1-system with service rate mμ!

ρρ−

=1Q

Q

PN


(34)

Inhalt



(35)

Warteschlangennetze

Bisher nur einzelne Bedieneinheiten betrachtetreale System lassen oft nur durch Zusammenschaltung mehrere Bedieneinheiten modellierenUnterscheidung

offene Netze: Aufträge können von außerhalb ankommen und das System wieder verlassengeschlossene Netze: Aufträge bewegen sich nur innerhalb des Systemsgemischte Netze

Notation der Zustandswahrscheinlichkeitenp(k1,k2,...,kN)

Die Zustandswahrscheinlichkeiten der einzelnen Knoten werden durch

angegeben.

∑∑

=

=

==N

jij kkKk

Ni kkkpkp

1

&

21 ),...,,()(


(36)

Reihenschaltung

Parallelschaltung

Gemischte Zusammenschaltung

Zusammenschaltung mehrerer Bedieneinheiten

μ1 μ2

μ1

μ2

μ2

μ3

μ1

Bei der Zusammenschaltung mehrere Bedieneinheiten sind zur Beschreibung des Systems nicht nur die Übergangsraten, sondern auf die Wahrscheinlichkeiten der Zustandsübergänge anzugeben.Dies ist bei Parallelschaltung wichtig, da dort zwei Zustandsübergänge möglich sind.

Auf die gemischte Zusammenschaltung angewandt bedeutet dies:Übergangsrate von System 1 zu System 2: µ1 p12Übergangsrate von System 1 zu System 3: µ1 p13Übergangsrate von System 2 zu System 1: µ2 p21= µ2, da p21= 1Übergangsrate von System 3 zu System 1: µ3 p31= µ3,, da p31= 1


(37)

Gleichungen für die Leistungsgrößen unter Verwendung der Zustandswahrscheinlichkeiten

Durchsatz λi eines Knotens i:

Gesamtdurchsatz des Systems λ :

im offenen Netz ist der Gesamtdurchsatz im Gleichgewichtszustand gleich der Rate der das Netz verlassenden oder erreichenden Bearbeitungsaufträge

∑=

=N

ii

1

λλ

λ μi i ik

p k k= ⋅=

∞

∑ ( ) ( )1


(38)

Auslastung ρi eines single-server Knotensm:=Zahl der Bedieneinheiten

mittlere Anzahl von Aufträgenim i-ten Knoten:

mittlere Warteschlangenlänge

mittlere Antwortzeit

mµBedienrateteAnkunftsra

kunftszeitZwischenanmittlereBedienzeitmittlere

kpk

ii

λ

ρ

===

=∑∞

=1)(

k k p ki ik

= ⋅=

∞

∑ ( )1

Q k p ki ik

= − ⋅=

∞

∑ ( ) ( )11

tk

ii

i=

λ


Literatur• Bolch, Gunter:

Leistungsbewertung von Rechensystemen mittels analytischer Warteschlangenmodelle, Stuttgart: Teubner, 1989

• Bronstein, I. N.; Semendjajew, K. A.:Taschenbuch der Mathematik23. Auflage, Frankfurt/Main: Thun, 1987

• Kleinrock, L.:Queueing Systems, Vol. 1 : TheoryNew York: Wiley & Sons, 1975

• Schuberth, W.:Verkehrstheorie Elektronischer KommunikationssystemeWien : Dr. Alfred Hüthig Verlag Heidelberg, 1986

• Schwartz, Mischa:Telecommunication networks Addison-Wesley Publishing Company, 1987

• Siemens AG:Tabellenbuch FernsprechverkehrstheorieBerlin, München: 1981

• Tanenbaum, Andrew S.:Computer-NetzwerkeAttenkirchen: Wolfram’s Fachverlag, 1992

Außerdem:• Kleinrock, L.:

Communication NetsNew York: Dover, 1964

• Schassberger, R.:WarteschlangenNew York; Wien: Springer Verlag, 1973

• Störmer u. a.:VerkehrstheorieMünchen: Oldenbourg Verlag, 1966

• Uhl, Tadeus:Verkehrstheoretische Untersuchungen und Dimensionierung von Rechner- und Datennetzen unter besonderer Berücksichtigung von ProtokollenDüsseldorf: VDI-Verlag, 1992


(40)

Weitere Folien zur Information

Die weiteren Folien enthalten zusätzliche Informationen


(41)

Warteschlangendisziplinen

FCFS (FIFO) First Come, First ServedLCFS (LIFO) Last Come, First ServedSIRO Served In Random OrderRR Round Robinstatische Prioritätendynamische PrioritätenVerdrängung

FIFO (First in, First out) oder auch FCFS (First come, First serve)Bearbeitung in der Reihenfolge des Eintreffensgerechte Bearbeitunggeringe Streuung der Wartezeitverteilung

LIFO (Last in, First out) oder auch LCFS (Last come, First serve)Bearbeitung in entgegengesetzter Reihenfolge des Eintreffenssehr große Streuung der Wartezeitverteilung

SIRO (Serve-In-Random-Order) Zufällige ReihenfolgeBearbeitung unabhängig von der Reihenfolge des Eintreffensgroße Streuung der Wartezeitverteilung

Round RobinAuftrag für eine Zeitspanne t bearbeitenRückschreiben des Auftrags in die Warteschlangesolange fortsetzen , bis der Auftrag fertig ist

PrioritätsmechanismenBereitstellung unterschiedlicher Prioritätsklassen zur schnellen Bearbeitung wichtiger AnforderungenEinführung getrennter Warteschlangen für Anforderungen unterschiedlicher PrioritätBevorzugung der Warteschlangen mit höherer PrioritätVergabe der Prioritäten

statischFest vorgegebene PrioritätenInnerhalb einer Prioritätsklasse, d.h. alle Anforderungen haben gleiche Priorität, erfolgt die Herausnahme der Aufträge aus der Warteschlange nach dem FCFS-Prinzip.

DynamischDie Prioritäten der Aufträge ändern sich mit der Zeit.Unterscheidung verschiedener Verfahrensweisen bei Anforderungen mit höherer Priorität

unterbrechende Priorität: Unterbrechung der Bearbeitung bei Eintreffen einer Anforderung mit höherer Priorität. Weiterführen der Bearbeitung nach Beendigung der bevorrechtigten Anforderungnicht unterbrechende Priorität. Bearbeitung der höher priorisierten Anforderung nach Abschluß der laufenden Aufgabe


x P x xii

m

i= ⋅=∑ ( )

1Erwartungswert:(zentrales Moment erster Ordnung)

Zentrales Moment bedeutet, das Moment der Zufallsvariablen bezogen auf den Erwartungswert.

E x E x P x x E xi i ii

m

i i[( ( )) ] ( ) ( ( ))− = = ⋅ −=∑2 2

1

2σVarianz:

(zentrales Moment zweiter Ordnung)

Die Varianz ist der mittlere quadratischen Fehler bei Approximation der Zufallsvariablen durch ihren Erwartungswert.

zentrales Moment n-ter Ordnung: E x E x P x x E xi in

ii

m

i in[( ( )) ] ( ) ( ( ))− = ⋅ −

=∑

1

Verteilungsfunktion:

Die Verteilungsfunktion F gibt an, mit welcher Wahrscheinlichkeit der Wert der Zufallsvariablen xi kleiner oder gleich einer vorgegebenen Zahl x istSie ist aufgrund der Eigenschaften von P eine auf das Intervallbeschränkte, nicht abnehmende FunktionIm Fall der diskreten Zufallsvariablen ist sie eine Treppenkurve.

F x P x xx ii( ) ( )= ≤

Variationskoeffizient: (normierte Standardabweichung)c

x=

σ

Beschreibung diskreter Zufallsvariablen

0 1≤ ≤F

(42)

Zufallsvariable

Ergebnis eines Zufallsexperimentes: ZufallsvariableUnterscheidung

diskrete Zufallsvariablen kontinuierliche Zufallsvariablen

im folgenden werden diskrete Zufallsvariablen betrachtetWahrscheinlichkeit für den diskreten Wert X=k oder xi=k:

pk= P(X=k) oder pk = P(xi=k)Es muß gelten

und

P X kk

( )= =∑ 1P X k( )= ≥ 0


(43)

Verteilungsfunktionen

ExponentialverteilungHyperexponentialverteilungErlang-k-VerteilungHypoexponentialverteilungGammaverteilungverallgemeinerte Erlang-VerteilungCox-Verteilung

(Bem.: Zur Beschreibung werden häufig der Mittelwert und die Varianz herangezogen)


(44)

am: mittlerer Einfallsabstand

F t P T t et

am( ) ( )≤ = ≤ = −−

1

Exponentialverteilung am Beispiel der Zwischenankunftszeiten

2 4 6 8 10Zeit t

Parameter: am Einfallabstand 1 .. 10 sek

0.2

0.4

0.6

0.8

1

Wahrscheinlichkeit F(=<t)

Die Exponentialverteilung ist eine wichtige Verteilung in der Verkehrstheorie. Sie kommt sehr häufig zur Anwendung, wenn zeitliche zufällige Abstände gemessen werden

Die Exponentialverteilung gibt die Wahrscheinlichkeit für genau ein Ereignis innerhalb des Intervalls t.

Definition: eine stetige Zufallsgröße heißt exponentialverteilt, wenn sie folgenden Dichte (Ableitung der Verteilungsfunktion) hat:

(s. Bronstein, Kap.5)

f xe für x

für x

x

( ) =⋅ ≥

<

⎧⎨⎩

⎫⎬⎭

−λ λ 00 0

1 2 3 4 5 6 am--t

0.2

0.4

0.6

0.8

1

am*f(t)


(45)

in 63% aller Fälle ist die Zeit bis zum Einfall des nächsten Ereignisses kleiner als der mittlere Einfallsabstand1 2 3 4 5 6

t/am

0.2

0.4

0.6

0.8

1

F(=>t)

Normierte Exponentialverteilung

1[ ]

( ) ( ) 11[ ] :

( ) ( ) 1

m

ta

mts

F t P T t emit a s

F t P T t e

−

−

≤ = ≤ = −=

≤ = ≤ = −

Die Normierung findet auf den Mittelwert der zeitlichen Dauer bis zum Eintreffendes des erwarteten Ereignisses statt, hier der mittleren Einfalldauer. Der Vorteil dieser Normierung ist die Reduzierung der prinzipiell unendlichen Kurvenschar auf eine einzelne Kurve.Bemerkenswerte Punkte dieser Kurve sind an der Stelle t/am = 1(dort ist die Zeit gleich dem mittleren Einfallabstand). Bereits in 63% aller Fälle ist der Abstand zwischen zwei Ereignissen kleiner als am.

Nach t>6am ist die Wahrscheinlichkeit für den Einfall eines Ereignisses schon fast 1, das Ereignis ist also nahezu sicher.


(46)

λ1

λ2

λ3

λ1 + λ2 + λ3

q1λ

q2λ

q3λ

λ

Zusammenfassung und Teilung von Poissonverteilungen

Das Zusammenfügen von Poissonverkehren zu einem neuen Poissonverkehr ist plausibel: Wenn drei Gruppen mit je 100 Teilnehmern (näherungsweise als Gruppen mit unendlich vielen Teilnehmern betrachtet) zu einer mit 300 Tln zusammengefaßt werden, dann ist auch diese Zahl nahezu unendlich. Damit ist auch wieder die Voraussetzung für Poissonverkehr geschaffen, wenn sonst keine Bedingungen verändert werden (Unabhängigkeit der Ereignisse)

Das Teilen jedoch ist nicht ganz so einsichtig. Der Verkehr wird z.B. geteilt, wenn er als Poissonverkehr einem Bündel angeboten wird, und mit Hilfe des Bündels in den Verkehr der Belastung und den Rest aufgeteilt. Diese beiden Verkehre sind nun aber keinesfalls mehr poissonverteilt.Die Aufteilung darf nicht durch Kappen erfolgen, sondern muß z.B. durch alternernierendes Zuweisen zu zwei Bündeln realisiert werden.Warum wird diese Aufteilung in der Praxis nicht vorgenommen, obwohl sich damit viel einfacher rechnen lassen würde? Antwort: der Bündelgewinn wird nicht ausgenutzt


(47)

• k: Anzahl der parallelen Stufen• Nachbildung der gewünschten

Verteilung durch Parallelschalten von exponentiell verteilten Einzelprozessen (Phasen)

• Ein Auftrag wird mit der Wahrscheinlichkeit qk von der Phase k bedient

• es ist nur eine Phase zur Zeit aktiv

μ1

μ2

μκ

F x q e xX jx

j

kj( ) ( ),= ⋅ − ≥− ⋅

=∑ 1 0

1

μ

Hyperexponentialverteilung Hk

zur Approximation nicht exponentieller Verteilung mit einem Variationskoeffizienten c > 1


(48)

• Serienschaltung von k identischen Stufen (Phasen)• jede Stufe für sich ist exponentiell verteilt

kμ kμ kμ

Phase 1 Phase 2 Phase k

F x ek x

jx kX

k xj

j

k

( )( )

!, , , , ...= − ⋅ ≥ =−

=

−

∑1 0 1 20

1μ μ

Erlang-k-Verteilung

Zur Approximation nichtexponentieller Verteilungen mit Variationskoeffizienten c<1


Verteilung Parameter Mittelwert X Varianz var(X) Variationskoeffizient cX

Exponential μ 1μ

12μ

1

Erlang k μ ,, ,...

kk = 1 2

1μ

12kμ

11

k≤

Hyperexponential k qi i, ,μqi

ii

k

μ μ=∑ =

1

12

12

12⋅ −

=∑ qi

ii

k

μ μ 2 122

1μ

μ⋅ − >

=∑ qi

ii

k

(49)


μ1j


μ1k


μ1r

μ1k μ1k

μ1j μ1j

μ1r μ1r

Hypoexponentialverteilung

Durch Kombination der Hyperexponential- und der Erlang-k-Verteilung können beliebig komplexe Strukturen erzeugt werden

Zusammenfassung der Kenngrößen der Verteilungen:


(50)

Zustandswahrscheinlichkeit p(k)Wahrscheinlichkeit, mit der sich k Aufträge im System befinden

Auslastung ρfür eine Bedieneinheit gilt:

für m Bedieneinheiten gilt entsprechend

Bem.: Das System ist stabil für ρ<1μ

λρ⋅

=m

ρλμ

= = =mittlere Bedienzeit

mittlere ZwischenankunftszeitAnkunftsrateBedienrate

Leistungsgrößen

Mit Hilfe der Auslastung läßt sich ein stabiles System definieren, für das < 1 gelten muß, d.h. es dürfen im Mittel nicht mehr Aufträge pro Zeiteinheit ankommen als bedient werden können. Hier werden nur stabile Systeme betrachtet


(51)

Leistungsgrößen

Durchsatz γmittlere Zahl von Kunden, die pro Zeiteinheit bedient werdenBeim stabilen System gilt analog zur Auslastung: γ = λ

Antwortzeit TvAntwortzeit ist die Verweildauer der Kunden im System, also Wartezeit Tw plus Bedienzeit

Warteschlangenlänge NZahl der Kunden in der Warteschlange

Füllung kZahl der Kundenim System

AnmerkungenBei realen Wartesystemen kann sich der Durchsatz allerdings von der Ankunftsrate unterscheiden, da dort der Verlust von Paketen zulässig istAlle Leistungsgrößen gelten für allgemeine Wartesysteme im stationären Zustand oder im statistischen Gleichgewicht


(52)

Average numbers of customers in M/M/m queue

The average number of customers in an M/M/m queue is given by

20

00

00

0

)1(!)(

!)(

!

)(

ρρρ

ρρ

−

=∑=∑

=∑=∑ −=

∞

=

∞

=

+

∞

=+

∞

=

mmp

nm

mpmpmnp

nppmnN

mn

nm

n

nmmn

nmmn

nQ

With PQ form the Erlang-C formula, we get

ρρ

ρρ

−=⇒

−=

1)1(!)(0

QQ

m

Q PNm

mpP


(53)

Average delay in M/M/m systems

The average waiting time in queue is given by Little‘s Law:

)1( ρλρ

λ −

⋅== QQ PN

W

The average time in system per customer is, therefore:

μλρ

λμμρλρ

μμ mmPP

WT QQ =−

+=−

⋅+=+= with 1

)1(11

Using Little‘s law again, the average number of customers in the system is:

μλρ

ρρ

ρλμ

λμλλ

mmP

TN Q =−

⋅+=

−+== with

1P

m Q

In an M/M/1-system, we have:

ρρ−

=1

N

The comparison of N in the M/M/m and the M/M/1 system shows again that the queue behaviour of the M/M/m system is equal to that of the M/M/1 system, under the assumption that all servers are busy.


(54)

am: mittlerer Einfallsabstand

F t P T t et

am( ) ( )≤ = ≤ = −−

1

Exponentialverteilung

2 4 6 8 10Zeit t

Parameter: am Einfallabstand 1 .. 10 sek

0.2

0.4

0.6

0.8

1

Wahrscheinlichkeit F(=<t)

Verständnisfrage:Für welche der Kurven ist am größer,für die unterste oder die oberste?

am steigt

Die Exponentialverteilung ist eine wichtige Verteilung in der Verkehrstheorie. Sie kommt sehr häufig zur Anwendung, wenn zeitliche zufällige Abstände gemessen werden

Die Exponentialverteilung gibt die Wahrscheinlichkeit für genau ein Ereignis innerhalb des Intervalls t.

Definition: eine stetige Zufallsgröße heißt exponentialverteilt, wenn sie folgenden Dichte (Ableitung der Verteilungsfunktion) hat:

(s. Bronstein, Kap.5)

f xe für x

für x

x

( ) =⋅ ≥

<

⎧⎨⎩

⎫⎬⎭

−λ λ 00 0

1 2 3 4 5 6 am--t

0.2

0.4

0.6

0.8

1

am*f(t)

Documents

[8] Nu P 04 3