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 intenso (a veces llamada teorema límite de tráfico intenso ^{[ 1 ]} o aproximación de difusión ) implica la correspondencia de un modelo de colas con un proceso de difusión bajo ciertas condiciones límite sobre 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 es cercano a 1, una versión escalada del proceso de longitud de la cola puede aproximarse con precisión mediante un movimiento browniano reflejado . ^{[ 2 ]}

Las aproximaciones de tráfico intenso se suelen expresar para el proceso X ( t ) que describe el número de clientes en el sistema en el instante 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 cuando n  →  ∞.

Existen 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) se incrementa 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 límite 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 de Halfin-Whitt ^{[ 1 ] [ 10 ] [ 11 ]} o régimen impulsado por la calidad y la eficiencia (QED). ^{[ 12 ]}

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

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

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

siempre que:

(a)${\displaystyle \operatorname {Var} [ST]>0}$

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

• Tiempo de espera en la cola

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

Entonces, por definición:

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

Tras el 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

Dejar${\displaystyle P^{(k)}=\sum _ {i=1}^{k}U^{(ni)}}$, con${\displaystyle U^{(i)}}$son iid; Definir${\displaystyle \alpha =-E[U^{(i)}]}$y${\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)};}$

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

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

• aproximación del movimiento browniano

Según el teorema de Donsker , una caminata aleatoria puede aproximarse mediante un movimiento browniano cuando el tamaño de los saltos se aproxima a 0 y el tiempo entre los saltos también se aproxima a 0.

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

• Supremo del movimiento browniano

Teorema 2. ^{[ 15 ] : 130} Sea${\displaystyle X}$ser un movimiento browniano con deriva${\displaystyle \mu }$y desviación estándar${\displaystyle \sigma }$comenzando en el origen, y dejemos${\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.}$

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

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

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

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

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

La aproximación correspondiente para tráfico pesado:

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

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

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

Por lo tanto, cuando${\displaystyle \rho \rightarrow 1}$, tenemos  :

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

• La cola G/G/1 de Sergey Foss