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

ВВЕДЕНИЕ

РАЗДАЛ I. АНАЛИЗ МЕТОДОВ УПРАВЛЕНИЯ В ВС РСТД И

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ.

1.1. Используемые объекты и предположения

1.2. Оптимальная маршрутизация: формальная постановка задачи

1.3. Оптимальная маршрутизация: анализ методов решения

1.4. Структурная устойчивость оптимального управления.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВО.Щ

Диссертационная работа выполнена в соответствии с работой Н4а задания 01 подпрограммы 0.54.16 ГКНТ СССР в рамках НИР "Интеграл" (шифр НИР МИЙГА - 17-82) и отражает один из аспектов управления связными ресурсами в интегрированной сети связи гражданской авиации. При выполнении работы лично автором получены следующие наиболее важные результаты:

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

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

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

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

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

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

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

Результаты проведенных исследований позволяют сделать следующие выводы:

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

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

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

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

5. Сравнение экспериментальных данных о скорости сходимости алгоритмов ДСМ с результатами исследования алгоритмов Галлагера и девиации потоков показывает, что скорость сходимости у алгоритмов ДСМ в 4-6 раз выше. Существенным преимуществом алгоритмов ДОМ перед известными алгоритмами является сходимость с произвольного начального приближения, тогда как алгоритмы Галлагера и девиации потоков в качестве начального приближения могут использовать только физически реализуемое распределение потоков.

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

7. Анализ количества вычислительных ресурсов, необходимых для реализации алгоритмов ДСМ показывает, что в случае распределенной систем управления потоками алгоритмы ДСМ могут быть реализованы в узлах коммутации, построенных на базе микро-ЭВМ. При этом для сети с 31 узлом коммутации время выполнения одной итерации не превышает 250мс на ЭВМ с быстродействием в 250тыс. операций в секунду и требуется около 4Кбайт памяти для хранения служебных таблиц.

Время счета и объем памяти растут линейно с ростом размеров сети.

ЗАКЛЮЧЕНИЕ

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

2. Проведено исследование характеристик различных вариантов реализации алгоритмов ДСМ-1 и ДСМ-2. Установлено, что алгоритм ДСМ-2 обеспечивает более высокую скорость сходимости и лучшую точность по сравнению с алгоритмом ДСМ-1. Алгоритм ДСМ-1 целесообразно использовать в сетях с малым объемом транзитного трафика.

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

4. Эксперименты показали, что алгоритмы ДСМ обеспечивают формирование физически реализуемого решения в диапазоне нагрузок до 97% от насыщающего потока. При уровне нагрузки до 80% от насыщающего потока погрешность алгоритма ДСМ-2 не превышает 4-5%. Для одного из вариантов сетей алгоритмы ДСМ находят точное решение вплоть до уровня нагрузки 97%.

5. Скорость сходимости алгоритмов ДСМ зависит от уровня нагрузки на сеть и величины возмущения установившегося распределения потоков. Проведенные сравнительные исследования показали, что скорость сходимости алгоритмов ДСМ в 4-6 раз вьппе, чем у алгоритма девиации потоков и алгоритма Галлагера. При уровне нагрузки до 80% от насыщающего потока скорость сходимости алгоритмов ДСМ практически равна теоретически предельной для распределенных алгоритмов маршрутизации.

6. Анализ времени моделирования и используемого объема памяти показывает, что эти характеристики растут в линейном соотношении от размера сети. Поэтому алгоритмы ДСМ могут использоваться в сетях с большим числом узлов. При распределенной схеме управления потоками алгоритмы ДСМ могут быть реализованы в УК, построенных на базе микро-ЭВМ.

1. Материалы ХХУ1 съезда КПСС.-М.: Политиздат, 1981. 223с.

2. Агаян A.A. О перераспределении пропускных способностей трактов передачи данных в сетях с адаптивной коммутацией.-В кн.: Четвертая Всесоюзная школа-семинар по вычислительным сетям. Ч.2.М.- Ташкент, АН СССР, 1979, с.6-13

3. Анализ и синтез сетей связи с использованием ЭВМ.- М.: Наука, 1974, 210с.

