Методы повышения эффективности функционирования сетей передачи данных.

Общая характеристика работы Актуальность и цель работы. Каждый вид управленческой деятельности, осуществляемой на любом уровне, от простейших технологических процессов до крупных организационных систем, предполагает использование информации о состоянии управляемого объекта и о его реакции на управляющие воздействия. Следовательно, успешное функционирование системы в решающей степени зависит от информационного звена, обеспечивающего сбор, обработку и доставку информации нужного качества в требуемом объеме и в приемлемые сроки. Поэтому одним из важнейших элементом управляющих систем являются сети передачи данных (СПД), осуществляющие основные функции по информационному обеспечению систем. Наряду с известными видами электросвязи (телефон, телеграф, радио, телевидение) все шире входят в обиход такие виды коммуникаций, как Internet (WEB, электронная почта, IP-телефония), цифровые сети с предоставлением комплексных услуг (ISDN), сотовая, спутниковая связь и др. Все это стало возможным благодаря развитию микроэлектроники, вычислительной техники, цифровых систем передачи данных, систем волоконно-оптической связи и других достижений в науке и технике. Современные СПД все более превращаются в сети интегрального обслуживания (СИО, ISDN) с расширением области их функциональных возможностей, что влечет за собой, однако, увеличение сложности и стоимости системы. Возрастающий поток научных исследований в данной области подтверждает ее актуальность. В связи с этим, основной целью работы является разработка методов повышения эффективности функционирования СПД. Научная задача и решаемые вопросы. Указанная цель может быть достигнута в том случае, если сетевые протоколы разных уровней, обеспечивающие процесс функционирования СПД, будут основаны на эффективных и надежных алгоритмах маршрутизации и при соответствующей топологии сети, поэтому научной задачей, решаемой в работе, является разработка комплекса математических моделей, методов и алгоритмов оптимизации функционирования и проектирования СПД. Решаемые при этом научные вопросы могут быть представлены в виде комплекса следующих трех групп математических моделей и мето-дов: - методы и алгоритмы маршрутизации пакетов информации в СПД; - модели, методы и алгоритмы оптимизации системной и технической надежности СПД и ее элементов; - методы оптимизации топологической структуры СПД и построения ее варианта на начальных этапах проектирования. Научная новизна и основные результаты. К новым, или содержащим элемент новизны, относятся следующие взаимосвязанные методы и алгоритмы, выносимые на защиту: - метод направленного поиска (МНП) кратчайшего маршрута (КМ) на графе (алгоритмы МНП-1 и МНП-2); - метод эстафетного поиска кратчайшего маршрута (МЭП); - метод и алгоритм оптимизации системной надежности; - метод двойной оптимизации (МДО) - для оптимизации технической надежности системы при разнотипных дублирующих элементах и многих ограничивающих факторах; - метод граничной точки (МГТ) - для решения задачи выпуклого программирования (ВП); - методика построения топологической структуры при проектировании альтернативного варианта СПД. Теоретические основы и методы исследования. Для анализа и синтеза СПД как сложной системы, в работе использовалась методология системного анализа; методы исследования операций и, в первую очередь, методы математического программирования; теория графов, теория вероятностей и математическая статистика, теория массового обслуживания, а также методы проектирования систем. Достоверность результатов и их практическая значимость. Раз-работанный комплекс математических моделей и методов имеет конкрет-ную прикладную направленность и позволяет достаточно эффективно решать ряд вопросов оценки и повышения эффективности функционирования и проектирования СПД. Это обеспечит более рациональное использование материальных, денежных и людских ресурсов при создании СПД и в ходе ее эксплуатации, что становится особо актуальной проблемой по мере увеличения сложности СПД. В основе достоверности и адекватности разработанных методов лежит корректное использование принципов системного анализа и современного математического аппарата при разработке и обосновании методов и алгоритмов. Достоверность МЭП - наиболее эффективного метода поиска КМ на графе, обусловлена реализацией на основе предложенного алгоритма условий глобального минимума. Проведенные оценки требуемого объема вычислений и сравнительный анализ с известным алгоритмом Флойда подтверждают высокую вычислительную эффективность алгоритма, реализующего метод эстафетного поиска. Метод двойной оптимизации обобщает некоторые известные ме-тоды оптимального резервирования на случай разнотипных резервирующих элементов и при наличии многих ограничений на переменные. Достоверность решения обусловлена выполнением условий оптимальности Куна-Таккера с учетом дискретности переменных. Эффективность метода граничной точки показана путем сравни-тельного анализа с наиболее известным (для данного класса задач) мето-дом Франка-Вулфа. Для алгоритмов, реализующих итерационные процедуры получено условие останова, гарантирующее требуемую точность ре-шения. Эффективность разработанных методов, как правило, иллюстрируется модельными примерами. Апробация и публикации. Полученные результаты в форме научных докладов (сообщений) представлялись на научных конференциях (см. список публикаций) , научных семинарах (ТГТУ, ТвТУ). По материалам диссертации опубликовано 12 печатных работ, список которых представлен в конце автореферата. Внедрение результатов работы. В 1999 г. под руководством автора на предприятии «Витэкс» (г. Тверь) разработана и внедрена локальная вычислительная сеть (акт внедрения). Материалы диссертации используются в учебном процессе на факультете АСУ ТГТУ, в Тверском филиале МЭСИ.

