Temas 5 y 6 6.263/16.37 Introducción a la teoría de colas

Temas 5 y 6

6.263/16.37

Introducción a la teoría de colas

Eytan Modiano MIT, LIDS

Eytan Modiano Dispositiva 1

Redes conmutadas por paquetes

Red de paquetesPS

PS PS

PS

PSPS

PS (buffer)

Los mensajes se dividenen paquetes que se enrutan hacia su destino

Eytan ModianoDiapositiva 2

paquetes

conmutaciónde

Cola

Sistemas de colas

• Se utilizan para analizar el rendimiento de las redes

• En las redes de paquetes, los eventos son aleatorios:– Llegadas de paquetes aleatorias – Tamaño de paquetes aleatorio

• Mientras en la capa física nos preocupaba la tasa de error de bits (BER),en la capa de red nos interesan los retardos:

– ¿Cuánto tiempo espera un paquete en la cola? – ¿Qué tamaño tienen las colas?

• En las redes conmutadas por circuitos queremos saber las

– ¿Cuántos circuitos son necesarios para limitar la probabilidad de bloqueo?

Eytan Modiano Diapositiva 3

probabilidades de que se produzca un bloqueo de llamada:

Eventos aleatorios

• Proceso de llegada:– Los paquetes llegan según un proceso aleatorio– Generalmente, el proceso de llegada se modela como proceso de Poisson

• El proceso de Poisson:– Tasa de llegada de λ paquetes por segundo

– Sobre un pequeño intervalo δ:

P(exactamente una llegada) = λδ + ο(δ) P(0 llegadas) = 1 - λδ + ο(δ) P(más de una llegada) = 0(δ)

donde 0(δ)/ δ −> 0 �� δ −> 0.

– Se puede demostrar que:

P(n llegadas en el intervalo T)= ( λT ) n e−λ T

n!


El proceso de Poisson

P(n llegadas en el intervalo T)= ( λT ) n e−λ T

n!

n = número de llegadas en T

Se puede demostrar que:

E[n] = λT

E[n2] = λT + (λT)2

σ 2 = E[(n -E[n])2] = E[n2] - E[n]2 = λT


Tiempos entre llegadas

• Tiempo que pasa entre las llegadas (IA)

P(IA <= t) = 1 - P(IA > t) = 1 - P(0 llegadas en un tiempo t)

= 1 - e-λt

• Esto se conoce como distribución exponencial:– CDF entre llegadas = FIA (t) = 1 - e-λt

– PDF entre llegadas = d/dt FIA(t) = λe-λt

• La distribución exponencial se suele utilizar para modelar los tiempos de servicio (es decir, la distribución del tamaño de los paquetes)


Propiedad de Markov (ausencia de memoria)

P(T ≤ t0 + t | T > t0 ) = P(T ≤ t)

Demostración:

P(T ≤ t0 + t | T > t0 ) = P(t0 < T ≤ t0 + t) P(T > t0 )

t 0 +t∫ λe−λtdt −e− λt | t0

t0 + t −e−λ ( t +t 0 ) + e−λ ( t0 ) t 0= = = ∞ ∞ e−λ ( t0 )

∫ λe− λtdt −e−λt |t 0 t0

= 1 − e − λt = P(T ≤ t)

• ¡Los antecedentes no ayudan a prevenir el futuro!

• ¡La distribución del tiempo hasta la próxima llegada es independiente decuándo se produjo la última llegada!


Ejemplo

• Supongamos que un tren llega a una estación siguiendo un procesode Poisson con una media de tiempo entre llegadas de 20 minutos

• Cuando un cliente llega a la estación, la media de tiempo transcurrido hasta la siguiente llegada es de 20 minutos:

– Independientemente de cuándo haya llegado el tren anterior

• ¡La media de tiempo desde la última salida es de 20 minutos!

• Paradoja: si pasaron una media de 20 minutos desde la llegada delúltimo tren y una media de 20 minutos hasta la llegada del próximo,entonces pasarán una media de 40 minutos entre los trenes:– ¡Pero nosotros supusimos una media de tiempo entre llegadas de 20 minutos! – ¿Qué ha sucedido?


Modelos de colas

Clientes

cola/buffer

• Modelo para: – Los clientes que esperan en línea– La línea de ensamblaje– Los paquetes de una red (línea de transmisión)

• Se quiere saber: – El promedio de clientes que hay en el sistema– La media de espera que experimenta un cliente

