Название: Автоматизированное проектирование вычислительных сетей крупных проектных организаций(Стецко А.А.)

Жанр: Информационные системы и технологии

Просмотров: 1347


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

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

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

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

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

нятию четкого гиперграфа. Пусть V = {vi }, i ∈ I{1,2,3,..., n} – коне чное множе -

ство и E = {e~}, j ∈ J = {1,2,..., m} – семейство нечетких подмножеств в V .

Пара ~ = {V , E}

H

 
~ называется нечетким неориентированным гипергра-~

фом, если е j  ≠ ∅, j∈  J и ∪  е j  = Vj∈J , где элементы v1 , v2 ,..., vn  ∈V являются

вершинами гиперграфа, множество  E , состоящее из нечетких ребер гиперграфа.~

1      2           m

 
~е ,~е  ,...е~  – множество

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

нечеткий мультигиперграф.Степень принадлежности вершины vi~

е

 
ребру ~ j называется степенью инци-

дентности вершины vi и ребра е j , и обозначается µ~

е

 
j (v j ) .

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

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

реднение может быть представлено вычислением среднего значения Bij , или

построением  на  основе  гистограммы  распределения  вероятностей,  или  по-строением функции принадлежности на основе распределения возможностей.Суммарный трафик, приходящийся на канал связи, зависит от типа канала.Рассмотрим на Топ-уровне только каналы типа <коммутатор/концентратор> ----- <коммутатор/концентратор>. Тогда      можно выделить следующие подвиды каналов:<коммутатор > -----            <коммутатор>;<концентратор>  -----          < концентратор>;<коммутатор >    -----      < концентратор>.Суммарный трафик выражается по-разному для 3-х подвидов каналов связи. Для суммарного трафика канала типа <коммутатор >  -----<коммутатор> справедлива формула:n          nTk  =  ∑ ∑ Biji∈M1  j∈M 2Множество вершин М1 и множество вершин M2 - это множества узлов по одну и другую стороны от канала связи.Суммарный трафик канала <концентратор> ----- < концентратор> изме-ряется по-другому, так как канал, образованный концентраторами, образует общую магистраль:n      n

Tk   = ∑         ∑ Biji =1,i ≠ j j =1,i ≠ j

Суммарный трафик канала  <концентратор> ----- <коммутатор>           может быть вычислен следующим образом:n       nTk  =  ∑ ∑ Biji∈M1  j =1,i ≠ j

Необходимость модификации (перепроектирования) ВС определяется по степени близости суммарного трафика и пропускных способностей каналов связи.При построении Тр-уровня Т-модели основной задачей является построе- ние переменной, значения которой могут быть либо измерены, либо выражены лингвистически в форме словесной экспертной оценки. Поэтому использование в качестве формы представления трафика либо вероятностной величины, либо лингвистической переменной недостаточно. Модель трафика ВС в Т-модели представляет собой нечеткую случайную величину (НСВ), которая имеет вид:Tr   = {A1 / P1 , A2  / P2 ,..., An  / Pn } ,

где A1 , A2 ,..., An – нечеткие значения, которые величина Tr принимает с вероят-

ностями P1 , P2 ,..., Pn , ∑ Pi  = 1 .i

Поскольку  при  проектировании ВС  специалист  прогнозирует трафик  в

лингвистической форме, набор вероятностей Pi    можно также выражать с по-

мощью слов. Для этого вводится понятие «степень уверенности НСВ». Каждый вектор вероятностей кодирует степень уверенности НСВ, которая представляет собой лингвистическую оценку вида «точно», «скорее всего» («скорее»), «на- верное» («возможно»). Каждую такую оценку можно представить в виде функ- ции распределения НСВ.Каждый процесс в функциональной модели ВС рассматривается как гене-ратор сетевого трафика с величиной, заданной словесной оценкой.  На рассмат-риваемом интервале времени значение трафика распределяется в соответствии с мерой возможности оценки его значения. Например, оценка «скорее высокий» расшифровывается как НСВ {«низкий»/0, «средний»/0.25, «высокий»/0.75}. На рис. 1 показано распределение значения трафика в интервале времени.Tr, (лингв.)высокий среднийнизкийt’1     t’2  t’3     t’4          t’5     t’6                      t t1                               t2Рис. 1. Распределение значения трафика по времениПоскольку каждый канал в сети рассматривается как отдельное обслужи-

