Замкнутые сети массового обслуживания: алгоритм Бузена и вычисление нормирующей константы

Математическая модель замкнутой сети Гордона-Ньюэлла содержит M узлов и строго фиксированную популяцию N заявок. Как и в открытых сетях, совместное стационарное распределение вероятностей (что в первом узле k1 заявок, во втором k2 и так далее) сохраняет мультипликативный вид (произведение функций от k_i). Но из-за того, что сумма всех заявок в сети должна строго равняться N, это произведение необходимо разделить на гигантскую нормирующую константу G(N). Эта константа обеспечивает равенство суммы всех вероятностей единице. Проблема заключается в том, что константа G(N) вычисляется как сумма мультипликативных членов по абсолютно всем возможным комбинациям распределения N заявок по M узлам.

Комбинаторная размерность этого пространства состояний равна числу сочетаний из (N + M - 1) по (M - 1). Если в сети 50 станков и 200 циркулирующих паллет, количество слагаемых в нормирующей константе достигает астрономических величин. Прямое вычисление G(N) перебором всех состояний заняло бы столетия работы суперкомпьютера, что делало теорию замкнутых сетей красивой математической абстракцией, абсолютно непригодной для инженерного проектирования реальных вычислительных систем. Настоящий прорыв произошел в 1973 году, когда Джеффри Бузен (Jeffrey Buzen) опубликовал свой рекурсивный алгоритм свертки (Convolution Algorithm), ставший фундаментом компьютерной инженерии производительности.

Алгоритм Бузена применяет принцип динамического программирования для вычисления G(N). Бузен ввел двумерную функцию G(m, n), которая представляет собой нормирующую константу для усеченной сети, состоящей только из первых m узлов и содержащей ровно n заявок. Вместо глобального суммирования миллиардов комбинаций, Бузен вывел простое рекуррентное соотношение: G(m, n) = G(m-1, n) + X_m * G(m, n-1), где X_m — относительная интенсивность загрузки m-го узла. Заполняя двумерную таблицу (матрицу) слева направо и сверху вниз, компьютер использует только результаты предыдущих ячеек. Вычислительная сложность падает с факториальной до тривиальной полиномиальной O(M * N). Константа G(M, N) в правой нижней ячейке матрицы является искомым ответом.

Но алгоритм Бузена — это не просто трюк для нормировки. Полученная двумерная матрица содержит в себе всю операционную метрику системы! Оперируя только значениями соседних ячеек этой матрицы G(m,n), инженер может за доли секунды вычислять любые макроскопические параметры сети. Коэффициент загрузки любого сервера вычисляется как отношение G(M, N-1) к G(M, N) умноженное на X_m. Пропускная способность всей сети (Throughput) вычисляется как отношение тех же двух констант. Используя теорему Литтла (Little Law), аналитики мгновенно находят средние времена отклика и длины очередей в многоядерных кластерах серверов. Алгоритм Бузена доказал, что аппарат исследования операций способен элегантно обходить комбинаторные взрывы, превращая неразрешимые дифференциальные уравнения в простые табличные вычисления.