Cadenas de Markov y Teoría de Colas Carlos F. Belaustegui Goitia

Procesos y Cadenas de Markov • • • • • •

Variables binomial, geométrica y de Poisson. Procesos puntuales. Procesos de Markov. Cadenas de Markov. Clasificación de estados, clases de cadenas, estado estacionario. Teorema de Perron-Frobenius. Cadenas de Markov en tiempo continuo. Ecuaciones de balance global. Aplicaciones.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

2

Variables Binomial y Geométrica Variable Binomial: La probabilidad de que el evento A, cuya probabilidad es P(A) = p, ocurra k veces en n pruebas es n pn (k ) =   p k (1 − p) n−k , k 

 n n!   =  k  k!(n − k )!

3 4

8

P( X = 1) = p P( X = 2) = (1 − p) p L P( X = n) = (1 − p) n−1 p = q n−1 p

n=22, k=7 1

Separación entre eventos: sea X= número de pruebas hasta el primer éxito

13

15

21 1

1 3 4 8 13 15 21 1 2 4 5 11 19 20 3 5 6 7 12 17 20 ............... 4 6 8 9 16 21 22

 22    combinaciones 7

3 4

8

15

21

X=n

Propiedad “sin memoria” de la distribución geométrica P ( X = n / X > n0 ) =

P ( X = n, X > n0 ) P ( X = n) = = P ( X > n0 ) P ( X > n0 )

q n −1 p ∞

∑q

k −1

= p

k = n0 +1

= 5 48 48

13

n0

X=n

Aplicación: Proceso de Bernoulli como modelo de flujo ATM

09/11/2003

Distribución geométrica. X es el número de pruebas hasta el primer éxito en una secuencia de pruebas de Bernoulli.

q n −1 ∞

∑q

i = n0

= i

q n −1 = q n − n0 −1 p = P ( X = n − n0 ) n0 1 1− q − 1− q 1− q

53 bytes C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas 1 CC = 2.83 uSec @ 149.76 Mbps

3

Variables Binomial y de Poisson Variable Binomial: La probabilidad de que el evento A, cuya probabilidad es P(A) = p, ocurra k veces en n pruebas es n pn (k ) =   p k (1 − p) n−k , k 

 n n!   =  k  k!(n − k )!

3 4

8

1 3 4 8 13 15 21 1 2 4 5 11 19 20 3 5 6 7 12 17 20 ............... 4 6 8 9 16 21 22

09/11/2003

13

1− k / n pn (k + 1) p n−k a a = ⋅ = ⋅ n → →∞ 1− p k +1 1− a / n k +1 pn (k ) k +1 a pn ( k ) k +1 p(0) = lim pn (0) = lim (1 − p) n = lim (1 − a / n) n = e −a

pn (k + 1) = n →∞

n=22, k=7 1

Variable de Poisson: Si p0/ πij(n)>0.

•

Comunicantes: los estados i y j comunican si son accesibles entre sí. Se escribe i↔j. La comunicación es una relación de equivalencia: i↔j, j↔k ⇒ i↔k.

•

Absorbente: Si es imposible abandonarlo: πii=1.

•

Recurrente: El estado i es recurrente si la probabilidad de regresar alguna vez a él es 1.

•

Periódico: Un estado es periódico con período d si sólo se puede regresar a él después de d, 2d, ..., nd pasos.

•

Aperiódico o Ergódico: Periódico con período d=1. Se puede regresar a él en cualquier momento.

•

Transitorio: La probabilidad de regresar al estado alguna vez es menor que 1. 09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

Recurrente ∞

f i = ∑ π ii (n) = 1 n =1

Transitorio ∞

f i = ∑ π ii (n) < 1 n =1

16

Clases de Estados •

•

• •

Cerrada: Si desde un estado interior no se puede alcanzar ningún estado exterior a la clase. Un estado absorbente es una clase cerrada con un único estado. Irreducible: Clase cerrada tal que ningún subclase propia es cerrada. En otros términos, la única clase cerrada es la de todos los estados. Dos estados pertenecen a un mismo conjunto si se comunican. Dos clases distintas deben ser disjuntas, pues si existe algún elemento común, los estados de una clase se pueden comunicar con los de la otra, y así resultan ser de la misma clase.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

Clase reducible Clase cerrada

Estados absorbentes

Clase irreducible

17

Clases de Cadenas •

Irreducible. Definiciones equivalentes: –

La que consiste en una única clase de equivalencia.

–

El único conjunto cerrado es el de todos los estados.

En una cadena irreducible, todos los estados son recurrentes o son todos transitorios. En una cadena irreducible finita, no pueden ser todos los estados transitorios; luego, son todos recurrentes.

•

Reducible. Opciones: 1.

Tiene uno o más estados absorbentes.

2.

Tiene un subconjunto de estados S1 desde el cual no es posible alcanzar estados fuera de S1.

•

Absorbente: la que tiene al menos un estado absorbente, accesible desde cualquier otro estado.

•

Aperiódica: Todos sus estados son periódicos con período 1.

•

Regular: Es posible ir de un estado a cualquier otro en exactamente n pasos: ∃n>0/ Π(n)= Π n > 0. Regular ⇒ Todos los estados comunican ⇒ Irreducible

•

Ergódica: Irreducible, aperiódica, recurrente positiva.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

18

Cadenas Absorbentes Una cadena es absorbente si es posible renombrar sus estados para escribir la matriz de probabilidades de transición como Q R  Π=  0 I 

11

22

33

(

tt

1

1

t+1 t+1

t+2 t+2

1 t+r t+r

[

r estados absorbentes

(I − Q )−1 R 

]

 

I

Q R  p Q (n + 1) p I ( n + 1) = p Q ( n) p I (n)   0 I  p Q ( n + 1) = p Q ( n)Q, p I ( n + 1) = p Q ( n)R + p I (n)

[

t estados transitorios

)

0 Q n Q n −1 + Q n − 2 + L + I R  Π = →  n→∞  0 I   0 p ( n) = p Q ( n) p I ( n ) n

] [

]

p Q ( n) → 0, p I ( n) → p Q (0)(I − Q ) R + p I (0) −1

Q

R

0

I

t 09/11/2003

n →∞

t

