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

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

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

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

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

метеорологические условия, нестандартные ситуации.Следовательно, необходимо вводить в  систему проектирования КСописание характеристик, которые влияют на прохождения пакетов в сети, что позволит даже на основании прогнозных данных вырабатывать оптимальные решения.Перечисленные аспекты проблемы проектирования КС делают тему диссертационной работы актуальной.Цель диссертационной работыЦелью диссертации является исследование применимости теории нечетких гиперграфов к задачам автоматизированного проектирования КС, разработка методов, моделей и алгоритмов, позволяющих повысить качество автоматизированного проектирования в условиях неопределенности, построение программной системы моделирования маршрутизации и разработки проектных решений КС с использованием нечетких метрик, позволяющей эффективно оптимизировать загрузку существующих КС.Задачи исследованияДля достижения поставленной цели необходимо решить ряд задач:1.  Провести            сравнительный          анализ существующих          систем моделирования методов маршрутизации КС;2.  Разработать средства представления структуры КС  на  основенечетких гиперграфов;3.  Построить методику учета нечетких метрик;4.  Разработать модель трафика КС;5.  Сформировать        алгоритм            маршрутизации         с          использованием нечетких гиперграфов и нечетких метрик;6.  Разработать    и          реализовать    программу     автоматизированного проектирования КС на основе предварительного моделированиямаршрутизации.Методы исследованияСовременная теория неопределенности, неточности и нечеткости; теория  вероятностей;  теория  графов,  теория  имитационного моделирования.Научная новизна диссертационной работы заключается в следующем:1.  Впервые построена модель КС на основе нечетких гиперграфов;2. Предложена методика расширения протоколов маршрутизации, отличающаяся от известных   использованием нечетких   метрик характеристик элементов сети;3. Разработан новый алгоритм моделирования роутинга для КС с использованием        нечетких   прогнозных   данных   о   трафике   и вычислительной загрузке сети;

4. Сформулирована  новая  методика  использования  результатов моделирования   маршрутизации      при       автоматизированном проектировании вычислительной сети.Достоверность результатов диссертационной работы.Достоверность научных положений, выводов и рекомендаций подтверждена результатами экспериментов, а также результатами использования материалов диссертации и разработанной системы в проектной организации.Основные положения, выносимые на защиту1. Модель КС, построенная на основе теории нечетких гиперграфов, которая позволяет оперировать прогнозными данными о трафике и вычислительной загрузке сети;2. Методика расширения протоколов маршрутизации, использующая нечеткие         метрики    характеристик    элементов    сети,    которая эффективно управляет трафиком в КС;3.  Алгоритм       поиска            пути    с          использованием        нечетких        метрик,применимый для маршрутизации КС;4.  Методика использования результатов САПР КС на основе нечетких гиперграфов,  позволяющая  эффективно  оптимизировать  загрузкусуществующих КС.Практическая значимость работыСозданная система автоматизированного проектирования КС используется в производстве и позволяет эффективно перераспределять высокоприоритетный трафик путем применения  предлагаемых методик и автоматической оптимизации,  а так же сократить время, затрачиваемое на проектирование КС.Реализация результатов работыРезультаты диссертации и практические рекомендации использованы при переконфигурации маршрутизаторов сегментов КС ГУ ЦБ РФ по Ульяновской области (г. Ульяновск 2005 г.), при проведении процессов проектирования сетей и обучения сетевым технологиям в АНО “Образовательный Центр Сетевых Технологий Диамонда” (г. Москва 2006 г.), в Федеральном научно производственном центре ОАО НПО “МАРС” ( г. Ульяновск 2006 г.).Апробация работыОсновные положения и результаты диссертации докладывались, обсуждались   и получили одобрение на международной конференции “Континуальные логико-алгебраические и нейросетевые методы в науке, технике и экономике” (г. Ульяновск, УлГТУ, 2000 г.), 4-й международной конференции “Интерактивные системы” (г. Ульяновск, УлГТУ, 2001 г.),

научно-технической конференции УлГТУ. "Вузовская наука  в современных условиях” (г. Ульяновск, УлГТУ, 2001, 2003, 2005, 2006 г.г.), научных сессиях МИФИ (г. Москва, МИФИ 2002, 2003 г.г.), на 2-ом Международном  научно-практическом  семинаре  "Интегрированные модели и мягкие вычисления в искусственном интеллекте". (г. Коломна, РАИИ ,РАНС 2003 г.), международной научно-технической конференции IEEE AIS’04, CAD-2004 “Интеллектуальные системы”, “Интеллектуальные САПР” (г. Двиноморское 2004 г.), 34-ом международном салоне изобретений, новой техники и товаров "Женева-2006" (г. Женева, Швейцария, 2006 г.).Публикация результатов работы.По теме диссертации опубликовано 12 работ.Личный вклад.Все результаты, составляющие содержание диссертации, получены автором самостоятельно.Структура и объем работыДиссертационная работа состоит из введения, четырех глав и заключения, содержит 267 страниц машинописного текста, 35 таблиц, 36 рисунков, список литературы из 137 наименования и 8 приложений.КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫВо введении рассмотрена актуальность проблемы проектирования современных распределенных КС, сформулированы объекты исследования и предмет исследования, излагаются цель и   соответствующие ей задачи работы.Первая глава «Обзор методов и средств автоматизированного проектирования       вычислительных       сетей»       посвящена       анализусуществующих моделей, систем автоматизации проектирования, методик и инструментов  для  моделирования  и   проектирования  вычислительных сетей. Изложено текущее состояние различных исследований, ведущихся вэтом   направлении.  Приведены   классификации  сетей,   определения  и свойства КС, принципы маршрутизации, алгоритмов построения путей в сетях и их эффективность.Рассматриваются     вопросы моделирования маршрутизации и оптимизации параметров, структуры и функциональности сетей, значимость показателей алгоритмов маршрутизации, обзор ведется по всем этим направлениям.Сделаны выводы о том, что использование пакетов различных классов позволяет строить адекватные модели современных систем и сетей в частности. Языки моделирования общего назначения обладают наиболееширокими  функциональными  возможностями  для  любых  предметных

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

            K1М1К2               K3М3 ε1        V7

MAN   WANМ2         М4 V3       V4       V5ε3   ε4

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

произвольные ребра могут иметь любое, в пределах данного числа вершин,количество нечетко инцидентных им вершин.Нечеткий ориентированный гиперграф можно рассматривать как произвольный набор нечетких подмножеств, определенных в одном множестве. Алгебраические операции являются операциями сравнения графовых представлений моделей КС. Использование такого подхода позволяет привлекать возможности теории графов для построения алгоритмов   принятия   решений   и   исследования   структуры   объектов, сетевых взаимодействий (описания маршрутов), представимых нечеткими гиперграфами.Для  решения  задачи  поиска  пути  в  графе  известны  алгоритмы,которые предложены Ахо А., Хопкрофтом Дж., Ульманом Дж.,         АсановымМ.О., Баранским В.А., Расиным В.В. , Кристофидесом Н.Среди предложенных механизмов были рассмотрены следующие алгоритмы поиска кратчайших путей в графах: алгоритм Беллмана-Форда,алгоритм Дейкстры, волновой алгоритм, алгоритм Флойда, Алгоритм ЙенаАлгоритм Крускала.Определено, что маршрут P  в распределенной КС, которая описана с помощью взвешенного графа G = {V,E,с}, представлен как   некоторый(v,w) путь:Е1   Е2        Екv = V0 ⎯⎯→V1 ⎯⎯→... ⎯⎯→Vк  = wДлина пути Р определена как c(P):c(P)=c(E1)+ c(E2)+…+ c(Eк).Для  поиска  пути  в  КС  предложено использование     алгоритма A1,который  находит  путь  минимальной  суммарной  длины  во  взвешенном графе с неотрицательными весами, описанный Асановым М.О., БаранскимВ.А., Расиным В.В.В  механизме  алгоритма  Дейкстры  используется  функция  Min(F),которая возвращает вершину w ∈  F, такую, что справедливо равенствоD[w] = min{D[v] | v ∈ F} , что является нахождением кратчайших путей отданной вершины-источника до всех остальных вершин, перебирая пути впорядке увеличения их длин.Вход  алгоритма:  сеть  G  =  {V,E,с}            заданная  матрицей  весов  Апорядка n; выделенная вершина s.Выход алгоритма: расстояния D[v] – расстояния s от всех вершинv∈V , где P[v] – предпоследняя вершина в кратчайшем (s,v) пути.В распределенных КС параметры узлов маршрутизации и каналовпередачи данных, используемые для определения метрики в протоколах маршрутизации,            являются        непостоянными         и          могут  изменяться.Появляется задача поиска оптимального пути в сети с нечетко заданными параметрами или множеством параметров. Поиск пути в распределенных КС происходит на любой стадии эксплуатации и проектирования путемприведения           к            минимизированному            виду    КС       в          форме объединения опорных  узлов  и  каналов  связи  между  ними.  Соответственно, каждый

