автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка и исследование алгоритмического и программного обеспечения методов проектирования интегральных сетевых систем

МИНИСТЕРСТВО СВЯЗИ РОССИЙСКОЙ ФЕДЕРАЦИЙ Московский технический университет связи и информатики

Р Г В ОД На правах рукописи

' ^ Гу: ...

Ерохин Андрей Густавович

УДК 681.31(075.8)

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМИЧЕСКОГО И ПР01РАШН0Г0 ОБЕСПЕЧЕНИЯ МЕТОДОВ ПРОЕКТИРОВАНИЯ ИНТЕГРАЛЬНЫХ СЕТЕВЫХ СИСТЕМ

Специальность 05.13.13 - Вычислительные машины, комплексы,

системы и сети

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1994

Раоота выполнена в йосковском техническом университете связи

н-ннформатики.-——------

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

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

Назаров отанислав иикторович, кандидат технических наук, доцент Шабанов Леонид Васильевич. Ведущее предприятие - центральный научно-исследовательский

институт связи министерства связи №.

Защита состоится " " (О(ОУУ> ¡Л&ри? 1994 года, в-/У с5с? часов на заседании епецвалиаированного совета к 118.06.02 по присуждению ученых степеней кандидата технических наук в ьгосковскоа ордена трудового фасного знамени техническом университете связи и информатики-по адресу: 1111£4, г. Москва, ул. Авиамоторная, д. ца.

С диссертацией шво ознакомиться в библиотеке университета. Автореферат разослан 1994 года.

Ученый секретать специализированного совета

К 118.06.02, доц. ¿ЗГ^ Е.В.Дешна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Основными ыетода?ха, нспользуе5Яши при ревении задачи анализа, являются методы аналитического, имитационного и детального событийном моделирования.

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

Основными аналитическими методами, используемыми для изучения процессов в вычислительных сетях, являются катоды теории массового обслукивання. Большинство суцествущих моделей систем и сетаа массового обслуживания основана на предгшохвЕиз об экспоненциальном характере распределения времени обслуживания и иуассояовсках потоках поступления заявок. В этом случае возможно точное решение, трудоемкость получения которого относительно невелика п определяется, в основном, размерностью сети, однако в большинстве сетей потоки не являются пуассоновскики. Известные в настоящее время методы анализа неэкспоненциальннх сетей не содерват явных аналитических формул, пригодных для использования, аффективное применение таких методов возможно только при разработке специальных процедур их реализации, включающих численные методы, алгоритмы и программы для ЭВМ.

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

¿51 з

систем.

-Под—сетевой—системой_в_работе___понимается совокупность

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

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

Согласно поставленной цели в диссертационной раооте решаются следующие задачи:

- разработка алгоритмического и программного обеспечения методов проектирования сетевых систем, в качестве моделей которых используются открытые, замкнутые и смешанные неоднородные неэкспонэвцналъные сети массового обслуживания;

- исследование точности методов проектирования указанных сетевых систем.

Методы исследования. Основными методами исследования, используемыми в настоящей работе, являются методы теории систем и сетей массового обслуживания. Для оценки вероятностно-временных характеристик отдельных узлов сетей массового обслуживания используются методы диффузионной аппроксимации. При нахождении вероятностно-временных характеристик сетей в целом используются математические методы катрищой алгебры, метод Гаусса для решения систем линейных уравнений и метод Брауна для решения систем нелинейных уравнений. При оценке точности аналитических методов расчета характеристик открытых и смешанных сетей в качестве базы для сравнения были использованы результаты имитационного моделирования, полученные с использованием оощецелевой системы моделирования СРББ. Для разработки црограммного обеспечения используется алгоритмический язык ФОРТРАН.

Научная новизна результатов диссертации состоит в следующем:

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

уравнений, метода диффузионной аппроксимации и методы определения моментов задержки в сети массового обслуживания.

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

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

4. Разработан пакет прикладных программ "Б1РАЯ" для анализа систем и сетей массового обслуживания, сетевых системно учетом двух моментов входных потоков и времени обслуживания, в основу которого положены процедуры и численные методы, разработанные в главах 2 и 3 настоящей диссертации.

Личный вклад. Все результаты, изложенные в диссертации, получены автором лично.

Практическая ценность. Разработанные в диссертации процедуры расчета вероятностно-временных характеристик открытых и смешанных моделей сетевых систем, реализованные в виде пакета прикладных программ "ВШЕ", используются при проектировании новых и анализе действующих технологий решения различных экономических задач с использованием сетевых систем, а также при проектировании и анализе различных вычислительных, информационно-вычислительных сетей, сетей передачи данных, цифровых сетей интегрального обслуживания. При этом время получения решения, по сравнению с имитационным моделированием, снижается в 2 - 10 раз.

Реализация результатов работы. Результата диссертационной работы в виде пакета прикладных программ "ЛХРАЯ" были использованы в

т

ходе выполнения опытно-конструкторской работы под шифром "Алиоек-М" в научно-исследовательском институте систем автоматизации, а также на Уфимском заводе коммутационной аппаратуры при решении задачи распределения заданий в системе управления заводом. Кроме того, результаты диссертации используются в учеоном процессе московского технического университета связи и информатики и московского коммерческого университета.

Апробация раооты. Основные результаты диссертации докладывались и оосувдались на У Всесоюзной конференции "Вычислительные сети коммутации пакетов" (Рига, 1987 г.), XIII, XIV, XVI Всесоюзных Школах-семинарах по вычислительным сетям (1988, 1989, 1991 гг.), XVII Международной школе-семинаре по вычислительным сетям (1992 г.), а такие на конференциях профессорско-преподавательского состава МТУСИ (1987 - 1993 гг.).

Публикации по раооте. Основные результаты диссертационной раооты онуоликс^аны в 9 печатных трудах.

Структура и осьем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 100 наименований и пяти приложений. Диссертация.включает 143 страницы основного текста, 33 рисунка и 15 таблиц,

Основные положения, выносимые на защиту;

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

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

- расчет параметров внутренних потоков;

- расчет характеристик узлов сети;

- расчет сетевых характеристик.

При этом результаты аналитического моделирования согласуются с результатами имитационного моделирования с доверительной

б

вероятностью 0.96. Относительная погрешность аналитических методов расчета по сравнению с имитационным моделированием не превышает 15 %, при среднем значении 4.5 *.

3. для получения характеристик сетевых систем, в качестве моделей которых используются смешанные неоднородные сети массового обслуживания с простой структурой. диалога, с относительной погрешностью та сравнению с результатами имитационного моделирования -не оолее 20 %, достаточно провести расчеты по разраоотанному в диссертации численному алгоритму в три этапа:

- расчет характеристик внутренних потоков в сети относительно внешних источников;

- расчет характеристик внутренних потоков в сети относительно диалоговых источников, характеристик общего штока и сетевых характеристик диалоговых потоков;

- расчет сетевых характеристик внешних штоков.

При этом среднее значение погрешности результатов аналитического моделирования по сравнению с имитационным моделированием составляет 7.6 %, результаты аналитического и имитационного моделирования согласуются с доверетельной вероятностью 0.98.

4. Использование для расчета показателей производительности сетевых систем, моделируемых смешанными сетями массового обслуживания со сложной структурой диалога абонентов, разработанного' в диссертации численного алгоритма позволяет получать результаты,, относительная погрешность которых по сравнению с имитационным моделированием не будет превышать 20 X при среднем значении 7.6 *. . Для этого достаточно провести расчеты в четыре этапа:

- расчет параметров внутренних потоков относительно внешних источников;

- расчет параметров внутренних потоков относительно диалоговых . источников, характеристик .общего .потока и сетевых характеристик диалоговых штоков;

- расчет характеристик технологических процессов;

- расчет сетевых характеристик внешних штоков.

Результаты аналитического и имитационного моделирования при этой согласуется с доверительной вероятностью 0.98.

5. Использование разработанного в диссертации программного обеспечения методов проектирования интегральных сетевых систем позволяет сократить время расчетов по сравнению с имитационным моделированием в 2 - 10 раз в зависимости от размерности сети*и

Ш - ■

типов узлов.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дано краткое описание_актуальности -рассматриваемой-

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

Первая глава посвящена анализу существующих методов исследования интегральных сетевых систем (ЯСС) и формализации постановки задачи анализа открытых и смешанных моделей сетевых систем.

В первом разделе приведена оощая модель интегральной сетевой системы-. 6 состав ИСС включаются:

- терминальная сеть передачи данных (ТС1Ш - источники информации и абонентские линии;

- базовая сеть передача данных (БСПД) - узлы коммутации и каналы межузловоя связи;

- обслуживающие машины-серверы.

Для дополнительной загрузки машин-серверов в сеть, помимо информации от удаленных источников, дополнительно поступают потоки информации от локальных источников, непосредственно соединеннвдх с сервером. Оощая структурная схема ИСС показана на рис. 1.

Во втором разделе определяются показатели качества функционирования ИСС. В настоящее время выделяют три группы критериев оценки качества функционирования ИСС:

- критерии ценности информации;

- критерии производительности сети;

- вероятностно-временных характеристики (БВХ).

В датой разделе рассматриваются все эти групш показателей, а также показатели экономической эффективности ИСС.

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

- применение аналитического моделирования по формулам расчета вероятностно-временнвх характеристик;

- использование, пакетов для разработки имитационных моделей ИСС и ее имитационное; моделирование;

локальные источники

^ ъ

удаленные источники

тспд

(53 ¿1

сервер|

удаленные источники

т

тспд

»к

-1 локальные

сервер| источники

I ^ ^

»к

оазовая сеть передачи данных

УК

локальные |сервер] источники 1-1

—"

I тспд I I _ , , !

УК

удаленные источники

ТСПД

►С? ►с?

I

¿1 ¿1

с? &

источники

удаленные источники

рис. 1. Структурная схема интегральной сетевой системы

- детальное событийное моделирование процессов передачи и обработки информации в ИСС на языках высокого уровня (например, Он-).

_В_четвертом разделе приведена общая постановка задачи анализа

открытых и смешанных моделей сетевых систем. Все потокиг циркулирующие в сетях, делятся на два типа: потоки ограниченного числа заявок, цирку лирушдах в сети, называемые диалоговым трафиком, и потоки неограниченной интенсивности,' называемые внешним, или фоновым, трафиком.

Для диалогового трафика задается: число диалоговых источников каждого типа (М1), среднее и дисперсия времени реакции диалоговго абонента (1/T)i, s|). Для внешнего трафика задается интенсивность и квадрат коэффициента вариации (ККВ) интервалов поступления в сеть внешних заявок каждого типа (К±, с|). По каждому типу трагика вводится среднее и ККВ времени обслуживания заявок данного типа в узлах сети, матрица вероятностей передач между узлами (ц^, Св^, IF8).

Определению подлежат: среднее и дисперсия времени задержки сообщения каждого типа в сети, максимальное время задержки сообщения каждого типа в сети, среднее и дисперсия времени задержки в узлах сети, загрузка узлов сети, вероятность потери сообщения в узлах.

Ограничения, накладываемые на результаты, состоят в том, что все характеристики должны быть неотрицательными, загрузка и вероятность потери не должны превышать 1, максимальное время не должно быть меньше среднего.

Вторая глава посвящена разработке алгори^яческого обеспечения методов расчета характеристик открытых неоднородных сетей.

В первом разделе приведена структурная модель .открытой неоднородной сети и постановка задачи анализа такой сети. Постановка задачи сформулирована исходя из общей постановки, приведенной в главе 1. Каждый узел сети моделируется системой массового обслуживания (CM0J одного из следующих типов: одноканалыше с ожиданием (G/G/1), одаоканальные с потерями (G/G/1/г), многоканальные с ожиданием (G/G/1), многоканальные с потерями (G/G/1/r), одаоканальные с групповым поступлением заявок (Gr/G/1), одаоканальные с хфушовым обслуживанием заявок (G/Gp/1). дисциплина обслуживания в каждом узле - PCFS.

во втором разделе разработана процедура расчета ВВХ открытой сети с учетом двух моментов входных потоков и времени обслуживания.

Характеристики сети могут оыть найдены в три этапа: 1) нахождение параметров внутренних потоков; 2; нахождение системных характеристик; 3) нахождение сетевых характеристик. Средние интенсивности входных потоков определяются из системы линейных уравнений:

м

Ла1 = + ^ . л.^, (1)

где представляет сооои общий внешний входной поток в сеть, Р^-элементы матрицы вероятностей передач, \ ^ - интенсивность потока заявок на выходе З-го узла, Н - число узлов сети.

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

са| = 1 + ¡Г - 1; • Р^ . Д.-1 + (С80г _ ,, . л

1 = Т ...М (2)

где С^ -ККВ потока на выходе ;}-го узла сети, иСео| -

интенсивность и ШШ потока, выходящего из сети через узел 1.

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

На третьем этапе решения задачи находятся сетевые характеристики. Среднее время пребывания заявки в сети определяется как взвешенная сумма времен задержки в узлах

м

тд =

где веса (коэффициенты передач) а. вычисляются, как отношение

_интенсивности входного потока в 1-й узел к оощему входному потоку в

сеть. -------

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

* Hai,atqi + II Ц covW^Mqg-Tqi, (4)

где ковариации

Г сц-3=1=1,г...М, 3 1 I а^-и^+су^-а^-с^, 3=1=1.2...Н, (5)

а тл^ определяются из матричного уравнения

У«(1-РГ1-Р. (6)

Для нахождения максимального времени задержки заявки в сети из уравнения

р Щ « Тчш) < Рдоп

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

В третьем разделе второй главы оценивается точность методм расчета характеристик открытых неоднородных сетей по двум моментам. Для этого были проведены аналитические расчеты характеристик сете! различной конЩгуращш с различными законами распределения входныз цотоков и времени обслуживания в широком диапазоне загрузок, дш этих же сетей было проведено имитационное моделирование ] осуществлено сравнение результатов. Общий диапазон погрешноси аналитического моделирования относительно имитационного оказался ] пределах от 0 до 15 % при среднем значении 4.5 %. По результата! имитационного моделирования были вычислены доверительные интервал! для времеви задержки в сети; частота попадания аналитически: результатов в эти интервалы составила 90 ж. На основании проведении исследований были сделаны выводы об основных факторах, влияющих н точность аналитического моделирования.

