Bedienungs-und Verkehrstheoriemidas1.e-technik.tu-ilmenau.de/~webkn/Webdaten/Lehre/WS2015... · BVT WS 2015/16 0. Organisatorisches 3 Gliederung II 4. Verkehrstheorie leitungsvermittelter

BVT WS 2015/16 1

Bedienungs- und Verkehrstheorie

Kontaktdaten

Dr.-Ing. Maik Debes

Raum: H 3507

Telefon: 03677 691246

Mail: [email protected]

Vorlesung

Mittwoch

13:00 Uhr – 14:30 Uhr

Sr H1520a

Übung

Freitag (U)

13:00 Uhr – 14:30 Uhr

Sr HU010

0. Organisatorisches

M.Sc. Silvia Krug

Raum: H 2516

Telefon: 03677 694138

Mail: [email protected]

Web: www.tu-ilmenau.de/it-kn

mailto:[email protected]

mailto:[email protected]

http://www.tu-ilmenau.de/it-kn

BVT WS 2015/16 0. Organisatorisches 2

Gliederung I

1. Einführung

Bediensysteme

Bedienkanal

Warteplätze

Verluste

2. Grundlagen zur Beschreibung von Bediensystemen

Klassifikation von Bediensystemen

Satz von Little

Kendall-Notation

3. Beschreibung von Verlustsystemen mit gleichen Bedienkanälen

Geburts- und Todesprozess

Binomial-, Poisson-, Erlang-, Engsetverteilung

BVT WS 2015/16 0. Organisatorisches 3

Gliederung II

4. Verkehrstheorie leitungsvermittelter Netze

Eigenschaften, Beschreibung

Zufallsverkehr I. und II. Art

Blockierungswahrscheinlichkeit

5. Beschreibung von Wartesystemen

Kenngrößen

Untersuchung von M/M/1, M/M/n, M/M/1/-/W, (M/D/1, M/G/1)

6. Zentralisierte Einrichtungen

Eigenschaften, Beschreibung

Verkehrsleistung, Wartezeiten

Berechnungsansatz bei statistischem Multiplex (allgemein)

7. Berechnungsansätze für ATM-Netze (QoS!!!)

Zugangssteuerung (Admission Control)

stochastischer Rucksack

8. …

0. Organisatorisches 4

Literatur

W. Schubert: Verkehrstheorie elektronischer Kommunikationssysteme. ITT

Austria GmbH, Wien, 1986.

P. Tran-Gia: Einführung in die Leistungsbewertung und Verkehrstheorie.

Oldenbourg Verlag, München, 2005

C. Grimm, G. Schlüchtermann: Verkehrstheorie in IP-Netzen. Hütig

Telekommunikation, Bonn, 2005

I.N. Bronstein: Taschenbuch Mathematik. 6. Auflage, Verlag Harri Deutsch,

Frankfurt am Main, 2005.

J. Flood: Telecommunications, Switching, Traffic and Networks. Prentice

Hall, New York, 1994.

R. Jain: The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John

Wiley & Sons, New York, 1993.

K.W. Ross: Multiservice Loss Models for Broadband Telecommunication Networks. Springer-Verlag, London, 1995.

BVT WS 2015/16


1. Einführung

Bediensysteme

Bedienkanal

Warteplätze

Verluste

BVT WS 2015/16 1. Einführung 6

Bediensystem

System

Auftreten von Forderungen

Zeitbehaftete Bearbeitung

Ressourcen für Bearbeitung notwendig

Bediensystem

Forde-

rungs-

quelle

Erledigte

Forde-

rungen



Teilgebiet der Nachrichtentechnik

Ausgangspunkt: Verhalten von Nachrichten-bzw. Informationsquellen

Bestimmung der Wechselwirkung dieses Verhaltens mit den nachrichtentechnischen Anlagen

Ziele: Angaben über Wartezeiten bei der Bedienung

Verluste von Forderungen

Durchsatz des Systems

…


Blick von außen

in ein Bediensystem

System bearbeitet Forderungen

Forderungen treten zufällig auf

Zur Bedienung einer Forderung benötigt

das System eine gewisse Zeit

Forderungen können

sofort bedient werden

auf Warteplätzen gespeichert werden

verloren gehen


Struktur von Bediensystemen

— Bedienkanal

Bedienkanal

Einrichtung in einem Bediensystem, die zu

einem Zeitpunkt genau eine Forderung

bedient oder frei ist

Beschreibung über Zustandsmodell

(belegt – frei)

Bediensystem besteht aus

einem Kanal: Einkanalsystem

mehreren Kanälen: Mehrkanalsystem

1. Einführung 10

Struktur von Bediensystemen

— Warteplatz

Bediensystem verfügt über

keine Speicherplätze für Forderungen

