Probabilidades de estado y tiempos medios de espera: M/D/1



Descargar 332.61 Kb.
Página1/14
Fecha de conversión10.01.2017
Tamaño332.61 Kb.
  1   2   3   4   5   6   7   8   9   ...   14

- -

13.5.2 Probabilidades de estado y tiempos medios de espera: M/D/1


Con la hipótesis de equilibrio estadístico se calculan ahora las probabilidades para M/D/1 de manera simple. La intensidad de llegada se representa por  y el tiempo de ocupación constante por h. Como se considera un sistema de tiempo de espera puro con un solo servidor, se tiene:

Tráfico ofrecido = Tráfico transportado = λ · h < 1, (13.39)

es decir

pues en cada estado con excepción de cero el tráfico transportado es igual a un erlang.

Se consideran dos épocas (puntos en el tiempo) t y t +h a una distancia de h. Todo cliente que es servido en época t (no más de uno) ha dejado el servidor en época t +h. Los clientes que llegan durante el intervalo (t, t + h) están aún en el sistema de puesta en fila en época t +h (en espera o en servicio).

El proceso de llegada es un proceso de Poisson. Por tanto, para el intervalo de tiempo (t, t +h), se tiene



p (j, h) =p {j llamadas en h} = Poisson distribuido (13.40)

La probabilidad que en un determinado estado se encuentre en época t +h se obtiene del estado en época t teniendo en cuenta todas las llegadas y salidas durante (t; t +h). Mediante observación en esas épocas se obtiene una cadena Markov incorporada en el proceso de tráfico original (véase la figura 13.4).

Se obtiene las ecuaciones de estado de Fry para n = 1 (Fry, 1928 [32]):

Además, se obtuvo:



p(0) = 1 . A


Figura 13.4  Ilustración de las ecuaciones de estado de
Fry para el sistema de puesta en fila M/D/1

Leyendas de la figura 13.4

1) Estado

2) Llegadas en (t, t+h)

3) Llegada

4) Salida

5) Tiempo

y con la hipótesis de equilibrio estadístico pt(i) = pt+h(i), se halla sucesivamente:



y en general:



El último término correspondiente a j = i siempre equivale a eiA, pues (1)  . En principio p(0) también se puede obtener requiriendo que todas las probabilidades de estado se deben añadir a uno.


13.5.3 Tiempos medios de espera y periodo ocupado: M/D/1


Para un proceso de llegada de Poisson la probabilidad D de retardo experimentando es igual a la probabilidad de no estar en estado cero (propiedad PASTA):

D = A = 1  p(0) (13.43)



W representa el tiempo medio de espera para todos los clientes y w el tiempo medio de espera para los clientes que experimentan un tiempo de espera positivo.

Se tiene siempre (3.20):



(13.44)

donde para todos los valores de n (más adelante se verá n >1):





W y w se obtiene fácilmente considerando un periodo ocupado (véase la figura 13.1).

En la época (punto en el tiempo) en el que el sistema se pone vació, se dice que este perdió su memoria (punto de regeneración = punto de equilibrio), y el siguiente cliente llega conforme a un proceso de Poisson con intensidad  (véase el ejemplo 6.2.1).

Sólo es necesario considerar un ciclo desde una época en el que el sistema se pone en reposo hasta la siguiente época en que vuelve a tomar ese estado. El ciclo comprende un periodo de reposo de duración T0 y un periodo de ocupado de duración T1 (véase la figura 13.1).

La proporción de tiempo en que el sistema está ocupado resulta entonces (13.7):



Un periodo de ocupado se compone de un número de llamadas uniformemente distribuidas (proceso de ramificación) durante el periodo de ocupado. (Paradoja: nótese que no hay llegadas durante el último tiempo de servicio de un periodo de ocupado). En promedio estos clientes, que experimentan un tiempo de espera positivo > 0, tienen los siguientes tiempos medios de espera:



Estos resultados también se obtienen utilizando la fórmula de Pollaczek-Khintchine. La distribución del número de clientes que llegan durante un periodo de ocupado se puede demostrar que viene dado por una distribución de Borél:




13.5.4 Distribución del tiempo de espera: M/D/1, FCFS


Se puede obtener mediante la siguiente expresión:

