автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Синтез структуры системного управления маршрутизацией информации в АСУ распределенными объектами

ВВЕДЕНИЕ.

1. МЕТОДИКА СИНТЕЗА СТРУКТУРЫ СИСТЕМНОГО УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ ИНФОРМАЦИИ. II

1.1 Особенности системного управления маршрутизацией информации в сетях обмена информацией АСУ распределенными объектами, выбор критерия . II

1.2 Описание структуры системного управления

1.3 Методика синтеза структуры системного управления маршрутизацией информации

В ы в о д ы

2. СИНТЕЗ ФИЗИЧЕСКОЙ СТРУКТУРЫ СИСТЕМНОГО УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ ИНФОРМАЦИИ.

2.1 Задачи этапа синтеза физической структуры.

2.2 Выбор локальных характеристик элементов графа топологии СОИ

2.3 Формализованное описание физической структуры

2.4 Алгоритмы синтеза физической структуры

В ы в о д ы

3. СИНТЕЗ ВЗАИМОДЕЙСТВИЯ ПРОЦЕССОВ СИСТЕМНОГО УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ ИНФОРМАЦИИ.

3.1 Задачи синтеза протоколов системного управления маршрутизацией информации

3.2 Отображение протоколов системного управления маршрутизацией сетью абстрактных процессов

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

3.4 Синтез поведений процессов системного управления маршрутизацией информации.

В ы в о д ы

4. ИМИТАЦИЯ ПРОЦЕССА СИСТЕМНОГО УПРАВЛЕНИЯ

МАРШРУТИЗАЦИЕЙ.

4.1 Цели и задачи моделирования, выбор моделей

4.2 Основные свойства предикатно-переходных и временных сетей Петри.

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

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

В ы в о д ы

Требования повышения эффективности учета, планирования и управления народным хозяйством, зафиксированные в "Основных направлениях экономического и социального развития СССР на 1981 - 1985 годы и на период до 1990 года", предопределяют интеграцию существующих АСУ [I] , а также создание новых автоматизированных систем управления на базе широкого применения средств вычислительной техники, ее интеграции с технологическим производственным оборудованием и процессами принятия решений на всех уровнях управления на основе использования средств связи. Подсистема обмена информацией, в качестве которой выступает сеть обмена информацией (СОИ), имеет важнейшее значение для АСУ распределенными объектами (РО) такими как объекты транспортного типа и общегосударственные системы, в которых СОИ используются для сбора, обработки, хранения и распространения информации различных видов, в том числе информации оперативного управления взаимодействием подсистем и локальных объектов РО.

Кроме повышения эффективности управления и использования средств вычислительной техники коллективное использование вычислительных ресурсов, как показывают предварительные оценки [ 2 ] , позволяет только для Ленинградского региона высвободить не менее 30 % парка ЭВМ и, что особенно важно, порядка 30-40 % квалифицированных специалистов, обслуживающих разрозненные ЭВМ.

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

Разработкам и исследованиям проблем организации маршрутизации посвящены работы отечественных и зарубежных авторов, среди которых можно выделить статьи и монографии А.В.Бутрименко, В.И.Варшавского, В.М.Глушкова, В.Н.Рогинского, В.М.Ченцова, В.Г.Лазарева, Ю.Д.Умрихина, Л.Клейнрока, М.Герла, У.Рудина, Дж.Макквиллана, А.Сегала, Д.Дэвиса, М.Шварца, У.Прайса,С.Йоне-ва. Несмотря на значительное число работ, многие проблемы организации маршрутизации остаются нерешенными. Общая теория построения систем, подобных системе маршрутизации, еще не сформировалась - основные усилия разработчиков направлены на поиск эвристик эффективных для конкретных сетей.

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

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

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

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

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

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

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

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

1. На основе анализа сущетсвующего опыта проектирования и эксплуатации систем маршрутизации, системного управления сетевыми функциями, а также международных рекомендаций в области архитектуры СОИ в работе предложена базовая система маршрутизации, являющаяся объектом управления со стороны ПСУ, реализующих оперативно статическую задачу маршрутизации в сетях АСУ РО.

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

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

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

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

Основные результаты работы внедрены при проектировании ряда сетей передачи данных и нашли отражение в 7 научно-технических отчетах по договорам на НИР кафедры Автоматизированных систем обработки информации и управления ордена Ленина ЛЭТИ имени В.И.Ульянова (Ленина). Основные положения и результаты диссертационной работы докладывались на 9 Всесоюзных конференциях и семинарах. По материалам диссертационной работы опубликовано II печатных работ.