• Cantidades obtenidas según: – La tasa de llegada de los clientes (promedio de clientes por unidad de tiempo) – La tasa de servicio (promedio de clientes que puede atender el servidor

por unidad de tiempo)

servidor


Teorema de Little

Red (sistema) (N,T)λ paquetes por segundo

• N = promedio de paquetes que hay en el sistema• T = promedio de tiempo que está un paquete en el sistema• λ = tasa de llegada de paquetes al sistema

(no necesariamente de Poisson)

• Teorema de Little: N = λT – Se puede aplicar a todo el sistema o a una de sus partes – Sistema concurrido -> largas esperas

¡En los días de lluvia, la gente conduce más despacio y las carreteras están más congestionadas!


Demostración del Teorema de Little

α(t), β(t)

t1 t2 t3 t4

• α(t) = número de llegadas en un tiempo t • β(t) = número de salidas en un tiempo t • ti = tiempo de llegada del cliente i • Ti = tiempo que el cliente i permanece en el sistema• N(t) = número de clientes que hay en el sistema en un tiempo t = α(t) - β(t)

• Demostración similar cuando no se sigue un servicio FCFS, es decir, cuando

α(t)

T1 T2

T3 T4

β(t)


el primero que llega no es el primero en ser atendido

Demostración del Teorema de Little

t1Nt = ∫ N (τ )dτ = tiempo medio de los clientes en la cola

t 0

N = Límitet→ ∞ Nt = tiempo medio en estado estacionario

λt = α (t) / t, λ = Límite t→ ∞ λ t = tasa de llegada

α

∑( t)

Ti Tt = i= 0

α (t) = tiempo medio de espera en el sistem a, T = Límitet → ∞ Tt

• Suponiendo que existen los límites anteriores; se supone un sistema ergódicoα ( t)

N (t) = α(t) − β(t ) ⇒ Nt = ∑ i=1 Ti

t α (t ) α( t )

α ( t)N = límt → ∞

∑i =1 Ti , T = límt →∞

∑i =1 Ti ⇒ ∑ i=1

Ti = α (t)T t α (t)

α ( t) α ( t)

Eytan Modiano N = ∑ i=1

Ti = (α(t)) ∑ i=1 Ti = λT

Diapositiva 13 t t α (t)

Aplicación del Teorema de Little

• El Teorema de Little se puede aplicar a casi todos los sistemas o a alguna de

• Ejemplo:Clientes servidor

Cola/buffer

1) El emisor: DTP = tiempo de transmisión de paquetes– Promedio de paquetes en el emisor = λDTP = ρ = uso del enlace

2) La línea de transmisión: Dp = retardo de propagación– Promedio de paquetes en camino = λDp

3) La cola: Dq = promedio de espera en la cola– Promedio de paquetes en la cola = Nq = λDq

4) Emisor + cola:– Promedio de paquetes = ρ + Nq


sus partes

Aplicación a un sistema complejo

λ 1

λ

λ

2

3 λ 1

λ 2

λ 3

• Tenemos una red compleja con varias líneas de tráfico que se mueven por ella e interactúan de forma arbitraria

• Para cada línea i por separado, Little dice que Ni = λiTi

• Para todas las líneas en conjunto, Little dice que N = λT, donde:

• N = ∑i Ni & λ = ∑i λi i= k

• Del Teorema de Little se obtiene: T = ∑ i=1 λ i Ti

i= k

Eytan Modiano ∑ i=1

λi Diapositiva 15

Colas con un único servidor

cola

λ paquetes por segundo

• M/M/1:

Servidor

µ paquetes por segundo

Tiempo de servicio = 1/µ

– Llegadas de Poisson; tiempos de servicio exponenciales

• M/G/1: – Llegadas de Poisson; tiempos de servicio generales

• M/D/1: – Llegadas de Poisson; tiempos de servicio deterministas (fijos)


Cadena de Markov para un sistema M/M/1

λδ λδ λδ λδ

0 1 2

1−λδ

k

µδ µδ µδ µδ

• Estado k => k clientes en el sistema

• P(I,j) = probabilidad de transición del estado I al estado j – Para δ => 0, se obtiene:

P(0,0) = 1 - λδ, P(j,j+1) = λδ P(j,j) = 1 - λδ −µδ P(j,j-1) = µδ

P(I,j) = 0 para todos los otros valores de I,j.

• Procesos de nacimiento y muerte: las transiciones se producen sólo entre

– λδ , µδ son las velocidades de flujo entre los estados


estados adyacentes:

Análisis de equilibrios