4. Арнольд В.И. Теория катастроф. Изд. 2.- М.: МГУ, 1983, 80с.

5. Ахо А., Хопкрофт Дж., Ульман Дк. Построение и анализ вычислительных алгоритмов. Пер. с англ. /Под ред. Ю.В.Матиясеви-ча.- М.: Мир, 1979, 536с.

6. Башарин Г.П., Самуйлов К.Е. Об оптимальной структуре буферной памяти в сетях передачи данных с коммутацией пакетов. (Предварительная публикация).- М., 1982, 70с.

7. Блехман И.И., Мышкис А.Д., Пановко Я.Г. Механика и прикладная математика. Логика и особенности приложений математики.-М.: Наука, 1983, 328с.

8. Бройтман М.Д., Эттингер Б.Я. Анализ процессов буферизациив системах телеобработки.- Автоматика и вычислительная техника, 198I, №2, с.55-61

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

10. Бутрименко A.B. Два критерия качества обслуживания и методы управления сетью коммутации сообщений. В кн.: Построение управляющих устройств и систем. М.: Наука, 1974, с.142-153.

11. Бутрименко A.B., Вишневский В.М., Гинзбург Б.М. 0 построении протокола глобального контроля перегрузок в вычислительной сети. В кн.: Пятая Всесоюзная школа-семинар по вычислительным сетям, М.- Владивосток, 1980, часть 2, с.40-45.

12. Бутрименко A.B. Разработка и эксплуатация сетей ЭВМ. М.: Финансы и статистика, 198I, 256с.

13. Васильев В.И., Коновалов В.М. Об эффективности функционирования сетей коллективного пользования Аэрофлота.- В кн.: Эффективность и оптимизация систем и процессов гражданской авиации.- М., 1976, вып.2, с.60-71.

14. Выставкин Я.П. Оптимальное распределение маршрутов передачи сообщений в вычислительных сетях. В кн.: Модели информационных сетей и коммутационных систем. М.: Наука, 1982,с .107-115.

15. Вычислительные сети: Адаптивность, помехоустойчивость, надежность/ С.И.Самойленко, А.А.Давыдов, В.В.Золотарев, Е.И.Третьякова.- М.: Наука, 1982, 227с.

16. Вычислительные сети. Терминология. (Проект).- М.: АН СССР, 198I, 36с.

17. Гилмор Р. Прикладная теория катастоф. Кн.1. Пер. с англ. /Под ред. 10.П.Гупало.- М.: Мир, 1984 , 350с.

18. Гилмор Р. Прикладная теория катастроф. Кн.2. Пер. с англ. /Под ред. Ю.П.Гупало.- М.: Мир, 1984, 285с.

19. Гинзбург Б.М. Оптимальное распределение потоков в изарит-мической сети обмена информацией между ЭВМ.- В кн.: Принципы построения устройств распределения информации. М.: Наука, 1978, с.54-63.

20. Горцев А.М., Назаров A.A., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания.- Томск, ТГУ, 1978, 202с.

21. Демидович Б.П., Марон И.А. Основы вычислительной математики. Изд.4.-М.: Наука, 1970, 644с.

22. Денисов A.A., Колесников Д.Н. Теория больших систем управления.- Л.: Энергоиздат, 1982, 288с.

23. Дрожжинов В.И., Мямлин А.И., Штаркман B.C. Управление обменом данными в сети ЭВМ с коммутацией пакетов.- В кн.: Алгоритмы и организация решений экономических задач. М., 1978, вып.12, с.83-116.

24. Дьяченко В.Ф., Лазарев В.Г., Саввин Г.Г. Управление на сетях связи,- М.: Наука, 1967, 223с.

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

26. Захаров Г.П. Методы исследования сетей передачи данных.-М.: Радио и связь, 1982, 208с.

27. Захаров Г.П., Андрианов A.B. Модель алгоритма маршрутизации, адаптивного к отказам каналов связи. В сб.: Методы управления и оптимизация вычислительных сетей. IX Всесоюзная школа-семинар по вычислительным сетям. 4.3.1, М.- Пущино, 1984,с.3-7.

