Автоматизированное проектирование вычислительных сетей крупных проектных организаций

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание ученой степени доктора технических наук

Автоматизированное проектирование вычислительных сетей крупных проектных организаций



Общая характеристика работы

Актуальность проблемы

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

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

Следовательно, автоматизированное проектирование (АП) ВС предполагает в качестве обязательной компоненты подсистему моделирования сети. Математическая модель ВС описывает топологию узлов, каналов и коммуникационного оборудования. Взаимодействие узлов на прикладном уровне описывается как взаимодействие производственных процессов. Однако современные средства АП ВС не решают задачу комплексно, в частности не включают специальные подсистемы математического моделирования трафика ВС.

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

Цель диссертационной работы

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

Задачи исследования

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

* необходимо провести сравнительный анализ известных интеллектуальных методов оптимизации, существующих систем автоматизированного проектирования и моделирования ВС, в том числе языков имитационного моделирования;

* необходимо построить математическую модель АП ВС, позволяющую использовать современные методы поиска проектных решений, в том числе генетическую оптимизацию; адаптировать генетические алгоритмы (ГА) к задаче оптимизации ресурсов в ВС;

* необходимо разработать интеллектуальную систему АП ВС на основе моделирования рассуждений проектировщика ВС, исследовать применимость схемы рассуждений на основе распространенного метода байесовских сетей доверия (БСД);

* необходимо разработать формализованную модель трафика ВС, позволяющую использовать как качественные оценки, так и результаты статистических измерений;

* необходимо выработать ряд дополнений к известным языкам имитационного моделирования с целью их адаптации к задаче АП ВС, построить методику слияния двух видов описаний сети: прикладного описания и описания транспортной структуры сети;

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

* необходимо разработать функциональные модели узлов на прикладном уровне: имитационные модели серверов и клиентов;

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

* необходимо разработать и реализовать средства оптимизации ВС как программную систему и исследовать ее результативность на примере ВС конкретных проектных организаций.

Методы исследования

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

Результаты, выносимые на защиту

Основные положения, выносимые на защиту.

1. Теоретический подход к построению САПР ВС, сочетающий проектные процедуры с моделированием трафика и оптимизацией проектируемой ВС.

2. Методы оптимизации проектных решений на основе генетических алгоритмов (ГА) и байесовских сетей доверия (БСД), позволяющие определить состав коммуникационного оборудования и пропускную способность каналов.

3. Язык дополненных потоковых диаграмм взаимодействия прикладных задач, позволяющий выполнить имитационное моделирование трафика ВС.

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

5. Формализованные функциональные модели прикладных процессов: имитационные модели серверов и клиентов на основе сетей Петри.

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

Научная значимость работы.

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

Научная новизна. Впервые:

1. Адаптированы методы генетической оптимизации для всех основных этапов автоматизированного проектирования ВС.

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

3. Разработаны методы поиска проектных решений на основе байесовской оптимизации.

4. Предложен язык модифицированных DFD-диаграмм (Data Flow Diagram), дополненных расписанием, для автоматизированного проектирования ВС.

5. Предложен метод моделирования протоколов маршрутизации с использованием нечетких метрик;

6. Разработаны формализованные функциональные модели узлов, как элементов прикладных процессов: имитационные модели серверов и клиентов на основе сетей Петри;

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

8. Разработан алгоритм для решения задачи генерации транспортной схемы ВС, обеспечивающей успешное выполнение прикладных задач.

Практическая ценность и внедрение результатов

Созданная система автоматизированного проектирования вычислительных сетей используется на производстве и позволяет достичь улучшенных технико-экономических показателей объектов проектирования. Предлагаемый теоретический подход, методы и средства автоматизированного проектирования были успешно применены в проектных работах, выполняемых предприятием ФНПЦ ОАО «НПО «МАРС» в интересах АСУ ВМФ РФ (Море-99, Мелодия, Запевала и др.). Созданная САПР ВС активно используется в производстве и позволяет эффективно перераспределять высокопроизводительный трафик путем применения предлагаемого подхода и автоматической оптимизации, а так же сокращать время, затрачиваемое на проектирование вычислительных сетей.

Практическая ценность состоит в том, что разработанные модели и алгоритмы реализованы в форме программной системы и внедрены в деятельность ФГУП НПО «Марс» (г. Ульяновск). Практическое использование результатов диссертационной работы подтверждено соответствующими документами о внедрении.

