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

РГВ 00

' - 1 ПАП 1893

Комитет по высшей школе Министерства науки, высаеи аколн и технической политики Российском федерации Московский институт электронного машиностроения (МИЭМ)

На правах р-укоп;т-и УДК €2.1.391. 037.3 72

КУРАКИН ДМИТРИИ ВЛАДИМИРОВИЧ

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

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

АВТОРЕФЕРАТ

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

Москва - 1993

Работа выполнена в Российском научно-исследовательском институте информационных систем (Рос НИИ ИС)

Научный руководитель: доктор технических наук, профессор

Иванников А.Д.

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

кандидат Физико-математических наук Платонов Л.П.

Ведущая организация - Научно-исследовательский институт автоматической аппаратуры

Защита состоится 23 нарта 1993 года на заседаниии Специализированного совета К 063,68.01 в московском институте электронного машиностроения (109028, Б.Бузовскии пер-3/12)

С диссертацией можно ознакомиться в библиотеке ИКЭВ

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

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

В.л.стармг

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

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

страны.'

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

Сотни организаций и Фирм в мире, включившись в производство вычислительных сетей, выпускают свою продукцию по своим стандартам, в результате чего интеграция средств вычислительной техники может сыть неосуществима. Получившие в настоящее время широкое признание, разработанные Международной Организацией по Стандартизации стандарты взаимосвязи открытых систем ( Open Systems Interconnection -OSI) являются эффективным инструментом, обеспечивающим физическую, программную и эксплуатационную совместимость средств вычислительной техники. Базой стандартов OSI является семиуровневая эталонная модель.

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

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

1

сетей.

Анализ литературных источников показывает, чта описанные »

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

Лртор защищает:

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

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

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

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

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

Кдучнз*; новизна

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

?.. Разработан алгоритм оптимального распределения информационных потоков применительно к комплексу всех узлов в сети.

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

4. ~ Епервне теория гиббсовских состояний на 'счетных мно-

жестЕах применена для анализа :« исследования гычислитгт ,шх сетей, а также протоколов эталонной модели взаимосмчян открытых систем, что дает возможность в Солее компактней и лаконичной форме задавать информацию о сетевом поле.

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

Практическая ценность

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

Разработаны перечни стандартов 0Б1 по степени их актуальности с целью Формирования очередности их внедрения п промышленность страны, которые приняты Госстандартом России для включения в план государственной стандартизации на 199^ год.

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

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

Улучшено качество Функционирования локальной вычислительной сети Управления планирования и финансирсеания научных исследований высшей школы Комитета по высшей школе путем реализации в ней оптимального правила разрешения конфликтов.

Разработаны алгоритмы оптимизации для использования г» распределенных сетях.

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

Апробация работы

Основные положения и результаты диссертационной■ работы докладывались и обсуждались на заседаниях международных Рабочих групп по стандартизации в совете экономической Взаимопомощи (г. Москва, 1988 - 1990 г. г. ) и на заседании Ученого Совета Российского научногисследовательского институт} им Формационных систем (г.Москва, 1992 г. ).

Публикации. По теме диссертации опубликовано 1t печатных работ.

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

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

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

В первой главе рассматривается современное состояние международной стандартизации в области взаимосвязи открытых систем. В разделе 1. 1 приводится анализ состояния и опыта применения стандартов взаимосвязи открытых систем и протоколов MAP/TOP в России, зарубежных странах и международных организациях. '

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

в виде таблиц показана доля стандартов ISO в области OSI в общем объеме* стандартов, применяемых в различных странах и международных организациях.

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

Делается вывод о необходимости Форсирования работ в России по введению стандартов OSI в промышленность. .

В разделе 1.2 представлено современное состояние и развитие архитектуры открытых систем. Рассмотрены интерфейсы, протоколы, сервис, функции уровней эталонной модели. Дана архитектура сетей НАР/ТОР 3. О. Исследована связь стандартов

OSI в функциональном профиле НАР/ТОР 3. о.

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

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

В разделе г. 1 представлена разработка метопа применения оптимального правила предоставления общих сетевых ресурсов на канальном уровне эталонной подели (алгоритм оптимальной диспетчеризации). Исследуется распространенный метод множественного доступа с контролем несущей и обнаружением коллизий, описанный в стандарте ISO/OSI ввО£.3. Метод реализуется в рамках локальных вычислительных сетей типа Ethernet. В соответствии с этим методом существуют следующие типы захвата ресурса:

1. Захват, когда обнаруживается, что канал свободен. FC-ли канал занят, станция выжидает случайный период времени. Потом снова пытается захватить ресурс, И так далее - до успешного захвата;

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

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

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

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

- в -

работе Екбрано правило, минимизирующее среднюю частоту

КОНФЛИКТОВ.

Критерий оптимизации имеет вид:

где - математическое ожидание при начальном состоя-

нии ¿£1— , й. - правило разрешения конфликтов; 5 - текущее состояние совокупности процессов; ХСЭ.К)- характеристическая Функция; К - множество состояний в пространстве , для которого по крайней нере две координаты равны , . обо-

значающее активное состояние; |_| = 1-1 * ''...Ь^- пространство, р котором содержится IV-мерная цепь Маркова.

Для двух параллельных процессов (Г\.= 2) и нескольких неделимых ресурсов (К=От»М-) конфликтное множество имеет вид:

Оценивая эффективность правила аналитически, приводится выражение пля средней частоты конфликтов при применении оптимальною правила:

т. 4

Выражение для средней частоты конфликтов, когда ресурс с рапной вероятностью предоставляется тому или иному процессу определяется как:

т.

^ 2.

т.

< 2.

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

Описаг.ный алгоритм диспетчеризации предлагается для включения б содержательную часть стандарта, являющегося дополнением положений, заложенным в стандарте 150/051 бвог. 3.

С разделе г. г приводится разработка алгоритма оптимального распределения потоков сообщений на ьетевон уровне %т!Е'-.ннеЯ модели. Проведена оценка стакдзртизационного обес-

печения сетевого уровня и рассмотреть Функция маршрутизации информационных потоков.

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

5 ( * \ V Лг^-ДкУ'

где №. - число каналов; \Г - суммарная скорость поступления сообщений; Ск- пропускная способность К -го канала; __■ средняя длина сообщений (в битах). ^

Находится распределение Л к потоков по всем каналам сета. Для этого вводится ограничение, проводятся необходимые подстановки, применяется метод неопределенных множителей Лагранжа и выводится Функция Лагранжа

/

1

V

У

«•".г1 4". «

Для поиска оптимума ока диф}еренцируется и приравнивается к нулю. В результате получается система уравнений

р - £ $ ^

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

При использовании другого подхода рассматривается сеть коммутации пакетов, состоящей из узлов. Тспг.логия сети

описывается матрицей размера \П * Л- , элемента которой имеют значения пропускных способностей каналов связи между 1-м и^-м узлами. Потоки сообщений предполагаются пуэссоковскими с ия-тенсивностями в секунду.

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

гае IX/ - интенсйеность потока сообщений Г1/с). Условием существования стационарного режима с конечной очередью на обработку является:

п, (V

«. У:

V ^

где X ~ интенсивность потока из узла к абоненту. Суммарное время ожидания в очередях на передачу определяется выражением:

щ. г Я)

Задача оптимизации заключается в определении таких которые удовлетворяют заданным ограничениям и минимизируют ФункциюТ. Для аналитического решения задачи используются метод неопределенных множителей Лагранжа и необходимые условия минимума Функции нескольких переменных. функция Лагранжа_ определена выражением

- 4 А'\ '

Щ

Дифференцируя ее по тем ^-у' пля которых С^^ 0 , получаем б качестве необходимого условия экстремума систему алгебраических уравнений

&

Система репеиа численны)! методом с использованием стандартной подпрограммы.

Описанный алгоритм оптимизации предлагается для включения в ссаер*ательную часть стандарта , являющегося дополнением к положениям, залоас-нтлч в стандартах 150/021 #4ТЗ„ -9575, -юоге, -юезо, -юейз.

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

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

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

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

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

Для марковских полей выполняется равенство

НАЦх) в#А\^Г((АПЭх)ихив ^

КАИ+КА) "г ((АПЭДи^ив)+^((дПзх)иь)] '

вслЧСЭхЦх)

т.е. вероятность занятости точки X, (интерпретирующейся как узел), если известна конфигурация на Л\х , зависит только от того, что происходит с соседними точками (узлами).

Для гиббсовских состояний выполняется равенство

Иди») . ИдП^Ца) •

Г(Аих)^(А) ~К(АПЭх)и*)+г(АПЭх) '

т. е. условная вероятность того, что конфигурация содержит СЕ. при условии, что на конфигурация равна А , совпа-