28. Зиновьев Э.В., Стрекалов A.A. Стратегия управления информационными процессами с учетом обнаружения и недопущения тупиковых ситуаций.- Автоматика и вычислительная техника, 1982, PI, с.22-29.

29. Зорич В.А. Математический анализ. Ч.1.- М.: Наука, 198I, 544с.

30. Иносэ X., Сайто Т. Теоретические аспекты анализа и синтеза сетей пакетной связи. ТИИЭР.- М.: Мир, 1978, т.66, №11,с .139-155.

31. Иносэ X. Интегральные цифровые сети связи: Введение в теорию и практику: Пер. с англ./Под ред. В.И.Неймана.- М.: Радио и связь, 1982, 320с.

32. Касти Дж. Большие системы. Связность, сложность и катастрофы. Пер. с англ. /Под ред. Ю.П.Гупало.- М.: Мир, 1982, 216с.

33. Клейнрок JI. Коммутационные сети. Стохастические потоки и задержки сообщений. Пер. с англ. /Под ред. А.А.Первозван-ского.- М.: Наука, 1970, 255с.

34. Клейнрок Л. Принципы и уроки пакетной связи. ТЙИЭР,- М.: Мир, 1978,т.66, №11, с.30-42.

35. Клейнрок Л. Теория массового обслуживания. Пер. с англ. /Под ред. В.И.Неймана.- М.: Машиностроение, 1979, 432с.

36. Клейнрок Л. Вычислительные сети с очередями. Пер. с англ. /Под ред. Б.С.Цыбакова.- М.: Мир, 1979, 600с.

37. Лазарев В.Г., Паршенков Н.Я. Игровой метод динамического управления сетью связи.- В кн.: Построение управляющих устройств и систем. M., 1974, с.161-172.

38. Лазарев В.Г. Управление потоками информации в сетях связи ЭВМ. В кн.: Вычислительные сети коммутации пакетов. Рига: Зинатне, 1979, с.8-12.

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

40. Липаев В.В. Распределение ресурсов в вычислительных системах.- М.: Статистика, 1979, 247с.

41. Математическая энциклопедия. T.I.-M.: Советская энциклопедия, 1977,1151с.

42. Математическая энциклопедия. Т.4.- М.: Советская энциклопедия, 1984, 1215с.

43. Методы моделирования и измерений в сетях с коммутацией пакетов. /Ф.А.Тобаги, М.Герла, Р.У.Пиблз, Э.Г.Маннинг. ТИИЭР, 1978, т.66, №11, с.157-185.

44. Мизин И.А., Уринсон Л.С., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений.: Изд. 2-е, перераб. и доп. М.: Связь, 1977, 328с.

45. Мизин И.А., Кулешов А.П., Богатырев В.А. Современное состояние проблемы управления потоками в сетях пакетной коммутации (датаграммный режим). (Предварительная публикация).-М., 198I, 63с.

46. Моисеев Н.Н. Математические задачи системного анализа. -М.: Наука, 198I, 488с.

47. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач.- М.: Наука, 1982, 256с.

48. Паршенков Н.Я. Вероятностно-игровой метод динамического управления потоками на сетях коммутации каналов.- В кн. : Системы управления сетями. М.: Наука, 1980, с.3-9.

49. Поляк Б.Т. Введение в оптимизацию.- М.: Наука, 1983, 384с.

50. Постон Т., Стюарт й. Теория катастроф и ее приложения. Пер. с англ. А.В.Чернавского.- М.: Мир, 1980, 607с.

51. Растригин Л.А. Современные принципы управления сложными объектами.- М.: Советское радио, 1980, 232с.

52. Самойленко С.И. 0 критериях оценки субоптимальных алгоритмов поиска решений.- Автоматика и вычислительная техника, 1977, №3, с.54-56.

53. Синтез информационных сетей и устройств на основе графов кодовых множеств. /В.И.Васильев, Л.Я.Заманский, В.М.Коновалов, Ф.Э.Келлер.- М.: АН СССР. Научный совет по комплексной проблеме "Кибернетика", 1979, 69с.

54. Соловьев В.А. Сети ЭВМ. Зарубежная электронная техника.-198I, PI, с.3-48.

