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

■2 5 9 о'

МОСКОВСКИМ ордена ЛЕНИНА и ордзна ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

КРАШХИН Владимир Анатольевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА ДЛЯ АНАЛИЗА «УНКЦИОНАЛЫШ ХАРАКТЕРИСТИК И ВЫБОРА ОПТШАЛЬШХ ПАРАМЕТРОВ СТРУКТУРЫ »ШЬТИСЕГНЕНТКИ ЛВС

C5.I3.I3 - вычислительные машин, комплексы, систекч и сети

АВТОРЕФЕРАТ диссертации на соискание учЭноП степени кандидата технических наук

Москва - 1990

Работа вшолнона на кафедре системотехники Московского ордена Ленина и ордена Октябрьской Революции энергетического института.

Научный руководитель: кандидат технических наук доцент Л.И.АБРОСЖЮВ

Официальные оппоненты: - доктор технических наук

профессор В.П.КУТЕПОВ - кандидат технических наук старший научный сотрудник В.Н.СИЛАЕВ

Ведущая организация: ВЦ АН СССР

Защита состоится " " а 1990 г. на заседанз

специализированного совета К 053.16.09 Московского энергеп ческого института в а уд. Г НУ в час. 00 мш

С диссертацией можно ознакомиться в библиотеке Московскс го энергетического института.

Отзыв,заверенный печатью, просим направлять по адресу : 105835, ГСП, Москва, Е-250, ул.Красноказарменная, д.14, УчЗный совет МЭИ.

Автореферат разослан "_"_1990 г.

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

■ц1'

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