канал новой сети может быть представлен  как канал связи, так и как подсеть, состоящая из отдельно взятых промежуточных узлов, связанных между  собой     каналами     связи.     При     объединении     структуры рассматриваемой      сети,   наглядно   вырисовывается   логическая   схема операторов связи в WAN сетях,   большинство   которых имеют связи со всеми остальными сетями.В описании объектов КС также появляются как четкие, так и нечеткие параметры. В процессе описания межсетевых процессов со стороны проектантов и администраторов КС появляются объективные и необъективные       параметры,   которые   описывают   передачу   трафика   и взаимодействие  межсетевых     процессов.  К  любой  составляющей  КС можно      применить   термин   как   “плохой   канал”,   “быстрая   линия”,“медленный маршрутизатор”, “хороший мультиплексор ” и т.д.Введены параметры,   относящиеся к узлам маршрутизации: Pr -пропускная способность маршрутизатора, Zr - задержка при передаче, Sr -стабильность работы  и  параметры, относящиеся к  каналам связи:  Pk  -пропускная способность канала, Sk - стабильность работы, Zk - задержка.Экспертом     описаны         лингвистические      переменные   с          7лексическими значениями. Рассмотрим описание  на примере переменной Sr,    определяющей факторы, влияющие на лексическое значение - перегрузка, нагрев, круглосуточный режим работы, погодные условия (Таб.1.)

Таб.1  Описание Sr1

Ok  = f1

нечеткие характеристики канала.1

нечеткие характеристики узла.Общая оценка пути вычисляется по формуле:

nOp  = ∑Orii =1 n −1+ ∑Ok jj =1

Каждая           нечёткая         величина Ori   и O  рассматривается   как

а'j         b'jhjMjhiMi     m'j

mi        miаi     bi m'j       m'jаj m'jbj

Рис. 2.  Формирование нечеткой метрикиКаждый из этих нечётких интервалов Mi представлен пятёркой:Mi  = (mi , mi ,αi , βi , hi ) , где

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

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

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

Нечёткая  величина  Mi+Mj,  где  Mi,  Mj  –  два  трапециевидных нечётких   интервала       (Рис.    2.)        есть            также  трапециевидный       нечёткий

интервал (m , m ,α , β , h ) ,           где       h          =          min(hi, hj); β =      ⎛  βi     β j ⎞

Pr         Zr       SrU Pr         Zr       SrU

OriOm 3KOkiU Ori UOki U Ori 1KOki U1ROri

Pk        Zk       Sк U4KPk            Zk       Sк       5R      U

6R       Pk        Zk       Sк5KРис. 3. Объединение нечетких интервалов ФПТаким образом, общей метрикой маршрута является объединение нечётких  величин  параметров  каналов  связи  и  узлов  маршрутизации,

которые          в          свою   очередь           представляют            собой  объединение  нечетких интервалов ФП каждой из локальных характеристик (Рис. 3).В  моменты  выбора  узла  с  наименьшей  накопленной  метрикой происходит дефаззификация и сравниваются два чётких числа (Рис. 4).

1h        x =  m1 + m2 + b2 2 − a 2

a          b

m1       X m2Рис. 4.        Дефаззификация

Нечеткий  ориентированный  гиперграф  первого  рода H~ = (V, D)

будет являться адекватной математической моделью маршрутных таблиц при моделирования процесса маршрутизации в КС, если   предположить, что множеству вершин V гиперграфа взаимно однозначно сопоставлено множество  активных   элементов  I   -   узлов   КС,   а   каждый   маршрутпрохождения по  элементам j∈J  представляет собой последовательностьпрохождения по  множеству I  и  соответствует ориентированному ребру

ориентированные графы G~(d ) = (V ,U~ ) , где

−          U~ = {< µ (v , v ) /(v , v ) >} - нечеткое множество ребер,

j           U j       i           k          i           k

где vi , vk ∈V ,

µ U  j для ребра (vi , vk ) .Значения функций при разбиении множества вершин V на части V1и V2 будут определяться следующим образом:

ϕ P       = ⎧ µ U    ( v a , v β  )

j           ⎩ 0 в противном случае;

⎧1ψ     = ⎨ при ϕ Pj ≠ 0 ;

