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

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

Диссертационная работа выполнена в соответствии с работой Н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(24 026), 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 hieiazcBicaB zouiing and f? oxs conlwe poeicy (HRFC) fot pacnet svritcAed 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 stoveand fo’zwatd computet netwotK.— IEEE Ttansactions on communications, /980, V. COM-28, A/2, p. 271- 279.

93. KEeinioK I. j Ketmani P. Dinamic ffovc/ contzoB in stoze-and fotx/atd computet netwotxs. — TE EE Transactions on communications, /980, V. COM -28, A/2, p. 263−271.

94. HBeinzoK L., GezEa M. F Bow ContzoBA comparative.

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

96. LaBetouBEe 7., Pujoeee G. A studu of f? oX/S iflioug 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 ine 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 neewotxs, 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/.