3. Определение направленности градиента относительно
области ……………………………………………………….
144
4. Акты реализации итогов диссертации …………………. . . 147
Перечень использованных источников ………………………. . 151
Выдержка
Действенное функционирование хоть какой технической, экономической либо общественной системы в настоящее время немыслимо без её высококачественного информационного снабжения. Разряд важных функций при этом возлагается на сеть передачи данных(СПД). Это и описывает злободневность указанной темы с учетом постоянного развития новейших информационных технологий, роста материальных и денежных издержек на их творение.
Значительно растет роль научных обоснований при разработке трудных информационных систем и управлении их функционированием, в связи, с чем в воображаемой работе решается научная задачка разработки комплекса математических моделей способов и алгоритмов оптимизации функционирования и проектирования СПД.
Исследование и анализ особой литературы, проскобленный в разделе 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. Наиболее высочайшая вычислительная эффективность МГТ, чем у способа Франка–Вулфа, обусловлена 2-мя причинами: ходом сообразно течению градиента и наименьшим объемом счета на каждом шаге(в способе Франка–Вулфа решается задачка ЛП, а МГТ параметр рассчитывается сообразно формуле). Приобретенное в работе верховодило останова(плакат 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.
Осмотренная в работе способ дозволяет найти главные характеристики СПД, как один из других её вариантов для предстоящего рассмотрения на новеньком наиболее высочайшем информационном уровне с привлечением наиболее широкого кружка профессионалов и следующего имитационного моделирования системы.
Таковым образом, в осмотренной работе изобретен комплекс математических моделей, способов и алгоритмов для оптимизации функционирования и проектирования СПД. К новеньким относятся последующие главные итоги, приобретенные собственно создателем:
– методы и методы направленного розыска КМ, комфортные для применения при проектировании СПД;
– метод и метод ЭП для решения задачки маршрутизации в ходе функционирования СПД;
– метод и метод оптимизации системной прочности СПД;
– метод метод оптимизации прочности СПД при разнотипных резервирующих элементах и почти всех ограничивающих причинах;
– метод и метод ГТ для решения класса задач выпуклого программирования;
– методика построения топологической структуры СПД, удовлетворяющей данным потребностям.
Разработанные модели, способы и методы имеют все шансы существовать применены при разработке информационных систем при решении задач повышения эффективности их функционирования.
Литература
Литература
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. Берзин Е. А. , Смирнов Д. В. 2 метода определения большого колличества Парето-оптимальных решений многокритериальной задачки линейного программмирования. //Программные продукты и системы. – Тверь. : ЦПС, - 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 с.
Эффективное функционирование любой технической, экономической или социальной системы в настоящее время немыслимо без ее качественного информационного обеспечени