Формула Энгсета - Engset formula

В теория массового обслуживания, то Формула Энгсета используется для определения вероятности блокировки очереди M / M / c / c / N (в Обозначения Кендалла ).

Формула названа в честь разработчика, Т. О. Энгсет.

Пример приложения

Рассмотрим флот из ${ displaystyle c}$ автомобили и ${ displaystyle N}$ операторы. Операторы входят в систему случайным образом, чтобы запросить использование транспортного средства. Если транспортных средств нет в наличии, запрашивающий оператор блокируется (т. Е. Оператор уезжает без транспортного средства). Владелец автопарка хотел бы выбрать ${ displaystyle c}$ небольшой, чтобы минимизировать затраты, но достаточно большой, чтобы гарантировать приемлемую вероятность блокировки.

Формула

Позволять

• ${ displaystyle c> 0}$ быть (целым) количеством серверов.
• ${ displaystyle N> c}$ быть (целым) количеством источников трафика;
• ${ displaystyle lambda> 0}$ быть скоростью поступления незанятого источника (т. е. скоростью, с которой свободный источник инициирует запросы);
• ${ displaystyle h> 0}$ - среднее время удержания (т.е. среднее время, необходимое серверу для обработки запроса);

Затем вероятность блокировки дается^[1]

${ displaystyle P = { frac {{ binom {N-1} {c}} left ( lambda h right) ^ {c}} { sum _ {i = 0} ^ {c} { binom {N-1} {i}} left ( lambda h right) ^ {i}}}.}$

Переставляя термины, можно переписать приведенную выше формулу как^[2]

${ displaystyle P = { frac {1} {{} _ {2} F_ {1} (1, -c; N-c; -1 / ( lambda h))}}}$

куда ${ displaystyle {} _ {2} F_ {1}}$ гауссовский Гипергеометрическая функция.

Вычисление

Есть несколько рекурсий^[3] что можно использовать для вычисления ${ displaystyle P}$ численно стабильным образом.

В качестве альтернативы любой числовой пакет, поддерживающий Гипергеометрическая функция Некоторые примеры приведены ниже.

Python с SciPy

из scipy.special импорт hyp2f1п = 1.0 / hyp2f1(1, -c, N - c, -1.0 / (Лямбда * час))

MATLAB с Набор инструментов для символьной математики

п = 1 / гипергеома([1, -c], N - c, -1 / (Лямбда * час))

Скорость поступления неизвестного источника

На практике часто бывает, что скорость поступления источника ${ displaystyle lambda}$ неизвестно (или трудно оценить), а ${ displaystyle alpha> 0}$, то предлагаемый трафик по источнику, известен.В этом случае можно заменить отношение

${ displaystyle lambda h = { frac { alpha} {1- alpha (1-P)}}}$

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

${ Displaystyle P = f (P)}$

куда

${ displaystyle f (P) = { frac {1} {{} _ {2} F_ {1} (1, -c; N-c; 1-P-1 / alpha)}}.}$

Вычисление

Хотя вышеизложенное устраняет неизвестное ${ displaystyle lambda}$ из формулы, это вводит дополнительную сложность: мы больше не можем вычислять вероятность блокировки напрямую и вместо этого должны использовать итерационный метод. Хотя итерация с фиксированной точкой заманчиво, было показано, что такая итерация иногда расходящийся когда применяется к ${ displaystyle f}$.^[2] В качестве альтернативы можно использовать один из деление пополам или же Метод Ньютона, для которого реализация с открытым исходным кодом доступен.

Рекомендации