55. Теория сетей связи. Учебник для вузов связи./Под ред. В.Н. Рогинского.- М.: Радио и связь, 1981, 192с.

56. Теория систем и методы системного анализа в управлении и связи,- М.: Радио и связь, 1983, 248с.

57. Умрихин 10.Д. Адаптивное управление и эффективность сети связи с централизованным контролем и принятием решений.

58. В кн.: Информационные сети и их структура. М., 1976,с.34-69.

59. Умрихин 30. Д. Проектирование систем передачи данных и сетей ЭВМ.- М., 1981, 108с.

60. Филипс Д., Гарсия-Диас А. Методы анализа сетей. Пер.с англ. /Под ред. Б.Г.Сушкова.- М.: Мир, 1984, 496с.

61. Форд Л.Д., Фолкерсон Д. Потоки в сетях.- М.: Мир, 1966,276с.

62. Фролов В. Если бы у Гераклита была ЭВМ.- "Правда", №135(24026), 14 мая 1984г.

63. Френк Г., Фриш И. Сети, связь и потоки. Пер. с англ.- /Под ред. Д.А.Поспелова.- М.: Связь, 1978, 448с.

64. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974, 519с.

65. Чиллингуорт Д. Структурная устойчивость математических моделей. Значение методов теории катастроф.- В кн.: Математическое моделирование. Пер. с англ. /Под ред. 10.П.ГУпало. М., Мир, 1979,с.249-276.

66. Шаповалов М.И. Разработка методов предотвращения перегрузок в системах телеобработки информации (на примере гражданской авиации). Диссертация на соискание ученой степени кандидата технических наук.- М.: МИЙГА, 1981, 230с.

67. Шварц М. Сети ЭВМ. Анализ и проектирование.- М.: Радио и связь, 1981, 336с.

68. Шеметов B.B. Об оптимальных алгоритмах маршрутизации для сетей ЭВМ с коммутацией пакетов,- Автоматика и вычислительная техника, 1984, №2, с.30-40.

69. Экланд И. Элементы математической экономики. Пер. с франц. /Под ред. А.А.Корбута.- М.: Мир, 1983, 248с.

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

71. Яновский Г.Г. Сети передачи данных с коммутацией пакетов.-М.: Наука, Электросвязь. Итоги науки и техники, 1980, т.2, с.3-47.

72. Список работ, опубликованных автором

73. Кузьмин А.Л. Об использовании гиперэкспоненциальной системы массового обслуживания в качестве модели выходной линии узла СЦЦ.- В сб.: Информационно-вычислительные сети гражданской авиации. М., МИИГА, 1982, c.III-115.

74. Кузьмин А.Л. Анализ распределения длины очереди в СМО с двумя потоками требований.- В сб.: Вопросы проектирования информационно-вычислительной сети гражданской авиации. М., МИИГА, 1983, с.27-31.

75. Кузьмин А.Л. Об особенностях отображений, задающих оптимальную маршрутизацию.- В сб.: Применение малых ЭВМ в системах обработки информации гражданской авиации, М.: МИИГА, 1984, с.16-21.

76. Кузьмин А.Л. Об обслуживании потока разнородных требований одним прибором.- В сб.: Проектирование и эксплуатация информационно-вычислительных комплексов. Тезисы докладов научно-технической конференции.Пенза, 1983 (в печати).

77. Кузьмин А.Л. Динамические свойства алгоритмов маршрутизации и задачи ограничения нагрузки.- Деп. ВИНИТИ от 23.07.84, №5320-84 Деп., М., 1984, 25с.

78. Кузьмин А.Л. Оптимальность по Парето в задачах управления потоками.- Деп. ЦНШ ГА от 28.08.84, Р248га-Д84, М., 1984, 20с.

79. Кузьмин А.Л. Алгоритмы маршрутизации в дифференциальной метрике.- Деп. ЦНТИ ГА от 28.08.84, №247га-Д84, М., 1984-, 29с.

80. П.1.2. Кузьмин А.Л. Проблемы оптимального управления потоками, с.24-32.

