Efektywność systemów
informatycznych
Wykład 7
TEMAT:Markowskie sieci kolejkowe
Efektywność systemów
informatycznych
Wykład 7
TEMAT:Markowskie sieci kolejkowe
2
Sieci kolejkowe
Siecią kolejkową
Siecią kolejkową
(siecią masowej obsługi)
(siecią masowej obsługi)
nazywamy zbiór pojedynczych systemów
nazywamy zbiór pojedynczych systemów
kolejkowych (węzłów), połączonych ze sobą w ten
kolejkowych (węzłów), połączonych ze sobą w ten
sposób, że zgłoszenia obsłużone w jednym węźle
sposób, że zgłoszenia obsłużone w jednym węźle
mogą trafić do innych węzłów lub opuścić sieć.
mogą trafić do innych węzłów lub opuścić sieć.
Zgłoszenia krążące między węzłami sieci mogą
Zgłoszenia krążące między węzłami sieci mogą
napływać z zewnątrz i po obsłużeniu opuszczać sieć
napływać z zewnątrz i po obsłużeniu opuszczać sieć
lub mogą na stałe krążyć wewnątrz sieci.
lub mogą na stałe krążyć wewnątrz sieci.
Formalnie sieć kolejkową można zdefiniować
Formalnie sieć kolejkową można zdefiniować
następująco:
następująco:
gdzie:
gdzie:
- zbiór numerów węzłów sieci, przyjmuje się że
- zbiór numerów węzłów sieci, przyjmuje się że
,
,
W
W
– zbiór numerów węzłów wewnętrznych sieci,
– zbiór numerów węzłów wewnętrznych sieci,
odpowiadają im pojedyncze systemy kolejkowe, „0”
odpowiadają im pojedyncze systemy kolejkowe, „0”
– węzeł będący modelem otoczenia.
– węzeł będący modelem otoczenia.
W
W
i
i
i
i
i
f
N
n
B
A
Q
S
)
,
,
,
(
,
,
,
0
0
0
0
W
0
0
W
W
3
Sieci kolejkowe - 2
Węzeł „0” można traktować jako źródło i odpływ
Węzeł „0” można traktować jako źródło i odpływ
zgłoszeń.
zgłoszeń.
Każdy węzeł ze zbioru
Każdy węzeł ze zbioru
W
W
={1, .., W}
={1, .., W}
opisywany jest przy użyciu wektora:
opisywany jest przy użyciu wektora:
gdzie:
gdzie:
- typ rozkładu czasu obsługi pojedynczego
- typ rozkładu czasu obsługi pojedynczego
zgłoszenia w
zgłoszenia w
i-tym węźle sieci,
i-tym węźle sieci,
- liczba kanałów obsługi w i-tym węźle sieci,
- liczba kanałów obsługi w i-tym węźle sieci,
- długość kolejki w i-tym węźle sieci,
- długość kolejki w i-tym węźle sieci,
- regulamin kolejki w i-tym węźle sieci.
- regulamin kolejki w i-tym węźle sieci.
macierz opisująca ruch pojedynczego
macierz opisująca ruch pojedynczego
zgłoszenia w sieci,
zgłoszenia w sieci,
W
i
i
i
i
i
f
N
n
B
)
,
,
,
(
i
B
i
n
i
N
i
f
0
Q
W
W
0
0
0
0
Q
Q
T
4
Sieci kolejkowe - 3
Przyjmuje się, że ruch zgłoszeń w sieci spełnia
Przyjmuje się, że ruch zgłoszeń w sieci spełnia
następujące założenia:
następujące założenia:
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
gdzie
gdzie
q
q
ij
ij
oznacza prawdopodobieństwo tego, że
oznacza prawdopodobieństwo tego, że
zgłoszenie opuszczając węzeł i-ty przejdzie do węzła
zgłoszenie opuszczając węzeł i-ty przejdzie do węzła
j-tego ze zbioru
j-tego ze zbioru
W
W
.
.
Wektory
Wektory
opisują komunikację
opisują komunikację
z otoczeniem
z otoczeniem
sieci.
sieci.
W
j
i
ij
q
Q
,
T
W
i
i
W
T
W
i
i
W
T
q
q
,..,
1
0
1
,..,
1
0
1
..,
,
..,
,
5
Sieci kolejkowe - 4
- typ strumienia wejściowego, zgodnie z notacją
- typ strumienia wejściowego, zgodnie z notacją
Kendalla.
Kendalla.
Określenie sieci za pomocą wektora:
Określenie sieci za pomocą wektora:
nie daje możliwości jednoznacznego opisu wszystkich
nie daje możliwości jednoznacznego opisu wszystkich
typów sieci (np.: wiele typów zgłoszeń, różniących
typów sieci (np.: wiele typów zgłoszeń, różniących
się rozkładami czasów obsługi, macierzami
się rozkładami czasów obsługi, macierzami
Q
Q
0
0
opisującymi ruch w sieci ).
opisującymi ruch w sieci ).
Klasyfikacja sieci kolejkowych ze względu na
Klasyfikacja sieci kolejkowych ze względu na
komunikacje z otoczeniem.
komunikacje z otoczeniem.
Rozpatrzmy proces
Rozpatrzmy proces
X
X
k
k
, którego wartość oznacza numer
, którego wartość oznacza numer
węzła sieci, w którym znajduje się ustalone
węzła sieci, w którym znajduje się ustalone
zgłoszenie po k-tej zmianie węzła. Biorąc pod uwagę
zgłoszenie po k-tej zmianie węzła. Biorąc pod uwagę
przyjęte założenia odnośnie do ruchu zgłoszeń w
przyjęte założenia odnośnie do ruchu zgłoszeń w
sieci, można stwierdzić, że
sieci, można stwierdzić, że
X
X
k
k
jest jednorodnym
jest jednorodnym
procesem Markowa klasy DD.
procesem Markowa klasy DD.
0
A
W
W
i
i
i
i
i
f
N
n
B
A
Q
S
)
,
,
,
(
,
,
,
0
0
0
6
Sieci kolejkowe - 5
Zbiór stanów łańcucha
Zbiór stanów łańcucha
X
X
k
k
stanowi zbiór
stanowi zbiór
W
W
0
0
, a
, a
macierz prawdopodobieństw przejść w jednym
macierz prawdopodobieństw przejść w jednym
kroku określona jest zależnością:
kroku określona jest zależnością:
Podział stanów procesu
Podział stanów procesu
X
X
k:
k:
- zbiór stanów tranzytywnych ze stanem „0” oraz
- zbiór stanów tranzytywnych ze stanem „0” oraz
stan „0”,
stan „0”,
- stany nietranzytywne ze stanem „0”,
- stany nietranzytywne ze stanem „0”,
- stany tranzytywne ze stanem „0” bez stanu „0”
- stany tranzytywne ze stanem „0” bez stanu „0”
Klasyfikacja sieci:
Klasyfikacja sieci:
jeśli
jeśli
to sieć otwarta,
to sieć otwarta,
jeśli
jeśli
to sieć zamknięta,
to sieć zamknięta,
jeśli
jeśli
to sieć mieszana.
to sieć mieszana.
Przyjmuje się, że sieć mieszana może wystąpić, jeśli
Przyjmuje się, że sieć mieszana może wystąpić, jeśli
mamy wiele typów zgłoszeń.
mamy wiele typów zgłoszeń.
0
)
1
(
Q
0
0
W
0
0
0
1
\ W
W
W
}
0
{
\
0
0
0
W
W
W
W
W
0
1
,
W
W
W
1
0
,
0
1
, W
W
7
Markowskie sieci kolejkowe
Rozpatrzmy następująca klasę sieci:
Rozpatrzmy następująca klasę sieci:
Są to tzw. sieci Jacksona (1957). W dalszy ciągu
Są to tzw. sieci Jacksona (1957). W dalszy ciągu
rozpatrzymy sieci Jacksona spełniające
rozpatrzymy sieci Jacksona spełniające
dodatkowe założenia:
dodatkowe założenia:
Sieć jest otwarta.
Sieć jest otwarta.
W celu wyznaczenia rozkładu liczby zgłoszeń w
W celu wyznaczenia rozkładu liczby zgłoszeń w
węzłach sieci
węzłach sieci
rozpatrzmy proces:
rozpatrzmy proces:
gdzie:
gdzie:
- proces stochastyczny, którego wartość
- proces stochastyczny, którego wartość
oznacza liczbę zgłoszeń w i-tym węźle w chwili t.
oznacza liczbę zgłoszeń w i-tym węźle w chwili t.
W
W
i
i
i
i
i
i
f
N
n
M
M
Q
S
)
,
,
),
(
(
),
(
,
,
0
0
0
W
i
FIFO
f
N
i
i
,
,
W
i
i
t
t
)
(
)
(
)
(t
i
8
Markowskie sieci kolejkowe - 2
Zbadamy istnienie i wyznaczymy postać
Zbadamy istnienie i wyznaczymy postać
rozkładu granicznego procesu
rozkładu granicznego procesu
.
.
W tym celu, wykonamy dwa kroki:
W tym celu, wykonamy dwa kroki:
1.
1.
Wyznaczenie intensywności przepływu zgłoszeń
Wyznaczenie intensywności przepływu zgłoszeń
między węzłami sieci w warunkach ergodyczności,
między węzłami sieci w warunkach ergodyczności,
2.
2.
Wyznaczenie rozkładu granicznego procesu
Wyznaczenie rozkładu granicznego procesu
na podstawie wyznaczonych
na podstawie wyznaczonych
intensywności przepływu zgłoszeń.
intensywności przepływu zgłoszeń.
Ad.1. Przyjmijmy następujące oznaczenia:
Ad.1. Przyjmijmy następujące oznaczenia:
-intensywność napływu zgłoszeń do węzła j-
-intensywność napływu zgłoszeń do węzła j-
tego,
tego,
-intensywność strumienia zgłoszeń
-intensywność strumienia zgłoszeń
obsłużonych w i-tym węźle
obsłużonych w i-tym węźle
)
(t
)
(t
W
j
j
j
,
0
0
0
W
i
ij
j
0
W
j
ij
i
9
Markowskie sieci kolejkowe - 3
Wyznaczając intensywności przepływu
Wyznaczając intensywności przepływu
zgłoszeń przyjmujemy, że spełnione są dwa
zgłoszeń przyjmujemy, że spełnione są dwa
warunki:
warunki:
A.
A.
Macierz
Macierz
Q
Q
0
0
jest nierozkładalna. Oznacza to, że
jest nierozkładalna. Oznacza to, że
wszystkie stany procesu
wszystkie stany procesu
X
X
k
k
są parami
są parami
tranzytywne.
tranzytywne.
B.
B.
Parametry obciążenia poszczególnych węzłów
Parametry obciążenia poszczególnych węzłów
sieci spełniają warunek „ergodyczności”:
sieci spełniają warunek „ergodyczności”:
Z warunku (B), Tw.5.2 (Tw.Burke’a), własności
Z warunku (B), Tw.5.2 (Tw.Burke’a), własności
sumowania i rozrzedzania strumieni Poissona,
sumowania i rozrzedzania strumieni Poissona,
wynikają następujące zależności:
wynikają następujące zależności:
0
0
0
0
,
)
)
)
W
W
j
i
q
III
II
j
I
ij
i
ij
j
df
j
j
W
j
n
j
j
j
,
10
Markowskie sieci kolejkowe - 4
Sumując obie strony równania III) po
Sumując obie strony równania III) po
i
i
W
W
0
0
oraz
oraz
uwzględniając równanie II) otrzymujemy
uwzględniając równanie II) otrzymujemy
następujący układ równań równowagi (URR):
następujący układ równań równowagi (URR):
(7.1)
(7.1)
Z własności macierzy
Z własności macierzy
Q
Q
0
0
wynika, że (URR) posiada
wynika, że (URR) posiada
jednoznaczne rozwiązanie.
jednoznaczne rozwiązanie.
Ad.2. Wyznaczenie rozkładu granicznego procesu
Ad.2. Wyznaczenie rozkładu granicznego procesu
Z określenia procesu
Z określenia procesu
wynika, że jest to
wynika, że jest to
wielowymiarowy jednorodny proces Markowa
wielowymiarowy jednorodny proces Markowa
klasy DC o następującej przestrzeni stanów:
klasy DC o następującej przestrzeni stanów:
0
1
0
1
0
W
i
i
i
W
i
ij
i
j
j
q
j
q
W
)
(t
)
(t
}
,..
1
,
0
:
)
,..,
(
{
1
W
k
X
i
k
k
k
i
W
11
Markowskie sieci kolejkowe - 5
Uwzględniając nierozkładalność macierzy
Uwzględniając nierozkładalność macierzy
Q
Q
0
0
(dla
(dla
każdego zgłoszenia osiągalny jest każdy węzeł),
każdego zgłoszenia osiągalny jest każdy węzeł),
można pokazać, że proces
można pokazać, że proces
posiada stany
posiada stany
parami tranzytywne, a jego rozkład graniczny
parami tranzytywne, a jego rozkład graniczny
istnieje jeśli istnieje rozkład stacjonarny
istnieje jeśli istnieje rozkład stacjonarny
Niech
Niech
będzie macierzą intensywności przejść
będzie macierzą intensywności przejść
procesu
procesu
. Rozkład stacjonarny tego
. Rozkład stacjonarny tego
procesu, oznaczony jako:
procesu, oznaczony jako:
wyznaczamy z układu równań równowago globalnej
wyznaczamy z układu równań równowago globalnej
(URRG):
(URRG):
Istnienie i postać rozwiązania (URRG) rozstrzyga
Istnienie i postać rozwiązania (URRG) rozstrzyga
następujące
następujące
twierdzenie:
twierdzenie:
)
(t
X
n
k,
kn
)
(t
X
k
k
(
)
1
X
k
k
12
Twierdzenie 7.1
Twierdzenie 7.1
[Jackson, 1957]
[Jackson, 1957]
Jeśli dla sieci
Jeśli dla sieci
macierz
macierz
Q
Q
0
0
jest nierozkładalna oraz
jest nierozkładalna oraz
, gdzie
, gdzie
stanowią rozwiązanie (URR) sieci, to
stanowią rozwiązanie (URR) sieci, to
rozkład
rozkład
graniczny procesu
graniczny procesu
istnieje i ma
istnieje i ma
następującą
następującą
multiplikatywną postać:
multiplikatywną postać:
(7.2)
(7.2)
i
n
k
i
i
i
i
W
i
i
k
i
i
i
i
i
k
i
i
i
i
W
W
i
W
i
i
i
k
i
i
i
n
k
n
n
n
k
k
k
W
G
k
k
k
k
k
k
k
W
G
k
i
i
i
i
!
,..
0
!
)
(
,
)
0
(
)
(
1
1
)
(
,
0
,
)
(
)
0
(
)
(
:
gdzie
)
,..,
(
,
)
(
)
(
1
)
(
1
0
1
1
1
X
k
k
W
W
i
i
i
i
i
f
n
M
M
Q
S
)
,
,
),
(
(
),
(
,
,
0
0
0
W
i
n
i
i
i
i
,
W
i
i
,..,
1
,
)
(t
13
Markowskie sieci kolejkowe - 7
Z powyższego twierdzenia wynika, że
Z powyższego twierdzenia wynika, że
charakterystyki graniczne węzłów sieci są
charakterystyki graniczne węzłów sieci są
identyczne z charakterystykami systemów
identyczne z charakterystykami systemów
kolejkowych
kolejkowych
przy spełnieniu warunku
przy spełnieniu warunku
.
.
Jeśli istniej taki węzeł sieci, dla którego zachodzi
Jeśli istniej taki węzeł sieci, dla którego zachodzi
warunek
warunek
, to twierdzenie Jacksona dla tej sieci nie
, to twierdzenie Jacksona dla tej sieci nie
zachodzi. Powstaje pytanie jakie są
zachodzi. Powstaje pytanie jakie są
charakterystyki graniczne takiej sieci.
charakterystyki graniczne takiej sieci.
Rozpatrzmy sieć spełniającą warunki Tw.7.1 oraz
Rozpatrzmy sieć spełniającą warunki Tw.7.1 oraz
dodatkowo warunek
dodatkowo warunek
. Dla takiej sieci możemy
. Dla takiej sieci możemy
zapisać zmodyfikowany układ równań
zapisać zmodyfikowany układ równań
równowagi postaci:
równowagi postaci:
(URR II)
(URR II)
(7.3)
(7.3)
i
i
i
n
M
M
|
)
(
|
)
(
i
i
n
i
i
n
W
i
n
i
,
1
}
,
min{
gdzie
,
)
(
0
i
i
i
i
i
ij
i
i
j
j
j
q
W
W
14
Markowskie sieci kolejkowe - 9
Dla sieci
Dla sieci
zachodzi następujące twierdzenie:
zachodzi następujące twierdzenie:
Twierdzenie 7.2
Twierdzenie 7.2
[J.Goodman, W.Massey, 1984]
[J.Goodman, W.Massey, 1984]
Jeśli macierz
Jeśli macierz
Q
Q
0
0
powyższej sieci jest nierozkładalna
powyższej sieci jest nierozkładalna
to (URR II) posiada jedyne dodatnie rozwiązanie.
to (URR II) posiada jedyne dodatnie rozwiązanie.
Może być ono wyznaczone (za pomocą algorytmu
Może być ono wyznaczone (za pomocą algorytmu
rekurencyjnego) w co najwyżej
rekurencyjnego) w co najwyżej
W
W
krokach.
krokach.
Wykorzystując rozwiązanie (URR II)
Wykorzystując rozwiązanie (URR II)
możemy podzielić zbiór
możemy podzielić zbiór
W
W
na następujące
na następujące
podzbiory:
podzbiory:
węzły ergodyczne,
węzły ergodyczne,
węzły nieergodyczne.
węzły nieergodyczne.
W
W
i
i
i
i
f
M
M
Q
S
)
,
,
1
),
(
(
),
(
,
,
0
0
0
)
..,
,
,
(
*
*
2
*
1
*
W
}
{
*
*
i
i
i
:
W
W
*
W
\
W
:
W
W
}
{
*
i
i
i
15
Markowskie sieci kolejkowe - 10
Zachodzi następujące twierdzenie:
Zachodzi następujące twierdzenie:
Twierdzenie 7.3
Twierdzenie 7.3
[Goodman, Massey, 1984]
[Goodman, Massey, 1984]
Przy spełnieniu założeń Tw. 7.2, istnieją
Przy spełnieniu założeń Tw. 7.2, istnieją
charakterystyki graniczne sieci postaci:
charakterystyki graniczne sieci postaci:
(7.4)
(7.4)
0
,
)
1
(
}
,
)
(
{
lim
i
i
k
i
i
i
j
t
k
i
k
t
P
i
*
W
*
W
W
j
k
k
t
P
j
j
j
t
,
0
,
0
}
)
(
{
lim
16
Zamknięte sieci Jacksona
Jeśli
Jeśli
, to mamy do czynienia z siecią
, to mamy do czynienia z siecią
zamkniętą.
zamkniętą.
Przyjmuje się, że w sieci zamkniętej krąży
Przyjmuje się, że w sieci zamkniętej krąży
ustalona liczba zgłoszeń, oznaczona jako
ustalona liczba zgłoszeń, oznaczona jako
N
N
.
.
Wobec tego, sieć zamkniętą można opisać
Wobec tego, sieć zamkniętą można opisać
następująco:
następująco:
Przyjmujemy, że
Przyjmujemy, że
f
f
i
i
= FIFO.
= FIFO.
Dodatkowo przyjmujemy, że
Dodatkowo przyjmujemy, że
Układ równań równowagi dla sieci zamkniętej
Układ równań równowagi dla sieci zamkniętej
przyjmuje postać:
przyjmuje postać:
(7.5)
(7.5)
Układ ten posiada rozwiązanie
Układ ten posiada rozwiązanie
jednoznaczne z dokładnością do mnożenia przez
jednoznaczne z dokładnością do mnożenia przez
stałą.
stałą.
W
W
W
1
0
,
W
W
i
i
i
i
i
i
f
N
n
M
Q
S
)
,
,
),
(
(
,
,
W
i
N
N
i
,
W
W
j
q
h
h
i
ij
i
j
,
T
W
T
h
h
h
0
)
..,
,
(
1
17
Zamknięte sieci Jacksona - 2
Zbiór stanów procesu
Zbiór stanów procesu
dla zamkniętej sieci
dla zamkniętej sieci
Jacksona ma następująca postać:
Jacksona ma następująca postać:
Twierdzenie 7.4
Twierdzenie 7.4
Jeśli macierz
Jeśli macierz
Q
Q
zamkniętej sieci Jacksona jest
zamkniętej sieci Jacksona jest
nierozkładalna, to proces
nierozkładalna, to proces
, opisujący
, opisujący
funkcjonowanie sieci, posiada rozkład graniczny o
funkcjonowanie sieci, posiada rozkład graniczny o
następującej multiplikatywnej postaci:
następującej multiplikatywnej postaci:
(7.6)
(7.6)
gdzie:
gdzie:
jedno z nieujemnych
jedno z nieujemnych
rozwiązań (URR) (7.5)
rozwiązań (URR) (7.5)
)
(t
}
..},
,
2
,
1
,
0
{
:
)
..,
,
(
{
1
N
k
k
k
k
i
i
i
W
W
k
X
)
(t
X
k
k
,
)
(
)
,
(
1
1
W
i
i
i
k
i
k
d
N
W
G
i
)
..,
,
(
,
1
W
T
i
i
i
h
h
h
h
d
18
Zamknięte sieci Jacksona - 3
(7.7)
(7.7)
X
k
0
,
1
,
)
(
)
,
(
1
N
W
k
d
N
W
G
W
i
i
i
k
i
i