Cola fluida

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , una cola de fluidos ( modelo de fluidos , ^[1] modelo de flujo de fluidos ^[2] o modelo de fluidos estocástico ^[3] ) es un modelo matemático utilizado para describir el nivel de fluido en un depósito sujeto a períodos determinados aleatoriamente de llenado y vaciado. El término teoría de presas 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 ruinas ^[5] y para modelar redes de datos de alta velocidad. ^[6] El modelo aplica el algoritmo del cubo 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 .

Las colas fluidas se han utilizado para modelar el rendimiento de un conmutador de red , ^[10] un enrutador , ^[11] el protocolo IEEE 802.11 , ^[12] el modo de transferencia asíncrona (la tecnología prevista para B-ISDN ), ^{[13] [14]} el intercambio de archivos entre pares , ^[15] la conmutación de ráfagas ópticas , ^[16] y tiene aplicaciones en ingeniería civil al diseñar represas . ^[17] El proceso está estrechamente relacionado con los procesos de nacimiento-muerte cuasi , para los que se conocen métodos de solución eficientes. ^{[18] [19]}

Descripción del modelo

Una cola de fluido puede verse como un tanque grande, que generalmente se supone que tiene una capacidad infinita, conectado a una serie de tuberías que vierten fluido en el 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 ingresa al buffer y la velocidad a la que sale. Cuando el operador pone el sistema en el estado i, escribimos r _i para la velocidad neta de llegada de fluido en este estado (entrada menos salida). Cuando el buffer contiene fluido, si escribimos X ( t ) para el nivel de fluido en el momento t , ^[20]

${\displaystyle {\frac {\mathrm {d} X(t)}{\mathrm {d} t}}={\begin{cases}r_{i}&{\text{ if }}X(t)>0\\\max(r_{i},0)&{\text{ if }}X(t)=0.\end{cases}}}$

El operador es una cadena de Markov de tiempo continuo y generalmente se denomina proceso de entorno , proceso de fondo ^[21] o proceso impulsor ^[6] . Como el proceso X representa el nivel de fluido en el buffer, 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 límite.

Distribución estacionaria