• Queremos obtener P(n) = la probabilidad de estar en el estado n

• En el equilibrio λP(n) = µP(n+1) para todo n: – Ecuaciones de equilibrio local entre dos estados (n, n+1) – P(n+1) = (λ/µ)P(n) = ρP(n), ρ = λ/µ

• Continúa: P(n) = ρn P(0) ∑i

∞

= 0 P(n) = 1

• Luego, por axioma de probabilidad: ∞ P(0)

⇒ ∑i =0 ρnP(0) =

1− ρ= 1

⇒ P(0) = 1 − ρ

P(n) = ρ n(1 − ρ)


Tamaño medio de la cola

∞ ∞

N = ∑ nP(n) =∑ nρn (1 − ρ) = ρ

n=0 n=0 1− ρ

N =ρ

= λ / µ

= λ

1 − ρ 1 − λ / µ µ − λ

• N = media de clientes en el sistema• El promedio de tiempo que pasa un cliente en el sistema T =

1 se puede obtener a partir de la fórmula de Little (N=λT => T = N/λ) µ − λ

• T incluye el tiempo de espera en la cola más el tiempo de servicio (tiempo de servicio= DTP = 1/µ ) 1

– W = tiempo que se pasa en la cola = T - 1/µ => W = µ − λ

− 1 µ

• Por último, la media de clientes en cola se puede obtener a partir de lafórmula de Little:

λNQ = λW =

µ − λ−

λ= N − ρ

µ


Ejemplo (restaurante de comida rápida)

• En un restaurante de comida rápida llegan 100 clientes por horay se tarda 30 segundos en servir a cada uno de ellos

• ¿Cuánto tiempo pasan los clientes en el restaurante?

– Tasa de servicio = µ = 60/0.5=120 clientes por hora– T = 1/µ−λ = 1/(120-100) = 1/20 hrs = 3 minutos

• ¿Cuánto tiempo esperan en la cola? – W = T - 1/µ = 2.5 minutos

• ¿Cuántos clientes hay en el restaurante? – N = λT = 5

• ¿Cuál es la utilización del que sirve? – ρ = λ/µ = 5/6


Conmutación de paquetes frente a conmutación de circuitos

1

λ/M

λ/MN

λ/M 1 2 3 M 1 2 3 M

Multiplexado por división de tiempo (TDM)Cada usuario puede enviar µ/N paquetes/seg yrecibirlos a una tasa de λ/N paquetes/seg

D = M / µ + M (λ / µ) (µ − λ ) M/M/1

Paquetes generados en tiempos aleatorios

λ/M λ Cola µ paquetes/segMultiplexadorestadístico

D = 1/ µ + ( λ / µ) Fórmula para

λ/M (µ − λ) M/M/1


2

Fórmula para

Conmutación de circuitos (tdm/fdm) frente a la de paquetes

Tiempo medio de servicio de paquetes(slots)

1

10

100

0 0.2 0.4 0.6 0.8 1

Carga de tráfico total; paquetes por slot

Tie

mp

o m

edio

de

serv

icio

TDM con 20 fuentes

Multiplexadoestadístico ideal(M/D/1)

Eytan ModianoDiapositiva 22

Sistemas de M servidores: M/M/m

cola

λ paquetes por segundo

Servidor

M servidores µ paquetes por segundo, por servidor

• La tasa de salida es proporcional al número de servidores utilizados

• Cadena de Markov similar:

λδ λδ λδ

m

λδ

m+1

λδ

0 1 2

1−λδ

µδ 2µδ 3µδ mµδ mµδ

Servidor


Colas M/M/m

λ P(n − 1) = nµ P(n) n ≤ m • Ecuaciones de equilibrio:

λ P(n − 1) = mµ P(n) n > m

P(0)( mρ )n / n! n ≤ m , ρ =

λ≤ 1P(n ) =

P(0)( mmρn ) / m! n > m mµ

• Resolver, una vez más, para P(0): m −1 (mρ) n ( mρ )m −1

P(0) = ∑ n =0 n!

+ m!(1− ρ)

n= ∞

PQ = ∑ P( n) = P(0)(mρ)m

n= m m!(1 − ρ)

n= ∞ n=∞ m + n ρNQ = ∑ nP(n + m) = ∑nP(0)(

mmρ ) = PQ (1 − ρ

) n=0 n =0 m!

W = N

λ Q , T = W + 1/ µ, N =λT =λ / µ + NQ


Aplicaciones de M/M/m

• Banco con m cajeros• Red con líneas de transmisión paralelas