Verlustsystem

unendlich viele Speicherplätze für

Forderungen

Wartesystem

endlich viele Speicherplätze für Forderungen

Warte-/Verlustsystem

BVT WS 2015/16

1. Einführung 11

Auftreten von Verlusten

Keine Bedienkapazität bei Eintreffen einer Forderung an einem Verlustsystem

Kein freier Bedienkanal und keine Wartemöglichkeit bei Eintreffen einer neuen Forderung an einem Warte-/ Verlustsystem

Verluste abhängig von

Forderungs- und Bedienrate

Speicherkapazität für ankommende Forderungen

BVT WS 2015/16

1. Einführung 12

Anwendung der


Kommunikationstechnik

Effektive Nutzung teurer Einrichtungen

Mehrfachnutzung von Ressourcen

Wahrscheinlichkeit, dass bestimmte Ressourcen (nicht) zur Verfügung stehen

Computer- und Steuerungstechnik

Einhaltung von Echtzeitbedingungen

Bedienung muss innerhalb einer bestimmten Zeit erfolgen

Verluste und Wartezeiten sind zu minimieren

BVT WS 2015/16


2. Grundlagen zur Beschreibung

von Bediensystemen

Taxonomie für Bediensysteme

Der Satz von Little

Kendall-Notation

BVT WS 2015/16 2. Grundlagen zu Bediensystemen 14

Einkanalsystem ohne

WarteplätzeAuftrag 1

Auftrag 2

Auftrag 3

Auftrag 4

Auftrag 5

Auftrag 1

erledigt

Auftrag 2

erledigt

Auftrag 4

erledigt

Auftrag 5

erledigt

Auftrag 3

verloren

freibelegt


Mehrkanalsystem ohne

Warteplätze

freibelegt

belegt frei

Auftrag 1

Auftrag 2

Auftrag 3

Auftrag 4

Auftrag 5

Auftrag 4

verloren

Auftrag 1

erledigt

Auftrag 2

erledigt

Auftrag 3

erledigt

Auftrag 5

erledigt


Einkanalsystem mit

WarteplätzenAuftrag 1

Auftrag 2

Auftrag 3

Auftrag 4

Auftrag 5

Auftrag 6

Warteschlange

für zwei Aufträge

Auftrag 1

erledigt

Auftrag 2

erledigt

Auftrag 3

erledigt

Auftrag 4

erledigt

Auftrag 5

erledigt

Auftrag 6

verloren

freibelegt

Auftrag 3Auftrag 4Auftrag 5 Auftrag 5


Taxonomie für Bediensysteme I

Bediensystem

Einkanalsystem mit Verlustbetrieb

Einkanal-

system

Mehrkanal-

system

Verlust-

betrieb

Warte-

betrieb

• Statistik des Forderungsstromes

• Verweildauer von Forderungen (Bedienzeit)

• Verlustwahrscheinlichkeit von Forderungen


Taxonomie für Bediensysteme II

Bediensystem

Mehrkanalsystem mit Verlustbetrieb

Einkanal-

system

Mehrkanal-

system

Verlust-

betrieb

Warte-

betrieb


• Verweildauer von Forderungen (Bedienzeit)



Taxonomie für Bediensysteme III

Bediensystem

Einkanalsystem mit Wartebetrieb

Einkanal-

system

Mehrkanal-

system

Verlust-

betrieb

Warte-

betrieb


• Verweildauer von Forderungen (Bedienzeit, Wartezeit)


Taxonomie für Bediensysteme III

Bediensystem

Mehrkanalsystem mit Wartebetrieb

Einkanal-

system

Mehrkanal-

system

Verlust-

betrieb

Warte-

betrieb




Taxonomie für Bediensysteme IV

Bediensystem

Einkanalsystem mit Warte-/Verlustbetrieb

Einkanal-

system

Mehrkanal-

system

Verlust-

betrieb

Warte-

betrieb





Taxonomie für Bediensysteme V

Bediensystem

Mehrkanalsystem mit Warte-/Verlustbetrieb

Einkanal-

system

Mehrkanal-

system

Verlust-

betrieb

Warte-

betrieb





Satz von Little (I)

Gegeben: Bedienstation mit folgenden Zufallsvariablen

AN(t) = Anzahl von Forderungen bis zur Zeit t

AB(t) = Anzahl von bedienten Forderungen zur Zeit t

Anfangsbedingungen

AN(0) = 0

AB(0) = 0

Beobachtungsdauer T

Für T ∞: AN(T) = AB(T)


Satz von Little (II)

Zu einem beliebigen Zeitpunkt t befinden sich

N(t) = AN(t) – AB(t)

Forderungen im System

Es sei TVi die Verweilzeit der Forderung i im System Verweilzeit = Wartezeit + Bedienzeit

