Aproximación de tráfico pesado

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , una aproximación de tráfico pesado (a veces llamada teorema del límite de tráfico pesado ^[1] o aproximación de difusión ) implica la correspondencia de un modelo de colas con un proceso de difusión bajo ciertas condiciones limitantes en los parámetros del modelo. El primer resultado de este tipo fue publicado por John Kingman , quien demostró que cuando el parámetro de utilización de una cola M/M/1 está cerca de 1, una versión escalada del proceso de longitud de cola puede aproximarse con precisión mediante un movimiento browniano reflejado . ^[2]

Condición de tráfico pesado

Las aproximaciones de tráfico pesado se establecen típicamente para el proceso X ( t ) que describe la cantidad de clientes en el sistema en el momento t . Se obtienen considerando el modelo bajo los valores límite de algunos parámetros del modelo y, por lo tanto, para que el resultado sea finito, el modelo debe reescalarse por un factor n , denotado ^{[3] : 490}

${\displaystyle {\hat {X}}_{n}(t)={\frac {X(nt)-\mathbb {E} (X(nt))}{\sqrt {n}}}}$

y el límite de este proceso se considera como n  → ∞.

Hay tres clases de regímenes bajo los cuales generalmente se consideran tales aproximaciones.

1. El número de servidores es fijo y la intensidad del tráfico (utilización) aumenta a 1 (desde abajo). La aproximación de la longitud de la cola es un movimiento browniano reflejado . ^{[4] [5] [6]}
2. La intensidad del tráfico es fija y el número de servidores y la tasa de llegada aumentan hasta el infinito. Aquí el límite de longitud de la cola converge a la distribución normal . ^{[7] [8] [9]}
3. Una cantidad β es fija donde

${\displaystyle \beta =(1-\rho ){\sqrt {s}}}$

donde ρ representa la intensidad del tráfico y s el número de servidores. La intensidad del tráfico y el número de servidores se incrementan hasta el infinito y el proceso de limitación es un híbrido de los resultados anteriores. Este caso, publicado por primera vez por Halfin y Whitt, se conoce a menudo como el régimen Halfin-Whitt ^{[1] [10] [11]} o el régimen impulsado por la calidad y la eficiencia (QED). ^[12]

Resultados para una cola G/G/1

Teorema 1. ^[13] Considere una secuencia de colas G/G/1 indexadas por . Para cola, denotemos el tiempo aleatorio entre llegadas, denotemos el tiempo aleatorio de servicio; denotemos la intensidad del tráfico con y ; denotemos el tiempo de espera en la cola para un cliente en estado estable; denotemos y ${\displaystyle j}$
${\displaystyle j}$ ${\displaystyle T_{j}}$ ${\displaystyle S_{j}}$ ${\displaystyle \rho _{j}={\frac {\lambda _{j}}{\mu _{j}}}}$ ${\displaystyle {\frac {1}{\lambda _{j}}}=E(T_{j})}$ ${\displaystyle {\frac {1}{\mu _{j}}}=E(S_{j})}$ ${\displaystyle W_{q,j}}$ ${\displaystyle \alpha _{j}=-E[S_{j}-T_{j}]}$ ${\displaystyle \beta _{j}^{2}=\operatorname {var} [S_{j}-T_{j}];}$

Supongamos que , , y . entonces ${\displaystyle T_{j}{\xrightarrow {d}}T}$ ${\displaystyle S_{j}{\xrightarrow {d}}S}$ ${\displaystyle \rho _{j}\rightarrow 1}$

${\displaystyle {\frac {2\alpha _{j}}{\beta _{j}^{2}}}W_{q,j}{\xrightarrow {d}}\exp(1)}$

siempre que:

(a) ${\displaystyle \operatorname {Var} [S-T]>0}$

(b) para algunos , y son ambos menores que alguna constante para todos . ${\displaystyle \delta >0}$ ${\displaystyle E[S_{j}^{2+\delta }]}$ ${\displaystyle E[T_{j}^{2+\delta }]}$ ${\displaystyle C}$ ${\displaystyle j}$

Argumento heurístico

• Tiempo de espera en la cola

Sea la diferencia entre el n-ésimo tiempo de servicio y el n-ésimo tiempo entre llegadas; Sea el tiempo de espera en la cola del n-ésimo cliente; ${\displaystyle U^{(n)}=S^{(n)}-T^{(n)}}$ ${\displaystyle W_{q}^{(n)}}$

