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

о т>

.и |=с

ю ШПШСПЕ7СГЮ ОКЩКА) И 1Ж»еС€СВ<№ЛЛЬВОГО __ОБРАЗОВАНИЯ РОССИЙСКОЙ ^£Ц1РАЦИИ____

ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

На Правах рукописи УДК 681.324

СИДОРЕНКО Виталий Георгиевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ПРОГРАММНО-ИНСГРУМЕНТАЛЬНЫХ СРЕДСТВ ИНТЕРАКТИВНОГО СИНТЕЗА РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ

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

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

АВТОРЕФЕРАТ

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

Таганрог-1996

Работа выполнена на кафедре вычислительной техники Таганрогского государственного радиотехнического университета

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук, профессор,

действительный член Академии естественных наук Российской Федерации ГУЗИК В.Ф.

НАУЧНЫЙ КОНСУЛЬТАНТ: кандидат технических наук, доцент

. РЕШЕТНЯК В.Н

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: ^доктор *ехнических наук, профессор

ВИТИСКА Н.И кандидат технических наук, доцент КОВАЛЕВ С.М

ВЕДУЩЕЕ ПРЕДПРИЯТИЕ: ° Вычислительный Центр РГУ,

■ г. Ростов-на-Дону.,

Защита состоится » декабря 1996 г. в 14' часов на заседани! диссертационного совета Д ,063.13.01 по защите диссертаций при Таганрогско? государственном радиотехническом университете * по . адресу: 347928 "г. Таганрог, пер. Некрасовский, 44, ауд, Д-4Й6.

С диссертацией можно ознакомься в библиотеке университет"».

Автореферат разослан « ¿ / » ноября 1996 г.

Ученый секретарь диссертационного совета техн. наук, додёнт

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

АКТУАЛЬНОСТЬ ТЕМЫ, Происходящий п настоящее время в России и ча рубежом активный процесс информатизации общества невозможен без разработки и внедрения распределенных информационно-вычислительных сетей (РИВС). В настоящее время в России и за рубежом эксплуатируется или проектируется значительное количество сетей ЭВМ. При этом весьма часто требуется не проектировать РИВС заново, "с нуля", а допроектировать или перепроектировать ее с целью подключения впервые создаваемых региональных РИВС к существующим глобальным телекоммуникациям: сетям типа Relcom и RunNet, телефонной сети.

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

Проблемой автоматизированного проектирования РИВС и смежными с ней занимались такие крупные отечественные ученые, как Советов Б.Я., Лазарев В.Г., Максименков A.B., Жожикашвили В.А., Богуславский Л.Б., Зайченко Ю.П., Гонта Ю.В. и др. Анализ российских и зарубежных разработок в данной области (ACCESS (г. Санкт-Петербург), МАРС-Техника (г. Калинин), ДИАТОС (Украина), ВАРИАНТ (Украина), NetSüite Professional Design (фирма NetSuite), NETWORK ILS, COMNET III, MIND (фирма NAC)) показывает, что указанные системы имеют ряд Недостатков, основными из которых являются их сложность, громоздкость, повышенные требования к вычислительной технике. Кроме того, некоторые из них предлагают автоматическое проектирование сетей в пакетном режиме, когда для разработчика затруднительно или невозможно влияние на процесс вычислений в ходе проектирования РИВС.

Учитывая, что задача проектирования РИВС обычно характеризуется малой достоверностью исходных данных, наличием трудно формализуемых- факторов и ограничений, наличием нескольких критериев эффективности, наиболее перспективным в данном случае является интерактивное визуальное проектирование РИВС, при котором на ЭВМ возлагаются основные задачи по выполнению трудоемких алгоритмов синтеза или анализа сети (в основной, оптимизация структуры и расчет характеристик как сети в целом, так и ев отдельных элементов), а на разработчика - не менее важная задача - принят »Я решений (принять или не принять данный вариант- сети, какие ограничения использовать, какой показатель эффективности считать наиболее важным и др.) При этом сам процесс проектирования представляет собой итерационный процесс включающий две основные фазы: расчет на 'ЭВМ и принятие решений

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

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

ОБЪЕКТ ИССЛЕДОВАНИЯ. Объектом исследования являются распределенные информационно-вычислительные сети, методика их проектирования и способы построения типовых программно-инструментальных средств для интерактивного визуального синтеза РИВС.

