Efektywność systemów
informatycznych
Wykład 11
TEMAT: Analiza opóźnień w sieciach
kolejkowych
Efektywność systemów
informatycznych
Wykład 11
TEMAT: Analiza opóźnień w sieciach
kolejkowych
2
Wstęp
Analiza opóźnień w sieciach kolejkowych
Analiza opóźnień w sieciach kolejkowych
polega na wyznaczeniu charakterystyk czasu
polega na wyznaczeniu charakterystyk czasu
pobytu zgłoszenia w sieci.
pobytu zgłoszenia w sieci.
Wyznaczanie wartości średnich
Wyznaczanie wartości średnich
(oczekiwanych) jest możliwa przy
(oczekiwanych) jest możliwa przy
wykorzystaniu np. Metody analizy średnich
wykorzystaniu np. Metody analizy średnich
(MVA).
(MVA).
Analiza opóźnień polegająca na wyznaczaniu
Analiza opóźnień polegająca na wyznaczaniu
rozkładu czasu pobytu zgłoszenia w sieci jest
rozkładu czasu pobytu zgłoszenia w sieci jest
możliwa jedynie dla sieci o wybranych
możliwa jedynie dla sieci o wybranych
strukturach – wybranych sposobach
strukturach – wybranych sposobach
poruszania się zgłoszeń w sieci.
poruszania się zgłoszeń w sieci.
3
Analiza opóźnień w sieci szeregowej
Rozpatrzmy sieć składająca się z szeregowo
Rozpatrzmy sieć składająca się z szeregowo
połączonych systemów kolejkowych typu M|M|
połączonych systemów kolejkowych typu M|M|
1|
1|
|FIFO
|FIFO
Twierdzenie 11.1
Twierdzenie 11.1
W sieci składającej się z szeregowo połączonych
W sieci składającej się z szeregowo połączonych
systemów typu M|M|1|
systemów typu M|M|1|
|FIFO, czasy
|FIFO, czasy
przebywania ustalonego zgłoszenia w
przebywania ustalonego zgłoszenia w
poszczególnych węzłach w trybie stacjonarnym
poszczególnych węzłach w trybie stacjonarnym
(po nieskończonym czasie) są zmiennymi
(po nieskończonym czasie) są zmiennymi
losowymi, pod warunkiem, ze spełniony jest w
losowymi, pod warunkiem, ze spełniony jest w
każdym węźle warunek ergodyczności:
każdym węźle warunek ergodyczności:
.
.
m
j
j
,..
1
,
1
2
m
1
2
m
4
Analiza opóźnień w sieci szeregowej
- 2
Przyjmijmy następujące oznaczenia:
Przyjmijmy następujące oznaczenia:
- czasy pobytu w kolejnych węzłach
- czasy pobytu w kolejnych węzłach
sieci,
sieci,
- łączny czas pobytu w sieci,
- łączny czas pobytu w sieci,
dystrybuanta
dystrybuanta
czasu
czasu
pobytu zgłoszenia w systemie M|M|1|
pobytu zgłoszenia w systemie M|M|1|
|FIFO,
|FIFO,
stąd:
stąd:
, zatem:
, zatem:
,
,..,
1 m
j
V
j
V
0
,
1
}
{
)
(
)
(
t
e
T
V
P
t
F
t
j
j
j
j
j
V
s
V
s
t
F
L
s
f
j
j
))
(
(
)
(
*
m
j
j
j
V
s
V
s
t
F
L
s
f
1
*
))
(
(
)
(
5
Analiza opóźnień w sieci szeregowej
- 3
Prostym uogólnieniem jest przyjęcie, że ostatni
Prostym uogólnieniem jest przyjęcie, że ostatni
w szeregu jest system typu M|G|n. Wówczas:
w szeregu jest system typu M|G|n. Wówczas:
gdzie
gdzie
jest transformatą L-S
jest transformatą L-S
dystrybuanty rozkładu czasu przebywania
dystrybuanty rozkładu czasu przebywania
zgłoszenia w m-tym węźle typu M|G|n.
zgłoszenia w m-tym węźle typu M|G|n.
)
(
))
(
(
)
(
*
1
1
*
s
f
s
t
F
L
s
f
m
V
m
j
j
j
V
s
V
)
(
*
s
f
m
V
6
Analiza opóźnień w sieci typu
dendryt
Zakres obowiązywania Tw.11. można rozszerzyć
Zakres obowiązywania Tw.11. można rozszerzyć
na sieci o innej postaci niż szeregowo połączone
na sieci o innej postaci niż szeregowo połączone
systemy kolejkowe.
systemy kolejkowe.
Rozpatrzmy sieć o strukturze dendrytu:
Rozpatrzmy sieć o strukturze dendrytu:
1
2
3
4
5
7
Analiza opóźnień w sieci typu
dendryt - 2
Twierdzenie 11.2
Twierdzenie 11.2
Czasy przebywania zgłoszenia w kolejnych węzłach
Czasy przebywania zgłoszenia w kolejnych węzłach
ustalonej drogi w sieci kolejkowej o strukturze
ustalonej drogi w sieci kolejkowej o strukturze
dendrytu z węzłami typu M|M|1|
dendrytu z węzłami typu M|M|1|
|FIFO są
|FIFO są
niezależnymi zmiennymi losowymi, przy założeniu,
niezależnymi zmiennymi losowymi, przy założeniu,
że
że
dla każdego węzła rozpatrywanej drogi.
dla każdego węzła rozpatrywanej drogi.
Jeśli przyjmiemy zatem, że zgłoszenie przebywa
Jeśli przyjmiemy zatem, że zgłoszenie przebywa
drogę
drogę
to transformata L-S dystrybuanty rozkładu
to transformata L-S dystrybuanty rozkładu
czasu pokonywania drogi
czasu pokonywania drogi
d
d
ma postać:
ma postać:
(11.1)
(11.1)
gdzie:
gdzie:
, a
, a
intensywność
intensywność
strumienia wejściowego do sieci.
strumienia wejściowego do sieci.
j
)
,...,
(
1
K
d
d
d
K
i
d
d
d
d
d
i
i
i
i
s
s
f
1
*
)
(
i
i
i
d
d
d
d
d
d
d
q
q
q
1
3
2
2
1
....
8
Analiza opóźnień w sieci typu
dendryt - 3
Można teraz wyznaczyć rozkład czasu pobytu
Można teraz wyznaczyć rozkład czasu pobytu
dowolnego zgłoszenia w sieci typu dendryt.
dowolnego zgłoszenia w sieci typu dendryt.
Dysponując macierzą
Dysponując macierzą
Q
Q
0
0
opisująca ruch
opisująca ruch
zgłoszeń w sieci, transformatę L-S dystrybuanty
zgłoszeń w sieci, transformatę L-S dystrybuanty
czasu pokonywania sieci przez ustalone
czasu pokonywania sieci przez ustalone
zgłoszenie po dowolnej drodze można opisać
zgłoszenie po dowolnej drodze można opisać
następująca zależnością:
następująca zależnością:
(11.2)
(11.2)
gdzie:
gdzie:
D
D
- zbiór wszystkich możliwych dróg w
- zbiór wszystkich możliwych dróg w
dendrycie rozpoczynających się w korzeniu
dendrycie rozpoczynających się w korzeniu
dendrytu, a kończących się w wierzchołku bez
dendrytu, a kończących się w wierzchołku bez
następnika,
następnika,
D
d
K
i
d
d
d
d
d
V
d
i
i
i
i
s
p
s
f
1
*
)
(
i
i
d
d
d
d
d
d
d
q
q
q
1
3
2
2
1
....
d
K
d
K
d
d
d
d
d
d
d
q
q
q
p
1
3
2
2
1
....
Prawdopodobieństwo
Prawdopodobieństwo
wyboru drogi d.
wyboru drogi d.
9
Uogólniona analiza opóźnień w
sieciach
Rozpatrzmy siec kolejkowa spełniającą
Rozpatrzmy siec kolejkowa spełniającą
następujące założenia:
następujące założenia:
1.
1.
Węzły sieci stanowią systemy typu *|M|1|
Węzły sieci stanowią systemy typu *|M|1|
|FIFO
|FIFO
2.
2.
Zgłoszenia przybywające do sieci należą do R
Zgłoszenia przybywające do sieci należą do R
typów,
typów,
R
R
={1,2,...,R},
={1,2,...,R},
3.
3.
Typ zgłoszenia jest określony przez :
Typ zgłoszenia jest określony przez :
Parę wierzchołków
Parę wierzchołków
(s, d)
(s, d)
gdzie
gdzie
s
s
– punkt wejściowy do
– punkt wejściowy do
sieci, a
sieci, a
d
d
- wierzchołek docelowy,
- wierzchołek docelowy,
Drogę miedzy wierzchołkami
Drogę miedzy wierzchołkami
s
s
i
i
d
d
,
,
Droga może być:
Droga może być:
jedna ustalona (droga prosta),
jedna ustalona (droga prosta),
Wybierana losowo ze zbioru rozłącznych (poza
Wybierana losowo ze zbioru rozłącznych (poza
wierzchołkami początkowym i końcowym) dróg prostych
wierzchołkami początkowym i końcowym) dróg prostych
4.
4.
Zgłoszenia r-tego typu przybywają do systemu
Zgłoszenia r-tego typu przybywają do systemu
zgodnie ze strumieniem Poissona o
zgodnie ze strumieniem Poissona o
intensywności
intensywności
r,
r,
5.
5.
Czas obsługi dowolnego zgłoszenia w i-tym
Czas obsługi dowolnego zgłoszenia w i-tym
węźle ma rozkład wykładniczy z parametrem
węźle ma rozkład wykładniczy z parametrem
W
i
i
,
10
Uogólniona analiza opóźnień w
sieciach -2
Rozpatrzmy w pierwszej kolejności zgłoszenia
Rozpatrzmy w pierwszej kolejności zgłoszenia
poruszające się po ustalonych pojedynczych
poruszające się po ustalonych pojedynczych
drogach,
drogach,
Przez
Przez
a(r)
a(r)
oznaczymy zbiór węzłów należących
oznaczymy zbiór węzłów należących
do drogi między wierzchołkami
do drogi między wierzchołkami
(s
(s
r
r
, d
, d
r
r
)
)
zgłoszeń typu
zgłoszeń typu
r
r
,
,
Niech
Niech
oznacza intensywności napływu
oznacza intensywności napływu
zgłoszeń r-tego typu do węzła i-tego. Z
zgłoszeń r-tego typu do węzła i-tego. Z
przyjętych założeń wynika, że:
przyjętych założeń wynika, że:
(11.3)
(11.3)
Niech
Niech
będzie obciążeniem i-tego węzła
będzie obciążeniem i-tego węzła
przez zgłoszenia r-tego typu. Wobec
przez zgłoszenia r-tego typu. Wobec
przyjętych założeń otrzymujemy:
przyjętych założeń otrzymujemy:
R
r
W
i
ir
,..,
1
,
,..,
1
,
)
(
jesli
0
)
(
jesli
r
a
i
r
a
i
r
ir
ir
R
r
W
i
i
ir
ir
,..,
1
,
,..,
1
,
(11.4)
11
Uogólniona analiza opóźnień w
sieciach -3
Całkowite obciążenie węzła i-tego wynosi
Całkowite obciążenie węzła i-tego wynosi
(11.5)
(11.5)
Zakładamy, że przy danych
Zakładamy, że przy danych
spełniony jest warunek
spełniony jest warunek
Oznaczmy przez
Oznaczmy przez
V
V
r
r
czas pokonywania sieci
czas pokonywania sieci
przez zgłoszenie r-tego typu.
przez zgłoszenie r-tego typu.
Niech
Niech
Można sformułować następujące twierdzenie:
Można sformułować następujące twierdzenie:
R
r
ir
i
1
i
r
r
a
,
),
(
W
i
i
,..,
1
,
1
)]
(
[
)
(
},
{
)
(
*
t
T
L
s
t
t
V
P
t
T
r
s
r
r
r
12
Uogólniona analiza opóźnień w
sieciach -4
Twierdzenie 11.3
Twierdzenie 11.3
Dla opisanej wyżej sieci kolejkowej z ustaloną droga
Dla opisanej wyżej sieci kolejkowej z ustaloną droga
dla zgłoszeń r-tego typu funkcja
dla zgłoszeń r-tego typu funkcja
ma
ma
postać:
postać:
(11.6)
(11.6)
Z twierdzenia 11.3 wynika, że czas przejścia
Z twierdzenia 11.3 wynika, że czas przejścia
przez sieć zgłoszeń r-tego typu można traktować
przez sieć zgłoszeń r-tego typu można traktować
jako sumę niezależnych zmiennych losowych
jako sumę niezależnych zmiennych losowych
oznaczających czasy pobytu w poszczególnych
oznaczających czasy pobytu w poszczególnych
węzłach należących do drogi
węzłach należących do drogi
a(r).
a(r).
Z (11.6) wynika również, że:
Z (11.6) wynika również, że:
(11.6A)
(11.6A)
)
(
*
)
1
(
)
1
(
)
(
r
a
i
i
i
i
i
r
s
s
t
)
(
*
s
t
r
)
(
)
1
(
1
r
a
i
i
i
r
EV
13
Uogólniona analiza opóźnień w
sieciach -5
Rozpatrzymy obecnie przypadek losowego doboru
Rozpatrzymy obecnie przypadek losowego doboru
drogi dla zgłoszeń r-tego typu,
drogi dla zgłoszeń r-tego typu,
Niech
Niech
k
k
r
r
oznacza liczbę możliwych dróg dla
oznacza liczbę możliwych dróg dla
zgłoszeń r-tego typu,
zgłoszeń r-tego typu,
Przez
Przez
a
a
j
j
(r)
(r)
oznaczymy węzły należące do j-tej drogi
oznaczymy węzły należące do j-tej drogi
zgłoszeń r-tego typu,
zgłoszeń r-tego typu,
Niech
Niech
q
q
j
j
(r)
(r)
oznacza prawdopodobieństwo wyboru
oznacza prawdopodobieństwo wyboru
j-tej drogi przez zgłoszenie r-tego typu,
j-tej drogi przez zgłoszenie r-tego typu,
W celu wyznaczenia rozkładu czasu pokonywania
W celu wyznaczenia rozkładu czasu pokonywania
sieci przez zgłoszenie r-tego typu wykorzystamy
sieci przez zgłoszenie r-tego typu wykorzystamy
Tw.11.3.
Tw.11.3.
W tym celu przyjmijmy, ze zgłoszenia r-tego typu
W tym celu przyjmijmy, ze zgłoszenia r-tego typu
poruszające się po j-tej drodze stanowią odrębny
poruszające się po j-tej drodze stanowią odrębny
typ
typ
r
r
j,
j,
Otrzymujemy zatem następujace typy zgłoszeń:
Otrzymujemy zatem następujace typy zgłoszeń:
R
R
={
={
r
r
j
j
: r=1,..,R, j=1,..,k
: r=1,..,R, j=1,..,k
r
r
},
},
14
Uogólniona analiza opóźnień w
sieciach -6
Z przyjętych założeń wynika, że intensywność
Z przyjętych założeń wynika, że intensywność
napływu zgłoszeń typu
napływu zgłoszeń typu
r
r
j
j
wynosi:
wynosi:
(11.7)
(11.7)
Oraz intensywność napływu zgłoszeń typu
Oraz intensywność napływu zgłoszeń typu
r
r
j
j
do
do
węzła i-tego wynosi:
węzła i-tego wynosi:
(11.7A)
(11.7A)
a obciążenie węzła i-tego ma postać:
a obciążenie węzła i-tego ma postać:
(11.7B)
(11.7B)
)
(
)
(
r
q
r
j
r
j
)
(
jesli
0
)
(
jesli
)
(
r
a
i
r
a
i
r
j
j
j
ir
j
R
r
k
j
i
ir
i
r
j
1
1
15
Uogólniona analiza opóźnień w
sieciach -7
Stosując twierdzenie 11.3 otrzymujemy
Stosując twierdzenie 11.3 otrzymujemy
zależności:
zależności:
(11.8)
(11.8)
gdzie:
gdzie:
W celu uzyskania rozkładu czasu pokonywania
W celu uzyskania rozkładu czasu pokonywania
sieci przez zgłoszenie r-tego typu po dowolnej
sieci przez zgłoszenie r-tego typu po dowolnej
z
z
k
k
r
r
dróg możemy skorzystać z następującej
dróg możemy skorzystać z następującej
zależności:
zależności:
(11.9)
(11.9)
)
(
*
)
1
(
)
1
(
)
(
r
a
i
i
i
i
i
r
j
j
s
s
t
}
{
)
(
)],
(
[
)
(
*
t
V
P
t
T
t
T
L
s
t
j
j
j
j
r
r
r
s
r
r
j
k
j
r
j
r
s
t
r
q
s
t
1
*
*
)
(
)
(
)
(