n→∞

r

r C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

19

Cadenas Reducibles e Irreducibles Matriz Reducible

Matrices de Permutación P es una matriz de permutación si exactamente 1 elemento en cada fila y 1 elemento en cada columna es 1 y los restantes son nulos.

0 1 0  1   2  P = 1 0 0, P 2 = 1 0 0 1 3 3 permuta las filas de A PA permuta las columnas de A AP A' = P T AP det P = ±1

P1 , P2 ∈ MP ⇒ P1 P2 ∈ MP

B C  A' = P T AP =    0 D Test: A ∈ℜN×N es irreducible sii:

Identidad de N×N

Matriz de valores absolutos Matriz positiva

(I

+ A)

N −1

N

>0

Permutación de estados en una cadena de Markov

Permuta las filas y columnas de A

P T = P −1

A es una matriz reducible (irreducible) si (si no) existe alguna matriz de permutación P tal que:

Π ' = PT ΠP

Permutar filas y columnas de Π equivale a renombrar los estados de la cadena

Cadena Reducible Una cadena de Markov es reducible si es posible renombrar sus estados para llevar la matriz de probabilidades de transición Π a la forma Q R  Π ' = PT ΠP =    0 A En caso contrario, la cadena de Markov es irreducible.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

20

Cadenas de Markov y Grafos Grafo de una cadena El grafo G(Π Π) de Π es el gráfico orientado sobre n nodos {N1, N2,..., Nn} en el cual hay un arco orientado de Ni a Nj si y sólo si πij≠0

Clase irreducible

Cambio de nombre de los nodos Si P es una matriz de permutación,

G (PT ΠP ) = G (Π )

Grafo fuertemente conexo Para Paracada cadapar parde denodos nodos(N (Ni,i,NNj )j )existe existeuna unasecuencia secuenciade dearcos arcos a N . orientados que conduce de N i j orientados que conduce de N a N . i

ΠΠesesirreducible irreducible

j

Todos Todoslos losestados estadoscomunican. comunican.La Lacadena cadenaconsiste consisteenenuna unaúnica únicaclase clase dedeequivalencia. equivalencia.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

21

Descomposición Espectral de una Matriz A∈ℜ ℜn×n es diagonalizable cuando tiene un conjunto completo de autovectores linealmente independientes.

Avi = λi v i

Autovector derecho

AT u i = µi u i ⇔ uTi A = µi uTi

Autovector izquierdo

(

det(A − λI ) = det AT − λI

)

A y AT tienen iguales autovalores

Avi = λi v i ⇒ uTj Avi = λi uTj v i  T ⇒ u  j v i = 0 si λi ≠ λ j T T T T u j A = λ j u j ⇒ u j Avi = λ j u j v i  Autovectores derecho e T i

u vi ≠ 0 T j

u v i = δ ij

izquierdo son biortogonales

Normalización

V = [v1 L v n ], U = [u1 Lu n ] Conjunto completo de autovectores l.i. ⇔ A es diagonalizable

Λ = diag (λ1 , K, λn )

AV = VΛ ⇔ V −1AV = Λ  −1 T T ⇔U =V ⇔U V=I T T T T −1 U A = ΛU ⇔ U A(U ) = Λ  n

A = VΛV = VΛU = ∑ λi v i uTi −1

T

i =1

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

Descomposición espectral

22

Teorema de Perron-Frobenius Teorema de Perron-Frobenius Si A≥0 es irreducible, entonces El radio espectral es un autovalor de A ρ (A )∈ σ (A ) El radio espectral es positivo ρ (A ) > 0 El radio espectral es un autovalor simple A alg mult ρ ( A) = 1 El autovector asociado al radio espectral es positivo. ∃x > 0 : Ax = ρ (A )x ∀A :1 ≤ geo mult ρ (A ) ≤ alg mult ρ (A ) = 1 ⇒ geo mult ρ (A ) = 1 El autovector asociado al radio espectral es único.

No existen otros autovectores no negativos aparte de x: Vector de Perron y T A = ρ (A)y T

El vector izquierdo de Perron tiene la misma propiedad.

Matriz primitiva A≥0, irreducible es primitiva si tiene un único autovalor r = ρ(A) de módulo máximo (es decir, un único autovalor sobre el círculo espectral). A≥0, irreducible es imprimitiva de índice h si tiene h autovalores de módulo máximo. Test de Frobenius: A≥0 es primitiva sii Am>0 para algún m≥1. n −2 n+ 2 >0 Test de Wielandt: A≥0 ∈ℜnxn es primitiva sii A 2

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

23

Matrices primitivas e imprimitivas Si A≥0 es irreducible y primitiva, entonces tiene un único autovalor r = ρ(A) sobre el círculo espectral.

Si A≥0 es irreducible e imprimitiva de índice h, entonces tiene h autovalores sobre el círculo espectral.

r = ρ ( A) B = A / r ⇒ ρ (B) = 1, σ (B) = {λ1 = ρ (B) = 1, λ2 ,K , λn }

alg mult λi = 1 ∀i = 1, 2, K, h

λi < λ1 = 1 ∀i = 2,K , n

Teorema: Los h autovalores de A sobre el círculo espectral, son las raíces de orden h de ρ(A)

Bx i = λi x i

   2πik  S =  ρ ( A) exp  : k = 0,1, K , h − 1  h   

y Tj B = λ j y Tj n

n

B = ∑ λi x i y Ti = x1y1T + ∑ λi x i y Ti i =1

lim B = lim (A / r ) = x y k →∞

En este caso, A/r no es convergente, pero es sumable Cesàro:

i=2

k

k

k →∞

09/11/2003

T 1 1

S = {λ1 = ρ ( A), λ2 ,K , λh }

A/r es convergente

I + ( A / r ) + L + ( A / r ) k −1 lim = x1y1T k →∞ k

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

24

Cadenas irreducibles y aperiódicas Propiedades generales de la matriz de probabilidades de transición Π n ≥ 0 ∀n ≥ 1

ρ (Π ) = 1 Π1 = 1

(1, 1) es un par propio de Π

i >1

i >1

Matriz irreducible Por el teorema de Perron-Frobenius, 1 es el vector de Perron asociado al autovalor 1. No existe otro autovector derecho no negativo. Para el mismo autovalor, existe un único autovector izquierdo p no negativo tal que Normalización