ЦЕЛЬ И ЗАДАЧИ РАБОТЫ. Целью диссертационной работы является анализ методов проектирования РИВС, а также исследование и разработка типовых программно-инструментальных средств, позволяющих организовать единый целенаправленный процесс проектирования РИВС от начального этапа (постановки технического задания на ее проектирование) до конечного этапа (получения спецификации по проекту РИВС). Для достижения поставленной цели решаются следующие задачи:

• анализ особенностей организации, структуры и методов синтеза РИВС в интерактивном режиме;

•• анализ, исследование и разработка методов интерактивного "электронного" описания (картографирования) зоны проектирования;

• анапп, исследование и разработка алгоритмов интерактивной визуальной декомпозиции (композиции) зоны проектирования;

• исследование и синтез алгоритмического и операционного базисов реализации процесса инструментального проектирования РИВС, алгоритмизация интерактивного визуального синтеза РИВС;

• разработка и исследование методики интерактивного визуального синтеза вертикальных и горизонтальных сетей РИВС;

• разработка типовой организации программно-инструментальных средств интерактивного визуального синтеза РИВС;

разработка* программно-инструментального комплекса (ПИК) NET-PRO для интерактивного визуального синтеза РИВС, в который воплощены основные научные результаты, полученные в диссертации.

МЕТОДЫ ' ИССЛЕДОВАНИЯ. Для решения поставленных задач' используются методы теории вычислительных систем, теории графов, аналитического моделирования, теории массового обслуживания, прикладного и системного программирования.

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ. На защиту выносятся следующие положения и результаты:

• единая алгоритмическая реализация новой методологии иерархического визуального интерактивного проектирования РИВС;

• способ описания зоны проектирования с использованием "подложки";

• методика шперакййвной визуальной декомпозиции зоны проектирования РИВС на элементы проектирования: кластеры и домены;

• алгоритмический и операционный базисы реализации процесса интерактивного визуальши-о синтеза РИВС в инструментальной среде;

• общая методика интерактивного визуальнрго синтеза вертикальных и горизонтальных сетей РИВС.

НАУЧНАЯ НОВИЗНА. Предложена единая алгоритмическая реализация методологии проектирования. РИВС, основанная на концепции трехуроиневого представления РИВС. и позволяющая организовать целенаправленный процесс визуального интерактивного проектирования РИВС с использование программно-инструментальных средств. Синтезированы алгоритмический и-, операционный базисы интерактивного визуального синтеза РИВС, разработана типовая структура программно-инструментальных средств . визуального интерактивного проектирования РИВС, уто дает возможность разрабатывать указанные типовые средства для синтеза РИВС на любых программно-аппаратных платформах.

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ:

• проведен анализ особенностей, организации, структуры н,методов синтеза РИВС в интерактивном режиме, в результате чего разработана алгоритмическая реализация новой м ею дики интерактивного визуального проектирования РИВС;

• проведен- анализ и исследование алгоритмов •Топологического синтеза применительно к интерактивному визуальному синтезу РИВС, что позволило синтезировать алгоритмический и . операционный базисы процесса интерактивного визуального проектирования РИВС в инструментальной среде;

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ РАБОТЫ представляют: алгоритмическая реализация методики визуального интерактивного проектирования РИВС и типовая структура программно-инструментальных средств для организации интерактивного синтеза РИВС, а также разработанный программно-инструментальный комплекс ЛЖ21-РДО, совместное использование которых позволяет осуществлять целенаправленный пбиск, проЫотр и исследование различных вариантов РИВС, создавать"Наиболее целесообразные и оптимальные. При зом время, затрачиваемое на проектирование," значительно уменьшается,. а разработчик Избавлен, от необзюднмосга выполнена* черновой рутинней рьботы по расчету характеристик каждогв отдельного ажриацтапроехтаруемой РИЗС-

ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТОВ РАБОТЫ- Теоретические и практические результаты диссертационной работы использовались при выполнении госбюджетных и хоздоговорных работ кафедры вычислительной техники Таганрогского государственного радиотехнического университета: "Разработка комплекса программно-инструментальных средств для топологического проектирования информационно-вычислительных, с етей" (№ г.р. 01.9.40 010258), "Разработка методологии; математического обеспечения и программно-аппаратного сопровождения синтеза. новых информационных технологий в региональ.юй информатизации России" (№ г.р. 01.9.50 004161), "Учебно-исследовательский программно-лабораторный модуль по теме "Синтез иерархических регконалы х вычислительных сетей"" (№ г.р. 0.1.93.0 010187), "Программный лаборр.орнай комплекс по курсу "Информационные вычислительные сети"" (№ г.р. 01.93.0_007029), "Программный инструментальный комплекс для студента-проектировщика распределенных информационно-вычислительных сетей (курсовое проектирование)" (№ г.р. 01.9.40 010259), "Автоматизированная обучающе-коитролирующая система по предметному курсу "Информационно-вычислительные сети"" (№г.р. 01.9.<0_б01012), выполненных в рамках Всероссийских научно-технических программ "Информатизация России" и "Перспективные информационные технологии в «высшей* рбразовании". Результаты данных работ (отчеты по НИР и программные продукты) были представлены в соответствующие научные Советы программ И успешно защищены.