Die gesamte Verweilzeit TVges ergibt sich zu:

T

Vges

TAN

i

ViVges

dttNT

TT

0

)(

1

)(


Satz von Little (III)

Die mittlere Anzahl von Forderungen im

System ergibt sich zu

T

dttN

T

T

T

TtNE

T

TAN

i

Vi

Vges

0

)(

1

)(

)]([


Satz von Little (IV)

Die mittlere Verweildauer der Aufträge

ergibt sich zu

)(

)(

)(

)(][

0

)(

1

TAN

dttN

TAN

T

TAN

TTE

T

TAN

i

Vi

Vges

V


Satz von Little (V)

Mit

ergibt sich

Es ist jedoch

die mittlere Forderungsrate.

][)( VVges TETANT

][)(

)]([ VTET

TANtNE

T

TAN )(


Satz von Little (VI)

Satz von Little:

Existieren für T∞ die Grenzwerte λ(T) = λ

und E[TV], so existiert auch der Grenzwert

von E[N(T)] = E[N] und es gilt

E[N] = λ • E[TV]


Die Kendall-Notation (I)

Berücksichtigung der wichtigsten Eigenschaften von Bediensystemen: Forderungsstrom

Bedienprozess / je Kanal

Wartemöglichkeiten

Zahl der Bedienkanäle

Allgemeine Form: A/B/C/D/E/F mit A: Repräsentation des Forderungsstroms

B: Repräsentation des Bedienprozesses

C: Anzahl der Bedienkanäle (Server)

D: Bedienstrategie

E: Zahl der Warteplätze

F: Zahl der Forderungsquellen

Einfachster Fall


Die Kendall-Notation (II)

Beschreibungen des Forderungsstroms bzw. des Bedienprozesses: M = Exponentiell (Markov)

Statistisch unabhängig, gedächtnislos

Ek = Erlang-Verteilung k-ter Ordnung

Hn = Hyper-Exponentialverteilung n-ter Ordnung

D = Deterministisch

G = General Willkürliche beliebige Zufallsfunktion

GI = General Independent Erneuerungsprozess

Es existiert eine identische unabhängige Verteilungsfunktion für die Einfallsabstände aufeinander folgender Ereignisse


Die Kendall-Notation (III)

Zusätzliche modifizierte Klammerschreibweisen mit zusätzlichen Angaben über Anzahl von Quellen

Anzahl von Senken

Anzahl der Warteplätze

Beispiele M/M/1

M/M/1/s(0)

M(n)/M/1/s(0)

M(n)/M/1/-/s(10)

Achtung: Notation ist nicht vollständig eindeutig, die ersten drei Positionen sind es aber immer.


Bedienstrategie

FCFS (First Come First Serve) Abarbeitungsreihenfolge entspricht der Ankunftsreihenfolge

LCFS (Last Come First Serve) Abarbeitung in umgekehrter Ankunftsreihenfolge

SIRO (Serve In Random Order) Zufällige Auswahl eines Auftrags in der Warteschlange

SPT (Shortest Processing Time) Auswahl des Prozesses mit der kürzesten Bedienzeit

Statische Prioritäten Auswahl erfolgt anhand von Prioritäten der Aufträge, innerhalb einer Stufe dann

FIFO oder LIFO

Statische Prioritäten mit Verdrängung Wie bei statischen Prioritäten, nur dass jetzt ein neu hinzugekommener

hochpriorer Auftrag die aktuelle Bearbeitung eines niederprioren Auftrags unterbrechen kann

Round Robin Aufträge werden in Zeitscheiben bedient, nach Ende der Zeitscheibe kommt der

nächste Auftrag an die Reihe


Das M/M/1 - Bediensystem

Ankunftsrate

m

Bedienrate

BedieneinheitWarteschlange

Aktuelle

Warte-

schlangen-

Länge L

Auftrag


Gewünschte Aussagen

Zustandswahrscheinlichkeit p(k) Wahrscheinlichkeit, dass k Aufträge im System sind

Auslastung r Bruchteil der Gesamtzeit, den die Bedieneinheit(en) belegt sind

Durchsatz

Mittlere Verweilzeit TV

Mittelwert für die Dauer, die ein Auftrag im System verbringt

Mittlere Wartezeit TW

Mittelwert für die Dauer, die ein Auftrag in der Warteschlange verbringt

Mittlere Anzahl K der Aufträge im System

Mittlere Warteschlangenlänge L

Documents

Bedienungs-und Verkehrstheoriemidas1.e-technik.tu-ilmenau.de/~webkn/Webdaten/Lehre/WS2015... · BVT WS 2015/16 0. Organisatorisches 3 Gliederung II 4. Verkehrstheorie leitungsvermittelter