Содержание к диссертации
Введение
Глава 1 Обзор и сравнительный анализ методов автоматизированного проектирования ВС 11
1.1 Задача проектирования ВС 11
1.2 Выбор средства принятия проектных решений 13
1.3 Модели вычислительных сетей 15
1.4 Функции режима моделирования при автоматизированном проектировании ВС 18
1.5 Обзор существующих средств имитационного моделирования ВС . 19
1.6 Проект NS2/VINT 29
1.6.1 Архитектура NS2 30
1.6.2 Возможности NS2 32
1.6.3 Протоколы, реализованные на уровне ядра NS2 33
1.6.4 Возможность построения САПР на основе NS2 33
1.7 Представление знаний и моделирование рассуждений 35
1.7.1 Представление знаний 35
1.7.2 Формальные модели представления знаний 37
1.7.3 Моделирование рассуждений 37
1.8 Деревья решений ., 38
1.8.1 Терминология .; 38
1.8.2 Преимущества использования деревьев решений 40
1.9 Нечёткие нейронные сети 41
1.10 Сети Петри 42
1.11 Нечёткие сети Петри 45
1.12 Байесовские сети доверия 46
1.12.1 Виды байесовских сетей доверия 47
1.12.2 Скрытая Модель Маркова (СММ) 48
1.12.3 Области применения байесовских сетей доверия 48
1.12.4 Краткий обзор программ для работы с байесовскими сетями доверия 51
1.13 Генетические алгоритмы 55
1.13.1 Схема генетического алгоритма 55
1.13.2 Сходимость ГА 57
1.14 Основные трудности при автоматизированном проектировании ВС . 58
1.15 Источники трафика при проектировании ВС 59
1.15.1 Измерения ВС 59
1.15.2 Функциональные диаграммы 60
1.16 Нечёткий вероятностный характер динамики вычислительной сети . 61
1.17 Постановка задачи 62
1.18 Выводы 63
Глава 2 Формализированные описания, модели, проектные решения автоматизированного проектирования ВС 66
2.1 Форма описания производственных процессов 67
2.1.1 Функциональные определения IDEF 68
2.1.2 Стандартные DFD - диаграммы 73
2.1.3 Обоснование выбора DFD - диаграмм 75
2.1.4 Дополненные DFD - диаграммы 78
2.2 Модель трафика 79
2.3 Байесовские сети как средство моделирования рассуждений с целью оптимизации ВС 82
2.3.1 Механизм работы байесовских сетей доверия 82
2.3.2 Причинно - следственные связи для задачи определение коммутационного оборудования 87
2.3.3 Байесовская сеть для определения состава коммутационного оборудования 88
2.3.4 Оценка размера БСД для определения состава коммутационного оборудования 90
2.3.5 Причинно - следственные связи для задачи определения пропускной способности каналов ВС 91
2.3.6 Байесовская сеть для определения пропускной способности каналов сети 92
2.3.7 Оценка размера байесовской сети для определения пропускной способности каналов сети 93
4 Формирование значений матриц условных вероятностей 94
5 Моделирование маршрутизации 95
6 Матрица интенсивностей взаимодействий 96
7 Модели сети 96
2.7.1 Распараллеливание на основе асинхронного параллелизма . 97
2.7.2 Модель сети для имитационного (динамического) моделирования 98
2.7.3 Модель сети для статического моделирования 106
8 Сравнение моделей ВС с существующими аналогами 109
2.8.1 Статическая модель ВС 109
2.8.2 Динамическая модель ВС 110
9 Адаптация генетического алгоритма для задач проектирования ВС .111
2.9.1 Генетический алгоритм для оптимизации подключения рабочих станций 111
2.9.2 Генетический алгоритм для определения размещения комму тационного оборудования 112
2.10 Выводы : 114
Глава 3 Структурно - функциональное решение САПР ВС 115
3.1 Структура САПР ВС 115
3.1.1 DFD - диаграммер 116
3.1.2 Модуль построения ВС 117
3.1.3 Визуальный редактор вычислительной сети 118
3.1.4 Модуль статического моделирования вычислительной сети 118
3.1.5 Модуль динамического моделирования вычислительной сети 118
3.1.6 Модуль байесовской оптимизации 119
3.1.7 Модуль генетической оптимизации 119
3.2 Реализация представления трафика, операции над нечётким трафиком, форматы входных файлов САПР ВС 122
3.3 Реализация байесовских сетей доверия 124
3.3.1 Реализация БСД для определения состава коммутационного оборудования 125
3.3.2 Реализация БСД для определения пропускной способности каналов сети 126
3.4 Реализация механизма обновления вероятностей в узлах БСД 127
3.5 Реализация имитационного моделирования 128
3.5.1 Классы, использованные в имитационной модели 128
3.5.2 Алгоритмы динамического моделирования 139
3.6 Реализация статического моделирования 143
3.6.1 Классы, использованные в статической модели 143
3.6.2 Алгоритм статического моделирования 144
3.7 Реализация генетических алгоритмов 145
3.7.1 Оптимизация подключения рабочих станций 148
3.7.2 Оптимизация размещения коммутационного оборудования 149
3.8 Выводы 149
Глава 4 Вычислительные эксперименты 151
4.1 Проверка адекватности реализованных в САПР ВС моделей 151
4.1.1 Описание ожидаемого и полученного результата 151
4.1.2 Описание полученного при помощи САПР ВС результата 152
4.2 Гипотетические сети и тестовые примеры 155
4.2.1 Тестовая сеть с четырьмя рабочими станциями и сервером 155
4.3 Эксперименты с реальной сетью 161
4.3.1 Структура и потоки данных в ВС ФНПЦ ОАО НПО Марс 161
4.4 Условия вычислительных экспериментов 163
4.5 Результаты вычислительных экспериментов для исходного варианта
ВС 167
4.6 Сводные таблицы для оптимизированного варианта ВС 168
4.7 Сводные таблицы для варианта ВС с утроенным трафиком 171
4.8 Сравнение эффективности генетического алгоритма и байесовских сетей доверия 174
Заключение
- Функции режима моделирования при автоматизированном проектировании ВС
- Стандартные DFD - диаграммы
- Визуальный редактор вычислительной сети
- Описание полученного при помощи САПР ВС результата
Введение к работе
Создание крупных высокоэффективных систем обработки данных связано с объединением средств вычислительной техники, обслуживающей подразделения предприятий и организаций, с помощью системы передачи данных в единую вычислительную сеть. В настоящее время при проектировании вычислительных сетей активно используются системы автоматизированного проектирования вычислительных сетей (САПР ВС). Так как задача проектирования вычислительной сети обладает большим объёмом и высокой степенью сложности, САПР ВС должна обладать элементами интеллектуальности. Существующие САПР ВС позволяют производить различные операции со структурой вычислительной сети (ВС), оптимизировать различные параметры и проводить моделирование заданных ВС. Но им присущи следующие недостатки: размер передаваемых пользователями данных должен иметь чёткую числовую размерность, построение структуры ВС производится пользователем - экспертом, при этом отсутствует возможность автоматизировать процесс построения структуры ВС, недостаточно развиты механизмы моделирования динамики трафика ВС.
Актуальность выбранной темы определяется тем, что при построении локальных и корпоративных вычислительных сетей необходимо учитывать автоматизируемые производственные процессы с целью минимизации затрат на построение сети и предоставления возможностей для развития ВС без её кардинальной перестройки. В процессе модернизации ВС возникает задача определения проблемных мест существующей ВС. Для определения каналов, обладающих недостаточной пропускной способностью, необходимо использовать диаграммы производственных процессов, автоматизируемых при помощи ВС, с целью получения значения величины трафика, адекватной реальной, и определить поведение полученного значения при развитии всей ВС или отдельных её подсетей.
Наряду с генетическими методами оптимизации в разработанной САПР ВС применяется аппарат байесовских сетей доверия. Данное решение позволит получать результаты оптимизации, обоснованные знаниями эксперта о структуре решаемой задачи, представленными в виде графа сети доверия и матрицами условных вероятностей узлов сети доверия. В разработанной САПР ВС сети доверия применяются для моделирования рассуждений проектировщика с целью определения состава коммуникационного оборудования и определения пропускной способности каналов ВС. Теоретическое описание механизма работы байесовских сетей доверия приведено в разделе 2.3.1, структура используемых сетей доверия приведена в разделах 2.3.3, 2.3.6, программная реализация сетей доверия приведена в разделе 3.3.
Научная новизна данной работы состоит в построении структур байесовских сетей доверия для оптимизации параметров вычислительной сети и применении аппарата байесовских сетей доверия для моделирования рассуждений проектировщика при оптимизации вычислительных сетей.
Преимуществами использования сетей доверия являются: обоснованность результатов моделирования рассуждений знаниями эксперта, представленными как структурой графа сети доверия, так и в форме матриц условных вероятностей в узлах сети доверия; скорость получения результата. Преимущества применения аппарата сетей доверия по сравнению с генетическими алгоритмами и ручным перебором вариантов представлены в 4.8; результат моделирования рассуждений проектировщика охватывает множество возможных решений и показывает уровень оптимальности каждого решения.
Основными недостатками использования сетей доверия являются:
Необходимость построения сети доверия для каждого варианта ВС
Сложность и длительность процесса заполнения таблиц условных вероятностей
Функции режима моделирования при автоматизированном проектировании ВС
Используя моделирование при проектировании или перестройке вычислительной системы, мы можем сделать следующее: оценить пропускную способность сети и ее компонентов, определить узкие места в структуре вычислительной системы; сравнить различные варианты организации вычислительной системы; осуществить перспективный прогноз развития вычислительной системы; предсказать будущие требования по пропускной способности сети, используя данные прогноза; оценить требуемое количество и производительность серверов в сети; сравнить различные варианты модернизации вычислительной системы; оценить влияние на вычислительную систему модернизации ПО, мощности рабочих станций или серверов, изменения сетевых протоколов.
Исследование параметров вычислительной системы при различных характеристиках отдельных компонентов позволяет выбрать сетевое и вычислительное оборудование с учетом производительности, качества обслуживания, надежности и стоимости. Поскольку стоимость одного порта активного сетевого оборудования в зависимости от производителя оборудования, используемой технологии, надежности, управляемости может меняться в широких пределах, моделирование позволяет минимизировать стоимость оборудования, предназначенного для использования в вычислительной сети.
Процесс проектирования и моделирование ВС является сложным и ресурсоёмким процессом и производится с использованием специальных программных продуктов. Существуют специальные, ориентированные на моделирование вычислительных сетей программные системы, в которых процесс создания модели упрощен ([34], [40], [30]). Такие программные системы позволяют генерировать модель сети на основе исходных данных о её топологии и используемых протоколах, об ин-тенсивностях потоков запросов между компьютерами сети, протяженности линий связи, о типах используемого оборудования и приложений. Программные системы моделирования могут быть узко специализированными и достаточно универсальными, позволяющими имитировать сети самых различных типов. Качество результатов моделирования в значительной степени зависит от точности исходных данных о сети, переданных в систему имитационного моделирования. Программные системы моделирования сетей - инструмент, который может пригодиться любому администратору корпоративной сети, особенно при проектировании новой сети или внесении кардинальных изменений в уже существующую сеть.
Продукты данной категории позволяют проверить последствия внедрения тех или иных решений еще до оплаты приобретаемого оборудования. Применение САПР ВС позволяет сократить денежные издержки при построении или модернизации вычислительной сети. В качестве основных недостатков существующих систем САПР следует отметить следующие: отсутствие возможности учёта особенностей автоматизируемых производственных процессов, необходимость задания информации о трафике в чёткой числовой форме.
Программы имитационного моделирования сети используют в своей работе информацию о пространственном расположении сети, числе узлов, конфигурации связей, скоростях передачи данных, используемых протоколах и типах оборудования, а также о выполняемых в сети приложениях [34]. Обычно имитационная модель строится не с нуля. Существуют готовые имитационные модели основных элементов сетей: наиболее распространенных типов маршрутизаторов, каналов связи, методов доступа, протоколов и т.п. Эти модели отдельных элементов сети создаются на основании различных данных: результатов тестовых испытаний реальных устройств, анализа принципов их работы, аналитических соотношений. В результате создается библиотека типовых элементов сети, которые можно настраивать с помощью заранее предусмотренных в моделях параметров. Системы имитационного моделирования обычно включают также набор средств для подготовки исходных данных об исследуемой сети - предварительной обработки данных о топологии сети и измеренном трафике. Эти средства могут быть полезны, если моделируемая сеть представляет собой вариант существующей сети и имеется возможность провести в ней измерения трафика и других параметров, нужных для моделирования. Кроме того, система снабжается средствами для статистической обработки полученных результатов моделирования.
В таблице 1.2 приведены характеристики нескольких популярных систем имитационного моделирования различного класса - от простых программ, предназначенных для установки на персональном компьютере, до мощных систем, включающих библиотеки большинства имеющихся на рынке коммуникационных устройств и позволяющих в значительной степени автоматизировать исследование изучаемой сети ([30]).
Стандартные DFD - диаграммы
Каждая сущность имеет своё имя и атрибуты. Атрибуты представляют собой характерные свойства и признаки объектов реального мира, относящихся к определенной сущности. Класс атрибутов представляет собой набор пар, состоящих из имени атрибута и его значения для определенной сущности. Атрибуты, по которым можно однозначно отличить одну сущность от другой называются ключевыми атрибутами. Каждая сущность может характеризоваться несколькими ключевыми атрибутами. Класс взаимосвязей в IDEF1 представляет собой совокупность взаимосвязей между сущностями. Взаимосвязь между двумя отдельными сущностями считается существующей в том случае, класс атрибутов одной сущности содержит ключевые атрибуты другой сущности. Каждый из вышеописанных классов имеет свое условное графическое отображение, согласно методологии IDEF1.
Концепции моделирования IDEF1
При построении информационной модели проектировщик всегда оперирует с двумя основными глобальными областями, каждой из которой соответствует множество характерных объектов. Первой из этих областей является реальный мир, или же совокупность физических и интеллектуальных объектов, таких, как люди, места, вещи, идеи и т.д., а также все свойства этих объектов и зависимости между ними. Второй же является информационная область. Она включает в себя существующие информационные отображения объектов первой области и их свойств. Информационное отображение, по существу, не является объектом реального мира, однако изменение его, как правило, является следствием некоторого изменения соответствующего ему объекта реального мира. Методология IDEF1 разработана как инструмент для исследования статического соответствия вышеуказанных областей и установления строгих правил и механизмов изменения объектов информационной области при изменении соответствующих им объектов реального мира.
Основные преимущества IDEFl Методология IDEFl позволяет на основе простых графических изображений моделировать информационные взаимосвязи и различия между: реальными объектами; физическими и абстрактными зависимостями, существующими среди реальных объектов; информацией, относящейся к реальным объектам; структурой данных, используемой для приобретения, накопления, применения и управления информацией.
Одним из основных преимуществ методологии IDEF1 является обеспечение последовательного и строго структурированного процесса анализа информационных потоков в рамках деятельности предприятия. Другим отличительным свойством IDEF1 является широко развитая модульность, позволяющая эффективно выявлять и корректировать неполноту и неточности существующей структуры информации, на всем протяжении этапа моделирования.
Так как в рамках данной работы учитываются только информационные потоки, сопровождающие производственные процессы автоматизируемого предприятия, то остальные стандарты семейства IDEF рассматривать не имеет смысла.
В разработанной САПР ВС для описания производственных процессов используются дополненные диаграммы потоков данных.
Стандартные DFD - диаграммы
Диаграммы потоков данных (Data Flow Diagram) представляют собой один из способов описания производственных процессов предприятия. Они отражают взаимодействие внешних по отношению к системе сущностей, хранилищ данных между собой при помощи потоков данных. Потоки могут быть управляющими (поток инструкций) или информационными (содержимое баз данных, рабочие документы, запросы и пр.).
Диаграммы потоков данных (DFD - Data Flow Diagram) строятся из элементов, представленных в таблице 2.1. 1.451.0
Визуальный редактор вычислительной сети
Мастер перехода позволяет получить первоначальный проект вычислительной сети на основании информации, заложенной в расширенных DFD - диаграммах и субъективного мнения эксперта - пользователя САПР. Процесс перехода является многоступенчатым. Далее последовательно описаны все шаги мастера.
1. Определение подсетей и размещение рабочих станций по подсетям. На данном шаге происходит определение количества подсетей и распределение рабочих станций пользователей, заданных в DFD - диаграмме по определённым подсетям.
2. Определение серверов данных и размещение на них баз данных. На данном шаге определяется количество серверов баз данных и происходит распределение по ним баз данных, заданных в DFD - диаграммах.
3. Распределение серверов данных по подсетям. На данном шаге происходит распределение серверов данных, определённых на предыдущем шаге, по подсетям, определённым на шаге 1.
4. Определение первоначального состава коммутационного оборудования, на данном шаге происходит определение первоначального состава коммутационного оборудования вычислительной сети. Оптимизация состава коммуникационного оборудования описана в разделе 3.3.1
5. Определение архитектуры вычислительной сети. На данном шаге происходит выбор между двумя архитектурами: "Общая шина"и "Звезда".
Основным преимуществом такого решения является автоматизация создания пилотного проекта ВС, основными недостатками являются большая зависимость от субъективного мнения эксперта и отсутствие оптимизации параметров создаваемого проекта ВС. Дальнейшая обработка пилотного проекта вычислительной сети происходит в модуле редактора вычислительной сети.
Данный модуль предназначен для визуального редактирования структуры ВС и параметров отдельных её элементов. Для рабочих станций такими параметрами являются уникальное имя и пространственное положение. Для узлов сети набор параметров следующий: уникальное имя, пространственное положение, тип устройства (хаб, свитч, роутер), количество портов. Для компьютеров редактируются уникальное имя, пространственное расположение, задачи пользователей (в случае рабочей станции) или хранимые базы данных (в случае сервера данных). Тип компьютера (рабочая станция или сервер) не редактируется. Также данный модуль может производить оценку стоимость коммуникационного оборудования на базе задаваемых пользователем цен на коммуникационное оборудование.
Модуль предназначен для нахождения пикового значения трафика. Пиковым значением трафика считается значение, получаемое при одновременном запуске всех выполняемых пользователями задач. Именно это значение используется при оптимизации генетическими алгоритмами подключения рабочих станций.
Модуль предназначен для определения динамики трафика на каналах сети. Модуль имитирует работу сети, исходя из данных о её структуре, расписании работ пользователей и выполняемых ими задачах. Имитация работы ВС происходит в режиме, максимально близком к режиму реального времени. Модуль не предназначен для нахождения пиковых нагрузок. Результатом работы модуля являются графики значений трафика на интересующих пользователя каналах сети. Реализация модели выполнена с использованием библиотеки объектно - ориентированного программирования Gala, описанной в [23].
Данный модуль предназначен для работы с байесовскими сетями доверия. Сети доверия, обрабатываемые данным модулем позволяют оптимизировать следующие параметры вычислительной сети:
Состав коммутационного оборудования. В результате работы модуля для каждого узла сети определяются вероятности нахождения в данном узле каждого типа коммуникационного оборудования, пропускная способность узла ВС и приоритетность его оптимизации.
Пропускная способность каналов. В результате работы для каждого канала сети определяется вероятность каждой градации пропускной способности.
Описание полученного при помощи САПР ВС результата
Для определения эффективности оптимизации состава коммутационного оборудования оценим время, необходимое для той же оптимизации при помощи генетического алгоритма. Для успешного решения задачи генетической оптимизации начальная популяция должна обладать разнообразием, достаточным для того чтобы в ней были представлены все возможные варианты каждого гена. Подобное соображение диктуется тем, что изменяющий гены оператор мутации выполняется довольно редко, в силу чего некоторые области множества возможных решений могут остаться нерассмотренными. В качестве примера рассмотрим ВС, состоящую из 21 узла, к каждому из которых подключено 4 рабочих станции. Все рабочие станции взаимодействуют с сервером данных, подключенным к одному из узлов. Топологическая схема сети - звезда, в центре которой находится узел, к которому подключён сервер данных. Из заданных условий следует, что начальная популяция должна состоять из 233 или 9621 хромосомы. Предположив количество поколений эволюции равным 100, получаем, что в процессе работы генетического алгоритма будет рассмотрено 962100 хромосом без учёта повторений.
В генетическом алгоритме оптимизации состава коммутационного оборудования функцией оптимиалыюсти является значение максимального трафика на каналах ВС. Следовательно, для того, чтобы определить значение функции оптимальности для конкретной хромосомы, необходимо провести статическое моделирование варианта ВС, кодируемого хромосомой. Статическое моделирование ВС занимает 14 секунд (все временные характеристики снимались на следующем компьютере: Pentium4 НТ ЗГгц, 512 Мб ОЗУ, Windows ХР Pro SP1, HyperThreading ON), следовательно, статическое моделирование 962100 хромосом займет 13469400 секунд (без учёта времени на дополнительные операции) или 155 дней, 21 час, минут.
Общее количество возможных хромосом составляет З21 или 1,046 1010. Следовательно, генетический алгоритм просмотрит 0,01% возможных решений.
Оптимизация при помощи БСД занимает по времени 15 минут на создание структуры БСД и около 30 секунд на задание начальных вероятностей и их распространение по структуре БСД. Таким образом, для получения множества решений при помощи БСД необходимо 930 секунд. Очевидно, что оптимизация при помощи БСД происходит несравненно быстрее, чем при помощи генетического алгоритма.
Пусть в вычислительной сети находится 2 сервера данных и некоторое количество коммуникационных узлов и рабочих станций. В подсети каждого узла находится десять рабочих станции. Сервера данных подключены к первому узлу.
Время оптимизации ВС зависит от количества рабочих станций и, соответственно, количества коммуникацонных узлов. Для сравнения методов оптимизации был проведён вычислительный эксперимент, состоящий в оптимизации вычис лительных сетей последовательно увеличивающегося размера. Временные замеры процессов оптимизации приведены на рисунке 4.9
На графике 4.9 видно, что время, занимаемое оптимизацией при помощи сетей доверия носит линейный характер, в то время как время оптимизации генетическим алгоритмом носит характер, близкий к квадратичному. Также следует отметить, что для малых сетей (до 30 рабочих станций) генетический алгоритм выполнил оптимизацию быстрее, хотя на больших сетях (от 60 рабочих станций) преимущество БСД становится заметным. Из этого можно сделать вывод, что применение байесовских сетей доверия оправдано при оптимизации ВС большого размера.
