Проектирование производительности ЛВС
Наиболее широко распространенные классы количественных индексов производительности для вычислительных систем перечислены в табл. 1. Из общих определений, данных в той же таблице, очевидно, что индексы продуктивности имеют размерность объем 7 & 0 время 5-1 0, индексы реактивности - размерность времени, а индексы использования безразмерны. В настоящее время не существует стандартизированного единого способа измерения объема, или количества информации, переработанной системой. Таким образом, в зависимости от системы и от ее рабочей нагрузки будут использоваться различные меры объема; среди наиболее распространенных можно назвать: задание, программу, процесс, шаг задания, задачу, сообщение, взаимодействие (обмен сообщениями), команду. Перечислить все значения, приписанные ранее и приписываемые ныне этим терминам в литературе по вычислительным системам, по-видимому, невозможно. Здесь мы только отметим, что все они до некоторой степени зависят от природы рабочей нагрузки, от языка, на котором программисты описывают свои алгоритмы для машины, от внутреннего языка машины и от способа организации системы. Таким образом, ни одна из этих мер не обладает свойством независимости от рабочей нагрузки и свойством независимости от системы - это два свойства, необходимые для того, чтобы можно было установить некоторую меру объема информации в качестве универсальной. .
- 11 -
АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ОСНОВЕ ТЕОРИИ
СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
ОБЩИЕ ПОЛОЖЕНИЯ
При аналитическом моделировании исследование процессов или объектов заменяется построением их математических моделей и исследованием этих моделей. В основу метода положены идентичность формы уравнений и однозначность соотношений между переменными в уравнениях, описывающих оригинал и модель. Поскольку события, происходящие в локальных вычислительных сетях, носят случайный характер, то для их изучения наиболее подходящими являются вероятностные математические модели теории массового обслуживания. Объектами исследования в теории массового обслуживания являются системы массового обслуживания (СМО) и сети массового обслуживания (СеМО).
Системы массового обслуживания классифицируются по следующим признакам:
- закону распределения входного потока заявок;
- числу обслуживающих приборов;
- закону распределения времени обслуживания в обслуживающих приборах;
- числу мест в очереди;
- дисциплине обслуживания.
Для краткости записи при обозначении любой СМО принята система кодирования A/B/C/D/E, где на месте буквы ставятся соответствующие характеристики СМО:
А - закон распределения интервалов времени между поступлениями заявок. Наиболее часто используются следующие законы распределения: экспоненциальное (М), эрланговское (Е), гиперэкспоненциальное (Н), гамма-распределение (Г), детерминированное (D). Для обозначения произвольного характера распределения используется символ G;
В - закон распределения времени обслуживания в приборах СМО. Здесь приняты такие же обозначения, как и для распределения интервалов между поступлениями заявок;
С - число обслуживающих приборов. Здесь приняты следующие обозначения: для одноканальных систем записывается 1, для многоканальных в общем случае - l (число каналов);
D - число мест в очереди. Если число мест в очереди не ограничено, то данное обозначение может опускаться. Для конечного числа мест в очереди в общем случае приняты обозначения r или n (число мест);
Е - дисциплина обслуживания. Наиболее часто используются следующие варианты дисциплины обслуживания: FIFO (первым пришел - первым вышел), LIFO (последним пришел - первым вышел), RANDOM (случайный порядок обслуживания) . При дисциплине обслуживания FIFO данное обозначение может опускаться.
Примеры обозначений:
М/М/1 - СМО с одним обслуживающим прибором, бесконечной очередью, экспоненциальными законами распределения интервалов времени между поступлениями заявок и времени обслуживания, дисциплиной
- 12 -
обслуживания FIFO;
Е/Н/l/r/LIFO - СМО с несколькими обслуживающими приборами, конечной очередью, эрланговским законом распределения интервалов между поступлениями заявок, гиперэкспоненциальным распределением времени обслуживания в приборах, дисциплиной обслуживания LIFO;
G/G/l - СМО с несколькими обслуживающими приборами, бесконечной очередью, произвольными законами распределения времени между поступлениями заявок и времени обслуживания, дисциплиной обслуживания FIFO.
Для моделирования ЛВС наиболее часто используются следующие типы СМО:
1) одноканальные СМО с ожиданием - представляют собой один обслуживающий прибор с бесконечной очередью. Данная СМО является наиболее распространенной при моделировании. С той или иной долей приближения с ее помощью можно моделировать практически любой узел ЛВС;
2) одноканальные СМО с потерями - представляют собой один обслуживающий прибор с конечным числом мест в очереди. Если число заявок превышает число мест в очереди, то лишние заявки теряются. Этот тип СМО может быть использован при моделировании каналов передачи в ЛВС;
3) многоканальные СМО с ожиданием - представляют собой несколько параллельно работающих обслуживающих приборов с общей бесконечной очередью. Данный тип СМО часто используется при моделировании групп абонентских терминалов ЛВС, работающих в диалоговом режиме;
4) многоканальные СМО с потерями - представляют собой несколько параллельно работающих обслуживающих приборов с общей очередью, число мест в которой ограничено. Эти СМО, как и одноканальные с потерями, часто используются для моделирования каналов связи в ЛВС;
5) одноканальные СМО с групповым поступлением заявок - представляют собой один обслуживающий прибор с бесконечной очередью. Перед обслуживанием заявки группируются в пакеты по определенному правилу;
6) одноканальные СМО с групповым обслуживанием заявок представляют собой один обслуживающий прибор с бесконечной очередью. Заявки обслуживаются пакетами, составляемыми по определенному правилу. Последние два типа СМО могут использоваться для моделирования таких узлов ЛВС, как центры (узлы) коммутации.
В таблице 2 приведены условные обозначения и схемы данных систем массового обслуживания.
Локальная вычислительная сеть в целом может быть представлена в виде сети массового обслуживания. Различают открытые, замкнутые и смешанные сети.
1Открытой 0 называется сеть массового обслуживания, состоящая из М узлов, причем хотя бы в один из узлов сети поступает извне входящий поток заявок, и имеется сток заявок из сети. Для открытых сетей характерно то, что интенсивность поступления заявок в сеть не зависит от состояния сети, т.е. от числа заявок, уже поступивших в сеть. Открытые сети используются для моделирования ЛВС, работающих в неоперативном режиме. Пример такой модели дан
- 13 -
на рис. 1. Здесь системы S1 и S2 моделируют работу узлов коммутации, системы S3 и S4 - работу серверов и системы S5 и S6 - работу межузловых каналов. В сети циркулируют два потока заявок. Каждая заявка поступает на вход соответствующего узла коммутации, где определяется место ее обработки. Затем заявка передается на "свой" сервер или по каналу связи - на "соседний" сервер, где обрабатывается, после чего возвращается к источнику и покидает сеть.
1Замкнутой 0 называется сеть массового обслуживания с множеством узлов М без источника и стока, в которой циркулирует постоянное число заявок. Замкнутые СеМО используются для моделирования таких ЛВС, источниками информации для которых служат абонентские терминалы, работающие в диалоговом режиме. В этом случае каждая группа абонентских терминалов предтавляется в виде многоканальной системы массового обслуживания с ожиданием и включается в состав устройств сети.
Различают простой и сложный режимы работы диалоговых абонентов. В простом режиме абоненты не производят никаких действий, кроме посылки заданий в ЛВС и обдумывания полученного ответа. Пример такой модели дан на рис. 2. Здесь системы S01 и S02 моделируют работу групп абонентских терминалов 1 и 2, системы S7 и S8 моделируют работу каналов связи с абонентами, системы S1 и S2 - работу узлов коммутации (моста), системы S3 и S4 - работу серверов и системы S5 и S6 - работу каналов межузловой связи. Абоненты с терминалов посылают запросы, которые по каналам связи поступают на узлы коммутации, а оттуда - на обработку на "свой" или ""соседний" сервер. Дальнейшая обработка осуществляется так же, как в сети на рис. 1.
При сложном режиме диалога работа абонентов представляется в виде совокупности операций некоего процесса, называемого 1техноло1гическим процессом 0. Каждая операция технологического процесса моделируется соответствующей СМО. Часть операций предусматривает обращение к ЛВС, а часть операций может такого обращения не предусматривать. Пример моделирования ЛВС со сложной структурой диалога абонентов с помощью замкнутых СеМО дан на рис. 3. Здесь имеются две группы абонентов, каждый абонент в процессе работы совершает несколько операций, причем часть из этих операций предусматривает обращение к ЛВС. Алгоритм работы самой ЛВС такой же, как для сети на рис. 2.
1Смешанной 0 называется сеть массового обслуживания, в которой циркулирует несколько различных типов заявок (трафика), причем относительно одних типов заявок сеть замкнута, а относительно других типов заявок сеть открыта. С помощью смешанных СеМО моделируются такие ЛВС, часть абонентов которых работает в диалоговом, а часть - в неоперативном режиме. Для диалоговых абонентов также различают простой и сложный режим работы. Часто смешанные СеМО моделируют ЛВС, в которых сервер дополнительно загружается задачами, решаемыми на фоне работы самой сети.
Пример моделирования ЛВС с простым режимом работы диалоговых абонентов с помощью смешанных СеМО дан на рис. 4. Алгоритм работы сети для диалоговых абонентов аналогичен алгоритму работы сети на рис. 2, а алгоритм работы сети для неоперативных абонентов - ал-
- 14 -
горитму работы сети на рис. 1.
Различают экспоненциальные и неэкспоненциальные модели ЛВС. 1Экспоненциальные модели 0 основаны на предположении о том, что потоки заявок, поступающие в ЛВС, являются пуассоновскими, а время обслуживания в узлах ЛВС имеет экспоненциальное распределение. Для таких сетей получены точные методы для определения их характеристик; трудоемкость получения решения зависит в основном от размерности сети.
Однако в большинстве сетей (и локальных сетей в частности) потоки не являются пуассоновскими. Модели таких сетей называются 1неэкспоненциальными 0. При анализе неэкспоненциальных сетей в общем случае отсутствуют точные решения, поэтому наибольшее применение здесь находят приближенные методы.
Одним из таких методов является метод диффузионной аппроксимации. Использование диффузионной аппроксимации позволило, к настоящему времени получить приближенные аналитические зависимости для определения характеристик всех типов СМО, рассмотренных выше. При этом не требуется точного знания функций распределения случайных величин, связанных с данной СМО (интервалов между поступлениями заявок временем обслуживания в приборах), а достаточно только знание первого (математического ожидания) и второго (дисперсии или квадрата коэффициента вариации - ККВ) моментов этих величин.
Применение диффузионной аппроксимации при анализе ЛВС основано на следующем:
1) по каждому типу заявок вычисляется интенсивность поступления заявок данного типа в узлы сети так, как если бы данный поток заявок циркулировал в сети только один;
2) по определенному правилу, зависящему от типа СМО и дисциплины обслуживания, складываются потоки заявок от всех источников;
3) по определенному правилу определяется среднее время обслуживания в каждом узле ЛВС;
4) полученные значения подставляются в соответствующую диффузионную формулу и определяются характеристики узлов ЛВС;
5) определяются характеристики ЛВС в целом.
Постановка задачи анализа ЛВС при этом примет следующий вид.
Дано:
число узлов ЛВС;
тип каждого узла ЛВС (тип СМО, моделирующей данный узел);
дисциплина обслуживания в каждом узле ЛВС;
общее число типов источников заявок, работающих в диалоговом режиме;
общее число типов источников заявок, работающих в неоперативном режиме;
для диалоговых источников в случае сложного режима работы - число технологических процессов каждого типа, число операций в каждом технологическом процессе, среднее и ККВ времени выполнения каждой операции, матрица вероятностей передач между операциями, а также наличие или отсутствие на каждой операции обращения к ЛВС;
для диалоговых источников в случае простого режима работы - число источников (терминалов) каждого типа, среднее и ККВ времени
- 15 -
реакции абонента на ответ сети;
для неоперативных абонентов - средняя интенсивность поступления заявок и ККВ времени между поступлениями заявок;
по каждому типу заявок (диалоговому и неоперативному) - средняя интенсивность обслуживания в каждом узле ЛВС, ККВ времени обслуживания в узлах ЛВС и матрица вероятностей передач между узлами.
Требуется найти:
среднее значение и дисперсию (или стандартное отклонение) времени задержки заявки каждого типа в ЛВС в целом;
среднее значение и дисперсию (или стандартное отклонение) времени задержки в узлах ЛВС;
загрузку узлов ЛВС;
вероятность потери заявки в узле ЛВС (для узлов, моделируемых СМО с потерями).
Ограничения могут быть следующими:
загрузка узлов не должна превышать 1;
вероятность потери заявки не должна превышать 1;
все характеристики должны быть положительны.
Иногда представляет интерес определение такого показателя, как максимальное время задержки заявки каждого типа в ЛВС. 1Макси1мальное время 0 - это такое время, превышение которого допустимо лишь для некоторого, наперед заданного процента заявок каждого типа. Для определения максимального времени используется методика, основанная на аппроксимации функции распределения времени задержки в сети эрланговским или гиперэкспоненциальным распределением, при этом необходимо задавать долю (процент) заявок, для которых рассчитывается максимальное время.
ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА МОДЕЛИРОВАНИЯ
Существует довольно значительное количество ППП, автоматизирующих процессы разработки и исследования аналитических моделей вычислительных систем и сетей. Рассмотрим один из них, достаточно простой и удобный в использовании, - ППП "ДИФАР". В основу его построения положены изложенные выше положения моделирования систем и сетей массового обслуживания.
Пакет ДИфАР предназначен для аналитического моделирования и оптимизации систем, сетей массового обслуживания и сетевых систем. Он позволяет рассчитывать вероятностно-временные характеристики СМО, СеМО и сетевых систем, задавая в качестве параметров два момента входных потоков и обслуживания, что позволяет исследовать поведение систем в широком диапазоне изменений как средних значений, так и дисперсий потоков и обслуживания, а также найти оптимальное построение сетевых систем по значениям вероятностно-временных характеристик (ВВХ), адекватных фактическим распределениям.
Пакет ДИФАР обеспечивает расчет:
- системных характеристик для одноканальных и многоканальных систем массового обслуживания без ограничений на емкости буферных накопителей (среднее значение и дисперсия времени пребывания, максимальное время пребывания для r процентов заявок, загрузка);
- 16 -
- системных характеристик для одноканальных и многоканальных систем массового обслуживания, учитывающих ограничения на емкости буферных накопителей (среднее значение и дисперсия времени пребывания, максимальное время пребывания для r процентов заявок, вероятность отказа в обслуживании, загрузка);
- системных характеристик для одноканальных систем массового обслуживания с групповым поступлением заявок или групповым обслуживанием заявок (среднее значение и дисперсия времени пребывания заявки, максимальное время пребывания для r процентов заявок, загрузка);
- системных и сетевых характеристик открытых неоднородных сетей массового обслуживания с узлами различных типов (среднее значение и дисперсия времени пребывания в сети, максимальное время пребывания в сети для r процентов заявок, среднее значение и дисперсия времени пребывания в каждом узле сети, максимальное время пребывания в каждом узле для r процентов заявок, загрузка узлов сети, вероятности отказов в обслуживании в узлах);
- системных и сетевых характеристик замкнутых и смешанных неоднородных сетей массового обслуживания с узлами различных типов, с простым режимом работы диалоговых абонентов (среднее значение и дисперсия времени пребывания в сети заявки каждого типа, максимальное время пребывания в сети для r процентов заявок каждого типа, среднее значение и дисперсия времени пребывания в каждом узле сети, загрузка узлов сети, вероятности отказов в обслуживании в узлах);
- системных и сетевых характеристик замкнутых и смешанных неоднородных сетей массового обслуживания с узлами различных типов со сложным режимом работы диалоговых абонентов (среднее значение и дисперсия времени цикла технологического процесса работы каждого диалогового абонента, максимальное время цикла для r процентов технологических процессов каждого типа, среднее значение и дисперсия времени пребывания в сети заявки каждого типа, максимальное время пребывания в сети для r процентов заявок каждого типа, среднее значение и дисперсия времени пребывания в каждом узле сети, загрузка узлов сети, вероятности отказов в обслуживании в узлах);
- показателей производительности сетевых систем, в качестве моделей которых используются открытые, замкнутые и смешанные сети массового обслуживания (локальные вычислительные сети, информационно-вычислительные сети, центры коммутации пакетов и др.) .
Пакет программ позволяет проводить анализ сетевых систем, включающих от 30 (замкнутые и смешанные сети со сложным режимом работы диалоговых абонентов) до 50 узлов СМО (открытые, замкнутые и смешанные сети с простым диалогом) на PC XT/AT с 512 Кбайтами оперативной памяти.
Ниже приведены примеры моделирования некоторых локальных вычислительных сетей. Результаты расчетов характеристик данных сетей получены с помощью пакета ДИФАР.
- 17 -
ПРИМЕРЫ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ ЛВС
2Пример 1 0. Рис. 5 иллюстрирует работу локальной сети с электронной почтой на базе городской телефонной сети (модель с потерями заявок). На вход каждого узла сети поступает поток заявок с некоторой интенсивностью. Системы S1 - S6 моделируют работу телефонных каналов. Если канал в требуемом направлении занят, то заявка теряется.
Исходные данные:
Устройство Среднее время ККВ времени
обслуживания обслуживания
1 7,69 с 2,0
2 7,69 с 2,0
3 7,69 с 2,0
4 7,69 с 2,0
5 7,69 с 2,0
6 7,69 с 2,0
Интенсивность поступления заявок от каждого источника - 0,3 з/с.
Результаты расчета:
среднее время задержки в сети - 15,0477 с;
стандартное отклонение времени