Capítulo 14 Redes de filas de espera



Descargar 155.15 Kb.
Página3/6
Fecha de conversión10.01.2017
Tamaño155.15 Kb.
1   2   3   4   5   6

14.4 Redes de puesta en fila de una sola cadena


Se examinarán principalmente las probabilidades de estado definidas por
p(i1, i2; . . . , ik, . . . , iK), donde ik es la cantidad de clientes en el nodo k (1  k K). Cuando se trata de sistemas abiertos, las operaciones son más sencillas de efectuar. Se resuelve primero la ecuación (14.5) de equilibrio de flujo y se obtiene la intensidad de llegada agregada a cada nodo (k). Mediante la combinación de las intensidades de llegada con la distribución del tiempo de servicio (k) se obtiene el tráfico ofrecido Ak en cada nodo y entonces, considerando el sistema de espera de Erlang, se obtienen las probabilidades de estado para cada nodo.

14.4.1 Algoritmo de convolución para una red de puesta en fila cerrada


Cuando se tratan redes de puesta en fila cerradas las operaciones son mucho más complicadas. En este caso, solo se conoce la carga relativa en cada nodo y no la carga absoluta, es decir, se conoce c . j, pero no se conoce c. Se pueden obtener probabilidades de estado relativas no normalizadas. Por último, se obtiene la normalización de las probabilidades de estado. Lamentablemente, normalización implica que se deben sumar todas las probabilidades de estado, es decir se debe calcular cada una de las probabilidades de estado (no normalizadas). El número de estados aumenta rápidamente cuando se incrementa el número de nodos y/o clientes. En general, la complejidad es similar a la correspondiente a sistemas de pérdidas multidimensionales (véase el Capítulo 10).

Se puede mostrar ahora cómo se puede aplicar el algoritmo de convolución a las redes de puesta en fila. El mecanismo de la operación corresponde al algoritmo de convolución para sistemas con pérdidas (véase el Capítulo 10). Se considera una red de puesta en fila con K nodos y una sola cadena con S clientes. Se supone que los sistemas de puesta en fila en cada nodo son simétricos (véase el § 14.2). El algoritmo tiene tres pasos:

Paso 1. Sea la intensidad de llegada a un nodo arbitrario igual a uno y se obtiene entonces las intensidades relativas restantes k. Mediante la resolución de la ecuación (14.5) de equilibrio de flujo para la red cerrada se obtiene las velocidades de llegada relativas (k1  k K) para cada nodo. Por último, se obtiene el tráfico ofrecido relativo k = k/k.

Paso 2. Considérese cada nodo como si estuviera aislado y tuviera el tráfico ofrecido k (1  k K). Dependiendo del sistema de puesta en fila simétrico real en el nodo k, se extraen las probabilidades de estado relativas qk(i) en el nodo k. El espacio de estado estará limitado por la cantidad total de clientes S, es decir 0  i S.

Paso 3. Repliéguese recurrentemente las probabilidades de estado para cada nodo. Por ejemplo, para los primeros dos nodos se tienen:

donde:


Cuando todos los nodos han sido replegados se obtiene:



En razón que la cantidad total de clientes es fija (S) sólo existe en el sistema combinado el estado q1,2. . . ,K(S) y, por tanto, este macroestado debe tener la probabilidad uno. Se pueden entonces normalizar todas las probabilidades de microestado.

Cuando se efectúa la última convolución se pueden obtener las medidas de calidad de funcionamiento para el último nodo. Variando el orden de convolución de los nodos se pueden obtener las medidas de calidad de funcionamiento de todos ellos.


Figura 14.5Modelo máquina – Reparador como redes de puesta en fila cerradas con dos nodos. Los terminales corresponden a un nodo IS, en razón que las
operaciones encuentran siempre un terminal en reposo,
mientras que la CPU corresponde a un nodo M/M/1


Ejemplo 14.4.1: Modelo máquina – Reparador de Palm

Se examinará ahora el modelo máquina – reparador de Palm introducido en el § 12.5 como red de fila de espera cerrada (véase la figura 14.5). Hay S clientes y terminales. El tiempo de activación medio es 1-1 y el tiempo de servicio medio en la CPU que es 2-1. En la terminología de redes de fila de espera hay dos nodos: En el nodo 1 están los terminales, es decir un sistema M/G/ (en realidad es un sistema M/G/S, pero en razón que la cantidad de clientes se limita a S, corresponde a un sistema M/G/), y el nodo 2 es la CPU, es decir un sistema M/M/1 con intensidad de servicio 2.