81. А ЗЪСХс/ А. А. Ми НI сот то с/I {у пеЬи/огк ¿Вот,—А 5и?уеу. Ме^оъкь, 1978, А/1, р. 37-91.

82. А1ксп$ У.Я. Ра 16. соп1ъо€ \ ±"гап^ро71 пе^о'гк с/ вЛ/А.-1ЕЕЕ ТгапъасИопя оп соттип1саИоп$, 1980, V. 28, а/4, р. 527-538.

83. ВеЫзесав Ъ.Р. СВасс оу орИтав 1оиЬ1п^ аВ^о^сЬгтз соттип1са1юп пе1чгоък$1пЬС1паИопа£ соп^егепсе оп сотри^съ соттип1саИопъ. РгосееЫсп^, А1Вап1ау 192>0, р. 71- 75.

84. СЯи W.W., SBett M.У. A hieïazcBicaB zouiing and f£o\xs conlwê poêicy ( HRFC) fot pacnet svritcÂed neiWSKS.1. : Compute2 performance, /977y p. 485-498.

85. Fioyd R.W. Shortest pathCommunications of ACM, У une 1962, p. 345.

86. Flatta L., GerBa M., KBeimoK L. ТЯе /¿ow dewldtion method An арргоасЯ to store and - fozwurd communication network design. — A/etwo^KS, 1973, V.3,p. 93 /33.

87. Gafni £.M., BevtseKas 2. P. Patft assignement foi vittuaB circuit touting. — SIGCOMM '83. Symposium Communications aicBitectuies $ ProtocoBs, p.21-25.

88. GaBBagei r.g. A minimum deiay touting aBgovitm using distributed Computation.— IEEE Transactionson communications, 1977, V. COM-25, 73-84.

89. GerBa M., Mason TJ. SistriButed touting in BiBtid pacnet and circuit data nctwo-zKS.— СОМРСОМ- 78, Ргос. IEEE, 1978, p. /25-13/.

90. Kamoun F.} HBeinrocn L. An Anaiysis of сЯаъес/ storage in a computet netwozK envizonement .— Ptoe. 8-tB Hawaii Int. Conf. System Science, /976, p. 89-92.

91. Kamoun FKEeinzocK L. Analysis of skated finite stozage in a computet netwozK node envizonement uncfez qenezaB traffic conditions. — IEEE Transactions on Computez, V. 28, A/7, 1980, p. 992- 1003.

92. HEeintOK L., Kezmani P. Static fEow contzoE in stove -and fo'zwatd computet netwotK.— IEEE Ttansactions on communications, /980, V. COM-28, A/2, p. 271- 279.

93. KEeinïoK I. j Ketmani P. Dinamic ffovc/ contzoB in stoze-and fot\x/atd computet netwotxs. — TE EE Transactions on communications, /980, V. COM -28, A/2, p. 263-271.

94. HBeinzoK L., GezEa M. F Bow ContzoB; A comparative.

95. Suzvey. — IEEE Transactions on communications, 1980, V.COM-28, //4, p. 553-574.

96. LaBetouBEe 7., Pujoeee G. A studu of f¿o\X/S iflïoug vi ttuaB circuits. — Computet netvvOZKS, /98/, p //9- Y26.

97. Mazuyama K,, Sdottet D. Dinamic zoute selection aEgotitms fot session Based communieaiion net wot ks 7-SIGCOMM '83. Symposium. Communications atcfii-teciute PzotocoEs, p. /62-/69.

98. Mc Qui EE an d., Ricdet 7., Rosen E.C. An overview of tfie new touting aBgozitm fot íñe ARPANET IEEE Tzansactions on communications, /980,

99. V. COM. 28, A/5, p. 7//-7/9.toi OBdet W. QuaEitative ana By si s of congestion-sensitive touting. — In: FEow conitoB in computet neéwotxs, Amsterdam, A/ozih RoBBand, /979, p. /3/-/54.

100. RosenBtic C. Tfie updating pzotocoB of ARPANET'S new touting aBgotitm. — Computet A/etwotKS, /920, V. a//,p. 11-19.

101. Rudin //., MueEEet H. Dynamic Routing and fBow conitoE. -IEEE Tzansactions on communications, /980, v.28, A/7,p.1030-104/.