Содержание к диссертации
Введение
Глава 1. Обзор и сравнительный анализ САПР вычислительных сетей ...10
1.1. Моделирование ВС с целью изучения поведения отдельных ее параметров 10
1.2. Моделирование потоков данных 16
1.3 Теория возможностного программирования 19
1.4. Методы описания прикладных процессов 22
1.4.1. Функциональное моделирование 22
1.4.2.Структурное моделирование 33
1.5. Обзор существующих систем моделирования и проектирования ВС 47
1.5.1 Зарубежные коммерческие системы 47
1.5.2. Проект Network Simulator 2 53
Глава 2. Модель вычислительной сети для автоматизированного проектирования
2.1. Виды переменных, характеризующих ВС 59
2.1.1. Трафик 59
2.1.2. Вычислительная загрузка узлов 59
2.2. Вероятностная и нечеткая природа трафика и вычислительной загрузки . 60
2.2.1. Вероятностная природа трафика 60
2.2.2. Вероятностная природа вычислительной загрузки 62
2.2.3. Возможности измерения трафика 63
2.2.4. Определение нечеткой вероятностной величины 65
2.3. Моделирование вычислительной сети 73
2.3.1. Функциональное моделирование ВС. Дополнения к языку DFD 73
2.3.2. Структурное моделирование ВС 74
2.3.4. Имитационная модель ВС 76
2.3.5. Лингвистическое описание модели ВС в САПР 78
2.4. Методика проектирования вычислительных сетей 83
2.5. Оптимизация результатов проектирования 84
2.5.1. Стандартный генетический алгоритм 84
2.5.2. Перегруппировка блоков потоковой диаграммы относительно физической структуры сети. Адаптация стандартного генетического алгоритма 86
Глава 3. Структурно функциональное решение САПР ВС 89
3.1. Выбор среды реализации 89
3.2. Этапы проектирования. Общая структура САПР ВС 90
3.2.1. Начальный этап проектирования ВС. Специализированный графический редактор 91
3.2.2. Расчет обобщенной модели. Генетический алгоритм 92
3.2.3. Общая структура САПР ВС 95
3.2.4. Интерфейс САПР ВС. Этапы проектирования 97
3.3. Иерархии классов системы 101
3.4. Основные алгоритмы САПР ВС 103
Глава 4. Реализация и внедрение САПР ВС 107
4.1. Реализация вычислительных экспериментов на базе локальной сети ОАО «УКБП» 107
4.1.1. Общее описание 107
4.1.2 Функциональная схема цикла деятельности УКБП 107
4.1.3. Формирование рабочей нагрузки в ЛВС УКБП 109
4.1.4. Структурная схема ЛВС УКБП 111
4.1.5. Вычислительные эксперименты по сети УКБП 113
4.2. Описание проектируемой сети ОАО «Ульяновский ?авод тяжелых и уникальных станков» 121
4.2.1. Общее описание 121
4.2.2. Описание основного цикла деятельности ОАО «УЗТС» 121
4.2.3. Описание прикладных процессов ЛВС ОАО УЗТС 123
4.2.4. Описание проекта локальной вычислительной сети ОАО «УЗТС». 124
4.2.5. Результаты вычислительных экспериментов 125
4.3. Преимущества автоматизированного проектирования вычислительных сетей 126
Заключение 129
Список литературы
- Теория возможностного программирования
- Вероятностная и нечеткая природа трафика и вычислительной загрузки
- Этапы проектирования. Общая структура САПР ВС
- Функциональная схема цикла деятельности УКБП
Введение к работе
Проектирование сложных технических систем, таких как локальные, корпоративные и телекоммуникационные вычислительные сети - сложный многоуровневый процесс. Он заключается в построении оптимальной системы, максимально использующей свои ресурсы. В настоящее время научные исследования направлены на моделирование уже существующей сети для проверки ее эффективности и выявления ошибок. При моделировании действующей сети, человек обладает рядом статистических данных, после обработки которых, он может внести изменения в ее конфигурацию. При проектировании новой сети, таких данных нет, и проектировщик может лишь предвидеть, прогнозировать, как будет загружен тот или иной сетевой канал, насколько велик будет объем вычислений, производимых тем или иным узлом сети. Подобные прогнозы представляют собой некоторые лингвистические формулировки, которыми можно оперировать, используя аппарат нечетких вероятностных величин. В процессе проектирования необходимо учесть и будущее назначение сети, для чего нужно построить имитационную модель тех процессов, которые будут в ней происходить. Только осознавая круг задач сети, можно построить ее наиболее эффективно. Модель прикладного уровня должна содержать прогнозные данные о сети, которые используются при ее дальнейшей оптимизации.
Актуальность проблемы
Учитывая огромное распространение локальных, глобальных и телекоммуникационных вычислительных сетей, необходимо развивать категорию САПР, относящуюся к ним. Существует несколько различных систем, позволяющих моделировать процессы, происходящие в вычислительных сетях на физическом уровне. Однако до сих пор не создавался (или не получил широкого распространения) инструмент который не просто моделирует, но и проектирует вычислительную сеть на всех ее уровнях.
Сейчас корпоративные сети создаются стихийно, привязываясь лишь к пространственному фактору. Сетевые администраторы опираются на расположение вычислительных машин в кабинетах, залах и на этажах. В таком подходе кроется множество подводных камней - ошибок, которые становятся критичными при дальнейшем росте и развитии сети. Порой приходится переделывать целые сегменты вычислительной сети из-за того, что изначальный проект не был рассчитан на дальнейший рост и развитие системы.
Первоначально необходимо создавать проект сетч, с возможностью моделировать и оптимизировать его, до того, как начаты работы по созданию физической сети. Однако среди существующих программных пакетов не представлены подобные решения. Не осознан до конца и сам процесс подобного проектирования, его этапы и методика. Основные методы моделирования и перестроения сетей построены на том, что с существующей сети, путем многократных статистических измерений, снимаются данные о трафике, вычислительной загрузке узлов. Затем эти данные анализируются, и эксперт выдает рекомендации по перестроению сегментов или всей сети в целом. Зачастую в этом процессе не учитывается структура потоков данных на предприятии, структура его прикладных процессов, которые и являются основными источниками трафика и вычислительной загрузки системы. Кроме этого, при проектировании сети с нуля, измерений для анализа не имеется, и проектировщик может оперировать лишь прогнозами. Следовательно, необходимо в систему проектирования вводить описания прикладных процессов, которые позволят даже на основании прогнозных данных вырабатывать оптимальные решения.
Перечисленные аспекты проблемы проектирования вычислительных сетей делают тему диссертационной работы актуальной.
Цель диссертационной работы
Целью диссертации является разработка методов, моделей и алгоритмов, позволяющих повысить качество автоматизированного проектирования вычислительных сетей в условиях неопределенности, за счет применения автоматической оптимизации, а так же позволяющих сократить время, затрачиваемое на проектирование.
Задачи исследования
Для достижения поставленной цели необходимо решить ряд задач:
1. Провести сравнительный анализ существующих систем моделирования вычислительных сетей, а так же анализ существующих языков имитационного моделирования;
2. Выработать ряд дополнений к выбранному языку имитационного моделирования с целью его адаптации к моделированию вычислительных сетей;
3. Построить методику слияния двух видов описаний сети: прикладного описания на уровне прикладных процессов и физической структуры сети; 4. Разработать модель трафика вычислительной сети;
5. Сформировать алгоритм оптимизации проектных результатов;
6. Разработать и реализовать систему автоматизированного проектирования вычислительных сетей на основе диаграмм потоков данных, и исследовать ее эффективность в вычислительных экспериментах.
Научная значимость работы
Автор защищает: разработанную методику автоматизированного проектирования вычислительных сетей; разработанные модели сети, и алгоритмы ее оптимизации; результаты теоретических, экспериментальных и практических разработок.
Научная новизна
Впервые:
1. Предложено проблемно-ориентированное расширение языка имитационного моделирования диаграмм потоков данных Data Flow Diagram (DFD) для проектирования вычислительных сетей;
2. Разработана модель трафика сети, позволяющая на основе вероятностных нечетких величин оперировать прогнозными данными о трафике и вычислительной загрузке сети;
3. Разработана модель рабочей нагрузки вычислительной сети на
основе потоков данных; 4. Исследована эффективность предлагаемых моделей и методик их использования при проектировании вычислительных сетей. Основные положения, выносимые на защиту.
1. Модель рабочей нагрузки вычислительной сети на основе описания потоков данных прикладных процессов, позволяющая отразить уровень прикладных процессов при проектировании вычислительной сети.
2. Расширение языка потоковых диаграмм (DFD), позволяющее описать расписание работы прикладных задач и выполнить имитационное моделирование трафика вычислительной сети.
3. Алгоритм топологического автоматизированного проектирования вычислительной сети, на основе потоковой модели рабочей нагрузки.
4. Алгоритм размещения прикладных процессов на основе нечеткого генетического гибридного алгоритма.
Практическая значимость работы.
Созданная система автоматизированного проектирования вычислительных сетей практически используется в производстве и позволяет достичь наиболее качественного построения вычислительных сетей, что влечет за собой повышение их эффективности.
Теория возможностного программирования
Теории возможностного программирования посвящены исследования А.В. Язенина, который работает на математическим аппаратом нечетких случайных величин.
Нечеткая случайная величина есть математическая модель случайного эксперимента с нечетким исходом. [Язенин, 1995]. В литературе, наряду с определением нечеткой случайной величины, вводятся определения ее математического ожидания, изучаются его свойства и предлагаются способы его вычисления в ряде частных случаев. Однако, по-прежнему, ряд важных вопросов, таких как способ представления нечеткой случайной величины, определение дисперсии и ковариации, разработка исчисления нечетких случайных величин, остается открытым. Это обстоятельство явно сдерживает применение нечетких случайных величин для моделирования комбинированного типа неопределенности в задачах принятия решений.
В работах [113,114] представлены результаты, отражающие последние достижения в приведенных выше направлениях. Рассматривается представление нечеткой случайной величины, позволяющее эксплицировать случайные и нечеткие факторы и построить соответствующее исчисление. Анализируются подходы к определению моментов второго порядка. Развиваемый математический аппарат и исчисление нечетких случайных величин ориентированы на их использование в задачах оптимизации и принятия решений, в частности на задачи портфельного анализа.
Автор [Язенин, 1995] в своих исследованиях вводит необходимые определения и понятия. Пусть Г есть множество элементов, обозначаемых далее через уеГ, Р(Г)- множество всех подмножеств Г, Еп - п - мерное евклидово пространство. Определение 1. Мерой возможности называется функция множеств л :Р(Г)— Ех, обладающая свойствами: я-{0} = О,;г{г} = 1; 2. {ЩЬзирф,}, /є/ /є/ для любого индексного множества / и множеств Аі є Р(Г ).
Триплет (Г,Р(г),;г) называется возможностным пространством. Определение 2. Возможностной (нечеткой) переменной (величиной) называется отображение Z :Г —» Е1. Распределением возможностных значений переменной Z называется функция //z : Е — Е1, определяемая по правилу: juz(z) = 7r{reT:Z(r) = z}, \/гєЕх. /л2 (z) - есть возможность того, что переменная Z может принять значение Z. Из последнего определения и свойств возможностной меры следует, что a)0 juz{z) \,VzeEx; б) supjuz(z) = 1. zeE1 Определение 3. Носителем возможностной переменной Z называется множество supp (z) = [zє El /juz(z) Oj. Определение 4. г- уровневым множеством нечеткой величины Z называется множество Zr = jz є Я11/лг{г) г],г є (0,l].
Мера необходимости v является двойственным понятием по отношению к мере возможности и определяется следующим образом: У{А) = \-Я(АС), где "с" обозначает дополнение множества А є Р(г).
Опираясь на результаты, дадим определение нечеткой случайной величины и ее интерпретацию.
Пусть (Q, В, Р) есть вероятностное пространство. Определение 5. Нечеткая случайная величина X есть вещественная функция Х(у):ПхГ- Е\ такая, что при любом фиксированном у є Г, величина Ху = Х(а),у) является случайной величиной на (Q,B,P). Из приведенного определения следует две интерпретации.
При фиксированном о) є Q мы получаем нечеткую величину Хт= Х{а,у). То есть мы имеем случайную величину, значениями которой являются нечеткие величины, описываемые возможностными распределениями jux(x,co).
При фиксированном у мы можем рассматривать X как случайную величину с возможностью, определяемой мерой возможности. Все сказанное выше становится более ясным, когда распределение jux (х,со) будет определяться как в случае нечеткой переменной: jux(x,6)) = 7г{у еГ:Х(со,у) = х) УхєЕ1. Теперь каждому со отвечает возможностное распределение, представляющее случайный выбор эксперта, который дает неопределенную, субъективную оценку при определенном количестве.
С другой стороны, фиксируя у, имеем, что X есть случайная величина, при этом мы не уверены в значении ее распределения.
В контексте принятия решений математическое ожидание играет решающую роль для объяснения случайной информации. Определить математическое ожидание Е{х(а ,у)} нечеткой случайной величины Х(со,у) можно различными способами.
Вероятностная и нечеткая природа трафика и вычислительной загрузки
В области математического моделирования потоков данных чаще встречаются работы, посвященные системам управления сложными техническими комплексами (СУ СТК), и перераспределению потоков данных в них. Авторы в своих исследованиях считают, что в процессе функционирования на СУ СТК оказывают влияние многочисленные внешние и внутренние возмущающие воздействия [Сухов, 2000]. Характер внутренних возмущающих воздействий обусловлен наличием случайных факторов в предметной области отношений - нестабильности в движении транспортных средств, осуществляющих обмен ресурсами, неплановые потери и расход ресурсов, внутренние сбои и отказы технических средств субъектов СУ СТК и т.п.
Для исследования автор [Сухов, 2000] ставит проблему оптимального управления объектом СУ СТК при ее адаптации в существующей социально-экономической среде на основе информационного противодействия внешним и внутренним возмущающим факторам с учетом ограниченных ресурсов системы. Предлагается подход, основанный на введении информационной меры, позволяющей получить отображение предметной (ресурсной) области отношений в информационную, целевую область. В информационной области отношений возможно корректное решение задачи оптимального управления с последующей реализацией полученных управляющих воздействий в предметной области отношений. Такой информационный подход позволяет в информационной области выявить и при наличии соответствующих ресурсов подавить вредное влияние на систему возмущающих факторов. При этом учитываются частные целевые задачи субъектов СУ СТК. В отличие от перечисленных выше данный подход использует детерминированные методы и позволяет четко сформулировать целевую задачу оптимального управления для системы со случайными параметрами.
Рассматривается система управления сложным техническим комплексом, состоящая из п субъектов и объекта управления, находящихся в заданной системе отношений между собой (связи между элементами). Для каждого элемента системы определен обобщенный вектор-столбец ресурсов Rh Rt = {R ti, R СІ) где верхний индекс 1 - символ транспонирования, 1 = 1, 2, ..., т, Ra -технические компоненты вектора, Rci - социальные компоненты вектора. Для объекта управления задан обобщенный вектор, описывающий начальное состояние RofTfJ, и вектор технических требований в конце временного отрезка управления RoCr ).
Вектор ресурсов является векторной функцией времени и меняет свое значение для каждого элемента системы в процессе ресурсного обмена: R = R(t), te[r№ TJ. Динамика обобщенного вектора ресурсов может быть представлена системой стохастических дифференциальных уравнений. R(t)= F(R(t),t,n{t)) где n(t) - вектор возмущающих факторов.
Требуется на заданном временном отрезке [Т№ TJ обеспечить изменение Ro(t) до значения Ro(TJ при условии функциональных ресурсных ограничений для элементов СУ СТК с минимизацией расходования ресурсов системы: WRo(rj - R0(TJ\ R(t)eRit te[TH, TJ, JTKL(R(t),t)dt- min где W- целевой оператор ресурсного отображения объекта управления, Ri - область допустимых ресурсных ограничений для элементов СУ СТК, і є [1, ..., m], L(.) - интегрант функционала расхода ресурсов.
Общая схема решения задачи заключается в выполнении следующих этапов: обоснование отображения предметной области в информационную область отношений; формулировка задачи оптимального управления в информационной области отношений; согласованное представление динамики ресурсного обмена: оптимальное оценивание вектора состояния для элементов системы в предметной области отношений (подготовка к отображению в информационную область); поиск оптимального управлетія в информационной области отношений и его реализация в предметной области.
С целью синтеза экспертной системы поддержки принятия решений для СУ СТК необходима реализация полученного математического обеспечения системы управления программными средствами на ЭВМ, что может быть получено с использованием объектно-ориентированного подхода.
Этапы проектирования. Общая структура САПР ВС
На начальном этапе проектирования необходимо описать предполагаемые задачи вычислительной сети и их взаимосвязи. Это производится путем составления диаграммы потоков данных сети на основе адаптированного языка DFD. На этом этапе проектировщик описывает происходящие в сети процессы блоками, а так же указывает взаимосвязи между ними. Здесь необходимо полное описание процессов с заполнение всех атрибутов (расписание работы и т.д.). Здесь же указываются и прогнозные оценки трафика и вычислительной загрузки узлов, генерируемых каждым из процессов.
Параллельно с составлением диаграммы потоков данных в сети проектировщик составляет и функциональную модель сети на уровне узлов, коммутаторов и каналов связи. Здесь составляется физическая структура сети с указанием ІР-адресов узлов. При составлении физической модели производится настройка IP-маршрутизации в системе.
Предлагаемая САПР ВС для решения зада1» начального этапа проектирования содержит в себе специализированный графический редактор. Работающий в двух режимах.
В первом режиме редактор позволяет создавать DFD-диаграммы, с заполнением всех атрибутов каждого процесса. Здесь устанавливаются расписания работы процессов, устанавливаются нечеткие случайные оценки генерируемого трафика и вычислительной загрузки. Прогноз формируется для каждого конкретного блока в отдельности. Используя этот редактор, проектировщик составляет графическую модель функциональной структуры сети. При этом данные, указанные в графической модели автоматически заносятся в структуру данных, описывающую обобщенную модель сети. Существует возможность копировать блоки диаграммы, копировать расписания из одних блоков в другие, реализован механизм Drag-n-drop, который позволяет удобно размещать блоки на диаграмме.
Второй режим графического редактора предназначен для составления физической модели сети. Имеется возможность добавлять в модель узлы сети, коммутаторы, концентраторы и так же шлюзы и соединять их каналами связи. Для каждого модуля в сети можно просмотреть и изменить его настройки. Параметры модулей в основном отвечают за ІР-маршруїйзацию в системе. В этом редакторе составляется графическое описание физической структуры сети со всеми ее свойствами. Так же как и в случае с редактором диаграмм, данные, использованные в графической модели, интегрируются в обобщенную модель сети.
После того, как модель прикладных процессов и предполагаемая модель сети составлены, необходимо построить их взаимосвязь. Это осуществляется путем распределения блоков диаграммы по физической структуре проектируемой сети. Фактически временно выстраивается обобщенная модель сети. За поиск наилучшего варианта этого распределения отвечает генетический алгоритм.
Хромосомой в данном генетическом алгоритме является единичный вариант расстановки блоков диаграммы по физическим узлам сети. В программной реализации хромосома имеет 2 части - фиксированную и изменяемую. Фиксированная часть содержит номера блоков диаграммы прикладных процессов, а в изменяемой части находятся номера узлов сети, взятые из схемы ее физической структуры.
Целевая функция генетического алгоритма состоит из 2-х частей. Первая часть функции стремится к уменьшению суммарного трафика в системе. Вторая часть стремится к тому, чтобы максимальная вычислительная загрузка одного узла была наименьшей.
Расчет целевой функции соответственно происходит в 3 этапа. На первом этапе рассчитывается суммарный трафик в системе. Расчет строится на суммировании нечетких оценок, заложенных в диаграмму потоков данных. При этом производится трассировка связей диаграммы по каналам, описанным в физической модели сети. Каждый узел и коммуникационный модуль сети представляется как генератор сетевого трафика с нечетким вероятностным значением на выходе. Соответственно если через такой генератор проходит несколько связей, то значение на выходе увеличивается. Связь трассируется по сети, с учетом особенностей используемого коммуникационного оборудования. Если генератор выдает трафик в подсеть с концентратором, то трафик, генерируемый самим концентратором, увеличится пропорционально количеству его портов. Если же в подсети стоит коммутатор, то при трассировке очередной связи, генерируемый им трафик увеличится на величину трафика этой связи. После трассировки все значения генераторов суммируются в единую вероятностную оценку суммарного трафика.
Вторая часть целевой функции рассчитывается подобным же образом, только система оперирует с нечеткими вероятностными оценками вычислительной загрузки.
Как заложено в СГА популяция подвергается отбору, рекомбинации и мутации. Рекомбинации подвергается изменяемая часть хромосомы.
Функциональная схема цикла деятельности УКБП
Основной цикл деятельности предприятия компьютеризован и охвачен ЛВС. Функциональная схема этого цикла приведена на рисунке 4.1.
Большую часть цикла деятельности предприятия составляет составление ПО для производимого оборудования. По каждому направлению одновременно ведется несколько проектов, за каждый из которых обычно отвечает 1 НИО. Начальники НИО и главные конструктора направлений занимаются сборкой проектов в одно целое, и отчитываются об их состоянии перед службой маркетинга и менеджмента. В свою очередь СММ составляет план-график работ и следит по этим отчетам за его выполнением, отчитываясь перед директором НТЦР (1 зам генерального директора ОАО).
В настоящий момент эта структура охвачена ЛВС, которая служит для передачи необходимой информации, оперативной связи, сборки проектов воедино и т.п.
Основной вид прикладных процессов, происходящих в ЛВС УКБП -передача данных по проектированию. Фактически на уровне каждой бригады программистов или конструкторов ведется распределенное проектирование, части которого собираются бригадиром, либо начальником НИО. Каждое НИО имеет свой сервер, на котором и хранится вся эта информация. Доступ к этим серверам имеют главные конструктора, которые контролируют процесс проектирования. СММ передает по серверам план-график для каждого конкретного направления и собирает информацию с главных конструкторов о ходе работ.
Общий принцип построения ЛВС УКБП - иерархический. Каждое подразделение, имеющее несколько вычислительных машин, имеет свой маршрутизатор, отделяющий его в подсеть. Маршрутизаторы, в свою очередь объединены в магистральную сеть, где коммутирующим модулем является мощный управляемый коммутатор. К магистральной сети подключен центральный сервер предприятия, который управляет маршрутизацией на магистральном уровне, а также является DNS-, WINS-, и локальным WEB-сервером. Общая структура сети УКБП представлена на рис. 4.5.
В магистральной сети содержатся все сервера подразделений, а так же вычислительный машины генерального директора и директора НТЦР. В большинстве подсетей для коммуникации использованы коммутаторы. В подсетях крупных отделов (КО, НИО-14, НИО-12) применено одноуровневое каскадирование коммутаторов. Подробная структура ЛВС УКБП и ее представление в вычислительном эксперименте отображено на рис. 4.6.
Эксперименты на сходимость показали, что СГА сходится к оптимуму практически при любых своих параметрах, поэтому для проведения дальнейших экспериментов были выбраны параметры Р=5000, элита=2000, мутация 0,4.
Второй этап экспериментов по сети УКБП включал в себя поиск оптимального расположения прикладных процессов сети в сравнении с существующим расположением. Оптимизация производилась по нескольку раз для различных значений коэффициентов важности.
Проведенный эксперимент показал, что в результате неоднократного поиска оптимального расположения прикладных процессов сети ОАО «УКБП», были получены конфигурации сети, отличающиеся более низким значением трафика сети и более низким значением вычислительной загрузки.
Третий этап экспериментов включал в себя ручное внесение изменений в конфигурацию существующей сети, и повторную оптимизацию проекта. В диаграмму прикладных процессов предприятия было вручную добавлено 4 новых прикладных процесса, т.е. было смоделировано добавление задач для существующей сети. Затем, так же как и во втором этапе экспериментов, было выполнено по нескольку прогонов оптимизации для разных значений коэффициентов важности. Сравнение производилось с параметрами сети, полученными после добавления прикладных процессов без использования оптимизации.
