Efektywność systemów
informatycznych
Wykład 8
TEMAT:Niemarkowskie sieci
kolejkowe
Efektywność systemów
informatycznych
Wykład 8
TEMAT:Niemarkowskie sieci
kolejkowe
2
Rozkład Coxa
Zmienna losowa
Zmienna losowa
X
X
ma rozkład Coxa, jeśli można
ma rozkład Coxa, jeśli można
jej wartość interpretować, jako czas
jej wartość interpretować, jako czas
przechodzenia pojedynczego zgłoszenie przez
przechodzenia pojedynczego zgłoszenie przez
system przedstawiony na poniższym rysunku:
system przedstawiony na poniższym rysunku:
Zgłoszenie trafia do systemu k stacji
Zgłoszenie trafia do systemu k stacji
(serwerów) i porusza się w nim według
(serwerów) i porusza się w nim według
następujących zasad:
następujących zasad:
Czas pobytu w
Czas pobytu w
i-tej
i-tej
stacji jest zmienną losową o
stacji jest zmienną losową o
rozkładzie
rozkładzie
wykładniczym z parametrem
wykładniczym z parametrem
i
i
,
,
Po opuszczeniu
Po opuszczeniu
i-tej
i-tej
stacji, zgłoszenie z
stacji, zgłoszenie z
prawdopodobieństwem
prawdopodobieństwem
b
b
i
i
trafia do stacji
trafia do stacji
i+1-
i+1-
szej,
szej,
a z prawdopodobieństwem
a z prawdopodobieństwem
1-b
1-b
i
i
opuszcza system.
opuszcza system.
1
1
2
2
k
k
b
b
0
0
1-b
1-b
0
0
b
b
1
1
1-b
1-b
1
1
b
b
2
2
1-b
1-b
2
2
b
b
k
k
=0
=0
1-b
1-b
k
k
=1
=1
3
Rozkład Coxa - 2
Rozkład zmiennej losowej
Rozkład zmiennej losowej
X
X
określa dystrybuanta:
określa dystrybuanta:
gdzie:
gdzie:
(8.1)
(8.1)
Jeśli
Jeśli
to
to
Wynika stąd, że
Wynika stąd, że
A
A
i
i
oznacza prawdopodobieństwo,
oznacza prawdopodobieństwo,
tego, że zgłoszenie dojdzie do i-tej stacji. Z (8.1)
tego, że zgłoszenie dojdzie do i-tej stacji. Z (8.1)
wynika, że:
wynika, że:
(8.3)
(8.3)
)
(
...
...
....
)
(
)
1
(
)
(
)
1
(
1
}
{
)
(
2
1
1
1
0
2
1
2
1
0
1
0
1
0
x
F
F
F
b
b
b
x
F
F
b
b
b
x
F
b
b
b
x
X
P
x
F
k
k
0
,
,..
1
,
1
)
(
k
x
i
b
k
i
e
x
F
i
))
(
(
)
(
*
x
F
L
s
f
s
)
2
.
8
(
:
)
1
(
1
)
(
1
0
1
1
0
*
i
r
r
i
k
i
i
j
j
j
i
i
b
A
gdzie
s
b
A
b
s
f
k
j
j
j
A
X
E
1
}
{
4
Rozkład Coxa - 3
Rozkład zmiennej Coxa jest jest uogólnieniem
Rozkład zmiennej Coxa jest jest uogólnieniem
rozkładu wykładniczego:
rozkładu wykładniczego:
- rozkład wykładniczy
- rozkład wykładniczy
Za pomocą dystrybuanty rozkładu Coxa można
Za pomocą dystrybuanty rozkładu Coxa można
przybliżyć z dowolna dokładnością dystrybuantę
przybliżyć z dowolna dokładnością dystrybuantę
dowolnego rozkładu ciągłego.
dowolnego rozkładu ciągłego.
Rozkład Coxa o k fazach oznacza się jako
Rozkład Coxa o k fazach oznacza się jako
C
C
k
k
.
.
x
e
x
F
x
F
b
b
1
1
)
(
)
(
1
,
1
1
1
0
5
Sieci niemarkowskie
W dalszym ciągu, będą rozpatrywane sieci
W dalszym ciągu, będą rozpatrywane sieci
spełniające następujące założenia:
spełniające następujące założenia:
występuje wiele typów węzłów:
występuje wiele typów węzłów:
M|M|n (typ 1),
M|M|n (typ 1),
*|C
*|C
k
k
|PS (typ 2),
|PS (typ 2),
*|C
*|C
k
k
|IS = *|C
|IS = *|C
k
k
|
|
(typ 3), (IS – infinite server)
(typ 3), (IS – infinite server)
*|C
*|C
k
k
|LIFO-PR (typ 4).
|LIFO-PR (typ 4).
występuje
występuje
R
R
klas (typów) zgłoszeń,
klas (typów) zgłoszeń,
R
R
={1,...,R}
={1,...,R}
– zbiór numerów typów zgłoszeń,
– zbiór numerów typów zgłoszeń,
Przed rozpoczęciem analizy sieci niemarkowskich
Przed rozpoczęciem analizy sieci niemarkowskich
omówione zostanie analiza pojedynczych
omówione zostanie analiza pojedynczych
systemów kolejkowych wymienionych wyżej typów.
systemów kolejkowych wymienionych wyżej typów.
Analizując pojedyncze systemy, zakładamy, że
Analizując pojedyncze systemy, zakładamy, że
zgłoszenia
zgłoszenia
r-tego
r-tego
typu
typu
przybywają do nich zgodnie ze
przybywają do nich zgodnie ze
strumieniem Poissona o intensywności
strumieniem Poissona o intensywności
.
.
r
6
Sieci niemarkowskie - 2
Przyjmujemy do dalszej analizy następujące oznaczenia:
Przyjmujemy do dalszej analizy następujące oznaczenia:
- rozkład Coxa o
- rozkład Coxa o
J
J
r
r
fazach obsługi dla zgłoszenia
fazach obsługi dla zgłoszenia
r-tego
r-tego
typu,
typu,
- parametr rozkładu czasu trwania
- parametr rozkładu czasu trwania
s-tej
s-tej
fazy czasu
fazy czasu
obsługi
obsługi
zgłoszenia
zgłoszenia
r-tego
r-tego
typu,
typu,
- prawdopodobieństwo przejścia do fazy
- prawdopodobieństwo przejścia do fazy
(s+1)-szej
(s+1)-szej
po
po
zakończeniu fazy
zakończeniu fazy
s-tej
s-tej
,
,
- prawdopodobieństwo osiągnięcia fazy
- prawdopodobieństwo osiągnięcia fazy
s
s
, przy
, przy
czym
czym
dla
dla
s=J
s=J
r
r
mamy
mamy
b
b
rs
rs
=0
=0
,
,
Średni czas obsługi zgłoszenia
Średni czas obsługi zgłoszenia
r-tego
r-tego
typu:
typu:
Przez
Przez
oznaczymy współczynnik obciążenia systemu przez
oznaczymy współczynnik obciążenia systemu przez
zgłoszenia
zgłoszenia
r-tego
r-tego
typu, a współczynnik obciążenia
typu, a współczynnik obciążenia
systemu wszystkimi typami zgłoszeń wyniesie:
systemu wszystkimi typami zgłoszeń wyniesie:
.
.
r
J
C
rs
1
0
s
i
ri
rs
b
A
rs
b
r
J
s
rs
rs
r
A
1
1
r
r
r
R
r
r
1
7
Węzeł typu 1 (M|M|n||FIFO)
Przyjmuje się założenie, że w węźle tego typu
Przyjmuje się założenie, że w węźle tego typu
wszystkie zgłoszenia mają jednakowy
wszystkie zgłoszenia mają jednakowy
wykładniczy rozkład czasu obsługi z
wykładniczy rozkład czasu obsługi z
parametrem
parametrem
. Charakterystyki graniczne dla
. Charakterystyki graniczne dla
systemów tej klasy zostały omówione w
systemów tej klasy zostały omówione w
wykładach wcześniejszych.
wykładach wcześniejszych.
8
Węzeł typu 2 (*|C|n|PS)
Jako model funkcjonowania węzła rozpatrzmy
Jako model funkcjonowania węzła rozpatrzmy
proces:
proces:
- liczba zgłoszeń typu
- liczba zgłoszeń typu
r
r
, które w chwili
, które w chwili
t
t
znajdują się w
znajdują się w
s-tej
s-tej
fazie obsługi.
fazie obsługi.
Zbiór stanów procesu można zdefiniować
Zbiór stanów procesu można zdefiniować
następująco:
następująco:
Przyjmijmy dodatkowe oznaczenia:
Przyjmijmy dodatkowe oznaczenia:
- liczba zgłoszeń r-tego typu w węźle,
- liczba zgłoszeń r-tego typu w węźle,
- liczba wszystkich zgłoszeń w węźle.
- liczba wszystkich zgłoszeń w węźle.
)
(
),..,
(
)
(
gdzie
,
)
(
),..,
(
)
(
1
1
t
X
t
X
t
X
t
X
t
X
t
X
r
rJ
r
r
R
)
(t
X
rs
}
,..
1
,
,..,
1
,..},
2
,
1
,
0
{
),
,...,
(
:
)
,...,
(
{
1
1
R
r
J
s
n
n
n
n
n
n
n
r
rs
rJ
r
r
R
r
X
r
J
s
rs
r
n
n
1
R
r
r
n
n
1
9
Węzeł typu 2 (*|C|n|PS) - 2
Można wykazać, że
Można wykazać, że
X(t)
X(t)
jest jednorodnym procesem
jest jednorodnym procesem
Markowa klasy DC. Jeśli
Markowa klasy DC. Jeśli
, to jego rozkład
, to jego rozkład
graniczny określony jest zależnościami:
graniczny określony jest zależnościami:
(8.4)
(8.4)
Jeśli interesuje nas jedynie liczba zgłoszeń
Jeśli interesuje nas jedynie liczba zgłoszeń
określonych typów, to rozpatrujemy następujący
określonych typów, to rozpatrujemy następujący
proces:
proces:
, gdzie:
, gdzie:
- liczba zgłoszeń r-tego typu w węźle.
- liczba zgłoszeń r-tego typu w węźle.
Zbiór stanów procesu
Zbiór stanów procesu
Y(t)
Y(t)
:
:
1
X
n
A
n
n
n
n
R
r
J
s
n
rs
rs
r
rs
R
n
r
rs
,
!
1
!
)
1
(
)
,..,
(
1
1
1
)
(
),...,
(
)
(
1
t
Y
t
Y
t
Y
R
)
(t
Y
r
}
,..},
2
,
1
,
0
{
:
)
,...,
(
{
1
R
Y
r
y
R
y
y
y
r
R
R
10
Węzeł typu 2 (*|C|n|PS) - 3
Można wykazać, że jeśli
Można wykazać, że jeśli
, to rozkład
, to rozkład
graniczny procesu
graniczny procesu
Y(t)
Y(t)
, określają zależności:
, określają zależności:
(8.4.A)
(8.4.A)
Przy dalszej agregacji stanu, kiedy interesuje
Przy dalszej agregacji stanu, kiedy interesuje
nas jedynie liczba wszystkich zgłoszeń łącznie,
nas jedynie liczba wszystkich zgłoszeń łącznie,
rozpatrujemy proces:
rozpatrujemy proces:
Jego rozkład graniczny określają zależności:
Jego rozkład graniczny określają zależności:
(8.4.B)
(8.4.B)
1
R
r
r
R
r
r
y
r
t
y
y
y
y
y
y
y
t
Y
P
r
1
1
:
gdzie
,
!
!
)
1
(
}
)
(
{
lim
Y
R
r
r
t
Y
t
Z
1
..}
,
2
,
1
,
0
{
),
(
)
(
Z
Z
z
z
t
Z
P
z
t
z
,
)
1
(
}
)
(
{
lim
11
Węzeł typu 3 (*|C|IS)
Proces
Proces
X(t)
X(t)
opisujący stan węzła jest identyczny
opisujący stan węzła jest identyczny
jak dla systemu typu 2. Jego rozkład graniczny
jak dla systemu typu 2. Jego rozkład graniczny
jest określony, w tym przypadku, zależnościami:
jest określony, w tym przypadku, zależnościami:
(8.5)
(8.5)
Po agregacji stanów, rozpatrujemy proces
Po agregacji stanów, rozpatrujemy proces
Y(t)
Y(t)
i
i
otrzymujemy następujący rozkład graniczny:
otrzymujemy następujący rozkład graniczny:
(8.5.A)
(8.5.A)
Dla procesu
Dla procesu
Z(t)
Z(t)
, postać rozkładu granicznego
, postać rozkładu granicznego
jest następująca:
jest następująca:
(8.5.B)
(8.5.B)
X
n
A
n
e
R
r
J
s
n
rs
rs
r
rs
n
r
rs
,
!
1
1
1
Y
y
y
e
R
r
r
y
r
y
r
1
!
..}
,
2
,
1
,
0
{
,
!
z
z
e
z
z
12
Węzeł typu 4 (*|C
k
|LIFO-PR )
Węzeł typu 4 pracuje w ten sposób, że zgłoszenie
Węzeł typu 4 pracuje w ten sposób, że zgłoszenie
przybywając do systemu, przerywa obsługę
przybywając do systemu, przerywa obsługę
aktualnie obsługiwanego zgłoszenia (jeśli system
aktualnie obsługiwanego zgłoszenia (jeśli system
przed jego przybyciem nie był pusty) i trafia do
przed jego przybyciem nie był pusty) i trafia do
kanału obsługi. Zgłoszenie, którego obsługę
kanału obsługi. Zgłoszenie, którego obsługę
przerwano, trafia na pierwsze miejsce w kolejce.
przerwano, trafia na pierwsze miejsce w kolejce.
W momencie zwolnienia się kanału obsługi,
W momencie zwolnienia się kanału obsługi,
obsługa tego zgłoszenia jest kontynuowana od
obsługa tego zgłoszenia jest kontynuowana od
miejsca, w którym ja przerwano.
miejsca, w którym ja przerwano.
Jako model funkcjonowania węzła przyjmuje się
Jako model funkcjonowania węzła przyjmuje się
proce
proce
X(t)
X(t)
o następującej przestrzeni stanów:
o następującej przestrzeni stanów:
Przyjmuje się, że zgłoszeniem obsługiwanym jest
Przyjmuje się, że zgłoszeniem obsługiwanym jest
zgłoszenie
zgłoszenie
, pozostałe zaś oczekują w kolejce.
, pozostałe zaś oczekują w kolejce.
}
..,
,
1
},
..,
,
2
,
1
{
,
:
))
,
(
...,
),
,
((
{
1
1
n
i
J
s
r
s
r
s
r
n
i
r
i
i
n
n
R
X
)
,
(
n
n
s
r
13
Węzeł typu 4 (*|C
k
|LIFO-PR ) - 2
Rozkład graniczny procesu
Rozkład graniczny procesu
X(t)
X(t)
określają zależności:
określają zależności:
Warunkiem istnienia rozkładu granicznego jest
Warunkiem istnienia rozkładu granicznego jest
spełnienie warunku
spełnienie warunku
.
.
Rozkład graniczny procesu
Rozkład graniczny procesu
określają
określają
zależności:
zależności:
(8.6.A)
(8.6.A)
Rozkład graniczny procesu
Rozkład graniczny procesu
Z(t)
Z(t)
, określony jest
, określony jest
następująco:
następująco:
(8.6.B)
(8.6.B)
)
.
(
n
A
s
r
s
r
n
j
s
r
s
r
r
n
n
n
j
j
j
j
j
6
8
,
)
1
(
))
,
(
...,
),
,
((
1
,
)
,
(
1
1
X
1
R
r
r
t
Y
t
Y
)
(
)
(
R
r
r
R
R
r
r
y
r
y
y
y
y
y
y
y
y
r
1
1
1
..,
,
,
!
!
)
1
(
...}
,
2
,
0
{
,
)
1
(
z
z
z
14
Model ruchu zgłoszeń w sieci
Przyjmujemy, że zgłoszenia poruszają się w sieci
Przyjmujemy, że zgłoszenia poruszają się w sieci
zgodnie z poniższymi założeniami:
zgodnie z poniższymi założeniami:
każde zgłoszenie porusza się w sieci niezależnie od
każde zgłoszenie porusza się w sieci niezależnie od
innych zgłoszeń,
innych zgłoszeń,
jeśli zgłoszenie znajdzie się w konkretnym węźle to
jeśli zgłoszenie znajdzie się w konkretnym węźle to
jego dalsza droga zależy jedynie od numeru tego
jego dalsza droga zależy jedynie od numeru tego
węzła, a nie zależy od dotychczasowej jego drogi,
węzła, a nie zależy od dotychczasowej jego drogi,
przejście zgłoszenia między węzłami wewnętrznymi
przejście zgłoszenia między węzłami wewnętrznymi
sieci opisuje macierz.
sieci opisuje macierz.
Ruch zgłoszeń w sieci opisuje macierz
Ruch zgłoszeń w sieci opisuje macierz
Q
Q
0
0
:
:
gdzie:
gdzie:
oznacza prawdopodobieństwo tego, że
oznacza prawdopodobieństwo tego, że
zgłoszenie
zgłoszenie
r-tego
r-tego
typu opuszczając
typu opuszczając
i-ty
i-ty
węzeł trafi
węzeł trafi
do węzła
do węzła
j-tego
j-tego
stając się zgłoszeniem
stając się zgłoszeniem
s-tego
s-tego
typu.
typu.
R
W
s
r
j
i
js
ir
q
Q
,
,
,
0
0
js
ir
q
,
15
Model ruchu zgłoszeń w sieci - 2
Jeśli przez
Jeśli przez
X
X
k
k
oznaczymy proces, którego
oznaczymy proces, którego
(i,r)
(i,r)
oznacza, że zgłoszenie w
oznacza, że zgłoszenie w
k-tym
k-tym
kroku znajduje
kroku znajduje
się węźle
się węźle
i-tym
i-tym
i jest
i jest
r-tego
r-tego
typu, to zbiór stanów
typu, to zbiór stanów
tego procesu jest następujący:
tego procesu jest następujący:
Z definicji wynika, ze proces
Z definicji wynika, ze proces
X
X
k
k
jest procesem
jest procesem
Markowa klasy DD o macierzy
Markowa klasy DD o macierzy
prawdopodobieństw przejść w jednym kroku
prawdopodobieństw przejść w jednym kroku
określonej zależnością:
określonej zależnością:
Dwa typy zgłoszeń nazwiemy wymienialnymi,
Dwa typy zgłoszeń nazwiemy wymienialnymi,
jeśli
jeśli
R
W
s
r
j
i
js
ir
q
Q
,
,
,
0
0
}
0
{
}
,
:
)
,
{(
0
0
R
W
X
r
i
r
i
0
)
(
0
)
(
,
,
,
0
,
0
,
0
,
t
p
p
k
l
j
i
t
kr
ls
js
ir
W
16
Model ruchu zgłoszeń w sieci - 3
gdzie
gdzie
prawdopodobieństwo przejścia ze stanu
prawdopodobieństwo przejścia ze stanu
(i,r)
(i,r)
do stanu
do stanu
(j,s)
(j,s)
po czasie
po czasie
t
t
nie przechodząc przez stan 0.
nie przechodząc przez stan 0.
Relacja wymienialności jest relacją równoważności
Relacja wymienialności jest relacją równoważności
(zwrotna, symetryczna i przechodnia). Zatem zbiór
(zwrotna, symetryczna i przechodnia). Zatem zbiór
typów zgłoszeń można podzielić na klasy
typów zgłoszeń można podzielić na klasy
równoważności:
równoważności:
a,
a,
K
K
jest zbiorem numerów klas równoważności.
jest zbiorem numerów klas równoważności.
Jeśli
Jeśli
R
R
k
k
jest klasą równoważności typów
jest klasą równoważności typów
(wymienialnych) to w zbiorze stanów
(wymienialnych) to w zbiorze stanów
X
X
0
0
łańcucha
łańcucha
X
X
k
k
można wyróżnić następujący podzbiór:
można wyróżnić następujący podzbiór:
Zbiór powyższy nazywa się łańcuchem stanów
Zbiór powyższy nazywa się łańcuchem stanów
osiągalnych przez zgłoszenia typów należących do
osiągalnych przez zgłoszenia typów należących do
zbioru
zbioru
R
R
k
k
.
.
)
(
0
,
t
p
js
ir
)
(
,
oraz
l
k
k
k
l
k
R
R
K
R
R
K
l
k
r
r
i
l
k
k
k
,
}
:
)
,
{(
R
R
R
X
X
R
X
17
Model ruchu zgłoszeń w sieci - 4
Uwzględniając rozłączność łańcuchów stanów
Uwzględniając rozłączność łańcuchów stanów
osiągalnych dla różnych klas równoważności
osiągalnych dla różnych klas równoważności
typów zgłoszeń, można rozpatrywać sieć
typów zgłoszeń, można rozpatrywać sieć
kolejkową rozbitą na podsieci, w których ruch
kolejkową rozbitą na podsieci, w których ruch
zgłoszeń opisany będzie procesami
zgłoszeń opisany będzie procesami
X
X
k
k
o
o
zbiorach stanów
zbiorach stanów
.
.
Zgłoszenia z tych podsieci poruszają się
Zgłoszenia z tych podsieci poruszają się
niezależnie od siebie, ale wspólnie obciążają
niezależnie od siebie, ale wspólnie obciążają
niektóre węzły sieci kolejkowej.
niektóre węzły sieci kolejkowej.
Jeśli
Jeśli
, to łańcuch jest
, to łańcuch jest
zamknięty. Przyjmuje się, że krąży w nim stała
zamknięty. Przyjmuje się, że krąży w nim stała
liczba zgłoszeń.
liczba zgłoszeń.
Jeśli
Jeśli
, to
, to
łańcuch jest otwarty.
łańcuch jest otwarty.
k
R
X
k
ir
ir
q
q
R
X
r)
(i,
dla
0
0
0
,
,
0
)
0
0
(
)
,
(
),
,
(
0
,
,
0
js
ir
q
q
r
i
s
j
k
R
X
18
Model ruchu zgłoszeń sieci - 5
Zgłoszenia do sieci napływają zgodnie ze
Zgłoszenia do sieci napływają zgodnie ze
strumieniem Poissona, którego intensywność
strumieniem Poissona, którego intensywność
może być zależna od stanu sieci:
może być zależna od stanu sieci:
Intensywność
Intensywność
, gdzie liczba zgłoszeń w
, gdzie liczba zgłoszeń w
całej sieci,
całej sieci,
Intensywność
Intensywność
, gdzie
, gdzie
jest liczbą zgłoszeń w
jest liczbą zgłoszeń w
k-tym łańcuchu
k-tym łańcuchu
.
.
Jeśli strumień wejściowy jest niezależny od stanu
Jeśli strumień wejściowy jest niezależny od stanu
systemu to
systemu to
jeśli jest jeden sumaryczny strumień wejściowy,
jeśli jest jeden sumaryczny strumień wejściowy,
jeśli zgłoszenia napływają osobno do
jeśli zgłoszenia napływają osobno do
każdego łańcucha.
każdego łańcucha.
k
R
X
)
(n
n
)
(
k
n
k
n
)
(n
K
k
n
k
k
,
)
(
19
Model ruchu zgłoszeń w sieci - 6
Układ równań równowagi (równania ruchu)
Układ równań równowagi (równania ruchu)
(8.7)
(8.7)
Układy dla poszczególnych łańcuchów stanów
Układy dla poszczególnych łańcuchów stanów
osiągalnych można rozwiązać niezależnie.
osiągalnych można rozwiązać niezależnie.
Interpretacje wielkości występujących w układzie
Interpretacje wielkości występujących w układzie
(8.7)
(8.7)
- względna częstość wizyt zgłoszenia r-tego typu w
- względna częstość wizyt zgłoszenia r-tego typu w
węźle i-tym (oczekiwana liczba wizyt w i-tym węźle
węźle i-tym (oczekiwana liczba wizyt w i-tym węźle
zgłoszenia r-tego typu miedzy dwiema kolejnymi
zgłoszenia r-tego typu miedzy dwiema kolejnymi
bytnościami w węźle 0) – dla sieci otwartych,
bytnościami w węźle 0) – dla sieci otwartych,
- intensywność strumienia zgłoszeń r-tego
- intensywność strumienia zgłoszeń r-tego
typu trafiających z otoczenia do węzła i-tego,
typu trafiających z otoczenia do węzła i-tego,
- intensywność strumienia zgłoszeń r-tego
- intensywność strumienia zgłoszeń r-tego
typu trafiających z otoczenia do węzła i-tego,
typu trafiających z otoczenia do węzła i-tego,
k
k
R
R
js
js
r
i
js
ir
ir
s
j
e
q
q
e
X
X
)
,
(
,
0
)
,
(
,
ir
e
ir
k
q
,
0
ir
k
e
20
Model ruchu zgłoszeń w sieci - 7
Układ (8.7) (URR) posiada jednoznaczne
Układ (8.7) (URR) posiada jednoznaczne
rozwiązanie jeśli
rozwiązanie jeśli
jest łańcuchem otwartym.
jest łańcuchem otwartym.
Dla łańcucha zamkniętego istnieje rozwiązanie
Dla łańcucha zamkniętego istnieje rozwiązanie
jednoznaczne z dokładnością do mnożenia przez
jednoznaczne z dokładnością do mnożenia przez
stałą.
stałą.
URR dla łańcucha zamkniętego
URR dla łańcucha zamkniętego
ma
ma
następująca postać:
następująca postać:
Rozpatrzmy dowolne rozwiązanie
Rozpatrzmy dowolne rozwiązanie
i
i
dokonajmy przekształcenia:
dokonajmy przekształcenia:
dla ustalonego
dla ustalonego
k
R
X
l
R
X
l
l
R
R
js
r
i
js
ir
ir
s
j
e
q
e
X
X
)
,
(
)
,
(
,
l
s
j
js
ir
js
e
e
e
e
R
X
)
,
(
*
*
1
l
s
j
js
e
e
R
X
)
,
(
l
r
i
R
X
)
,
(
21
Model ruchu zgłoszeń w sieci - 8
Wektor
Wektor
e
e
*
*
posiada następujące własności:
posiada następujące własności:
e
e
*
*
jest również rozwiązaniem URR,
jest również rozwiązaniem URR,
,
,
oznacza oczekiwaną liczbę wizyt
oznacza oczekiwaną liczbę wizyt
zgłoszenia s-tego typu w j-tym węźle między kolejnymi
zgłoszenia s-tego typu w j-tym węźle między kolejnymi
wizytami tego zgłoszenia w i-tym węźle jako
wizytami tego zgłoszenia w i-tym węźle jako
zgłoszenia r-tego typu.
zgłoszenia r-tego typu.
1
*
ir
e
)
,
(
)
,
(
dla
r
i
s
j
e
js
22
Sieci BCMP
Biorąc pod uwagę omówione wcześniej typy
Biorąc pod uwagę omówione wcześniej typy
węzłów oraz typy zgłoszeń, sieć BCMP [Baskett,
węzłów oraz typy zgłoszeń, sieć BCMP [Baskett,
Chandy, Munz, Palacios 1976] możemy określić
Chandy, Munz, Palacios 1976] możemy określić
następująco:
następująco:
Uwzględniając występowanie w sieci wielu
Uwzględniając występowanie w sieci wielu
typów zgłoszeń przyjmijmy następujące
typów zgłoszeń przyjmijmy następujące
oznaczenia dla ustalonego i-tego węzła:
oznaczenia dla ustalonego i-tego węzła:
- liczba faz w rozkładzie Coxa zgłoszeń r-tego
- liczba faz w rozkładzie Coxa zgłoszeń r-tego
typu
typu
- prawdopodobieństwo osiągnięcia s-tej fazy
- prawdopodobieństwo osiągnięcia s-tej fazy
obsługi przez zgłoszenia r-tego typu,
obsługi przez zgłoszenia r-tego typu,
}
4
,
3
,
2
,
1
{
kolejki
regulamin
:
gdzie
,
,
,
,
,
,
,
,
0
0
i
i
i
i
i
i
BCMP
typ
f
i
typ
f
n
C
M
Q
S
W
R
W
ir
J
irs
A
23
Sieci BCMP - 2
- intensywność obsługi w s-tej fazie zgłoszeń
- intensywność obsługi w s-tej fazie zgłoszeń
r-tego typu,
r-tego typu,
- oczekiwany czas obsługi zgłoszeń r-tego
- oczekiwany czas obsługi zgłoszeń r-tego
typu,
typu,
- liczba zgłoszeń r-tego typu w s-tej fazie
- liczba zgłoszeń r-tego typu w s-tej fazie
obsługi w stanie
obsługi w stanie
n
n
,
,
-
-
liczba zgłoszeń r-tego typu w stanie n,
liczba zgłoszeń r-tego typu w stanie n,
- liczba zgłoszeń w i-tym węźle w stanie n,
- liczba zgłoszeń w i-tym węźle w stanie n,
irs
ir
1
irs
n
ir
n
i
n
ir
k
ir
ir
ir
ir
e
1
k
-
-
intensywność
intensywność
napływu zgłoszeń do k-
napływu zgłoszeń do k-
tego łańcucha
tego łańcucha
R
r
ir
i
1
- współczynnik obciążenia węzła.
- współczynnik obciążenia węzła.
24
Sieci BCMP - 3
Jako model funkcjonowania sieci BCMP
Jako model funkcjonowania sieci BCMP
przyjmujemy proces stochastyczny
przyjmujemy proces stochastyczny
X(t)
X(t)
o
o
następującej przestrzeni stanów:
następującej przestrzeni stanów:
wezle
tym
-
i
w
kolejce
w
zgloszenia
tego
-
j
typ
4
jesli
))
,
(
),..,
,
(
),..,
,
((
)
,..,
,..,
(
3
,
2
jesli
)
,..,
,..,
(
wezle
tym
-
i
w
w
zgloszenia
kolejce
w
tego
-
j
typ
1
jesli
)
,..,
,..,
(
:
)
,..,
,..,
(
{
1
1
1
1
1
1
ij
i
n
i
n
i
ij
ij
i
i
i
irJ
irs
ir
ir
i
iR
ir
i
i
ij
i
n
i
ij
i
i
W
i
r
typ
s
r
s
r
s
r
n
n
n
n
n
typ
n
n
n
n
r
typ
r
r
r
n
n
n
n
n
i
i
r
i
X
25
Sieci BCMP - 4
Twierdzenie 8.1. BCMP
Twierdzenie 8.1. BCMP
Jeśli we wszystkich węzłach sieci BCMP spełnione
Jeśli we wszystkich węzłach sieci BCMP spełnione
sa warunki ergodyczności (tzn.:
sa warunki ergodyczności (tzn.:
dla węzłów
dla węzłów
typu: 1,2,4) to rozkład graniczny procesu
typu: 1,2,4) to rozkład graniczny procesu
X(t)
X(t)
istnieje i jest określony następującymi
istnieje i jest określony następującymi
zależnościami:
zależnościami:
gdzie:
gdzie:
G
G
stała normalizacyjna,
stała normalizacyjna,
(8.8)
(8.8)
1
i
)
(
)..
(
..
)
(
)
(
}
)
(
{
lim
)
(
1
1
1
W
W
i
i
t
n
p
n
p
n
p
n
d
G
n
t
X
P
n
p
i
ij
n
j
i
ir
i
i
e
n
p
1
)
(
dla węzłów typu 1 (FIFO)
dla węzłów typu 1 (FIFO)
R
r
J
s
n
irs
irs
ir
irs
i
i
i
ir
irs
A
e
n
n
n
p
1
1
!
1
!
)
(
dla węzłów typu 2 (PS)
dla węzłów typu 2 (PS)
26
Sieci BCMP - 5
i
ij
ij
ij
ij
ij
n
j
s
ir
s
ir
ir
i
i
A
e
n
p
1
)
(
dla węzłów typu 4 (LIFO-PR)
dla węzłów typu 4 (LIFO-PR)
R
r
J
s
n
irs
irs
ir
irs
i
i
ir
irs
A
e
n
n
p
1
1
!
1
)
(
dla węzłów typu 3 (IS)
dla węzłów typu 3 (IS)
Stałą normalizacyjną
Stałą normalizacyjną
G
G
wyznaczamy z warunku:
wyznaczamy z warunku:
1
)
(
X
n
n
p
Stałą
Stałą
d(n)
d(n)
definiuje się następująco:
definiuje się następująco:
gdzie
gdzie
- liczba zgłoszeń w k-tym łańcuchu
- liczba zgłoszeń w k-tym łańcuchu
stanów osiągalnych
stanów osiągalnych
, jeśli intensywność
, jeśli intensywność
napływu zgłoszeń zależy od liczby zgłoszeń w
napływu zgłoszeń zależy od liczby zgłoszeń w
sieci,
sieci,
K
k
n
l
k
k
l
n
d
1
1
0
)
(
)
(
k
n
k
R
X
(8.9
(8.9
)
)
27
Sieci BCMP - 6
─
jeśli intensywność napływu zgłoszeń nie zależy
jeśli intensywność napływu zgłoszeń nie zależy
od stanu sieci:
od stanu sieci:
w szczególności, jeśli K=1 to
w szczególności, jeśli K=1 to
K
k
n
k
k
n
d
1
)
(
n
n
d
)
(
(8.9A)
(8.9A)
(8.9B)
(8.9B)
28
Zagregowane modele sieci BCMP
Jeśli interesuje nas jedynie liczba zgłoszeń
Jeśli interesuje nas jedynie liczba zgłoszeń
poszczególnych typów w poszczególnych
poszczególnych typów w poszczególnych
węzłach sieci, to modelem sieci BCMP będzie
węzłach sieci, to modelem sieci BCMP będzie
proces:
proces:
- liczba zgłoszeń r-tego typu w i-tym węźle
- liczba zgłoszeń r-tego typu w i-tym węźle
w chwili t,
w chwili t,
Zbiór stanów procesu
Zbiór stanów procesu
Y(t)
Y(t)
:
:
)
(
),..,
(
),..,
(
(
)
(
))
(
),..,
(
(
)
(
1
1
t
Y
t
Y
t
Y
t
Y
t
Y
t
Y
t
Y
iR
ir
i
i
W
)
(t
Y
ir
..}}
,
1
,
0
{
),
,..,
(
:
)
,..,
(
{
1
1
ir
iR
i
i
W
y
y
y
y
y
y
y
Y
29
Zagregowane modele sieci BCMP - 2
Wykorzystując rozkład graniczny procesu
Wykorzystując rozkład graniczny procesu
X(t)
X(t)
oraz definicję procesu
oraz definicję procesu
Y(t)
Y(t)
, można pokazać, że:
, można pokazać, że:
gdzie:
gdzie:
)
(
)..
(
)
(
)}
(
{
lim
)
(
1
1
1
W
W
t
y
g
y
g
y
d
G
t
Y
P
y
p
i
ir
y
i
y
ir
R
r
ir
i
i
i
e
y
y
y
g
1
!
1
!
)
(
1
dla węzłów typu 1
dla węzłów typu 1
ir
y
ir
ir
R
r
ir
i
i
i
e
y
y
y
g
1
!
1
!
)
(
dla węzłów typu 2 i 4
dla węzłów typu 2 i 4
ir
y
ir
ir
R
r
ir
i
i
e
y
y
g
1
!
1
)
(
dla węzłów typu 3
dla węzłów typu 3
(8.10
(8.10
)
)
30
Zagregowane modele sieci BCMP - 3
Najbardziej zagregowany opis sieci uzyskamy
Najbardziej zagregowany opis sieci uzyskamy
rozpatrując proces:
rozpatrując proces:
gdzie:
gdzie:
liczba wszystkich zgłoszeń w i-
liczba wszystkich zgłoszeń w i-
tym wężle w chwili
tym wężle w chwili
t
t
.
.
Zbiór stanów procesu
Zbiór stanów procesu
Z(t)
Z(t)
:
:
Można wykazać, ze rozkład graniczny procesu
Można wykazać, ze rozkład graniczny procesu
Z(t)
Z(t)
ma postać:
ma postać:
dla węzłów typu 1, 2,
dla węzłów typu 1, 2,
4
4
dla węzłów typu
dla węzłów typu
3.
3.
))
(
..,
),
(
(
)
(
1
t
Z
t
Z
t
Z
W
)
(t
Z
i
,..}}
2
,
1
,
0
{
:
)
..,
,
(
{
1
i
W
z
z
z
z
Z
W
i
i
i
t
z
p
z
t
Z
P
z
p
1
)
(
}
)
(
{
lim
)
(
gdzie:
gdzie:
i
z
i
i
i
i
z
p
)
1
(
)
(
i
i
e
z
z
p
i
z
i
i
i
!
)
(
(8.11
(8.11
)
)