La distribución estacionaria es una distribución de tipo fase ^[2] como lo demostró por primera vez Asmussen ^[22] y se puede calcular utilizando métodos de análisis matricial . ^[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 tasas λ y 0 (en los estados 1 y 2 respectivamente) de acuerdo a una cadena de Markov de tiempo continuo con matriz generadora

${\displaystyle Q={\begin{pmatrix}-\alpha &\alpha \\\beta &-\beta \end{pmatrix}}}$

La distribución estacionaria se puede calcular explícitamente y se da por ^[6]

${\displaystyle F(x,1)={\frac {\beta }{\alpha +\beta }}\left(1-e^{\left({\frac {\beta }{\mu }}-{\frac {\alpha }{\lambda -\mu }}\right)x}\right)}$

${\displaystyle F(x,2)={\frac {\alpha }{\alpha +\beta }}-{\frac {\beta \left(\lambda -\mu \right)}{\alpha +\beta }}e^{\left({\frac {\beta }{\mu }}-{\frac {\alpha }{\lambda -\mu }}\right)x}}$

y el nivel medio de líquido ^[25]

${\displaystyle {\frac {(\lambda -\mu )\beta }{(\mu (\alpha +\beta )-\beta \lambda )(\alpha +\beta )}}(\mu ,\lambda -\mu ).}$

Periodo de mucha actividad

El período de actividad 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 se vacía nuevamente ( 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 de actividad se conoce para la cola de fluido con búfer infinito ^{[27] [28] [29]} y el período de actividad esperado en el caso de un búfer finito y llegadas como saltos instantáneos. ^[26]

Para un buffer infinito con tasa de servicio constante μ y llegadas a tasas λ y 0, modulado por una cadena de Markov de tiempo continuo con parámetros

${\displaystyle Q={\begin{pmatrix}-\alpha &\alpha \\\beta &-\beta \end{pmatrix}}}$

escriba W *( s ) para la transformada de Laplace-Stieltjes de la distribución del período ocupado, luego ^[29]

${\displaystyle W^{\ast }(s)={\frac {\beta \lambda +s\lambda -\beta \mu +\alpha \mu -{\sqrt {4\beta \alpha \mu (\mu -\lambda )+(s\lambda +\beta (\lambda -\mu )+\alpha \mu )^{2}}}}{2\beta (\lambda -\mu )}}}$

que da el período medio de actividad ^[30]

${\displaystyle \mathbb {E} (W)={\frac {\lambda }{\alpha \mu +\beta (\lambda -\mu )}}.}$

En este caso, de una única fuente de encendido/apagado, se sabe que la distribución del período de actividad es una función de tasa de falla decreciente , lo que significa que cuanto más haya durado un período de actividad, es probable que dure más. ^[31]

Existen dos enfoques principales para resolver el período de actividad en general: mediante la descomposición espectral o un método iterativo recurrente. ^[32] Ahn y Ramaswami publicaron un algoritmo cuadráticamente convergente para calcular los puntos de la transformación. ^[33]

Ejemplo

Por ejemplo, si una cola de fluido con una 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 de ocupación con media 1 y varianza 5/3.

Tasa de pérdida

En un buffer finito, la tasa a la que se pierde fluido (se rechaza del sistema debido a un buffer 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 buffer alcanzado durante un período de 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 exhibe una distribución estacionaria en forma de producto en casos no triviales. ^{[25] [30] [37] [38] [39]}

Colas de fluidos de retroalimentación

Una cola de fluidos de retroalimentación es un modelo en el que los parámetros del modelo (matriz de tasa de transición y vector de deriva) pueden depender hasta cierto punto del contenido del búfer. Normalmente, el contenido del búfer está dividido y los parámetros dependen de la partición en la que se encuentra 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 de fluidos de segundo orden

Las colas de fluidos de segundo orden (a veces llamadas procesos de difusión modulados por 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]} Se consideran comúnmente dos tipos diferentes de condiciones de contorno: absorbentes y reflectantes. ^[44]

Enlaces externos

• BuTools, una implementación en MATLAB , Python y Mathematica de algunos de los resultados anteriores.
• PevaTools, código MATLAB para modelos multirregímenes
• Tutorial de modelos de flujo de fluidos por V. Ramaswami en MAM8

Referencias

1. Mitra, D. (1988). "Teoría estocástica de un modelo fluido de productores y consumidores acoplados por un amortiguador". Avances en probabilidad aplicada . 20 (3): 646–676. doi :10.2307/1427040. JSTOR  1427040.
2. Ahn, S.; Ramaswami, V. (2003). "Modelos de flujo de fluidos y colas: una conexión mediante acoplamiento estocástico" (PDF) . Modelos estocásticos . 19 (3): 325. doi :10.1081/STM-120023564. S2CID  6733796.
3. Elwalid, AI; Mitra, D. (1991). "Análisis y diseño de control de congestión basado en la tasa 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.
4. Stanford, David A.; Latouche, Guy; Woolford, Douglas G.; Boychuk, Dennis; Hunchak, Alek (2005). "Colas de fluidos erlangizadas con aplicación al perímetro de incendios no controlados". Modelos estocásticos . 21 (2–3): 631. doi :10.1081/STM-200056242. S2CID  123591340.
5. Remiche, MA (2005). "Cumplimiento del modelo Token-Bucket con el tráfico markoviano". Modelos estocásticos . 21 (2–3): 615–630. doi :10.1081/STM-200057884. S2CID  121190780.
6. Kulkarni, Vidyadhar G. (1997). "Modelos de fluidos para sistemas de un solo buffer" (PDF) . Frontiers in Queueing: Models and Applications in Science and Engineering . pp. 321–338. ISBN 978-0-8493-8076-1.
7. Moran, PAP (1954). "Una teoría de probabilidad de represas y sistemas de almacenamiento". Aust. J. Appl. Sci . 5 : 116–124.
8. Phatarfod, RM (1963). "Aplicación de métodos de análisis secuencial a la teoría de presas". Anales de estadística matemática . 34 (4): 1588–1592. doi : 10.1214/aoms/1177703892 .
9. Gani, J.; Prabhu, NU (1958). "Tratamiento de un problema de almacenamiento mediante tiempo continuo". Nature . 182 (4627): 39. Bibcode :1958Natur.182...39G. doi :10.1038/182039a0. S2CID  42193342.
10. Anick, D.; Mitra, D .; Sondhi, MM (1982). "Teoría estocástica de un sistema de manejo de datos con múltiples fuentes" (PDF) . The Bell System Technical Journal . 61 (8): 1871–1894. doi :10.1002/j.1538-7305.1982.tb03089.x. S2CID  16836549.
11. Hohn, N.; Veitch, D.; Papagiannaki, K.; Diot, C. (2004). "Uniendo el rendimiento del router y la teoría de colas". Actas de la conferencia internacional conjunta sobre medición y modelado de sistemas informáticos - SIGMETRICS 2004/PERFORMANCE 2004 . p. 355. CiteSeerX 10.1.1.1.3208 . doi :10.1145/1005686.1005728. ISBN  978-1581138733.S2CID14416842  .​
12. Arunachalam, V.; Gupta, V.; Dharmaraja, S. (2010). "Una cola fluida modulada por dos procesos independientes de nacimiento y muerte". Computers & Mathematics with Applications . 60 (8): 2433–2444. doi : 10.1016/j.camwa.2010.08.039 .
13. Norros, I.; Roberts, JW; Simonian, A.; Virtamo, JT (1991). "La superposición de fuentes de velocidad de bits variable en un multiplexor ATM". Revista IEEE sobre áreas seleccionadas en comunicaciones . 9 (3): 378. doi :10.1109/49.76636.
14. Rasmussen, C.; Sorensen, JH; Kvols, KS; Jacobsen, SB (1991). "Procedimientos de aceptación de llamadas independientes de la fuente en redes ATM". IEEE Journal on Selected Areas in Communications . 9 (3): 351. doi :10.1109/49.76633.
15. 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 del rendimiento . 63 (3): 149. CiteSeerX 10.1.1.102.3905 . doi :10.1016/j.peva.2005.01.001. 
16. Yazici, MA; Akar, N. (2013). "Análisis de colas de fluidos de Markov con retroalimentación continua y sus aplicaciones para modelar la conmutación por ráfagas ópticas". Actas del 25.° Congreso Internacional de Teletráfico (ITC) de 2013. págs. 1–8. doi :10.1109/ITC.2013.6662952. hdl :11693/28055. ISBN 978-0-9836283-7-8.S2CID863180  .​
17. Gani, J. (1969). "Avances recientes en la teoría del almacenamiento y las inundaciones". Avances en probabilidad aplicada . 1 (1): 90–110. doi :10.2307/1426410. JSTOR  1426410.
18. Ramaswami, V. Smith, D.; Hey, P (eds.). "Métodos analíticos matriciales para flujos de fluidos estocásticos". Ingeniería de teletráfico en un mundo competitivo (Actas del 16.º Congreso Internacional de Teletráfico) . Elsevier Science BV
19. 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.
20. Rogers, LCG ; Shi, Z. (1994). "Cálculo de la ley invariante de un modelo de fluido". Journal of Applied Probability . 31 (4): 885–896. doi :10.2307/3215314. JSTOR  3215314.
21. Scheinhardt, W.; Van Forest, N.; Mandjés, M. (2005). "Colas fluidas de retroalimentación continua". Cartas de investigación operativa . 33 (6): 551. doi :10.1016/j.orl.2004.11.008.
22. Asmussen, Søren (1995). "Distribuciones estacionarias para modelos de flujo de fluidos con o sin ruido browniano". Communications in Statistics. Modelos estocásticos . 11 : 21–49. doi :10.1080/15326349508807330.
23. Akar, N.; Sohraby, K. (2004). "Colas de fluidos de Markov de buffer finito e infinito: un análisis unificado" (PDF) . Journal of Applied Probability . 41 (2): 557. doi :10.1239/jap/1082999086. hdl : 11693/24279 . JSTOR  3216036.
24. 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. Vol. 356. pág. 167. doi :10.1007/978-3-642-35980-4_19. ISBN . 978-3-642-35979-8.
25. Field, A.; Harrison, P. (2007). "Un enfoque compositivo aproximado para el análisis de redes de colas fluidas". Evaluación del rendimiento . 64 (9–12): 1137. doi :10.1016/j.peva.2007.06.025.
26. Lee, Eui Yong; Kinateder, Kimberly KJ (2000). "El período húmedo esperado de una presa finita con entradas exponenciales". Procesos estocásticos y sus aplicaciones . 90 : 175–180. doi : 10.1016/S0304-4149(00)00034-X .
27. Boxma, OJ ; Dumas, V. (1998). "El período de mayor actividad en la cola de fluidos". ACM SIGMETRICS Performance Evaluation Review . 26 : 100–110. doi :10.1145/277858.277881.
28. Field, AJ; Harrison, PG (2010). "Períodos de actividad en colas de fluidos con múltiples estados de entrada de vaciado". Journal of Applied Probability . 47 (2): 474. doi : 10.1239/jap/1276784904 .
29. Asmussen, SR (1994). "Análisis de períodos de actividad, eventos raros y comportamiento transitorio en modelos de flujo de fluidos" (PDF) . Revista de Matemáticas Aplicadas y Análisis Estocástico . 7 (3): 269–299. doi : 10.1155/S1048953394000262 .
30. Kroese, DP ; Scheinhardt, WRW (2001). "Distribuciones conjuntas para colas de fluidos en interacción". Queueing Systems . 37 : 99–139. doi :10.1023/A:1011044217695. S2CID  3482641.
31. Gautam, N.; Kulkarni, VG; Palmowski, Z.; Rolski, T. (1999). "Límites para modelos de fluidos impulsados ​​por entradas semimarkovianas" (PDF) . Probabilidad en la ingeniería y las ciencias de la información . 13 (4): 429. doi :10.1017/S026996489913403X.
32. Badescu, Andrei L.; Landriault, David (2009). "Aplicaciones de métodos analíticos de matrices de flujo de fluidos en la teoría de la ruina: una revisión" (PDF) . RACSAM - Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas . 103 (2): 353–372. doi :10.1007/BF03191912. S2CID  53498442.
33. Ahn, S.; Ramaswami, V. (2005). "Algoritmos eficientes para el análisis transitorio de modelos de flujo de fluidos estocásticos" (PDF) . Journal of Applied Probability . 42 (2): 531. doi : 10.1239/jap/1118777186 .
34. O'Reilly, MGM; Palmowski, Z. (2013). "Tasas de pérdida para modelos de fluidos estocásticos". Evaluación del desempeño . 70 (9): 593. doi :10.1016/j.peva.2013.05.005.
35. Boxma, OJ ; Perry, D.; Van Der Duyn Schouten, FA (1999). "Colas de fluidos y procesos de montaña". Probabilidad en la ingeniería y las ciencias de la información . 13 (4): 407–427. doi :10.1017/S0269964899134028.
36. Boxma, OJ ; Perry, D. (2009). "Sobre el ciclo máximo de montañas, presas y colas". Comunicaciones en Estadística - Teoría y Métodos . 38 (16–17): 2706. doi :10.1080/03610910902936232. S2CID  9973624.
37. Kella, O. (1996). "Estabilidad y forma no productora de redes de fluidos estocásticos con entradas de Lévy". Anales de probabilidad aplicada . 6 : 186–199. doi : 10.1214/aoap/1034968070 .
38. Kella, O. (2000). "Forma no producto de redes de fluidos bidimensionales con entradas de Lévy dependientes". Journal of Applied Probability . 37 (4): 1117–1122. doi :10.1239/jap/1014843090.
39. Dębicki, K.; Dieker, AB; Rolski, T. (2007). "Formas de cuasidiproducto para redes de fluidos impulsadas por Levy". Matemáticas de la investigación de operaciones . 32 (3): 629. arXiv : math/0512119 . doi :10.1287/moor.1070.0259. S2CID  16150704.
40. 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 de operaciones . 70 : 149–169. doi : 10.1007/s00186-008-0235-8 .
41. Kankaya, HE; ​​Akar, N. (2008). "Resolució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.
42. Ivanovs, J. (2010). "Movimiento browniano modulado por Markov con dos barreras reflectantes". Journal of Applied Probability . 47 (4): 1034–1047. arXiv : 1003.4107 . doi :10.1239/jap/1294170517. S2CID  19329962.
43. Karandikar, RL; Kulkarni, VG (1995). "Modelos de flujo de fluidos de segundo orden: movimiento browniano reflejado en un entorno aleatorio". Investigación de operaciones . 43 : 77–88. doi :10.1287/opre.43.1.77.
44. Gribaudo, M.; Manini, D.; Sericola, B.; Telek, M. (2007). "Modelos de fluidos de segundo orden con comportamiento general en el límite". Anales de investigación de operaciones . 160 : 69–82. CiteSeerX 10.1.1.484.6192 . doi :10.1007/s10479-007-0297-7. S2CID  1735120.