Capítulo 14 Redes de filas de espera



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

14.3 Teorema de Jackson


En 1957, Jackson, que trabajaba con sistemas de fabricación y planeamiento de la producción, publicó un documento con un teorema que se denomina ahora teorema de Jackson (Jackson, 1957 [46]). En dicho teorema demostró que una red de puesta en fila de espera de nodos M/M/n tiene forma de producto. Sus conclusiones fueron inspiradas por el resultado obtenido por Burke el año anterior (Burke, 1956 [13]).

Teorema 14.1. Teorema de Jackson: Considérese una red de puesta en fila de espera abierta con K nodos que satisfacen las siguientes condiciones

a) Cada nodo es un sistema de puesta en fila M/M/n. El nodo k tiene nk servidores y el promedio del tiempo de servicio es 1=k.

b) Los clientes llegan desde fuera del sistema al nodo k conforme a un proceso de Poisson con intensidad k. Pueden llegar también clientes de otros nodos al nodo k.

c) Un cliente, que acaba de finalizar su servicio en el nodo j, se transfiere inmediatamente al nodo k con probabilidad pjk o sale de la red con probabilidad:



Un cliente puede visitar varias veces el mismo nodo si pkk > 0.

El promedio de la intensidad de llegada k en el nodo k se obtiene empleando las ecuaciones de equilibrio de flujo:

Sea p(i1, i2, . . ., iK) la representación de las probabilidades de espacio de estado conforme a la hipótesis de equilibrio estadístico, es decir la probabilidad que haya ik clientes en el nodo k. Asimismo, se supone que



Las probabilidades de espacio de estado vienen dadas entonces en forma de producto:



Aquí para el nodo k, pk(ik) es la probabilidad de estado de un sistema de puesta en fila M/M/n con intensidad de llegadas k y velocidad de servicio k (14.1). El tráfico ofrecido c/k =_k al nodo k debe ser menor que la capacidad nk del nodo para entrar en equilibrio estadístico (14.6).

El punto fundamental del teorema de Jackson es que cada nodo puede ser considerado independientemente de los otros y que las probabilidades de estado vienen dadas por las fórmula C de Erlang. Esto simplifica considerablemente el cálculo de las probabilidades de espacio de estado. La prueba del teorema fue obtenida por Jackson en 1957 demostrando que la solución satisface las ecuaciones de equilibrio para el equilibrio estadístico.

En el último modelo de Jackson (Jackson, 1963 [47] la intensidad de llegada proveniente del exterior:



puede depender del número corriente de clientes en la red. Asimismo, k puede depender del número de clientes en el nodo k. De esta manera, se pueden modelar redes de puesta en fila que sean cerradas, abiertas o mixtas. En los tres casos, las probabilidades de estado tienen forma de producto.

El modelo de Gordon y Newell (1967 [33]), que se cita a menudo en la literatura, puede ser tratado como un caso especial del segundo modelo de Jackson.



Figura 14.2  Diagrama de transición de estado de una red de puesta en
fila abierta constituida por dos sistemas M/M/1 en serie


Ejemplo 14.3.1: Dos nodos M/M/1 en serie

La figura 14.2 muestra una red de puesta en fila abierta de dos nodos M/M/1 en serie. El diagrama de transición de estado correspondiente se ilustra en la figura 14.3. Evidentemente, el diagrama de transición de estado no es reversible: entre dos estados vecinos sólo hay flujo en un sentido (véase el § 10.2) y aparentemente no hay forma de producto. Si se resuelven las ecuaciones de equilibrio para obtener las probabilidades de estado se encuentra que la solución se puede expresar en forma de producto:



donde A1 = /1 y A2 = /2. Las probabilidades de estado se pueden expresar en forma de producto p(i, j) = p(i) . p(j), donde p(i) es la probabilidad de estado para un sistema M/M/1 con tráfico ofrecido A1 y p(j) es la probabilidad de estado para un sistema M/M/1 con tráfico ofrecido A2. Las probabilidades de estado indicadas en la figura 14.3 son idénticas a las de la figura 14.4 que tiene equilibrio local y forma de producto. Es posible así encontrar un sistema que es reversible y tenga las mismas probabilidades de estado que el sistema no reversible. En la figura 14.3 hay equilibrio regional y no local. Si se considera un cuadrado de cuatro estados habrá equilibrio para el mundo exterior pero, internamente, habrá circulación a través de la diagonal de desplazamiento de estado.

En redes de fila de espera los clientes a menudo son puestos en operación bucle, de modo tal que un cliente puede visitar varias veces el mismo nodo. Si se tiene una red de puesta en fila con clientes en bucle, donde los nodos son sistemas M/M/n, los procesos de llegada a cada uno de los nodos ya no son procesos de Poisson. De cualquier modo se pueden calcular las probabilidades de estado como si los nodos fueran sistemas M/M/n independientes. Esto se explica en el siguiente ejemplo.

Ejemplo 14.3.2: Redes con retroalimentación

El concepto de retroalimentación se introdujo en el ejemplo 14.3.1 en el que un cliente, que acaba de concluir su servicio en el nodo 2, retorno al nodo 1 con probabilidad p21. El cliente deja el sistema con probabilidad con 1 - p21. La ecuación (14.5) de equilibrio de flujo permite calcular la intensidad de llegada total a cada nodo y la probabilidad p21 se debe elegir de modo tal que las relaciones 1=1 y 2=2 sean menor que uno. Si  0 y p21 1 se comprenderá que los procesos de llegada no son procesos de Poisson. Rara vez llegará un nuevo cliente, pero una vez que ha ingresado al sistema circulará durante un tiempo relativamente largo. El número de circulaciones estará distribuido geométricamente y el tiempo entre llegadas es la suma de los dos tiempos de servicio; es decir, cuando en el sistema hay uno o más clientes, la velocidad de llegada a cada nodo será relativamente alta, mientras que si en el sistema no hay clientes la velocidad será muy baja. El proceso de llegada será en ráfagas.



La situación es similar a la descomposición de una distribución exponencial en una suma ponderada de distribuciones de Erlang-k, con factores geométricos ponderados (véase el § 4.4). En lugar de considerar una distribución entre llegadas exponencial simple se puede descomponer esto en k fases (véase la figura 4.9) y considerar cada fase como una llegada. En consecuencia, el proceso de llegada ha sido transformado de un proceso de Poisson a un proceso con llegadas en ráfagas.



Figura 14.3  Diagrama de transición de estado para la red de puesta en fila
abierta que se ilustra en la figura 14.2. El diagrama no es reversible




Figura 14.4  Diagrama de transición de estado para dos sistemas de puesta en
fila M/M/1 independientes con idéntica intensidad de llegada, pero tiempos
medios de servicio individuales. El diagrama es reversible

14.3.1 Suposición de independencia de Kleinrock


Si se considera una red de datos de vida real, los paquetes tendrán la misma longitud constante y, por tanto, el mismo tiempo de servicio en todos los enlaces y nodos de igual velocidad. La teoría de redes de puesta en fila supone que un paquete (un cliente) toma muestras de un nuevo tiempo de servicio en cada nodo. Esta es una suposición necesaria para la forma de producto. Kleinrock (1964 [65]), investigó por primera vez esta suposición y resultó ser una buena aproximación en la práctica.
1   2   3   4   5   6


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

    Página principal