donde h = 1 se toma como unidad de tiempo, t = T + , T es un entero, y 0   <1.





Figura 13.5  Distribución del tiempo complementario para todos los clientes en
el sistema de puesta en fila M/M/1 y M/D/1 para filas ordenadas (FCFS).
Unidad de tiempo = tiempo medio de servicio. Se señala que el tiempo
medio de servicio para M/D/1 es menor que para M/M/1

Leyendas de la figura 13.5

1) Distribución del tiempo de espera p(W > t)

El gráfico de la distribución del tiempo de espera presenta una irregularidad cada vez que el tiempo de espera supera un múltiplo entero del tiempo de ocupación constante. En la figura 13.5 se muestra un ejemplo. La fórmula (13.49) no es adecuada para la evaluación numérica. Puede mostrar (Iversen, 1982 [41]) que el tiempo de espera se puede expresar en forma cerrada, como fue señalado por Erlang in 1909:



que es apropiado para la evaluación numérica de pequeños tiempos de espera.

Para tiempos de espera más largo se utilizará, por lo general, sólo valores enteros de t. Se puede mostrar (Iversen, 1982 [41]) que para un valor entero de t se tiene

Las probabilidades de estado p(i) se calculan con mayor precisión utilizando una fórmula recursiva basada en las ecuaciones de estado de Fry (13.42):



Para tiempos de espera no enteros se puede expresar la distribución del tiempo de espera en términos de tiempos de espera enteros. Si se toma h = i, la ecuación (13.50) puede ser entonces un desarrollo binomial expresado en potencias de , donde:



t = T + τ, T entero, 0 ≤ τ < 1

Se obtiene entonces:



donde p {WT} viene dado por la ecuación (13.51).

La evaluación numérica es muy precisa cuando se utilizan las ecuaciones (13.51), (13.52) y (13.53).

13.5.5 Probabilidades de estado: M/D/n


Cuando se aplican las ecuaciones de estado de Fry (13.41) se obtienen más combinaciones:

Con la hipótesis de equilibrio estadístico (A <n) se puede hacer caso omiso de los puntos absolutos en el tiempo:



El sistema de ecuaciones (13.55) sólo se puede resolver por sustitución, si se conoce


p(0), p(1), . . .; p(n1). En la práctica, se pueden obtener valores numéricos suponiendo un conjunto aproximado de valores para p(0), p(1), . . ., p(n1), y luego sustituirlos en la fórmula de recursión (13.55) y obtener nuevos valores. Luego de algunas aproximaciones se obtienen los valores exactos.

La solución matemática explícita se obtiene mediante funciones generatrices (The Erlang book, páginas 81 a 83).


13.5.6 Distribución del tiempo de espera: M/D/n, FCFS


La distribución del tiempo de espera viene dada por la distribución de Crommelin:

donde A es el tráfico ofrecido y



La fórmula (13.56) se puede expresar en forma cerrada a semejanza de la ecuación (13.50):



Para valores enteros del tiempo de espera t se tiene:



El tiempo medio de espera exacto de todos los clientes W es difícil de calcular. Se puede obtener una aproximación por medio de la expresión de Molina:



Para tiempos de espera no enteros t = T + , T entero, 0  < 1, se puede expresar la distribución del tiempo de espera en términos de tiempos de espera enteros en cuanto a M/D/1:



donde k = n(T + 1)1 y p(i) es la probabilidad de estado (13.55).


13.5.7 Proceso de llegada de Erlang-k: Ek/D/r


Sea un sistema de puesta en fila de espera con n = r . k (siendo r y k valores enteros), proceso general de llegada GI, tiempo de servicio constante y criterio de puesta en fila ordenada (FCFS). Los clientes que llegan durante periodos de reposo buscan servidores en orden cíclico

1; 2, . . ., n  1, n,1, 2, . . .

Un determinado servidor dará servicio entonces a los n-ésimos clientes, pues los clientes debido al tiempo de servicio constante dejan los servidores en el mismo orden en que llegaron a los mismos. Ningún cliente puede superar a otro cliente.

Un grupo de servidores constituidos por:



X, x + k, x + 2 . k, . . ., x + (r  1) . k, 0 < xk (13.62)

