Обеспечение отказоустойчивости сети повышением надежности её топологии

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы естественных и точных наук


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 7
ОБЕСПЕЧЕНИЕ ОТКАЗОУСТОЙЧИВОСТИ СЕТИ ПОВЫШЕНИЕМ НАДЕЖНОСТИ ЕЁ ТОПОЛОГИИ
Балашова Т. И. 1
1 ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева», Нижний
Новгород, Россия (603 950, г. Нижний Новгород, ГСП-41, ул. Минина, д. 24), e-mail: tibalashova@mail. ru_
Предлагается метод построения оптимальной топологии сети передачи данных по критериям надежности при наличии ограничений, основанный на применении алгоритмов эволюционного моделирования. В качестве показателей надежности используются минимальная степень исхода дуг из любой вершины, минимальное сечение, вероятность связности графа, количество минимальных сечений граф-модели сети. Выполнена адаптация генетического алгоритма, настройка его операторов для решения задач внесения избыточности в виде дополнительных каналов связи и определения оптимальной топологии сети. Топология представляется граф-моделью, которая в генетическом алгоритме кодируется битовой строкой с ненулевыми элементами, соответствующими каналам связи. Данный подход направлен на решение задач построения отказоустойчивых сетей, в том числе устойчивых к воздействию распределенных атак типа «отказ в обслуживании», направленных на заполнение канала передачи данных, эффективен при решении задач балансировки нагрузки.
Ключевые слова: сети передачи данных, надежность, топология, количественные оценки надежности, генетический алгоритм.
NETWORK FAULT TOLERANCE ENSURING BY INCREASING OF ITS TOPOLOGY RELIABILITY
Balashova T.I. 1
1 & quot-Nizhny Novgorod State Technical University n.a. R.E. Alekseev& quot- Nizhny Novgorod, Russia (603 950, Nizhny
Novgorod, streetMinin, 24), e-mail: tibalashova@mail. ru_
The method of the optimal network topology development considering reliability criteria with certain restrictions based on evolutionary computation algorithms is proposed. The minimum degree of a vertex, the minimum graph cut, the graph connectivity probability, the number of minimum network graph-model cuts are used as a reliability indicators. The genetic algorithm adaptation, its operators tuning are performed to solve the problems of redundancy introduction in the form of additional communication channels and optimal network topology determination. The topology is represented as a graph model which is coded in genetic algorithm in the bit string with nonzero elements corresponding to a communication channel. This approach aims at solving of fault-tolerant networks development problems including the networks resistant to the & quot-Denial of service& quot- attacks, which aim to the communication channel flood- it is effective in the problem of load balancing solving.
Keywords: network, reliability, topology, quantitative reliability estimations, genetic algorithm.
Современный этап развития территориально распределённых сетей передачи данных характеризуется ростом сложности и масштабов инфраструктур, непрерывным повышением требований к качеству предоставляемых услуг связи, доступа к сервисам. Сеть передачи данных должна быть экономически эффективной, и при ее проектировании или модернизации должно быть выполнено соответствующее обоснование и предоставлены расчеты по обеспечению надежности. К надежности сетей предъявляются все более высокие требования. Низкая надежность приводит к потере клиентов, убыткам и штрафным санкциям. Повышение надежности сети связано с дополнительными затратами, которые могут превысить прибыль, получаемую от предоставления инфокоммуникационных услуг
[6]. В этой связи актуальна задача достижения требуемых характеристик надежности при проектировании или модернизации сети при минимально возможных затратах на ее обеспечение.
Необходимость надежного планирования телекоммуникационных сетей (ТС) подчеркивается в принятой еще в 1988 г. и пересмотренной уже в 1992 г. рекомендации Международного телекоммуникационного союза «Надежность планирования телекоммуникационных сетей» [5].
Под термином «надежность» понимается свойство сети сохранять во времени в установленных пределах значения всех параметров, характеризующих способность выполнять требуемые функции в заданных режимах и условиях использования [2]. Характеристики надежности сети должны обеспечивать клиентам возможность обмениваться информацией и получать сервисы в условиях технических отказов, эксплуатационных ошибок, а также с учетом возможных угроз и рисков, связанных с атаками типа «отказ в обслуживании».
Надежность сети обеспечивается применением надежного оборудования и внесением избыточности в структуру сети для повышения готовности сети, т. е. обеспечения ее отказоустойчивости [3]. Комплексное решение задач обеспечения надежности включает оба направления — обеспечение аппаратной и структурной надежности. В первом случае решается проблема обеспечения надежности элементов сети — сетевого оборудования, каналов передачи данных, программного обеспечения. Структурная надежность обеспечивает функции сети, связанные с передачей данных. Для анализа структурной надежности используются показатели связности граф-моделей сети. Нарушить связность может как отказ аппаратуры в узлах сети, так и отказ каналов передачи данных. При этом отказ канала может быть связан как с его механическим повреждением (обрывом), так и с ухудшением его характеристик, в том числе превышением его пропускной способности. Для обеспечения связности сети применяются отказоустойчивые сетевые технологии, связанные с введением избыточности реализацией обходных путей передачи информации, и применением протоколов, например БТР, автоматически обеспечивающих обход отказавшего участка. Внесение избыточности в топологию корпоративных сетей позволяет повысить надежность маршрутизации больших объемов трафика, обеспечив связность с максимальным числом внешних сетей.
В настоящее время опубликовано большое число работ, в которых рассматриваются вопросы оценки надежности сетей стандартных топологий (шина, кольцо, звезда), тогда как задача оценки надежности сетей произвольных топологий изучена недостаточно. В работе
рассматривается задача определения оптимальной топологии сети по критериям связности с учетом затрат на изменение топологии сети.
В качестве отказа будем рассматривать структурно-топологические изменения, приводящие к нарушению связности сети, недопустимому снижению пропускной способности каналов и, соответственно, задержке получения информации или полному отказу в предоставлении сервисов пользователям.
Построение модели топологии сети передачи данных
Сеть передачи данных включает множество узлов коммутации, обрабатывающих данные, и множество каналов передачи данных. Логическую топологию сети будем представлять в виде ориентированного графа, описывающего пути передачи потоков данных между сетевыми устройствами и определяющими направление и способ передачи данных между узлами сети.
Под надежностью сети передачи данных, с точки зрения ее топологии, будем понимать свойство сети, заключающееся в том, что отказ части оборудования сети (каналов) не окажет значимого влияния на передачу информации между узлами сети.
Модель топологии сети передачи данных представляется в виде неориентированного графа G без петель, построенного на п вершинах V = |у1,…, Уп } и т ребрах V = {и1,…, ит}.
Каждая вершина V, г = 1, п графа G соответствует некоторому узлу сети, а ребра
, ] = 1, т графа представляют каналы передачи данных между узлами сети.
Задача повышения надежности топологии сети в общем случае формулируется как задача проектирования топологии сети или как задача модернизации ее топологии при наличии ограничений на бюджет. Данная задача может быть решена методом перебора решений. Однако если строится достаточно разветвленная протяженная сеть с большим количеством узлов, то поиск оптимальной топологии сети методом перебора требует значительных вычислительных ресурсов. Например, если сеть построена на п узлах, то
п (п-1)
количество возможных топологий сети будет равно 2 2. Сокращенный перебор, реализуемый с учетом отбрасывания недопустимых решений (несвязных графов), позволяет сократить вычислительную сложность, но его эффективность зависит от конкретных данных.
Построение топологий сетей с большим количеством обходных резервных каналов передачи данных, построенных на большом количестве узлов, создает условия невозможности использования алгоритмов перебора возможных вариантов решений. В этом случае эффективны методы случайного поиска, направленные на получение субоптимальных
решений. Рассмотрим применение генетических алгоритмов для решения задачи построения оптимальных топологий сетей с целью повышения надежности их функционирования.
Решение задачи оптимизации топологии сети с использованием генетического алгоритма
Применение генетического алгоритма начинается с разработки метода кодирования
решения. Топологию сети будем кодировать с помощью битовой строки размером п (/!, 1,
где п — количество вершин графа, в которой ненулевое значение в соответствующем бите означает наличие канала связи между узлами сети, 0 — отсутствие канала связи. Адаптация генетического алгоритма для решения конкретной оптимизационной задачи включает кодирование допустимого решения (точки в области допустимых значений), определяемого граничными условиями задачи, и его расшифровывания, т. е. представления решения, полученного с помощью генетического алгоритма, к удобному для восприятия виду.
В данной задаче под решением понимается допустимая топология сети, которая представляет связный граф.
При кодировании решения задачи в битовую строку будем использовать полную матрицу инцидентности. Размер битовой строки, кодирующей решение, определяется количеством столбцов в полной матрице инцидентности и зависит от количества вершин граф-модели.
Полная матрица инцидентности С, номера строк которой соответствуют номерам множества существующих узлов сети, а номера столбцов соответствуют номерам возможных
. --. п (п -1) каналов связи, состоит из элементов еу, I = 1, п, у = 1, ---, значения которых
(1 — если 1-й узел соединен с ]-м каналом сети, [0 — в противном случае.
Полная матрица инцидентности включает в себя все возможные каналы сети, количество которых определяется полным перебором соединений каждой вершины с каждой. При этом в у-м столбце матрицы два ненулевых элемента стоят в строках, номера которых соответствуют номерам узлов сети, соединяемым каналом с номером у. Решение, определяющее топологию графа, кодируется при помощи битовой строки размерности
, в котор°м единица в& gt-ы столбцеет ноичие ребра с н°мер°му в гроф-модели.
Полная матрица инцидентности полносвязного графа, построенного на 8 вершинах, имеет следующий вид (рис. 1).

1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 в 0 в в 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 в 1 0 в 1 1 0
0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 в 1 в в 1 в 1 0 1
0 0 в 0 0 в 1 в 0 в 0 0 1 0 0 0 0 1 0 в 0 1 в 0 1 в 1 1
Рис. 1. Матрица инцидентности полносвязного графа на 8 вершинах.
Пример топологии сети и соответствующая ей битовая строка, кодирующая данное решение, представлены на рисунке 2, при этом ненулевые элементы битовой строки (рис. 2б) стоят в столбцах, номера которых соответствуют номерам каналов, присутствующих в данной топологии.
а)
б)
Рис. 2. Допустимое решение: а) граф-модель- б) битовая строка.
В качестве целевой функции для оценки решений можно использовать такие показатели надежности, как минимальная степень исхода дуг из любой вершины, минимальное сечение, вероятность связности графа, количество минимальных сечений граф-модели сети. При поиске допустимых решений учитываются ограничения, связанные с реализацией топологии сети.
Значения целевой функции и затраты на реализацию решения определяются по математическому эквиваленту граф-модели — матрице смежности, значения ненулевых элементов
которой являются характеристиками (вероятность безотказной работы, пропускная способность, стоимость) каналов связи между 7-м и у-м узлами сети.
Допустимость решений, получаемых в процессе работы алгоритмов оптимизации, будет зависеть от двух факторов:
1) корректность сгенерированной граф-модели, включающей проверку связности графа-
2) выполнение ограничений на область допустимых решений.
Итерация генетического алгоритма при решении задачи построения топологии сети состоит из следующих шагов:
• генерируется начальное множество допустимых решений определенной мощности, представляющих совокупность N битовых строк, ненулевые элементы которых соответствуют множеству каналов связи в топологии сети. Для каждого решения вычисляется значение целевой функции и проверяются существующие ограничения-
• разрабатываются и реализуются механизмы формирования новых решений-
• разрабатываются методы отбора решений для следующей итерации алгоритма-
• проверяются условия окончания процесса моделирования [1].
Выводы
В результате проведенных исследований генетический алгоритм адаптирован к решению задач определения оптимальной топологии сети по показателям надежности, выполнены настройки операторов генетического алгоритма для поиска оптимальной топологии сети передачи данных. В результате проведенного моделирования для структур графов с количеством вершин, варьируемых в пределах от 100 до 1000, выполнены настройки операторов генетического алгоритма для обеспечения наилучшей сходимости алгоритма к оптимальному решению при минимальных вычислительных затратах. Получены следующие результаты: двухточечный оператор кроссовера следует использовать с вероятностью 70%, вероятность инвертирования бит для оператора мутации должна быть равна 2%, следует использовать смешанный тип оператора отбора для формирования нового поколения решений, когда топологии сети отбираются с помощью таких методов, как колесо рулетки, случайный и элитный выбор.
Предлагаемые методы и алгоритмы позволяют проектировать сети передачи данных, устойчивых к воздействию распределенных атак типа «отказ в обслуживании», целью которых является выведение из строя канала передачи или сопряженного с ним аппаратного обеспечения. Наличие дополнительных обходных каналов в условиях пиковых нагрузок в ходе атаки позволяет балансировать трафик внутри атакуемой сети и повысить ее пропускную способность, что является очень важным для транзитных сетей. В условиях программно-конфигурируемых сетей это дает дополнительные возможности для управления
потоками данных, что также повышает гибкость сети и ее устойчивость к экстремальным пиковым нагрузкам.
На разработанные алгоритмы получено свидетельство о регистрации программы для ЭВМ № 2 014 661 486 от 30. 10. 2014 г. «Библиотека, реализующая методы оптимизации топологии сетей передачи данных» [4].
Работа выполнена при поддержке ФЦП Министерства образования и науки РФ в рамках Соглашения о предоставлении субсидии № 14. 574. 21. 0034 от 17. 06. 2014.
Список литературы
1. Балашова Т. И. Кодирование допустимого решения задачи построения архитектуры вычислительной сети // 5-й Междунар. форум информац. технологий (ITFORUM 2020): тезисы докл. XVIII Междунар. научно-технич. конф. (ИСТ-2012). — Н. Новгород, 2012. — С. 272−273.
2. ГОСТ 27. 002−89. Надежность в технике. Основные понятия. Термины и определения.
3. Додд А. Мир телекоммуникаций. Обзор технологий и отрасли / Т. Хусаинов, А. З. Додд.
— М.: Олимп-Бизнес, 2002. — 400 с.
4. Капранов С. Н., Балашова Т. И., Соколова Э. С., Кобляков Д. А. Библиотека, реализующая методы оптимизации топологии сети передачи данных: Свидетельство о государственной регистрации программы для ЭВМ № 2 014 661 486 от 30. 10. 2014.
5. Семашко А. В. Задача оптимизации структуры магистральной корпоративной сети // Информационно-измерительные и управляющие системы. — 2010. — Т. 8, № 2. — C. 65−68.
6. Соколова Э. С. Построение модели надежности компьютерных сетей для решения задач их модернизации // Сб. ст. 5-й Мультиконференции по проблемам управления (МКПУ-2012).
— СПб., 2012. — С. 658−661.
Рецензенты:
Есипенко В. И., д.т.н., профессор, профессор кафедры «Электроника и сети ЭВМ», ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева», г. Нижний Новгород.
Андреев В. В., д.т.н., профессор, профессор кафедры «Ядерные реакторы и энергетические установки», ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева», г. Нижний Новгород.

ПоказатьСвернуть
Заполнить форму текущей работой