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