Кроме этого, результаты диссертационной работы внедрены в учебный процесс и используются на кафедрах вычислительной техники ТРТУ и СПбГЭТУ, а также на кафедре АСОиУ СПбГЭТУ.

АПРОБАЦИЯ РАБОТЫ; Основные результаты работы докладывались и обсуждались на нэучйо-техническгос конференциях (НТК) и семинарах: Международном семинаре "Проблемы региональных и ведомственных информационно-компьйэтгряих сетей" (г. Одесса, 1993 г.), Ш Межрегиональном семинаре по ООП (г. Минск, 1993 г.), ;Северо-кавказсксЙ[ региональной НТК "Методы и средства цифровой, обработки сигналов" (г.Таганрог, 1993г.), НТК "Автоматизация исследования, проектирования и испытания сложных технических систем к проблемы математического моделирования" (г. Калуга, 1993 г.), 1П Санкт-Петербургской ' международной конференции "Региональная икформатика-94" (г. Санкт-Петербург, 1994 г.), Ш Всероссийской научной конференции студентов и аспирантов.Техническая киберкешка, радиоэлектроника и системы управления" (г, Таганрог, 1996 г.), НТК профессорско-преподавательского состава, аспирантов и сотруднтаов ТРТУ (г. Таганрог, 1992-1996 г.г.).

ПУЕйШСАЦШ.-По результатам дассертгциош5§Й работы опубликовано 10 печатных работ. Крр&ге того; зщчтельная часть ирактичеекзж результатов изложена ь 7 отчетах о вшюдшекии ТШР, передалшж к зарегистрированных в ВНШЦ-жре, р«зультать; .-работи иснолвзошиш 'вря написании 2 учебно-гсзсобга!.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 188 страницах, содержит 79 рисунков, 53 наименования библиографии и 9 страниц приложения, ecefo 197

ЛТПШШ!

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

Во введении обосновывается актуальность проблемы, формулируется цель и основные задачи исследований. " . ■ • * . ■

В первой главе был произведен анализ ..существующих методов проектирования РИВС применительно к визуальному интерактивному синтезу. Была обоснована необходимость использования для этих, целей трехуровневой методики, предложенной В.Н. Решетником, с применением методов декомпозиции и иерархии зоны проектирования (ЗП) для уменьшения размерности задачи. и снижения вычислительных и, соответственно, временных затрат. - • '

Для представления сети используется иерархическая структура с тремя уровнями: региональным, кластерным и доменным. Исходный регион подвергается декомпозиций с целью выделения множества кластеров, Каждый из которых, будет являться ячейкой создаваемой РИВС.Еслй число узло? в кластере"превышает Nk, (где Nk - величина, зависящая от типа ЭВМ, используемой для проектирования РИВС, оцениваемая для IBM PC величйной 25-30), то такой кластер определяется как "сложный" и должен быть поджфгнут декомпозиции на домены. Далее осуществляется проектирование вертикальных кластерных сетей ' (ВКС) для "простых" кластеров, число узлов в которых'не-превышает TV*, и проектирование вертикальных доменных сетей (ВДС)- wirf всех доменов, входящих в "сложные" кластеры. Посде этого прошводигся ^композиция ВДС в горизонтальные сети "сложных" кластеров (ГССК), Синтез общей горизонтальной сети (ОГС), узлами которой являются. кластерные центры всех кластеров, а затем композиция окончательного цроекта РИВС. На' обнове анализа- ошкэдшой м4тодаки были определены реновцые этапы синтеза РИВС, необходимые для осуществления единого целенаправленного ' процесса проектирования: 1) предпроектное исследование и . разработка технического задания на проектирование РИВС; 2) "электронное '^описаний ЗП; 3) декомпозиция ЗП; 4) визуальный Етг^активный синтез вертикальных сетей РЙВС; 5) нюуальный нптерахтивйый синтез горизонтальных ' сетей РИВС; 6) композиция окончательного проекта РИВС;