Π = 1p T + ∑ λ i v i u Ti

Π n = 1p T + ∑ λ ni v i u Ti

Radio espectral unitario

pT Π = p

Matriz irreducible y primitiva

λi < 1 ∀i > 1

Por ser primitiva, 1 es el único autovalor sobre el círculo espectral

lim Π k = 1pT

Todas las filas son iguales. Todas las columnas tienen iguales elementos

k →∞

lim pT (k ) = lim pT (0)Π k = pT (0)1pT = pT k →∞

k →∞

La distribución de probabilidades estacionaria es el vector izquierdo de Perron. La cadena es aperiódica.

pT 1 = 1

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

25

Cadenas irreducibles y periódicas Forma canónica de Frobenius para matrices imprimitivas

Matriz irreducible e imprimitiva I + Π + L Π k −1 = 1pT k →∞ k pT (0) + pT (1) + L + pT (k − 1) = pT (0)1pT = pT lim k →∞ k lim

Si Π es imprimitiva de orden h>1, entonces existe una permutación tal que

Interpretación 1 si el estado inicial es j 1 si el estado en tiempo n es j Z0 =  , Zn =  0 si no 0 si no k −1

∑Z

n

: número de visitas al estado j antes del tiempo k .

n

/ k : fracción de veces que el estado j es visitado antes del tiempo k .

n =0 k −1

∑Z

 0  0  PT ΠP =  M   0 Π h1

Π12 0 M 0 0

0 L 0  Π 23 L 0  O O M   L 0 Π h −1,h  L 0 0 

La cadena es periódica de período h.

n =0

E ( Z n ) = 1 ⋅ P( Z n = 1) + 0 ⋅ P( Z n = 0) = P( Z n = 1) = p j (n)  k −1  k −1  k −1  E  ∑ Z n / k  = ∑ p j ( n) / k =  ∑ p T ( n ) / k  = p T  n=0  n =0  n =0 j

( )

j

La fracción de tiempo a largo plazo que la cadena pasa en j es pj : componente j del vector de Perron pT. La interpretación vale también cuando la matriz es primitiva y existe un estado estacionario.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

26

Cadenas reducibles (1) Cadena Reducible Una cadena de Markov es reducible si es posible renombrar sus estados para llevar la matriz de probabilidades de transición Π a la forma X Y  Π ' = PT ΠP =    0 Z

 X11 R S T   0 X Y     Π≡  ≡ 0 U V  ≡L≡  M 0 Z      0 0 W   0 Si X o Z es reducible Si R, U o W es reducible, etc.

X12 X 22 M 0

L L O L

Π11  0  X1k   M  X 2 k   0 ≡ M   0   X kk   0  M   0

Cada Xii es irreducible o [0]1x1.

09/11/2003

Π12 Π 22 M 0 0 0 M 0

Cada Πii es irreducible o [0]1x1 i-ésima clase transitoria: cuando se la abandona, no se regresa a ella

L Π rr L Π 2r L M L Π rr L 0 L 0 L M L 0

Π1,r +1 Π1, r + 2 Π 2,r +1 Π 2,r + 2 M M Π r ,r +1 Π r ,r + 2 Π r +1, r +1 0 0 Π r + 2,r + 2 M M 0 0

L L L L L L O L

Π 1m  Π 2 m  M   Π rm  0   0  M   Π mm 

Forma canónica para matrices reducibles

Cada Πr+j,r+j es irreducible. j-ésima clase ergódica. Cada clase ergódica es una cadena irreducible en sí misma

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

27

Cadenas reducibles (2)  n Γ Π =  11   0

Cada Πii es irreducible o [0]1x1 i-ésima clase transitoria: cuando se la abandona, no se regresa a ella

ρ (Π ii ) = 1 ⇒ Π ii 1 = 1, pero   ⇒ ρ (Π ii ) < 1 Π ii 1 ≤ 1 porque hay bloques Π ij , j ≠ i, no nulos

ρ (Γ11 ) < 1 ⇒ lim k →∞

Π11  0   M  0 Π≡  0   0  M   0

Π12 L Π rr Π 22 L Π 2 r M

Π1,r +1 Π 2,r +1

Π1,r + 2 Π 2,r + 2

M

M

Π r ,r +1

Π r ,r + 2 0

0

L M L Π rr

0 0

L L

0 0

Π r +1,r +1 0

Π r + 2,r + 2

M

L L

M

M

M

0

0

0

0

n −1

∑Γ

n

k −1 11

I + Γ11 + L + Γ k

L Π 1m  L Π 2 m  L M   L Π rm  Γ11 ≡ L 0   0  L 0  O M   L Π mm 

k = lim Γ11 =0 k →∞

i=0

 Γ12 Γ n22−1−i   Γ n22 

i 11

1 k −1 n −1 i 1 k −1 k i Γ11Γ12 Γ n22−1−i = ∑ ∑ Γ11 Γ12 Γ n22−1−i = ∑∑ k n =1 i =0 k i = 0 n =i +1 I + Γ22 + Γ222 + L + Γ22k −1−i = ∑ Γ Γ12 k i=0 k −1

i 11

1 k −1 n −1 i n −1− i =(I − Γ11 )Γ12 L Γ11Γ12 Γ 22 ∑∑ k →∞ k n =1 i = 0

lim

Γ12  Γ 22 

−1 I + Π + L + Π k −1 0 (I − Γ11 ) Γ12 L  = lim  k →∞ k L 0  −1 0 (I − Γ11 ) Γ12 L  lim Π k =   k →∞ L 0 

Siempre

Sii todas las submatrices de Γ22 son primitivas

pTj Π jj = pTj , j = r + 1,K , m 1pTr+1  +L+ Γ   = O M =L k  1pTm   lim Γ 22 = L si todas las submatrices de Γ 22 son primitivas

Cada Πr+j,r+j es irreducible. I + Γ 22 j-ésima clase ergódica. Cada clase ergódica es una cadena irreducible en sí misma lim k →∞ Los autovalores unitarios de cada Πr+j,r+j son simples y son raíces de la unidad. Los autovalores unitarios de Π son el conjunto de los autovalores unitarios de las submatrices Πr+j,r+j . k Pueden estar repetidos por aparecer en más e una submatriz Πr+j,r+j .

