Анализ сетей с очередями как моделей ВС

Наиболее эффективным и качественно ясным способом расчёта таких сетей является метод анализа средних (МАС). Метод применим также для сетей массового обслуживания, стохастических сетей. Сеть состоит из узлов или систем массового обслуживания, пронумерованных числами i = 0, 1, 2, …. Объект, который обслуживают в узлах, называют заявкой (запросом, сообщением, процессом).

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

Рассмотрим сети с активными ресурсами (узлами), трудоёмкость которых характеризуется временем v_ir, где r = 1,R - тип заявки и её цепь. Если r-заявки поступают в сеть из внешнего источника и после обслуживания покидают её, сеть называется открытой (разомкнутой) по отношению к цепи r. Сеть не имеющая внешних источников, называется замкнутой. В смешенных сетях существуют как открытые, так и замкнутые цепи заявок.

В зависимости от области приложений сети с несколькими типами заявок называют либо многоцепными, либо многопродуктовыми. В замкнутых цепях назначают узел, возможно даже фиктивный, который принимают за начало и конец маршрута. Некоторые из узлов могут повторятся в маршрутной цепи несколько раз. Число α_ir, характеризующее число визитов в узел i заявок маршрута r, называют коэффициентом посещения (передачи).

Коэффициент посещения в стационарном режиме обслуживания можно определить из отношения:

α_ir = λ_ir / λ_0r (23)

где λ_0r - интенсивность потока r-заявок из начального узла маршрутной цепи заявок.

λ_ir - интенсивность потока заявок в узел i.

Для разомкнутой цепи величину λ_0r задают. Для замкнутой цепи величина λ_0r определяется как множество параметров сети и характеризует её производительность (пропускную способность).

В стохастической сети движение r-заявок описывают маршрутной матрицей вероятностей переходов P_r = | p_ij^r |, где p_ij^r - вероятность того, что r-заявка после обслуживания в узле i переходит к узлу j.

В стационарном режиме обслуживания для каждого из узлов записывают следующее условие баланса потоков:

N

λ_ir = ∑λ_ji^r (24)

j=0

Поскольку p_ij^r характеризует долю r-заявок, переходящих из узла i в узел j, то:

λ_ji^r = λ_jr p_ji^r (25)

Подставив выражение (25) в уравнение (24), получим систему уравнений:

N

λ_ir = ∑ p_ji^r λ_jr I =0,N (26)

j=0

Поскольку для разомкнутой цепи задают поток из внешнего источника λ_0r, то из уравнений (23) и (26) можно найти λ_ir и α_ir.

Для замкнутой цепи уравнение балансов потоков (26) представляются однородной системой с бесконечным множеством решений. Поэтому для расчёта прочесов в замкнутых цепях в качестве исходных данных берут величины λ_ir. Поскольку за полный цикл заявка посещает начальный узел трассы один раз, коэффициент посещения нулевого узла равен единице. Учитывая, что λ_0r=1 и подставляя λ_ir = α_ir λ_0r (из (23)) в систему уравнений (26), получаем уравнения для расчёта коэффициентов посещения замкнутой цепи:

α_ir = ∑p_ji^rα_jr /(λ_0r=1)

Для спецификации (описания) маршрута процесса в сетевой модели необходимо задать либо вектор коэффициентов посещения, либо матрицу вероятностей перехода. Если маршрут заявки детерминирован, он сразу описывается коэффициентами посещения, поскольку число визитов в каждый из узлов определено. Стохастический маршрут представляется матрицей Р.

Внутри каждой цепи переходы заявок могут задаваться не на множестве устройств i = l,N, а на множестве пар (i,l), где l = 1, 2, …, L. Если l≠0, то сеть называется много- или мультиклассовой. Каждый из маршрутов многоцепной мультиклассовой сети характеризуется матрицей вероятностей передач: P_r = | P_il,js^r |. Элементы матрицы P_r задают вероятности переходов заявок к обслуживанию классом s в узле сети j, после обслуживания их в узле i классом l.

Состояние заявки внутри каждой цепи характеризуется парой (i,l), что позволяет с помощью P_il,js^r отражать сложные траектории движения заявок и строить модели реальных систем, которые обладают большей достоверностью по сравнению с одноклассовыми.

Интенсивность потока заявок в классе s системы i из других систем сети обозначим λ_is. Уравнения баланса потоков стационарного режима сети имеют вид:

N L

λ_is = ∑ ∑ λ_jL,is (27)

j=0 l=1

Для замкнутой сети из выражения (27) можно определить лишь коэффициенты передачи по отношению к некоторой начальной точке маршрута, которая представляется парой (i, l) = (0, 1).

Коэффициент посещения α_is = λ_is / λ₀₁ характеризует число запросов на обслуживание s-го типа в узле i за полный цикл заявки. Поскольку (0, 1) – начальная точка маршрута, то α₀₁= 1. С учётом этого факта, а также того, что λ_is = α_is λ₀₁, из выражения (27) получаем систему уравнений для вычисления коэффициентов посещения:

α_is = ∑∑ α_jl p_jl,is (28)

Разработаны эффективные способы расчёта сетей, реализующих в узлах следующие способы обслуживания:

· обслуживание в порядке поступления (FiFo);

· разделение времени (PS), предполагающее, что если в узле находится n запросов, то в единицу времени каждому из них будет представлен квант обслуживания длиною 1/n;

· прерывание на основе абсолютных приоритетов с дообслуживанием в обратном порядке;

· обслуживание без ожидания (Д)

Первые три способа представляют узлы, обслуживающие с ожиданием (узлы типа 1). Узлы второго типа, представляют индивидуальные ресурсы, закреплённые за процессом.

Введём обозначения:

n_il - среднее число заявок класса l в узле i;

n_i = ∑_l n_il- среднее число заявок в узле i;

K_r = ∑_i n_i - среднее число заявок цепи r;

K = ∑_r K_r - число заявок в сети.

Состояние сети описывается вектором n = (n₁ n₂ … n_i … n_N), где n_i - состояние узла i.

В случае многопотоковой одноклассовой сети состояние узла представляется набором n_i = (n_i1 … n_ir … n_iR) Если p(n) - вероятность состояния сети, то их сумма по всем состояниям сети ∑_n p(n) = 1.

Основной подход к расчёту сетей состоит в том, что делается группа предположений, используемых в теории стохастических процессов:

· система работает в стационарном режиме;

· процессы движения заявок стохастически независимы;

· задания переходят от узла к узлу по Марковской цепи в соответствии с матрицей вероятностей передач P = | P_ij |;

· распределение времени обслуживания в узлах экспоненциально и т. д.

Характеристики сетей находят через вероятности её состояний.