Systemy kolejkowe
- twierdzenie Little’a
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,