7) имитационное моделирование- и прогнозирование развития РИВС;

8) гоготОвление документации fp проекту РИВС,

В ходе исследозйякй,- проведенных в диссертационной работе, были определенй /Ёач'^стпгндае а количестаешше характеристики РИВС, которые следует пехкгьзогать • при интерактивном проектировании, в частности, набор матриц: reûipî.<Jm;cknx (или декартовых) координат, требований на передачу потоков информации, расстояний,

связности (смежности), пропускных способностей (емкостей) ребер, стоимости, трафиков, маршрутов, задержек при

iicjvjj.n«; сообщений nb сети, загрузки каналов, а ыкжс рлд iapaMeqvк .\oropwc следует задать в качестве'входных ограничений при проектировании i-HBC: набо| каналообразующей аппаратуры, предназначенной для установки в узлах сети. иабо[ типов каналов, связи,> которые можно использовать при проектировании icih средняя длина сообщения, предназначенного для передачи по сети, максималык допустимая задержка.при передаче сообщений по сети, максимально допустима количество переприемов в, маршруте, зависимость стоимости канала связи от ег < длины и пропускной способности/Кроме этого; было показано, чго при втуально.\ интерактивцом проектировании РИВС следует использовать следующие кршерш эффективности функционирования сети: общая стоимость сети. ei производительность, среднее время задержки при передаче сообщений, ¡аг ручк; сети, среднее время пребывания сообщений в сети, параметры надежности сет) (связность узлов, вероятность нарушения связности при отказах каналов свяш i других компонентов сети). Учитывая, что интегральные характеристики сеп взаимосвязаны и зачастую^ противоречивы, при синтезе" РИВС рекомендуете! оптимизировать один, наиболее важный с точки зрения проектировщик;! показатель, а остальные использовать как ограничения^

При рассмотрении проблемы "электронного описания" зоны проектирования (ЭОЗП) после проведенного анализа существующих систем "эле.лтюмпшо' картографирования (например, ArcView, Buisness Map, Maplnfo) был сделан вывод о практической невозможности их использования для проектирования РИВС. гак как они генерируют описание ЗП в виде, це пригодном для дальнейшего использований при визуальной-интерактивном проектирование РИВС.

В данной диссе]Угащ)оы!ЮЙ работе показано, что при организации визуалыюго интерактивного проектирования РИВС наиболее целесообразным является представление ЗП в- виде реальной географической карты, отображенной на экране компьютера, что может зцаЗМельно улучшить визуальное восприятие и облегчить процесс проектирования. Кроме этого, предложено использовать при описании зоны проектирования, новый, весьма важный при проектировании РИВС картографический элемент-.- "подложку" зоны проектирования (изображение выбранного pemrsrd s т.спектс некоторого критерия, например водные или горные преграды, плодородные земли, автомагистрали, экономические регионы и др.). Использование "цоддожкк" позволяет ввести 1 ограничения, вызванные невозможностью прокладки реального физического канала связи, между., двумя узлами" сети вследствие налипни непреодолимых' географических преград, имеющихся $ зоне проектирования (река, озеро и т.п.)..

На основе анализа осшеных характеристик РИВС, онисанных" выше, был сиктезирэ1йш . картографический базис "электронного" описания" . зоны проектирования, олределеа необходимый и-дестаточньгй набор функций описания, разработок общий ' алгоритм "электронного" - описания -зрны проецирования (ЭОЗП). -

Внзчале создается новое ЭОЗП, при этом должна быть выбрана система координст проекта (декартова или географическая). Затем в ЭОЗП добавляются

узлы (для каждого узла указываются его название, координаты, а также население или вес). При нсобходимостг i ледует изменить параметры существу куцего узла и) Ю'ЗП пли удалить его ГЦ д лото необходимо определить набор допустимых типов каналов сняли и кан : < ö-vtлютей аппаратуры, а также внести в ЗОЗП существующие . с екомму, i i. п. К'огда формирование 'ЗОЗП завершено. >:собход;..<ГО опре й !и;ь матр'--ч> ¡мок-ния передачи информации, сохранить ЭОЗГ1 и вывести результаты нл принтер.