В вводы

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

2• Анализ двух, интерпретации сетей Петри - цредикатно-пере-ходных сетей и временных сетей Петри - показал возможность1 построения на их основе сетевых моделей, инвариантных к топологии исследуемой СОИ, а также возможность исследования предикатно-переходных сетей методами анализа временных сетей, Петри.

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

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

ЗАКЛЮЧЕНИЕ

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

1# На основе анализа существующего опыта проектирования и эксплуатации систем маршрутизации, общесетевого управления сетевыми функциями, а также международных рекомендаций в области архитектуры СОИ в работе предложена реализация функции маршрутизации с помощью базовой системы, являющейся объектом управления со стороны, процессов системного управления, оперативно решающих статическую задачу маршрутизации в сетях АСУ распределенными объектами.

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

- многообразия, иерархии, связности и интенсивности взаимодействия компонент - по критерию, минимизирующему потери от неоперативности реагирования на структурные изменения СОИ.

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

4. Предложены модели и метод для формирования поведений

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

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

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

Исследования, выполненные в диссертационной работе, являются частью тематики научно-исследовательских работ, проводимых' кафедрой Автоматизированных систем обработки информации и управления ордена Ленина ЛЭЖ имени В.И.Ульянова /Ленина/.

1. Тихонов Н.А. Основные направления экономического и социального развития СССР на 1981 - 1985 годы и на период до 1990 года. Доклад ХХУ1 съезду КПСС '27 февраля 1981 г.- М.:Политиздат, 1981,-46 с.

2. Кезлинг Г.Б., Советов Б.Я. и др. Основные направления разработки региональной сети вычислительных центров коллективного пользования.- Л.:ЛДНТП, 1982, 32 с.

3. Клейнрок Л. Вычислительные системы с очередями.- М.:Мир, 1979, 600 с.у 4. Мамиконов А.Г. Основы построения АСУ. М.:Высшая школа, 1981, - 248 с.

4. Основы построения больших информационно-вычислительных сетей./ Ред. Жимерин Д.Г. М.:Наука, 1976,-320 с.

5. Цвиркун А.Д. Основы синтеза структуры сложных систем.- М.:Наука, 1982, 200 с.

6. Выставкин Я.П. Сети обмена информацией между ЭВМ.- М.:Наука, 1975, 216 с.

7. Сети ЭВМ. / Ред. Глушков В.М. М.:Связь, 1977,-279 с.

8. Лазарев В.Г.,Лазарев Ю.В. Динамическое управление потоками информации в сетях связи.-М.:Радио и связь, 1983, 216 с.

9. Бутрименко А.В. Разработка и эксплуатация сетей ЭВМ.- М.Финансы и статистика, 1981,-256 с.

10. Теория сетей связи./Ред. В.Н.Рогинский-М.:Радио и связь, I98I.-I92 с.

11. Якубайтис Э.А. Архитектура вычислительных сетей.--М.:Статистика, 1980,-280 с.

12. Schwartz M»', Stern T'vE. Routing techniques used in computer communication networks',- IEEE Trans',on Commuri. ,1980, v,COM—28,IT 4, p. 539-552

13. Landon M. Tele comm. support begins with focus on requirements.-Data Management, 1983»v.21,1T6,p. 12-16

14. Gerla M. Routing and flow control.-InsErotocols^ and techniques for data communication networks/ Ed'.Kuo F.FV --R?entice Hall Inc.,New Jersey , 1981,p.122-175

15. Ченцов B.M. Системы распределения информации. Синтез структуры и управления.-М.:Связь,1980,-144 с.

16. Йонев С.С.,Рухман Е.Л.,Советов Б.Я. Оценка эффективности алгоритмов адаптивного управления в сетях обмена данными. Автоматика и вычислительная техника, 1983,№ 3 ,с. 79 85

17. Варшавский В.И. Коллективное поведение автоматов.- MviHayica, 1973, 407 с.

18. Gerla M.,Kleinrock L. Plow control: A comparative serve}.- IEEE Trans.Commun.,v.C0M-28,114,1980,pV 553-574

