Моделирование и анализ распределенных информационно-вычислительных систем на основе аппарата стохастических сетей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Соколов, Александр Евгеньевич

• Соколов, Александр Евгеньевич
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Соколов, Александр Евгеньевич

Глава 1. Анализ математических методов и моделей распределенных систем обработки информации

1.1. Эволюция и тенденции развития технологии распределенной 10 обработки информации

1.2. Проблематика анализа распределенных систем обработки 15 информации

1.3. Методы анализа распределенных систем обработки 22 информации

1.4. Постановка задачи 26 Цель работы и задачи исследования 29 Выводы

Глава 2. Модели элементов распределенной системы обработки 33 информации

2.1. Модель канала передачи данных с возможными потерями 34 пакетов или столкновениями

2.2. Модель ЭВМ

2.3. Взаимодействие блокировками 50 Выводы

Глава 3. Стохастическая модель распределенной системы 54 обработки информации

3.1. Сеть массового обслуживания с переменными вероятностями 54 переходов

3.1.1. Замкнутая сеть с несколькими классами заявок

3.1.2. Показатели качества функционирования

3.2. Эквивалентное преобразование модели элемента 70 Выводы

Глава 4. Алгоритмизация процедур расчета характеристик объекта 81 моделирования

4.1. Алгоритм формирования математической модели

4.2. Алгоритм вычисления функций вероятности стационарного 86 состояния

4.3. Алгоритм вычисления нормализующей константы 89 Выводы

Глава 5. Структура и состав системы моделирования и анализа 99 распределенных систем обработки информации. Результаты практического использования

5.1. Структура программного обеспечения системы 99 моделирования

Введение диссертации (часть автореферата) на тему «Моделирование и анализ распределенных информационно-вычислительных систем на основе аппарата стохастических сетей»

АКТУАЛЬНОСТЬ ТЕМЫ

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

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

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

Тематика диссертационной работы соответствует одному из основных научных направлений Воронежского государственного технического университета «Вычислительные и информационно-телекоммуникационные системы для управления технологическими процессами».

ЦЕЛЬ РАБОТЫ

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

Исходя из данной цели в работе определены следующие задачи исследования:

• анализ содержания и специфики решения задачи анализа распределенных информационно-вычислительных систем;

• структурная декомпозиция распределенной информационно-вычислительной системы и разработка формализованного описания элементов объекта исследования;

• разработка алгоритмов расчета характеристик, учитывающих особенности модели распределенной обработки информации;

• алгоритмизация процесса построения модели, применительно к специфическим особенностям конкретных распределенных информационно-вычислительных систем, а также формирование процедур расчета их характеристик;

• разработка прикладного программного и сервисного обеспечения алгоритмов моделирования и анализа распределенных информационно-вычислительных систем.

МЕТОДЫ ИССЛЕДОВАНИЯ Методы исследования основаны на использовании теории неоднородных замкнутых сетей массового обслуживания, теории вероятностей, дискретной математики, теории графов, вычислительной математики, объектно-ориентированного программирования, компьютерных технологий.

НАУЧНАЯ НОВИЗНА Научная новизна результатов исследования. В работе получены следующие результаты, характеризующиеся научной новизной:

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

• визуальная среда содержательной компоненты модели объекта исследования, позволяющая в интерактивном режиме создавать и использовать библиотеки типовых элементов модели;

• алгоритм формирования структуры модели объекта исследования, реализующей визуальный прототип;

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ В работе предложен комплекс моделей, алгоритмов и программных средств, позволяющий произвести анализ качества функционирования комплекса приложений в распределенной вычислительной сети.

Использование данного комплекса на этапе проектирования распределенной информационно-вычислительной системы позволяет найти потенциальные «узкие места» в вычислительной сети, определить запас производительности, оптимально использовать ресурсы вычислительной сети. РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ Основные теоретические и практические результаты работы реализованы в виде специального программного обеспечения анализа характеристик функционирования распределенных информационно-вычислительных систем. Результаты работы использованы в ЗАО «Интеркон» при проектировании сети узла поставщика услуг Интернет.

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

