Вычислительные сети, теория и практика.

АНАЛИЗ И ПРОЕКТИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ (часть 2)

Абросимов Л. И.

2. МЕТОД КОНТУРОВ ДЛЯ ОЦЕНКИ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ

2.1. Основные положения и определения

Вычислительные сети характеризуются большой сложностью составляющих элементов, связей, взаимодействий, параметров и характеристик. При построении моделей основное внимание уделяется тем характеристикам и параметрам, которые интересуют исследователя - проектировщика.

К основным понятиям рассматриваемой модели относятся структура и составляющие ее компоненты.

Под структурой модели вычислительной сети понимаются условия и средства соединения компонентов сети ( рис.2).

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

Узел моделируемой сети — это аппаратные и программные средства файл-сервера, хостмашины, коммуникационного контроллера, терминала (см. рис. 2). Каждый узел при обработке осуществляет задержку сообщений и поэтому моделируется одноканальной системой массового обслуживания M/M/1/ (рис. 3).

Основными параметрами сообщений являются: интенсивность поступления сообщений и интенсивность обслуживания сообщений в узле.

Интенсивность поступления сообщений равна усредненному количеству сообщений, поступающих на вход узла в единицу времени.

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

Основными характеристиками узлов, как систем массового обслуживания являются:

время обслуживания сообщений узлом, где
(1)

время задержки t сообщений в системе i (в узле и очереди на обслуживание) :
(2)

коэффициент загрузки узла i:
(3)

количество сообщений в системе обслуживания (в узле и очереди на обслуживание)
(4)

количество сообщений в очереди на обслуживание:
(5)

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

Количество сообщений в открытой системе определяется по формуле Литтла (6).

Если обслуживающая система содержит несколько узлов, а поток сообщений с выхода последнего узла поступает на вход первого узла , то такая система называется замкнутой системой, а интенсивность потока сообщений является неизвестной величиной, зависящей от параметров и структуры соединения узлов. (рис. 6 )

Для замкнутой системы применение формул (4, 5), выведенных для одноканальной системой массового обслуживания M/M/1/, приводит при небольших количествах сообщений (n= 1 — 10) к значительным погрешностям. Для уменьшения погрешности при расчете характеристик замкнутых систем необходимо использовать коэффициент ограниченности очереди:

= ( —)/; где = 0 |; = 1|.

Тогда соотношения (4, 5) преобразуются к следующему виду:

количество сообщений в замкнутой системе обслуживания (в узле и в очереди на обслуживание):
(6)

количество сообщений в очереди на обслуживание к узлу i в замкнутой системе обслуживания:
(7)

В вычислительных сетях можно выделить потоки сообщений, каждый из которых в установившемся режиме имеет свой путь прохождения через узлы сети и свои параметры обслуживания в узлах. Такой условно выделенный путь движения сообщений назван контуром , где . Контуры могут быть разомкнутыми (см. рис. 5, 8) и замкнутыми (см. рис.6, 7).

Разомкнутый контур — это путь потока идентичных сообщений от входа в сеть через промежуточные узлы к выходу из сети.

Замкнутый контур — это путь потока идентичных сообщений от узла-источника до обслуживающего узла и обратно.

Фаза контура — это часть контура, в которой каждый узел только один раз обслуживает сообщение.

Пример 2.1 (см. рис 7) : замкнутый контур содержит узлы: (A)¾k₁¾k₂¾k₃¾(B)¾k₂¾(A).

Пример 2.2 (рис 7) : Фаза =1 содержит узлы: (A)¾k₁¾k₂¾k₃¾(B). Фаза = 2 содержит узлы: (B)¾k₂¾(A).

В реальных сетях в стационарном режиме сообщения с выхода одного узла могут поступать на входы различных узлов. При моделировании такие переходы от узла k_i к узлу k_j оцениваются вероятностью перехода сообщений (см. рис 9).

Вероятности перехода позволяют для разомкнутых контуров выразить интенсивность потока сообщений любого перехода через базовую интенсивность потока сообщений и коэффициент базовой интенсивности. Базовую интенсивность потока сообщений обычно представляет поток сообщений, поступающий на вход узла. Коэффициент базисной интенсивности, показывает, какая часть базисной интенсивности переходит от узла k_i к узлу k_j, т.е.:
(8)

Пример 2.3 (см. рис 9):

a₁₂ = p₁₂ ; a₁₃ = p₁₃ ; a₂₄ = p₁₂× p₂₄ = p₁₂ ;

a₃₄ = = p₁₃× p₃₄ ; a₃₅ = p₁₃× p₃₅;

a₄₅ = (a₂₄ + a₃₄)p₄₅ = a₂₄ + a₃₄.

2.2. Линейные уравнения