19. Бутрименко А.В.,Вишневский B.M.,Гинзбург Б.М. О построении протокола глобального контроля перегрузок в сети.- В кн.:Теэ.докл.Всесоюз. школы-семинара по вычислительным се-1 тям, М.-Владивосток:ВИШШ,1980,часть 2, с.40-46

20. Дэвис Д.,Барбер Д.,Прайс У.,Соломонидес С. Вычислительные сети и сетевые протоколы. М.:Мир, 1982,- 600 с.

21. Schwartz Ж.1,Yum T.-S.P. The Join-Biased-Queue Rule and its application to routing in computer communicatio networks.ч- 176

22. Пашкеев С.Д. ,Минязов Р.И, ,Могилевский В.Н. Машинныеметоды оптимизации в технике связи.-М.:Радио и связь, 1983,216 с.

23. Segall A»,Sidi М. A failsafe distributed protocol forminimum delay routing';*- IEEE TransVCommun, ,v.C0M-29»N5>pV689

24. Ильин В.П.,Йонев С,С.,Смирнов М.И.,Советов Б.Я., Яковлев С.А. Разработка моделей для оценки эффективности методов управления в информационных сетях с учетом динамики их развития. Вопросы кибернетики, вып.72, М.,1980, с.41-52

25. McQuillan J.М.,Richer I.,Rosen E.C. An overview of the new routing algorithm for the ARPAUHD.-In: 6-th Data CommunV Synrp'.',Nov.27-29,1979»Pacific Grove,California.- Hew York,IT .Y.: IEEE, 1979 »P* 63-68

26. Chow W.',Bragg A'.VT.',Nilsson A.A. The need for adaptive routing in the chaotic and rnibalanced traffic environment".- IEEE Trans.Commun.,v.C0M-29,M,19S1»pV481-^90

27. Мизин И.A.,Богатырев B,A# Анализ зарубежного опытапостроения систем пакетной коммутации на примере сети АРПА.- Вопросы кибернетики, вып. 77, М.:ВИБИТИ, 1982, с* 84 97

28. Самойленко С.И., Давыдов А.А., Золотарев В.В. и др. Вычислительные сети. Адаптивность. Помехоустойчивость. Надежность.- М,:Наука, 1981, 277 с.

29. Фано Р. 0 роли организации службы передачи данных вжизни общества. .ТИИЭР, т.60,№ II, 1972, с.210-215

30. Jacobsen Т. The ISO Reference Model of Open Systems1.t erconnection. -In: IT et wor k-80, Int.Conf .,London, June 1980. --Lond on: Online, 1980 ,p. 431-453

31. Илюшин А.И.,Мямлин A.H. .Штаркман B.C. Принципы построения верхних уровней программного обеспечения сетей ЭВМ.- Управляющие системы и машины, 1981,№ 6, с.3-12

32. Bohme E. A communication service applied in a distributed data base systems'.- Lect:.Notes Coinp.Sci. ,v.123,1981, pi205-222

33. Sunshine С.A. Factors in interprocess communication protocol efficiency for computer networks.-In:AFIPS Conf.Proc. New York,N.Y.', 1976,v.45,p.571-576

34. Davies DVWV,Holler E.,Jensen E.D. e.a'. Distributed systems- architecture and inqplementation.- Lect.Notes.Сотр. SciV, 1981, v.105,p:.510

35. Шварц М» Сети ЭBM. Анализ и проектирование.- 179 - М. :Радио и связь, I98I.-336 с.

36. Сипсер Р. Архитектура связи в распределенных системах.-- М.:Мир, 1981, том 1,-435 с.

37. Ильин В.П., Кутузов 0.И.,Смирнов М.И., Рухман Е.Л. Эвристическая декомпозиция при синтезе структуры и управления сети обмена информацией. В кн.: Тез Докл. Всесоюз. конф. "Синтез и проектирование многоуровневых систем управления",1

38. Барнаул, 1982, часть 2, с.108-110

39. Аветов Ю.В.,Смирнов М.И. Высокоуровневые протоколы контроля и управления вычислительной сетью. В кн.: Тез:, докл. Всесоюз. конф. "Программное обеспечение вычислительных сетей и систем реального времени".-Киев,1981,с.28-29

40. Илюшин А.И.,Дерябин Н.Б.,Зарубин А.Г. и др. Вызов процедур в распределенных, системах. Методические материалы и документация по пакетам прикладных программ, вып.24Дз I.1. М. :МЦНТИ, с. 104 131