k −1 22

k →∞

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

28

Cadenas reducibles (3) Π11  0   M  0 Π≡  0   0  M   0

Π12 L Π rr

Π1,r +1

Π1,r + 2

Π 22 L Π 2 r M L M

Π 2,r +1 M

Π 2,r + 2 M

Π r ,r +1 Π r +1,r +1

Π r ,r + 2 0

0 0

L Π rr L 0

0

L

0

0

Π r + 2,r + 2

M

L L

M

M

M

0

0

0

0

L Π 1m  L Π 2 m  L M   L Π rm  Γ11 ≡ 0   0 L  L 0  O M   L Π mm 

I + Π + L + Π k −1 0 (I − Γ11 ) Γ12 L  lim =  k →∞ k L 0  0 (I − Γ11 )−1 Γ12L  k lim Π =   k →∞ 0 L   −1

Γ12  Γ 22 

Siempre Sii todas las submatrices de Γ22 son primitivas

Cada Πr+j,r+j es irreducible. j-ésima clase ergódica. Cada clase ergódica es una cadena irreducible en sí misma. Toda cadena reducible eventualmente queda absorbida en una clase ergódica. Si Πr+j,r+j es primitiva, la cadena llega a un estado estacionario determinado por el vector izquierdo de Perron de Πr+j,r+j . Si Πr+j,r+j es imprimitiva, la cadena oscila en la clase ergódica para siempre.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

29

Valor medio y autocorrelación en la cadena de Markov (t. discreto) R(n, n + k ) = E ( X n X n + k ) = ∑∑ xi x j P ( X n+ k = j, X n = i ) =

p T ( n + k ) = p T ( n) Π k

i

lim p(n) = p

= ∑∑ xi x j P( X n + k = j / X n = i) P ( X n = i )

n→∞

n

lim Π = 1p

T

i

n→∞

j

= ∑∑ xi x jπ ij (k ) pi (n) =

x = [x1 x2 L x N ]

T

i

y (n) = [x1 p1 (n) x2 p2 (n) L x N p N (n)]

T

n→∞

m X ( n) = E ( X n ) = ∑ xi pi (n) =pT ( n)x = pT (0)Π n x i

m X = lim m X (n) = pT x = y T 1

j

= y T ( n )Π k x → y T Π k x = R ( k ) n →∞

lim y (n) = y

n→∞

j

R (n, n) = y T (n)x = ∑ pi (n) xi2 = E ( X n2 ) = m X2 (n) i

R( k ) = y T Π k x → y T 1pT x = m X2 k →∞

C ( k ) = R (k ) − m X2 = y T (Π k − 1pT )x

C (0) = y T (I − 1pT )x = y T x − y T 1pT x = E ( X 2 ) − m X2 = σ X2

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

30

Cadenas de Markov en Tiempo Continuo Cadenas homogéneas

πij(t1, t2)

t2 − t1 = τ ,

ai

Π (τ + α ) = Π (τ )Π (α ) aj

t1

Ecuaciones de Kolmogorov t2

Puntos de Poisson

Cadena de Markov en tiempo continuo: Los cambios de estado ocurren en los puntos aleatorios Tn.

Π (t1 , t 2 )1 = 1 pT (t 2 ) = pT (t 2 )Π (t1 , t 2 ) Π (t1 , t3 ) = Π (t1 , t 2 )Π (t 2 , t3 )

Matriz de velocidad de cambio de la probabilidad de transición

t3 − t2 = α

Propiedades básicas

Π (t + τ ) = Π (t )Π (τ ) d Π (t + τ ) dΠ (τ ) = Π (t ) dτ dτ & (t + τ ) = Π (t )Π & (τ ) Π & (t ) = Π (t ) Π & (0) Π

& (τ ) = Π & (0 + ) Λ = lim Π τ →0 +

& (t ) = Π (t )Λ Π pT (t ) = pT (0)Π (t ) & (t ) = pT (0)Π (t )Λ = pT (t )Λ p& T (t ) = pT (0)Π

Solución

Π (t ) = e Λ t p T (t ) = pT (0)Π (t ) = pT (0) e Λ t

1 0 L 0 0 1 L 0  Π (0) = I =  L L L L   0 0 L 1 Condición inicial

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

31

Ecuaciones de Balance Global Solución en estado estacionario

kk

p(t ) = p = cte. ⇒ p& (t ) = 0 T

p Λ=0

Sistema de ecuaciones homogéneas

pT 1 = 1

Condición adicional

λij

p

ii

λji

Ecuaciones de balance global

∑ piλij = 0 ⇒ ∑ pi λij = − p j λ jj i≠ j

i

∑π ji = 1 ⇒ ∑ λ ji = 0 ⇒ −λ jj = ∑ λ ji i

i

∑ p j λ ji = ∑ piλij i≠ j

ll

i≠ j

i≠ j

Flujo Flujo de de velocidad velocidad de de probabilidad probabilidad saliente de j saliente de j

09/11/2003

jj

Flujo Flujo de de velocidad velocidad de de probabilidad probabilidad entrante a j entrante a j

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

32

Evolución de la cadena en tiempo continuo Π (t ) = e

Λvi = λi vi

Λt

p(t ) = p(0)Π (t ) = p(0) e Λ t Π (t )1 = 1 & (t )1 = 0 Π Λ1 = 0 pT Λ = 0

uTi Λ = λiuTi uTi v j = δij

U = [u1 LuN ], V = [v1 LvN ] UT V = I Λk = ∑λki viuTi i

f (Λ) = ∑ f (λi )viuTi i

λ1 = 0 > λ2 > L> λN

eΛt = ∑eλit viuTi = 1pT + ∑eλit viuTi → = 1pT i

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

i>1

t →∞

33

Valor medio y autocorrelación en la cadena de Markov (t. continuo) R (t1 , t 2 ) = E ( X (t1 ) X (t 2 )) = ∑∑ xi x j P ( X (t 2 ) = j , X (t1 ) = i ) =

Π (t ) = exp(Λt )

