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

Ad. 2 b

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