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

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

Введение
Принятые сокращения и обозначения
1. Анализ методов повышения эффективности функциони-рования СПД и постановка задачи исследования
- 1. 1. Анализ методов оценки и повышения эффективности функ-ционирования СПД
- 1. 2. Постановка задачи и структурная схема исследования
- 1. 3. Выводы по разделу
2. Методы и алгоритмы маршрутизации пакетов в сети передачи данных
- 2. 1. Кратчайший маршрут при одинаковой загрузке узлов коммутации и метод направленного поиска
- 2. 2. Кратчайший маршрут при различных загрузках узлов коммутации и модифицированный метод направленного поиска
- 2. 3. Метод эстафетного поиска кратчайшего маршрута
- 2. 4. Выводы по разделу
3. Математические модели и методы оценки и оптимизации надежности функционирования сети передачи данных
- 3. 1. Повышение системной надежности сети передачи данных методом маршрутизации
- 3. 2. Оптимальное резервирование разнотипными элементами при многих ограничивающих факторах
  - 3. 2. 1. Постановка задачи оптимального резервирования блоков сети разнотипными элементами
  - 3. 2. 2. Решение задачи оптимального резервирования при различ-ных элементах методом двойной оптимизации
  - 3. 2. 3. Пример решения и алгоритм метода двойной оптимизации
- 3. 3. Метод граничной точки для решения задачи выпуклого программирования
  - 3. 3. 1. Постановка задачи и содержание метода граничной точки
  - 3. 3. 2. Определение граничной точки и оптимизация на поверхности области допустимых решений
  - 3. 3. 3. Алгоритм метода граничной точки
  - 3. 3. 4. Обеспечение точности решения и оценка объема вычислений
- 3. 4. Выводы по разделу
4. Методы анализа и синтеза СПД
- 4. 1. Анализ и синтез топологической структуры СПД
  - 4. 1. 1. Параметрический анализ топологии СПД
  - 4. 1. 2. Анализ и синтез топологии СПД на основании графов КМ
- 4. 2. Сравнительный анализ вариантов СПД и учет основных требований к ней при проектировании
  - 4. 2. 1. Основные положения методики сравнительного анализа ва-риантов СПД
  - 4. 2. 2. Требование двусвязности при проектировании топологиче-ской структуры СПД
  - 4. 2. 3. Ограничение межконцевых задержек
  - 4. 2. 4. Учет входящего потока заявок
  - 4. 2. 5. Определение пропускных способностей СПД
- 4. 3. Выводы по разделу
Заключение
Приложения
1. Оценка числа возможных способов коммутации 2-х узлов
2. Построение кратчайшего маршрута по матрице задержек
3. Определение направления градиента относительно области
4. Акты реализации результатов диссертации
Список использованных источников

Общая характеристика работы

Актуальность и цель работы. Каждый вид управленческой деятельности, осуществляемой на любом уровне, от простейших технологических процессов до крупных организационных систем, предполагает использование информации о состоянии управляемого объекта и о его реакции на управляющие воздействия. Следовательно, успешное функционирование системы в решающей степени зависит от информационного звена, обеспечивающего сбор, обработку и доставку информации нужного качества в требуемом объеме и в приемлемые сроки. Поэтому одним из важнейших элементом управляющих систем являются сети передачи данных (СПД), осуществляющие основные функции по информационному обеспечению систем. Наряду с известными видами электросвязи (телефон, телеграф, радио, телевидение) все шире входят в обиход такие виды коммуникаций, как Internet (WEB, электронная почта, IP-телефония), цифровые сети с предоставлением комплексных услуг (ISDN), сотовая, спутниковая связь и др. Все это стало возможным благодаря развитию микроэлектроники, вычислительной техники, цифровых систем передачи данных, систем волоконно-оптической связи и других достижений в науке и технике. Современные СПД все более превращаются в сети интегрального обслуживания (СИО, ISDN) с расширением области их функциональных возможностей, что влечет за собой, однако, увеличение сложности и стоимости системы. Возрастающий поток научных исследований в данной области подтверждает ее актуальность. В связи с этим, основной целью работы является разработка методов повышения эффективности функционирования СПД.

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

Решаемые при этом научные вопросы могут быть представлены в виде комплекса следующих трех групп математических моделей и мето-дов:

— методы и алгоритмы маршрутизации пакетов информации в СПД;

— модели, методы и алгоритмы оптимизации системной и технической надежности СПД и ее элементов;

— методы оптимизации топологической структуры СПД и построения ее варианта на начальных этапах проектирования.

Научная новизна и основные результаты. К новым, или содержащим элемент новизны, относятся следующие взаимосвязанные методы и алгоритмы, выносимые на защиту:

— метод направленного поиска (МНП) кратчайшего маршрута (КМ) на графе (алгоритмы МНП-1 и МНП-2);

— метод эстафетного поиска кратчайшего маршрута (МЭП);