Los flujos a los nodos son iguales (1 = 2) y la carga relativa en el nodo 1 y nodo 2 son

1 = /1 y 2 = /2,

respectivamente. Si se considera cada nodo por separado se obtienen las probabilidades de estado de cada uno de ellos, q1(i) y q2(j), y por convolución de q1(i) y q2(j) se obtiene q12(x), (0  x S), como se muestra en el cuadro 14.1. El último término con S clientes (probabilidad no normalizada) q12(S) está compuesto por:

Por simple transposición resulta:



donde


La probabilidad de que todos los terminales estén "activados" se identifica con el ultimo término (normalizado por la suma) (S terminales en el nodo 1, cero terminales en el nodo 2):



que es la fórmula B de Erlang. Así, el resultado está de acuerdo con el obtenido en el § 12.5. Se observa que aparece con la misma potencia en todos los términos de q1,2(S) y así corresponde a una constante que desaparece cuando se normaliza.



Cuadro 14.1  Algoritmo de convolución aplicado al modelo máquina – Reparador
de Palm. El nodo 1 es un sistema IS mientras que el nodo 2 es un
sistema M/M/1 (véase el ejemplo 14.4.1)


Estado

i

Nodo 1

q1(i)

Nodo 2

q2(i)

Red de puesta en fila

q12 = q1 * q2










Ejemplo 14.4.2: Servidor central

En 1971 J.P. Buzen introdujo el modelo de servidor central que se ilustra en la figura 14.6 para modelar un sistema informático multiprogramado con una CPU y un número de canales de entrada/salida (unidades periféricas). El grado de multiprogramación S describe la cantidad de operaciones procesadas simultáneamente. El número de unidades periféricas se representa por K 1 como se muestra en la figura 14.6, que también indica las probabilidades de transición.

Típicamente una operación requiere servicios cientos de veces, ya sea por la unidad central o bien por uno de los periféricos. Se supone que la operación una vez finalizada es inmediatamente remplazada por otra; por tanto S es constante. Los tiempos de servicios están todos distribuidos exponencialmente con intensidad i (i = 1, . . . ,K).

Buzen formuló un esquema para evaluar este sistema. El esquema es un caso especial del algoritmo de convolución. Sea un caso con S = 4 clientes y K = 3 nodos, y:






Figura 14.6 – Sistema de puesta en fila de servidor central constituido por un
servidor central (CPU) y (K1) canales de entrada/salida. En el sistema
circula un número fijo de operaciones S

Leyendas de la figura 14.6

1) S operaciones de circulación

2) Nuevas operaciones

3) Canales entrada/salida

Las cargas relativas resultan:



Si se aplica el algoritmo de convolución se obtienen los resultados que figuran en el cuadro 14.2. El término q123(4) está compuesto por:



El nodo 3 sirve a los clientes en todos los estados con excepción del estado q3(0) . q12(4) = 5. La utilización del nodo 3 es por tanto a3 = 52/57. Basado en las cargas relativas se obtienen ahora las cargas exactas:



El promedio del número de clientes en el nodo 3 es:



Cambiando el orden de convolución se obtiene el promedio de longitudes de fila de espera L1 y L2 y concluye con:





Cuadro 14.2 – Algoritmo de convolución aplicado al
sistema del servidor central


Estado

Nodo 1

Nodo 2

Nodo 1*2

Nodo 3

Red de puesta en fila

i

q1(i)

q2(i)

q12 = q1 * q2

q3

q123 = (q1 * q2) * q3

0

1

2



3

4


1

1

1



1

1


1

1

1



1

1


1

2

3



4

5


1

2

4



8

16


1

4

11



26

57

La suma de todos los promedios de longitudes de filas de espera es, por supuesto, igual al número de clientes S. Se debe señalar que en redes de puesta en fila se define la longitud de la fila de espera como la cantidad total de clientes en el nodo, incluidos los que están recibiendo un servicio. De los tiempos medios de servicio y de utilización se obtiene el promedio de número de clientes que concluyen el servicio por unidad de tiempo en cada nodo:

Aplicando el resultado de Little se obtiene finalmente el tiempo medio de estado: Wk Lk /k:




14.4.2 Algoritmo de valor medio


El algoritmo de valor medio (MVA, mean value algorithm) es un mecanismo para calcular medidas de calidad de funcionamiento de redes de puesta en fila de espera. Combina de excelente manera dos resultados principales de la teoría de puesta en fila de espera: el teorema de llegada (§ 8.28) y la ley de Little (§ 5.20). El algoritmo fue publicado por primera vez por Lavenberg y Reiser (1980 [73]).

En el mismo se considera una red de puesta en fila con K nodos y S clientes (todos pertenecientes a una sola cadena). Las cargas relativas de los nodos se simbolizan por k (k = 1, 2, . . . ,K). El algoritmo es recurrente en el número de clientes, es decir, una red con x clientes se evalúa a partir de una red con x1 clientes.

Supóngase que el promedio de la cantidad de clientes en el nodo k es Lk(x) donde x es el número de clientes total en la red. Obviamente:

El algoritmo actúa recurrentemente en dos pasos:



Paso 1:

Aumentar el número de clientes de x a (x + 1). Conforme al teorema de llegada, el


(x + 1)-ésimo cliente verá el sistema como si éste tuviera x clientes en equilibrio estadístico. Por tanto, el promedio de tiempo de ocupación (tiempo de espera, + tiempo en servicio) en el nodo k es:

• Para M/M/1, M/G/1PS, M/G/1, y LCFSPR:



• para M/G/:



donde sk es el promedio del tiempo de servicio en el nodo k que tiene nk servidores. En razón que solo se calcula el tiempo medio de espera, se puede suponer el criterio de fila de espera FCFS.



Paso 2:

Se aplica la ley de Little (L = .W), que es válida para todos los sistemas en equilibrio estadístico. Para el nodo k se tiene Lk = k . Wk, donde k es la velocidad de llegada relativa al nodo k. Se tiene



La constante c se obtiene del número total de clientes:



Mediante estos dos pasos se ha efectuado la recursión de x a (x + 1) clientes. Para x = 1 no habrá tiempo de espera en el sistema y Wk(1) es igual al promedio del tiempo de servicio sk.

El algoritmo MVA se indica a continuación para nodos de un solo servidor, pero es bastante sencillo generalizarlo a nodos con criterios de múltiples servidores, o bien infinitos servidores.

Ejemplo 14.4.3: Modelo de servidor central

Se aplica el algoritmo MVA al modelo de servidor central (véase el ejemplo 14.4.2). Las velocidades de llegada relativa son:









Nodo 1

Nodo 2

Nodo 3
































Naturalmente, el resultado es idéntico al obtenido con el algoritmo de convolución. El tiempo de permanencia en cada nodo (utilizando la unidad de tiempo original) es el siguiente:



W1(4) = 1,6154 . 28 = 45,23,

W2(4) = 1,6154 . 40 = 64,62,

W3(4) = 2,7693 . 280 = 775,38,

Ejemplo 14.4.4: Algoritmo MVA aplicado al modelo máquina - reparador

Se examina el modelo máquina - reparación con S fuentes, tiempo de activación del terminal A y tiempo de servicioCPU igual a una unidad de tiempo. Como se indicó en el § 12.5.2 esto es equivalente a un sistema de pérdidas de Erlang con S servidores y tráfico ofrecido A. Es también una red de puesta en fila cerrada con dos nodos y S clientes en una cadena. Si se aplica el algoritmo MVA a este sistema se obtendrá entonces la fórmula de recursión para la fórmula B de Erlang (véase el § 7.27). Las velocidades de visita relativa son idénticas, pues un cliente visita alternativamente el nodo 1 y el nodo 2: 1 = 2 = 1.







Nodo 1

Nodo 2












Se sabe que la longitud de la fila de espera en los terminales (nodo 1) es igual al tráfico transportado en el sistema B de Erlang equivalente y que todos los otros clientes se quedan en la CPU (nodo 2). Así tenemos en general:







Nodo 1

Nodo 2






De esto se obtiene la constante de normalización c = 1  Ex(A) y se calcula para el (x+1)-ésimo cliente:



pues se sabe que c = 1- Ex+1. Esta es la formula de recursión para la fórmula B de Erlang.


1   2   3   4   5   6


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

    Página principal