darán servicio al k-ésimo cliente. Si se consideran los servidores conforme a la agrupación (13.62), se estudian entonces como un solo grupo equivalente al sistema de puesta en fila GIk*/D/r, donde el proceso de llegada GIk* es una convolución de k veces la distribución del tiempo de llegada.

Lo mismo sucede para los otros sistemas k  1. El tráfico en estos sistemas k está mutuamente correlacionado, pero si sólo se considera un sistema por vez, este es entonces un proceso de llegada GIk*/D/n, sistema de puesta en fila FCFS.

La hipótesis de búsqueda cíclica de los servidores no es necesaria con los sistemas individuales (13.62). Las probabilidades de estado, tiempos medios de espera, etc. son independientes del criterio de puesta en fila, que tiene importancia sólo para la distribución del tiempo de espera.

Si el proceso de llegada GI fuera un proceso de Poisson, GIk* resulta entonces un proceso de llegada Erlang-k. Se encuentra así que los siguientes sistemas son equivalentes con respecto a la distribución del tiempo de espera:

M/D/r · k, FCFS ≡ Ek/D/r, FCFS

por tanto, Ek/D/r se puede obtener mediante tablas para M/D/n.



Ejemplo 13.5.1: Procesos de llegada regulares

En general, se sabe que para un determinado tráfico por servidor el tiempo medio de espera disminuye cuando aumenta el número de servidores (economía de escala, convexidad). Por la misma razón, el tiempo medio de espera disminuye cuando el proceso de llegada se hace más

regular. Esto se puede ver directamente de la equivalencia anterior, donde el proceso de llegada para Ek/D/r se hace más regular para incrementos de k (siendo r constante). Para A = 0,9 erlang por servidor (L = longitud media de fila de espera) se tiene:

E4/E1/2: L = 4,5174,

E4/E2/2: L = 2,6607,

E4/E3/2: L = 2,0493,

E4/D/2: L = 0,8100.

13.5.8 Sistema de puesta en fila finito: M/D/1/k


En sistemas reales siempre se tiene una fila de espera finita. En sistemas informáticos la capacidad de almacenamiento es finita y en sistemas ATM hay memorias intermedias finitas. Lo mismo se aplica para posiciones de espera en sistemas de fabricación flexibles FMS, flexible manufacturing systems). En un sistema con un solo servidor y (k 1) posiciones de fila de espera se tienen (k +1) estados (0, 1, . . . , k).

Las ecuaciones de equilibrio para los estados 0, 1, . . ., k 2 se pueden aplicar del mismo modo que las ecuaciones de estado de Fry, pero no es posible formular ecuaciones simples independientes del tiempo para los estados k 1 y k. Pero las primeras ecuaciones (k 2) (13.53) junto con el requisito de normalización



y el hecho que el tráfico ofrecido es igual al tráfico transportado más el tráfico rechazado (propiedad PASTA):



A = 1  p(0) + A . p(k)

dan por resultado (k +1) ecuaciones lineales independientes, que son sencillas de resolver numéricamente.

Se obtienen tiempos de espera enteros de las probabilidades de estado y tiempos de espera no enteros de los tiempos de espera enteros, como se indicó anteriormente.

Ejemplo 13.5.2: Cubo no estanco

El cubo no estanco es un mecanismo para controlar los procesos de llegada de células (paquetes) de un usuario (fuente de tráfico) en un sistema ATM. El mecanismo corresponde a un sistema de puesta en fila de espera con tiempo de servicio constante (dimensión de la célula) y una memoria intermedia finita. Si el proceso de llegada es un proceso de Poisson, se tendrá un sistema M/D/1/k. La magnitud de la fuga corresponde a la intensidad de llegada aceptable del promedio a largo plazo mientras que el tamaño del cubo describe el exceso (incremento repentino permitido). El mecanismo funciona como un sistema de puesta en fila virtual en el que las células se aceptan inmediatamente o bien son rechazadas conforme al valor de un contador que es el valor entero de la función de carga (véase la figura 13.2). En un contrato entre el usuario y la red se celebra un acuerdo sobre la magnitud de la "fuga" y la dimensión del "cubo". Sobre esta base la red puede garantizar una determinada calidad de servicio.


  1   2   3   4   5   6   7   8   9   ...   14


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal