Дипломная работа

от 20 дней
от 9999 рублей

Заказать

Курсовая работа

от 10 дней
от 1999 рублей

Заказать

Реферат

от 3 дней
от 699 рублей

Заказать

Контрольная работа

от 3 дней
от 99 рублей
за задачу

Заказать

Диссертация

Сроки и стоимость индивидуальные

Заказать

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

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

  • Тема: Методы повышения эффективности функционирования сетей передачи данных
  • Автор: Коновалов Сергей
  • Тип работы: Диссертация
  • Предмет: Информатика, Вычислительная техника, телекоммуникации
  • Страниц: 151
  • Год сдачи: 2001
  • ВУЗ, город: ТВЕРСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
  • Цена(руб.): 7000 рублей

Заказать персональную работу

Выдержка

Эффективное функционирование любой технической, экономической или социальной системы в настоящее время немыслимо без ее качественного информационного обеспечения. Ряд важнейших функций при этом возлагается на сеть передачи данных (СПД). Это и определяет актуальность указанной темы с учетом непрерывного развития новых информационных технологий, роста материальных и финансовых затрат на их создание. Существенно возрастает роль научных обоснований при создании сложных информационных систем и управлении их функционированием, в связи, с чем в представляемой работе решается научная задача разработки комплекса математических моделей методов и алгоритмов оптимизации функционирования и проектирования СПД. Изучение и анализ специальной литературы, проделанный в разделе 1, позволил выделить 3 группы актуальных вопросов, наиболее полно отвечающих решению названной научной задачи: – вопросы эффективного функционирования СПД и управления информационными потоками в них; – вопросы обеспечения высокой системной, технической надежности и живучести СПД; – вопросы структурной оптимизации СПД при проектировании и разработке. Указанные вопросы определяют собой структуру и содержание исследования, представленные на плакате 1. Центральным вопросом, определяющим эффективность функционирования СПД, является выбор маршрута доставки пакета абоненту с минимальной межконцевой задержкой (МКЗ). В разделе 2 разработаны новые методы построения кратчайших маршрутов (КМ). Наиболее эффективным из них является метод Эстафетного поиска, который обеспечивает построение всего множества КМ из некоторого узла-источника УИ при минимальном числе операций сравнения; при этом число шагов не более чем . Вычислительная система и весь объем расчетов представлен на плакате 2. При поиске только заданного КМ средний объем вычислений еще более снижается. Например, КМ найден уже на t=3–м шаге и проходит через вершины B9,10=<9,5,6,10>; при этом МКЗ Т9,10= 4 ед. и потребовалось выполнить всего 11 операций сравнения и 2 сложения. Для определения всего семейства КМ из УИ реально потребовалось выполнить до 30 операций сравнения и 14 сложений. Полученное семейство КМ записано в нижней половине плаката 2. Граф КМ получен методом направленного поиска, который в вычислительном плане уступает МЭП, однако представляет семейство КМ в виде, более удобном для статистического анализа при оптимизации топологической структуры СПД. Метод эстафетного поиска более эффективен для использования в ходе функ-ционирования СПД и в сетевых протоколах разных уровней. Эффективность МЭП подтверждается и сравнением его с известными методами (Форда, Флойда–Дейкстра). Блок–схема алгоритма МЭП представлена на плакате 3. Другим важным показателем функционирования СПД является надежность доставки пакета абоненту, зависящая от технической надежности средств и от выбора маршрута передачи пакета, т.е. от системной надежности. Постановка задачи максимизации системной надежности представлена формулами (1), (2) на плакате 4. Дополнительной информацией является матрица вероятностей надежной доставки пакетов между узлами коммутации. Построение наиболее надежного маршрута осуществляется МЭП-ом после сведения функции надежности (1) на плакате 4 к аддитивному виду. Из плаката 4 видно, что наиболее надежный маршрут <9,6,1,5> имеет в 2,5 раза большую МКЗ (10 вместо 4), однако самый короткий по МКЗ маршрут имеет низкую надежность (0,49 вместо 0,77). Обоснованный и примененный в работе обобщенный критерий средней задержки обеспечил более приемлемое решение, при этом МКЗ снизилась с 10 до 5,5, а системная надежность возросла с 0,49 до 0,73 (красный цвет на плакате 4). Однако при низкой технической надежности средств невозможно обеспечить высокий уровень системной надежности. Одним из способов повышения техниче-ской надежности является дублирование элементов системы. В работе сформулирована математическая модель, представленная на плакате 5, и разработан метод двойной оптимизации, позволяющий достаточно эффективно решать задачу оптимального дублирования элементов системы при наличии разнотипных дублирующих средств и при многих ограничивающих факторах. На плакате 5 представлен тестовый пример и полученный методом двойной оптимизации результат решения. В основе метода лежит градиентная итерационная процедура. На каждой итерации для каждого блока определяется оптимальный тип дублирующего средства (I этап). На II этапе выбирается номер дублируемого блока. Далее согласно пункту алгоритма «Пересчет тек. величин» на плакате 6 уточняются остатки ресурсов и другие текущие величины и цикл повторяется до израсходования ресурсов. Решение записано внизу на плаката 5. В разделе 3 разработан метод решения задачи выпуклого программирования (ВП) – метод граничной точки (МГТ). В основе МГТ лежит идея проекции градиента на область допустимых решений (ОДР). При этом текущая точка на каждой итерации перемещается в направлении градиента или его проекции (субградиента) на ОДР. Длина шага определяется оптимальной по Коши или лежит на границе ОДР в зависимости от соотношения параметров, определяющих величину смещения текущего решения ( П.8). Отдельные детали МГТ иллюстрируются на плакате 7. Более высокая вычислительная эффективность МГТ, чем у метода Франка–Вулфа, обусловлена двумя факторами: движением по направлению градиента и меньшим объемом счета на каждом шаге (в методе Франка–Вулфа решается задача ЛП, а МГТ параметр вычисляется по формуле). Полученное в работе правило останова (плакат 7,8) гарантирует заданную точность решения. Адекватность правила останова стано-вится очевидной, если рассмотреть предельные значения погрешности. Рассмотренные в предыдущих разделах методы позволяют получить количественную информацию, необходимую для решения ряда вопросов проектирования СПД и, прежде всего, оптимизации ее топологической структуры. Основные черты разработанной методики состоят в следующем. На основании матрицы задержек с максимально возможной ее полнотой ( , плакат 9) строится большой цикл семейств графов КМ. Статистическая обработка графов позволяет выявить частоты использования ЛС. Например, ЛС (1–5) использовалась всего 1 раз, что и записано в совмещенной матрице задержек–частот (плакат 9, 1–я строка). ЛС, выделенные синей тушевкой, не использовались ни разу. Удаление таких и редко используемых ЛС (желтая тушевка) позволило снизить полноту матрицы с , что сильно снижает затраты на СПД, т.к. ЛС – наиболее затратные ее элементы. Далее снова проводится большой цикл расчетов для сокращенной матрицы задержек. Например, для УИ вследствие ликвидации ЛС (4;7), КМ Т<4;7>=10 заменился другим Т<4;1;7>=11, при этом МКЗ несколько увеличилась. Статистическая обработка нового семейства позволяет найти новые частоты использования ЛС и новые МКЗ. Сумма МКЗ, как основная характеристика варианта данной топологической структуры, увеличилась с Т=639 ед. до Т=649 ед. ( 2%). Дальнейшая обработка и укрупнение полученных данных (формулы (1)–(3), плакат 10) позволяют выявить мало загруженные УК и рассмотреть вопрос об их ликвидации (например, и , синяя тушевка на плакате 9, снизу). При этом в ходе неформального анализа проверяется возможность выполнения других требований к СПД (двусвязность, живучесть и т.д.). СПД – сложная динамическая система, состояние которой зависит от многих параметров, изменяющихся во времени. Одним из важнейших таких параметров является входящий поток заявок (внешний трафик). Он определяет собой и внутренние информационные потоки (внутренний трафик), плотности потоков которого для каждого участка сети пропорциональны соответствующим частотам использования данных участков сети (плакат 9) при ее нормальном функционировании. Однако при изменении внешнего трафика будут меняться и внутренние потоки, а следовательно, если не обеспечить соответствующие пропускные способности ЛС и УК, то изменятся задержки в УК, изменятся КМ, внесенные в сетевые протоколы. Чтобы избежать этого в предлагаемой методике на основе данной плотности потока и заданной величины допустимой задержки определяется требуемая пропускная способность (плакат 10). Если весь ресурс (пропускная способность) сосредоточен в одном канале, то вместо номограммы (плакат 10) требуемая пропускная способность находится по формуле, представленной на плакате 10. Рассмотренная в работе методика позволяет определить основные параметры СПД, как один из альтернативных ее вариантов для дальнейшего рассмотрения на новом более высоком информационном уровне с привлечением более широкого круга специалистов и последующего имитационного моделирования системы. Таким образом, в рассмотренной работе разработан комплекс математических моделей, методов и алгоритмов для оптимизации функционирования и проектирования СПД. К новым относятся следующие основные результаты, полученные лично автором: – методы и алгоритмы направленного поиска КМ, удобные для использования при проектировании СПД; – метод и алгоритм ЭП для решения задачи маршрутизации в ходе функционирования СПД; – метод и алгоритм оптимизации системной надежности СПД; – метод алгоритм оптимизации надежности СПД при разнотипных резервирующих элементах и многих ограничивающих факторах; – метод и алгоритм ГТ для решения класса задач выпуклого программирования; – методика построения топологической структуры СПД, удовлетворяющей заданным требованиям. Разработанные модели, методы и алгоритмы могут быть использованы при разработке информационных систем при решении задач повышения эффективности их функционирования.

Содержание

Оглавление Введение ………………………………………………………… 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 с.

Форма заказа

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

Тип работы *
Предмет *
Название *
Дата Сдачи *
Количество Листов*
уточните задание
Ваши Пожелания
Загрузить Файлы

загрузить еще одно дополнение
Страна
Город
Ваше имя *
Эл. Почта *
Телефон *
  

курсовые, дипломные, контрольные на заказ скидки на курсовые, дипломные, контрольные на заказ

© 2010-2016, Все права защищены. Принимаем заказы по всей России.