Реферат: Проектирование производительности ЛВС
на в виде сети массового обслуживания. Различают открытые, замк-
нутые и смешанные сети.
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 с;
стандартное отклонение времени задержки в сети - 18,7703;
максимальное время задержки в сети для 90% заявок - 35,2611
с.
Характеристики устройств:
Среднее время Стандартное от- Загрузка Вероятность
задержки, с клонение времени потери
задержки
1 7,69231 10,8786 0,451431 0,022396
2 7,69231 10,8786 0,451431 0,022396
3 7,69231 10,8786 0,451431 0,022396
4 7,69231 10,8786 0,451431 0,022396
5 7,69231 10,8786 0,451431 0,022396
6 7,69231 10,8786 0,451431 0,022396
2Пример 2. 0 Рис. 6 иллюстрирует работу локальной сети с элект-
ронной почтой на телефонной сети (модель с ожиданием и без потерь
заявок). Системы S1, S5, S9 моделируют работу передатчика инфор-
мации (узла коммутации). Системы S2, S3, S6, S7, S10, S11 модели-
руют задержку в каналах связи между соответствующими узлами. Сис-
темы S4, S8, S12 моделируют работу приемника информации (ЭВМ).
Принцип работы следующий.
Абонент узла 1 готовит письмо, которое поступает на узел
коммутации (система S1), где определяется адресат письма и осу-
ществляется передача в нужном направлении. Если адресатом являет-
ся абонент узла 2, то письмо передается по каналу S3, а если ад-
ресат - абонент узла 3, то передача осуществляется по каналу S2.
- 18 -
В случае занятости канала передатчик ожидает его освобождения,
после чего производит передачу. На приемном конце стоит персо-
нальная ЭВМ с жестким магнитным диском, куда записывается полу-
ченное письмо. Письма от абонентов других узлов передаются анало-
гично.
Исходные данные:
Устройство Среднее время ККВ времени
обслуживания обслуживания
1 12,000 с 0,5
2 3,410 с 2,0
3 3,410 с 2,0
4 0,016 с 2,0
5 12,000 с 0,5
б 3,410 с 2,0
7 3,410 с 2,0
8 0,016 с 2,0
9 12,000 с 0,5
10 З,410 с 2,0
11 3,410 с 2,0
12 0,016 с 2,0
Интенсивность поступления заявок от каждого источника - 0,04
з/с,
Результаты расчета:
среднее время задержки в сети - 33,1653 с;
стандартное отклонение времени задержки в сети - 26,0897;
максимальное время задержки в сети для 90% заявок - 67,1629
с.
Характеристики устройств:
Среднее время Стандартное от- Загрузка
задержки, с клонение времени
задержки
1 29,7505 25,6393 0,4819280
2 3,41322 1,82667 0,0013930
3 3,41322 1,82667 0,0013930
4 0,01600 0,00226 0,000001З
5 29,7505 25,6393 0,4819280
6 3,41322 1,82667 0,0013930
7 3,41322 1,82667 0,0013930
8 0,01600 0,00226 0,0000013
9 29,7505 25,6393 0,4819280
10 3,41322 1,82667 0,0013930
11 3,41322 1,82667 0,0013930
12 0,01600 0,00226 0,000001З
2Пример 3 0. Рис. 7 моделирует работу локальной сети по продаже
билетов. Детально моделируется только работа одного абонентского
пункта, потоки заявок от остальных пунктов сети представляются в
- 19 -
виде некоторого общего внешнего потока.
Система S1 моделирует работу центрального процессора компь-
ютера, установленного в пункте продажи билетов. Система S2 моде-
лирует работу принтера данного компьютера. Система S3 моделирует
задержку в канале передачи к серверу при посылке запроса на би-
лет. Система S4 моделирует задержку в канале передачи от сервера
на абонентский пункт при ответе на запрос. Система S5 моделирует
работу сервера в центральном пункте сети.
Принцип работы схемы следующий.
Посетитель делает заказ на билет (операция 1). Оператор на-
бирает запрос на клавиатуре и посылает его в центральную базу
данных на сервер (операция 2). После получения ответа клиент при-
нимает решение (операция 3). С вероятностью 0,1 требуемого билета
нет, и клиент уходит. С вероятностью 0,3 требуемого билета нет, и
клиент просит послать запрос на другой билет. С вероятностью 0,6
требуемый билет имеется, оператор посылает в базу данных заявку
на этот билет и после получения ответа печатает билет на принтере
(операция 4). Затем клиент расплачивается, проверяет билет и ухо-
дит (операция 5). Работа остальных пунктов сети моделируется об-
щим потоком со средней интенсивностью 100 з/мин, которые поступа-
ют непосредственно на сервер.
Исходные данные.
Техпроцесс:
Среднее время выпол- ККВ времени
нения операции, мин выполнения операции
1 2,0 2,0
2 1,0 2,0
3 4,0 2,0
4 1,0 2,0
5 4,0 2,0
Локальная сеть:
Среднее время обслужи- ККВ времени обслужи-
вания в устройстве, мин вания в устройстве
1 0,1000 2,0
2 0,1500 2,0
3 0,0220 2,0
4 0,0022 2,0
5 0,0001 2,0
Результаты расчета.
Характеристика техпроцесса:
Среднее время цикла - 11,4027 мин
Стандартное отклонение времени цикла - 8,8591
Максимальное время цикла
для 90% случаев) - 22,9642 мин
- 20 -
Характеристики запроса 1:
Среднее время задержки в сети - 0,245675 мин
Стандартное отклонение задержки - 0,284096
Максимальное время задержки
(для 90% случаев) - 0,574786 мин
Характеристики запроса 2:
Среднее время задержки в сети - 0,361328 мин
Стандартное отклонение задержки - 0,497105
Максимальное время задержки
(для 90% случаев) - 0,839882 мин
Характеристики устройств:
Среднее время Стандартное от- Загрузка
задержки, мин клонение времени
задержки
1 0,109870 0,146328 0,0311816
2 0,257241 0,357637 0,0073082
3 0,022222 0,003143 0,0000282
4 0,002222 0,031427 0,0002815
5 0,001488 0,001718 0,1001267
.
ЛИТЕРАТУРА
1. Локальные вычислительные сети. Книги 1-3.
Под ред. Назарова С.В.
Москва "Финансы и статистика" 1995
2. Д. Феррари.
Оценка производительности вычислительных систем.
Москва "Мир" 1981
3. Максименков А.В., Селезнев М.Л.
Основы проектирования информационно-вычислительных систем
и сетей ЭВМ.
Москва "Радио и связь" 1991
