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] o red Gelenbe [2] ) es una red abierta de colas G introducida por primera vez por Erol Gelenbe como modelo para sistemas de colas. con funciones de control específicas, como el redireccionamiento del tráfico o la destrucción del tráfico, así como un modelo para redes neuronales . [3] Una G-queue es una red de colas con varios tipos de clientes novedosos y útiles:
- clientes positivos , que llegan de otras colas o llegan externamente como llegadas de Poisson, y obedecen las disciplinas estándar de servicio y enrutamiento como en los modelos de red convencionales,
- clientes negativos , que llegan de otra cola, o que llegan externamente como llegadas de Poisson, y eliminan (o 'eliminan') clientes en una cola no vacía, lo que representa la necesidad de eliminar el tráfico cuando la red está congestionada, incluida la eliminación de " lotes "de clientes [4] [5] [6]
- "disparadores", que provienen de otras colas o de fuera de la red, y que desplazan a los clientes y los trasladan 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 redes G mientras que las ecuaciones de tráfico de una red G están en hecho sorprendentemente no lineal, y el modelo no obedece al equilibrio parcial. Esto rompió los supuestos anteriores de que el equilibrio parcial era una condición necesaria para una solución de 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. [7]
Definición
Una red de m colas interconectadas es una red G si
- cada cola tiene un servidor, que sirve a una tasa μ i ,
- llegadas externas de clientes positivos o de desencadenantes o reinicios de procesos de tasa de Poisson para los clientes positivos, mientras que los activadores y restablecimientos, incluidos los clientes negativos, forman un proceso de Poisson de tasa ,
- al completar el servicio, un cliente pasa de la cola i a la cola j como un cliente positivo con probabilidad, como disparador o reinicio con probabilidad y sale de la red con probabilidad ,
- al llegar a una cola, un cliente positivo actúa como de costumbre y aumenta la longitud de la cola en 1,
- 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 un cliente probabilísticamente a otra cola y un reinicio establece el estado de la cola a su estado estable si la cola está vacía cuando llega el reinicio. Todos los disparadores, los clientes negativos y los restablecimientos 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 activadores o restablecimientos y clientes negativos cuando visitan la siguiente cola.
Una cola en red tal es conocido como un G-cola .
Distribución estacionaria
Definir la utilización en cada nodo,
donde el por satisfacer
( 1 )
( 2 )
Luego, escribiendo ( n 1 ,…, n m ) para el estado de la red (con una longitud de cola n i en el nodo i ), si es una solución única no negativaexiste para las ecuaciones anteriores ( 1 ) y ( 2 ) tal que ρ i para todo i, entonces la distribución de probabilidad estacionaria π existe y está dada por
Prueba
Es suficiente para mostrar 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.
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 las imágenes de resonancia magnética.
Distribución del tiempo de respuesta
El tiempo de respuesta es el tiempo que pasa un cliente en el sistema. La distribución del tiempo de respuesta para una sola cola G es conocida [8] donde los clientes son atendidos usando una disciplina FCFS a una tasa μ , con llegadas positivas a una tasa λ + y llegadas negativas a una tasa λ , lo que mata a los clientes desde el final de la cola. . La transformada de Laplace de la distribución del tiempo de respuesta en esta situación es [8] [9]
donde λ = λ + + λ - y ρ = λ + / ( λ - + μ ), requiriendo ρ <1 para la estabilidad.
También se conoce el tiempo de respuesta para un par en 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. [9]
Referencias
- ^ Gelenbe, Erol (septiembre de 1993). "G-Networks con movimiento de clientes activado". Revista de probabilidad aplicada . 30 (3): 742–748. doi : 10.2307 / 3214781 . JSTOR 3214781 .
- ^ Gelenbe, Erol ; Fourneau, Jean-Michel (2002). "Redes G con reinicios". Evaluación de desempeño . 49 (1/4): 179-191. doi : 10.1016 / S0166-5316 (02) 00127-X .
- ^ Harrison, Peter (2009). "Regresar el tiempo - ¿Qué impacto en el rendimiento?". The Computer Journal . 53 (6): 860–868. CiteSeerX 10.1.1.574.9535 . doi : 10.1093 / comjnl / bxp021 .
- ^ Gelenbe, Erol (1991). "Redes de colas en forma de producto con clientes negativos y positivos" . Revista de probabilidad aplicada . 28 (3): 656–663. doi : 10.2307 / 3214499 . JSTOR 3214499 .
- ^ Gelenbe, Erol (1993). "G-Networks con señales y eliminación de lotes". Probabilidad en Ingeniería y Ciencias de la Información . 7 (3): 335–342. doi : 10.1017 / s0269964800002953 .
- ^ Artalejo, JR (octubre de 2000). "G-Networks: un enfoque versátil para la eliminación de trabajo en las redes de cola". Revista europea de investigación operativa . 126 (2): 233–249. doi : 10.1016 / S0377-2217 (99) 00476-2 .
- ^ Gelenbe, Erol; Mao, Zhi-Hong; Da Li, Yan (1999). "Aproximación de funciones con redes aleatorias con púas". Transacciones IEEE en redes neuronales . 10 (1): 3–9. CiteSeerX 10.1.1.46.7710 . doi : 10.1109 / 72.737488 . PMID 18252498 .
- ^ a b Harrison, PG ; Pitel, E. (1993). "Tiempos de estancia en colas de un solo servidor con clientes negativos". Revista de probabilidad aplicada . 30 (4): 943–963. doi : 10.2307 / 3214524 . JSTOR 3214524 .
- ^ a b Harrison, Peter G. Los tiempos de respuesta en G-redes . XIII Simposio Internacional de Ciencias de la Información y la Computación (ISCIS 1998). págs. 9-16. ISBN 9051994052.