Основания для выполнения работы

Данная научная работа выполнялась в рамках тематического плана научных исследований Федерального агентства по образованию в 2005, 2006, 2007, 2008 г., была поддержана грантами РФФИ №06-01-02012 и 06-01014087 в 2006 г., №08-01-97006 в 2008 г., ряд задач исследования решался в рамках х/д НИР №100/05, выполняемого Ульяновским государственным техническим университетом по заказу ФНПЦ ОАО «НПО МАРС»

Достоверность результатов диссертационной работы.

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

Апробация работы и публикации

Основные положения и результаты диссертации докладывались, обсуждались и получили одобрение на Международной конференции «Континуальные логико-алгебраические и нейросетевые методы в науке, технике и экономике» (г. Ульяновск, 2005 г., 2006 г.), на Международной конференции «Интерактивные системы» (г. Ульяновск, 2005 г.), на Научных сессиях МИФИ (г. Москва, 2007 г., 2008 г.), на Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте». (г. Коломна, 2007 г.), на Международной научно-технической конференции «Интеллектуальные системы», «Интеллектуальные САПР» (г. Дивноморское, 2006 г., 2007 г., 2008 г.), на Первой Всероссийской конференции «Нечеткие системы и мягкие вычисления» (г. Тверь 2006 г.), на Второй Всероссийской конференции «Нечеткие системы и мягкие вычисления» (г. Ульяновск, 2008 г.), на Национальных конференциях с международным участием по искусственному интеллекту (г. Обнинск 2006 г., г. Дубна 2008 г.), на Всемирном конгрессе IFSA'07 (Мексика, г. Канкун, 2007 г.), на 34-ом международном салоне изобретений, новой техники и товаров «Женева-2006» (г. Женева, Швейцария, 2006 г.).

Структура и объем работы

Диссертация состоит из введения, шести глав, заключения и приложений. В диссертации приведены 96 рисунков, 23 таблицы и 7 приложений.



Основное содержание работы

сеть алгоритм маршрутизация автоматизированный

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

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

Анализ предметной области позволил выделить следующие особенности ВС крупных проектных организаций:

* ВС за время эксплуатации постоянно изменяется - эволюционирует, так как увеличение объема проектных работ требует адекватного роста ресурсов ВС.

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

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

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

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

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

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

* для того чтобы прогнозировать трафик на том или ином канале ВС, необходимо понимать его нечеткую и одновременно вероятностную природу;

* для того чтобы САПР могла обрабатывать прогнозные значения трафика, необходимо использовать специализированный математический аппарат, в котором заложена возможность работы с подобными величинами.

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

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

В главе сделан вывод о том, что автоматизированное проектирование ВС требует в качестве обязательной компоненты систему моделирования сети. Сеть представляет собой топологию узлов, каналов и коммуникационного оборудования. Каналы обеспечивают передачу сигналов - пакетов трафика. Природа трафика - нечеткая случайная величина. Топология задается графом, в развитом виде - нечетким гиперграфом. Узлы на транспортном уровне представляют собой генераторы и потребители трафика и могут быть заданы матрицей интенсивности. На прикладном уровне узлы делятся на серверы: данных, файлов, прокси и на «толстых» и «тонких» клиентов. Взаимодействие узлов на прикладном уровне может быть описано на уровне прикладных процессов, например с помощью модифицированных DFD-диаграмм (дополненных расписанием работы ВС).

Приведенные в главе обзор и анализ состояния автоматизированного проектирования ВС позволяют сформулировать основные задачи исследования.

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

* уровень топологии, включающий в себя структуру ВС и схему коммуникационного оборудования (Топ-уровень);

* уровень генерации, передачи и потребления трафика (Тр-уровень);

* уровень маршрутизации ВС (М-уровень).

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

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

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

Рассмотрим составные части Т-модели < Топ-уровень, Тр-уровень, М-уровень> последовательно.

Топ-уровень представления Т-модели - это нечеткий гиперграф. Из большого разнообразия графовых моделей представления структуры ВС выбран гиперграф, так как каждая вершина гиперграфа может раскрываться в самостоятельный граф (гиперграф) по мере уточнения проекта топологии ВС. Нечеткий гиперграф позволяет учесть вариативность фрагментов топологии на тех стадиях проектирования, когда проектное решение еще не выбрано.

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

