Upload
ikhristian-apple
View
227
Download
2
Embed Size (px)
DESCRIPTION
Capitulo 5
Citation preview
126
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
CAPÍTULO 5. SISTEMAS DE PÉRDIDAS
Lección 21: Sistemas de espera
Esta sección se estudia el tráfico hacia un sistema con n servidores idénticos, accesibilidad
completa, y un número infinito de posiciones de espera. Cuando los n servidores están ocupados
en su totalidad, el cliente que llega se pone en cola de espera hasta que un servidor quede en
estado libre. Ningún cliente puede estar en cola de espera cuando hay un servidor está en estado
libre (accesibilidad completa).
Se consideran los dos mismos casos de tráfico que los Capítulos anteriores:
1. Proceso de llegada de Poisson (un número ilimitado de fuentes) y tiempos de servicios
distribuidos exponencialmente (PCT-I). Este es el sistema de asignación en cola más
importante, denominado sistema de espera de Erlang.
2. Un número limitado de fuentes de tráfico y tiempos de servicio con distribución exponencial
(PCT-II ).
21.1 Sistema de espera de Erlang M/M/n
Sea un sistema de asignación en cola M/M/n con proceso de llegada de Poisson (M), tiempos de
servicio exponenciales (M), n servidores y un número infinito de posiciones de espera. El estado
del sistema se define como el número total de clientes (estén servidos o puestos en cola). Se
examinarán las probabilidades en régimen permanente del sistema. Mediante el procedimiento
descrito anteriormente se construye el diagrama de transición de estado que se muestra en la
figura 12.1. Suponiendo equilibrio estático, las ecuaciones de corte dan por resultado:
Figura 12.1 − Diagrama de transición de estado del sistema de espera M/M/n que tiene n
servidores y un número ilimitado de posiciones de espera
127
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Como A = λ/μ es el tráfico ofrecido, se tiene:
Por normalización de las probabilidades de estado se obtiene p(0):
Los paréntesis internos tienen una progresión geométrica con el cociente A=n. La condición de
normalización sólo se puede satisfacer para:
A < n: (12.3)
El equilibrio estadístico solo se tiene para A < n. De otra manera, la cola de espera continuará
aumentando hasta el infinito. Se obtiene:
Las ecuaciones (12.2) y (12.4) calculan las probabilidades en régimen permanente.
128
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
21.2 Características del tráfico de sistemas de demora
Para evaluar la capacidad y rendimiento funcional del sistema, se deben examinar diversas
características, que estarán expresadas por las probabilidades en régimen permanente.
21.2.1 Fórmula de Erlang C
Cuando el proceso de llegada de Poisson es independiente del estado del sistema, la probabilidad
que un cliente de llegada arbitrario deba ponerse en cola de espera es igual a la proporción del
segmento de tiempo que todos los servidores estén ocupados (propiedad PASTA: Poisson arrivals
See Time Average - llegada de Poisson, véase promedio temporal).
El tiempo de espera es una variable estocástica por W. Para un cliente de llegada arbitrario se tiene:
Fórmula de Erlang C:
Esta probabilidad de espera depende sólo de A como producto de λ y s, y no de los parámetros λ
y s individualmente.
Esta fórmula tiene diversos nombres: fórmula de Erlang C, segunda fórmula de Erlang, o
fórmula de Erlang para sistemas de tiempo de espera. En los textos especializados presentan
las siguientes notaciones:
Como los clientes tienen la posibilidad de ser servidos inmediatamente o puestos en cola de
espera, la probabilidad que un cliente sea servido inmediatamente resulta:
El tráfico transportado Y equivale al tráfico ofrecido A, pues ningún cliente es rechazado y el
proceso de llegada es un proceso de Poisson.
129
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
donde se han aplicado las ecuaciones de compensación de corte.
La longitud de la cola de espera es una variable estocástica L. La probabilidad de tener clientes en
cola de espera en un punto aleatorio del tiempo es:
donde se ha aplicado la ecuación (12.5).
Evaluación numérica:
La ecuación es similar a la fórmula de Erlang B (7.9) salvo para el factor n/(n - A) en el último
término. Como se dispone de fórmulas recursivas muy exactas para la evaluación numérica de la
fórmula de Erlang B (7.27) se utilizará la siguiente relación para obtener valores numéricos de la
fórmula C.
Se observa que:
pues el término A {1 – E1,n(A)}/n es el promedio de tráfico transportado por canal en el sistema de
pérdidas correspondiente. Para A ≥ n, se tiene E2,n(A) = 1 pues es una probabilidad que todos los
clientes estén en espera.
La fórmula de Erlang C se puede expresar de manera apropiada por la fórmula B como fue observado por B-Sanders:
130
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
donde I es la probabilidad inversa (7.28):
La formula de Erlang C fue recogida en el principio de Moe (Jensen, 1950 [50]) y se muestra en la figura 12.2.
21.2.2 Longitudes media de asignación en cola
Se debe distinguir entre longitudes de asignación en cola en un punto arbitrario del tiempo y la
longitud de asignación en cola cuando hay clientes que esperan en la cola.
Longitud media de asignación en cola en un punto arbitrario del tiempo:
La longitud de asignación en cola L en un punto arbitrario del tiempo se denomina longitud virtual
de asignación en cola. Esta es la longitud de asignación en cola observada por un cliente arbitrario
pues la propiedad PASTA es válida al proceso de llegada de Poisson (promedio de tiempo =
promedio de llamadas). Se obtiene así la longitud media de asignación en cola Ln = E{L} en un
punto arbitrario del tiempo:
131
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Figura 12.2 − Fórmula de Erlang C para el sistema de espera M/M/n.
La probabilidad E2,n(A) para un tiempo de espera positivo se muestra en función del tráfico ofrecido
A para valores del número de servidores n. Mientras A/n ≤ c < 1, la serie es uniformemente
convergente, y el operador de diferenciación se puede expresar fuera de la suma:
La longitud de media de asignación en cola se puede interpretar como el tráfico transportado por
las posiciones de asignación en cola y, por tanto, también se denomina tráfico de tiempo de
espera.
Longitud media de asignación en cola dado una asignación en cola mayor que cero:
El promedio de tiempo es también, en este caso, igual al promedio de llamadas. La longitud de
asignación en cola media condicional resulta:
132
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Con la aplicación de las ecuaciones (12.8) y (12.12) este resultado es, por supuesto, el mismo que:
donde L es la variable estocástica para la longitudes de asignación en cola.
Lección 22: Tiempos de espera medios
Aquí también hay dos elementos de interés: el tiempo medio de espera W para todos los clientes y
el tiempo medio de espera w para clientes que experimentan un tiempo de espera positivo. El
primero es un indicador para el nivel de servicio de todo el sistema, mientras que el segundo es de
importancia para los clientes que se encuentran en cola de espera. Los promedios temporales
serán iguales a los promedios de llamadas en razón de la propiedad PASTA.
Tiempo medio de espera W para todos los clientes:
Indica que la longitud media de asignación en cola es igual a la intensidad de llegada multiplicada
por el tiempo de medio de espera, es decir:
donde Ln = Ln(A), y Wn = Wn(A). De la ecuación (12.12) se obtiene considerando el proceso de
llegada:
Como A = λs, donde s es el tiempo medio de servicio, se obtiene:
133
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Tiempo medio de espera w para clientes con demora:
El tiempo de espera total es constante y puede ser promediado con todos los clientes (Wn) o sólo
con clientes que experimentan tiempos de espera positivos (wn) (3.20):
Ejemplo 12.2.1: Sistema servidor de asignación en cola simple M/M/1. Este es el sistema que
aparece más frecuentemente en los textos. Las probabilidades de estado (véase 12.2) vienen
dada por una serie geométrica:
siendo p(0) = 1-A. La probabilidad de espera resulta:
La longitud media de asignación en cola Ln (12.12) y el tiempo medio de espera para todos los
clientes
Wn (12.15) se calculan con las siguientes expresiones:
De esto se observa que un aumento del tráfico ofrecido produce un aumento de Ln a la tercera
potencia independientemente si éste se debe a un número superior de clientes (λ) o a un tiempo
de servicio superior (s). El tiempo medio de servicio Wn aumenta a la tercera potencia de s, pero
sólo a la segunda potencia de λ. El tiempo medio de espera Wn para clientes en espera se
incrementa con la segunda potencia de s y la primera potencia de λ. Un aumento de la carga
debido a la mayor cantidad de clientes es así mejor que un incremento de la misma debido a
tiempos de servicios mayores. Por tanto, es importante que los tiempos de servicio de un sistema
no aumenten durante las sobrecargas.
22.1 Funciones de mejora para M/M/n
La mejora marginal del tráfico transportado cuando se agrega un servidor se puede expresar de
diversas maneras. La disminución en la proporción del tráfico total (es decir, la proporción de todos
los clientes) que experimenta demora viene dado por:
134
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
La disminución de las longitudes media de asignación en cola (es decir, el tráfico transportado por
las posiciones de espera) resulta, aplicando la ley de Little (12.14):
donde Wn(A) es el tiempo medio de espera para todos los clientes cuando el tráfico ofrecido es A y
el número de servidores es n (12.15). Las ecuaciones (12.21) y (12.22) están tabuladas en el
Principio de Moe (Jensen, 1950 [50]) y son simples de calcular con medios informáticos.
Lección 23: Principio de Moe para sistemas de espera
Moe fue el primero en establecer un principio para los sistemas de asignación en cola. Estudio los
tiempos de espera de los abonados como operador en centrales manuales de la compañía
telefónica de Copenhague.
Considérense k sistemas de asignación en cola independientes. Un cliente servido en todos los k
sistemas tiene el tiempo medio de espera total ∑i Wi, donde Wi es el tiempo medio de espera del i-
ésimo sistema que tiene ni servidores y que ofrece el tráfico Ai. El costo de un canal es Ci,
posiblemente más un costo constante, que se incluye en la constante Co indicada a continuación.
Así, el costo total para canales resulta:
Si el tiempo de espera también se considera como costo, el costo total que se ha de minimizar
resulta f = f(n1; n2, . . . , nk). Esto se debe minimizar en función del número de canales n1 en los
sistemas individuales. Si el tiempo medio de espera total es W, la atribución de canales a los
sistemas individuales se determina por:
donde ν (letra griega theta) es el multiplicador de Lagrange. Como ni es entero, condición
necesaria para el valor mínimo, que en este caso también se puede mostrar con una condición
suficiente, resulta:
135
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
que corresponde a:
donde Wni(Ai) viene dado por la ecuación (12.15). Expresado por la función mejora para el tiempo
de espera FW,n(A) (12.22) la solución óptima resulta:
La función FW,n(A) está tabulada según el principio de Moe (Jensen, 1950 [50]). Para otras
funciones de mejora se pueden efectuar optimizaciones similares.
Ejemplo 12.3.1: Sistema de espera. Se consideran dos sistemas de asignación en cola M/M/n el
primero tiene un tiempo medio de servicio de 100 s y el tráfico ofrecido es 20 erlang. La relación de
costo c1/ν es igual a 0,01. El segundo sistema tiene un sistema medio de servicio igual a 10 s y el
tráfico ofrecido es 2 erlang. La relación de costos es c2/ν = 0,1.
Una tabla de la función mejora FW,n(A) indica:
n1 = 32 canales y
n2 = 5 canales.
Los tiempos medios de espera son:
W1 = 0,075 s.
W2 = 0,199 s.
Esto muestra que un cliente, que está servido en ambos sistemas, experimenta un tiempo medio
de espera total igual a 0,274 s, y que el sistema con menos canales contribuye más al tiempo
medio de espera.
El costo de espera está referido a la relación de costos. Mediante la inversión de una unidad
monetaria más en el sistema anterior, se reducen los costos en la misma cantidad
independientemente de saber en qué sistema de asignación en cola se incrementa la inversión. Se
debe continuar invirtiendo en la medida que se obtengan ganancias. Las investigaciones de Moe
durante el decenio de 1920 demostraron que el tiempo medio de espera de los abonados en
pequeñas centrales con pocos operadores sería mayor que el tiempo medio de espera en
centrales más grande con muchos operadores.
136
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
23.1 Distribución del tiempo medio de espera para M/M/n, FCFS
Los sistemas de asignación en cola, donde la disciplina de servicio sólo depende de los tiempos de
llegada, tienen todos los mismos tiempos medios de espera. En este caso la estrategia sólo tiene
influencia frente a la distribución de los tiempos de espera para el cliente individual. La derivación
de la distribución del tiempo de espera es simple en el caso de cola de espera ordenada, FCFS
(primero en llegar, primero en estar servido). Esta disciplina también se denomina FIFO (primero
en llegar, primero en salir). Los clientes que llegan primero al sistema serán servidos primero, pero
si hay servidores múltiples no pueden necesariamente dejar el primer servidor. De modo tal que
FIFO se refiere al tiempo de salir de la cola de espera e iniciar el servicio.
Sea un cliente arbitrario. A su llegada al sistema, el cliente es servido inmediatamente o se pone
en cola de espera (12.6).
Se supone ahora que el cliente considerado debe esperar en la cola, es decir el sistema puede
estar en estado [n+ k], (k = 0, 1, 2, . . .), donde k es el número de posiciones de espera ocupadas
en el momento de la llegada del cliente.
El cliente considerado debe esperar hasta los clientes que k + 1 hayan completado su servicio
antes que un servidor en estado libre sea accesible. Cuando todos los n servidores están
funcionando, el sistema completa los clientes con una intensidad constante nμ, es decir el proceso
de salida es un proceso de Poisson con esta intensidad.
Se aprovecha la relación entre la representación de número y la representación de intervalo (5.4):
La probabilidad p{W ≤ t} = F(t) de experimentar un tiempo de espera positivo igual o menor a t es
igual a la probabilidad que en un proceso de llegada de Poisson con intensidad (nμ) lleguen al
menos (k+1) clientes durante el intervalo t (6.1):
F(t | k de espera)= (12.28)
La expresión anterior está basada en la hipótesis que el cliente considerado debe esperar en la
cola. La probabilidad condicional que el cliente considerado cuando llega observa todos los n
servidores ocupados y k clientes en espera (k = 0, 1, 2; . . . ) es:
Esta es una distribución geométrica que incluye la clase cero (véase el cuadro 6.1). La distribución
137
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
del tiempo de espera incondicional resulta entonces:
pues se pueden intercambiar las dos sumas cuando todos los términos son probabilidades
positivas. La suma interior es una progresión geométrica:
Aplicando esto se obtiene:
es decir, una distribución exponencial.
Aparentemente se tiene una paradoja: cuando se llega a un sistema con todos los servidores ocupados se puede:
1) Contar el número k de clientes en espera que están delante. El tiempo de espera total tendrá
entonces distribución de Erlang (k+1).
2) Hacer caso omiso. El tiempo de espera resulta entonces distribuido exponencialmente. La
138
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
interpretación de esto es que una suma ponderada de distribuciones de Erlang con factores
ponderados distribuidos geométricamente es equivalente a una distribución exponencial. En la
figura 12.3 se muestra el diagrama de fase para la ecuación (12.30), y se observa
inmediatamente que puede ser reducido a una distribución exponencial simple (véase la figura
4.9). La ecuación (12.31) confirma que el tiempo medio de espera wn para los clientes que
deben ponerse en cola de espera se torna como se indica en la ecuación (12.17).
La distribución del tiempo de espera para todos(un cliente arbitrario) resulta (3.19):
y el valor medio de esta distribución es Wn conforme a la ecuación (12.15). Los resultados se pueden calcular de un modo más simple por medio de funciones de generación.
Figure 12.3 − La distribución del tiempo de espera para M/M/n - FCFS resulta distribuida
exponencialmente con la intensidad (nμ-λ).
El diagrama de fase a la izquierda corresponde a una suma ponderada de distribuciones Erlang-k
pues el régimen de todas las fases es (1-A/n) = nμ-λ
23.2 Tiempo de respuesta con un solo servidor
Cuando sólo hay un servidor, las probabilidades de estado (12.2) vienen dadas por una serie
geométrica (12.18), es decir p(i) = p(0) . Ai para todas las i ≥ 0. Cada cliente emplea un intervalo de
tiempo distribuido exponencialmente con intensidad μ en cualquier estado. El cliente que encuentra
el sistema en el estado [i] permanecerá en el sistema un intervalo de tiempo con distribución
Erlang- (i + 1). Por tanto, el tiempo de permanencia total en el sistema (tiempo de espera + tiempo
de servicio), es decir el tiempo de respuesta, está distribuido en forma exponencial con la
intensidad (μ-λ) (véase la figura 4.9):
Esta expresión es idéntica a la distribución del tiempo de espera de cliente con demora.
139
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Lección 24: Sistemas terminales
La división de tiempo es una ayuda para ofrecer un servicio óptimo a un considerable grupo de
clientes utilizando, por ejemplo, terminales conectados a una unidad de procesamiento central.
Cada usuario se debe sentir como si fuera el único del sistema informático (véase la figura 12.5)
Figure 12.5 − Un sistema informático con S terminales (sistema interactivo) corresponde a
un sistema de tiempo de espera con un número de fuentes limitado (véase el caso Engset
para el caso de sistemas de pérdidas)
El terminal individual varía todo el tiempo entre dos estados (interactivo) (véase la figura 12.6):
el usuario está pensando (trabajando), o
el usuario está esperando (una respuesta de la computadora).
El intervalo de tiempo cuando el usuario está pensando (trabajando) se denomina tiempo entre
llegadas Tt, y el valor medio se simboliza mt.
El intervalo de tiempo cuando el usuario está esperando la respuesta de la computadora, se
denomina tiempo de respuesta R. Esto incluye el intervalo de tiempo Tw(valor medio mw), donde la
tarea está esperando obtener el acceso a la computadora, y el propio tiempo de servicio Ts (valor
medio ms).
Tt + R se denomina tiempo de circulación (véase la figura 12.6). Al término de este intervalo de
tiempo un terminal retorna al mismo estado que se dejó al comienzo del intervalo (evento
recurrente).
140
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Figura 12.6 − Los terminales puede tener tres estados.
El usuario trabaja activamente en el terminal o bien está a la espera de la respuesta de la
computadora. El último intervalo de tiempo (tiempo de respuesta) se divide en dos fases. Una fase
de espera y una fase de servicio
Ejemplo 12.5.1: Sistema de información. Considérese un sistema de información que esté
organizado de la siguiente manera: toda la información se mantiene en seis discos que se
conectan al mismo terminal de datos entrada/salida, un canal multiplexor. El tiempo de búsqueda
medio (colocación del elemento de búsqueda) es de 3 ms y el tiempo medio de espera para
localizar el archivo es 1 ms que corresponde a un tiempo de rotación de 2 ms. El tiempo de lectura
de un archivo está distribuido exponencialmente con el valor medio 0,8 ms. El almacenamiento de
disco se basa en la detección de la ubicación rotacional, de modo tal que el canal está ocupado
sólo durante la lectura. Se desea determinar la máxima capacidad del sistema (número de pedidos
por segundos).
El tiempo en estado activo es 4 ms y el tiempo de servicio es 9,8 ms. La relación de servicio resulta así 5, y mediante la fórmula B de Erlang se obtiene el valor siguiente.
Esto corresponde a γmáx= 0,8082/0,0008 = 1 010 pedidos por segundo.
24.1 Estados de los terminales y características del tráfico
Las medidas de rendimiento funcional se obtienen fácilmente a partir de la analogía con el sistema
de pérdidas clásico de Erlang. La computadora funciona con la probabilidad (1 - p(0)). Se tiene
entonces que el número medio de terminales que está servido viene dado por:
El número medio de terminales en estado activo corresponde al tráfico transportado en el sistema de pérdida de Erlang:
141
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
El número medio de terminales en espera resulta:
Si se considera un terminal aleatorio en un punto arbitrario en el tiempo se tiene:
p {terminal servido} = (12.41)
p {terminal en estado activo} = (12.42)
p {terminal en espera} = (12.43)
Aplicando el teorema de Little W = λW a los terminales, a las posiciones en espera y a la
computadora, respectivamente, se obtiene (λ es la velocidad de circulación del tráfico):
o
Empleando las ecuaciones (12.38) y (12.44) se obtiene:
De esta manera el tiempo de respuesta es independiente de las distribuciones del tiempo pues
está basado en las ecuaciones (12.38) y (12.44) (Ley de Little). Sin embargo, p(0) dependerá de
los tipos de distribución al igual que en la fórmula de Erlang B. Si el tiempo de servicio de la
computadora tiene distribución exponencial (valor medio ms = 1/μ), entonces p(0) viene dado por la
ecuación (12.37). En la figura 12.8 se muestra el tiempo de respuesta en función del número de
terminales en este caso.
142
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Figura 12.8 − Tiempo de respuesta medio en función del número de terminales.
El factor de servicio es ρ = 30. El tiempo de respuesta converge a una línea recta, cortando el eje x
en S = 30 terminales. La curva se calcula utilizando la fórmula de Erlang B
Si todos los intervalos de tiempo son constantes, la computadora puede servir a K sin tiempo de espera donde:
K es, por tanto, un parámetro adecuado para describir el punto de saturación del sistema. El
tiempo de espera medio para un terminal arbitrario se obtiene empleando la ecuación (12.45):
mv= R − ms
Ejemplo 12.5.2: Computadora de compartición en el tiempo. En un sistema terminal la
computadora queda a veces en reposo, (a la espera de terminales) y a veces los terminales
esperan que la computadora quede libre. Pocos terminales producen baja utilización de la
computadora, mientras que muchos terminales conectados consumen el tiempo de los usuarios.
En la figura 12.9 se muestra el tráfico de tiempo de espera en erlang, para la computadora y para
un terminal simple. El costo total del tiempo de espera se obtiene mediante la ponderación
143
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
apropiada de costos y sumas de tiempos de espera de la computadora y de todos los terminales.
Para el ejemplo, en la figura 12.9 se obtienen los costos mínimos de la espera total para unos 45
terminales aun cuando el costo por el tiempo de espera correspondiente a la computadora es cien
veces mayor que el costo de un terminal. En 31 terminales, la computadora y cada uno de ellos
consume el 11,4% del tiempo de espera. La relación de costos es 31 y este será el número óptimo
de terminales. Sin embargo, hay otros factores que se han de tener en consideración.
Figura 12.9 − Tráfico en tiempo de espera (proporción del tiempo transcurrido durante la
espera) medido en erlang para la computadora y los terminales, respectivamente, en un
sistema de cola de espera interactivo (factor de servicio ρ = 30)
Lección 25: Aplicación de la Teoría de colas de espera
Hasta el momento, se han examinado sistemas clásicos de colas de espera, donde todos los
procesos de tráfico son procesos de renovación. La teoría de los sistemas de pérdidas se ha
aplicado con éxito durante muchos años en el campo de la telefonía, mientras que la teoría de los
144
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
sistemas de espera sólo se ha aplicado en los últimos años en el terreno de la ciencia informática.
Los clásicos sistemas de espera desempeñan una función primordial en la teoría de asignación en
cola de espera. Por lo general, se da por supuesto que la distribución del tiempo entre las llegadas
a destino de las llamadas o la distribución del tiempo de servicio son exponenciales. Por razones
teóricas y físicas, a menudo se utilizan sistemas de cola de espera con un solo servidor.
Este Capítulo se centra en la cola de un solo servidor y se analiza este sistema para distribuciones generales de tiempo de servicio, diferentes tipos de cola de espera y clientes con propiedades de atención preferentes.
25.1 Clasificación de modelos de colas de espera
En esta sección se introducirán notaciones compactas para sistemas de asignación en cola de espera, denominada notación de Kendall.
25.1.1 Descripción del tráfico y la estructura
D.G. Kendall (1951 [60]) introdujo la siguiente notación para modelos de asignación en cola de
espera:
A/B/n donde
A = proceso de llegada,
B = distribución del tiempo de servicio,
n = número de servidores.
Para procesos de tráfico se utilizan las siguientes notaciones normalizadas:
M ~ Markovian. Intervalo de tiempo exponencial (proceso de llegada de Poisson, tiempos
de servicios distribuidos exponencialmente).
D ~ Determinístico. Intervalos de tiempo constante.
Ek ~ Intervalos de tiempo con distribución de Erlang-k (E1 = M).
Hn ~ Hiperexponencial de intervalos de tiempo distribuidos de orden n.
Cox ~ Intervalos de tiempo distribuidos de Cox.
Ph ~ Intervalos de tiempo distribuidos de tipo fase.
GI ~ Intervalos de tiempo independiente general, renovación de proceso de llegada.
G ~ General. Distribución arbitraria de intervalo de tiempo (puede incluir correlación).
Ejemplo 13.1.1: Modelos comunes de asignación en cola. M/M/n es un sistema de espera puro
con proceso de llegada Poisson, tiempos de servicio de distribución exponencial y n servidores. Es
el clásico sistema de espera de Erlang.
GI/G/1 es un sistema de espera general con un solo servidor.
La notación indicada anteriormente es ampliamente utilizada en la literatura especializada. Para
145
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
obtener la especificación completa de un sistema de asignación en cola se requiere más
información:
A/B/n/K/S/X
donde:
K = es la capacidad total del sistema, alternativamente sólo el número de posiciones de espera,
S = es el tamaño de la población (número de clientes),
X = es el tipo de cola de espera (véase el § 13.1.2), K = n corresponde a un sistema de pérdidas, que a menudo se simboliza como A/B/n-pérdidas.
Un superíndice b sobre A, respectivamente B, indica llegada de grupo (llegada a granel, llegada de
lote), grupo de servicio, respectivamente. C (reloj) puede indicar que el sistema funciona en tiempo
discreto.
Generalmente se supone plena accesibilidad.
25.1.2 Estrategia de las colas de espera: tipos y organización
Los clientes puestos en cola de espera para ser atendidos son seleccionados conforme a diversos
principios. Se considerará primero los tres tipos clásicos de asignación en cola de espera:
FCFS, (first come - first served). Primero en llegar - primero en ser servido
Se denomina también cola de espera ordenada o cola de espera justa, y este tipo se prefiere a
menudo en la vida real cuando los clientes son seres humanos. También se denomina FIFO: (first
in - first out) primero en entrar - primero en salir. Se debe señalar que FIFO se refiere sólo a
cola de espera y no al sistema total. Si se tiene más de un servidor, un cliente con un tiempo de
servicio breve puede dar alcance a un cliente con un tiempo de espera mayor aun si tiene cola de
espera FIFO.
LCFS: (last come - first served). Último en llegar - primero en ser servido
Esto corresponde al principio de disposición apilada. Se utiliza por ejemplo en almacenamiento de
datos, en anaqueles de establecimientos comerciales y, en general, en memorias de retención
temporal. Esta técnica también se denomina LIFO: (last in - first out) último en entrar, primero
en salir.
SIRO: (service in random order). Servicio en orden aleatorio
Todos los clientes puestos en cola de espera tienen la misma probabilidad de ser escogidos para
tener el servicio. Esto también se denomina RANDOM o RS (random selection) selección
aleatoria.
Los dos primeros tipos de asignación en cola de espera sólo toman en consideración los tiempos
de llegada, mientras que el tercer tipo no considera ningún criterio y, por tanto, no requiere
ninguna memoria (contrariamente a los dos anteriores).
146
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
Los tres tipos detallados se pueden aplicar en sistemas técnicos simples. En una central telefónica
electromecánica se utiliza a menudo el tipo de cola de espera SIRO pues (casi) corresponde a
búsqueda secuencial sin reposición.
Para los tres tipos mencionados anteriormente el tiempo total de espera de todos los clientes es el
mismo. El tipo de asignación en cola sólo decide qué tiempo de espera se atribuye a cada uno de
los clientes. Esto se puede efectuar utilizando el tiempo de servicio como criterio. En un sistema de
cola de espera con control por programa habría disciplinas de cola de espera más complejas. En
general, en la teoría de cola de espera asumimos que el tráfico total ofrecido es independiente de
la disciplina de cola de espera.
En el caso de sistemas informáticos a menudo tendemos a reducir el tiempo total de espera.
SJF: (shortest job first). Tarea más breve primero, SJN: (shortest job next) tarea más corta
después, SPF: (shortest processing time first) tiempo de tratamiento más corto primero. Esta
técnica supone que se conoce el tiempo de servicio por adelantado y reduce al mínimo el
tiempo total de espera de todos los clientes.
Las técnicas mencionadas tienen en cuenta los tiempos de llegadas o los tiempos de servicio. Se
obtiene un compromiso entre esas disciplinas mediante las siguientes técnicas:
RR (round robin) Retorno al origen.
A un cliente servido se le da a lo sumo un tiempo de servicio fijo (segmento de tiempo). Si el
servicio no se completa durante ese intervalo el cliente vuelve a la cola de espera que es del
tipo FCFS.
PS (processor sharing) Compartición del procesador.
Todos los clientes comparten la capacidad del servicio en igual medida.
FB (foreground - background) Primer plano - segundo plano.
Esta técnica trata de aplicar el criterio SJF sin conocer de antemano los tiempos de servicio. El
servidor ofrecerá servicio al cliente que hasta ese momento ha recibido la menor cantidad de
servicio. Cuando todos los clientes han obtenido la misma cantidad de servicio, FB se hace
idéntico a PS.
Las últimas técnicas indicadas son dinámicas pues los criterios de asignación en cola de espera
dependen de la cantidad de tiempo empleado en la cola.
25.1.3 Prioridad de los clientes
En condiciones reales los clientes se dividen a menudo en N clases prioritarias, en la que un
cliente que pertenece a la clase p tiene mayor prioridad que un cliente que pertenece a la clase
p+1.
Se ha de distinguir entre dos tipos de prioridades:
147
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
No preferente = Cabecera de línea. Un nuevo cliente de llegada con prioridad más alta que está
siendo servido espera hasta que un servidor esté desocupado (y todos los clientes con alta
prioridad hayan sido servidos). Este criterio también se denomina HOL,(head-of-the-line) cabecera
de línea.
Preferente: Un cliente al que se está dando servicio tiene prioridad inferior que un nuevo cliente
que llega, es interrumpido.
Se distingue entre:
Reanudar preferencia: El servicio continúa desde donde fue interrumpido.
Preferencia sin remuestreo: El servicio se reinicia desde el comienzo con el mismo tiempo de
servicio.
Preferencia con remuestreo: El servicio se inicia nuevamente con un nuevo tiempo de
servicio.
La dos últimas técnicas se aplican, por ejemplo, en fabricación de sistemas y seguridad del
servicio.
En la literatura relativa a asignación de cola de espera aparecen muchas otras estrategias y
símbolos. Las siglas GD representan una disciplina de asignación en cola de espera arbitraria
(disciplina general). El comportamiento de los clientes también está sujeto a modelos:
Tentativa inconclusa: se refiere a sistemas de asignación en cola de espera en el que el
cliente con una probabilidad que depende de la cola puede desistir de permanecer en la misma.
Renuncia: se refiere a sistemas con clientes impacientes que salen de la cola de espera sin
haber sido servidos.
Cambio de cola: se refiere a los sistemas en el que los clientes pueden pasar de una cola de
espera (por ejemplo larga) a otra cola más corta.
Así, hay muchos modelos posibles. En este Capítulo sólo se tratarán los más importantes. Por lo
general, sólo se consideran sistemas con un servidor.
Ejemplo 13.1.2: Sistema de conmutación de programa almacenado controlado. En sistemas
de programa almacenado controlado las tareas de los procesadores se dividen, por ejemplo, en
diez clases de prioridades. La prioridad se actualiza, cada quinto de milisegundo. Los mensajes de
error que provienen de un procesador tienen la más alta prioridad, mientras que las tareas de
control de rutina tiene la prioridad más baja. Dar servicio a las llamadas aceptadas tiene mayor
prioridad que la detección de nuevas tentativas de llamada.
25.2 Resultados generales en la teoría de asignación en cola de espera
Como se indicó anteriormente hay muchos modelos de asignación en cola de espera pero,
lamentablemente, hay sólo algunos resultados generales en la teoría de asignación en cola. La
literatura es muy extensa pues muchos casos especiales son importantes en la práctica. En esta
148
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍAS E INGENIERÍAS CONTENIDO DIDÁCTICO DEL CURSO: 208022-TELETRAFICO
sección se examinarán los resultados generales más importantes.
El teorema de Little es el resultado más general que es válido para un sistema de asignación en
cola de espera arbitrario. El teorema es fácil de aplicar y muy útil en muchos casos.
En general, sólo los sistemas de asignación en cola con procesos de llegada de Poisson son
simples de abordar. Referente a sistemas de asignación en cola en serie y redes de cola de
espera (por ejemplo redes informáticas) es importante conocer casos en el que el proceso de
partida de un sistema de asignación en cola es un proceso de Poisson. Los sistemas de cola de
espera se denominan sistemas de asignación en cola de espera simétricos, pues son simétricos
en el tiempo, ya que el proceso de llegada y el proceso de salida son del mismo tipo. Si se filmara
el desarrollo del tiempo, no se podría decidir si la película pasa hacia adelante o hacia atrás (véase
reversibilidad) (Kelly, 1979 [59]).
Los modelos clásicos de asignación en cola desempeñan un papel principal en la teoría de cola de
espera, pues otros sistemas convergirán a menudo hacia ellos cuando el número de servidores
aumenta.
Los sistemas que más se apartan de los modelos clásicos son los que tienen un solo servidor. Sin
embargo, esos sistemas son los más simples de abordar.
En sistemas de tiempo de espera se distingue también entre promedios de llamadas y promedios
temporales. El tiempo de espera virtual es el tiempo que un cliente experimenta si llega a un punto
aleatorio del tiempo (promedio temporal). El tiempo de espera real es el tiempo que experimenta el
cliente real (promedio de llamada). Si el proceso de llegada es un proceso de Poisson los dos
promedios son entonces idénticos.