Оглавление Стр. Введение ………………………………………………………… 5 Принятые сокращения и обозначения ……………………… 8 1. Анализ методов повышения эффективности функциони-рования СПД и постановка задачи исследования 1.1. Анализ методов оценки и повышения эффективности функ-ционирования СПД ……………………………………………... 9 1.2. Постановка задачи и структурная схема исследования ……… 12 1.3. Выводы по разделу 1 ………………………………………….. 16 2. Методы и алгоритмы маршрутизации пакетов в сети передачи данных 2.1. Кратчайший маршрут при одинаковой загрузке узлов коммутации и метод направленного поиска …………………………. 18 2.2. Кратчайший маршрут при различных загрузках узлов коммутации и модифицированный метод направленного поиска ….. 24 2.3. Метод эстафетного поиска кратчайшего маршрута ………….. 33 2.4. Выводы по разделу 2 ………………………………………….. 40 3. Математические модели и методы оценки и оптимизации надежности функционирования сети передачи данных 3.1. Повышение системной надежности сети передачи данных методом маршрутизации ……………………………………….. 42 3.2. Оптимальное резервирование разнотипными элементами при многих ограничивающих факторах ……………………………. 51 3.2.1. Постановка задачи оптимального резервирования блоков сети разнотипными элементами ………………………………….. 51 3.2.2. Решение задачи оптимального резервирования при различ-ных элементах методом двойной оптимизации ………………. 53 3.2.3. Пример решения и алгоритм метода двойной оптимизации … 57 3.3. Метод граничной точки для решения задачи выпуклого программирования 3.3.1. Постановка задачи и содержание метода граничной точки …. 69 3.3.2. Определение граничной точки и оптимизация на поверхности области допустимых решений …………………………………. 72 3.3.3. Алгоритм метода граничной точки ……………………………. 82 3.3.4. Обеспечение точности решения и оценка объема вычислений 85 3.4 Выводы по разделу 3 ………………………………………….. 89 4. Методы анализа и синтеза СПД 4.1. Анализ и синтез топологической структуры СПД 4.1.1. Параметрический анализ топологии СПД …………………….. 93 4.1.2. Анализ и синтез топологии СПД на основании графов КМ …. 96 4.2. Сравнительный анализ вариантов СПД и учет основных требований к ней при проектировании 4.2.1. Основные положения методики сравнительного анализа ва-риантов СПД …………………………………………………….. 106 4.2.2. Требование двусвязности при проектировании топологиче-ской структуры СПД ……………………………………………. 107 4.2.3. Ограничение межконцевых задержек …………………………. 114 4.2.4. Учет входящего потока заявок ………………………………… 115 4.2.5. Определение пропускных способностей СПД ………………... 123 4.3. Выводы по разделу 4 ………………………………………….. 131 Заключение ……………………………………………………... 132 Приложения ……………………………………………………. 1. Оценка числа возможных способов коммутации 2-х узлов …... 134 2. Построение кратчайшего маршрута по матрице задержек …... 136 3. Определение направления градиента относительно области ………………………………………………………. 144 4. Акты реализации результатов диссертации …………………... 147 Список использованных источников ……………………….. 151

