Red G

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , una red G ( red de colas generalizada , ^{[ 1 ] [ 2 ]} a menudo llamada red de Gelenbe ^{[ 3 ]} ) es una red abierta de colas G introducida por primera vez por Erol Gelenbe como un modelo para sistemas de colas con funciones de control específicas, como el redireccionamiento o la destrucción del tráfico, así como un modelo para redes neuronales . ^{[ 4 ] [ 5 ]} Una cola G es una red de colas con varios tipos de clientes novedosos y útiles:

• clientes positivos , que llegan desde otras colas o llegan externamente como llegadas de Poisson, y obedecen las disciplinas de servicio y enrutamiento estándar como en los modelos de red convencionales,
• clientes negativos , que llegan de otra cola, o que llegan externamente como llegadas de Poisson, y eliminar (o 'matar') clientes en una cola no vacía, lo que representa la necesidad de eliminar tráfico cuando la red está congestionada, incluida la eliminación de "lotes" de clientes ^{[ 6 ] [ 7 ]}
• "Disparadores", que llegan de otras colas o desde fuera de la red, y que desplazan a los clientes y los mueven a otras colas.

Existe una solución en forma de producto, superficialmente similar al teorema de Jackson , pero que requiere la solución de un sistema de ecuaciones no lineales para los flujos de tráfico, para la distribución estacionaria de redes G, mientras que las ecuaciones de tráfico de una red G son, de hecho, sorprendentemente no lineales, y el modelo no cumple con el equilibrio parcial. Esto rompió supuestos previos que consideraban el equilibrio parcial como una condición necesaria para una solución en forma de producto. Una propiedad poderosa de las redes G es que son aproximadores universales para funciones continuas y acotadas, por lo que pueden usarse para aproximar comportamientos de entrada-salida bastante generales. ^{[ 8 ]}

Una red de m colas interconectadas es una red G si

1. cada cola tiene un servidor, que atiende a una tasa μ _i ,
2. Las llegadas externas de clientes positivos o de disparadores o reinicios forman procesos de Poisson de tasa${\displaystyle \scriptstyle {\Lambda _{i}}}$para clientes positivos, mientras que los desencadenantes y reinicios, incluidos los clientes negativos, forman un proceso de Poisson de tasa${\displaystyle \scriptstyle {\lambda _{i}}}$,
3. Al completar el servicio, un cliente pasa de la cola i a la cola j como un cliente positivo con probabilidad${\displaystyle \scriptstyle {p_{ij}^{+}}}$, como un disparador o reinicio con probabilidad${\displaystyle \scriptstyle {p_{ij}^{-}}}$y abandona la red con probabilidad${\displaystyle \scriptstyle {d_{i}}}$,
4. Al llegar a una cola, un cliente positivo actúa como de costumbre y aumenta la longitud de la cola en 1.
5. Al llegar a una cola, el cliente negativo reduce la longitud de la cola en un número aleatorio (si hay al menos un cliente positivo presente en la cola), mientras que un disparador mueve a un cliente probabilísticamente a otra cola y un reinicio restablece el estado de la cola a su estado estable si la cola está vacía cuando llega el reinicio. Todos los disparadores, clientes negativos y reinicios desaparecen después de haber realizado su acción, por lo que en realidad son señales de "control" en la red.

• Tenga en cuenta que los clientes normales que abandonan una cola pueden convertirse en desencadenantes o reinicios y en clientes negativos cuando visitan la siguiente cola.

En una red de este tipo , una cola se conoce como cola G.

Defina la utilización en cada nodo,

${\displaystyle \rho _{i}={\frac {\lambda _{i}^{+}}{\mu _{i}+\lambda _{i}^{-}}}}$

donde el${\displaystyle \scriptstyle {\lambda _{i}^{+},\lambda _{i}^{-}}}$para${\displaystyle \scriptstyle {i=1,\ldots ,m}}$satisfacer

Luego, escribiendo ( n ₁ ,  ...  , n _m ) para el estado de la red (con longitud de cola n _i en el nodo i ), si existe una solución única no negativa${\displaystyle \scriptstyle {(\lambda _{i}^{+},\lambda _{i}^{-})}}$Si existe para las ecuaciones anteriores ( 1 ) y ( 2 ) tal que ρ _i para todo i, entonces existe la distribución de probabilidad estacionaria π y está dada por

${\displaystyle \pi (n_{1},n_{2},\ldots ,n_{m})=\prod _{i=1}^{m}(1-\rho _{i})\rho _{i}^{n_{i}}.}$

El tiempo de respuesta es el tiempo que un cliente pasa en el sistema. Se conoce la distribución del tiempo de respuesta para una única cola G ^{[ 9 ]} donde los clientes son atendidos utilizando una disciplina FCFS a una tasa μ , con llegadas positivas a una tasa λ ⁺ y llegadas negativas a una tasa λ− que eliminan a los clientes del final de la cola. La transformada de Laplace de ^la distribución del tiempo de respuesta en esta situación es ^{[ 9 ] [ 10 ]}

${\displaystyle W^{\ast }(s)={\frac {\mu (1-\rho )}{\lambda ^{+}}}{\frac {s+\lambda +\mu (1-\rho )-{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}{\lambda ^{-}-\lambda ^{+}-\mu (1-\rho )-s+{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}}}$

donde λ  = λ ⁺ + λ ⁻ y ρ = λ ⁺ /( λ ⁻ + μ ), requiriendo ρ < 1 para la estabilidad.         

También se conoce el tiempo de respuesta para un par de colas G en tándem (donde los clientes que terminan el servicio en el primer nodo se mueven inmediatamente al segundo y luego abandonan la red), y se cree que las extensiones a redes más grandes serán intratables. ^{[ 10 ]}