— метод и алгоритм оптимизации системной надежности;

— метод двойной оптимизации (МДО) — для оптимизации технической надежности системы при разнотипных дублирующих элементах и многих ограничивающих факторах;

— метод граничной точки (МГТ) — для решения задачи выпуклого программирования (ВП);

— методика построения топологической структуры при проектировании альтернативного варианта СПД.

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

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

В основе достоверности и адекватности разработанных методов лежит корректное использование принципов системного анализа и современного математического аппарата при разработке и обосновании методов и алгоритмов. Достоверность МЭП — наиболее эффективного метода поиска КМ на графе, обусловлена реализацией на основе предложенного алгоритма условий глобального минимума. Проведенные оценки требуемого объема вычислений и сравнительный анализ с известным алгоритмом Флойда подтверждают высокую вычислительную эффективность алгоритма, реализующего метод эстафетного поиска.

Метод двойной оптимизации обобщает некоторые известные ме-тоды оптимального резервирования на случай разнотипных резервирующих элементов и при наличии многих ограничений на переменные. Достоверность решения обусловлена выполнением условий оптимальности Куна-Таккера с учетом дискретности переменных.

Эффективность метода граничной точки показана путем сравни-тельного анализа с наиболее известным (для данного класса задач) мето-дом Франка-Вулфа.

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

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

Апробация и публикации. Полученные результаты в форме научных докладов (сообщений) представлялись на научных конференциях (см. список публикаций), научных семинарах (ТГТУ, ТвТУ). По материалам диссертации опубликовано 12 печатных работ, список которых представлен в конце автореферата.

Внедрение результатов работы. В 1999 г. под руководством автора на предприятии «Витэкс» (г. Тверь) разработана и внедрена локальная вычислительная сеть (акт внедрения). Материалы диссертации используются в учебном процессе на факультете АСУ ТГТУ, в Тверском филиале МЭСИ.

Показать весь текст

Список литературы