АПРОБАЦИЯ РАБОТЫ Основные результаты докладывались и обсуждались на IV Международной электронной научной конференции «Современные проблемы информатизации» (Воронеж, 1999), Всероссийской конференции

Интеллектуальные информационные системы» (Воронеж, 1999), V Международной электронной научной конференции «Современные проблемы информатизации в непромышленной сфере и экономике» (Воронеж, 2000), Международной научной конференции «Математические методы в технике и технологиях» (Санкт-Петербург, 2000), а также на научных семинарах кафедры автоматизированных и вычислительных систем.

ПУБЛИКАЦИИ По материалам диссертации опубликовано 8 научных работ.

СТРУКТУРА И ОБЪЕМ РАБОТЫ Диссертация состоит из введения, пяти глав, заключения, списка литературы из 106 наименований и приложения на 21 странице. Основная часть работы изложена на 127 страницах, содержит 31 рисунок и 2 таблицы.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Соколов, Александр Евгеньевич

Выводы

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

2. Активное использование средств визуализации стохастической модели, использование технологии «Перетащить-и-положить» в интерфейсе программы позволяет значительно повысить эффективность труда при описании модели.

3. Возможность создания и использования библиотеки моделей типовых элементов распределенных систем обработки информации позволяет сократить время на анализ характеристик.

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

5. Введение в программу функции сохранения матриц вероятностей перехода и результатов расчета в формате файла CSV (таблица с разделителями «точка с запятой») позволяет осуществлять импорт и

Заключение

Проведенные в рамках диссертации теоретические исследования позволили получить следующие результаты, имеющие прикладное и научное значение:

1. Для моделирования процесса функционирования распределенной информационно-вычислительной системы проведен выбор и обоснование использования средств аналитического моделирования методами аппарата теории стохастических сетей.

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

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

4. Разработаны рекуррентные алгоритмы расчета характеристик модели, отличающиеся учетом зависимости вероятностей перехода фаз обслуживания заявки от состояния модели объекта.

5. На основании предложенной модели и алгоритмов анализа разработано специальное программное обеспечение расчета характеристик функционирования.

6. Разработана визуальная среда содержательной компоненты

Список литературы диссертационного исследования кандидат технических наук Соколов, Александр Евгеньевич, 2001 год

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

2. ATM: Архитектура и реализация / Дж Мартин., К. Чапмен, Д. Либен и др.: М.: Лори, 1999.-322 с.

3. ISDN. Просто и доступно /Э. Титтель, С. Джеймс, Д. Пискителло, Л. Пфайфер М.: Лори, 1999. 254 с.

4. Авен О. И. Оценка качества и оптимизации вычислительных систем. -М.: Наука, 1982.-464 с.

5. Аншина М.И. Биография бизнес-объекта // Мир ПК. -1998. № 11 С. 31-39.

6. Аншина М.И. Симфония CORBA // Открытые системы. 1998. № 3. С. 24-28.

7. Ахо А. Построение и анализ вычислительных алгоритмов. Пер с. англ.; Под ред. Ю.В. Матиясевича.М.: Мир, 1979. -536 с.

8. Башарин Г.П. Массовое обслуживание в телефонии / Г.П. Башарин, А.Д. Харкевич, М.А. Шнепс М.: Наука, 1968. 464 с.

9. Башилов Г. Р2Р или путь в никуда // Компьютерра. 2000. № 40. С. 12. Ю.Безопасность глобальных сетевых технологий/ В.М. Зима, А.А.

10. Молдовян, Н.А. Молдовян М.: BHV, 2001. 572 с.

11. П.Блэк У. Интернет: протоколы безопасности. СПб.: Питер-Пресс, 1998. -482 с.

12. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. М.: Энергоатомиздат, 1984. -168 с.

13. Боровиков А. А Вероятностные процессы в теориии массового обслуживания. М.: Наука, 1972. -288 с.

14. Н.Браун С. Виртуальные частные сети: М.: Лори, 2001. 376 с.

15. Брентон К. Разработка и диагностика многопротокольных сетей: М.: Лори, 1999.-680 с.

16. Бусленко Н.П. Математическое моделирование производственных процессов на цифровых вычислительных машинах. М.: Наука, 1978. -210 с.

