Transcript
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 p<<1, np=a, y k del orden de np
n→∞
n→∞
p(1) = ae −a 15
21
22 combinaciones 7
p ( 2) =
a a2 p(1) = e −a 2 2
L a k −a p(k ) = e k!
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
4
Puntos de Poisson 6 1 5
Puntos de Poisson: Se colocan al azar n puntos en el intervalo real [0, T) t 2 − t1 ∆t = T T n pn (k puntos en [t1 , t 2 ]) = p k (1 − p) n−k k
3 2 t1
(λ∆t ) k −λ∆t pn (k puntos en [t1 , t 2 ]) n → = p(k ) e ,T →∞ k!
09/11/2003
t2
T
P(1 punto en [t1 , t 2 ]) = p =
λ = n /T n → ∞, T → ∞, λ = cte., p = ∆t / T → 0 a = np = n ∆t / T = λ ∆t
∆t
94 8 7
Densidad de puntos → λ∆t p(1) = λ∆t e − λ∆t ≈ λ∆t (1 − λ∆t ) ∆ t →0 (λ∆t ) k −λ∆t (λ∆t ) k (λ∆t ) k ≈ → e (1 − λ∆t ) ∆ t →0 k! k! k! P (1 punto en [t, t + ∆t ]) λ = lim ∆t →0 ∆t p(k ) =
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
5
Distribución Exponencial X t
x0
t+x
t
Separación entre puntos: sea X = distancia desde t al primer punto a la derecha de t. FX ( x) = P( X ≤ x) = 1 − P( X > x) = = 1 − P (0 puntos en [t , t + x]) = 1 − e
−λx
x≥0
f X ( x) = λ e −λx u ( x) ∞
1 1 E ( X ) = ∫ xλ e −λx dx = , var( X ) = 2 λ λ 0 Los tiempos entre arribos son independientes y distribuídos exponencialmente con parámetro λ
09/11/2003
X
Propiedad “sin memoria” de la distribución exponencial FX ( x / X ≥ x0 ) = P( X ≤ x / X ≥ x0 ) = =
P( X ≤ x, X ≥ x0 ) = P( X ≥ x0 )
P( x 0 ≤ X ≤ x) FX ( x) − FX ( x0 ) = = 1 − e−λ ( x − x0 ) P( X ≥ x0 ) 1 − FX ( x0 )
f X ( x / X ≥ x0 ) = λ e−λ ( x − x0 ) u ( x − x0 ) = f X ( x − x0 ) Lo que ocurre después de t0 es independiente de lo que ocurrió antes de t0..
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
6
Relación entre procesos de Bernoulli y Poisson Tiempo continuo
Tiempo discreto
Proceso de Bernoulli
Proceso de Poisson
Distribución entre arribos:
Distribución entre arribos:
Geométrica
Exponencial
09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
7
Ejemplo: Arribos Aleatorios servidor
A
09/11/2003
B
C
D
arribos
tiempo
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
•El proceso de arribos es Poisson. •Los tiempos entre arribos son independientes y distribuidos exponencialmente con parámetro λ.
8
Ejemplo: Modelo de Tráfico Telefónico fTh(t) X
Th: duración de la comunicación (holding time)
t+x
t
fTh (t ) = µ e − µ t u (t )
f X ( x) = λ e − λx u ( x) ∞
E ( X ) = ∫ xλ e 0
Arribos de Poisson
−λx
Fdp experimental
1 1 dx = , var( X ) = 2 λ λ 1/µ
Separación entre arribos exponencial
t
tk 1 2
L
λ: tasa de arribos (llamadas/seg) 1/µ: duración media de la llamada (seg) a = λ ⋅ (1/ µ )
Tráfico (Erlang)
i T ai = λˆi ⋅ Eˆ (Thi ) = a = ∑ ai = i
09/11/2003
N i 1 Ni 1 Ni ⋅ ∑ tki = ∑ tki T N i k =1 T k =1
1 L ∑ jtj T j =0
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
Número de ocupaciones simultáneas
Tiempo medio de ocupación de una línea Promedio de líneas ocupadas simultáneamente
Tiempo total en el que exactamente j líneas están ocupadas
9
Procesos de Markov Proceso de Markov: Es un proceso estocástico cuyo pasado no tiene influencia sobre el futuro si el presente está especificado.
Cadena de Markov: Proceso de Markov en tiempo discreto con un conjunto numerable de estados ai. Especificado en términos de:
π ij (n1, n2 ) = P( X n2 = a j / X n1 = ai )
Tiempo continuo: t n −1 < t n
P[X (t n ) ≤ xn / X (t ) ∨ t ≤ t n −1 ] = P[X (t n ) ≤ xn / X (t n −1 )]
Tiempo discreto:
∑π
ij
( n, m ) = 1
Π (n, m)1 = 1
πi1
continuo discreto
estado
p j (n) = ∑ pi (k )π ij (k , n)
Cadenas de Markov discreto
Procesos puntualesColas continuo
tiempo
πi2 ai
Matriz estocástica
P[X (t n ) ≤ xn / X (t n −1 ),L, X (t1 )] = P[X (t n ) ≤ xn / X (t n −1 )]
Sistemas dinámicos
Prob. transición
Propiedades: j
t1 < t 2 < L < t n
09/11/2003
Prob. estado
pi (n) = P( X n = ai )
i
p T ( n ) = p T ( k ) Π ( k , n)
πik
p1
π1j
aj
π2j
p2
πij p i
π ij (k , n) = ∑π il (k , m)π lj (m, n) l
Π (k , n) = Π (k , m)Π (m, n) C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
Ecuación de Chapman-Kolmogorov
10
Propiedades de las Cadenas de Markov Propiedades generales de los procesos de Markov P[ X (t n ) ≤ xn / X (t n −1 ),L, X (t1 )] = P[ X (t n ) ≤ xn / X (t n −1 )] ⇒ f ( xn / xn −1 , L, x1 ) = f ( xn / xn −1 ) E ( X n / X n −1 ,L , X 1 ) =
n −1
,L , x1 ) dx =
(n, m) = ∑ P( X m = a j / X n = ai ) = j
P( X m = a j , X n = ai ) P( X n = ai )
∑ p (k )π i
∞
∫ x f ( x / xn−1 ) dx =E ( X n / X n−1 )
−∞
f ( xn / xn +1 ,L , xn + k ) = f ( xn / xn +1 )
ij
j
=∑
−∞
=
∑π j
∞
∫ x f (x / x
Propiedades de las cadenas de Markov
ij
i
=
P( X n = ai ) =1 P( X n = ai )
(k , n) = ∑ P( X k = ai ) P( X n = a j / X k = ai ) = i
= ∑ P( X k = ai , X n = a j ) =P( X n = a j ) = p j (n) i
Un proceso de Markov también es de Markov si el tiempo se invierte.
k < m < n:
π ij ( k , n) = P ( X n = a j / X k = ai ) = ∑ P ( X n = a j , X m = al / X k = ai ) = l
k < m < n: f ( xn , x m , xk ) f ( xn , xk / x m ) = = f ( xm ) =
Si el presente está especificado, el pasado es independiente del futuro.
f ( xn / xm ) f ( xm / xk ) f ( xk ) = f ( xn / xm ) f ( xk / xm ) f ( xm )
=∑
P ( X n = a j , X m = a l , X k = ai ) = P ( X k = ai )
=∑
P ( X n = a j / X m = a l , X k = ai ) P ( X m = al , X k = a i )
l
l
P ( X k = ai )
= ∑ P ( X n = a j / X m = a l , X k = a i ) P ( X m = a l / X k = ai ) = l
= ∑ P ( X n = a j / X m = a l ) P ( X m = al / X k = a i ) = l
09/11/2003
=
= ∑ π il ( k , m)π lj ( m, n)
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría l de Colas
11
Evolución de una Cadena de Markov Cadenas homogéneas: Las probabilidades de transición πij(m,n) sólo dependen de la diferencia k=n-m. Ecuación de Chapman-Kolmogorov:
π ij (k , n) = ∑ π il (k , m)π lj (m, n)
Evolución del sistema
Π (2) = Π (1)Π (1) = Π 2 L Π (n + 1) = Π (n)Π Π ( n) = Π n
p(n) = [ p1 (n) L p N ( n)]T p T ( n) = p T ( k ) Π ( k , n) = = pT (k )Π (n − k ) = = pT (k )Π n − k = = pT (0)Π n
l
Estado estacionario
Π (k , n) = Π (k , m)Π (m, n)
p ( n) = p pT = pT Π
π ij (n − k ) = ∑ π il (m − k )π lj (n − m) l
Π ( n − k ) = Π ( m − k )Π ( n − m) Π ( p + q ) = Π ( p ) Π ( q ) = Π ( q )Π ( p )
Matriz de probabilidades de transición a n pasos. El elemento i,j de Πn es la probabilidad de llegar de i a j en exactamente n pasos.
Si existe el estado estacionario, el vector de probabilidad de estados p de una cadena de Markov, es un autovector izquierdo de su matriz de transición Π con autovalor 1. ¿Existe ¿Existeun unestado estado estacionario? Si p(1) ≠ p, el proceso no es estacionario. estacionario? Si Πn tiende a un límite para n → ∝, el proceso es asintóticamente estacionario.
09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
12
Ejemplo: Cadena de 2 estados Aplicación: Es un modelo para voz en paquetes.
a
1-a 00
11
1-b
b
Matriz de transición
Solución en estado estacionario
π 01 1 − a a π = Π = 00 π 10 π 11 b 1 − b 1 b a (1 − a − b) n a − a n + Π ( n) = Π = a + b b a a + b − b b
09/11/2003
Estado 0: inactivo (silencio). La probabilidad de que la próxima TS sea activa es a, y la probabilidad de que permanezca en el estado inactivo es 1-a. Estado 1: activo (habla). La probabilidad de que la próxima TS sea inactiva es b, y la probabilidad de que permanezca en el estado activo es 1-b. En el estado activo, una TS contiene una celda con probabilidad p, y se tiene un proceso de Bernoulli.
p = pΠ
[ p0
p1 ] = [ p0
a p0 = b 1 − a p1 ] a+b ⇒ b b 1 − a p0 + p1 = 1 p1 = a+b
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
13
Ejemplo: Proceso de cuenta binomial Ejemplo: Proceso de cuenta binomial.
1-p
Es una secuencia de variables aleatorias de Bernoulli independientes. Sn es el proceso de suma o cuenta que da el número de éxitos en las primeras n pruebas. En cada paso, Sn puede incrementarse en 1 con probabilidad p o quedar igual con probabilidad 1-p. 1 Ik = 0
p
11
1-p p
22
1-p p
n-1 n-1
1-p p
Matriz de transición
Con probabilidad p Con probabilidad 1-p
n Sn = I1 + L + I n ⇒ P( Sn = j ) = p j (1 − p) n− j j
09/11/2003
00
1-p
0≤ j≤n
p 0 0 1 − p 0 1− p p 0 Π= 0 0 1− p p L L L L
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
L L L L
14
nn
Propiedades Generales de la Matriz de Transición Radio espectral
Matriz no negativa
ρ (Π ) = max λ
Π ≥ 0 ⇔ π ij ≥ 0 ∀i, j
λ∈σ (Π )
1 ∈ σ (Π ) ⇒ 1 ≤ ρ (Π )
n
Π ≥0 Matriz Estocástica Π1 = 1 ⇔ (1,1) es un par propio de Π
Π1 = 1 ⇔ Π ∞ max Πx ∞ = max ∑ π ij = 1 x ∞ =1
i
ρ (∗) ≤ ∗ ⇒ ρ (Π ) ≤ Π ∞ = 1
El radio espectral es menor o igual que cualquier norma
ρ (Π ) = 1 El radio espectral es unitario
i
Norma infinito: máxima suma de valores absolutos de cada fila = 1
09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
15
Clasificación de Estados •
Accesible: j es accesible desde i si hay alguna secuencia de transiciones de i a j con probabilidad no nula: ∃n>0/ π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
ρ = λ / µ <1⇔ λ < µ
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
La tasa de arribos debe ser menor que la velocidad de servicio; de otro modo, la cola crece sin límite.
38
Ejemplo: Proceso de Nacimiento y Muerte General •Transiciones limitadas a estados adyacentes. •Los arribos ocurren como un proceso de Poisson de tasa λι. Los tiempos entre arribos son vv.aa. exponenciales iid con media 1/ λι. •El tiempo entre desapariciones está distribuido exponencialmente con media 1/ µι.
Ecuaciones de balance global
µ1 p1 = λ0 p0 λ j −1 p j −1 + µ j +1 p j +1 = (λ j + µ j ) p j
j=0 j = 1,2,..., N - 1
λ N −1 p N −1 = µ N p N
j=N
Solución de las ecuaciones de balance global λ0 00
λ1 11
µ1
λ2 22
µ2
jj µ3
µj
λN-1
λj
λj-1
j+1 j+1 µj+1
N N µN
µ1 p1 − λ0 p0 = 0 λ j −1 p j −1 + µ j +1 p j +1 − (λ j + µ j ) p j = cte. = 0 λ N −1 p N −1 − µ N p N = 0
j=0 j = 1,2,..., N - 1 j=N
i −1
λ pi = i −1 pi −1 = µi
∏λ
i
i =0 i
∏µ
p0 i
i =1
09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
39
Ejemplo: Proceso de Poisson Modulado por Markov (MMPP) •Modelo para voz en paquetes. •Duración del intervalo de silencio: fdp exponencial, 1/λ = 600 mseg. •Duración del intervalo de habla: fdp exponencial, 1/µ = 400 mseg.
Modelo para N fuentes Νλ 00
11 µ
22
jj
2µ
11 habla µ
i −1
pi =
V paquetes/seg
λi −1 pi −1 = µi
∏λ
i
i
i=0 i
∏µ
p0 i
i =1
λ p0 µ p0 + p1 = 1
µp1 = λp0 ⇒ p1 =
09/11/2003
N N Nµ
Probabilidad que i fuentes entre N estén activas
λ 00
j+1 j+1 (j+1)µ
Modelo para una fuente única
silencio
λ
(Ν−j)λ
(Ν−1)λ
µ = 0.6 µ +λ λ p1 = = 0.4 µ +λ p0 =
λi = ( N − i )λ , µ i = iµ N
∑p
i
i=0
=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
40
N −i
Ejemplo : Modelo MMPP del multiplexado estadístico de voz (1) Aplicación: Multiplexado Estadístico de Voz •Describe el comportamiento de multiplicadores de tramas (DCME). •Próxima generación de DCME soportada por AAL2. •Duración del intervalo de silencio: fdp exponencial, 1/λ = 600 mseg. •Duración del intervalo de habla: fdp exponencial, 1/µ = 400 mseg.
N fuentes de voz
MUX Estadístico
Capacidad del canal: C canales de voz equivalentes
N λ pi = i µ + λ µ p0 = = 0.6, µ +λ E (i ) = Np1
N −i
N µ = p1i p0N −i i µ +λ λ p1 = = 0.4 µ +λ
Probabilidad que i fuentes entre N estén activas
var(i ) = Np0 p1 Promedio de tráfico recortado Promedio de tráfico total N n Promedio de tráfico recortado =∑ r (k ) p k (1 − p ) N − k k =0 k F ( N , C , p1 ) =
k − C r (k ) = 0 F ( N , C , p1 ) =
09/11/2003
i
k >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 = = = <1 rc rc rc brc
09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
43
Ejemplo : Modelo MMPP del multiplexado estadístico de datos (2) i
N λ µ pi = i µ λ µ λ + + µ λ , p1 = p0 = µ +λ µ +λ E (i) = Np1
N −i
N = p1i p0N −i Probabilidad que i fuentes entre N estén activas i
pi Np1 (1 − p1 )
Np1 C
i
Aproximación gaussiana a la distribución binomial
var(i) = Np1 (1 − p1 ) PL = Q (α )
Probabilidad de pérdida
C ≈ Np1 + α Np1 (1 − p1 )
Número de canales para la prob. de pérdida PL
C = 1/η 0 = Np1 + α 1 − p1 Np1 − 1 / η Np1 = −
α 1 − p1 1 ± α 2 (1 − p1 ) + 4 / η 2 2
09/11/2003
Throughput normalizado
[
η α 2 (1 − p1 ) + 4 / η − α 1 − p1 4 p1 (Grc / rp )rm Grm Nr S= m = = = Gp1 rc rc rp
G = Nη =
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
44
]
2
Ejemplo : Modelo MMPP del multiplexado estadístico de datos (3) Ganancia de Multiplexado Estadístico
Ganancia
10.00 8.00 6.00
Throughput
Prob. pérdida = 10-6
12.00
b=2 b=4 b=8 b=12 b=16 b=20
0.90 0.80
b=2 b=4 b=6 b=8 b=10 b=12 b=14 b=16 b=18 b=20
16.00 14.00
Throughput Normalizado
4.00 2.00
0.70 0.60 0.50 0.40 0.30 0.20 0.10 0.00
0.00 0
0.05
0.1
0.15
0.2
0.25
0
0.3
Relación vel. pico/vel. enlace
G = Nη =
09/11/2003
η 4 p1
[ α (1 − p ) + 4 / η − α 2
1
0.05
0.1
0.15
0.2
0.25
0.3
Relación vel. pico/vel. enlace
1 − p1
]
2
S=
Nrm (Grc / rp )rm Grm = = = Gp1 rc rc rp
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
45
Ejemplo : Modelo MMPP del multiplexado estadístico de datos (4) Ganancia de Multiplexado Estadístico 30.00
Ganancia
N=30
Prob. pérdida 10-2
25.00
b=32
25
20.00
0.00
η 4 p1 G = Nη
G=
[ α (1 − p ) + 4 / η − α 2
1
15 16
10.00 5.00
20
24
15.00
Solución simultánea de las ecuaciones
10
12 6 2
0
0.2
0.4
0.6
0.8
1
Relación vel. pico/vel. enlace 09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
46
1 − p1
]
2
Utilidad de los modelos de Markov •
•
El modelo de Poisson es apropiado si hay un gran número de usuarios similares e independientes. Si se combinan n procesos de arribos iid, no necesariamente Poisson de tasa λ/n, – –
•
La tasa de arribos del agregado es λ. El proceso agregado se aproxima a un proceso de Poisson de tasa λ cuando n→∞ en condiciones bastante amplias.
PASTA: Poisson Arrivals See Time Averages
09/11/2003
•
La distribución exponencial no tiene memoria. –
–
• •
Lo que ocurre después del tiempo t es independiente de lo que ocurrió antes de t. El conocimiento del pasado no sirve para predecir el futuro.
Para los tiempos de servicio: P(s>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
ρ = λ / µ <1 p j = (1 − ρ ) ρ j = P[ N (t ) = j ]
ρ ρ , var( N ) = σ N2 = 1− ρ (1 − ρ ) 2 1/ µ E ( S ) 1 E( N ) 1 ρ E (T ) = T = = = = = λ λ 1− ρ 1− ρ 1− ρ µ − λ E(N ) = N =
E (W ) = W = T − S = λ 00
λ 11
µ
λ 22
µ
λ
λ jj
µ
µ
λ j+1 j+1
µ
µ
ρ S −S = S 1− ρ 1− ρ
λρ ρ2 E ( N q ) = N q = λW = S= 1− ρ 1− ρ E ( N s ) = N s = λS = λ (1/ µ ) = ρ P(servidor ocupado) = 1 − p0
µp1 = λp0 λp j −1 + µp j +1 = (λ + µ ) p j 09/11/2003
j=0 j = 1,2,...
Ecuaciones de balance global
P(servidor ocupado) = N s
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
⇒ ρ = 1 − p0
63
Cola M/M/1 (2)
E(N)
20
20
15
15
10
µE(T)
5
5
0
0 0
0,2
0,4
E (N ) =
09/11/2003
10
0,6
ρ 1− ρ
0,8
ρ
1
0
0,2
0,4
0,6
0,8
1
ρ E (T ) =
E (S ) 1/ µ = 1− ρ 1− ρ
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
64
Aplicación: Multiplexado de tráfico Capacidad de transmisión del canal: C bit/seg. M flujos de tráfico de Poisson de tasa λ/M comparten el canal. Longitud de paquetes distribuida exponencialmente con media L.
FDM, TDM •Se crean M canales separados, cada uno de capacidad C/M. •En FDM, el retardo de transmisión es ML/C. •En TDM, el retardo de transmisión es ML/C si el paquete es mucho más largo que 1 TS. Si L = 1 TS, el retardo de transmisión es L/C, pero debe esperar (M-1) tiempos de TS entre transmisiones.
09/11/2003
Retardo de transmisión del canal
Estadístico Los paquetes de cada flujo se combinan en una sola cola y se transmiten con un ordenamiento FCFS.
λ/M
C/M
λ/M
λ/M
C/M
λ/M
λ/M
C/M
λ/M
µ C/M = L M M 1 = T = µ /M −λ /M µ −λ µi =
1 L = µ C
•Un •Unpaquete paquetetarda tardaMMveces vecesmás másenenlalacola colayyenenser serservido servidoenenTDM TDMooFDM, FDM,que queenen multiplexado estadístico. multiplexado estadístico. •Sin •Sinembargo, embargo,lavarianza lavarianzadel delretardo retardoesesmenor menorenenTDM TDMooFDM. FDM. •TDM y FDM malgastan capacidad del canal cuando un flujo •TDM y FDM malgastan capacidad del canal cuando un flujononotiene tienetráfico, tráfico,pero pero eliminan la necesidad de identificar a qué flujo pertenece cada paquete. eliminan la necesidad de identificar a qué flujo pertenece cada paquete. C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
λ C
µ=
C L
T =
1 µ −λ 65
Cola M/M/1/K (1) Cola M/M/1 con capacidad finita. El sistema puede contener hasta K clientes. Los que llegan cuando el sistema está lleno, son devueltos. pj λ 00
λ 11
λ 22
µ
µ
λp0 = µp1 λp j −1 + µp j +1 = (λ + µ ) p j λpK −1 = µpK
λ
λ K-1 K-1
µ
µ
0 K K
µ
j =0 j = 1,2,L.K − 1 j=K
p j = ρp j −1 = ρ p0 1− ρ K ρj 1 − ρ K +1 ⇒ p j = K +1 1 = ∑ p j = p0 1− ρ 1 − ρ j =0 j
09/11/2003
j = 0,L, K
ρ<1 K
ρ=1 pj
pj 0
K
ρ>1
0
K
( K + 1) ρ K +1 ρ − 1− ρ 1 − ρ K +1 1− ρ Probabilidad de bloqueo PB = P( N = K ) = pK = ρK K +1 1− ρ λB = λPB Tasa de rechazos Tasa efectiva de arribos λ A = λ − λB = λ (1 − PB ) Carga ofrecida E ( N ) = λE ( S ) = ρ E(N ) =
1 1− ρ K E ( N A ) = λ A E ( S ) = λ (1 − pK ) = ρ µ 1 − ρ K +1
Carga satisfecha
E(N ) E(N ) 1 1 ( K + 1) ρ K 1 − ρ K +1 E (T ) = = = − λA λ (1 − PB ) µ 1 − ρ 1 − ρ K +1 1 − ρ K
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
66
Cola M/M/1/K (2) 1
10
K=10
K=10
0,8
8
K=2
λA/µ
0,6
6
µE(T) 0,4
4
0,2
2
K=2 0
0
0
0,5
1
1,5
2
ρ
λA = λ
K
09/11/2003
0,5
1
1,5
2
ρ
K
1− ρ 1− ρ = µρ K +1 1− ρ 1 − ρ K +1
E ( N A ) = λA / µ
0
1 1 ( K + 1) ρ K 1 − ρ K +1 − E (T ) = µ 1 − ρ 1 − ρ K +1 1 − ρ K
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
67
Ejemplo: Dimensionamiento de un buffer Capacidad del buffer requerida
1,00E+00
200
1,00E-01
180
1,00E-02
160
1,00E-03
140
1,00E-04
ρ = 0.9
1,00E-05
0.5 0.7
1,00E-06
0.8
0.8
0.9
1,00E-07
0.7
1,00E-08
120 100 80 60 40
0.5
1,00E-09
Capacidad
P(overflow)
Probabilidad de "overflow"
20
1,00E-10
0 0
20
40
60
80
100
120
140
160
180
200
0,0
0,1
0,2
0,3
Tamaño del buffer
PB = P( N = K ) = pK =
0,4
0,5
0,6
Carga ofrecida
ρ
0,7
0,8
0,9
1− ρ ρK K +1 1− ρ
λB = λPB λ A = λ − λB = λ (1 − PB ) 09/11/2003
C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas
68
1,0
Cola M/M/c (1) El número de servidores es c. La tasa de partidas es kµ cuando k servidores están ocupados, pues: k servidores ocupados ⇒ tiempo hasta la próxima partida T = min(T1,LTk ) P(T > 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