Волкова В.Н., Денисов А. А. Основы теории систем и системного анализа. — Санкт-Петербург.: Изд-во СПбГТУ, 1997. — 510 с.
Перегудов Ф.И., Тарасенко Ф. П. Введение в системный анализ. — М.: Высшая школа, 1989. — 367 с.
Воронков В.А. Системный анализ экономики связи. — М.: Радио и Связь, 1993. — 127 с.
Моисеев Н.Н. Математические задачи системного анализа. — M.: Наука. — 488 с.
Исследование операций. Т.1. Математические основы и математические методы. //Под ред. Дж. Моудера, С. Элмаграби (пер. с англ.). — М.: Мир, 1981. — 712 с.
Вентцель Е.С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988. — 83 с.
Вагнер Г. Основы исследования операций Т.1 (пер. с англ.).- М.: Мир, 1972. — 335 с.
Системный анализ и исследование операций. Кн.1 Оценочные модели и методы. //Под ред. Е. А. Берзина. — Тверь.: ТГТУ, 1996. — 152 с.
Дегтярев Ю.И. Исследование операций. — М.: Высшая школа. — 1986. — 320 с.
Васильев Н.С. Математическое моделирование в задачах маршрутизации сетей передачи данных (многокритериальный подход) //Диссертация на соискание уч.ст. доктора физико-математических наук. — М.: ИВВС, РАН, 1999. — 231 с.
Филипс Д., Гарсиа-Диас А. Методы анализа сетей (пер. с англ.). — М.: Мир, 1984. — 496 с.
Рейнгольд Э., Нивергельдт Ю., Део М. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.
Гери, Джонсон Д. Вычислительные машины и трудно решаемые задачи — М.: Мир, 1983.
Основы теории оптимального управления. //Под ред. В. Ф. Кротова. — М.: Высшая школа, 1990. — 429 с.
Протоколы и методы управления в сетях передачи данных. //Под ред. Ф. Ф. Куо. — М.: Радио и Связь, 1985. — 479 с.
Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981.
Советов Б.Я., Яковлев С. А. Построение сетей интегрального обслуживания. — Л.: Машиностроение, 1990. — 330 с.
Барлоу Р., Прошан Ф. Математическая теория надежности (пер. с англ.). — М.: Сов. радио, 1969. — 487.
Нечипоренко В.И. Структурный анализ и методы построения надежных систем. — М.: Сов. радио, 1968.
Ушаков И.А. Методы решения простейших задач оптимального резервирования. — М.: Сов. радио, 1969. — 175 с.
Ушаков И.А. Вероятностные модели надежности информационно-вычислительных систем. — М.: Радио и связь, 1991. — 132 с.
Самойленко А.А., Давыдов В. В. и др. Вычислительные сети: адаптивность, помехоустойчивость. — М.: Наука, 1981. — 227 с.
Дудник Б.Я., Овчаренко В. Ф. Надежность и живучесть систем связи. — М.: Радио и связь, 1984.
Артамонов Г. Т. Топология регулярных вычислительных сетей и средств. — М.: Радио и связь, 1985. — 192 с.
Цвиркун А.Д. Основы синтеза структуры сложных систем. — М.: Наука, 1982. — 200 с.
Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей. //Автоматика. — 1981. — № 4 — с. 27−40.
Агаян А.А. Исследование алгоритмов многокритериальной оптимизации топологии вычислительных сетей. //Препринт / научный совет по комплексной проблеме «Кибернетика» АН СССР. — М.: Наука, 1984. — 56 с.
Цвиркун А.Д., Акинфиев В. К., Филиппова В. А. Имитационное моделирование в задачах синтеза структуры сложных систем. — М.: Наука, 1985. — 173 с.
Федотов Е.В. Разработка и исследование алгоритмов синтеза топологической структуры сетей передачи данных АСМО. //Диссертация кандидата технических наук. — М.: АН ИПУ, 1988.
Берсекас Д., Галлагер Р. Системы передачи данных. — М.: Мир, 1989.
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.
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.
Емеличев В.А. и др. Лекции по теории графов. — М.
Берж К. Теория графов и ее применение. — М.: ИИЛ, 1962. — 319.
Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. — 412.
Вишневецкий В.М., Федотов Е. В. Комбинаторный алгоритм синтеза топологической структуры сети пакетной коммутации. //12-й Всесоюзный семинар по вычислительным сетям. — М.: АН СССР, 1986.
Немировский А.С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. — М.: Наука, 1979. — 383 с.
Клейнрок Л. Вычислительные системы с очередями. — М.: Мир, 1979. — 600 с.
Клейнрок Л. Теория массового обслуживания. //Под ред. В. И. Неймана (пер. с англ.). — М.: Машиностроение, 1979. — 431 с.
Гнеденко Б.В., Коваленко И. Н. Введение в теорию массового обслуживания. — М.: Наука, 1987. — 336 с.
Овчаров Л.А. Прикладные задачи теории массового обслуживания. — М.: Машиностроение, 1969.
Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения (пер. с англ.). — М.: Радио и связь, 1992. — 504 с.
Дубов Ю.А., Травкин С. И., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. — 250 с.
Подиновский В.В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. — М.: Наука 1982. — 286 с.
Машунин Ю.К. Методы и модели векторной оптимизации. — М.: Наука, 1986. — 140 с.
Системный анализ и исследование операций. //Кн.2. Оптимизационные модели и методы. //Под ред. Е. А. Берзина — Тверь.: ТГТУ, 1998. — 182 с.
Шеннон К., Роберт Ю. Имитационное моделирование систем — искусство и наука. (пер. с англ.) //Под ред. Е. К. Масловского — М.: Мир, 1978. — 418 с.
Советов Б.Я., Яковлев С. А. Моделирование систем. — М.: Высшая школа, — 1985.
Шварц М. Сети ЭВМ. Анализ и проектирование. — М.: Связь и радио, — 1981.
Зайченко Ю.П., Гонта Ю. В. Структурная оптимизация сетей ЭВМ. — Киев.: Техника, — 1986.
Максименков А.В., Селезнев М. Л. Основы проектирования информационно-вычислительных систем и сетей ЭВМ. — М.: Радио и связь, — 1991.
Демидович Б.П., Марон И. А. Основы вычислительной математики. — М.: Наука, — 1970. — 664 с.
Вентцель Е.С. Теория вероятностей. — М.: Наука, 1964. — 576 с.
Гмурман В.Е. Теория вероятностей и математическая статистика. — М.: Высшая школа, — 1977. — 479 с.
Берзин Е.А., Смирнов Д. В. Два алгоритма определения множества Парето-оптимальных решений многокритериальной задачи линейного программмирования. //Программные продукты и системы. — Тверь.: ЦПС, — 1997. — с. 28−33.
Берзин Е.А., Палюх Б. В. Оптимизация надежности АСУ методом нормированных функций. //СНТ-Синтез систем вычислительного эксперимента, ч.1. — Апатиты, КНЦ РАН, 1995. — с. 112−121.
Берзин Е.А., Палюх Е. В., Смирнов Д. В., Карначев И. П. Алгоритм определения оптимального состава разнотипных средств для резервирования блока системы. //СНТ-Интеллектуальные инструментальные средства вычислительного эксперимента. — Апатиты, КНЦ РАН, 1997. — с. 171−179.
Карманов В.Г. Математическое программирование. — М.: Наука, 1986. — 285 с.
Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. — М.: Сов. радио, 1974. — 303 с.
Муртаф Б. Современное линейное программирование. — М.: Мир, 1984. — 224 с.
Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 318 с.
Сухарев А.Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. — М.: Наука, 1986. — 325 с.
Корн Г., Корн Т. Справочник по математике для научных работников и инженерров. — М.: Наука, 1968. — 720 с.

Заполнить форму текущей работой