λ

 
вающее устройство, обозначим через        i среднее число сообщений в секунду,

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

λ

 

i

 
через   ~ нечетко заданное среднее число сообщений в секунду, проходящих по

i-му каналу. Тогда полный трафик в ВС является НСВM

~

 
λ  =  ∑ λ i   ,i =1где сложение означает сложение НСВ.Результат сложения двух операндов, выраженных НСВ, рассматривается как объединение трапециевидных нечетких интервалов параметров узлов и ка-

налов. Каждый из этих нечетких интервалов М i представлен пятеркой:

M i  = (mi , mi ,α i , βi , hi ) ,

где mi   – нижнее модальное значение нечеткого интервала Mi ;

mi – верхнее модальное значение нечеткого интервалаαi – левый коэффициент нечеткости; Mi ;

βi  – правый коэффициент нечеткости;hi  – высота нечеткого интервала.

Нечеткая величина M i  + M j , где M i , M j – два трапециевидных нечётких

интервала, есть также трапециевидный нечеткий интервал

⎛ β      β (m , m , α⎞ , β , h ) , где h = min(hi , h j ) ;

β = h⎜      i  + j  ⎟ ; m = m + m − α  − α + a;  m = m + m − β  − β + β .

⎜  h     h  ⎟      i      j           i           j      i      j           i           j

⎝         i           j  ⎠Топ-уровень и Тр-уровень для Т-модели определяют структуру и трафик ВС, но для моделирования передачи трафика необходимо адекватно предста- вить уровень маршрутизации (М-уровень).  Маршрут P  в распределенной ВС, которая представлена нечетким гиперграфом G = {V,E,с}, определен как неко- торый (v,w) путь:Е1  Е2        Екv = V0 ⎯⎯→V1 ⎯⎯→... ⎯⎯→Vк  = wВ территориально распределенных ВС существуют факторы, которыепри различных условиях оказывают влияние на параметры узлов маршрутиза-ции и каналов передачи данных. Факторы являются непостоянными и могут изменяться. Параметрические данные, которые изменяются под влиянием дан- ных факторов, используются для определения метрики в протоколах маршру-

тизации. Длина пути Р может быть определена на основе метрик с,  как величинаc(P):

c(P)=c(E1)+ c(E2)+…+ c(Eк).Если для        узлов маршрутизации определены следующие метрики: Pr    -

пропускная способность маршрутизатора; Z r - задержка при передаче; Sr - ста-

бильность работы, а канал характеризуется метриками: Pk    - пропускная спо-

собность канала; Sk - стабильность работы; Z k   - задержка, то оценки

узла и канала, как элементов маршрута, определяют следующие формулы:.

= ω      1  + ω  + ω = ϖ      1  + ϖ  + ϖ

Z

 
Ok       1k 2 S k 3 Pk , Or

1

 
Z r 2 S r 3 Pr

где ω1 , ω2,ω3 ϖ 1 ,ϖ 2 ,ϖ 3 – коэффициенты на основе нечетких характеристик кана-

ла и узла. Для формирования интегральной оценки целесообразно использовать аддитивную свертку:

n

i

 
Op  = ∑ Ori=1 n−1

j

 
+ ∑ Ok    .j =1

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

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

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

