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

Введение.

Принятые сокращения и обозначения.

1. Анализ методов повышения эффективности функционирования СНД и постановка задачи исследования

1.1. Анализ методов оценки и повышения эффективности функционирования СПД.

1.2. Постановка задачи и структурная схема исследования.

1.3. Выводы по разделу 1.

2. Методы и алгоритмы маршрутизации пакетов в сети передачи данных

2.1. Кратчайший маршрут при одинаковой загрузке узлов коммутации и метод направленного поиска.

2.2. Кратчайший маршрут при различных загрузках узлов коммутации и модифицированный метод направленного поиска

2.3. Метод эстафетного поиска кратчайшего маршрута.

24. Выводы по разделу 2.

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 Выводы по разделу 3.

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. Выводы по разделу 4.

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

Информационные технологии берут свое начало с момента появления первых вычислительных машин и к настоящему времени прошли четыре основных этапа своего развития. Это были этапы внедрения и широкой эксплуатации ЭВМ среднего и малого классов, персональных компьютеров. Четвертый этап - этап повсеместного использования сетевых технологий - западными странами практически пройден. В этих странах наступила эпоха Internet. Наша страна еще только подошла к серьезному использованию сетевых технологий. Проходят времена бездумного внедрения сетей на предприятиях и в организациях. Руководители и простые пользователи поняли все выгоды, которые предоставляет грамотно спроектированная и построенная сеть. Уже понятно, что организация, позволяющая строить у себя систему, не отвечающую современным и насущным требованиям, обречена на неуспех.

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

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

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

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

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

Комплекс математических методов и алгоритмов, разработанный в ходе решения поставленной научной задачи, можно рассматривать как вариант решения трех групп взаимоувязанных вопросов:

- о методах дальнейшего сокращения времени доставки информации потребителю;

- о методах оптимизации системной и технической надежности для более сложных структур и условий функционирования СПД;

- о вопросах выбора и обоснования варианта рациональной структуры СПД и пропускных способностей ее элементов.

Методы и алгоритмы, позволяющие получать ответы на указанные вопросы и содержащие элементы новизны, определяют собой структуру данной работы и ее содержание.

Принятые сокращения и обозначения

ГКМ - граф КМ;

КМ - кратчайший маршрут;

ЛП - линейное программирование;

ЛПР - лицо,принимаюш;ее решение;

ЛУ - линия уровня;

ЛС - линии связи;

МГТ - метод граничной точки;

МДО - метод двойной оптимизации; мкз - межконцевая задержка;

МНП-1 - алгоритм №1 метода направленного поиска; МНП-2 - алгоритм №2 МНП; ОЖИ - обыкновенные жордановы исключения;

ОВ - опорный вариант;

ОЗУ - оперативно запоминаюп1;ее устройство; ОП - опорный план; р. - раздел;

ТКС - телекоммуникационная система; т.о. - таким образом; УИ - узел-источник; УП - узел-приемник; УК - узел коммутации; - множество номеров элементов; ЛС = [хЗ)А - вектор-строка размера п; х= вектор-столбец размерам; хА = X - транспонированный вектор; л: = [х; У = X. - матрица тхп; - номер итерации (шага); л:' = [хА )А - текупдая точка;

А^'А х а - упорядоченное множество кортеж) точек (траектория точки х'); {цк; у} - кортеж элементов;

ТА1(к,],1) - межконцевая задержка между узлами коммутации (к,1) при данном маршруте {к,.],.1); ((г, у)) - кортеж пар элементов (дуг); - область допустимых решений (ОДР);

Вх с О л - область допустимых граничных решений; дг{х)дГ(х) Эх, значение частной производной в точке х ;

V - квантор общности;

3 - квантор существования; а - знак включения; е - знак принадлежности; П - пересечение множеств; и - объединение множеств; \ - вычитание множеств; 0 - пустое множество; л - логическое умножение;

V - логическое сложение;

- знак эквивалентности;

- знак следования; а,Ь) - скалярное произведение векторов аиЬ.

Выводы по разделу 4

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

2. Сформулированы необходимые условия двусвязности сети СПД и методы построения запасных КМ. Двусвязность практически не увеличивает надежность СПД, однако, повышает ее живучесть и возможности при альтернативной (динамической) маршрутизации.

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

4. При обосновании пропускных способностей ЛС и УК СПД особая роль принадлежит коэффициенту использования. Обратная ему величина указывает во сколько раз пропускная способность должна превысить интенсивность трафика для обеспечения задержки не более заданного уровня.

ЗАКЛЮЧЕНИЕ

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

- методы и алгоритмы направленного поиска КМ (МНП-1, МНП-2), позволяющие строить графы КМ и удобные для использования при проектировании СПД;

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

- метод и алгоритм оптимизации системной надежности СПД, основанный на использовании разработанных алгоритмов маршрутизации;