Если все различны, гиперграф называется простым, иначе, получаем нечеткий мультигиперграф.

Степень принадлежности вершины ребру называется степенью инцидентности вершины и ребра, и обозначается.

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

Топ-уровень Т-модели включает в себя кроме описания топологии и коммуникационную схему. Коммуникационное оборудование представлено маршрутизаторами, концентраторами и / или коммутаторами. Каждый узел (рабочая станция) может быть подключен только к одному коммутатору / концентратору. Таким образом, каждый коммутатор/ концентратор определяет сегмент ВС. Вид коммуникационного оборудования (коммутаторов или концентраторов) значительно влияет на загруженность каналов связи. Реальная ВС содержит как коммутаторы, так и концентраторы. Улучшить пропускные способности каналов связи можно за счет оптимального выбора коммутаторов или концентраторов.

Задача выбора коммуникационного оборудования задается на уровне каналов связи, каждый канал k характеризуется пропускной способностью - реальной Pk и максимальной Pmaxk (бит/сек.). Интенсивность взаимодействия (передачи сообщений) любой пары узлов - это величина Bij (бит/сек.). Величина Bij измеряется в течение длительного промежутка времени Т и усредняется. Усреднение может быть представлено вычислением среднего значения Bijср, или построением на основе гистограммы распределения вероятностей, или построением функции принадлежности на основе распределения возможностей.

Суммарный трафик, приходящийся на канал связи, зависит от типа канала. Рассмотрим на Топ-уровне только каналы типа <коммутатор / концентратор> - <коммутатор / концентратор>. Тогда можно выделить следующие подвиды каналов:

<коммутатор > - <коммутатор>;

<концентратор> - < концентратор>;

<коммутатор > - < концентратор>.

Суммарный трафик выражается по-разному для 3-х подвидов каналов связи. Для суммарного трафика канала типа <коммутатор > -<коммутатор> справедлива формула:

Множество вершин М1 и множество вершин M2 - это множества узлов по одну и другую стороны от канала связи.

Суммарный трафик канала <концентратор> - < концентратор> измеряется по-другому, так как канал, образованный концентраторами, образует общую магистраль:

Суммарный трафик канала <концентратор> - <коммутатор> может быть вычислен следующим образом:

Необходимость модификации (перепроектирования) ВС определяется по степени близости суммарного трафика и пропускных способностей каналов связи.

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

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

Каждый процесс в функциональной модели ВС рассматривается как генератор сетевого трафика с величиной, заданной словесной оценкой. На рассматриваемом интервале времени значение трафика распределяется в соответствии с мерой возможности оценки его значения. Например, оценка «скорее высокий» расшифровывается как НСВ {«низкий»/0, «средний»/0.25, «высокий»/0.75}.

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

При использовании НСВ в качестве формы выражения величины трафика операция сложение выполняется как сложение нечетких величин. Обозначим через нечетко заданное среднее число сообщений в секунду, проходящих по i-му каналу.

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

c(P)=c(E1)+ c(E2)+ … + c(Eк).

Таким образом, общей метрикой маршрута является объединение нечетких величин параметров каналов связи и узлов маршрутизации, которые в свою очередь представляют собой объединение нечетких интервалов каждой из локальных характеристик.

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

Таким образом, вторая глава диссертационной работы содержит описание предложенной Т-модели транспортной схемы ВС. Т-модель позволяет выполнить имитационное моделирование варианта проектного решения ВС в процессе автоматизированного проектирования.

В третьей главе содержится описание разработанной математической модели для представления прикладных процессов в ВС (П-модель). П-модель учитывает широкое распространение современной сервисо-ориентированной архитектуры прикладных информационных систем. Любая реальная прикладная среда представляет собой сложное сочетание взаимодействующих прикладных агентов ВС: сервисов и клиентов (уровень агентов: сервисов и клиентов). Такой уровень описания назовем А-уровень. Взаимодействие агентов формирует прикладной процесс, состоящий из событий, связанных между собой потоками передаваемых данных. Поэтому можно говорить о потоковом уровне описания П-модели. Потоки данных принято выражать с помощью какой-либо разновидности потоковых диаграмм (Data Flow Diagram) или DFD-диаграмм. Назовём уровень П-модели, отражающий потоки данных DFD-уровнем. Таким образом, П-модель состоит из двух составных частей: <A-уровень, DFD-уровень>.

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