pT (t + τ ) = pT (t )Π (τ ) = pT (t ) exp(Λτ ) lim p(t ) = p t →∞

lim Π (t ) = 1pT

j

= ∑∑ xi x j P ( X (t 2 ) = j / X (t1 ) = i ) P ( X (t1 ) = i ) i

j

= ∑∑ xi x jπ ij (t1 , t 2 ) pi (t1 ) = i

t →∞

j

R(t , τ ) = ∑∑ xi x jπ ij (τ ) pi (t ) =

x = [x1 x2 L x N ]

T

i

y (t ) = [x1 p1 (t ) x2 p2 (t ) L xN p N (t )]

T

j

= y T (t )Π (τ )x → y T Π (τ )x = y T e Λτ x = R (τ ) n→∞

lim y (t ) = y

R (t , t ) = y (t )x = ∑ pi (t ) xi2 = E ( X 2 (t )) = m X2 (t ) T

t →∞

m X (t ) = E ( X (t )) = ∑ xi pi (t ) =pT (t )x = pT (0)Π (t )x i

m X = lim m X (t ) = pT x = y T 1 t →∞

i

i

R(τ ) = y T Π (τ ) x → y T 1pT x = m X2 k →∞

(

)

C (τ ) = R (τ ) − m = y T Π (τ ) − 1pT x

(

2 X

)

C (0) = y T I − 1pT x = y T x − y T 1pT x = E ( X 2 ) − m X2 = σ X2

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

34

Ejemplo : Proceso de Poisson Otra forma de obtener la matriz Λ:

π ij (t ) = P[ X (t ) = j / X (0) = i ] = = P[ j − i puntos en [0, t ]] = e−λt  0 Π=  0  L

λt e−λ t e −λt 0 L

− λ  0 & (0 + ) =  Λ =Π  0  L

(λt ) 2 e −λ t / 2! L λt e −λ t (λt )2 e −λ t / 2! λt e −λ t e −λt L L

λ 0 −λ λ 0 −λ L L

π ii (τ ) = P[ X (τ ) = i / X (0) = i ] = = P[T1 > τ ] = 1 − P[T1 ≤ τ ] =

(λt ) j −i −λ t e ( j − i)!

L L  L  L

L  L L  L

λii = π&ii (0) = −λ λi ,i +1 = π&i ,i +1 (0) = λ

= 1 − FT1 (τ ) = e −λτ

π i ,i +1 (τ ) = P[ X (τ ) = i + 1 / X (0) = i] = = P[T1 ≤ τ ] = FT1 (τ ) = 1 − e −λτ Solución de p& (t ) = p(t )Λ

p (0) = [1 0 0 L]

Condición inicial

p& 0 (t ) = −λp0 (t ) ⇒ p0 (t ) = e − λt p&1 (t ) = λp0 (t ) − λp1 (t ) = λ e −λt − λp1 (t ) ⇒ p1 (t ) = λt e −λt L (λt ) n −λ t p& n (t ) = λpn−1 (t ) − λpn (t ) ⇒ pn (t ) = e n!

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

35

Ejemplo : Señal binaria aleatoria a -a

0

1

-b

b

π 01 (τ ) = P[X (τ ) = 1 / X (0) = 0] = P[1 punto en `[0,τ ]] = 1 − e − aτ

π 10 (τ ) = P[X (τ ) = 0 / X (0) = 1] = P[1 punto en `[0,τ ]] = 1 − e −bτ  e − aτ Π (τ ) =  −bτ 1 − e

1 − e − aτ   e −bτ 

− a a  & (0) =  Λ=Π   b − b  b + a e −( a+b)t  a+b e Λt =  b  1 − e −( a + b )t  a + b

09/11/2003

]

 b p= a + b

a  a + b 

T

a  a + b  a E ( X (t )) = pT x = a+b  y = 0 

 a 1 − e −( a+b)t  a+b  a + b e − ( a +b )t   a+b b   ap0 = bp1   p0 = a + b p T Λ = 0 ⇔ ⇒ pT 1 = 1   p0 + p1 = 1  p1 = a a+b 