Актуальность темч. Прогресс в области информатики приво-: к созданию мультисегмонтшх локальных вычислительных се-I (ШШС) ( характеризующихся следующими Еарьируешми парамот-ш:

сонфигурацией структура, объединяодой отдельные сегменты ВС,

[{¡пользованием различных методов доступа в разных сегментах ВС,

гспользованием шлюзов - специализированных коммуникационно-[нтерфейсных ЗИЛ для связи различию: сегментов ЛВС.

Наличие таких параметров ставит дерод разработчиком ШШС на этапе эскизного проектирования взаимосвязанные задачи: нализа характеристик функционирования компонентов сети, ыбора конфигурации ШШС.

Автоматизация процесса разработки требует построения сбоб-ного алгоритма решения задач проектирования. Этот алгоритм хен использовать зависимости мевду параметрами, внутренними нешними характеристика?«! МЛВС, которое составляют математику» модель, описывающую информационное взаимодействие в про-ируекой МЛВС.

Как показал анализ существующих методов, наиболее полно и ективно специфику процессов и особенности структуры ШШС Зраглет аппарат сетей массового обслуживания (СеМО).

Однако известные модели СеМО не позволяют непосредственно зйти к расчету ШШС .для вшзода обобщенного алгоритма из-за: элъшого числа разнообразных квазинезависимых информационных этоков,

гобходимости расчета сетей смешанных типов, ножной топологии многоуровневого типа, 1зличных методов доступа к среде связи, граничений на величину буфера сетевых адаптеров ЭВМ.

В связи с невозможностью непосредственного использования )ствуюаих моделей для проектировали МЛЗС необходима разра-са новых или модификация наиболее подходящих аналитических ;лей.

Цель шбоуы. Цель» диссертационной работы является:

- разработка аналитической модели ШВС на основе модификации метода контуров,

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

- постановка задач выбора оптимального состава оборудования и размещения средств вычислительной техники во сегментам МЛВС и разработка методики для их решения на основе разработаь ной модели,

- разработка обобщенного алгоритма решения задач проекта!

1 вания МЛВС,

- разработка на основе обобщенного алгоритма расчета МЛВС лакета прикладных программ для автоматизации процесса решения задач проектирования МЛВС,

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

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

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

- математически строго сформулированы три группы задач проектирования, которые включают в себя:

а) задачи определения функциональных характеристик разомкнуты: и диалоговых МЛВС заданной структуры при изменении варьируемых параметров,

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

в) задачи выбора оптимальных параметров МЛВС.

- модифицирован метод контуров для учета ограниченности буферов компонентов ШШС, дефекта потока в замкнутых диалоговых СеЮ, выведены новые соотношения для модели

- разработаны основанные на модифицированном методе кон-

дики расчЗта функциональных характеристик и выбора оптимальных параметров ШВС,

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

Практическая ценность. Результаты, приведенные в диссертации, получены в процэссо работа над заданиями целевой комплексной программы ПШТ СССР , Освоения! направлениями научзо-тэзши-ческой деятельности Московского энергетического института.

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

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

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

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

¿лробация работ и публикации. Основные результаты диссертационной работы докладывались и обсуздалпсь на конференции "ЛОКСЕТЬ-вб" в ИЭВТ АН Латвийской ССР (г.Рига,198в), на шестом Всесоюзном симпозиуме по модульным информационно-вычислительным системам в АН Литовской ССР (г.Вильнюс, 1987).

Основные результаты работы опубликованы в трЗх печатных работах. Материалы диссертации обсузздены па семинарах кафодры СТ.

Объем I! структура писсертац'-те. Диссертация состоит из введения, пяти глав л заключения. Общий объем работы 205 е., 20 рисунков, 9 таблиц. Список литературы включает 127 наименований.

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

ллруются основные задачи, решению которых посвящена работа, приводятся сведения о структуре работы

В петеоп главе содержится аналлз современного состояния ЛВС, на основе которого сделан вывод о появлении нового класса ЛВС - ШВС. Выявлено, что ШЗС как новый класс объектов обладает ряд&н новых параметров по сравнению с ЛВС. Вся совокупность варьируемых параметров, характеризующих ШШС, объединена по типу изменения в три группы:

- варьируемые параметры ШВС, имеющие непрерывный характер изменения,

- варьируемые параметры МЛВС, пмеюнше дискретный характер изменения, -

- неупорядочиваемые параметры.

С учетом принятого разбиения, определен следующий состав задач проектирования МЛВС.

- задачи определения функциональных характеристик разомкнутых и диалоговых ¡/ЛВС заданной структуры при изменении непрерывных варьируемых параметров,

- задачи определения функциональных характеристик разомкнутых и диалоговых МЛВС заданной структуры при изменении дискретных варьируемых параметров,

- задачи определения функциональных характеристик разомкнутых и диалоговых МЛВС заданной структуры при изменении неупо-рядочиваемых варьируемых параметров,

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

- задачи выбора оптимальных параметров ЬИВС.

обосновывается актуальность исследования, форму-

Таким образом задача исследований состоит в том, чтобы сознать математическую модель функционирования МЛВС и разработать т ее основа методику решения, которая обеспечит решение Еиде-мнного состава задач проектирования МЛВС.

При этом мсдоль МЛВС долина отражать как общие для ЛВС, гак и специфические для МЛВС паралгетры, взкные .для ее проектирования. В качестве модели МЛВС предложено использовать смешанную-:тохастическую, учитывающую ограниченности очередей, СеМО с не-)днородашми запросами, одноканальными разами, экспоненциальным »определением времени обслуживания в обрабатывающих центрах ШЗС и произвольным распределением времени обслуживания в кана-ш ШШС.