Линейные уравнения являются одной из составных частей аналитической модели метода контуров. Составление и последующее их совместное решение позволяет для потоков каждого контура q определить коэффициенты базовой интенсивности.

В основу составления линейного уравнения положено условие, что для установившегося процесса движения сообщений одного контура количество входящих в узел k_i сообщений равно количеству сообщений его покидающих и поступающих на вход следующего узла k_j (рис 10).

Тогда для каждого контура , каждого узла и для каждой дуги можно записать:
(9)

Пример 2.4. (см. рис. 9):

Система линейных уравнений имеет вид:

= ; = ; = ;

= ; = ; = ( + ).

Решая системы линейных уравнений, получаем:

= ; = ; = ; = ; = ; = +

2.3. Нелинейные уравнения

Нелинейные уравнения также являются частью аналитической модели метода контуров. Каждое нелинейное уравнение составляется для одного контура. Составление и последующее их совместное решение позволяет для потоков всех контуров сети определить базовые интенсивности. . Основу составления каждого нелинейного уравнения составляет условие, что для установившегося процесса движения сообщений одного контура количество сообщений в контуре не изменяется и равно сумме математических ожиданий сообщений рассматриваемого контура во всех узлах сети. Тогда для каждого контура можно записать:
(10)

Пример 2.5 (см.рис.11):

Рассматриваемая система содержит два замкнутых контура.

контур q = 1 содержит в своем составе узлы: k₁¾k₃¾k₄¾k₃¾(k₁ ; первая фаза = 1 содержит узлы k₁—k₃—k₄ ; вторая фаза = 2 содержит узел k₃ . контур q= 2 содержит в своем составе узлы: k₂¾k₃¾k₄¾k₃¾(k₂ ; первая фаза = 1 содержит узлы k₂—k₃—k₄_..; вторая фаза = 2 содержит узел k₃.

Система нелинейных уравнений для рис. 11 на основании (6) и (10) может быть записана в следующем виде:

(11)

где .

2.4. Решение нелинейных уравнений

Целью решения системы нелинейных уравнений является вычисление базисных интенсивностей для каждого контура . В качестве базисной обычно выбирается дуга контура , выходящая из узла k_i с наименьшим номером i.

Анализ соотношений (6) и (10) показывает, что каждое нелинейное уравнение в области допустимых решений представляет собой монотонно возрастающую функцию. Вид зависимости () для первого нелинейного уравнения примера 2.5 представлен на рис 12.

На рис. 12 номера "1", "3", "4" — соответствуют номерам узлов первого контура, которые описываются слагаемыми в соотношении (11). Знаком обозначена вся правая часть первого нелинейного уравнения.

Для решения системы нелинейных уравнений используем итеративный метод дихотомии, называемый также "метод проб" [9].

Для этого представим соотношение (10) в канонической форме:
(12)

Каноническая форма нелинейного уравнения (12) изображена на рис 13.

Решению уравнения соответствует равенство: () = 0.

В основу процедуры решения нелинейного уравнения положены следующие условия:

1) если корень уравнения лежит между = и = , то вычисляют {( + )/2};

2) если {(+)/2}.имеет тот же знак, что и (), то присваивают = ( + )/2 , а не изменяют и повторяют процедуру вычисления ();

3) если {(+)/2} имеет тот же знак, что и (), то присваивают = ( + )/2 , а не изменяют и повторяют процедуру вычисления ();

4) расчет продолжается до тех пор, пока на шаге будет достигнуто условие:

= |( ) — ()| /( ) < , где

— заданная точность вычислений.

Ответственным является шаг = 0, на котором назначаются значения граничных величин: и .

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

Пример 2.6. (см. рис. 10): для контура = 1, n₁=3; m₁=1 1/s;

m₃=4 1/s; m₄=3 1/s , );

для контура = 2 n₂=4; m₂=2 1/s; m₃=4 1/s; m₄=3 1/s (точность вычислений = 6%).

По соотношению (11) вычисляем :

g₁=0,67; g₂=0,75; g₃=0,86; g₄=0,86 .

Последовательно для каждого контура и каждого шага вычисляем: (q,s), (q,s), f(q,s), (s):

s=0 L_B(1,0)=0; L_E(1,0)=1; L_B(2,0)=0; L_E(2,0)=2 ;

s=1 l₁(1)=0,5; l₂(1)=1; f(1,1)=1,26; f(2,1)=1,22 ;

L_B(1,1)=0,5; L_E(1,1)=1; L_B(2,1)=1; L_E(2,1)=2 ;

s=2 l₁(2)=0,75; l₂(2)=1,5; f(1,2)= -10,75; f(2,2)= -22,2;

