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

*

*

)

(

)

(

)

(