дает с условной вероятностью того, что конфигурация содержит X при условии, что на Л\л конфигурация равна АПЗх..

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

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

Разработаны два проекта государственных Функциональных стандартов взаимосвязи открытцх систем : "Функциональный стандарт. Взаимосвязь открытых систем. ■ Профили- базовых стандартов для построения распределенных и локальных ияфор-мацйоннно-вычислительных систем" и " Локальные вычислительные сети. Протокол исходящей маршрутизации в ЛВС, обьединенных мостами на подуровне управления доступом к среде". I

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

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

Разработанные метод применения оптимального правила и алгоритм оптимального распределения потоков информации реализованы в виде программ на языке "С".

Дано описание и'принципы Формирования локальной вычисли- < тельной сети Управления планирования и Финансирования научных исследований Комитета по высшей школе, в которой реализован метод применения оптимального правила разрешения конфликтов. Представлены результаты работы программы. В сети инсталлирована сетевая операционная система NetWare v. з. 14. -выбор указанной системы осуществлен в связи с ее поддержкой стандартов OSI. Учитывая возможность комплексирования локальных сетей и построения на их основе глобальных распределенных сетей, разработанный алгоритм оптимального распределения потоков информации представля'ет собой перспективный продукт для повышения качества Функционирования сети в целом. Предложено использование алгоритма в . системе электронной почты сети RELCOM для Формирования маршрутных карт.'

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОИ РАВОТЫ.

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

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

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

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

!. Разработаны и внедрены в промышленность страны стандарт« ВЭаИМОСВЯЭЙ ОТКРЫТЫХ СИСТем СТ СЭВ 6178-88, '-6179-6?, -6185-68, -6366-86, -6367-88, -6368-88, -6762-89.

6. ВключенЬ в план государственной стандартизации России на 1993 год предложения по разработке стандартов взаимосвязи открытых систем.

7". разработаны йрограммы, реализующие метод и алгоритм

оптимизации.

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

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

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

1. Е»)ттнер х. Г. , Куракю Д. Б. Оптимизация маршрутизации пакетов сообценнй зз информационно-вычислительных сетях, построенных на базе стандартов 031. Сб. Вопросы'стандартизации. N £. К.. ¡98?. (диссертанту принадлежит разработка математических положений оптимизации).

2. Куракин Д. В. Оптимальное управление в информационна-вычислительных сетях, построенных :на' базе стандартов

.0С1. Сб. Вопросы стандартизации. N3, н. , 1990.

1. Куракин Д. В. , Ижэанов Ю. Л. Рекомендации по применению

оптимального, алгоритма диспетчеризации в составе.стандартов

ОС1. Труды Института СЭВ по стандартизации. Вып. 19, И. ,

1965. (диссертанту принадлежит применение оптимального пра-

1

вила предоставления обцих ресурсов на канальном уровне эталонной модели 031).

ч. Куракин Д.В. Рекомендации по применению оптимального алгоритма диспетчеризации. Сб. Стандартизация и качество продукции за рубежом. К 11, И., 1569.

ь. ст сэв б17а-еа (гост гео79-в9) "системы обработки информации. Протокол уровня звена данных. Методы синхронной позначной передачи данных".

6. Ст сэв 6179-66 "Системы обработки информации. Протокол уровня эвена данных. Метод синхронной побитовой передачи данных".

7. СТ СЭВ 6165-66 (ГОСТ 28062-69) "Системы обработки информации. Методы обнаружения ошибок при последовательной передаче данкых".

6. ст СЭВ 6366-68 (ГОСТ 26270-69) "Системы обработки информации. Спецификация файла' описания данных для обмена.информацией".

9. СТ СЭВ 6367-08 (ГОСТ 16145-69) "системы обработки информации. Стык сг. Цепи и функциональные характеристики".

10- СТ СЭВ 6366-66 "Системы обработки информации. Стык С2. Электрические параметры".

11. СТ СЭВ 6762-39 (ГОСТ 2*694-90) "СИСТеМН iOp.ir.ij гки ИНФ'.'ГК-1ЦЯИ. Передача данник. Определен!:? услуг Э1<«на пере.и-чи данник для взаимосвязи открытых систем".

Подписано к пзчата 07.02.93 Зак.ЗЗ Тип.ЮП * ч.-.

!.ЕШ, Москва, М.Пиокерскач ул.,12