В главе приводится обзор опубликованных в настоящее время шалитических моделей сетевых структур и анализируется возмож-юсть юс использования для решения задач проектирования МЛВС. [а основе анализа положительных и отрицательных сторон известих моделей и методик выделен вариант полиномиальной апдрокси-¡ации СеМО, известней под назвашгом"кетод контуров". В главе ;елается вывод о необходимости модификации метода конртуров .идя го использования в расчетах МЛВС и о направлениях такой моди-икашга. Ставится задача построения обобшенного алгоритма реше-ия задач проектирования ШШС на основа применения модифициро-анного метода контуров.

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

Во второй главе диссертационной работе приводится формализация описания ШШС для задачи расчета ШШС.

Пусть заданы 5 - количество уровней сегментов ШШС,

- число сегментов в кавдом из б уровней ШШС, Г> , ;4Али- тип канала к-го сегмента 1-го уровня ШШС, и» ЦК.4 .

а -173 .

- количество хост-ЭВМ в к. -м сегменте 1-го [/ровня.

- I* - количество транспортных станций в к ~м сегменте 1-го

уровня,

- - количество абонентов, подключенных к 1-й транспорт-

ной станции 1<-го сегмента 1-го уровня,

- Яв - обкее число абонентов МЛВС, ... •

- я3 - общее число хост-ЭВМ МЛВС,

~ 0* - количество ллюзов межсегментного обслуживания, подключенных к- к -му сегменту 1-го уровня,

- - матрица вероятностей поступления заявок от каздого из

абонентов каздого из сегментов к любой из хост-ЭВМ, В - штриха вероятностей поступления заявок от каздого из абонентов каждого из сегментов к хост-ЭВМ любого другого сегмента МЛВС, ' -С - матрица коэффициентов связности МЯЗС,

- - пропускная способность канала к -го сегмента 1-го

уровня,

- Лх - производительность хост-ЭВМ,

- Лт - производительность ЭВМ транспортной станции,

- Е*- - производительность ЭВМ шлюза,

- т( - емкость буфера сетевого адаптера хост-ЭВМ,

- щ - емкость буфера сетевого аадаптера транспортной стан-

ции,

- т^ - емкость буфера адаптера МЛВС шлюза,

- - среднее количество операций, затрачиваемых хост-ЭВМ

дая обработки одного пакета,

- 1Ц - среднее количество операций, затрачиваемых транспорт-

ной станцией для обработки одного пакета,

- Я,* среднее количество операций, затрачиваемых илюзом

дая обработки одного пакета,

- <СА - среднее время обдумывания абонента,

- 1. (и)- дайна пакета (преамбулы), передаваемого по сегменту

канала МЯЗС.

Требуется для решения задач определения значений функциональных характеристик определить:

- Л»^ - интенсивность поступления заявок (пакетов на обра-

ботку) на вход компонента V МЛВС по контуру обслуживания а ,

-Трч, - среднее время реакции на пакет, соответствующий запросу, для замкнутых контуров обслуживания ^ ,

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

.

- уV - показатель загрузки компонента 1МВС,

- - средняя длина очереди пакетов к компоненту МЛВС,

- - полные стоимостные затраты на рассматриваешь вариант

реализации МЛВС. Для вывода соотношений, связывающих входные параметры и функциональные характеристики компонентов МЛВС, представпмих в виде СМО Я/М./1/т (транспортные станции, алвзы, хост-ЭВМ), в диссертационной работа выведены расчетные соотношения для определения базовых параметров компонента н/М/1/т - вероятности р» пребывания компонента в свободном состоянии:

_1_

Р» = 1 . г 2-1 . >

I + ~

■г г>г ^ "ио

- Р.** - вероятности пребывания компонента в состоянии с запол-

ненным буфером, объемом т :

т

т.;

р я _»2_

, X "Щ . „ II1 . Ч\

где за счет дефекта потоков в замкнутых контурах обработки справедливо:

X , 1 = 0

величина дефекта интенсивности потока аХ^ определяется из соотношения:

I _

дЛ-т - » 3- 1, п»-1.

^ N

Параметр интенсивности обслуживания для компонентов, представи-мых в виде СМО М/М./А/т , определим так

п„

— , где V - либо хост-ЭВМ, либо шлюз,

либо транспортная станция, а дом компонентов, представишх в виде СМО н/Ъ/1 (каналы сегментов) значение параметра зависит от МА^ , , к, 1 К"5 и Мя детерминированных циклических методов доступа первые два момента определяются как:

2-Ч1

СЯЦ.2) • ь

Ь 42 ( КГ*Л4- VI

для случайных методов доступа:

м. 15

ь

.2

Для расчета временных характеристик компонентов, представимых в виде СМО Я/л/1/т справедлива формула:

а для вычисления среднего времени пребывания запроса в компоненте гг , представимом в виде СКО М/5/4- воспользуемся формулой Полячека-Хшпкпа:

V

+

К1 + ( I-

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

потока в любом компоненте через интенсивность потока або-

нента МЛВС. Используя в выражениях для расчета базовых

параметров Р0+РЗАН , получаем выражения для вычисления среднего числа требований в системе:

1

' , л с^^ ) %

п*= 21(^0 = -г3^-—).

¿•0 '1-1

Система нелинейных уравнений баланса выражает математическое ожидание числа запросов гч^ в компоненте у контура ^ как функцию от значений интенсивности д^ потоков, форьыруе-шх абонентами, обслуживаемыми данным контуром. Нелинейное уравнение баланса требует, чтобы математическое ожидание числа запросов гц в контуре ^ , Q^i . равнялось сумме математических ожиданий числа запросов nv<1 в компонентах, охватываемых контуром ^ :

п» = je1 п»« +21 >4, + 51. nv, + 21 п».

1 lieA vet 1 1 Ге-w 1 тгвмл. 1

и 5 к* ii

21 "г- =

Ч A-L fc.L l-l

■ Совместное решение систем линейных и нелинейных уравнений баланса позволяет определить значение функциональных характе- " ристик как функцией от . Аналитическое решение такой сис-

темы уравнений связано, как это видно из формул, приведенных выше, с нахождением корней (jN^ -1)-й степени, что уже при чрезвычайно затруднено.

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

В диссертационной работе предложена процедура, содержащая .два взаимосвязанных итерационных процесса. В первом (внешнем) производится расчет вероятностей Ргм( v, а во втором (внутреннем) производится расчет значений интенсивностеи . Проведенный анализ сходимости разработанных итерационных процедур,

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

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

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

1-2 > К-12/,65

-12.3,45-, _

- (2),f2,A),8-256 > mat - с CSMA.. TOKEN

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

Анализ точности позволил установить, что при принятых диапазонах изменений параметров, соответствуют большинству проектируемых МЛВС, погрешность предлагаемого метода не превышает

что свидетельствует о практической ценности разработанного метода при решети -задач реальной размерности.

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

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

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

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

- задачи выбора параметров оборудования МЛВС с заданной конфигурацией, оптимизирующих выбранную целевую функцию,

- задачи выбора структуры МЛВС с заданным составом оборудования, оптимизирующей выбранную целевую функцию.

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

- множество <CHS> характеристик структуры МЛВС,

- множество <1ЯР> внутренних параметров сети,

- множество <СНЕ> функциональных характеристик МЛВС,

- множество <vap> варьируемых параметров сети,

- подмножество <ЛМН> варьируемых параметров множества OJAP> , • таких, что любой из них изменяется непрерывно в области существования (диапазона изменения значений),

- подмножество <VAP2> варьируемых параметров множества <vat> таких, что каждый из них может изменяться .дискретно и может быть упорядочен по возрастанию или по убыванию в области су-шествования,

- подмножество <va?3> варьируемых параметров множества <¿va2> , таких, что каддый из них изменяется дискретно на множестве допустимых значений, причем упорядочение дискретного изменения значений производить невозможно.

Тогда, в соответствии с введенными обозначениями:

<chs>6{s,kj,ko,ot,n,b,c5 .

< ШР> * i nv, R,,m„, V¡2, MAt,U,L „,<C • <vat2>* is,k* 3t,l4. bt, oí, m„ r l

<\Щ> = <ЛХАР иоШ2> и <Л7А?3> .

Значение целевой функции вычисляется по формуле:

где г1 , га ~ экспертные оценки "важности" временных или стоимостных показателей для разработчиков и пользователей МЛВС, "Л, - нормативное время реакции МЛВС, УГ0 - норматив полных затрат на сеть. Для решения оптимизационных задач составляется вспомогательная функция Лаграша в виде:

где IV - экспортная оценка важности использования компонента V , цультишшкат; •? - коэффициент учета использования компонента у ! ^ _ множитель Лаграша, для нахождения которого решается уравнение, учитывающее замкнутость всех маршрутов и диалоговый характер обработки, то есть:

^ = Я,,-Кь(пи, + гц, - л,. пт).

Оптимум определяется в точке, где выполняется ОФле

9 П^г

'ЭП*

О для всех V , где

л» '

^ (Д-'д'СП^и)) - ( АУ(Дс „-а Я ))

+

4 ^ п а _ ^ (К(х-1) и)

В диссертационной работе доказывается, что для возможности ресения задачи нахозденпя опти.'.ума в точке я. необходимо выполнение условия одинаковой мерности пространств параметров, соответствующих точкам * вектора X^txi,:*,, ... х.,... у

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

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

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

Здесь же даны характеристики модулей пакета прикладных программ и функций, реализуемых этими модулями. Приводятся рекомендации для системных программистов по установке пакета и характеристики среда его генерации. В табличной форме описаны переменные программ и их соответствие переменным модели, разработанной во второй главе. Сдолан вывод о возыонности использования разработанного пакета на ПЭВМ класса IBM PC. Язык реализации пакета - TURBO-Pascal , версии 2.0 и выше. Общий объем текстов программ - 38 КЗ, загрузочных модулей - около 60 KB, время работы пакета на задачах реальной размерности - 10+50 минут.

Пятая глава содержит описания практических применений пакета, описанного в четвертой глазе: результаты решения задач анализа сети подвижной платформы, двухкабинного комплекса и задачи выбора оптимальной структуры автоматизированной системы информационного обслуживания Агекства печати "Новости" (АСИО АПН). Для этих задач приведены результаты в виде графиков зави-

- 16 -

скмости характеристик вариантов сетей от изменения входных потоков, рекомендации по оптимальной структуре МЛВС

Подученные теоретичзымо результаты и разработанное математическое обеспечение, опробованные на раде практических задач, могут быть применены при анализе функциональных характеристик, Екборо оптимальных параметров и оптимальных, структур МЛВС реальной размерности широкого класса.

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

ПУБЛИКАЦИИ ПО ТШЗ ДИССЕРТАЦИОННОЙ РАБОТЫ

1) Абросимов Л.И., Краизкш В.А. Сравнительный анализ двух методов доступа в моноканал локальной вычислительной сйти //Сб.науч.трудов/Ыоск.энерг.ин-т.-1986.-й 86.-С.5-IO.

2) Абросимов Л.И..Крашшш В.А.Расчбт характеристик локальных вычислительных сетей с неоднородным трафиком// . "ЛОКСЕТЬ-вб" : Тез. докл. конференции учбных социалистических стран. -Рига : ИЭВТ АН Латвийской ССР, 1986.

-С.132-136.

3) Абросимов Л.И.,Краоткин В.Л..Волочков Н.Ф-.Конытев А.Д. Оценка взаимосвязей ресурсоз и функциональных характеристик комплекса СМ-4 - "Электроника-60"//Мэжвуз.с0. трудов/MûCK.8H0pr.HH-T.-1985.-й 81.-СЛCB-113.

4) Абросимов Л.К.,Крашкин В.А.,Минин В.А.,Рякш1 О.Ы. Исследование вариантов архитектуры ЛВС МЭИ//Сб.науч. трудов/Ыоск.энерг.ин-т.-I988.-Л I54.-C.8-II.

5) Абросимов Л.И.,Краюшкин В.А. Анализ функциональных характеристик сёгментарованных кольцевых ЛВС//УТ Всесоюзный симпозиум по модульным информационно-вычислительным системам : Сборник материалов. -Вильнюс : АН Литовской ССР -"БИТАС", 1987. -С.77-79.

/,/

, „¿л-

¡tr;"1;^....... /,->:■ ^

I» ,.;-i!.i n-u: к,... 11

/