Литература 1. Волкова В.Н., Денисов А.А. Основы теории систем и системного анализа. – Санкт-Петербург.: Изд-во СПбГТУ, 1997. – 510 с. 2. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. – М.: Высшая школа, 1989. – 367 с. 3. Воронков В.А. Системный анализ экономики связи. – М.: Радио и Связь, 1993. – 127 с. 4. Моисеев Н.Н. Математические задачи системного анализа. – M.: Наука. – 488 с. 5. Исследование операций. Т.1. Математические основы и математические методы. //Под ред. Дж. Моудера, С. Элмаграби (пер. с англ.). – М.: Мир, 1981. – 712 с. 6. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука, 1988. – 83 с. 7. Вагнер Г. Основы исследования операций Т.1 (пер. с англ.).- М.: Мир, 1972. – 335 с. 8. Системный анализ и исследование операций. Кн.1 Оценочные модели и методы. //Под ред. Е.А. Берзина. – Тверь.: ТГТУ, 1996. – 152 с. 9. Дегтярев Ю.И. Исследование операций. – М.: Высшая школа. – 1986. – 320 с. 10. Васильев Н.С. Математическое моделирование в задачах маршрутизации сетей передачи данных (многокритериальный подход) //Диссертация на соискание уч.ст. доктора физико-математических наук. – М.: ИВВС, РАН, 1999. – 231 с. 11. Филипс Д., Гарсиа-Диас А. Методы анализа сетей (пер. с англ.). – М.: Мир, 1984. – 496 с. 12. Рейнгольд Э., Нивергельдт Ю., Део М. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 476 с. 13. Гери, Джонсон Д. Вычислительные машины и трудно решаемые задачи – М.: Мир, 1983. 14. Основы теории оптимального управления. //Под ред. В.Ф. Кротова. – М.: Высшая школа, 1990. – 429 с. 15. Протоколы и методы управления в сетях передачи данных. //Под ред. Ф.Ф. Куо. – М.: Радио и Связь, 1985. – 479 с. 16. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. 17. Советов Б.Я., Яковлев С.А. Построение сетей интегрального обслуживания. – Л.: Машиностроение, 1990. – 330 с. 18. Барлоу Р., Прошан Ф. Математическая теория надежности (пер. с англ.). – М.: Сов. радио, 1969. – 487. 19. Нечипоренко В.И. Структурный анализ и методы построения надежных систем. – М.: Сов. радио, 1968. 20. Ушаков И.А. Методы решения простейших задач оптимального резервирования. – М.: Сов. радио, 1969. – 175 с. 21. Ушаков И.А. Вероятностные модели надежности информационно-вычислительных систем. – М.: Радио и связь, 1991. – 132 с. 22. Самойленко А.А., Давыдов В.В. и др. Вычислительные сети: адаптивность, помехоустойчивость. – М.: Наука, 1981. – 227 с. 23. Дудник Б.Я., Овчаренко В.Ф. Надежность и живучесть систем связи. – М.: Радио и связь, 1984. 24. Артамонов Г.Т. Топология регулярных вычислительных сетей и средств. – М.: Радио и связь, 1985. – 192 с. 25. Цвиркун А.Д. Основы синтеза структуры сложных систем. – М.: Наука, 1982. – 200 с. 26. Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей. //Автоматика. – 1981. - №4 – с. 27-40. 27. Агаян А.А. Исследование алгоритмов многокритериальной оптимизации топологии вычислительных сетей. //Препринт / научный совет по комплексной проблеме «Кибернетика» АН СССР. – М.: Наука, 1984. – 56 с. 28. Цвиркун А.Д., Акинфиев В.К., Филиппова В.А. Имитационное моделирование в задачах синтеза структуры сложных систем. – М.: Наука, 1985. – 173 с. 29. Федотов Е.В. Разработка и исследование алгоритмов синтеза топологической структуры сетей передачи данных АСМО. //Диссертация кандидата технических наук. – М.: АН ИПУ, 1988. 30. Берсекас Д., Галлагер Р. Системы передачи данных. – М.: Мир, 1989. 31. Prank H., Prish I.T., Chou W. Topological considerations in the design of the ARPA computer network. //APIPS Conf. (Montvale, New Jershu 1970) – New York: APIPS Presa – 1970. – vol. 36 – p. 581-587. 32. Lavia A., Mannin E.G. Perturbation techniques for topological optimization of computer networks //4 th Data Commun. Symp. – New York, 1978. – p. 4/16-4/23. 33. Емеличев В.А. и др. Лекции по теории графов. – М. 34. Берж К. Теория графов и ее применение. – М.: ИИЛ, 1962. – 319. 35. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 412. 36. Вишневецкий В.М., Федотов Е.В. Комбинаторный алгоритм синтеза топологической структуры сети пакетной коммутации. //12-й Всесоюзный семинар по вычислительным сетям. – М.: АН СССР, 1986. 37. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. – М.: Наука, 1979. – 383 с. 38. Клейнрок Л. Вычислительные системы с очередями. – М.: Мир, 1979. – 600 с. 39. Клейнрок Л. Теория массового обслуживания. //Под ред. В.И. Неймана (пер. с англ.). – М.: Машиностроение, 1979. – 431 с. 40. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: Наука, 1987. – 336 с. 41. Овчаров Л.А. Прикладные задачи теории массового обслуживания. – М.: Машиностроение, 1969. 42. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения (пер. с англ.). – М.: Радио и связь, 1992. – 504 с. 43. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. – М.: Наука, 1986. – 250 с. 44. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – М.: Наука 1982. – 286 с. 45. Машунин Ю.К. Методы и модели векторной оптимизации. – М.: Наука, 1986. – 140 с. 46. Системный анализ и исследование операций. //Кн.2. Оптимизационные модели и методы. //Под ред. Е.А. Берзина – Тверь.: ТГТУ, 1998. – 182 с. 47. Шеннон К., Роберт Ю. Имитационное моделирование систем – искусство и наука. (пер. с англ.) //Под ред. Е.К. Масловского – М.: Мир, 1978. – 418 с. 48. Советов Б.Я., Яковлев С.А. Моделирование систем. – М.: Высшая школа, - 1985. 49. Шварц М. Сети ЭВМ. Анализ и проектирование. – М.: Связь и радио, - 1981. 50. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. – Киев.: Техника, - 1986. 51. Максименков А.В., Селезнев М.Л. Основы проектирования информационно-вычислительных систем и сетей ЭВМ. – М.: Радио и связь, - 1991. 52. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Наука, - 1970. – 664 с. 53. Вентцель Е.С. Теория вероятностей. – М.: Наука, 1964. – 576 с. 54. Гмурман В.Е. Теория вероятностей и математическая статистика. – М.: Высшая школа, - 1977. – 479 с. 55. Берзин Е.А., Смирнов Д.В. Два алгоритма определения множества Парето-оптимальных решений многокритериальной задачи линейного программмирования. //Программные продукты и системы. – Тверь.: ЦПС, - 1997. – с. 28-33. 56. Берзин Е.А., Палюх Б.В. Оптимизация надежности АСУ методом нормированных функций. //СНТ-Синтез систем вычислительного эксперимента, ч.1. – Апатиты, КНЦ РАН, 1995. – с. 112-121. 57. Берзин Е.А., Палюх Е.В., Смирнов Д.В., Карначев И.П. Алгоритм определения оптимального состава разнотипных средств для резервирования блока системы. //СНТ-Интеллектуальные инструментальные средства вычислительного эксперимента. – Апатиты, КНЦ РАН, 1997. – с. 171-179. 58. Карманов В.Г. Математическое программирование. – М.: Наука, 1986. – 285 с. 59. Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. – М.: Сов. радио, 1974. – 303 с. 60. Муртаф Б. Современное линейное программирование. – М.: Мир, 1984. – 224 с. 61. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 318 с. 62. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986. – 325 с. 63. Корн Г., Корн Т. Справочник по математике для научных работников и инженерров. – М.: Наука, 1968. – 720 с.