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 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 redireccionamiento de tráfico o destrucción de 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 disciplinas de servicio y enrutamiento estándar como en los modelos de red convencionales,
• clientes negativos , que llegan desde otra cola, o que llegan externamente como llegadas de Poisson, y eliminan (o 'matan') 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</ref> ^{[6] [7]}
• "disparadores", que llegan desde 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 en forma 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 las redes G, mientras que las ecuaciones de tráfico de una red G son de hecho sorprendentemente no lineales, y el modelo no obedece al equilibrio parcial. Esto rompió con los supuestos previos de que el equilibrio parcial era 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, de modo que pueden usarse para aproximar comportamientos de entrada-salida bastante generales. ^[8]

Esta sección incluye una lista de referencias , lecturas relacionadas o enlaces externos , pero sus fuentes no están claras porque carece de citas en línea . Ayúdenos a mejorar esta sección introduciendo citas más precisas. ( Febrero de 2012 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Una red de m colas interconectadas es una red G si

1. cada cola tiene un servidor, que presta servicio a una velocidad μ _i ,
2. Las llegadas externas de clientes positivos o de activadores o restablecimientos forman procesos de Poisson de tasa para clientes positivos, mientras que los activadores y restablecimientos, incluidos los clientes negativos, forman un proceso de Poisson de tasa .${\displaystyle \scriptstyle {\Lambda _{i}}}$${\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 , como un disparador o reinicio con probabilidad y sale de la red con probabilidad ,${\displaystyle \scriptstyle {p_{ij}^{+}}}$${\displaystyle \scriptstyle {p_{ij}^{-}}}$${\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 de manera probabilística a otra cola y un reinicio establece el estado de la cola en su estado estable si la cola está vacía cuando llega el reinicio. Todos los disparadores, clientes negativos y reinicios desaparecen después de que hayan realizado su acción, de modo que, de hecho, son señales de "control" en la red.

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

Una cola en dicha red se conoce como cola G.

Definir la utilización en cada nodo,

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

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

${\displaystyle \lambda _{i}^{+}=\sum _{j}\rho _{j}\mu _{j}p_{ji}^{+}+\Lambda _{i}\,}$

( 1 )

${\displaystyle \lambda _{i}^{-}=\sum _{j}\rho _{j}\mu _{j}p_{ji}^{-}+\lambda _{i}.\,}$

( 2 )

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 no negativa única 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 \scriptstyle {(\lambda _{i}^{+},\lambda _{i}^{-})}}$

${\displaystyle \pi(n_{1},n_{2},\ldots ,n_{m})=\prod_{i=1}^{m}(1-\rho_{i})\rho_{i}^{n_{i}}.}$

Esta sección incluye una lista de referencias , lecturas relacionadas o enlaces externos , pero sus fuentes no están claras porque carece de citas en línea . Ayúdenos a mejorar esta sección introduciendo citas más precisas. ( Febrero de 2012 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Es suficiente demostrar que satisface las ecuaciones de equilibrio global que, a diferencia de las redes de Jackson, no son lineales. Observamos que el modelo también permite múltiples clases.${\estilo de visualización \pi}$

Las redes G se han utilizado en una amplia gama de aplicaciones, incluida la representación de redes reguladoras de genes, la combinación de control y carga útil en redes de paquetes, redes neuronales y la representación de imágenes en color e imágenes médicas como imágenes de resonancia magnética.

El tiempo de respuesta es el tiempo que un cliente pasa en el sistema. La distribución del tiempo de respuesta para una única cola G es conocida ^[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 tándem de colas G (donde los clientes que terminan el servicio en el primer nodo pasan inmediatamente al segundo y luego abandonan la red), y se cree que las extensiones a redes más grandes serán intratables. ^[10]