L_B(1,2)=0,5; L_E(1,2)=0,75; L_B(2,2)=1; L_E(2,2)=1,5;

s=3 l₁(3)=0,62; l₂(3)=1,25; f(1,3)=-0,09; f(2,3)=-0,94;

L_B(1,3)=0,5; L_E(1,3)=0,62; L_B(2,3)=1,0; L_E(2,3)=1,25;

s=4 l₁(4)=0,56; l₂(4)=1,13; f(1,4)=0,72; f(2,4)=0,22;

L_B(1,4)=0,56; L_E(1,4)=0,62; L_B(2,4)=1,13; L_E(2,4)=1,25.

С заданной точностью = 6% получаем,

l₁ = 0,59 1/s, l₂ = 1,19 1/s.

2.5. Определение функциональных характеристик

Каждый узел вычислительной сети характеризуется временем обслуживания сообщений, которое зависит от объема заданий и производительности узла:
(13)

Если узел моделирует компьютер, то объем заданий измеряется в операциях, а производительность узла измеряется в операциях в секунду. Если узел моделирует аппаратуру связи, то объем заданий измеряется в битах, а производительность узла измеряется в битах в секунду.

После того, как определены интенсивности потоков сообщений каждого контура в каждом узле k_i вычислительной сети можно определить основные характеристики вычислительной сети.

Среднее время доставки сообщений контура в разомкнутой сети:
(14)

Среднее время отклика сообщений замкнутого контура , содержащего сообщений, каждое из которых генерируется узлом k_i :
(15)

Коэффициент загрузки узла i:
(16)

2.6. Стадии метода контуров

Изложенные основные определения позволяют сформулировать следующие этапы метода контуров:

- описание структуры вычислительной сети,

- описание функциональной схемы вычислительной сети,

- представление графовой модели вычислительной сети,

- составление линейных уравнений баланса,

- составление нелинейных уравнений баланса,

- решение линейных уравнений баланса,

- решение нелинейных уравнений баланса,

- определение функциональных характеристик ВС.

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

Переход к функциональной схеме вычислительной сети отражает требования проектировщика-исследователя к степени детализации построения модели, т.е. функциональная схема содержит те элементы сети, которые вносят, по-мнению проектировщика существенные задержки времени в обработку сообщений. На этой стадии определяются контуры и фазы поступающих на обслуживание потоков сообщений, а также интенсивности обслуживания сообщений в узлах.

Графовая модель служит для формализорванного представления функциональной модели и позволяет символьно определить все параметры и характеристики для математического описания модели. При наличии узлов, имеющих идентичные интенсивности обслуживания вводятся типы узлов обслуживания.

Составление линейных уравнений баланса выполняется в соответствии с пояснениями, изложенными в параграфе 2.2. и записывается в виде соотношения (9).

Составление нелинейных уравнений баланса выполняется в соответствии пояснениями, изложенными в параграфе 2.3. и записывается в виде соотношения (10).

Решение системы линейных уравнений баланса направлено на определение коэффициентов базисной интенсивности для чего, в зависимости от размерности сети могут использоваться различные методы решения (подстановки или итеративные методы [9]).

Решение системы нелинейных уравнений баланса ставит своей целью вычисление базисных интенсивностей для замкнутых контуров. Для систем не большой размерности целесообразно использовать метод дихотомии, изложенный в разделе 2.4. Выбор метода решения для сетей большой размерности требует дополнительного анализа специфических особенностей каждой исследуемой сети.

Для определение функциональных характеристик вычислитель-ных сетей используются соотношения параграфа 2.5.

2.7.Упражнения

Контрольные вопросы

1. Какие условия являются главными для рассмотрения компоненты сети в качестве узла?

2. Какие характеристики трафика являются известными (заданными) для замкнутых и разомкнутых контуров?

3. Почему для замкнутых систем обслуживания с узлами M/M/1 и M/G/1 необходимо вводить коэффициент ограниченности очереди? В каком диапазоне он изменяется?

4. Сколько фаз может иметь контур?

5. Почему уравнения (9) называют линейным, а уравнение (10) — нелинейным?

6. Какие итеративные методы решения нелинейных уравнений Вам известны?

Задания

1. Разомкнутая система обслуживания А имеет интенсивность входного потока и время обслуживания . Разомкнутая система обслуживания В состоит из двух последовательно-соединенных узлов и имеет время обслуживания в каждом узле = /2. Для одинаковой интенсивности входного потока определите, какая система имеет большее время обслуживания? Может ли быть равным ?

2. Разомкнутая система обслуживания C состоит из двух параллельно соединенных узлов, входной поток сообщений с равными вероятностями поступает на входы каждого узла, который имеет время обслуживания = . Определите время обслуживания и сравните с и (см. Задание 1).