[

x = [0 1]

T

Puntos de Poisson

[

]

2

ab  a  R(τ ) = y e x =  e −( a +b )τ  + 2  a + b  (a + b ) T

Λt

= m X2 + σ X2 e −( a +b )τ C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

36

Ejemplo: Cola M/M/1 (1) Clientes atendidos de a uno por vez en orden de llegada •Tiempo entre arribos distribuido exponencialmente con parámetro λ. •Tiempo de servicio de un cliente distribuido exponencialmente con •parámetro µ.

π j , j +1 (τ ) = P( X (τ ) = j + 1/ X (0) = j ) = = P(1 arribo en [0,τ ]) = (λτ ) e −λτ → λτ + o(τ ) π j , j + 2 (τ ) = P( X (τ ) = j + 2 / X (0) = j ) = 2

= P(2 arribo en [0,τ ]) = (λτ ) e π j , j −1 (τ ) = P( X (τ ) = j − 1/ X (0) = j ) =

−λτ

/ 2!→ o(τ )

− λ µ & Λ = Π (0) =   0  L

λ 0 λ − (λ + µ ) µ − (λ + µ ) L L

pΛ Λ=0 − λp0 + µp1 = 0 λp j −1 − ( µ + λ ) p j + µp j +1 = 0

= P(1 partida en[0, τ ]) = ( µτ ) e −µτ → µτ + o(τ ) π jj (τ ) = P( X (τ ) = j / X (0) = j ) = = P(0 arribo y 0 partida en [0,τ ]) + P (1 arribo y 1 partida en [0,τ ]) + L =

µp1 = λp0 λp j −1 + µp j +1 = (λ + µ ) p j

j=0 j = 1,2,...

j=0 j = 1,2,...

= e−λτ ⋅ e − µτ + λτ e −λτ ⋅ µτ e −µτ → 1 − (λ + µ )τ + o(τ ) Flujo entrante

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

Flujo saliente

37

L L  L  L

Ejemplo: Cola M/M/1 (2) λ 00

11 µ

µp1 = λp0 λp j −1 + µp j +1 = (λ + µ ) p j

λ

λ 22

µ

j=0 j = 1,2,...

λ

λ jj

µ

µ

λ j+1 j+1

µ

µ

λp0 − µp1 = 0 λp j −1 − µp j = λp j − µp j +1 = cte.

  ⇒ cte. = 0 ⇒ λp j − µp j +1 j ≥ 1

p j = (λ / µ ) p j −1 = ρp j −1   j ∞ ∞ p0  ⇒ p j = (1 − ρ ) ρ j 1 = ∑ p j = p0 ∑ ρ = 1 − ρ  j =0 j =0 p j = ρ n p0

09/11/2003

ρ = λ / µ C k ≤C n 1 N (k − C )  p k (1 − p ) N − k ∑ Np1 k = 0 k 

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

41

Ejemplo : Modelo MMPP del multiplexado estadístico de voz (2) Freeze Out Fraction 30

Freeze Out Fraction

F ( N , C , p1 ) =

n 1 (k − C )  p k (1 − p ) N − k ∑ Np1 k =0 k  N

25

Capacidad del Canal (C)

MUX Estadístico

N fuentes de voz

Capacidad del canal: C canales de voz equivalentes

20

15

0.1 % 0.5 % 1.0 % 5.0 % 10.0 %

10

5

0 0

10

20

30

40

50

60

Número de Fuentes de Voz (N)

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

42

Ejemplo : Modelo MMPP del multiplexado estadístico de datos (1) Aplicación: Multiplexado Estadístico de Datos Caracterización de una fuente •Duración del intervalo OFF: fdp exponencial, 1/λ = tOFF. •Duración del intervalo ON: fdp exponencial, 1/µ = tON. •Burstiness: vel. pico/vel. promedio. T

1 1 rm = ∫ r (t )dt = ∑ rp tONi = rp P (ON ) T 0 T i P(ON ) = p1 = rm / rp b = rp / rm = 1 / p1

Probabilidad de actividad de la fuente Burstiness

G = N / C  ⇒ G = Nrp / rc = Nη > 1 C = rc / rp 

Ráfaga perdida o retrasada

rp

rc

rm

Ganancia de multiplexado estadístico

Se debe cumplir la condición de estabilidad:

S=

Capacidad del canal: C canales Velocidad del canal: rC

MUX Estadístico

N fuentes

Entradas

Nλarribos L Nrm Nrp pON Nrp = = = r+t / s>t) = P(s>r) El tiempo adicional necesario para completar el servicio del cliente que está siendo atendido, es independiente de cuándo comenzó el servicio.

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

47

Teoría de Colas • • • • • •

Teorema de Little Cola M/M/1 Cola M/M/1/K Cola M/M/c. Fórmula Erlang-C Cola M/M/c/c. Fórmula Erlang-B Cola M/M/N/N/N

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

48

Introducción • Teoría de Colas: Tipos de problemas y soluciones. • Introducción a las colas de espera. • Fundamentos: Probabilidad, estadística, procesos aleatorios.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

49

Tipos de problemas y soluciones (1) Usuario Usuario11 Recursos Recursoscompartidos compartidos Usuario UsuarioNN

• El modelo de una cola de espera generalmente se usa para representar un sistema de recursos compartidos.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

50

Tipos de problemas y soluciones (2) Flujo entrante Clientes que arriban

Cola Línea de espera

Servidor Cabeza de línea

Flujo saliente Clientes atendidos

Bloqueo, pérdida o desborde

Concepto básico: •Los clientes llegan para ser atendidos. Si todos los servidores están ocupados, el cliente espera en la cola y es atendido después. •Parámetros: tasa de arribos, velocidad de atención, número de servidores, capacidad de la cola... •Medidas: tiempo de espera, utilización de los servidores, tamaño de la cola, probabilidad de rechazo... 09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

51

Ejemplos Sistema

Clientes

Servidor

Procesador

Programas o procesos

CPU, disco, dispositivos I/O, bus...

MUX estadístico

Paquetes o celdas

Enlace de comunicaciones

Conmutador de circuitos

Llamadas

Canales

Red de acceso múltiple (LAN, LAN inalámbrica)

Paquetes o tramas

Medio (FO, UTP, RF)

Servicios Web

Requerimientos de cliente

Web server

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

52

Objetivos y métodos Objetivos • •

Método

Predecir la performance del sistema. Determinar cómo 9 Dimensionar el sistema (ancho de banda) 9 Controlar la entrada

•

Análisis de un modelo matemático.

•

Simulación.

•

Medición de sistemas reales.

para obtener la performance requerida, en términos de: 9 Grado de servicio (GoS) 9 Retardo

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

53

Factores Básicos • • • •

Tasa de arribos. Tiempo de servicio. Número de servidores. Longitud máxima de la cola (tamaño del “buffer”).

Otros • • • •

Tamaño de la población. Disciplina de servicio (FCFS, LCFS, prioridades, vacaciones). Modelo de carga de trabajo (tráfico). Comportamiento del cliente: Desistir, abandonar, ...

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

54

Modelos de tráfico Voz Video CBR

Dependencia de corto alcance

•Poisson •Modelos de regresión

Datos en paquetes Imágenes

Modelos de tráfico Dependencia de largo alcance

Video VBR

•F-ARIMA (Fractional AutoRegressive Integrated Moving Average) •FBM (Fractional Brownian Motion) ...

Dificultad del modelo

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

55

Modelo de switch o de router Link

Port

Port

Router / Switch

Router / Switch

Tasa de arribos

λ Paquetes/seg

09/11/2003

Tamaño del Buffer

B paquetes L bytes/paquete

µ

Tasa de servicio

Velocidad de Transmisión R bits/seg

µ = R/8L Paquetes/seg

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

56

Componentes del Retardo λ

µ

Procesamiento:

Cola:

Transmisión:

Propagación:

Tiempo desde que el paquete es recibido hasta que se le asigna un enlace de salida.

Tiempo desde que al paquete se le asigna un enlace de salida hasta que comienza la transmisión (tiempo de espera).

Tiempo entre la transmisión del primer bit y el último bit del paquete.

Tiempo desde que el último bit es transmitido por la fuente hasta que el último bit es recibido por el receptor.

Dependen de la carga de tráfico y el tamaño de los paquetes

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

57

Tipos de Colas Notación de Kendall