17. Бутрименко А.В. Разработка и эксплуатация сетей ЭВМ. М.: Финансы и статистика, 1981. 256 с.

18. Вайк A. eTime Capital приобретает Dynamic Transactions // Computer Word-Россия. 1999. № 23. С. 1.

19. Вайк A. Lotus выпускает Discovery Server // Computer Word-Россия. -1999. № 10. С. 5.

20. Вальтер Г. Технологии ADSL и DSL: М.: Лори, 2000. 512 с.

21. Васильев В.И. , Гориков Л.Ф., Сидоренко В.А. Методы и средства организации каналов передачи данных. М.: Радио и связь, 1982. -150 с.

22. Вентцель А.Д. Курс теории случайных процессов. М.: Наука, 1975. -452 с.

23. Вычислительные сети и сетевые протоколы / Д. Девис, Д. Барбер, У. Прайс, С Соломонидес. М.:Мир, 1982. 563 с.

24. Вычислительные сети: адаптивность, помехоустойчивость, надежность / С.И. Самойленко, А.А. Давыдов, В.В. Золотарев, Е.И. Третьякова. М.: Наука, 1981. -277 с.

25. Галкин Г. Тенденци: Р2Р наносит ответный удар // Сетевой журнал Data Communications. 2000. № 10. С. 8

26. Гнеденко Б.В. Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1969. 180 с.

27. Гук М. Аппаратные средства локальных сетей. СПб.: Питер-Пресс, 2001.-740 с.

28. ГукМ. Сети NetWare 3.12-4.1: книга ответов. СПб.: Питер-Пресс, 1997. 662 с.

29. Гук М. Локальные сети Novell. СПб.: Питер-Пресс, 1996. 584 с.

30. Джейсоул Н. Очереди с приоритетами. М.:Мир, 1973. 460 с.

31. Дубова Н. Н., Кутукова Е.М. Unicenter TNG управление распределенной корпорацией // Открытые системы. 1998. № 2 - с. 54-59.

32. Жожикашвилли В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988.-192 с.

33. Зб.Зельтцер Дж. В поисках "тонкого клиента"//Сети и системы связи. -1999. №6.-С. 25-27

34. Иглхарт Д.Л., Шедлер Д.С. Регенеративное моделирование сетей массового обслуживания. -М.: Радио и связь, 1984. 135 с.

35. Казанский Д.И. Системы ERP: основные задачи и область применения // Сети и системы связи. 1998. № 2. С. 30-35.

36. Катышев C.B. Об одной концепции управления распределенными ресурсами // Открытые системы. 1999. № 6. - с. 36-41.

37. Кёнинг Д., Штоян Д. Методы теории массового обслуживания: Пер с нем. / Под ред. Г.П. Климова. М.: Радио и связь, 1981. -128 с.

38. Клейнрок JT. Вычислительные системы с очередями. М.: Мир, 1979.600 с.

39. Клейнрок Л. Коммуникационные сети: Стохастические потоки и задержки сообщений. М.: Наука, 1970.- 255 с.

40. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.-432 с.

41. Климов Г.П. Стохастические системы обслуживания. -М.: Наука, 1966. 172 с.

42. Коваленко И.Н. Некоторые аналитические методы в теории массового обслуживания. М.: Энергия, 1964 236 с.

43. Колосков М. Как поставить диагноз своей сети. Самоучитель по Теории очередей для сетевых администраторов // Сети и Системы Связи. -2000. №8. С. 45-53.

44. Коновалов Б.А, Шамаев А.С., Катышев С.В. Построение систем высокой готовности // BYTE-Россия. 1999. № 2 (6). - С. 28-36

45. Кофман А., Крюон Р. Массовое обслуживание: теория и приложения. М.: Мир, 1965.-470 с.

46. Кочегаров. В.А., Фролов Г.А. Проектирование систем распределения информации. Марковские и немарковские модели. М.: Радио и связь, 1991.216 с.

47. Кульгин М. И. Технологии корпоративных сетей. Энциклопедия . СПб.: Питер-Пресс, 2000,- 704 с.

48. Кульгин М. Технологии корпоративных сетей. СПб.: Питер-Пресс, 2000. 668 с.