структурой сети в свойства процесса добавлен IP-адрес того компьютера, на ко- тором этот процесс выполняется. Информация о диаграмме DFD хранится в классе «Блок диаграммы» (TBlockData): номер, названия задач, расписания ра- боты, присваиваемые IP-адреса и др. (рис. 3).Класс «Блок диаграммы» (TBlockData) Номер блока (Block Number) Название задачи (TaskName)IP-адрес узла (IPaddress)Расписание работы блока (Schedule) Сетевая загрузка (Traffic) Вычислительная загрузка (Loading)Рис. 3. Атрибуты узла модифицированной DFD-диаграммы.Так как разработанная П-модель прикладных процессов ВС служит не только для решения задач собственно моделирования сети, но также  является основой для построения средства автоматизации проектирования, то для разра- ботанной П-модели адаптирован известный интеллектуальный метод принятия проектных решений – байесовская оптимизация. Для адаптации необходимо построить граф байесовской сети доверия (БСД).БСД для решения задачи оптимизации ВС состоит из четырех слоев: слой взаимодействий, слой интенсивности трафика, слой внутрисегментных и меж- сегментных трафиков, слой согласования Т-модели и П-модели. Рассмотрим кратко функции каждого слоя БСД.Слой 1 – слой взаимодействий. Данный слой вводит в БСД начальные данные об интенсивностях взаимодействия компьютеров ВС между собой наосновании информации об автоматизируемых производственных процессах, описанных на языке DFD-диаграмм. Величина интенсивности взаимодействия является  нечёткой,  так  как  передаваемый  трафик  состоит  из  документов,имеющих четкий размер, и запросов к базам данных, имеющих нечеткий раз-мер.Слой 2 – слой интенсивности трафика. На данном слое происходит группировка информации об интенсивностях взаимодействия компьютеров по каналам сети, через которые проходят взаимодействия.Слой 3 – слой внутрисегментных и межсегментных трафиков. На дан- ном уровне определяется интенсивность внутрисегментных и межсегментных взаимодействий для каждого узла сети. Каждый узел сети образует сегмент. Для каждого узла сети в данном слое существуют два узла БСД – на одном формируется внутрисегментный трафик, на другом – межсегментный трафик. Трафик формируется по принципу протекания через сегмент или внутри него.

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

1. Разработка П-модели для проектирования, то есть описание при- кладных задач проектируемой вычислительной сети. На этом этапе со- ставляется модель потоков данных проектируемой сети без привязки к транспортной структуре сети. Этот этап является важнейшим в предла- гаемом методе проектирования ВС, так как правильно составленная диаграмма процессов, происходящих в сети, является основой для даль- нейшей разработки ВС.2.  Разработка Т-модели для проектирования, то есть описание транс-портной схемы,  структуры ВС. На этом этапе проектировщик описыва-ет саму ВС на уровне узлов сети и каналов связи. Здесь устанавливают- ся взаимосвязи узлов сети через коммутирующие модули, или маршру- тизаторы, расставляются серверы. Для каждого узла сети задается таб- лица маршрутизации. Фактически моделируется процесс составления и настройки реальной локальной сети.3.  Формирование ТП-модели. На этом этапе производится слияние моде-ли прикладных процессов (П-модель) и транспортной  модели сети (Т- модель) в обобщенную модель (ТП-модель) и моделирование ВС на ос- нове прогнозных значений трафика, представленного временным рядом нечетких тенденций. САПР ВС автоматически расставляет блоки диа- граммы прикладных процессов, учитывая суммарный трафик сети, а так же вычислительную загрузку отдельных узлов. При помощи генетиче- ского алгоритма система находит оптимальный вариант наложения со- ставленной схемы прикладных процессов на спроектированную ВС.4.  Модификация. Заключается во внесении изменений в Т-модель.Этапы модификации и оптимизации могут повторяться несколько раз, до тех пор, пока полученная система не будет удовлетворять всем требованиямпроектировщика. При формировании описания прикладных процессов устанав-ливаются расписания работы процессов, генерируются прогнозные временные ряды трафика на основе нечетких тенденций.Окончательная цель    автоматизированного           проектирования            ВС       –формирование обобщенной модели сети (ТП-модели). После того, как модель прикладных процессов и предполагаемая модель сети составлены, необходимопостроить их взаимосвязь. Это осуществляется путем распределения блоков диаграммы (DFD) по транспортной структуре проектируемой сети. Фактическивременно выстраивается проектный вариант обобщенной модели сети (ТП- модели). За поиск наилучшего варианта этого распределения отвечает генети- ческий алгоритм.Целевая функция генетического алгоритма состоит из 3-х частей. Перваячасть функции стремится к уменьшению суммарного трафика в системе. Вто- рая часть стремится к тому, чтобы максимальная вычислительная загрузка од- ного узла была наименьшей. Третья часть целевой функции отвечает за качест- во группировки блоков диаграммы прикладных процессов по подсетям.F= Fтрафик + Fвыч.загрузка +Fгруппировка

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

Определение 1. Нечеткая тенденция (НТ). Пусть ~y        = {~y ,..., ~y  } – не-

∆          1          m~четкий       временной     ряд      лингвистической      переменной   ( Y ,Ty ,U y , Gy , M y ),

