Teoría elemental colas

NOTAS DE TEORÍA DE COLAS

Introducción

Teorema de Little

Es la única expresión válida para todos los tipos de colas. Fue publicado por Little en 1961.
Se considera un sistema al que le llegan peticiones de servicio de manera aleatoria. Las peticiones esperan hasta obtener servicio, una vez completado abandonan el sistema.

El teorema establece que

N = (W

N: númeromedio de usuarios en la cola
( : tasa media de llegadas a la cola
W: tiempo medio en la cola

Para probar esta relación consideremos que el sistema está en equilibrio estadístico. Para un intervalo de tiempo T

N (T) = número de llegadas en T
A (T) = tiempo total de servicio para todos los usuarios en el intervalo de tiempo T.
( (T) = N (T) / T intensidad media de las peticionesen el intervalo T
W (T) =A (T) / N (T) tiempo medio en el sistema durante el intervalo T
L (T) = A (T) / T número medio de peticiones en el sistema durante el intervalo T

[pic]

En el límite haciendo T( (
Si los límites existen

[pic]

también existirá el límite de L

L = ( W

Notación de Kendal

Modelo de Kendal (D.G. Kendal) estableció en 1953 el modelo:
A/B/c/k/s/Z• A : proceso de llegada
• B : proceso de servicio
• c : número de canales o servidores
• k : capacidad del sistema
• s: el número de fuentes
• Z : la disciplina de la cola

Proceso llegada
• M : Markoviano, Random , exponencial
• E : Erlangiano
Colas concatenadas (Ej. Carné de conducir)
Ek k colas concatenadas
• H :Hiperexponencial
tráficos de pico
• h : Hipoexponencial
trafico alisado
• G : General

Proceso de servicio
• Markoviano
• Erlangiano
• Hiperexponencial
• Hipoexponencial
• General

Número de canales
1,2, 3, ...(

Capacidad del sistema
Servidores + posiciones de cola

Número de fuentes
1,2, 3, ...(

Disciplina de la cola• FCFS Primero entra - primero sale (PEPS)
• LCFS Último entra - primero sale
• SIRO Servicio aleatorio (Service in random order)
• GD General (General Discipline)
• RR Round robin

Colas de longitud infinita. M/M/N

Cálculo de las probabilidades de estado

Partiremos de la ecuación de equilibrio de estado

La tasa de salida hasta el estado N (siendo N elnúmero de servidores) es de
[pic]

A partir del estado N, no puede aumentar la tasa de salida, es decir para los estados
N, N+1, N+2, .... la tasa de salida es constante

[pic]

Planteando las ecuaciones de estado

[pic]

a partir de aquí y conociendo que el sumatorio de probabilidades de estado es igual a 1 se obtiene la fórmula del estado 0.

[pic]
Obtenido el valor de [0] se conocenlos valores de las probabilidades de estado

Por ejemplo la probabilidad de tener todos los servidores ocupados será

[pic]

Cálculo de la probabilidad de entrar en cola. Escenario M/M/N

La probabilidad de entrar en cola será la probabilidad de que entre una petición de servicio cuando todos los servidores estén ocupados. Esa situación se dará cuando el sistema se encuentre en los estados[pic]

Usualmente la probabilidad de entrar en cola se representa como p(>0), literalmente la probabilidad de que el tiempo de espera sea mayor que cero.

Por lo tanto

[pic]

es decir la relación entre las peticiones de servicio que llegan con todos los servidores ocupados y todas las peticiones de servicio.

Eliminando ( y poniendo todas las probabilidades de estado en función de laprobabilidad [0]

[pic]
eliminando [0] , y reordenando reutilizando los resultados obtenidos en el cálculo de las probabilidades de estado

[pic]

Esta expresión admite una simplificación elegante.
Acciones:
Sumar y restar en el denominador el término [pic] con lo que el denominador quedaría
[pic]
[pic]
dividiendo ahora numerador y denominador por [pic] e identificando que...