Systemy kolejkowe
- twierdzenie Little’a

Plan prezentacji



Twierdzenie Little’a



Twierdzenie Little’a - dowód



Twierdzenie Little’a - przykłady



Twierdzenie Little’a – zastosowanie



Twierdzenie Little’a - podsumowanie

Modele kolejkowe - twierdzenie
Little’a

Modele kolejkowe

zgłoszenia

kolejka/bufor

serwer

- model dla:

- zgłoszeń (klientów) oczekujących w kolejce,

- linii montażowej,

- pakietów w sieci (kanał transmisyjny)

- chcemy znać:

- średnią liczbę zgłoszeń w kolejce,

- średnie opóźnienie doświadczane przez zgłoszenia (wnoszone przez system obsługi)

- z wykorzystaniem wartości:

- średniej szybkości (intensywności) napływu zgłoszeń (średniej liczby zgłoszeń
w jednostce czasu),

- szybkości obsługi (średniej liczby zgłoszeń, którą serwer może obsłużyć w jednostce
czasu).

System kolejkowy

System kolejkowy:
- zgłoszenia napływają do obsługi w losowych chwilach czasu,

- rozkład prawdopodobieństwa odstępów czasu pomiędzy zgłoszeniami jest znany,

- rozkład prawdopodobieństwa czasu obsługi poszczególnych zgłoszeń jest znany,

Możliwa interpretacja:

- zgłoszenia to pakiety przekazywane do transmisji w kanale komunikacyjnym,

- czas obsługi jest czasem transmisji pakietu i jest równy L/C, gdzie:

- L jest długością pakietu (bity/sekundę),

- C jest pojemnością kanału transmisyjnego (bity/sekundę)

Inna interpretacja:

- zgłoszenia to aktywne w sieci konwersacje (połączenia wirtualne)
pomiędzy węzłami sieci,

- czas obsługi to czas trwania tych konwersacji

Charakterystyki systemu
kolejkowego

Charakterystyki systemu kolejkowego:

-

średnia liczba zgłoszeń w systemie („typowa” liczba zgłoszeń

oczekujących na obsługę i obsługiwanych),

-

średnie opóźnienie zgłoszeń („typowy” czas spędzany przez

zgłoszenie w systemie, tzn. suma czasu oczekiwania przez

z

głoszenie na obsługę i czasu obsługi zgłoszenia),

Jeżeli:

-

)

(t

p

n

oznacza prawdopodobieństwo zdarzenia, że

n zgłoszeń

oczekuje w kolejce lub jest obsługiwanych w chwili

t ,

-

)

(t

N oznacza średnią liczbę zgłoszeń w systemie w chwili

t ,

-

k

T

oznacza średnie opóźnienie każdego spośród

k zgłoszeń,

-

n

p , N i T, o

dpowiednio, to wartości

)

(t

p

n

,

)

(t

N i

k

T w stanie

ustalonym

to:

-

)

(

lim

)

(

lim

0

0

t

N

t

np

np

N

n

t

n

t

n

n



























,

-

















k

i

i

k

k

k

T

k

T

T

1

1

lim

lim

Twierdzenie Little’a

Twierdzenie:

Średnia liczba zgłoszeń w systemie kolejkowym

N oraz średnie

opóźnienie zgłoszeń T

wnoszone przez system kolejkowy są związane

zależnością:

T

N 



gdzie  jes

t średnią szybkością napływu zgłoszeń do systemu

kolejkowego.

Znaczenie twierdzenia wynika z jego ogólności:

-

jest prawdziwe dla większości systemów kolejkowych, które

osiągają w granicy stan równowagi statystycznej,

-

jest prawdziwe dla złożonych systemów

napływu zgłoszeń i ich

obsługi,

-

system kolejkowy nie musi być pojedynczą kolejką.

Twierdzenie Little’a -dowód

J e ż e l i :
-

)

( t



- l i c z b a n a d c h o d z ą c y c h z g ł o s z e ń w p r z e d z i a l e c z a s u [ 0 , t ] ,

-

)

( t



- l i c z b a o b s ł u ż o n y c h z g ł o s z e ń w p r z e d z i a l e c z a s u [ 0 , t ] ,

t o l i c z b a z g ł o s z e ń w s y s t e m i e w c h w i l i t ( z a k ł a d a j ą c , ż e w c h w i l i t =

0 s y s t e m j e s t p u s t y ) w y n o s i :

)

(

)

(

)

(

t

t

t

N









.

J e ż e l i t

i

i T

i

s ą , o d p o w i e d n i o , c h w i l ą n a p ł y w u i c z a s e m s p ę d z o n y m

w s y s t e m i e p r z e z i - t e z g ł o s z e n i e , t o :



















t

t

t

i

i

t

i

i

t

t

T

d

N

0

)

(

1

)

(

)

(

1

)

(

)

(











,

t

t

t

i

i

t

i

i

t

t

T

t

t

t

T

t

t

t

d

N

N



































)

(

)

(

)

(

)

(

)

(

1

)

(

1

0

g d z i e N

t

, 

t

i T

t

t o ś r e d n i e w a r t o ś c i l i c z b y z g ł o s z e ń , i n t e n s y w n o ś c i

n a p ł y w u i c z a s u s p ę d z a n e g o p r z e z j e d n o z g ł o s z e n i e w s y s t e m i e .

Twierdzenie Little’a - dowód

)

