Современный этап развития территориально распределённых сетей передачи данных характеризуется ростом сложности и масштабов инфраструктур, непрерывным повышением требований к качеству предоставляемых услуг связи, доступа к сервисам. Сеть передачи данных должна быть экономически эффективной, и при ее проектировании или модернизации должно быть выполнено соответствующее обоснование и предоставлены расчеты по обеспечению надежности. К надежности сетей предъявляются все более высокие требования. Низкая надежность приводит к потере клиентов, убыткам и штрафным санкциям. Повышение надежности сети связано с дополнительными затратами, которые могут превысить прибыль, получаемую от предоставления инфокоммуникационных услуг [6]. В этой связи актуальна задача достижения требуемых характеристик надежности при проектировании или модернизации сети при минимально возможных затратах на ее обеспечение.
Необходимость надежного планирования телекоммуникационных сетей (ТС) подчеркивается в принятой еще в 1988 г. и пересмотренной уже в 1992 г. рекомендации Международного телекоммуникационного союза «Надежность планирования телекоммуникационных сетей» [5].
Под термином «надежность» понимается свойство сети сохранять во времени в установленных пределах значения всех параметров, характеризующих способность выполнять требуемые функции в заданных режимах и условиях использования [2]. Характеристики надежности сети должны обеспечивать клиентам возможность обмениваться информацией и получать сервисы в условиях технических отказов, эксплуатационных ошибок, а также с учетом возможных угроз и рисков, связанных с атаками типа «отказ в обслуживании».
Надежность сети обеспечивается применением надежного оборудования и внесением избыточности в структуру сети для повышения готовности сети, т.е. обеспечения ее отказоустойчивости [3]. Комплексное решение задач обеспечения надежности включает оба направления – обеспечение аппаратной и структурной надежности. В первом случае решается проблема обеспечения надежности элементов сети - сетевого оборудования, каналов передачи данных, программного обеспечения. Структурная надежность обеспечивает функции сети, связанные с передачей данных. Для анализа структурной надежности используются показатели связности граф-моделей сети. Нарушить связность может как отказ аппаратуры в узлах сети, так и отказ каналов передачи данных. При этом отказ канала может быть связан как с его механическим повреждением (обрывом), так и с ухудшением его характеристик, в том числе превышением его пропускной способности. Для обеспечения связности сети применяются отказоустойчивые сетевые технологии, связанные с введением избыточности реализацией обходных путей передачи информации, и применением протоколов, например STP, автоматически обеспечивающих обход отказавшего участка. Внесение избыточности в топологию корпоративных сетей позволяет повысить надежность маршрутизации больших объемов трафика, обеспечив связность с максимальным числом внешних сетей.
В настоящее время опубликовано большое число работ, в которых рассматриваются вопросы оценки надежности сетей стандартных топологий (шина, кольцо, звезда), тогда как задача оценки надежности сетей произвольных топологий изучена недостаточно. В работе рассматривается задача определения оптимальной топологии сети по критериям связности с учетом затрат на изменение топологии сети.
В качестве отказа будем рассматривать структурно-топологические изменения, приводящие к нарушению связности сети, недопустимому снижению пропускной способности каналов и, соответственно, задержке получения информации или полному отказу в предоставлении сервисов пользователям.
Построение модели топологии сети передачи данных
Сеть передачи данных включает множество узлов коммутации, обрабатывающих данные, и множество каналов передачи данных. Логическую топологию сети будем представлять в виде ориентированного графа, описывающего пути передачи потоков данных между сетевыми устройствами и определяющими направление и способ передачи данных между узлами сети.
Под надежностью сети передачи данных, с точки зрения ее топологии, будем понимать свойство сети, заключающееся в том, что отказ части оборудования сети (каналов) не окажет значимого влияния на передачу информации между узлами сети.
Модель топологии сети передачи данных представляется в виде неориентированного графа G без петель, построенного на n вершинах 
и m ребрах 
. Каждая вершина 
графа G соответствует некоторому узлу сети, а ребра 
графа представляют каналы передачи данных между узлами сети.
Задача повышения надежности топологии сети в общем случае формулируется как задача проектирования топологии сети или как задача модернизации ее топологии при наличии ограничений на бюджет. Данная задача может быть решена методом перебора решений. Однако если строится достаточно разветвленная протяженная сеть с большим количеством узлов, то поиск оптимальной топологии сети методом перебора требует значительных вычислительных ресурсов. Например, если сеть построена на n узлах, то количество возможных топологий сети будет равно 
. Сокращенный перебор, реализуемый с учетом отбрасывания недопустимых решений (несвязных графов), позволяет сократить вычислительную сложность, но его эффективность зависит от конкретных данных.
Построение топологий сетей с большим количеством обходных резервных каналов передачи данных, построенных на большом количестве узлов, создает условия невозможности использования алгоритмов перебора возможных вариантов решений. В этом случае эффективны методы случайного поиска, направленные на получение субоптимальных решений. Рассмотрим применение генетических алгоритмов для решения задачи построения оптимальных топологий сетей с целью повышения надежности их функционирования.
Решение задачи оптимизации топологии сети с использованием генетического алгоритма
Применение генетического алгоритма начинается с разработки метода кодирования решения. Топологию сети будем кодировать с помощью битовой строки размером 
, где n – количество вершин графа, в которой ненулевое значение в соответствующем бите означает наличие канала связи между узлами сети, 0 – отсутствие канала связи. Адаптация генетического алгоритма для решения конкретной оптимизационной задачи включает кодирование допустимого решения (точки в области допустимых значений), определяемого граничными условиями задачи, и его расшифровывания, т.е. представления решения, полученного с помощью генетического алгоритма, к удобному для восприятия виду.
В данной задаче под решением понимается допустимая топология сети, которая представляет связный граф.
При кодировании решения задачи в битовую строку будем использовать полную матрицу инцидентности. Размер битовой строки, кодирующей решение, определяется количеством столбцов в полной матрице инцидентности и зависит от количества вершин граф-модели.
Полная матрица инцидентности С, номера строк которой соответствуют номерам множества существующих узлов сети, а номера столбцов соответствуют номерам возможных каналов связи, состоит из элементов 
, значения которых
.
Полная матрица инцидентности включает в себя все возможные каналы сети, количество которых определяется полным перебором соединений каждой вершины с каждой. При этом в j-м столбце матрицы два ненулевых элемента стоят в строках, номера которых соответствуют номерам узлов сети, соединяемым каналом с номером j. Решение, определяющее топологию графа, кодируется при помощи битовой строки размерности 
, в котором единица в j-м столбце означает наличие ребра с номером j в граф-модели.
Полная матрица инцидентности полносвязного графа, построенного на 8 вершинах, имеет следующий вид (рис. 1).
Рис. 1. Матрица инцидентности полносвязного графа на 8 вершинах.
Пример топологии сети и соответствующая ей битовая строка, кодирующая данное решение, представлены на рисунке 2, при этом ненулевые элементы битовой строки (рис. 2б) стоят в столбцах, номера которых соответствуют номерам каналов, присутствующих в данной топологии.
а)
б)
Рис. 2. Допустимое решение: а) граф-модель; б) битовая строка.
В качестве целевой функции для оценки решений можно использовать такие показатели надежности, как минимальная степень исхода дуг из любой вершины, минимальное сечение, вероятность связности графа, количество минимальных сечений граф-модели сети. При поиске допустимых решений учитываются ограничения, связанные с реализацией топологии сети.
Значения целевой функции и затраты на реализацию решения определяются по математическому эквиваленту граф-модели – матрице смежности, значения ненулевых элементов которой являются характеристиками (вероятность безотказной работы, пропускная способность, стоимость) каналов связи между i-м и j-м узлами сети.
Допустимость решений, получаемых в процессе работы алгоритмов оптимизации, будет зависеть от двух факторов:
1) корректность сгенерированной граф-модели, включающей проверку связности графа;
2) выполнение ограничений на область допустимых решений.
Итерация генетического алгоритма при решении задачи построения топологии сети состоит из следующих шагов:
-
генерируется начальное множество допустимых решений определенной мощности, представляющих совокупность N битовых строк, ненулевые элементы которых соответствуют множеству каналов связи в топологии сети. Для каждого решения вычисляется значение целевой функции и проверяются существующие ограничения;
-
разрабатываются и реализуются механизмы формирования новых решений;
-
разрабатываются методы отбора решений для следующей итерации алгоритма;
-
проверяются условия окончания процесса моделирования [1].
Выводы
В результате проведенных исследований генетический алгоритм адаптирован к решению задач определения оптимальной топологии сети по показателям надежности, выполнены настройки операторов генетического алгоритма для поиска оптимальной топологии сети передачи данных. В результате проведенного моделирования для структур графов с количеством вершин, варьируемых в пределах от 100 до 1000, выполнены настройки операторов генетического алгоритма для обеспечения наилучшей сходимости алгоритма к оптимальному решению при минимальных вычислительных затратах. Получены следующие результаты: двухточечный оператор кроссовера следует использовать с вероятностью 70%, вероятность инвертирования бит для оператора мутации должна быть равна 2%, следует использовать смешанный тип оператора отбора для формирования нового поколения решений, когда топологии сети отбираются с помощью таких методов, как колесо рулетки, случайный и элитный выбор.
Предлагаемые методы и алгоритмы позволяют проектировать сети передачи данных, устойчивых к воздействию распределенных атак типа «отказ в обслуживании», целью которых является выведение из строя канала передачи или сопряженного с ним аппаратного обеспечения. Наличие дополнительных обходных каналов в условиях пиковых нагрузок в ходе атаки позволяет балансировать трафик внутри атакуемой сети и повысить ее пропускную способность, что является очень важным для транзитных сетей. В условиях программно-конфигурируемых сетей это дает дополнительные возможности для управления потоками данных, что также повышает гибкость сети и ее устойчивость к экстремальным пиковым нагрузкам.
На разработанные алгоритмы получено свидетельство о регистрации программы для ЭВМ № 2014661486 от 30.10.2014 г. «Библиотека, реализующая методы оптимизации топологии сетей передачи данных» [4].
Работа выполнена при поддержке ФЦП Министерства образования и науки РФ в рамках Соглашения о предоставлении субсидии № 14.574.21.0034 от 17.06.2014.
Рецензенты:
Есипенко В.И., д.т.н., профессор, профессор кафедры «Электроника и сети ЭВМ», ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева», г. Нижний Новгород.
Андреев В.В., д.т.н., профессор, профессор кафедры «Ядерные реакторы и энергетические установки», ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева», г. Нижний Новгород.