третья глава посвящена разработке алгоритмического ооеспэчени методов расчета характеристик смешанных неоднородных сетей.

В первом разделе приведена структурная модель смешанной неоднородной сети с простым диалогом и постановка задачи анализа такой сети.

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

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

1) нахождение параметров внутренних штоков относительно внешнего трагика;

2) нахождение параметров внутренних потоков относительно диалогового трафика, оощвго потока и определение характеристик диалогового трафика;

3) нахождение параметров внешнего трафика.

Для внешних потоков, относительно которых сеть разомкнута, используются методы расчета характеристик открытых сетей, рассмотренные в главе 2.

Характеристики диалоговых потоков могут оыть наадеЕЫ из системы 4хш нелинейных уравнении (ш - число диалоговых источников; вида:

М(ш)

л(и;=-,

1/т)(ш) +

(7)

м

(8)

М

(9)

м

где м - число узлов сети, Л(т) - средняя интенсивность поступления диалогового традика типа т в сеть; С2 да) - ККВ интервалов времени между поступлениями диалоговых "заявок типа т в~сеть; ц^(т)--- среднее время задержки диалоговых заявок типа т в сети; С^(ш) - ККВ времени нахождения диалогового задания типа ш в сети.

Величины а^(т) и 7^х(т) вычисляются аналогично соответствующим величинам для открытых сетей. Среднее и дисперсия времени ожидания в очереди к 1-му узлу и определяются в ходе решения системы уравнении (7 - 10) с помощью метода диффузионной аппроксимации.

