Model Erlanga z oczekiwaniem (M/M/N) (1) Teoria ruchu
ZałoŜenia:
telekomunikacyjnego
• w systemie tym istnieje N stanowisk obsługi
• czasy między kolejnymi wywołaniami są zmiennymi losowymi o rozkładzie wykładniczym
Systemy z oczekiwaniem
• czasy obsługi są zmiennymi losowymi o rozkładzie zgłoszeń
wykładniczym
• wywołania, które napotykają na blokadę są umieszczane w kolejce, gdzie oczekują na zwolnienie się stanowisk obsługi
2
Model Erlanga z oczekiwaniem (M/M/N) (2) Model Erlanga z oczekiwaniem (M/M/N) (3)
• Warunkiem równowagi statystycznej jest spełnienie λ
λ
λ
λ
λ
λ
λ
nierówności A < N, w przeciwnym przypadku kolejka rosłaby do nieskończoności, przy czym:
0
1
2
N-1
N
N+1
λ
µ
2µ
3µ (N-1)µ
Nµ
Nµ
Nµ
A = µ
Diagram równowagi dla systemu M/M/N
• W przypadku, gdy w systemie znajduje się x wywołań i x
• Dzięki wcześniejszym załoŜeniom moŜna zapisać
≤ N (x stanowisk obsługi jest zajętych) intensywność następujące równania:
zakończenia obsługi wynosi xµ
dla 1 ≤ x < N
λ P −1 = xµ P
• JeŜeli x > N, czyli x - N wywołań oczekuje w kolejce, x
x
intensywność jest stała i wynosi Nµ
λ −1 = µ
3
dla x
P
N P
≥ N
4
(ilustracja – nastę pny slajd) x
x
Model Erlanga z oczekiwaniem (M/M/N) (4) Model Erlanga z oczekiwaniem (M/M/N) (5) Po podstawieniu
λ
A = µ
Wykorzystując warunek normalizacyjny
∞
∑ Px = 1
Otrzymujemy:
P = AP
1
0
x=0
2
A
P =
P
2
0
!
2
moŜna zapisać:
L
AN
1
1
P =
P
0 =
=
N
0
P
N!
i
−1
i
N
N −1 Ai
AN ∞ A
N
A
A
N
A AN
∑ +
∑
∑ +
P + =
P
N 1
0
=
!
!
!
!
0
=0
=0
−
N N!
i
i
N i
N
i
i
N N
A
2
A AN
P + =
P
N 2
0
N N!
5
6
Natomiast...
L
Interfejsy dostępowe w ogólnym modelu
węzła komutacyjnego
1
Model Erlanga z oczekiwaniem (M/M/N) (6) Model Erlanga z oczekiwaniem (M/M/N) (7)
• Prawdopodobieństwo blokady, czyli prawdopodobieństwo wystąpienia opóźnienia wynosi
• Istnieje związek pomiędzy pierwszym i drugim wzorem Erlanga. Jest on opisany następującą zaleŜnością: N
A
N
∞
N! N
A
E
( A)
P
2, N
= ∑
−
x = N −1
i
N
NE
( )
A
x= N
∑ A + A
N
E
( )
,
1
A
N
=
!
!
2, N
0
i
N N
A
i =
−
N − A + AE
( )
A
,
1 N
• PowyŜszy wzór nosi nazwę drugiego wzoru Erlanga.
W literaturze amerykańskiej jest on nazywany „wzorem C-Erlanga”
7
8
Model Erlanga z oczekiwaniem (M/M/N) (8) Model Erlanga z oczekiwaniem (M/M/N) (9)
- kilka uŜytecznych wzorów
- kilka uŜytecznych wzorów
• Prawdopodobieństwo, Ŝe wszystkie stanowiska są zajęte i w kolejce oczekuje „j” wywołań:
• Z punktu widzenia projektowania systemów z j
j
N
A A
A
A
oczekiwaniem waŜna jest nie tylko znajomość P + =
P 0 = E ( A
) 1
2,
−
N
j
N
prawdopodobieństwa, Ŝe zgłoszenie trafi do kolejki, N! N
N
N
ale równieŜ
rozkład czasów oczekiwania na obsługę,
• Prawdopodobieństwo, Ŝe wszystkie stanowiska obsługi są a w tym
zajęte, a w kolejce znajduje się „j” lub więcej wywołań: prawdopodobieństwo, Ŝe czas oczekiwania na i
i
i
j
∞
∞
j
A
A
A
A
−1 A
A
∑
obsługę przekroczy określoną wartość t
E
( A
) 1
2,
−
= E
( A
) 1
2,
− ∑ − ∑ = E ( A
)
N
N
2, N
=
N
N
N =
(czyli P(γ>t)).
0 N
=0 N
N
i j
i
i
9
10
Model Erlanga z oczekiwaniem (M/M/N) (10) Model Erlanga z oczekiwaniem (M/M/N) (11)
- kilka uŜytecznych wzorów
- kilka uŜytecznych wzorów
• Korzystając ze wzoru na prawdopodobieństwo całkowite
• P
(γ>t) moŜna wyrazić korzystając ze wzoru Poissona i N+j
moŜna powiedzieć, Ŝe:
mamy wtedy:
∞
i
P (γ > t ) =
∑
P
γ
N + j P N +
(
j
> t )
t
j = 0
N
t
gdzie:
j
−
h
N h
P
stanowi prawdopodobieństwo, Ŝe wszystkie (γ > t ) = ∑
e
P
N+j
N + j
stanowiska obsługi są zajęte i w kolejce oczekuje j i = 0
i!
zgłoszeń,
gdzie:
P
(γ>t) jest prawd., Ŝe czas oczekiwania będzie większy h jest średnim czasem obsługi
N+j
niŜ t pod warunkiem, Ŝe zgłoszenie napłynęło, gdy w 11
systemie znajduje się N+j zgłoszeń
12
Stąd po podstawieniu do poprzedniego wzoru mamy: Interfejsy dostępowe w ogólnym modelu
węzła komutacyjnego
2
Model Erlanga z oczekiwaniem (M/M/N) (12) Model Erlanga z oczekiwaniem (M/M/N) (10)
- kilka uŜytecznych wzorów
- kilka uŜytecznych wzorów
• Średni czas oczekiwania w kolejce W odniesiony do
• Prawdopodobieństwo, Ŝe czas oczekiwania będzie większy wszystkich wywołań (zarówno oczekujących jak i nie niŜ t (przy załoŜeniu regulaminu kolejki typu FIFO): oczekujących) wynosi:
h
−
W = E
( A)
( N − A) t / h P(γ > t) = E
( A) e
2, N
N − A
2, N
• Średni czas oczekiwania odniesiony do wywołań gdzie:
opóźnionych wynosi:
h – średni czas obsługi
W
h
W =
=
o
13
14
E
( A)
N
2,
− A
N
Model Erlanga z oczekiwaniem (M/M/N) (11) Przykład 1
Do koncentratora przyłączono 512 abonentów telefonicznych, z których kaŜdy generuje ruch o średnim natęŜeniu 0,085 Erl. Koncentrator połączono z centralą
- kilka uŜytecznych wzorów
za pomocą dwóch traktów PCM 30/32.
1.
Oblicz prawdopodobieństwo oczekiwania abonenta na przydzielenie kanału.
2.
Oblicz średni czas oczekiwania odniesiony do wszystkich zgłoszeń oraz do zgłoszeń opóźnionych. Przyjmij, Ŝe strumień zgłoszeń jest strumieniem
• Średnia liczba wywołań oczekujących w kolejce Q: : Poissona. Przeprowadź obliczenia przyjmując, Ŝe średni czas trwania połączenia wynosi: a) 2 min; b) 3 min.
Rozwiązanie:
S=512, N=2*30=60, A = 512*0,085 = 43,52 Erl Q = λ ⋅ W
S>>N model Erlanga
Ad. 1
NE
( )
A
E
( )
,
1
A
N
=
2, N
N − A + AE ( )
A
16
,
1 N
15
E
(A) – odczytujemy z tablic:
Ad. 2 a
1,N
h = 2 min
Średni czas oczekiwania w kolejce W odniesiony do wszystkich wywołań: h
W = E
( A)
2, N
N − A
2
W = ,
0 01
= ,
0 00121 min = ,
0 073 s
60 − 43 5
, 2
Średni czas oczekiwania odniesiony do wywołań opóźnionych wynosi: W
h
W =
=
E
(A)= 0,003165
o
1,N
E
( A)
N
2,
− A
N
60 ⋅ 0
,
0 03165
1
,
0 899
E
( )
A
2
N
=
=
= 0
,
0 1
2,
=
=
=
60 − 43 5
, 2 + 43 5
, 2 ⋅ ,
0 003165
16 6
, 18
W
1
,
0 21min
,
7 2 s
8
17
o
18
60 − 43 5
, 2
Interfejsy dostępowe w ogólnym modelu
węzła komutacyjnego
3
h = 3 min
Średni czas oczekiwania w kolejce W odniesiony do wszystkich wywołań: h
W = E
( A)
2, N
N − A
3
W = ,
0 01
= ,
0 0018 min =
s
1
,
0
60 − 43 5
, 2
Średni czas oczekiwania odniesiony do wywołań opóźnionych wynosi: W
h
W =
=
o
E
( A)
N
2,
− A
N
3
W =
= 1
,
0 82 min = 10 9
, s
o
19
60 − 43 5
, 2
Interfejsy dostępowe w ogólnym modelu
węzła komutacyjnego
4