Базовые сети очередей

Такие сети – это подмножество общего класса сетевых моделей, для которых распределение вероятностей состояний представляется в особо простой аналитической форме. По времени анализа модели делят на быстрые, медленные и приближённые методы анализа основанные на базовых моделях.

К медленным моделям относятся многие Марковские модели сложных систем. Так решение систем с несколькими тысячами состояний упирается в проблему времени. В других случаях может потребоваться большой объём памяти. К медленным также часто относятся имитационные модели, но они обладают высоким правдоподобием в отображении процессов.

Для расчёта сетей, которые здесь названы базовыми, используется возможность представления вероятностей их состояний в форме произведения

P(S₁, S₂, …, S_N) = (P₁(S₁) P₂(S₂) … P_N(S_N))/G (29)

где P_i(S_i) - вероятность того, что i-я система сети находится в состоянии S_i = 0, 1, 2, …, K; К – число заявок, циркулирующих в сети; G - нормализующая константа, выбираемая такой, чтобы сумма вероятностей всех состояний сети была единичной.

Выражение вероятности состояния сложной системы в виде произведения вероятностей состояния более простых систем (элементов сети) связано с поиском «независимости» между различными узлами сети, или, что тоже самое, с использованием декомпозиции (структурирования). Основой классических алгоритмов вычисления G(K) является операция свертки нескольких векторов, которая представима в виде рекуррентных выражений по многомерной схеме Горнера.

При расчёте замкнутых сетей используют также рекуррентные процедуры над такими характеристиками как средняя длина очереди, среднее время ожидания. Этот подход называют методом анализа средних (МАС). Алгоритмы свертки плохо интерпретируют содержательный (прикладной) смысл. МАС основан на ясных содержательных трактовках и разработан для решения численных проблем, возникающих в алгоритмах свертки.

Разомкнутые сети. представим математическое обеспечение для расчёта однородных экспоненциальных сетей с несколькими потоками заявок. Математические модели названного класса описывают следующими исходными данными:

· интенсивность внешних источников пуассоновских потоков – λ_0r;

· экспоненциально распределённой трудоёмкостью обслуживания в узле i – v_i = 1/μ, где μ - интенсивность обслуживания;

· коэффициентами посещения узлов i - α_ir.

Доказано, что в этих условиях сеть математически декомпозируется на множество несвязанных узлов.

Характеристики сети рассчитывают следующим образом. Загрузка узла i со стороны потока заявок типа r

P_ir =λ_irv_i = α_irλ_0rv_i p_i = λ_i/μ_i v_i = 1/μ_i

Тогда суммарная загрузка узла p_i =∑_r p_ir.

Среднее время ожидания до начала обслуживания в узле i вычисляют по формуле:

W_ir = W_i = p_iv_i/(1-p_i)

Время пребывания:

v_ir = V_i = W_i + v_i = v_i/(1-p_i)

Воспользовавшись формулой Литма (n_i = λ_iV_i), найдём число заявок каждого типа в узле i:

n_ir = λ_ir v_ir = p_ir + λ_ir W_ir

Полное время пребывания заявки r в сети:

V_r = ∑_i α_ir v_ir