Модели, методы и алгоритмы повышения структурной надежности сетей передачи данных Балашова Татьяна Ивановна

Содержание к диссертации

Введение

1. Анализ проблемы структурной надежности сетей передачи данных 15

1.1 Топологический анализ надежности сетевых структур 20

1.2 Топологический синтез сетевых структур 27

1.3 Постановка задач и целей исследования 37

2 Анализ топологии сети по критериям надежности и стоимости 40

2.1 Математическая модель представления топологии сети передачи данных 40

2.2 Количественные показатели структурной надежности сети 44

2.3 Алгоритмы анализа структурной надежности СПД

2.3.1 Применение алгоритма Мура-Шеннона для определения вероятности связности сети 53

2.3.2 Алгоритм Штор-Вагнера для определения минимального разреза графа 57

2.3.3 Разработка метода анализа структурной надежности СПД на базе алгоритма Штор-Вагнера

2.4 Обеспечение структурной надежности СПД с учетом многообразия факторов, влияющих на их функционирование 65

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

2.6 Выводы по главе 75

3 Разработка и исследование эвристических алгоритмов решения задач синтеза топологии сетей передачи данных 77

3.1 Разработка эвристических алгоритмов в задачах синтеза топологий сетей большой размерности 77

3.1.1 Метод кодирования решения задачи синтеза топологии сети передачи данных 79

3.1.2 Описание эвристических алгоритмов в терминах задачи построения оптимальной топологии сети 82

3.1.3 Модификация эвристических алгоритмов в соответствии со спецификой решаемых задач 3.2 Разработка метода настройки параметров эвристических алгоритмов для решения задач построения оптимальных топологий СПД 97

3.3 Разработка и моделирование методов корректировки решений с целью получения допустимых вариантов топологий СПД 105

3.4 Разработка алгоритма формирования начального множества решений 108

3.5 Сравнительный анализ эффективности эвристических алгоритмов для решения задач синтеза оптимальной топологии сети по показателю надежности 114

3.6 Разработка алгоритма динамической перестройки топологии сети передачи данных при возникновении пиковых нагрузок на сеть 115

3.7 Выводы по главе 121

Практическая реализация разработанного метода анализа структурной надежности и синтеза оптимальных топологий СПД 122

4.1 Моделирование процессов построения оптимальных топологий сети с использованием картографического сервиса Mapbox на базе разработанного программного обеспечения 122

4.2 Применение разработанных методов к проектированию оптимальной топологии при модернизации СПД предприятия 133

4.3. Выводы по главе 140

Заключение 141

Библиографический список

• Топологический синтез сетевых структур
• Алгоритмы анализа структурной надежности СПД
• Описание эвристических алгоритмов в терминах задачи построения оптимальной топологии сети
• Применение разработанных методов к проектированию оптимальной топологии при модернизации СПД предприятия

Введение к работе

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

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

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

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

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

Фундаментальные положения по вопросам структурного проектирования СПД и анализа сетевой надежности приведены в работах российских и зарубежных ученых, таких, как Г.Ф. Янбых, К.И. Ивановой, В.Г. Олифера, А.В. Бутрименко, С.И. Самойленко, Ю.П. Зайченко, В.М. Вишневского, Э. Таненбаума, М. Шварца, М.В. Кульгина, А.В. Шмалько, В.К. Попкова, В.М. Гостева, М.Х. Прилуцкого, В.В. Крылова, Е.И. Литвака, И.А. Ушакова, Э. Мура, К. Шеннона, Р. Барлоу, Ф. Прошана и других авторов. С

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

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

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

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

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

1. Исследование и разработка методов анализа структурной надежности СПД.

2. Исследование и разработка методов повышения структурной надежности сетей.

3. Адаптация эвристических алгоритмов к решению задач построения оптимальных топологий сетей.

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

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

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

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

практической апробации и настройки разработанных алгоритмов применено моделирование с использованием разработанного программного обеспечения, реализованного на языке JAVA в среде Eclipse, и картографического сервиса Mapbox.

Объектом исследования является структурная надежность корпоративных территориально-распределенных магистральных сетей передачи данных.

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

Научная новизна диссертационной работы заключается в следующем:

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

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

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

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

Практическая значимость работы

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

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

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

Сведения о внедрении результатов

Результаты, полученные при выполнении диссертационной работы, были использованы при проектировании корпоративной мультисервисной СПД ЗАО «Производственное объединение «Оргхим»», подтверждены Актом о внедрении. Полученные теоретические результаты используются в учебном процессе кафедры «Информатика и системы управления» Нижегородского государственного технического университета им. Р.Е. Алексеева в дисциплинах «Надежность и качество АСОиУ», «Сетевые технологии», «Защита информации в сетях передачи данных» а также при выполнении магистерских исследований. Получены 3 свидетельства об официальной регистрации программы для ЭВМ – №2014661486 «Библиотека, реализующая методы оптимизации топологии сетей передачи данных», № 2014662031 «Программа анализа надежности сетевых структур по граф-модели», №2015617989 «Программный комплекс для многопоточной генерации сетевого трафика».

