En la teoría de las colas , una disciplina dentro de la teoría matemática de la probabilidad , una cola de fluido ( modelo de fluido , [1] modelo de flujo de fluido [2] o modelo de fluido estocástico [3] ) es un modelo matemático utilizado para describir el nivel de fluido en un yacimiento. sujeto a períodos de llenado y vaciado determinados aleatoriamente. El término teoría de la presa se utilizó en la literatura anterior para estos modelos. El modelo se ha utilizado para aproximar modelos discretos, modelar la propagación de incendios forestales , [4] en la teoría de la ruina [5] y para modelar redes de datos de alta velocidad. [6]El modelo aplica el algoritmo de cubeta con fugas a una fuente estocástica.
El modelo fue introducido por primera vez por Pat Moran en 1954, donde se consideró un modelo de tiempo discreto. [7] [8] [9] Las colas fluidas permiten que las llegadas sean continuas en lugar de discretas, como en modelos como las colas M / M / 1 y M / G / 1 .
Se han utilizado colas fluidas para modelar el rendimiento de un conmutador de red , [10] un enrutador , [11] el protocolo IEEE 802.11 , [12] Modo de transferencia asincrónica (la tecnología prevista para B-ISDN ), [13] [14] intercambio de archivos peer-to-peer , [15] conmutación de ráfagas ópticas , [16] y tiene aplicaciones en ingeniería civil al diseñar presas . [17] El proceso está estrechamente relacionado con los procesos de cuasi nacimiento-muerte , para los que se conocen métodos de solución eficientes. [18] [19]
Descripcion del modelo
Una cola de fluidos se puede ver como un tanque grande, típicamente asumido que tiene una capacidad infinita, conectado a una serie de tuberías que vierten fluido al tanque y una serie de bombas que extraen fluido del tanque. Un operador controla las tuberías y las bombas controlando la velocidad a la que el fluido se vierte al amortiguador y la velocidad a la que sale el fluido. Cuando el operador pone el sistema en el estado i , escribimos r i para la tasa neta de llegada de fluido en este estado (entrada menos salida). Cuando el búfer contiene líquido, si escribimos X ( t ) para el nivel de líquido en el tiempo t , [20]
El operador es una cadena de Markov de tiempo continuo y generalmente se denomina proceso ambiental , proceso de fondo [21] o proceso de conducción . [6] Como el proceso X representa el nivel de fluido en el búfer, solo puede tomar valores no negativos.
El modelo es un tipo particular de proceso de Markov determinista por partes y también puede verse como un modelo de recompensa de Markov con condiciones de contorno.
Distribución estacionaria
La distribución estacionaria es una distribución de tipo fase [2] como lo mostró por primera vez Asmussen [22] y se puede calcular utilizando métodos analíticos matriciales . [10]
El método de descomposición aditiva es numéricamente estable y separa los valores propios necesarios para el cálculo mediante la descomposición de Schur . [23] [24]
Modelo encendido / apagado
Para un sistema simple donde el servicio tiene una tasa constante μ y la llegada fluctúa entre las tasas λ y 0 (en los estados 1 y 2 respectivamente) de acuerdo con una cadena de Markov en tiempo continuo con matriz generadora
la distribución estacionaria se puede calcular explícitamente y viene dada por [6]
y nivel medio de líquido [25]
Periodo ocupado
El período ocupado es el período de tiempo medido desde el instante en que el fluido llega por primera vez al búfer ( X ( t ) se vuelve distinto de cero) hasta que el búfer está nuevamente vacío ( X ( t ) vuelve a cero). En la literatura anterior, a veces se lo denomina período húmedo (de la presa). [26] La transformada de Laplace-Stieltjes de la distribución del período ocupado es conocida por la cola fluida con búfer infinito [27] [28] [29] y el período ocupado esperado en el caso de un búfer finito y las llegadas como saltos instantáneos. [26]
Para un búfer infinito con tasa de servicio constante μ y llegadas a tasas λ y 0, modulado por una cadena de Markov de tiempo continuo con parámetros
escriba W * ( s ) para la transformada de Laplace-Stieltjes de la distribución del período ocupado, luego [29]
que da el período medio ocupado [30]
En este caso, de una sola fuente de encendido / apagado, se sabe que la distribución del período ocupado es una función de tasa de falla decreciente, lo que significa que cuanto más tiempo haya durado un período ocupado, es probable que dure más. [31]
Hay dos enfoques principales para resolver el período ocupado en general, utilizando la descomposición espectral o un método iterativo recurrente. [32] Un cuadráticamente convergente algoritmo para puntos de la transformada fue publicado por Ahn y Ramaswami de cálculo. [33]
Ejemplo
Por ejemplo, si una cola de fluido con tasa de servicio μ = 2 es alimentada por una fuente de encendido / apagado con parámetros α = 2, β = 1 y λ = 3, entonces la cola de fluido tiene un período ocupado con media 1 y varianza 5/3.
Tasa de pérdida
En un búfer finito, la velocidad a la que se pierde el fluido (rechazado del sistema debido a un búfer lleno) se puede calcular utilizando transformadas de Laplace-Stieltjes. [34]
Proceso de montaña
El término proceso de montaña se ha acuñado para describir el valor máximo del proceso de contenido de búfer alcanzado durante un período de mucha actividad y se puede calcular utilizando los resultados de una cola G / M / 1 . [35] [36]
Redes de colas fluidas
Se ha calculado la distribución estacionaria de dos colas de fluidos en tándem y se ha demostrado que no presenta una distribución estacionaria de la forma del producto en casos no triviales. [25] [30] [37] [38] [39]
Colas fluidas de retroalimentación
Una cola de fluido de retroalimentación es un modelo en el que se permite que los parámetros del modelo (matriz de velocidad de transición y vector de deriva) dependan en cierta medida del contenido de la memoria intermedia. Normalmente, el contenido del búfer está dividido y los parámetros dependen de la partición en la que se encuentre el proceso de contenido del búfer. [40] La factorización de Schur ordenada se puede utilizar para calcular de manera eficiente la distribución estacionaria de dicho modelo. [41]
Colas fluidas de segundo orden
Las colas de fluidos de segundo orden (a veces llamadas procesos de difusión modulada de Markov o colas de fluidos con ruido browniano [42] ) consideran un movimiento browniano reflejado con parámetros controlados por un proceso de Markov. [22] [43] Comúnmente se consideran dos tipos diferentes de condiciones de contorno: absorbente y reflectante. [44]
enlaces externos
- BuTools , una implementación de MATLAB , Python y Mathematica de algunos de los resultados anteriores.
- PevaTools , código MATLAB para modelos de múltiples regímenes
- Tutorial de modelos de flujo de fluidos por V. Ramaswami en MAM8
Referencias
- ^ Mitra, D. (1988). "Teoría estocástica de un modelo fluido de productores y consumidores acoplado por un búfer". Avances en probabilidad aplicada . 20 (3): 646–676. doi : 10.2307 / 1427040 . JSTOR 1427040 .
- ^ a b Ahn, S .; Ramaswami, V. (2003). "Modelos de flujo de fluidos y colas: una conexión por acoplamiento estocástico" (PDF) . Modelos estocásticos . 19 (3): 325. doi : 10.1081 / STM-120023564 . S2CID 6733796 .
- ^ Elwalid, AI; Mitra, D. (1991). "Análisis y diseño de control de congestión basado en tarifas de redes de alta velocidad, I: Modelos de fluidos estocásticos, regulación de acceso". Sistemas de colas . 9 (1–2): 29–63. doi : 10.1007 / BF01158791 . S2CID 19379411 .
- ^ Stanford, David A .; Latouche, Guy; Woolford, Douglas G .; Boychuk, Dennis; Hunchak, Alek (2005). "Colas de fluido erlangizadas con aplicación a perímetro de fuego incontrolado". Modelos estocásticos . 21 (2-3): 631. doi : 10.1081 / STM-200056242 . S2CID 123591340 .
- ^ Remiche, MA (2005). "Cumplimiento del modelo Token-Bucket con el tráfico de Markov". Modelos estocásticos . 21 (2–3): 615–630. doi : 10.1081 / STM-200057884 . S2CID 121190780 .
- ^ a b c Kulkarni, Vidyadhar G. (1997). "Modelos fluidos para sistemas de un solo tampón" (PDF) . Fronteras en colas: modelos y aplicaciones en ciencia e ingeniería . págs. 321–338. ISBN 978-0-8493-8076-1.
- ^ Moran, PAP (1954). "Una teoría de la probabilidad de presas y sistemas de almacenamiento". Aust. J. Appl. Sci . 5 : 116-124.
- ^ Phatarfod, RM (1963). "Aplicación de métodos de análisis secuencial a la teoría de presas" . Los Anales de Estadística Matemática . 34 (4): 1588-1592. doi : 10.1214 / aoms / 1177703892 .
- ^ Gani, J .; Prabhu, NU (1958). "Tratamiento en tiempo continuo de un problema de almacenamiento". Naturaleza . 182 (4627): 39. Bibcode : 1958Natur.182 ... 39G . doi : 10.1038 / 182039a0 . S2CID 42193342 .
- ^ a b Anick, D .; Mitra, D .; Sondhi, MM (1982). "Teoría estocástica de un sistema de manejo de datos con múltiples fuentes" (PDF) . Revista técnica de Bell System . 61 (8): 1871–1894. doi : 10.1002 / j.1538-7305.1982.tb03089.x . S2CID 16836549 .
- ^ Hohn, N .; Veitch, D .; Papagiannaki, K .; Diot, C. (2004). "Teoría de puesta en cola y rendimiento de enrutador de puente". Actas de la conferencia internacional conjunta sobre medición y modelado de sistemas informáticos - SIGMETRICS 2004 / PERFORMANCE 2004 . pag. 355. CiteSeerX 10.1.1.1.3208 . doi : 10.1145 / 1005686.1005728 . ISBN 978-1581138733. S2CID 14416842 .
- ^ Arunachalam, V .; Gupta, V .; Dharmaraja, S. (2010). "Una cola fluida modulada por dos procesos independientes de nacimiento-muerte". Computadoras y Matemáticas con Aplicaciones . 60 (8): 2433–2444. doi : 10.1016 / j.camwa.2010.08.039 .
- ^ Norros, I .; Roberts, JW; Simonian, A .; Virtamo, JT (1991). "La superposición de fuentes de tasa de bits variable en un multiplexor ATM". Revista IEEE sobre áreas seleccionadas en comunicaciones . 9 (3): 378. doi : 10.1109 / 49.76636 .
- ^ Rasmussen, C .; Sorensen, JH; Kvols, KS; Jacobsen, SB (1991). "Procedimientos de aceptación de llamadas independientes de la fuente en redes ATM". Revista IEEE sobre áreas seleccionadas en comunicaciones . 9 (3): 351. doi : 10.1109 / 49.76633 .
- ^ Gaeta, R .; Gribaudo, M .; Manini, D .; Sereno, M. (2006). "Análisis de transferencias de recursos en aplicaciones de intercambio de archivos peer-to-peer utilizando modelos fluidos". Evaluación de desempeño . 63 (3): 149. CiteSeerX 10.1.1.102.3905 . doi : 10.1016 / j.peva.2005.01.001 .
- ^ Yazici, MA; Akar, N. (2013). "Análisis de colas de fluido de Markov de retroalimentación continua y sus aplicaciones para modelar Optical Burst Switching". Actas del 25º Congreso Internacional de Teletrafico (ITC) de 2013 . págs. 1–8. doi : 10.1109 / ITC.2013.6662952 . hdl : 11693/28055 . ISBN 978-0-9836283-7-8. S2CID 863180 .
- ^ Gani, J. (1969). "Avances recientes en teoría de almacenamiento e inundaciones". Avances en probabilidad aplicada . 1 (1): 90-110. doi : 10.2307 / 1426410 . JSTOR 1426410 .
- ^ Ramaswami, V. Smith, D .; Hola, P (eds.). "Métodos analíticos matriciales para flujos de fluidos estocásticos". Ingeniería de Teletráfico en un Mundo Competitivo (Actas del XVI Congreso Internacional de Teletráfico) . Elsevier Science BV
- ^ Govorun, M .; Latouche, G .; Remiche, MA (2013). "Estabilidad para colas fluidas: desigualdades características". Modelos estocásticos . 29 : 64–88. doi : 10.1080 / 15326349.2013.750533 . S2CID 120102947 .
- ^ Rogers, LCG ; Shi, Z. (1994). "Cálculo de la ley invariante de un modelo de fluido". Revista de probabilidad aplicada . 31 (4): 885–896. doi : 10.2307 / 3215314 . JSTOR 3215314 .
- ^ Scheinhardt, W .; Van Foreest, N .; Mandjes, M. (2005). "Colas de fluido de retroalimentación continua" . Cartas de investigación operativa . 33 (6): 551. doi : 10.1016 / j.orl.2004.11.008 .
- ^ a b Asmussen, Søren (1995). "Distribuciones estacionarias para modelos de flujo de fluidos con o sin ruido browniano". Comunicaciones en estadística. Modelos estocásticos . 11 : 21–49. doi : 10.1080 / 15326349508807330 .
- ^ Akar, N .; Sohraby, K. (2004). "Colas de fluidos de Markov de búfer infinito y finito: un análisis unificado" (PDF) . Revista de probabilidad aplicada . 41 (2): 557. doi : 10.1239 / jap / 1082999086 . hdl : 11693/24279 . JSTOR 3216036 .
- ^ Telek, MS; Vécsei, MS (2013). "Análisis de colas de fluidos en saturación con descomposición aditiva" (PDF) . Métodos probabilísticos modernos para el análisis de redes de telecomunicaciones . Comunicaciones en Informática y Ciencias de la Información. 356 . pag. 167. doi : 10.1007 / 978-3-642-35980-4_19 . ISBN 978-3-642-35979-8.
- ^ a b Field, A .; Harrison, P. (2007). "Un enfoque compositivo aproximado para el análisis de redes de colas fluidas" . Evaluación de desempeño . 64 (9-12): 1137. doi : 10.1016 / j.peva.2007.06.025 .
- ^ a b Lee, Eui Yong; Kinateder, Kimberly KJ (2000). "El período húmedo esperado de presa finita con insumos exponenciales" . Procesos estocásticos y sus aplicaciones . 90 : 175–180. doi : 10.1016 / S0304-4149 (00) 00034-X .
- ^ Boxma, DO ; Dumas, V. (1998). "El período ocupado en la cola fluida". Revisión de la evaluación del desempeño de ACM SIGMETRICS . 26 : 100-110. doi : 10.1145 / 277858.277881 .
- ^ Field, AJ; Harrison, PG (2010). "Períodos ocupados en colas fluidas con múltiples estados de entrada de vaciado" . Revista de probabilidad aplicada . 47 (2): 474. doi : 10.1239 / jap / 1276784904 .
- ^ a b Asmussen, SR (1994). "Análisis de período ocupado, eventos raros y comportamiento transitorio en modelos de flujo de fluidos" (PDF) . Revista de Matemática Aplicada y Análisis Estocástico . 7 (3): 269–299. doi : 10.1155 / S1048953394000262 .
- ^ a b Kroese, DP ; Scheinhardt, WRW (2001). "Distribuciones conjuntas para la interacción de colas de fluidos". Sistemas de colas . 37 : 99-139. doi : 10.1023 / A: 1011044217695 . S2CID 3482641 .
- ^ Gautam, N .; Kulkarni, VG; Palmowski, Z .; Rolski, T. (1999). "Límites para modelos fluidos impulsados por entradas de Semi-Markov" (PDF) . Probabilidad en Ingeniería y Ciencias de la Información . 13 (4): 429. doi : 10.1017 / S026996489913403X .
- ^ Badescu, Andrei L .; Landriault, David (2009). "Aplicaciones de los métodos analíticos de matriz de flujo de fluidos en la teoría de la ruina: una revisión" (PDF) . RACSAM - Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas . 103 (2): 353–372. doi : 10.1007 / BF03191912 . S2CID 53498442 .
- ^ Ahn, S .; Ramaswami, V. (2005). "Algoritmos eficientes para el análisis transitorio de modelos de flujo de fluidos estocásticos" (PDF) . Revista de probabilidad aplicada . 42 (2): 531. doi : 10.1239 / jap / 1118777186 .
- ^ O'Reilly, MGM; Palmowski, Z. (2013). "Tasas de pérdida para modelos de fluidos estocásticos". Evaluación de desempeño . 70 (9): 593. doi : 10.1016 / j.peva.2013.05.005 .
- ^ Boxma, DO ; Perry, D .; Van Der Duyn Schouten, FA (1999). "Colas fluidas y procesos de montaña" . Probabilidad en Ingeniería y Ciencias de la Información . 13 (4): 407–427. doi : 10.1017 / S0269964899134028 .
- ^ Boxma, DO ; Perry, D. (2009). "En el Ciclo Máximo de Montañas, Represas y Colas". Comunicaciones en estadística: teoría y métodos . 38 (16-17): 2706. doi : 10.1080 / 03610910902936232 . S2CID 9973624 .
- ^ Kella, O. (1996). "Estabilidad y forma no productiva de redes de fluidos estocásticos con insumos de Lévy" . Los anales de la probabilidad aplicada . 6 : 186-199. doi : 10.1214 / aoap / 1034968070 .
- ^ Kella, O. (2000). "Forma no producto de redes fluidas bidimensionales con insumos Lévy dependientes". Revista de probabilidad aplicada . 37 (4): 1117–1122. doi : 10.1239 / jap / 1014843090 .
- ^ Debicki, K .; Dieker, AB; Rolski, T. (2007). "Formularios de cuasi-producto para redes de fluidos impulsadas por impuestos". Matemáticas de la investigación operativa . 32 (3): 629. arXiv : math / 0512119 . doi : 10.1287 / moor.1070.0259 . S2CID 16150704 .
- ^ Malhotra, R .; Mandjes, MRH; Scheinhardt, WRW; Berg, JL (2008). "Una cola de fluido de retroalimentación con dos umbrales de control de congestión" . Métodos matemáticos de investigación operativa . 70 : 149-169. doi : 10.1007 / s00186-008-0235-8 .
- ^ Kankaya, ÉL; Akar, N. (2008). "Solución de colas de fluidos de retroalimentación de múltiples regímenes". Modelos estocásticos . 24 (3): 425. doi : 10.1080 / 15326340802232285 . hdl : 11693/23071 . S2CID 53363967 .
- ^ Ivanovs, J. (2010). "Movimiento browniano modulado por Markov con dos barreras reflectantes". Revista de probabilidad aplicada . 47 (4): 1034-1047. arXiv : 1003.4107 . doi : 10.1239 / jap / 1294170517 . S2CID 19329962 .
- ^ Karandikar, RL; Kulkarni, VG (1995). "Modelos de flujo de fluido de segundo orden: movimiento browniano reflejado en un entorno aleatorio". Investigación operativa . 43 : 77–88. doi : 10.1287 / opre.43.1.77 .
- ^ Gribaudo, M .; Manini, D .; Sericola, B .; Telek, M. (2007). "Modelos de fluidos de segundo orden con comportamiento de contorno general". Anales de investigación operativa . 160 : 69–82. CiteSeerX 10.1.1.484.6192 . doi : 10.1007 / s10479-007-0297-7 . S2CID 1735120 .