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

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

Формула названа в честь ее разработчика TO Engset .

Пример приложения [ править ]

Рассмотрим парк транспортных средств и операторов. Операторы входят в систему случайным образом, чтобы запросить использование транспортного средства. Если транспортных средств нет, запрашивающий оператор блокируется (т. Е. Оператор уезжает без транспортного средства). Владелец автопарка хотел бы выбрать небольшой, чтобы минимизировать затраты, но достаточно большой, чтобы обеспечить приемлемую вероятность блокировки.${\ 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; Nc; -1 / (\ lambda h))}}}$

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

Вычисление [ править ]

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

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

Python с SciPy

из  scipy.special  import  hyp2f1 P  =  1.0  /  hyp2f1 ( 1 ,  - c ,  N  -  c ,  - 1.0  /  ( Lambda  *  h ))

MATLAB с Symbolic Math Toolbox

P = 1 / hypergeom ([ 1 , - c ], N - c , - 1 / ( Lambda * h ))             

Частота прибытия неизвестного источника [ править ]

На практике часто бывает так, что скорость поступления источника неизвестна (или ее трудно оценить), в то время как предлагаемый трафик для каждого источника известен. В этом случае можно заменить отношение${\ 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; Nc; 1-P-1 / \ alpha)}}.}$

Вычисление [ править ]

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

Ссылки [ править ]