A/S/M/K/N/Q Distribución del tiempo entre arribos: M: exponencial (Markov) D: determinística (constante) G: General Distribución del tiempo de servicio: M: exponencial (Markov) D: determinística (constante) G: General Número de servidores

09/11/2003

Disciplina de servicio: FIFO, LIFO, prioridad,... Tamaño de la población. Puede ser finito o infinito.

Tamaño máximo de la cola, longitud del buffer o capacidad de almacenamiento.

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

58

Teoría de Colas • • • • • •

Teorema de Little Cola M/M/1 Cola M/M/1/K Cola M/M/c. Fórmula Erlang-C Cola M/M/c/c. Fórmula Erlang-B Cola M/M/N/N/N

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

59

Teorema de Little Tk

0

k =1

N (t )

D(t): partidas

T1

N(t)=A(t)-D(t): número de clientes en el sistema

A (T )

∫ N (t )dt =

A(t): arribos

T2

T

t

T

∑ Tk

1T 1 = ∫ N (t )dt = T0 T

A (T )

A(T ) 1 A(T ) A(T ) ∑Tk = T ⋅ A(T ) ∑ Tk = T Tk k =1 k =1

A(T ) ˆ = λT T N (t )

T

t

Número medio de clientes en el sistema

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

T

= λˆT Tk

T

E ( N ) = λ E (T )

Tasa de arribos

Tiempo medio de permanencia en el sistema

60

T

Teorema de Little: Aplicación Flujo entrante

Cola

Clientes que arriban

T =W + S E (T ) = E (W ) + 1/ µ E( N ) = E( Nq ) + λ / µ = = E( Nq ) + ρ

++ E(W)

09/11/2003

Nq

clientes en la cola

W

S

Tiempo de espera en la cola

Tiempo de servicio

N E(T)

ρρ

E ( N q ) = λE (W ) Tiempo medio de servicio: E ( N ) = λE (T ) E(S) = 1/µ seg/cliente “Little” means a lot!

λ clientes/seg

1/ µ 1 E (T ) = = 1− ρ µ − λ

Flujo saliente

Cabeza de línea Clientes atendidos

Línea de espera

E (W ) = E ( N )(1 / µ ) = λE (T ) / µ = ρE (T ) E (T ) = E (W ) + 1 / µ = ρE (T ) + 1 / µ

1/µ

Servidor

clientes en el sistema

T Tiempo en el sistema o retardo

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

61

Tipos de Colas Notación de Kendall

A/S/M/K/N/Q Distribución del tiempo entre arribos: M: exponencial (Markov) D: determinística (constante) G: General Distribución del tiempo de servicio: M: exponencial (Markov) D: determinística (constante) G: General Número de servidores

09/11/2003

Disciplina de servicio: FIFO, LIFO, prioridad,... Tamaño de la población. Puede ser finito o infinito.

Tamaño máximo de la cola, longitud del buffer o capacidad de almacenamiento.

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

62

Cola M/M/1 (1) •Sistema de un único servidor. •Clientes atendidos de a uno por vez en orden de llegada. •Los clientes arriban como un proceso de Poisson de tasa λ. Los tiempos entre arribos son vv.aa. exponenciales iid con media 1/ λ. •Tiempo de servicio de un cliente distribuido exponencialmente con media 1/ µ. •El sistema puede acomodar un número ilimitado de clientes.

Solución de las ecuaciones de balance global

ρ = λ / µ t ) = P[min(T1,L, Tk ) > t ] =

aj p0 j! c j −c a pj = ρ p0 c!

= P(T1 > t )L P(Tk > t ) = =e

−µ t

Le

−µ t

=e

pj =

−kµ t

kµ k servidores ocupados ⇒ tasa de partidas =  cµ λ 00

λ 11

µ

09/11/2003

λ 22

2µ

λp0 = µp1 λp j −1 + ( j + 1) µp j +1 = (λ + jµ ) p j λp j −1 + cµp j +1 = (λ + cµ ) p j

k 0) = P( N ≥ c) = ∑ ρ j −c pc = j =c

pc = C (c, a ) 1− ρ

1 a c  c −1 a j a c 1  C (c, a ) = ∑ + 1 − ρ c!  j =0 j! c! 1 − ρ  ∞

−1

∞

E ( N q ) = ∑ ( j − c) p j = ∑ ( j − c) ρ j −c pc = j =c

E( Nq )

j =c

C ( c, a ) C ( c , a ) = cµ − λ µ (c − a) λ C (c, a ) 1 E (T ) = E (W ) + E ( S ) = + µ (c − a ) µ λ E ( N ) = λE (T ) = λE (W ) + = E ( N q ) + a µ E (W ) =

09/11/2003

=

ρ C ( c, a ) 1− ρ

Probabilidad de encontrar todos los c servidores ocupados y tener que esperar en la cola: fórmula Erlang C.

Número medio de clientes en la cola.

Tiempo medio de espera en la cola. Tiempo medio total en el sistema (retardo). Número medio de clientes en el sistema.

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

70

Fórmula Erlang-C

1 a c  c −1 a j a c 1  ∑ +  C ( c, a ) = 1 − ρ c!  j =0 j! c! 1 − ρ  09/11/2003

−1

Probabilidad de encontrar todos los c servidores ocupados y tener que esperar en la cola: fórmula Erlang C.

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

71

Fórmula Erlang-C: Tiempo de espera

E (W ) = 09/11/2003

E(Nq )

λ

=

C ( c , a ) C ( c, a ) = cµ − λ µ (c − a)

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

72

Ejemplo: Call Center Ejemplo Un call center recibe 600 llamadas por hora, con una duración media de 3’. El operador trabaja durante 20’’ después de cada llamada. Se quiere que el tiempo medio de espera sea 20’’. Obtener el número de operadores necesario. a = (600/3600) ×(3×60+20) = 33.33 Erlang µE(W) = 20/(3×60) = 0.111 (Tiempo de espera normalizado) µE(W) =C(c,a)/(c-a) 0.111 = C(c,33.33)/(c-33.33) c = 36 operadores.

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

73

Ejemplo: Retardo en acceso DVB-RCS Internet access (browsing) Assumptions: Users: Internet usage/month/user Day-to month ratio BH-to-day ratio