Entonces por definición:

${\displaystyle W_{q}^{(n)}=\max(W_{q}^{(n-1)}+U^{(n-1)},0)}$

Después del cálculo recursivo, tenemos:

${\displaystyle W_{q}^{(n)}=\max(U^{(1)}+\cdots +U^{(n-1)},U^{(2)}+\cdots +U^{(n-1)},\ldots ,U^{(n-1)},0)}$

• Paseo aleatorio

Sea , con son iid; Defina y ; ${\displaystyle P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}}$ ${\displaystyle U^{(i)}}$ ${\displaystyle \alpha =-E[U^{(i)}]}$ ${\displaystyle \beta ^{2}=\operatorname {var} [U^{(i)}]}$

Entonces tenemos

${\displaystyle E[P^{(k)}]=-k\alpha }$

${\displaystyle \operatorname {var} [P^{(k)}]=k\beta ^{2}}$

${\displaystyle W_{q}^{(n)}=\max _{n-1\geq k\geq 0}P^{(k)};}$

lo conseguimos tomando límite sobre . ${\displaystyle W_{q}^{(\infty )}=\sup _{k\geq 0}P^{(k)}}$ ${\displaystyle n}$

Por lo tanto, el tiempo de espera en la cola del n-ésimo cliente es el supremo de un paseo aleatorio con una deriva negativa. ${\displaystyle W_{q}^{(n)}}$

• Aproximación del movimiento browniano

El paseo aleatorio se puede aproximar mediante un movimiento browniano cuando los tamaños de los saltos se aproximan a 0 y los tiempos entre los saltos se aproximan a 0.

Tenemos y tiene incrementos independientes y estacionarios . Cuando la intensidad del tráfico se acerca a 1 y tiende a , tenemos después reemplazado con valor continuo según el teorema del límite central funcional . ^{[14] : 110} Por lo tanto, el tiempo de espera en la cola del cliente n se puede aproximar por el supremo de un movimiento browniano con una deriva negativa. ${\displaystyle P^{(0)}=0}$ ${\displaystyle P^{(k)}}$ ${\displaystyle \rho }$ ${\displaystyle k}$ ${\displaystyle \infty }$ ${\displaystyle P^{(t)}\ \sim \ \mathbb {N} (-\alpha t,\beta ^{2}t)}$ ${\displaystyle k}$ ${\displaystyle t}$ ${\displaystyle n}$

• Movimiento browniano supremo

Teorema 2. ^{[15] : 130} Sea un movimiento browniano con deriva y desviación estándar que comienza en el origen, y sea ${\displaystyle X}$ ${\displaystyle \mu }$ ${\displaystyle \sigma }$ ${\displaystyle M_{t}=\sup _{0\leq s\leq t}X(s)}$

si ${\displaystyle \mu \leq 0}$

${\displaystyle \lim _{t\rightarrow \infty }P(M_{t}>x)=\exp(2\mu x/\sigma ^{2}),x\geq 0;}$

de lo contrario

${\displaystyle \lim _{t\rightarrow \infty }P(M_{t}\geq x)=1,x\geq 0.}$

Conclusión

${\displaystyle W_{q}^{(\infty )}\thicksim \exp \left({\frac {2\alpha }{\beta ^{2}}}\right)}$ bajo condiciones de tráfico pesado

De esta manera, el teorema del límite de tráfico pesado (teorema 1) se argumenta heurísticamente. Las demostraciones formales suelen seguir un enfoque diferente que involucra funciones características . ^{[4] [16]}

Ejemplo

Considere una cola M/G/1 con una tasa de llegada , una media del tiempo de servicio , y una varianza del tiempo de servicio . ¿Cuál es el tiempo de espera promedio en la cola en estado estable ? ${\displaystyle \lambda }$ ${\displaystyle E[S]={\frac {1}{\mu }}}$ ${\displaystyle \operatorname {var} [S]=\sigma _{B}^{2}}$

El tiempo de espera promedio exacto en cola en estado estable viene dado por:

${\displaystyle W_{q}={\frac {\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}{2\lambda (1-\rho )}}}$

La aproximación de tráfico pesado correspondiente:

${\displaystyle W_{q}^{(H)}={\frac {\lambda ({\frac {1}{\lambda ^{2}}}+\sigma _{B}^{2})}{2(1-\rho )}}.}$

