Например, Бобцов

ОЦЕНИВАНИЕ КОЛИЧЕСТВА ИНФОРМАЦИОННОЙ РАБОТЫ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ

16
УДК 621. 324
В. А. СМАГИН, И. Ю. ПАРАМОНОВ
ОЦЕНИВАНИЕ КОЛИЧЕСТВА ИНФОРМАЦИОННОЙ РАБОТЫ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ
Предлагается метод расчета моментов и закона распределения количества информационной работы компьютерной сети, состоящей из нескольких взаимосвязанных узлов, при постоянной пропускной способности и произвольных законах распределения времени функционирования узлов. Метод пригоден и для сетевых структур, не связанных с преобразованием информации. Ключевые слова: эффективная работа, информационная сеть, плотность и функция распределения, пропускная способность, матричный метод.
Компьютерные сети — неотъемлемый элемент современной цивилизации. На их основе строятся системы управления объектами различного назначения [1]. Для управления сложными объектами все чаще применяется сетецентрическое управление.
Возрастание сложности систем управления и информационных сетей неизбежно приводит к удорожанию их создания и применения. Кроме того, ухудшаются отдельные эксплуатационные характеристики объектов, несмотря на наличие положительных системных эффектов. Поэтому количественное изучение свойств сетей необходимо для сравнения их друг с другом и выбора наилучших: экономных в эксплуатации, быстродействующих и т. д.
Одной из важнейших характеристик информационных сетей является величина (количество) их эффективной информационной работы, под которой будем понимать количество информации полученной на выходе сети за время ее функционирования.
Формализация задачи. Рассмотрим сеть, состоящую из M узлов. Представим ее в виде ориентированного графа с нулевым узлом (истоком), узлами 1, 2,…, M и выходным узлом ( M + 1) — стоком. Переходы между узлами определим матрицей вероятностей передач сети pi, j . Положим, что значения плотности распределения длительности пребывания в рабочем состоянии всех узлов fi (t) известны [2]. Также положим, что известна пропускная способность
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 12

Оценивание количества информационной работы вычислительной сети

17

(производительность) Ii всех узлов сети (число операций в единицу времени). Задача состоит
в том, чтобы определить значение плотности распределения вероятности величины работы, выполняемой сетью при переходе от ее истока к стоку, по которому можно определить начальные моменты и функцию распределения количества работы сети. Решив эту задачу, можно также определить количество работы, выполняемой на траектории между i -м и j -м узла-

ми сети ( i = 0, M + 1; j = 0, M + 1; i ≠ j ). Метод решения задачи основывается на предположе-
нии о вероятностной независимости значений времени функционирования узлов. Однако это ограничение при необходимости может быть снято, что приведет только к усложнению математического алгоритма решения задачи и длительности получения численных расчетов.
Чтобы перейти от времени пребывания узлов в работоспособном состоянии к величине
работы, выполняемой узлами, выполним простое преобразование W i = Ii ti (W i — случайная
величина работы в i -м узле сети за случайное время ti ). Плотность распределения вероятности величины работы будет равна:

ϕi (w) =

1 Ii

fi

⎛ ⎝⎜

w Ii

⎞ ⎟⎠

.

(1)

Размерность данной плотности — величина, обратная числу операций в единицу времени. В технологических приложениях плотность может измеряться как стоимость на единицу времени.
В дальнейшем требуется на любой траектории случайного процесса суммировать количество работы, поэтому представим соотношение (1) в преобразовании Лапласа:

gi (s) = f i (Ii s),

(2)

где — символ преобразования, s — переменная Лапласа. Введем в рассмотрение матрицу:

⎡ p0,0

⎢ ⎢

p1,0 g1(s)

G(s) = ⎢

⎢ ⎢

pM

,0

gM

(s)

⎣⎢ pM +1,0

p0,1 p1,1 g1 ( s)
pM ,1gM (s) pM +1,1

p0,M p1,M g1(s)

p0,M +1