На А-уровне П-модели разработаны формализованные модели «тонкого» и «толстого» клиентов. «Тонкий» клиент реализует только презентационную логику - прикладной интерфейс для пользователя. Основной функцией для «тонкого» клиента является генерация запроса, а, следовательно, основная характеристика - частота генерации запроса. «Толстый» клиент объединяет в себе презентационную логику и логику выполнения и представляет собой обычную архитектуру рабочей станции. Основными функциями «толстого» клиента являются генерация запроса, анализ запроса, обработка запроса. Основные характеристики: частота генерации запроса, время обработки запроса, занятость (выходная переменная).

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

Каждый прикладной агент А-уровня представляется в виде раскрашенной сети Петри. Поскольку моделирование проводится на прикладном уровне, то в сети передаются не пакеты, а абстрактный объект с данными (фрейм). С помощью раскрашенных сетей Петри удобно моделировать переходы данных по вычислительной сети, с выбором устройств на которых проводится обработка. Цветами выступают адреса (mac), данные (data), коэффициенты загрузки (load). Клиент генерирует запрос по заданному расписанию с частотой, указанной в базе данных приложений. Запросы генерируются каждый такт с вероятностью, пропорциональной частоте, по нормальному закону распределения.

Взаимодействие прикладных агентов: клиентов и серверов порождает события, составляющие, в свою очередь, прикладной процесс (DFD-уровень). В главе представлен анализ возможности применения DFD-диаграмм (Data Flow Diagram) для формализованного описания процесса проектирования. Основным источником сетевого трафика являются процессы, происходящие на узле сети. При составлении функциональной модели сети следует обозначить все эти процессы и потоки данных, генерируемые ими. Кроме того, каждый из процессов имеет свое расписание выполнения в течение дня, и его необходимо учитывать при моделировании. В связи с этим к части языка DFD, описывающей сущность «процесс», были сделаны дополнения для полного описания процессов, происходящих в ВС. А именно, в свойства сущности «процесс», помимо названия и номера, включены еще нечеткие прогнозные оценки трафика и вычислительной загрузки, а также расписание выполнения процесса. При моделировании работы системы расписание имеет решающее значение, так как в определенные моменты времени процесс не функционирует и генерации трафика в сеть не происходит. Кроме того, для дальнейшей взаимосвязи с физической структурой сети в свойства процесса добавлен IP-адрес того компьютера, на котором этот процесс выполняется.

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

БСД для решения задачи оптимизации ВС состоит из четырех слоев: слой взаимодействий, слой интенсивности трафика, слой внутрисегментных и межсегментных трафиков, слой согласования Т-модели и П-модели. Рассмотрим кратко функции каждого слоя БСД.

Слой 1 - слой взаимодействий. Данный слой вводит в БСД начальные данные об интенсивностях взаимодействия компьютеров ВС между собой на основании информации об автоматизируемых производственных процессах, описанных на языке DFD-диаграмм. Величина интенсивности взаимодействия является нечёткой, так как передаваемый трафик состоит из документов, имеющих четкий размер, и запросов к базам данных, имеющих нечеткий размер.

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

Слой 3 - слой внутрисегментных и межсегментных трафиков. На данном уровне определяется интенсивность внутрисегментных и межсегментных взаимодействий для каждого узла сети. Каждый узел сети образует сегмент. Для каждого узла сети в данном слое существуют два узла БСД - на одном формируется внутрисегментный трафик, на другом - межсегментный трафик. Трафик формируется по принципу протекания через сегмент или внутри него.

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

Таким образом, модели прикладных процессов ВС определяют масштаб, а значит, в конечном счете, транспортную схему ВС.

Итак, третья глава содержит описание разработанной П-модели, включающей модели основных прикладных агентов: серверов и клиентов разных типов, (А-уровень) и модель взаимодействия прикладных процессов, выраженную на языке модифицированных DFD-диаграмм. Построенная П-модель позволяет провести байесовскую оптимизацию параметров прикладных процессов (времени отклика). Разработанные Т-модель и П-модель составляют основные положения нового теоретического подхода к автоматизированному проектированию ВС.

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

Рассмотрим в первую очередь методологию, метод и алгоритмы формирования ТП-модели на основе генетической оптимизации. Можно выделить следующие основные этапы автоматизированного проектирования ВС:

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

