Алгоритм свертки

Алгоритм предусматривает последовательное нахождение нормализующих констант G₁ G₂ … и на их основе – необходимых характеристик сети. Для двухпотоковой сети

G_i(m,n) = G_i-1(m,n) +x_iG_i(m-1,n) +y_iG_i(m,n-1),

где x_i = α_i1v_i1; y_i = α_i2 v_i2; G_i(m,0) = 0; G₀(m,n) = 0;

m =1,K1; n = 1,K2; i = 1,N.

Рекуррентные вычисления дают в конце каждого двумерного цикла нормализующие константы G(K1,K2) = G_N(K1,K2). Значение G(K1,K2) используют для вычисления характеристик узлов сети.

Загрузка узла i со стороны каждого из потоков и их сумма:

p_i1(K1,K2) = x_iG(K-1,K2)/G(K1,K2);

p_i2(K1,K2) = y­_iG(K1,K2-1)/G(K1,K2);

p_i = p_i1 + p_i2.

Пропускная способность цепей:

λ₀₁ = G(K1-1,K2)/G(K1,K2);

λ₀₂ = G(K1,K2-1)/G(K1,K2).

Число заявок каждого из двух типов в узле i:

n_i1(K1,K2) = p_i1 (K1,K2) [1+n_i(K1-1,K2)];

n_i2(K1,K2) = p_i2 (K1,K2) [1+n_i(K1,K2-1)].

Время пребывания в узлах i заявок каждой из цепей:

V_i1(K1,K2) = v_i1[1+n_i(K1-1,K2)];

V_i2(K1,K2) = v_i2[1+n_i(K1,K2-1)]. (35)

Приведённые зависимости верны, если в FIFO-узлах время обслуживания не зависит от цепи, т. е. v_i1 =v_i2. В PS-узлах оно может различаться. При необходимости через G можно найти вероятности состояний и другие характеристики.

Основной недостаток алгоритма – большой диапазон изменения величины G, приводящий к переполнению, потери значности, погрешностям округления.

Метод анализа средних (МАС)

МАС может быть легко получен из алгоритма свертки и формул (n_i = λ_iV_i) Литла для цепи и узлов сети. Так, в случае одноцепной сети при K1 = K из выражения (35) имеем:

V_i(K) = v_i[1 + n_i(K-1)] (36)

tобсл. tожид. v_i

Исходя из формулы Литла для цепи и учитывая, что время полного цикла заявки в сети:

C(K) = ∑_i α_iV_i(K) (37)

получаем

λ₀(K) = K/C (38)

а из формулы Литла для узла находим

n_i(K) = α_iλ₀(K)V_i(K) (39)

Заметим, что n_i(O) =0. Рекуррентные вычисления по формулам (35) – (38) сразу дают искомые характеристики процессов и узлов сети. Загрузку находят из соотношения:

p_i(K) = α_iλ₀(K)v_i.

Рассмотрим уравнение (36). Время пребывания заявки в узле i слагается из времени обслуживания v_i и времени ожидания, равного

W_i(K) = v_in_i(K-1) (40)

Из выражения (40) следует, что если число заявок сети равно К, то в момент прихода в узел i очередной заявки их среднее число в узле равно n_i(K-1), а поскольку каждая из заявок требует времени обслуживания v_i, необходимо подождать v_in_i(K-1) единиц времени до начала обслуживания пришедшей в узел заявки.

Содержательная трактовка формулы Литла

n_i(K) = λ_i(K) V_i(K)

может быть следующей: В единицу времени в узел i приходит λ_i заявок. За время от момента прихода заявки в узел до момента ухода из узла, равное V_i, в узле накапливается λ_iV_i заявок. В стационарном режиме обслуживания их число в узле сохраняется.

Просуммировав n_i по всем узлам сети К = ∑_i n_i(K) = λ₀ ∑_i α_iV_i(K), получим формулу:

K = λ₀ C λ₀ = K / C (38)

Рассмотрим более общий случай обслуживания в узлах. Введём величину b_i(j), характеризующую ёмкость узла i, когда в нём находится j заявок. Для одноканальных обслуживающих приборов с постоянной скоростью обслуживания b_i(j) =1. Для Д-узлов b_i(j) =j. Для узлов, скорость обслуживания в которых зависит от нагрузки, имеем 0 < b_i(j)<∞. Обычно b_i(j) - монотонная неубывающая функция j, т. е.

b_i(j) > b_i(j-1) и b_i(j+1) - b_i(j) ≤ b_i(j) - b_i(j-1).

Например, если в узле находится двухканальный обслуживающий прибор, то b_i(1) =1, b_i(j) =2 для всех j ≥2.

Ёмкость узла (нагрузочная способность) определяется отношением:

b_i(j) = μ_i(j)/μ_i(1) (41)

где μ_i(j) - интенсивность обслуживания в узле i, если в нём находится j заявок, а μ_i(1) - если одна заявка.

Если скорость обслуживания в узле зависит от нагрузки, как это описано формулой (41), то время пребывания можно вычислить по формуле:

b_m

V_i(K) = v_i[1+ n_i(K-1) + ∑ j(¹/ _bi(j) -1) P_i(j-1,K-1)] (42)

j=1

где b_m - максимальная нагрузочная способность узла i, b_m≤K;

(43)

вероятность того, что в i-м узле находится j из всех К заявок, циркулирующих в сети;

K

Pi(0,K) = 1 - ∑Pi(j,K) (44)

j=1

вероятность того, что узел j пуст.

Для одноканального FIFO-узла из формулы (42) получается выражение (36), а для Д-узла

V_i(K) =v_i (45)