41. Дэйт К. Введение в системы баз данных. М.:Наука, 1980,- 463 с.

42. Сандстрем Р.Д. ,Шульц Г.Д. SNA : первые шесть лет / 1974 1980 гг. / . - Проблемы МСНТЙ, 1981, lb 2

43. Holzman С.J.' A theory for protocol validation.- IEEE Trans. Coniput., 1982, v. 31 ,N8 ,p. 730-738

44. Бусленко Н.П. Моделирование: сложных систем. М. :Наука, 1978, - 400 с.

45. Айзерман М.А.,Гусев Л.А. ,Розоноэр Л.И. и др. Логика,

46. Автоматы. Алгоритмы,. М. :Физматгиз:, 1963,556 с.

47. Gentlemen M.W. Message passing between sequentialprocesses: reply primitive and. administrator concept1.- Software practice and. experience, 1981 »v.11,N5»pV435~466

48. Rothnie J.B.,Goodman J.NY, Merrill T. Data Networks.- In: Protocols and Techniques for data communication networks/ Ed. Euo F.P.-Prentice Hall Inc.,1981,p.433-461

49. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969, часть I, - 543 с.

50. Байцер Б. Архитектура вычислительных комплексов.- М.:Мир, 1974, том 1,-498 с.

51. Кристофидес Н. Теория графов. Алгоритмический подход.- М.:Мир, 1978. 432 с.

52. Погребной В.К. Об одном методе определения изоморфизма графов. Кибернетика, 1982, № 2, с. 7-13,24

53. Гадасин В.А.,Ушаков И.А. и др. Надежность сложных информационно-управляющих систем.-М.:Сов.радио,1975,-191 с.

54. Артемьева С.Я., Маматов А.И., Страхов А.Д. К анализу надежности сетей связи. В кн.: Информация и информационные сети, М.:Наука,1977, с.113-123

55. Касти Дд. Сложные системы: связность,сложность и катастрофы. -М. ;Мир, 1982,-216 с. .67» Petri С.A. Introduction to general net thory.- beet.

56. Notes Conrp.Sci.,1979»v.84,p.1-21

57. Genrich H.J. ,Lautenbach K. jThiagarajan P.S.' General general net thery.- Lect. Notes Conrp. Sci1.,1979»v.84,p.21-159

58. Voss K. Using predicate/transition nets to model and analise distributed database Systems'.-In: COMPSAC 79,Proc. IEEE Comput.Soc's ,3-rd Int.Сотр.Software,1979»

59. Jensen K. Coloured Petri nets and the invariant method.- Theor. Сотр.Sci.,1981,v.14,N3,p.317-336

60. Nutt G.JV Evaluation nets for computer system performance evaluation.- Proc. of the Pall Joint Comp.Conf.,1972, v.41,p.279-285

61. Noe J.D. Nets in modelling and simulation.- Lect. Notes Comp.Sci.,v.84,1981,p.347-36873; Merlin P.M.' A methodology for the design and implementation of communication protocols'.'- IEEE Trans.on Commun., 1976,v. COM-24,N6,p.614-621

62. Sifakis J. Performance evaluation of systems using nets.'- Lect. Notes Сотр.Sci.,1979,v.84,p.307~319

63. Zuberek W.M. Timed Petri nets and preliminary performance evaluation .'-In: 7-th Annu.Symp.Comp.'Archit.Conf .Eroc., 1980.-New York,N.Y., 1980,p.88-96

64. Анисшов H.A. Средства формального описания сервиса и протоколов сетей ЭВМ с помощью сетей Петри. Владивосток, ИАПУ ДВНЦ АН СССР, Препринт 16 ДОЗ/, 1983', 25 с.

65. Sifakis J. Use of Petri nets for performance evaluation.- Acta Cybernetica,19791v #4,N2,p .185-202

66. Segall A. Distributed network protocols.- IEEE Trans. Inf.Theory,1983,v.29,N1,p.23-35

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

68. Условный экономический эффект от внедрения результатов диссертационной работы Смирнова М.И. составляет 83,12 тыс.рублей.1. От предприятия п/я, Уот ЛЭТИ им. В.И.Ульянова(Ленина)1. Б.Давыдов1. В.И.Петрович41. Ю.В.Аветов/j О.И.Кутузов

69. Начальник лаборатории ценообразования и экономической эффективности1. Э.И.Килюп ^^-> 1?Ч iy.