Приближение интенсивного движения

В теории массового обслуживания , дисциплине математической теории вероятностей , приближение интенсивного трафика (иногда предельная теорема интенсивного трафика). или диффузионное приближение ) — это сопоставление модели массового обслуживания с диффузионным процессом при некоторых предельных условиях на параметры модели. Первый такой результат был опубликован Джоном Кингманом , который показал, что когда параметр использования очереди M/M/1 близок к 1, масштабированная версия процесса длины очереди может быть точно аппроксимирована отраженным броуновским движением .

Условия интенсивного движения

Аппроксимации интенсивного трафика обычно формулируются для процесса X ( t ), описывающего количество клиентов в системе в момент времени t . Они достигаются путем рассмотрения модели при предельных значениях некоторых параметров модели, и поэтому для того, чтобы результат был конечным, модель должна быть масштабирована с коэффициентом n , обозначаемым

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

и предел этого процесса рассматривается при n → ∞.

Существует три класса режимов, при которых обычно рассматриваются такие приближения.

1. Количество серверов фиксировано, а интенсивность трафика (загрузка) увеличена до 1 (снизу). Приближение длины очереди представляет собой отраженное броуновское движение .
2. Интенсивность трафика фиксирована, а количество серверов и скорость поступления увеличены до бесконечности. Здесь предел длины очереди сходится к нормальному распределению .
3. Величина β фиксирована, где

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

где ρ представляет интенсивность трафика, а s — количество серверов. Интенсивность трафика и количество серверов увеличиваются до бесконечности, а процесс ограничения представляет собой гибрид приведенных выше результатов. Этот случай, впервые опубликованный Халфином и Уиттом, часто известен как режим Халфина-Уитта. или режим, ориентированный на качество и эффективность (QED).

Результаты для очереди G/G/1

Теорема 1. Рассмотрим последовательность очередей G/G/1, индексированную $j$.
Для очереди $j$ позволять $T_{j}$ обозначают случайное время между прибытиями, $S_{j}$ обозначают случайное время обслуживания;позволять $\rho _{j}={\frac {\lambda _{j}}{\mu _{j}}}$ обозначим интенсивность движения через ${\frac {1}{\lambda _{j}}}=E(T_{j})$ и ${\frac {1}{\mu _{j}}}=E(S_{j})$; позволять $W_{q,j}$ обозначают время ожидания в очереди для клиента в устойчивом состоянии; Позволять $\alpha _{j}=-E[S_{j}-T_{j}]$ и $\beta _{j}^{2}=\operatorname {var} [S_{j}-T_{j}];$

Предположим, что $T_{j}{\xrightarrow {d}}T$, $S_{j}{\xrightarrow {d}}S$, и $\rho _{j}\rightarrow 1$. затем

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

при условии, что:

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

(б) для некоторых $\delta >0$, $E[S_{j}^{2+\delta }]$ и $E[T_{j}^{2+\delta }]$ оба меньше некоторой константы $C$ для всех $j$.

Эвристический аргумент

• Время ожидания в очереди

Позволять $U^{(n)}=S^{(n)}-T^{(n)}$ быть разницей между n-м временем обслуживания и n-м временем между прибытиями;Позволять $W_{q}^{(n)}$ — время ожидания в очереди n-го клиента;

Тогда по определению:

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

После рекурсивного расчета имеем:

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

• Случайное блуждание

Позволять $P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}$, с $U^{(i)}$ являются идентификаторами; Определять $\alpha =-E[U^{(i)}]$ и $\beta ^{2}=\operatorname {var} [U^{(i)}]$;

Тогда у нас есть

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

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

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

мы получаем $W_{q}^{(\infty )}=\sup _{k\geq 0}P^{(k)}$ превысив лимит $n$.

Таким образом, время ожидания в очереди n-го клиента $W_{q}^{(n)}$ является супремумом случайного блуждания с отрицательным дрейфом.

• Приближение броуновского движения

Случайное блуждание можно аппроксимировать броуновским движением , когда размеры прыжков приближаются к 0, а время между прыжками приближается к 0.

У нас есть $P^{(0)}=0$ и $P^{(k)}$ имеет независимые и стационарные приращения . Когда интенсивность движения $\rho$ приближается к 1 и $k$ имеет тенденцию $\infty$, у нас есть $P^{(t)}\ \sim \ \mathbb {N} (-\alpha t,\beta ^{2}t)$ после замены $k$ с непрерывным значением $t$ согласно функциональной центральной предельной теореме . Таким образом, время ожидания в очереди $n$Этот заказчик можно аппроксимировать супремумом броуновского движения с отрицательным дрейфом.

• Супремуум броуновского движения

Теорема 2. Позволять $X$ быть броуновским движением со сносом $\mu$ и стандартное отклонение $\sigma$ начиная с начала координат, и пусть $M_{t}=\sup _{0\leq s\leq t}X(s)$

если $\mu \leq 0$

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

в противном случае

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

Заключение

$W_{q}^{(\infty )}\thicksim \exp \left({\frac {2\alpha }{\beta ^{2}}}\right)$ в условиях интенсивного движения

Таким образом, эвристически аргументируется предельная теорема интенсивного движения (теорема 1). Формальные доказательства обычно следуют другому подходу, в котором используются характеристические функции .

Пример

Рассмотрим очередь M/G/1 со скоростью поступления $\lambda$, среднее время обслуживания $E[S]={\frac {1}{\mu }}$, и дисперсия времени обслуживания $\operatorname {var} [S]=\sigma _{B}^{2}$. Каково среднее время ожидания в очереди в установившемся режиме ?

Точное среднее время ожидания в очереди в устойчивом состоянии определяется по формуле:

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

Соответствующее приближение интенсивного движения:

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

Относительная ошибка аппроксимации интенсивного движения:

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

Таким образом, когда $\rho \rightarrow 1$, у нас есть :

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

Внешние ссылки

• Очередь G/G/1 Сергея Фосса