Pj         ⎩0 в противном случае;

Целевая функция выглядеть как ϕ (H~ ) разбиения множества V на V1  и V2          будет

m∑ϕ ( H~ ) = k j∑ ϕ P jj        .

j = 1 P   = 1

m∑j = 1 k j∑ ψ P jP j  = 1

При выполнении разбиения и минимизации целевой функции ϕ (H~ )происходит формирование групп активных элементов I в КС, для которыхможно определить оптимальный маршрут с предпочтительным временем обработки  внутри  выделяемой  группы.  Алгоритм  А1  используется  дляпоследовательного            выбора            наиболее        приемлемых  вершин           V,        по выбранному  критерию  для  включения  в  формируемую  группу  вершинϕ (H~ ) .Допустим, что некоторые вершины v∈V на шаге t алгоритма      уже

вошли  во  множество V t .  Для  произвольной  вершины  v ∈VV t будем

1          f           1использовать оценку ϕ(vf), такую же, как и определение целевой функцииϕ (H~ ) , но характеризующую разбиение гиперграфа  H~  при условии, чтовыделена группа вершин V t ∪{v }. В итоге получаем1      fm        k j

ϕ t ( v  ) = j = 1 Pj = 1 , где     (ф. 1.)

f           m         k j

j = 1 Pj = 1

⎧ µ U

j           ⎩ 0 ∨ (vβ  ∈V1 ∪ {v f }) & va ∈V ) (v1  ∪ {v f })

⎧1ψ     = ⎨ при ϕ Pj ≠ 0 ;

Pj         ⎩0 в противном случае;~           , Pj=1,2,3… kj,

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

вершину vv , для которойt   t

ϕ  (vv ) = min ϕt (v f ) . (ф. 2.)

v f ∈V V1Это позволяет утверждать, что на каждом шаге поиска формируетсянаилучшее - в смысле принятого выбранного критерия - подмножество элементов., а следовательно приводит к получению оптимального разбиения множества V на V1 и V2.  Первая вершина, помещаемая в V1, аналогично выбирается по ф. 2., при этом фактически берется вершина с наименьшим значением средней степени предпочтительности выходящихt

из  нее ребер. Значение величины ϕ  (vv ) вершины, помещаемой в  V1,

представляет  собой  значение  целевой  функции множества вершин V на V1 и V2. ϕ (H~ ) при  разбиении

Сформулируем алгоритм выделения множества V1  содержащего n1,вершин (Алгоритм А2.).

Таб. 2. - Алгоритм А2 выделения множества активных элементов в нечетком гиперграфеДля        выделения            следующей     группы           активных       элементов      I           из

множества  вершин  V  гиперграфа H~ = (V, D) производим  удаление  всех

вершин в гиперграфе H~  сформированной части V1, а к оставшейся частигиперграфа применяем алгоритм А2. Процедуру повторяем до тех пор,пока не будут сформированы все группы активных элементов.Третья глава «Структурно функциональное решение автоматизации проектирования Кѻ данной главе рассматривается практическая реализация системы моделирования КС с использование нечетких гиперграфов. Основное внимание уделяется описанию данных, позволяющим представить процессмаршрутизации в КС с использованием нечетко заданных параметров и использованию алгоритмов маршрутизации в распределенных КС. Обосновывается  выбор  инструментальных  средств  и  рассматриваютсянаправления дальнейшего развития системы.Система  подразделена  на  шесть  основных  блоков–  интерфейсный,

блок исходных данных, блок динамических данных, блок маршрутизации,блок алгоритмов и блок моделирования (Рис.5).

Модуль анализа и сохранения параметров Модуль установки элементов сети

Структура  исходных данных сетевых элементов  и сетевых связей Модуль описания сетевых компонентМодуль управления сетевыми компонентами Модуль визуализации Модуль журнализации

Блок исходных  данных Интерфейсный блок Модуль посылки пакетов в сети

Модуль формирования параметров узловМодуль формирования параметров каналов связиМодуль формирования моделей подсетейСтруктура  текущих данных сетевых элементов  и межсетевых связей Модуль установки параметров маршрутизацииБлок маршрутизацииАлгоритмы маршрутизации с четкими параметрамиБлок алгоритмов Модуль формирования таблиц маршрутизацииАлгоритм маршрутизации с нечеткими параметрами Модуль анализа прохождения пакетов в сетиМодуль формирования сетевого пакета

Блок динамических данных Рис.5. –