49. Кутукова Е.М. Системы управления распределенными информационными ресурсами// Открытые системы. 1998. № 3. - С. 36-41.

50. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи. М.: Радио и связь, 1983. 216 с.

51. М.С. Колосков. Время доставки пакета и пропускная способность локальной вычислительной сети. Автоматика и вычислительная техника. 1990 г. Академия наук Латвийской ССР.

52. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М.: Радио и связь, 1986. 408 с.

53. Моделирование систем сбора и обработки данных/В.П. Евдокимов,

54. B.И.Мановицкий, Ю.А. Семенишин и др.-М.:Наука, 1983. 128 с.

55. Муси П. Пользователи требуют 10 Ебит/с Ethernet // LAN. 2001. №8.1. C. 35.

56. Нейман В.И. Теоретические основы единой автоматизированной сети связи. М.: Наука, 1984. 221 с.

57. Башарин Г.П. , Бордукова В.Т. Некоторые точные и эвристические результаты для многолинейных СМО с ограниченным накопителем // Теория телетрафика и информационные сети. М., Наука, 1977. С. 6-15.

58. Толмачев А.Л. Некоторые характеристики замкнутых экспоненциальных сетей. // Теория телетрафика и информационные сети. М., Наука, 1977. С. 3-6.

59. В.В. Калашников, Б.В.Немчинов, В.М.Симонов. Нить Ариадны в лабиринте моделирования. М.: Наука, 1993. -192 с.62.0лифер В. , Олифер Н. Компьютерные сети. Принципы, технологии, протоколы. СПб.: Питер-Пресс, 2001. 320 с.

60. Олифер В., Олифер Н. Сетевые операционные системы: СПб.: Питер-Пресс, 2001. 810 с.

61. Основы теории вычислительных систем/С.А. Майоров, Г.И. Новиков, Т.И. Алиев, Э.И. Махарев, Б.Д. Тимченко. -М.:Высшая школа, 1978. 408 с.

62. Башарин Г.П., Громов А.И., Наумов В.А. Оценка производительности ЦВМ со страничной организацией двухуровневой памяти. // Теория телетрафика и информационные сети. М., "Наука", 1977. С. 25-29.

63. Понамарев В.А. СОМ и ActiveX в Delphi. СПб.: BHV. 2000. 320 с.

64. Проект SETI@home // e-Media.- 1999. № 7. С. 4.

65. Розенберг В.Я., Прохоров А.И. Что такое теория массового обслуживания. М.: Сов. радио, 1965. - 180 с.

66. Саати Т.Л. Элементы теории массового обслуживания с применениями. М.: Сов. радио, 1965. - 262 с.

67. Салливан Т., Визард. Е. Архитектуры Р2Р для Web-служб // Computer Word-Россия. 2001. № 10. С. 5.

68. Секреты создания интрасетей: Micro Modeling Associates, Inc. СПб.: Питер-Пресс, 1998. 476 с.

69. Сетевые средства Windows NT Server 4.0: Пер с англ. -СПб.: BHV-Санкт-Петербург, 1998,- 880 с.

70. Сети предприятий на основе Windows NT для профессионалов/ М. Стерн, Г. Монти, В. Бэчманн. СПб.: Питер-Пресс, 1999. 796 с.

71. Скотт X. Анализ и диагностика компьютерных сетей. Просто и доступно: М.: Лори, 2001. 594 с.

72. Скринсейверы Popular Power работают на человечество // e-Media.2000. № 8. С. 3.

73. Смолко А.Е. Алгоритм реконфигурирования структуры высоконадежной децентрализованной информационной системы управления//Современные проблемы информатизации: Тез. докл. IV Междунар. Электронной науч. конф. Воронеж, 1999.-С 40.

74. Смолко А.Е., Бурковский В.Л. Алгоритмизация задачи высоконадежного функционирования распределенных информационных систем управления //Современные проблемы информатизации: Тез. докл. IV Междунар. электронной науч. конф. Воронеж, 1999. С. 170.

75. Смолко А.Е., В. Л. Бурковский В. Л. Алгоритм формирования отказоустойчивой структуры распределенной системы управления // Интеллектуальные информационные системы: Тез. докл. Всеросс. науч. конф. Воронеж, 1999. С. 225.