После формирования Э(ЯГ! следует выполнить декомпозицию ЗП на кластеры, а в том случае, если <;удут получены "сложные" кластеры, то и декомпозиции "сложных" кластеров на домены. В данной диссертационной работе был разрабоы: новый алгоритм декомпозиции, ориентированный на визуальную интерактивную реализацию процесса синтеза РИВС.

Укрупненно процесс декомпозиции зоны проектирования (кластера) пи кластеры (домены) может быть представлен как - совокупность двух этапов определение центров "кристаллизации"' (ЦК) н непосредственно "кристаллизация" узлов вокруг выбранных ЦК. Процесс нахождения'центров "кристаллизации' следует проводить с помощью выбора следующих узлов: имеющих макеимальньи значения объемов трафика для передачи информации в другие узлы; одного из дву> наиболее близкорасположенных узлов (по критерию. близкодейетвйя); узлов, имеющий Максимальное население (максимальный p.ecj; узлов, являющихся административными центрами (имеющих выход в другие вычислительные сети); узлов, выбранных,, разработчиком вручную. Затем необходимо выровпп ь "кристаллизацию''' одним из следующих способов: с помощью выбора узлов в некоторой /^окрестности 11К. выбора совокупностиЙлижайицтх к ЦК узлов, выбора узлов на еснове алгоритма "центра масс'* либо- разработчикомвручную на г/виот-прийципа территориально-алминистративного р£0деле"ния. .'

' •■' \ • - - i

В ходе ряда вычислительных экспериментов, проведенных .в .данной

диссёртациЬнйой работе, были определены , временные ' характер-лет^ и предлоядгнного алгоритма на примере регионов Ростовской области и Украины, основные 'критерии -выбора его параметров, показана' пригодность дактгего алгоритму к йрзуааьному интерактивному проек^ирозаншо РИВС.

, Н% основе анализа предложенного алгоритма, а также метод и .-л? проектнр.овашм, РИВЬ^ был синтезирован алгоритмический базке декомпозиции

зоны проектирования (АБДЗП): \ - ^ . -

» > • - -

" 1г<АБД31Т>::~<АВУ1С>, <АВПК>. <АП>1<^АСОМ>,<ОАЯД>у

где <4ВУХ>,-р алгоритм выбора узлов "кристаллизации"; <АВПК> - алгоритм выполнения (Процесса "кристаллизации"; <А1Т> - алгоритм. Прима; <АСОМ> -алгоритм СОМ; <ОАЦД> - общий алгоритм интерактивной декомпозшпш.

Я - '• ■ * ' -

Во второй главе рассматривается проблема^ визуального интерактивного синтеза вертикальных сетей РИВС. На основе анализа алгоритмов, которые могут быть нелользезаны в качестве базовых при визуальном интерактивном синтезе товопогии' вертикальных сетей РИВС, для построения ВКС (ВДС) древовидной

1и

шпозпгии в качестве базовых были выбраны алгоритмы Прима, Крускала, Ежи-Вильямса, была определена их пригодностьЛизу&тьному интерактивному синтезу. Для построения ВКС (ВДС) звездообразной топологии были разработаны алгоритмы построения "звезды" минимальной стоимости, "звезды" с заданным центром, а *акже алгоритм построения топологической структура "звезда звезд". В ходе вычислительных экспериментрв на примере тестового региона были определены сравнительные характеристики Вазовых алгоритмов. На основе анализа них алгоритмов и их временных характеристик в диссертации была предложена процедура "индексов подграфов", использование которой позволило уменьшить нремя выполнения алгоритмов Ежи-Вйлушса на 15-.£0% и Крускала на 40-50%.

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

В данной диссертационной работе реализованы и исследованы алгоритмы, которые; мож^о1 использовать в качестве базовых для решения задачи маршрутизации при визуальном интерактивнбм проектировании РИВС. Была лроведен? серия вычислительных экспериментов для получения сравнительных характеристик базовых алгоритмов, Дейкстры и Флойда. После проведенного анализа для решения задачи маршрутизации в ходе интерактивного визуального .интез'а РИВС -был выбран алгоритм Флойда в связи с меньшим по сравнению с алгоритмом Дейкстры временем выполнения.

.. Определены 'основные положения, которые следует использовать при оценке допустимости и оптимальности поучаемых решений. Решения, синтезируемые проектировщиком, должны удовлетворять входным ограничениям на прбёктирование, ■ а ^ их характеристики (должны быть не хуже характеристик решений, получаемы* с помощью базовых алгоритмов. Определены математические соотношения для расчета основных параметров и интегральных характеристик вертикальных сетей РЙВС (ВКС и ВДС).

Общая длина сети Ог вычисляется по формуле:

|»1 ¡шМ

где Щ - расстояние между узлами 1 и/;

/У- чискю узлов сйт^и; .

а здемЬну цатрицы смежности

{1, если существует ребро (/', /);

0, если это ребро не существует. .. . . . .

Общг(я стоимость сетй вычисляется по формуле:

V • 1-1 м ■ »-1

где - стоимость кайала связи (/,/);

Б? г- стоимость аппаратуры, установленной в узле к.

Суммарный график, передаваемый по сети, определяется по формуле'

У I» (-1

где—трафик канала (/./)

Д.тн организации визуального интерактивного синтеза вертикальных сетей * РИВС и ,1ссертации разработана методика, основными этапами которой являются: 1) построение связной топологической структуры сети; 2) выполнение процедур маршрутизации и распределения трафиков по каналам связи: 3) расчет пропускных способностей каналов связи; 4) расчет характеристик сети; 5) определение допустимости и оптимальности полученных решений.

Синтезирован алгоритмический базис ннтеракгизного визуального синтеза вертикальных сетей РИВС (АБИСВС).

<ЛБИСВО::-<ЛОМТ>, <АП>, <АЕВ>, <АПЗМО, <АПЗЗЦ>, <АПЗЗ>У <АФ>, <ЛОСО, <ЛОДР>, <ЛОСКО. <АООХЗО,

где <АОМТ> - алгоритм определения матрицы тяготения передачи информации; <АП> - алгоритм Прима; <АЕВ> - алгоритм Ежи-Внльямса; <АПЗМО - алгоритм построения "звезды" минимальной стоимости; <АПЗЗЦ> -алгоритм построения "звезды" с заданным центром; <АПЗЗ> - алгоритм построения топологической структуры "зве}да заезд"; <АФ> - алгоритм Флойда; <АОСО - алгоритм определения связности ссти; <АОДР> - алгоритм определения допустимости решения; <АОСКО - адгорятм определения стоимости канала евчзн; <АООХВО - алгоритм определения основных характеристик вертикальной сети РИВС.

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

В третьей главе рассматривается проблема визуального интерактивного синтеза горизонтальных сетей РИВС.

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

После реализации и исследования алгоритмов, которые могут быть использованы в качестве базовых при синтезе горизонтальных сетей Р.ПВС, да* синтеза оптимальной кольцеобразной сети был выбран алгоритм Литтла ди решения задачи коммивояжера го соображений надежности (требование двухсвязкости сети), а также для минимизации общей стоимости сети (сумьарай-! длины связей). ~ •

Для построения распределенной сети преда->жен\следук>щпй' аягорагс*. Вначале решается задача коммивояжера, в результате »гвге» стрсктся фшаизамке. сеть. Посла чего проюгпзвкг добавлок» ^полшпокак'«?,

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

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

Определена последовательность этапов, выполнение которых позволяет произвести процесс- композиции горизонтальных сетей РИВС и окончательного проекта РИВС в целом. Определены математические соотношения для расчета основных характеристик ГССК и ОГС.

Общая длина ГССК с учетом длин всех ВДС, входящих, в данную ГССК, вычисляется по формуле:

= *>*+£ А..

где А; - длина каналов ГССК;

.Оц - длина каналов ВДС*, входящей в ГССК;

т - количество ВДС, входящих в ГССК.

Стоимость ГССК

с учетом стоимостей всех ВДС, входящих в ГССК,

определяется по формуле:

где£2; - стоимость ГССК;

- стоимость ВДС*, входящей в ГССК. ,

Трафик Р^ ГССК' с учетом трафиков всех ВДС, входящих в ГССК, определяется по формуле:

где - трафик ГССК;

где Ги - трафик ВДС*, входящей в ГССК.

Общая длина ОГС О'1* с учетом длин всех ВДС, ГССК и ВКС, входящих в ОГС, вычисляется по формуле:

/.I >1

где - длина каналов ГССК/, входящих в ОГС, с учетом длин каналов ВДС;

т - число "сложных" кластеров,

Бу - длина канатов ВКС/, входящих в ОГС; \

Л-число "простых" кластеров.

Стоимость ОГС с учетом длин всех ВДС, Г ССК и ВКС, входящих в ОГС, вычисляется по формуле:

где - стоимость ГССК,, входящих в ОГС, с учетом стоимостей ВДС: - стоимость В Квходящих в ОГС.

Синтезирован алгоритмический базис интерактивного визуального синтеза горизонтальных сетей РИВС (АБИСГС).

<АБИСГО::=<АОМТ>, <АПТСК>, <АПТСР>, <АПТСД>, <АПТСЗ>, <АПТСЗЗ>, <АФ>, <АОСО, <АОДР>, <АОСКО, <ЛООХГО, <ЛКГО,

где <АОМТ> - алгоритм определения матрицы тяготения передачи информации; <АПТСК> - алгоритм построения топологической структуры "кольцо"; <АПТСР> - алгоритм построения топологической структуры "распределенная"; <АПТСЗ> - алгоритм построения топологической структуры "звезда"; <АПТСЗЗ> - алгоритм построения топологической структуры "звезда звезд"; <АФ> - алгоритм Флойда; <АОСО - алгоритм определения связности сети; <АОДР> - алгоритм определения допустимости решение; <АОСКО - алгоритм определения стоимости канала связи; <АООХГО - алгоритм определения основных характеристик горизонтальной сети РИВС; - <АКГС> - алгоритм композиции горизонтальной сети.

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

Для организации визуального, интерактивного синтеза горизонтальных сетей РИВС в диссертации обоснована необходимость использовать методику, основными этапами которой являются: 1) определение матрицы тяготения передач»: информации на основе результатов синтеза вертикальных сетей; 2) построение :вязной топологической структуры горизонтальной сети; 3) выполнение процедуры маршрутизации; 4) расчет основных параметров горизонтальной сети; 5) проверка допустимости и оптимальности полученных решений. Если на последнем этапе Зудет определено, что основные характеристики горизонтальной сети могут быт:, улучшены путем модификации входящих в нее вертикальных сетей, необходим.;: товгорно выполнить синтез вертикальных сетей, входящих в данную сеть. При :интезе ОГС может потребоваться возврат не только на уровень ВКС, но и на фовни ГССК и ВДС. После окончания процесса синтеза горизонтальной сети «обходимо сохранить решение с целью возможного возврата к нему, а также толучить отчет по результатам синтеза.

В четвертой главе на основе анализа результатов, полученных в трех предыдущих главах, была синтезирована структура типового программно-шетрументального комплекса (ПИК) визуального интерактивного проектирование 'ИВС, состоящего из общего программного монитора (ОПМ), инструментальной гасти (ИЧ) и функциональной части" (ФЧ). На основе анализа характеристик, гспользуемых для описания РИВС, разработана типовая структура баз данных ТИК. На основе анализа описанной методики синтеза РИВС, а также >азработанных алгоритмических и операционных базисов этапов проектирования 'ИВС определены категории пользователей ПИК, предложена программно--

аппаратная платформа для реализации процесса интерактивного визуального проектирования РИВС с испрльзованием- ПИК. показана пригодность и целесообразность использования ПИК. Для проверки и верификации основных научных результатов, полученных в работе, был разработан типовой ПИК NETPRO. Данный комплекс поддерживает все основные этапы проектирования РИВС и позволяет выполнять проектирование РИВС практически л1ор>п размерности.

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

В приложении приведены примеры отчетов о результатах проведений "электронного" описания зоны проектирования, интерактивной декомпозиции сложного кластера на домень?, интерактивного синтеш вертикальных и горизонтальных сетей РИВС с использованием разработанного ПИК NET-PRO, а также акты об использовании результатов работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РА КОТЫ

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

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

2. Разработана последовательность^ этапов построения оптимальной РИВС в смысле используемых критериев эффективности и надежности. Определены алгоритмический и операционный базисы всех этапов проектирования РИВС.

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

4. Разработан новый алгоритм синтеза топологической структуры "звезда звезд". Исследованы его сравнительные характеристики. Данный алгоритм позволяет получить проектные решения стоимостью йЛ, 20-25% меньше по сравнению с алгоритмом построения звезды минимальной стоимости..

5. Проведено исследование базовых алгоритмов топологического проектирования применительно к интерактивному синтезу РИВС. Показано, что оптимальные решения при синтезе вертикальных сетей РИВС получаются в результату использования алгоритмов построения топологических структур "дерево", "звезда", "звезда звезд", а при синтезе горизонтальных еггей РИВС - в результате объединения (симбиоза) сетей, полученных с помощью алгоритмов

построения топологических структур: "дерево",- "звезда", "кольцо", "ячеистая" (или распределенная).

6. Определены основные положение и математические соЬтнптпения. к-оторые следует использовать при расчете характеристик вертикальный и горизонтальных сетей РИНГ.

7. Определены основные ириюнпы и методы, которые следует применять при построении программно-инструментальных средств ' для интерактивного проектирования РИВС, 1 определена типовая 'структура данных средств, сформированы алгоритмический неструктурный базисы, функций проектирования, необходимых для реализации. ' * ' . .8. Разработан типовой ПИК ШТ-РЛО для Интерактивного синтеза РИВС с

использованием ЭВМ типа 1ВМ АТ, в который воплощены? основные научные результаты, полученные в диссертации. Данный комплекс внедрен в учебный процесс, апробирован в научно-исследовательских работах. Показал свою пригодность, полезность,.удобство в работе, простоту освоения..

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

1. Гузик В.Ф., Рещетйяк В.Н:, Сидоренко В.Г. и др. Городская'распределенная сеть экологического мониторинга на йримере региона п Таганрога.'В сб.: Методы к средства цифровой обработки сигналов. Тезисы докладов, Таганрог, ТРТИ, 1993,1е.

2. Гузик В.Ф., Решетник В.Н., Сидоренко В.Г. N Система5 интерактиЕнда проектирования вычислительных ^сетей. // Материалы .XXXIX научно-технической конференции, ТРТУ, Таганрог,. 1993. ~ с.^7-60.- - , "" .,

' .-я ' '

,3. Гузик" ' В.Ф., Решетник В.Н", Сидоренко, В.Г> Организация автоматизированйога проектирования топологии,региональных Информационно-вычислительных (телекоммуникационных) сетеД. //5III СанКт-Петербургскзг международная конференция "Региональная информатика-94": Тезисы докяадос. Часть 1.-С.-П6., 1994.-с.47-48.

** .ь -Г

4. Решетняк . В.Н., Левин' ЕЛ.,. Сидоренко В.Г. Учебк^нсследовэтеЕьсж? программно-лабораторный комплекс ЫЕТ_ЬАВ. // 'Программные продукш к системы,№2,Трерь, 1994. -с.27^32. . : ' '' , ■

5. Гузик ВЛ>., Решетняк : ВЛ., Сидоренко ВЯ\, Зфоеияровеккз распределенных информа^ионно-вычнслитейьнбгх сетей в инструмёнталькзй САПР. И "Интеллектуальные САПР". Межведомственный тематический сборку выпуск 5,.Таганрог, 1995,-с.?2-'26. .

6. РешеуцякВЛ., Сидоре^ко^В-Г. Программной ;инструтйенгальный комплекс! для студента-проектировщика распределенных Ж1формацно1шо1вьгчисл1ггелькы:: сетей. // ПрЪграмкные продукш и системы, 2, Тверь, 1995. - с. 17-22.,

7. Гузик В.Ф., Решетняк В.Н., Сидоренко В.Г. СЬстел(а НЕТ_РКО 'кг;:, якструмейгальное средство дам преекгарозаш-д топологии распределенных

зшф6рмацио1шо1-вычисднт«львых ocrtfl. // Ущшюшт «мпкмн ■ кяюом, ЛЬ 1/2, Киев, 1995. -с. 44-49.

8. Сидоренко В.Г. Использование программного комшмюа KET PRO для

преподавания курса "Информационно-вычислительные сети" ¡1 Всероссийская научная конференция студентов . и аспирантов "Новые информационные технологии. Информационное, программно? й аппаратное обеспечение". Тезисы докладов. ТРТУ, Таганрог, 1995, с.127-128.

9. )Гузик В.Ф., Решетняк В.Н., Сидоренко В.Г. и др. Автоматизированное проектирование топологии информационно-вычислительных сетей // Материалы

•З^ХХХ наз'чдю-техническойчконферёнций, ТРТУ, ТаганрЬг, 1995. - с.67.

1 - ТО.ДЗйдорен^о В.Г. Подсистема декомпозиций для автоматизированного проекяфовайия'РИВС // Третья Всероссийская научная конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления". Тезисы докладов.' ТРТУ, Таганрог, 1996.'с,. 111,

В работах, Написанных в'' соавторстве, личный вклад автора состоит в ¡следующем: в .[1,3,4] - предложена- алгоритмическая реализация методики трехуровневого проектирования, описан подход к интерактивному

проектированию РИВС, в [5,7] - описано использование ПИК NET-PRO для проектирования РЙВС, в* [9] - предложено использование автоматизированного проектирования РИДС в учебном процесс^, а [6] - рассмотрено исполь юванае 1ТИК NET-PRO для преподавания курса "Информационно-вычислительные сети".

Тнрогр^фия Таганрогского гос>дарственного радиотехнического Унилсрагта -

NkJiJTKRi* 100 экз. Цена "С".