Работа выполнена при финансовой поддержке Министерства образования и науки РФ по федеральной целевой программе «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы», Соглашение о предоставлении субсидии №14.574.21.0034 от 17.06.2014 «Разработка и исследование технологий и программного обеспечения программно-конфигурируемых сетей с целью противодействия распределенным атакам типа «отказ в обслуживании» и перехвату данных», уникальный идентификатор ПНИ RFMEFI57414X0034.

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

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

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

3. Метод направленной настройки параметров эвристических
алгоритмов для адаптации к задачам синтеза оптимальных топологий СПД
по критериям надежности и стоимости. Эвристический метод формирования
начальной популяции топологий для повышения качества работы
эвристических алгоритмов при исследовании области допустимых решений.

4. Оценка эффективности модифицированного алгоритма отжига по
сравнению с генетическим и иммунным алгоритмами.

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на 5-й Российской мультиконференции по проблемам управления (МКПУ-2012) «Управление в технических, эргатических, организационных и сетевых системах» (Санкт-Петербург, 2012 г.), на Международных научно-технических конференциях «Информационные системы и технологии» г. Нижний Новгород, 2012 г., 2013 г., 2014 г., 2015 г.

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

Публикации

По результатам диссертационной работы опубликовано 18 работ, в том числе 6 работ в изданиях, рекомендованных ВАК, 9 работ в материалах международных конференций, получены 3 свидетельства о регистрации программ для ЭВМ.

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

Диссертационная работа изложена на 166 печатных листах, включает 46 рисунков и 6 таблиц, состоит из введения, 4 глав, заключения, библиографического списка из 142 наименований и 3 приложений.

Топологический синтез сетевых структур

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

Эффективное функционирование коммерческих, производственных и государственных структур в настоящее время во многом зависит от наличия современных средств телекоммуникаций [5]. Грамотно организованная корпоративная сеть становится залогом коммерческого успеха всего предприятия (эффективность управления компанией, по некоторым оценкам, на 70% зависит от полноты и своевременности предоставления информации)[44].

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

Главным требованием, предъявляемым к сети, является выполнение основной функции по обеспечению пользователей потенциальной возможностью доступа ко всем разделяемым ресурсам, объединенным этой сетью [5]. Классификация сетей передачи данных по размеру является наиболее распространенной, при этом в качестве критерия используется территориальная принадлежность, определяемая размером площади, на которой расположены входящие в сеть узлы. Построение территориально-распределенных сетей требует больших затрат, основную долю которых составляет стоимость каналообразующего оборудования и работы по его прокладке, стоимость коммутационного оборудования, а также эксплуатационные затраты, связанные с поддержанием в работоспособном состоянии территориально распределенной каналообразующей аппаратуры сети. В этой связи актуальны задачи проектирования оптимальной структуры сетей передачи данных.

Большое число работ, обусловленное актуальностью проблемы качества проектирования сетей связи, посвящено вопросам построения архитектуры, выбора оборудования и определения топологии сетей передачи данных. В работе [24] рассматривается общая организация, методы и средства эффективного построения и эксплуатации информационно-вычислительных телекоммуникационных сетей. В работах [112-117] рассмотрены вопросы планирования и построения цифровых сетей связи на основе современных сетевых технологий, предлагаются практические рекомендации по выбору архитектуры, разработке топологии, применению оптических кабелей, подбору аппаратуры цифровых систем передачи и организации современных цифровых сетей связи.

Постоянно растущая сложность и размерность телекоммуникационных сетей, увеличение нагрузки на них в связи с увеличением объема передаваемого трафика, заставляет обратить внимание на качество выполнения процесса проектирования с целью получения оптимальной топологии сети [61–63].

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

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

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

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

Алгоритмы анализа структурной надежности СПД

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

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

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

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

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

Внести в топологию сети дополнительное множество каналов связи Еopt , обеспечивающего максимизацию показателя надежности, при наличии ограничений на стоимость их реализации: R(G(V, Е),Р) - функция, характеризующая структурную надежность сети, вычисляемая по формуле полной вероятности, где G(V,E) - граф, построенный на V вершинах и Е ребрах, Е={Єі,е2, ...,ет} - исходное множество ребер в граф-модели сети, Е ={ет+і, ...,em+k}- добавляемое множество ребер в граф-модели, Е - недопустимое множество ребер в граф-модели, ЕР - оптимальное множество ребер добавляемое в граф-модель по заданному критерию, Р={рьР2, —,Рт,Рт+ь —,Рт+к} - множество вероятностных характеристик ребер, R3ad. - заданное значение показателя надежности сети, Стал - максимально допустимая стоимость реализации сети, deg(vi) - степень исхода дуг из вершины v, (узла связи), MinCut(G) - количество минимальных разрезов граф-модели сети, для вычисления которого используется разработанный алгоритм анализа структурной надежности на базе алгоритма Штор-Вагнера, который будем называть методом минимальных разрезов СПД, R (G(V, Е),Р) - функция, характеризующая структурную надежность сети, учитывающая все множество минимальных разрезов граф-модели сети и их характеристики, где G(V,E) - граф, построенный на V вершинах и Е ребрах, Е пЕ =0 - условие, означающее что множество добавляемых ребер в граф-модель не должно содержать ребра, входящие в множество ребер недопустимых к реализации.

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

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

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

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

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