При решении система уравнений (7 - Ю) в диссертации оыл выбран метод Брауна. Этот метод не треоует дифференцирования уравнений, входящих в систему, и позволяет найти решение за меньшее число итераций по сравнению с другими методами.

Для задания начальных значений переменным, входящим в систему (7 - 10), в диссертации оыл разработан специальный алгоритм. Он основан на возможно оолее точном определении интенсивности поступления диалоговых заявок й приближенной оценке времени задержки диалоговых заявок в сети в условиях большой загрузки.

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

Сетевые характеристики диалового трафика вычисляются Ьс /онове величин, полученных в ходе решения системы уравнений (7 - Ю). Сетевые характеристики внешнего трафика определяются также, как и для открытых сетей, при определении максимального времени задержки диалох'овых и внешних заявок в сети использован тот же метод, что и в главе 2.

Третий раздел посвящен оценке точности методов расчета характеристик смешанных неоднородных сетей с простым диалогом. Для этого было проведено имитационное моделирование ряда схем замкнутых и смешанных сетей и для этих же схем осуществлены аналитические расчеты. Сравнение показало, что максимальное значение относительной погрешности аналитических методов по сравнению с имитационным моделированием не превышает 20 * при средней погрешности 7.6 ж.

В четвертом разделе приведена структурная модель смешанной неоднородной сети со сложным диалогом и постановка задачи анализа