p1,M +1g1(s)

⎥ ⎥

⎥.

pM ,M gM (s) pM ,M gM (s)⎥⎥

pM +1,M pM +1,M +1 ⎦⎥

(3)

Каждый элемент матрицы pi, j gi (s) есть произведение преобразования Лапласа плотно-
сти вероятности количества выполненной работы в i -м узле сети на вероятность перехода после завершения работы в i -м узле в узел j . Величина работы в нулевом и M + 1 узлах по-
лагается равной нулю, а g0 (s) = gM +1(s) = 1 . Изображение Лапласа плотности распределения количество работы между узлами i и j
сети будет равно элементу (i, j) матрицы T(s) вида:

T(s) = I + G(s) + G2 (s) + = I / (I − G(s))−1,

(4)

где I — единичная матрица. В соответствии с правилом вычисления обратной матрицы элемент (i, j) равен [5]:

Yi, j (s) = Aj,i (s) / R(s),

(5)

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 12

18 В. А. Смагин, И. Ю. Парамонов

где Aj,i (s) — алгебраическое дополнение элемента (i, j) матрицы T(s) ; R(s) — определитель матрицы T(s) . Из (5) следует, что преобразование Лапласа плотности распределения величины работы в сети будет равно:

Y0,M +1(s) = AM +1,0 (s) / R(s) .

(6)

Если величину работы в каждом узле сети задать начальными моментами, то можно предложить алгоритм определения ее начальных моментов между i -м и j -м узлами сети.

Алгоритм учитывает связь между k -м начальным моментом и k -й производной преобразо-

вания Лапласа

в

точке

s = 0.

Подставив вместо

(−1)k

d k gl (s) dsk

s=0

,

l

= 0, M

+ 1,

значение

k -го

момента распределения величины работы в l -м узле сети, а вместо gl (s) s=0 — единицу, по-

лучим k -й начальный момент распределения величины работы между i -м и j -м узлами сети.

По вычисленным начальным моментам с помощью одного из методов, указанных в статьях [3, 4], можно получить аппроксимирующую плотность распределения величины работы, выполненной между узлами i и j сети.

Если в модели сети полагать Ii = 1 для всех i, то в результате анализа получим моменты
и плотность распределения вероятности времени пребывания заявки в сети. При таком условии можно использовать эти параметры для анализа в обычных моделях систем массового обслуживания.
Пример. Требуется оценить вычислительную работу сети, состоящей из трех взаимосвязанных компьютеров. Стохастический граф сети приведен на рис. 1.

2

g1(s)

р12

р24

0 1 р23

4

р13 р13

3

р34

g3(s)

Рис. 1
Заданы значения производительности узлов сети I1 =10, I2 = 7 , I3 = 4 операций/ч;
плотность распределений времени работы узлов f1(t) = δ(t − T1), f2 (t) = δ(t − T2 ),
δ(t) = δ(t − T3 ) , T1 = 12 , T2 = 15 , T3 = 9 ч; вероятность переходов между узлами р12=0,7; р13=0,3; р23=0,6; р24=0,4; р31=0,8; р34=0,2. Распределения времени работ в примере взяты вырожденными для ускорения решения задачи на компьютере. Изображения плотности распределения количества работы узлов в преобразовании Лапласа принимают вид: g1(s) = e−I1T1s , g2 (s) = e−I2T2s , g3 (s) = e−I3T3s ; M = 3 . Матрицы G(s) и I − G(s) представляются в виде:

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 12

Оценивание количества информационной работы вычислительной сети

0 0 G(s) = 0 0 0

1 0 0 p31g3 (s) 0

0 p12 g1(s)
0 0 0

0
p13 g1(s) p23 g2 (s)
0
0

0
0
p24 g2 (s) , p34 g3 (s)
0

19

1 0 (I − G(s)) = 0 0 0

−1 1 0 − p31g3 (s) 0

0 − p12 g1(s)
1 0 0