El error relativo de la aproximación del tráfico pesado:

${\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}}$

Así, cuando , tenemos: ${\displaystyle \rho \rightarrow 1}$

${\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}\rightarrow 0.}$

Enlaces externos

• La cola G/G/1 de Sergey Foss

Referencias

1. Halfin, S.; Whitt, W. (1981). "Límites de tráfico pesado para colas con muchos servidores exponenciales" (PDF) . Investigación de operaciones . 29 (3): 567. doi :10.1287/opre.29.3.567.
2. Kingman, JFC ; Atiyah (octubre de 1961). "La cola de un solo servidor en tráfico pesado". Mathematical Proceedings of the Cambridge Philosophical Society . 57 (4): 902. Bibcode :1961PCPS...57..902K. doi :10.1017/S0305004100036094. JSTOR  2984229.
3. Gautam, Natarajan (2012). Análisis de colas: métodos y aplicaciones . CRC Press. ISBN 9781439806586.
4. Kingman, JFC (1962). "Sobre colas en tráfico pesado". Revista de la Royal Statistical Society. Serie B (Metodológica) . 24 (2): 383–392. doi :10.1111/j.2517-6161.1962.tb00465.x. JSTOR  2984229.
5. Iglehart, Donald L.; Ward, Whitt (1970). "Colas de múltiples canales en tráfico pesado. II: secuencias, redes y lotes" (PDF) . Avances en probabilidad aplicada . 2 (2): 355–369. doi :10.2307/1426324. JSTOR  1426324 . Consultado el 30 de noviembre de 2012 .
6. Köllerström, Julian (1974). "Teoría del tráfico pesado para colas con varios servidores. I". Revista de probabilidad aplicada . 11 (3): 544–552. doi :10.2307/3212698. JSTOR  3212698.
7. Iglehart, Donald L. (1965). "Aproximaciones de difusión limitante para la cola de muchos servidores y el problema del reparador". Journal of Applied Probability . 2 (2): 429–441. doi :10.2307/3212203. JSTOR  3212203.
8. Borovkov, AA (1967). "Sobre leyes límite para procesos de servicio en sistemas multicanal". Siberian Mathematical Journal . 8 (5): 746–763. doi :10.1007/BF01040651.
9. Iglehart, Donald L. (1973). "Convergencia débil en la teoría de colas". Avances en probabilidad aplicada . 5 (3): 570–594. doi :10.2307/1425835. JSTOR  1425835.
10. Puhalskii, AA; Reiman, MI (2000). "La cola multiclase GI/PH/N en el régimen Halfin-Whitt". Avances en probabilidad aplicada . 32 (2): 564. doi :10.1239/aap/1013540179.
11. Reed, J. (2009). "La cola G/GI/N en el régimen Halfin–Whitt". Anales de probabilidad aplicada . 19 (6): 2211–2269. arXiv : 0912.2837 . doi :10.1214/09-AAP609.
12. Whitt, W. (2004). "Aproximaciones de tráfico pesado basadas en eficiencia para colas de muchos servidores con abandonos" (PDF) . Management Science . 50 (10): 1449–1461. CiteSeerX 10.1.1.139.750 . doi :10.1287/mnsc.1040.0279. JSTOR  30046186. 
13. Gross, D.; Shortie, JF; Thompson, JM; Harris, CM (2013). "Límites y aproximaciones". Fundamentos de la teoría de colas . págs. 329–368. doi :10.1002/9781118625651.ch7. ISBN 9781118625651.
14. Chen, H.; Yao, DD (2001). "Desiderata técnica". Fundamentos de las redes de colas . Modelado estocástico y probabilidad aplicada. Vol. 46. págs. 97–124. doi :10.1007/978-1-4757-5301-1_5. ISBN 978-1-4419-2896-2.
15. Chen, H.; Yao, DD (2001). "Colas de una sola estación". Fundamentos de las redes de colas . Modelado estocástico y probabilidad aplicada. Vol. 46. págs. 125–158. doi :10.1007/978-1-4757-5301-1_6. ISBN 978-1-4419-2896-2.
16. Asmussen, SR (2003). "Propiedades de estado estable de GI/G/1". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. Vol. 51. págs. 266–301. doi :10.1007/0-387-21525-5_10. ISBN 978-0-387-00211-8.