такой сети.

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

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

1) нахождение параметров внутренних потоков относительно внешнего трафика;

2) нахождение параметров внутренних потоков относительно диалогового трафика, общего потока и определение характеристик диалогового трафика;

3) нахождение характеристик технологических процессов;

4) нахождение характеристик внешнего трафика.

Характеристики диалоговых потоков определяются с помощью

решения системы 4хЬ (Ь - общее число типов диалоговых заявок в сети) нелинейных уравнении ввда:

¡2 гп (1

Ш1)'

(12)

(11)

я

___и

с*1а11),= Ц "з(с111)}7(01*У~ + (а}1}) • 1 _+_

н и

где М - число узлов сети, - номер (тип) диалогового сообщения,

и»

генерируемого в сеть х-оа операцией 1-го техпроцесса, Мй]) -

средняя интенсивность поступления сообщения от операции 1

техпроцесса группы 1 в сеть, С2(й|1)) - ККВ интервалов между

поступлениями диалоговых сообщений типа а^1' в сеть, -

среднее время задержки диалоговых сообщении от операции 1

техпроцесса группы 1 в сеть, (¿(а!1') - шш времени нахождения

(-I 1 " х м > п \

диалоговых задания типа а^' в сети, т^ц, и я^Ц) - среднее и

дисперсия времени цикла технологического процесса относительно 1-й

операции (времени между двумя очередными входами в 1-ю операцию).

Как и в случае простой структуры диалога, коэффициенты передач суа}1'), коввриации среднее (Т*^) и дисперсия (о^)

времени ожидания в очереди в ¿-м узле вычисляются в ходе решения системы уравнений.

При решении системы нелинейных уравнений (11 - 14) в диссертации был выбран, как и в случае простой структуры диалога, метод Брауна. Для задания начальных значений переменным в данном разделе разработан соответствующий алгоритм. Он позволяет найти в условиях большой загрузки максимально близкое к искомому значение интенсивности поступления диалоговых заявок в сеть и приближенно оценить время задержки диалоговых заявок в сети.

Сетевые характеристики диалогового трафика и техпроцессов находятся на основе величин, полученных в ходе решения системы уравнения (11 - 14). Сетевые характеристики внешнего трафика определяются по формулам для открытых сетей. При определении максимального времени задержки диалоговых и внешних заявок в сети, а также максимального времени цикла, использован тот же метод, что и в главе 2.

шестой раздел посвящен оценке точности методов расчета

характеристик смешащих неоднородных сетей со сложным диалогом. Для этого оыло осуществлено сравнение результатов, полученных путем аналитических расчетов и имитационного моделирования сетей оо сложным диалогом при различных законах распределения входных штоков и времени обслуживания, исследования показали, что относительная погрешность аналитических методов по сравнению с имитационным моделированием лежит в пределах от 0.5 до 20 % при среднем значении 7.6 %. при этом 85 % аналитических результатов попадают в доверительные интервалы.

В четвертой главе осуществляется разработка программного обеспечения методов расчета характеристик интегральных сетевых систем. Программное обеспечение реализовано в виде пакета прикладных программ (ШП) "БШЛ" аналитического моделирования систем, сетей массового обслуживания и сетевых систем. Предметом рассмотрения в главе 4 являются программы анализа открытых, замкнутых и смешанных сетей. В соответствующих разделах главы дано краткое описание этих программ и примеры расчетов.

Программа расчета ВВХ открытых неоднородных сетей занимает около 150 КБайт и позволяет анализировать сети размерностью до 50 узлов.

Программа расчета ВЕХ смешанных неоднородных сетей с простим диалогом занимает около 200 КБаят и позволяет анализировать сети размереностью до 50 узлов с Ю-в различными типами диалоговых и внешних источников.

Программа расчета ВВХ смешанных неоднородных свтвз со елокнкм диалогом занимает около 250 КБаят и позволяет анализировать сети размерностью до 30 узлов с 5-ю различными тапа>Я1 технологических процессов по 5 операций в каждом, 15-ю различными типами диалоговых и Ю-ю типами внешних заявок.

Минимальный требуемый объем оперативной памяти для работы программ пакета - 640 КБаят. Пакет работает на ЭВМ типа 1ВИ РС ХТ/А1 в операционной системе ИЗ-ЛОБ.

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

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

ЗАКЛЮЧЕНИЕ

Основными результатами диссертационной работы являются:

-1.-Доказано,_что в условиях произвольного характера распределения

входных потоков и времени обслуживания в сетевых—системах-

эффективное применение аналитических методов расчета характеристик таких систем возможно только при использовании специальных процедур их реализации, включающих численные методы, алгоритмы и программы для ЭВМ.

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

3. Проведено сравнительное исследование результатов, полученных на основе разработанных в диссертации методик расчета характеристик сетевых систем и имитационного моделирования. Показано, что диапазон относительной погрешности для открытых сетей лежит в пределах от О до 15 % при среднем значении 4.5 %, для смешанных сетей - в пределах от 0.5 до 20 ж при среднем значении 7.6 ж.

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

5. Разработанные процедуры, численные методы и алгоритма доведены до практической реализации в виде пакета прикладных программ "ШРАй" анализа систем, сетей массового обслуживания и сетевых систем по двум моментам входного штока и времени обслуживания.

6. Показано, что реализация методов расчета характеристик интегральных сетевых систем в виде пакета прикладных программ позволяет сократить время расчета в 2 - 10 раз в зависимости от размерности сети и типов узлов.

ГОБЛИМЦИИ

По теме диссертации опуоликоваш следующие научные работы:

1. Воронцов Ю.А., Егорова И.Н., Ерохи.* А.Г., Комаров А.О. Аналитическое моделирование задачи диспетчеризации в сетевых системах. В со.: тезисы докладов Пятой Всесоюзной конференции "Вычислительные cera коммутации пакетов", ч. 1, Рига, 1987, с. 98-101.

2. Ерохин А.Г. Алгоритм диспетчирования нагрузки в сетевых системах. В сб.: тезисы докладов 13 Всесоюзной школы-семинара по вычислительным сетям, М. - Алма-Ата, 1988, ч. 3., с. 124-129.

3. Воронцов Ю.А., Ерохин Л.Г., Комаров А.О. Алгоритмическое и программное обеспечение расчетов сетевых систем на основе методов диффузионной аппроксимации. В сб.: тезисы докладов 14 Всесоюзной школы-семинара по вычислительным сетям, М. - Минск, 1989, ч. 3, с. 38-42.

4. Ерохин А.г. комплекс программ для расчета характеристик двухузловой смешанной неоднородной сети. Деп. в ЦНТИ "Информсвязь", Н., 1991, 5 с.

5. Ерохин А.Г. Программное обеспечение расчетов смешанной неоднородной сети на основе методов диффузионной аппроксимации. В сб.: тезисы докладов 16 Всесоюзной школы-семинара по вычислительным сетям, Ы. - Винница, 1991, ч. 3, с. 24-28.

6. Отчет по НИР "Разработка АСУ цехами Уфимского завода коммутационной аппаратуры" (шифр "Модель"), научный руководитель Ю.А.Воронцов, й гос. per. 01860081212 /Воронцов Ю.А., Егорова И.Н., Ерохин А.Г., Комаров А.О/, М., Московский институт связи, 1988.

7. Ерохин А.Г. Расчет характеристик информационно-вычислительной сети с различными типами узлов, деп. в ЦНТИ "Информсвязь", М., 1992, 5 с.

8. Ерохин А.г. О точности расчетов открытых СеМО с неоднородными узлами с помощью пакета прикладных программ "ДИФАР".В сб.: тезисы докладов 17 Международной школы-семинара по вычислительным сетям, м. - Алма-Ата, 1992, ч. 2, с. 145-149.

9. Ерохин А.Г. Алгоритмы моделирования интегральных сетевых систем, деп. в Ш'ГМ "Информсвязь", М., 1993, Ю с.