Y

 

 
~  = {~y } – множество нечетких временных рядов одинаковой длины. Тогда

~

 
~

 

 
нечеткая тенденция τ, определенная на Y∆ , есть совокупность упорядоченных

пар τ = {~y∆к НТ. , µτ ( ~y )}, где µτ ( ~y  ) представляет собой степень принадлежности y∆

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

как (τ ,{τ i }, ~ , G , M ) , i=1..p, где p – количество видов НТ, определенных на

Y∆       τ           τ~

ВР; Y∆ - множество НВР переменной длины.

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

t m+1            t

 

y

 

t

 
Определение  2.  Временной  ряд  нечеткой  тенденции  (ВРНТ).  Пусть

{y

 

}

 
~∆t – множество нечетких временных рядов длиной m, где ~          = {~y ,..., ~y },

~          ~

( y

 
yt  ∈ Y t. Тогда временной ряд нечеткой тенденции  есть упорядоченное во вре-

мени нечеткое множество: τ t = {t, µτ ~∆t )} .

Для лингвистической переменной «тенденция» временной ряд определяет-ся совокупностью значений всех видов нечетких тенденций:τ  = {t,τ 1 ,...,τ p }.t     t           tДелая предположение о состоянии системы, зависящем от предыдущих со- стояний, предполагаем наличие зависимости НТ от значений тенденций в пре- дыдущие моменты времени.Моделью нечетких тенденций (МНТ) с характеризующими параметрами

t

 
(n, p, m, l) обозначим совокупность компонент и уравнений:

y

 

i

 
~t   = Fuzzy[ yt ] , y't = deFuzzy[ ~y ' ],

τ

 

t

 
j  = Tend[ ~y t −m  +1 ,..., ~yt ] ,

j

 

t

 

t

 
~y 'i = deTend[τ ,...,τ t +m−1 ],

τ t  = f (τ t −1 ,...τ t −l ) , i = 1..n , j = 1.. p , m = max(m j ) ,

где ~y  = {~y i } – НВР, n – количество термов НВР, Fuzzy – функционал фаззифи-

t           tкации;

τ  = {τ j } – ВРНТ, p – количество термов НТ, m – интервал определения

t           t           jНТ, Tend – функционал распознавания НТ;

t

 
f – функциональная зависимость, l – временной лаг;

t

 
~y ' = {~y 'i } – НВР, полученный из ВРНТ, deTend – функционал получения

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

t

 
~y ' – дефаззифицированный ВР, deFuzzy – функционал получения четкого

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

EНВР = ( yt − deFuzzy(Fuzzy( y )))2 = ( yt − y′ )2 .

t

 

t

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

E          = ( ~y i  − deTend(Tend ( ~y )))2 = ( ~y i  − ~y 'i ) 2 .

НТ       t t           t           t

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

EВР = ( yt − deFuzzy(deTend(Tend(Fuzzy( y )))))2  =

t

 

t

 
= (yt − y′)2

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

ВР:τ t  = f (τ t −a ,...τ t −l ) ⇒  yt  = f ' ' ( yt +m−a−1 ,..., yt −m−l +1 ).

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

:           τ  = {τ i  = mj(       (~a(i, j,k ) ))}.

R1       t t           S Tj      k =1 yt −k +1

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

t

 

tk

 

t

 
R2 : τ  = {τ i  = S (Tj    k =1 (τ c(i, j,k ) ))}.

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

R3 : ~ = {~y k p= S

y

 

t

 

t

 
i=1 mi(  Sj=1,

τ

 
it + j−1 )}.

b(i, j )=kТаким образом, МНТ полностью реализуется многоуровневой системой

логических отношений: R1  ⇒ R2  ⇒ R3 , где выходы в виде нечетких перемен-

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

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

Блок имитационного моделирования на осно- ве сетей Петри библиотека функциональных моде- лей прикладных агентов блок имитационного моделирования на осно- ве временных рядов не- четких тенденций Интерфейсный блокВвод исходных данных П-моделиВвод исходных данных Т-модели Оптимизация:блок байесовской оп-тимизацииблок генетической оп-тимизации

Блок моделирования маршрутизации Блок согласования прикладной процессной и транспортной схем (формирование ТП-модели)

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

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