2. Разработка Т-модели для проектирования, то есть описание транспортной схемы, структуры ВС. На этом этапе проектировщик описывает саму ВС на уровне узлов сети и каналов связи. Здесь устанавливаются взаимосвязи узлов сети через коммутирующие модули, или маршрутизаторы, расставляются серверы. Для каждого узла сети задается таблица маршрутизации. Фактически моделируется процесс составления и настройки реальной локальной сети.

3. Формирование ТП-модели. На этом этапе производится слияние модели прикладных процессов (П-модель) и транспортной модели сети (Т-модель) в обобщенную модель (ТП-модель) и моделирование ВС на основе прогнозных значений трафика, представленного временным рядом нечетких тенденций. САПР ВС автоматически расставляет блоки диаграммы прикладных процессов, учитывая суммарный трафик сети, а так же вычислительную загрузку отдельных узлов. При помощи генетического алгоритма система находит оптимальный вариант наложения составленной схемы прикладных процессов на спроектированную ВС.

4. Модификация. Заключается во внесении изменений в Т-модель.

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

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

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

F= Fтрафик + Fвыч.загрузка +Fгруппировка

Расчет целевой функции соответственно происходит в 3 этапа. На первом этапе рассчитывается суммарный трафик в системе. Расчет строится на суммировании нечетких оценок, заложенных в диаграмму потоков данных. При этом производится трассировка связей диаграммы по каналам, описанным в транспортной модели сети. Каждый узел и коммуникационный модуль сети представляется, как генератор нечеткого временного ряда трафика на выходе. Соответственно, если через такой генератор проходит несколько связей, то значение на выходе увеличивается. Связь трассируется по сети, с учетом особенностей используемого коммуникационного оборудования. Вторая часть целевой функции рассчитывается подобным же образом, только система оперирует с нечеткими вероятностными оценками вычислительной загрузки. Третья часть целевой функции отвечает за качество группировки блоков диаграммы прикладных процессов по подсетям. Алгоритм ее вычисления таков: определяется количество групп, заданных пользователем. Затем для каждой из групп строится массив IP-адресов, присвоенных узлам, находящимся в этой группе. В этом массиве отыскивается максимальное количество повторяющихся элементов. Чем больше в группе повторяется IP-адресов, тем качество группировки выше.

Так как трафик ВС в Т-модели представлен нечеткой случайной величиной, в четвертой главе предложен метод, использующий нечеткие тенденции временного ряда для генерации трафика в системе моделирования.

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

Определение 1. Нечеткая тенденция (НТ). Пусть - нечеткий временной ряд лингвистической переменной (), - множество нечетких временных рядов одинаковой длины. Тогда нечеткая тенденция ?, определенная на, есть совокупность упорядоченных пар где представляет собой степень принадлежности к НТ.

Если говорить о тенденции как лингвистической переменной, терм-множеством которой является множество различных тенденций, наблюдаемых на ВР, а универсумом - множество всевозможных функций, НТ определяется как, i=1..p, где p - количество видов НТ, определенных на ВР; - множество НВР переменной длины.

Определяя НТ на всех интервалах [t-m+1, t] ВР и позиционируя начало или окончание интервала к временной шкале, получим временной ряд нечеткой тенденции.

Определение 2. Временной ряд нечеткой тенденции (ВРНТ). Пусть - множество нечетких временных рядов длиной m, где, t. Тогда временной ряд нечеткой тенденции есть упорядоченное во времени нечеткое множество:.

В результате экспертного построения НТ могут возникнуть отклонения между исходным ВР и смоделированным. Обозначим данные отклонения как ошибки построения:

- ошибка построения НВР:

.- ошибка построения ВРНТ:

.- ошибка построения ВР:

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

МНТ можно привести к разностному уравнению четкого ВР:

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

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

Множество правил уравнения МНТ составляет второй уровень вывода:

Таким образом, МНТ полностью реализуется многоуровневой системой логических отношений:, где выходы в виде нечетких переменных одного набора правил подаются на входы следующего набора правил без дефаззификации и фаззификации. Преобразования в нечеткие и четкие значения происходит только в отношениях R1 и R3 соответственно. Разработанная модель нечеткой тенденции (МНТ) позволяет построить генераторы нечеткого временного ряда трафика, соответствующего заданной экспертом нечеткой тенденции изменения трафика. Следовательно, МНТ является составной частью обобщенной ТП-модели, на основе которой можно построить результативную систему моделирования ВС в ходе автоматизированного проектирования.

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

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