76. Соколов А.Е., Бурковский B.JI. Проблемы алгоритмизации формирования отказоустойчивой структур распределенной системы управления //Информационные технологии моделирования и управления: Межвуз . сб. науч. тр. Воронеж, 1999.- С.48-54.

77. Соколов А.Е., Бурковский А.В. Исследование производительности канала связи с произвольной дисциплиной доступа к среде // Электротехнические комплексы и системы управления: Сб. науч. тр. Воронеж, ВГТУ, 2001. С. 125-128.

78. Соколов А.Е., Бурковский В.Л. Стохастическая модель системы хранения данных// Электротехнические комплексы и системы управления: Сб. науч. тр. Воронеж, ВГТУ, 2001. С. 86-89.

79. Суздалев А.В. Сети передачи информации АСУ. М.: Радио и связь, 1983 153 с.

80. Такач Л. Комбинаторные методы в теории случайных процессов. М.: Мир, 1968.-276 с.

81. Терес Чан. Системное программирование на С++ для UNIX: Пер. с англ. К.: BHVJ997 592 с.

82. Тител. Э., Хадсон К., Стюарт Дж. М. NT Workstation 4. Сертификационный экзамен экстерном (экзамен 70-073). СПб.: Питер Ком, 1999.-480 с.

83. Торстен Б. Технология DCOM в Windows NT // Computerworld. -1996. №42. С. 12-13.

84. Фейт С. TCP/IP:-М.: Лори, 2000. 322 с.

85. Форд Л., Фалкерсон Д. Потоки в сетях: -М.: Мир., 1966. 276 с.

86. Хинчин А.Я. Работы по математической теории массового обслуживания.-М.: Физматгиз, 1963. -390 с.

87. Хочмут Ф. 10 Gigabit Ethernet набирает силу // Computerworld-Россия. 2001. №7. С. 1.

88. Цимбал Ю. Д. Технология CORBA для профессионалов. СПб. Изд-во Питер, 2000. -624 с.

89. Ченцов В.М. Системы распределения информации. М.: Связь, 1980. -142 с.

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

91. Шварц М. Сети связи: протоколы моделирование и анализ: В 2 ч. М.: Наука. Гл. ред. физ.-мат. лит., 1992. Ч. I 336 с.

92. Шварц М. Сети связи: протоколы моделирование и анализ: В 2 ч. М.: Наука. Гл. ред. физ.-мат. лит., 1992. Ч. II 272 с.

93. Шнепс М.А. Численные методы теории телетрафика. М.: Связь, 1974. -288 с.

94. Штоян Д. Качественные свойства и оценки стохастических моделей. М.: Мир, 1971. 162 с.

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

96. Якубайтис Э.А. Информационно-вычислительные сети. М.: Финансы и статистика, 1984. 232 с.

97. Baskett F., Chandy К. М., Muntz R. R., Palacioc F. G. Open, closed and mixed networks of queues with different. J. Assoc. Comput. Mach., 1975, 22, №2

98. Buzen J. P. Computation algorithms of closed quequeing networks with exponential servers. Communications of the ACM, 1973, 16, № 9

99. Diffusing update algorithms for message routing in computer networks and internetworks. Invenstion Discosure P-3089, SRI Unt., Mento Park, CA, Sept, 1991.

100. Garcia J.J. Loop-Free Routing Using Diffusing Computatons. IEEE/ASM Transactions on Network. V 1. N 1. Feb, 1993.

101. Gordon W. J., Newell G. F. Closed queueing systems width exponential servers. Oper. Res. 1967, 15, № 2

102. Hayes-Roth F., Jacobstein N. The State of Enowledge-Based Systems. Communications of the AI, March, 1994, v. 37, n. 3, pp. 27-39.

103. Simpson A. Inversion of a class of matrices occuriny in control-system theory by an m-step procedure allied to Gaussian elimination. Electron. Lett., 1970, 6, № 16

104. Whitaker B. A. Analysys and optimum design of a multiserver, multiqueue system with finite waiting space in each queue. BSTY, 1975, 54, № 3142