- метод оптимизации технической надежности элементов системы при многих ограничивающих факторах и разнотипных резервирующих элементах {метод двойной оптимизации);

- метод граничной точки и алгоритм, позволяющий эффективно решать класс задач выпуклого программирования при линейных ограничениях на переменные;

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

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

133

1. Волкова В.Н., Денисов A.A. Основы теории систем и системного анализа. - Санкт-Петербург.: Изд-во СПбГТУ, 1997. - 510 с.

2. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989. - 367 с.

3. Воронков В.А. Системный анализ экономики связи. М.: Радио и Связь, 1993.-127 с.

4. Моисеев H.H. Математические задачи системного анализа. М.: Наука. - 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. Самойленко A.A., Давыдов В.В. и др. Вычислительные сети: адаптивность, помехоустойчивость. М.: Наука, 1981. - 227 с.

23. Дудник Б.Я., Овчаренко В.Ф. Надежность и живучесть систем связи. -М.: Радио и связь, 1984.

24. Артамонов Г.Т. Топология регулярных вычислительных сетей и средств. М.: Радио и связь, 1985. - 192 с.

25. Цвиркун А.Д. Основы синтеза структуры сложных систем. М.: Наука, 1982.-200 с.

26. Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей. //Автоматика. 1981. - №4 - с. 27-40.

27. Aгаян A.A. Исследование алгоритмов многокритериальной оптимизации топологии вычислительных сетей. //Препринт / научный совет по комплексной проблеме «Кибернетика» AH CCCT. М.: Наука, 1984. -56 с.

28. Цвиркун A.Д., Aкинфиев B.K., Филиппова B.A. Имитационное моделирование в задачах синтеза структуры сложных систем. М.: Наука, 1985.- 173 с.

29. Федотов E.B. Разработка и исследование алгоритмов синтеза топологической структуры сетей передачи данных ACMО. //Диссертация кандидата технических наук. М.: AH ИПУ, 1988.

30. Берсекас Д., Галлагер Р. Cистемы передачи данных. М.: Мир, 1989.

31. Prank Н., 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., Marmin E.G. Perturbation techniques for topological optimization of computer networks //4 th Data Commun. Symp. New York, 1978. - p. 4/16-4/23.

33. Емеличев B.A. и др. Лекции по теории графов. М.

34. Берж К. Теория графов и ее применение. М.: ИИЛ, 1962. - 319.

35. Кристофидес Н. Теория графов. Aлгоритмический подход. М.: Мир, 1978.-412.

36. Bишневецкий B^., Федотов E.B. Комбинаторный алгоритм синтеза топологической структуры сети пакетной коммутации. //12'" Bсесоюз-ный семинар по вычислительным сетям. М.: AH CCCT, 1986.

37. Немировский A.C., Юдин Д.Б. Cложность задач и эффективность методов оптимизации. М.: Наука, 1979. - 383 с.

38. Клейнрок Л. Bычислительные системы с очередями. М.: Мир, 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. Советов Б.Я., Яковлев CA. Моделирование систем. М.: Высшая школа, - 1985.

49. Шварц М. Сети ЭВМ. Анализ и проектирование. М.: Связь и радио, -1981.

50. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. -Киев.: Техника, 1986.

51. Максименков A.B., Селезнев М.Л. Основы проектирования информационно-вычислительных систем и сетей ЭВМ. М.: Радио и связь, -1991.

52. Демидович Б.П., Марон И.А. Основы вычислительной математики. -М.: Наука,- 1970.-664 с.

53. Вентцель Е.С. Теория вероятностей. М.: Наука, 1964. - 576 с.

54. Гмурман В.Е. Теория вероятностей и математическая статистика. -М.: Высшая школа, 1977. - 479 с.

55. Берзин Е.А., Смирнов Д.В. Два алгоритма определения множества Па-рето-оптимальных решений многокритериальной задачи линейного программмирования. //Программные продукты и системы. Тверь.: ЦПС,- 1997.-С. 28-33.

56. Берзин Е.А., Палюх Б.В. Оптимизация надежности АСУ методом нормированных функций. //СНТ-Синтез систем вычислительного эксперимента, 4.1. Апатиты, КНЦ РАН, 1995. - с. 112-121.

57. Карманов В.Г. Математическое программирование. М.: Наука, 1986. -285 с.

58. Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. М.: Сов. радио, 1974. - 303 с.

59. Муртаф Б. Современное линейное программирование. М.: Мир, 1984.-224 с.

60. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. - 318 с.

61. Сухарев А.Г., Тимохов A.B., Федоров В .В. Курс методов оптимизации. М.: Наука, 1986. - 325 с.

62. Корн Г., Корн Т. Справочник по математике для научных работников и инженерров. М.: Наука, 1968. - 720 с.