0
− p13 g1(s) − p23 g2 (s)
1
0

0
0
− p24 g2 (s) . − p34 g3 (s)
1

Элемент матрицы (I − G(s))−1 с номером (0,4), в соответствии с формулой (6), будет равен:

Y0,4 (s) =

p12

g1(s) p23 g2 (s) p34 g3 (s) + 1 − p13 g1(s) p31g3 (s)

p12 g1(s) p24 g2 (s) + − p12 g1(s) p23 g2 (s)

p13 g1(s) p34 p34 g3 (s)

g3

(s)

.

(7)

Подставив исходные данные в (7) и полагая s = 0 , получим Y0,4 (0) = 1 , что подтверждает

выполнимость условия нормирования плотности. Значения трех начальных моментов, най-

денные с помощью дифференцирования (7) и взятия пределов при s = 0 , равны:

ν1 = 517, 5; ν2 = 423590,5; ν3 = 5, 08 ⋅108 . Среднеквадратическое отклонение и коэффициент вариации σ = 394, 7; η = 0, 763. Нормировав плотность вероятности с коэффициентом

С = 1,105 , вычислим новые значения моментов P(w)

ν1 = 535,1; ν2 = 4,179 ⋅105 , ν3 = 3,833 ⋅108 , для кото- 1

рых подберем нормальную плотность распределения

вероятности. Найдем по ней третий начальный мо-

мент и сравним его с вычисленным по формуле (7) третьим моментом. Погрешность этого сравнения не 0,5

превышает ∆ = 10,5 % , что вполне удовлетворительно

для аппроксимации нормальным распределением.

График вероятности P(w) того, что количество эф-

фективной информационной работы, выполненной в сети, будет не менее w , приведен на рис. 2.

0

400 Рис. 2

800 w

Заключение. Предложен метод определения объема работы, выполненной информаци-

онной сетью. В нем используется понятие случайной работы и ее вероятностных характери-

стик. Для получения интегральной характеристики — количества работы сети — использова-

ны стохастический граф сети и его матричное представление.

Предложенная математическая модель метода может быть применена для сетей самого

различного назначения. Вместо показателя эффективной работы в них может использоваться,

например, стоимость и т.д. Ограничительные допущения метода (независимость работы уз-

лов, детерминированность их производительности, фиксированность вероятностей перехо-

дов) могут быть сняты. Но это приведет к усложнению метода и увеличению времени реали-

зации его на компьютере.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 12

20 В. А. Смагин, И. Ю. Парамонов

СПИСОК ЛИТЕРАТУРЫ

1. Олифер В. Г., Олифер Н. А. Основы компьютерных сетей. СПб: Питер, 2009. 352 с.

2. Смагин В. А., Бубнов В. П., Филимонихин Г. В. Расчет вероятностно-временных характеристик пребывания задач в сетевой модели массового обслуживания // Изв. вузов. Приборостроение. 1989. № 2. С. 23—25.

3. Смагин В. А., Филимонихин Г. В. Аппроксимационный метод расчета разомкнутых сетей массового обслуживания // АВТ. 1986. № 4. С. 28—33.

4. Смагин В. А. Об одном методе исследования немарковских систем // Изв. АН СССР. Техническая кибернетика. 1983. № 6. С. 31—36.

5. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988. 548 с.

Сведения об авторах

Владимир Александрович Смагин — д-р техн. наук, профессор; Военно-космическая академия им. А. Ф. Мо-

жайского, кафедра метрологического обеспечения, Санкт-Петербург;

E-mail: va_smagin@mail.ru

Иван Юрьевич Парамонов

— канд. техн. наук; Военно-космическая академия им. А. Ф. Можайско-

го, отдел перспектив развития АСУ и связи, Санкт-Петербург; на-

чальник отдела; E-mail: ivan_paramonov@mail.ru

Рекомендована отдел перспектив развития АСУ и связи

Поступила в редакцию 15.05.12 г.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 12