1. Интерфейсный блок позволяет ввести описание прикладных процессов проектируемой сети при помощи адаптированного языка DFD. На этом этапе проектировщик строит описание структуры прикладных процессов, происходящих в сети, задает расписание работы процессов, и формирует прогнозные оценки генерируемого трафика и вычислительной загрузки. Интерфейсный блок предоставляет возможность проектировщику создать описание исходного варианта транспортной схемы ВС на уровне ее элементов - узлов, коммутаторов, шлюзов.

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

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

4. Блок генетической оптимизации применяет генетическую оптимизацию для решения двух задач: выбора вида коммуникационного оборудования, сегментации ВС.

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

6. Модуль согласования прикладной процессной и транспортной схем (формирование ТП-модели) выполняет поиск оптимального размещения сервисов по транспортной структуре сети. Оптимизация производится по трем критериям качества - максимальное снижение пиковых нагрузок трафика, максимальное снижение пиковых нагрузок вычислительной загрузки и максимальная группировка прикладных процессов по группам.

7. Блок имитационного моделирования на основе временных рядов нечетких тенденций содержит все компоненты системы нечеткого вывода: блоки фаззификации и дефаззификации, блок нечеткого вывода, базу знаний. Блок реализует все этапы построения МНТ, решает широкий спектр задач: многомерный анализ, графическое представление информации, моделирование и прогнозирование, хранение базы знаний.

Созданная программная система автоматизированного проектирования вычислительных сетей практически используется на производстве и позволяет достичь улучшенных технико-экономических показателей объектов проектирования, эффективно перераспределять высокопроизводительный трафик, а так же сокращать время, затрачиваемое на проектирование вычислительных сетей. Предлагаемый теоретический подход, методы и средства автоматизированного проектирования были успешно применены в проектных работах, выполняемых предприятием ФНПЦ ОАО «НПО «МАРС» в интересах АСУ ВМФ РФ (Море-99, Мелодия, Запевала и др.).

В следующей главе приведены результаты вычислительных экспериментов в данной программной среде САПР ВС.

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

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

2. Разработка Т-модели для проектирования, то есть описание транспортной схемы, структуры ВС. Генетическая оптимизация для решения двух задач: выбора вида коммуникационного оборудования, сегментации ВС.

3. Формирование ТП-модели. Слияние модели прикладных процессов (П-модель) и транспортной модели сети (Т-модель) в обобщенную модель ТП-модель (САПР ВС расставляет блоки диаграммы прикладных процессов, учитывая суммарный трафик сети, а так же вычислительную загрузку отдельных узлов при помощи генетического алгоритма).

4. Моделирование ВС на основе прогнозных значений трафика.

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

* Построение модели нечетких тенденций динамики трафика, моделирование и прогнозирование эксплуатационных характеристик ВС.

Разработка П-модели для проектирования

Для вычислительного эксперимента была выбрана ВС ФГУП НПО «Марс» на одном из этапов ее развития. Она состоит из сегмента конструкторов, сегмента технологического и нормоконтроля, сегмента технологов и сегмента архива. В сеть объединены отделы, связанные прежде всего с разработкой программного обеспечения, конструкторские, технологические отделы, отделы программистов и разработчиков, а также менеджеры по управлению этими подразделениями. Основой для ВС на глобальном уровне служит движение электронной инженерно-технической документации. На уровне подразделений сеть служит для распределенного ведения комплексных проектов различного оборудования, а также проектов программного обеспечения. Кроме этого, на уровне подразделений сеть позволяет вести централизованную распечатку документов. Основные прикладные агенты: сервера и клиенты описываются с помощью интерфейсного блока в форме сетей Петри, а их взаимодействие - с помощью DFD-диаграмм.

Если САПР ВС использована в режиме модернизации сети, а не проектирования с нуля, то результатом оптимизации транспортной схемы ВС будет перечень рекомендаций по модернизации сети.

Формирование ТП-модели. Слияние модели прикладных процессов (П-модель) и транспортной модели сети (Т-модель) в обобщенную модель ТП-модель.

...