(t

N



7

6

5

4

3

2

1

0

t

1

t

2

t

3

t

4

t

)

(t



)

(t



1

T

2

T

3

T

Twierdzenie Little’a – przykład I

J e ż e li:

-



- s z y b k o ś ć n a p ły w u p a k ie tó w d o tra n s m is ji,

- N

Q

- ś re d n ia lic z b a p a k ie tó w o c z e k u ją c y c h w k o le jc e n a tra n s m is ję a le

n ie w tra k c ie tra n s m is ji) ,

- W - ś re d n i c z a s o c z e k iw a n ia p a k ie tu w k o le jc e n a tra n s m is ję ,

to :

W

N

Q





C o w ię c e j, je ż e li:

-

X

- ś re d n i c z a s trw a n ia tra n s m is ji p a k ie tu ,

to :

X



 

P o n ie w a ż w d a n e j c h w ili c o n a jw ię c e j (n a jw y ż e j? ) je d e n p a k ie t je s t
tra n s m ito w a n y , p a ra m e tr  m a s e n s w s p ó łc z y n n ik a w y k o rz y s ta n ia

k a n a łu tra n s m is y jn e g o , tz n . je g o w a rto ś ć je s t m ia rą z a ję to ś c i k a n a łu .

Twierdzenie Little’a – przykład II

J e ż e li w s ie c i:

- n je s t lic z b ą w ę z łó w , w k tó r y c h p a k ie ty ( w ia d o m o ś c i) w p ły w a ją d o

s ie c i,

-

i

 je s t s z y b k o ś c ią n a p ły w u p a k ie tó w w i - ty m w ę ź le (

n

i

,...,

2,

1



) ,

-

i

N je s t ś r e d n ią lic z b ą p a k ie tó w w s ie c i, k tó r e w p ły n ę ły w i - ty m

w ę ź le ,

-

i

T je s t ś r e d n im o p ó ź n ie n ie m p a k ie tó w , k tó r e w p ły n ę ły w i - ty m

w ę ź le ,

- N je s t ś r e d n ią c a łk o w itą lic z b ą p a k ie tó w w s ie c i,

to ( n ie z a le ż n ie o d r o z k ła d u d łu g o ś c i p a k ie tó w i m e to d y w y z n a c z a n ia

tr a s d la p a k ie tó w ) ś r e d n ie o p ó ź n ie n ie p a k ie tu je s t r ó w n e :







n

i

i

N

T

1



o r a z

i

i

i

T

N





Twierdzenie Little’a
– przykład zastosowania
(przepustowość)

W s y s t e m i e k o m p u t e r o w y m z p o d z i a ł e m c z a s u :

- N - l i c z b a t e r m i n a l i ,

- R - ś r e d n i c z a s o c z e k i w a n i a n a r e a k c j ę s y s t e m u ( p o z a l o g o w a n i u s i ę

u ż y t k o w n i k a ) ,

- P - ś r e d n i c z a s o b s ł u g i j e d n e g o z a d a n i a , k t ó r e o c z e k u j ą w k o l e j c e ,

- D - ś r e d n i e o p ó ź n i e n i e ( c z a s o c z e k i w a n i a z a z a k o ń c z e n i e z a d a n i a ) ,

O p ó ź n i e n i e d m o ż e s i ę z m i e n i a ć w g r a n i c a c h o d P ( b e z o c z e k i w a n i a n a
o b s ł u g ę ) d o N x P ( o c z e k i w a n i e n a z a k o ń c z e n i e o b s ł u g i z a d a ń

w s z y s t k i c h p o z o s t a ł y c h u ż y t k o w n i k ó w ) . S t ą d :

P

1





NP

R

T

P

R









































P

R

N

P

NP

R

N

P

R

N

T

N

NP

R

N

,

1

min

)

(





o r a z





NP

R

T

P

R

NP









,

max

Twierdzenie Little’a
– przykład zastosowania
(przepustowość)

d

o

s

t

ę

p

n

a

p

r

z

e

p

u

s

t

o

w

o

ś

ć

ś

r

e

d

n

i

c

z

a

s

u

ż

y

t

k

o

w

n

i

k

a

w

s

y

s

t

e

m

i

e

l i c z b a t e r m i n a l i N

l i c z b a t e r m i n a l i N

P

1

o g r a n i c z e n i e
w p r o w a d z a n e p r z e z
l i c z b ę t e r m i n a l i

o g r a n i c z e n i e
w p r o w a d z a n e p r z e z
l i c z b ę t e r m i n a l i

g w a r a n t o w a n a
p r z e p u s t o w o ś ć

P

R



1

1 2 3 4

R + P

R

P

2 P

3 P

4 P





NP

R

T

P

R

NP









,

max

R + 2 P

R + 3 P

Twierdzenie Little’a
- podsumowanie



wiąże liczbę zgłoszeń w systemie,
intensywność napływu zgłoszeń i średni czas
oczekiwania zgłoszeń na zakończenie
obsługi,



jest prawdziwe dla większości systemów
kolejkowych, które w granicy osiągają stan
ustalony,



obowiązuje zarówno w pojedynczych
kolejkach, jak i w złożonych systemach
kolejkowych,