m líneas de tasa µ cada unaUtilizar la

λNodo

A Nodo

B fórmula de M/M/m

VS . Una línea de tasa mµ Utilizar la

λNodo

A Nodo

B fórmula de M/M/1

• Cuando el sistema está ligeramente cargado, PQ~0 y el servidor único es m

• Cuando el sistema está muy cargado, predomina la espera en la cola y los sistemas permanecen más o menos igual


veces más rápido

M/M/Infinito

• Número ilimitado de servidores => los clientes no sufren retardo en cola• El número de clientes que hay en el sistema representa el número de

clientes que están siendo servidos en ese momento

λδ λδ λδ

n

λδ

n+1

λδ

0 1 2

1−λδ

µδ 2µδ 3µδ nµδ (n+1)µδ

λP(n − 1) = nµP(n), ∀n > 1, ⇒ P( n) = P(0)(λ / µ)n

n!

∞ −1 P(0) = [1 + ∑ n=1

(λ / µ)n / n!] = e−λ / µ

P(n ) = (λ / µ) n e− λ / µ / n! => ¡distribución de Poisson !

N = promedio del sistema =λ / µ, T = N / λ =1/ µ = tiempo de servicioEytan Modiano Diapositiva 26

Probabilidad de bloqueo

• Una red conmutada por circuitos se puede ver como un sistema de colas multiservidor:

– Las llamadas se bloquean cuando no hay servidores disponibles :

– Para las redes conmutadas por circuitos nos interesa la probabilidadde bloqueo de llamadas

• Sistema M/M/m/m:– m servidores => m circuitos – Las anteriores m indican que el sistema no puede sostener más de

• Fórmula B de Erlang:– Nos da la probabilidad que existe de que el usuario que inicia una llamada

– Vale para la distribución de las llamadas recibidas en general (aunquenosotros aquí demostremos sólo el supuesto de Markov)

PB = ∑

( m

λ / µ)m / m!

n= 0(λ / µ)n / n!


"señal de ocupado"

m usuarios

encuentre todos los circuitos ocupados

Sistema M/M/m/m: fórmula B de Erlang

λδ λδ λδ λδ

0 1 2

1−λδ

m

µδ 2µδ 3µδ mµδ

λP(n − 1) = nµP(n ), 1 ≤ n ≤ m, ⇒ P(n) = P(0)( λ / µ)n

n! −1m

P(0) = [∑n= 0(λ / µ)n / n!]

PB = P(bloqueo) = P(m) = ( m

λ / µ)m / m!

∑n= 0(λ / µ) n / n!


Fórmula B de Erlang

• La carga del sistema se suele expresar en Erlangs: – A= λ/µ = (tasa de llegada)*(durac. med. de llamadas) = carga media PB =

( mA)m / m!

– La fórmula se ve afectada por variaciones en la relación existente ∑n= 0( A)n / n!

• Se utiliza para calcular el tamaño de la línea de transmisión:– ¿Cuántos circuitos ha de soportar el satélite? – El número de circuitos es una función de la probabilidad de bloqueo que podemos tolerar:

Los sistemas están diseñados para unas predicciones de carga y probabilidades de bloqueo

• Ejemplo:– Tasa de llegada = 4 llamadas por minuto, promedio de 3 minutos por llamada => A = 12

– ¿Cuántos circuitos debemos preveer? Depende de la probabilidad de bloqueo que podamos tolerar

Circuitos PB 20 1% 15 8% 7 30%


determinadas (generalmente pequeñas)

entre λ y µ, no por sus respectivos valores

Cadenas multidimensionales de Markov

• K clases de clientes:– Clase j: tasa de llegada λ j; tasa de servicio µj

• Estado del sistema: n = (n1, n2… nk); nj = número de clientes de la clase j que hay en el sistema

• Si las ecuaciones de equilibrio detalladas valen para estados adyacentes, entonces existe una solución en forma de producto, en la que:

– P(n, n2… nk) = P 1(n1)*P2(n2)*…*Pk(nk)

• Ejemplo: K sistemas M/M/1 independientes

Pi (ni ) = ρini (1 − ρi ), ρi = λi / µi

• Esto también es aplicable a otras cadenas de nacimiento y muerte

– Ej.: M.M/m, M/M/Inf o M/M/m/m

Eytan Modiano Diapositivas 30

independientes

Truncación

• Elimina algunos de los estados:– Ej.: en las K colas M/M/1, elimina todos los estados en los que n1+n2+…+nk > K1 (constante)