Описание эвристических алгоритмов в терминах задачи построения оптимальной топологии сети

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

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

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

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

Топология сети, принадлежащая множеству допустимых решений, начиная от минимально связной структуры до полносвязного графа, имеет количество ребер, лежащее в диапазоне от L=(n-1) до H=(n (n-1)/2), где n -число узлов сети. Если количество ребер в топологии менее, чем (n-1), то решение, описывающее топологию, является несвязной сетью. Количество ребер, образующих кратчайший путь в графе, называется расстоянием между узлами коммуникационной сети, максимальное расстояние между двумя узлами называется диаметром. Диаметр полносвязной топологии равен 1. Значения L=(n-1) и H=(n (n-1)/2) являются нижней и верхней границами диапазона мощности множества ребер, образующих решение – [L;H].

Приведем пример оценки размерности области допустимых решений в предположении отсутствия ограничений, накладываемых на структуру топологии сети, для графа, построенного на n=10 вершинах (рис.3.11). Количество ребер в каждом их графов, включая несвязные структуры, находится в диапазоне от 1 до H=n (n-1)/2, количество ребер связных топологий меняется в пределах от 9 до 45 (для полносвязной топологии). Мощность множества всех возможных топологий равна 2H, и, например, количество топологий графов с 1 ребром равно

В качестве механизма генерации решений на каждом этапе будем использовать классический метод имитации отжига. Пусть на первом этапе значение мощности ребер Ne=(Н+L)/2. На всем протяжении этапа значение Ne будет неизменным. При получении решения, удовлетворяющего накладываемому условию надежности, значение Ne должно быть уменьшено до величины (Ne+L)/2. В случае, если на текущем этапе не было получено ни одного допустимого решения (с точки зрения надежности), то уточним область поиска допустимых решений, присвоив L текущее значение Ne, и выполним переход алгоритма к состоянию со значением Ne=( Ne+H)/2. Пример изменения нижней L и верхней H границ диапазона мощности множества ребер, образующих допустимое решение представлен на рисунке 1. Если найдено решение с допустимым значением надежности. 2. Если в течении Imax итераций не было найдено ни одного допустимого решения. На всем протяжении выполнения этапа генерируемые решения будут иметь фиксированное значение характеристики Ne, которое меняется при переходе на следующий этап, при этом все структурные компоненты алгоритма (используемый закон изменения температуры, функция вероятности принятия и функция поиска решения) будут оставаться неизменными.

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

Результаты моделирования для топологий, построенных на 10-50 вершинах приведены на рисунке 3.13. Модифицированный метод отжига для топологий, построенных на количестве до 20 узлов имеет значительно большую эффективность по сравнению с классическим настроенным методом отжига.

Применение разработанных методов к проектированию оптимальной топологии при модернизации СПД предприятия

Для качественного и непрерывного функционирования всех уровней управления предприятия требуется создание каналов непрерывного обмена данными между этими уровнями, что делает необходимым наличие физических каналов связи как внутри уровней, так и между уровнями. Оптимизации топологии расположения физических каналов и посвящена данная работа. Здесь структурированная кабельная система, являющаяся основой производственного сегмента сети, это некий физический уровень нахождения всех систем. Т.е. создается единая платформа для уровня АСУТП, MES, ERP и BI. Поэтому задача оптимизации СКС выходит на первый план.

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

При модернизации производства были пересмотрены подходы к построению СКС, а именно критерии надежности и отказоустойчивости сети были выдвинуты на первый план. Топологическая схема завода после его модернизации была построена с учетом центров концентрации сетевого оборудования, представленных на рисунке 4.14. Рис. 4.14 – Топологическая схема завода после его модернизации с выделением узлов концентрации сетевого оборудования 137 Результат модернизации предприятия представлен на рисунке 4.15, где синими кружками указаны узлы, участвующие в технологическом процессе.

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

До модернизации СПД предприятия структурная надежность сети оценивалась 6-ю минимальными разрезами размерностью 1, т.е. в соответствие формуле (5) Ns=6, s=1, и при значении вероятности безотказной работы канала связи p=0,99 показатель вероятности связности сети был равен R=1-6(0,01)1=0,94. После модернизации СПД предприятия структурная надежность сети оценивается одним минимальным разрезом размерностью 2, т.е. Ns=1, s=2. При том же значении вероятности безотказной работы канала связи p=0,99 вероятность связности граф-модели СПД предприятия, вычисленная по формуле (5), стала равна R= 1- 1(0,01)2=0,9999. Таким образом, вероятность связности СПД повысилась более, чем на 6%.

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

Работа выполнена при финансовой поддержке Министерства образования и науки РФ (Соглашение о предоставлении субсидии №14.574.21.0034 от 17.06.2014, уникальный идентификатор ПНИ RFMEFI57414X0034) [82,83] .