1000 20 h 1/20 1/10

Pages/session 36 Page size 50 Kbyte Page delivery time 2 sec Page view time 60 sec Mean upstream packet length 80 Byte Mean downstream packet length 560 Byte Simultaneous session in BH 100 i.e. 10 % users Protocol: TCP/IP with 560 bytes/OB packet and 80 bytes/IB packet.

Peak dnstream thput in BH/user Peak upstream thput in BH/user Session duration Mean thput/user Mean upstream thput in BH Mean dnstream thput in BH Upstream packets in BH Dnstream packets in BH

DVB-S BASIC ACCESS PROFILE BA1

Forward max (Kbps) Forward min (Kbps) Return max (Kbps) Return min (Kbps) Unav/month (%) Activity MBH (%)

09/11/2003

256 8 16 2 0.1 20

Qty. 200.0 28.6 37.2 6.5 92.2 645.2 147.5 147.5

Unit Kbit/s Kbit/s sec Kbit/s Kbit/s Kbit/s

• • • • • •

Tráfico elástico NRT - transferencia de archivos. Proceso de arribo de archivos: Poisson con tasa λ.(archivos/seg) Tamaño medio de archivo: L (bits) Max. Bitrate de una terminal: rb (bit/seg) Ancho de banda (capacidad total) disponible: C (bit/seg). Objetivo: Garantizar un tiempo medio de transferencia E(T), o bien un determinado throughput promedio L/E(T) para todas las transacciones.

C (c , a ) 1 1  C (c , a )  + = 1 +  c−a  µ (c − a ) µ µ  µ = rb / L, c = C / rb , a = λL / rb

E (T ) = E (W ) + E ( S ) =

Downstream : Pag/session *(2+60)/60 PageSize*8/(2+60) Mean dnstream thput*80/560 MeanThput/user*10 users (50*1024/560)*10/(4+60)

BA2 BA3 BA4 BA5 BA6 BA7 256 256 512 1024 2048 4096 16 32 64 128 256 512 32 64 128 256 512 1028 4 8 16 32 64 128 0.1 0.1 0.1 0.1 0.1 0.1 20 20 25 25 25 30

E (T ) =

Byte bits rb Kbit/s µ paq/s λ paq/s a Erlang

Downstream 560.0 4,480.0 256.0 57.1 147.5 2.6

Upstream 80.0 640.0 32.0 50.0 147.5 2.9

Upstream : E (T ) =

BA8 4096 1024 1028 256 0.1 30

1  C (c,2.6)  C (c,2.6) < 16.1 ⇒ c = 4  < 0.3 ⇒ 1 + 57.1  c − 2.6  c − 2.6

L

1  C (c,2.9)  C (c,2.9) < 15.0 ⇒ c = 4 1 +  < 0.3 ⇒ 50.0  c − 2.9  c − 2.9

Para mantener acotado el retardo, se necesitan •4×256 = 1024 Kbit/s downstream •4×32 = 128 Kbit/s upstream. Comparar con los valores de throughput medio: •645.2 Kbit/s downstream •92.2 Kbit/s upstream .

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

74

Cola M/M/c/c La capacidad de la cola es igual al número total de servidores. Los clientes que arriban cuando todos los servidores están ocupados, son devueltos. a =λ/µ Carga ofrecida pj =

j

a p0 j!

00

λ 11

µ

λ 22

2µ

λ

λ c-1 c-1

3µ (c-1)µ

cc cµ

j = 0,L, c

 c aj  1 = ∑ p j ⇒ p0 =  ∑  j =0  j =0 j!  c

λ

−1

Probabilidad de que los c servidores estén ocupados = ac a c / c! P ( N = c ) = pc = = B(c, a) = PB probabilidad de bloqueo: Fórmula Erlang B p0 = c! 1 + a + a 2 / 2!+ L + a c / c! Tasa efectiva de arribos λ A = λ − λpc = λ [1 − B(c, a)]

λA = a[1 − B (c, a )] µ λ A a[1 − B(c, a)] λ = = [1 − B (c, a)] = ρ [1 − B (c, a)] µc µc c λ E ( N ) = λ A E ( S ) = [1 − B (c, a)] µ 09/11/2003

Carga soportada por cada servidor = utilización

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

75

Fórmula Erlang-B Fórmula Erlang-B

Fórmula Erlang-B 20

50 0.1%

18

45

0.5% 16

5.0%

35 Número de circuitos

14 Número de circuitos

40

1.0%

10.0%

12

20.0%

10 8

0.5% 25

1.0% 5.0%

20

6

15

4

10

2

5

0

0.1%

30

10.0% 20.0%

0 0,0

1,0

2,0

3,0

4,0

5,0

6,0

7,0

8,0

9,0

10,0

0,0

5,0

10,0

15,0

Tráfico total ofrecido (Erlang)

20,0

25,0

30,0

35,0

40,0

45,0

Tráfico total ofrecido (Erlang)

a c / c! a c / c! = P ( N = c) = B (c, a) = PB = 1 + a + a 2 / 2!+ L + a c / c! c k ∑ a / k! k =0

B (c + 1, a) = 09/11/2003

aB(c, a) c + 1 + aB(c, a )

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

76

50,0

Cola M/M/N/N/N •El número de servidores es N. La tasa de partidas es kµ cuando k servidores están ocupados. •La cantidad de fuentes (o “tamaño de la población”) es N. La tasa de arribos es (N-i)λ cuando hay i fuentes activas. •Es un modelo idéntico al MMPP.

Νλ 00

11 µ

λ

(Ν−j)λ

(Ν−1)λ 22

jj

2µ

j+1 j+1

N N

(j+1)µ

Nµ

Probabilidad que i fuentes entre N estén activas i −1

pi =

λi −1 pi −1 = µi

∏λ

i

i

i=0 i

∏µ

p0 i

i =1

λi = ( N − i )λ , µ i = iµ N

∑p

i

i=0

09/11/2003

=1

 N  λ   λ  pi =    1 +   i  µ   µ  λ E (i ) = N µ +λ λµ var(i ) = N (µ + λ )2

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

−N

 N  λ   =    i  µ + λ 

i

 µ    µ +λ 

Número medio de fuentes activas

77

N −i