• La cadena resultante debe ser irreducible:– Todos los estados se deben comunicar entre sí

Producto para la distribución estacionaria del sistema truncado

• Ej.: K colas M/M/1 independientes:

nK nKP(n1, n2 ,...nk ) =

ρ1 n1ρ2

n2....ρ K , G =∑ ρn1ρ2 n2....ρK1G n∈S

• Ej.: K colas M/M/inf independientes:

P(n1, n2 ,...nk ) = (ρ1

n1 / n1!)(ρ2 n2 / n2!)....(ρK nK / nk !)G

nK / nk !), G =∑(ρ1

n1 / n1!)(ρn2 / n2!)....(ρK2 n∈S

– G es una constante de normalización que convierte P(n) en una distribución – S es el conjunto de estados del sistema truncado


Ejemplo

• Dos clases de sesiones en un sistema conmutado por circuitos:– M canales de igual capacidad– Dos tipos de sesión:

Tipo 1: tasa de llegada λ1 y tasa de servicio µ1 Tipo 2: tasa de llegada λ2 y tasa de servicio µ2

• El sistema puede soportar hasta M sesiones de cada clase:– Si µ1= µ2, tratar el sistema como una cola M/M/m/m con una tasa de llegada de λ1+ λ2 – Cuando µ1!= µ2 es necesario saber el número de llamadas en curso de cada tipo

– Dos estados de la cadena de Markov dimensional = (n1, n2) – Se quiere que P(n1, n2): n1+n2 <=m

• Se pueden considerar como colas M/M/Inf truncadas:– Obsérvese que las tasas de transición en la cola M/M/Inf son iguales a las de la

cola M/M/m/m truncada

i = m j = m −i

P(n1, n2 ) = (ρ1

n1 / n1!)(ρ2 n2 / n2!) , G = ∑ ∑(ρi / i!)(ρ2

j / j!), n1+ n2≤ m1G i =0 j =0

– Obsérvese que la doble suma contabiliza sólo los estados para los que j+i <= m Eytan Modiano Diapositiva 32

de sesión

La propiedad PASTA (Poisson Arrivals See Time Averages)

• El estado de una cola M/M/1 es el número de clientes que hay en el sistema

• Los sistemas de colas más generales tienen un estado más general que puede incluir la cantidad de servicio que ha recibido ya cada cliente

• En las llegadas de Poisson, las llegadas en cualquier futuro incremento detiempo son independientes de las producidas en pasados incrementos y, para muchos sistemas de interés, independientes del estado actual S(t) (verdadero

• Para estos sistemas, P{S(t)=s|A(t+δ)-A(t)=1} = P{S(t)=s} – (donde A(t)= número de llegadas desde t=0)

• En el estado estacionario, las llegadas siguen las probabilidades del estado


para M/M/1, M/M/m y M/G/1)

estacionario

Distribución de ocupación en la llegada

• Las llegadas pueden no seguir siempre los promedios del estado

• Ejemplo: – Llegadas deterministas: 1 por segundo– Tiempo de servicio determinista de 3/4 de segundo

λ = 1 paquete/segundo T = 3/4 de segundo (sin cola)

N = λT = ocupación media = 3/4

• Sin embargo, obsérvese que una llegada siempre encuentra


estacionario

el sistema desocupado (vacío)

Ocupación en la llegada para una cola M/M/1

an = Lím t-> inf (P (N(t) = n | se produjo una llegada justo después del tiempo t)) Pn = Lím t-> inf (P(N(t) = n))

En los sistemas M/M/1 an = Pn

Demostración: supongamos que A(t, t+δ) es el evento y que la llegada tuvo lugar

an (t) = Lím t-> inf (P (N(t) = n| A(t, t+δ) ) = Lím t-> inf (P (N(t) = n, A(t, t+δ) )/P(A(t, t+δ) ) = Lím t-> inf P(A(t, t+δ)| N(t) = n)P(N(t) = n)/P(A(t, t+δ) )

• Dado que las futuras llegadas son independientes del estado del sistema:

P(A(t, t+δ)| N(t) = n)= P(A(t, t+δ))

• De este modo, an (t) = P(N(t) = n) = Pn(t)

• Calculando los límites cuando t tiende a infinito, obtendremos que: an = Pn

• Este resultado vale también para los sistemas M/G/1 Eytan Modiano Diapositiva 35

entre t y t+δ

Documents

Temas 5 y 6 6.263/16.37 Introducción a la teoría de colas