АЛГОРИТМ МАРШРУТИЗАЦИИ СЕТЕВЫХ ПОТОКОВ С УЧЕТОМ ТРЕБОВАНИЙ ПО БЕЗОПАСНОСТИ
Авторы:
1.
Астраханский государственный технический университет
2.
Астраханский государственный технический университет
(старший преподаватель кафедры информационной безопасности)
Россия
Россия
Тип:
Статья
Страницы:
с 35
по 41
Статус:
Опубликован
Получено:
05.04.2016
Одобрено:
25.04.2016
Опубликовано:
25.04.2016
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.738.3:004.056.5
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.738.3:004.056.5
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
сетевые потоки, безопасность данных, алгоритм маршрутизации, отклонение потоков, время задержки пакета
Аннотация (русский):
Предложено решение классической задачи оптимальной маршрутизации сетевых потоков, когда в качестве критерия оптимизации выбирается не время задержки, а вероятность нарушения безопасности информации в процессе передачи данных. В отличие от многих других работ по маршрутизации, содержащих ограничения по безопасности, предлагаемый критерий безопасности зависит также от времени задержки. Этот критерий связан с вероятностью нарушения сервиса безопасности пакета данных в процессе его передачи по каналам. Исходными данными модели являются матрица смежности графа, описывающая топологию сети, пропускные способности каналов, и матрица тяготения, описывающая относительный объем передаваемых данных для различных пар сети. Предлагаемый метод маршрутизации относится к классу методов отклонения потока, когда конечным результатом реализации метода является не перечисление конкретных маршрутов передачи, а объемы передаваемых данных по каждому каналу при оптимальной маршрутизации. В процессе формирования альтернативных способов передачи используется метод Флойда - метод формирования матрицы кратчайших маршрутов. Такая постановка проблемы маршрутизации наиболее адекватна требованиям обеспечения безопасности передачи данных в сети. Предварительно проведен анализ и получены соотношения для всех характеристик, используемых при реализации метода в сети: времени задержки в каждом канале, длины пакета (сообщения), искомой целевой функции. Непосредственно алгоритм маршрутизации подобен алгоритму маршрутизации Клейнрока. Разработанный алгоритм может быть достаточно просто модифицирован при необходимости учета дополнительных ограничений любого типа - по составу маршрутов передачи, по условиям передачи, учета и индивидуальных ограничений по каждому каналу.
Предложено решение классической задачи оптимальной маршрутизации сетевых потоков, когда в качестве критерия оптимизации выбирается не время задержки, а вероятность нарушения безопасности информации в процессе передачи данных. В отличие от многих других работ по маршрутизации, содержащих ограничения по безопасности, предлагаемый критерий безопасности зависит также от времени задержки. Этот критерий связан с вероятностью нарушения сервиса безопасности пакета данных в процессе его передачи по каналам. Исходными данными модели являются матрица смежности графа, описывающая топологию сети, пропускные способности каналов, и матрица тяготения, описывающая относительный объем передаваемых данных для различных пар сети. Предлагаемый метод маршрутизации относится к классу методов отклонения потока, когда конечным результатом реализации метода является не перечисление конкретных маршрутов передачи, а объемы передаваемых данных по каждому каналу при оптимальной маршрутизации. В процессе формирования альтернативных способов передачи используется метод Флойда - метод формирования матрицы кратчайших маршрутов. Такая постановка проблемы маршрутизации наиболее адекватна требованиям обеспечения безопасности передачи данных в сети. Предварительно проведен анализ и получены соотношения для всех характеристик, используемых при реализации метода в сети: времени задержки в каждом канале, длины пакета (сообщения), искомой целевой функции. Непосредственно алгоритм маршрутизации подобен алгоритму маршрутизации Клейнрока. Разработанный алгоритм может быть достаточно просто модифицирован при необходимости учета дополнительных ограничений любого типа - по составу маршрутов передачи, по условиям передачи, учета и индивидуальных ограничений по каждому каналу.
Ключевые слова:
сетевые потоки, безопасность данных, алгоритм маршрутизации, отклонение потоков, время задержки пакета
сетевые потоки, безопасность данных, алгоритм маршрутизации, отклонение потоков, время задержки пакета
Введение Задача маршрутизации сетевых потоков достаточно известна. Эта задача возникла почти одновременно с созданием глобальных сетей, и ее решению посвящено достаточно много работ. В настоящее время имеются достаточно совершенные алгоритмы ее решения, основные из которых приведены в [1, 2]. Однако в существующих алгоритмах основное внимание уделено времени доставки пакета либо другим временным характеристикам сети. Показатели же безопасности сети рассматриваются только как дополнительные, которые обычно учитываются в виде ограничений. Глобализация сетей в настоящее время привела к существенному росту числа атак на рабочие станции пользователей сети (в частности, сети Интернет), что, как следствие, все в большей степени выдвигает требования по обеспечению информационной безопасности в качестве основных требований, предъявляемых к технологии передачи и обработки данных в сети Интернет. В данной работе рассматривается задача маршрутизации, в которой наряду с показателем задержки сообщения в сети рассматривается вероятность нарушения сохранности и (или) безопасности сообщения. Работ по маршрутизации сетей, в которых показатели безопасности входили бы в состав целевой функции, почти нет; укажем лишь работы [1, 2]. Описание модели Пусть задана сеть, состоящая из N узлов. Для простоты рассмотрения мы не детализируем сетевое оборудование, используемое при подключении к сети. Тогда сеть может быть представлена в виде следующего графа: каждая пользовательская рабочая станция может быть представлена в виде одного узла сети, который описывается следующими параметрами. Пронумеруем все узлы сети и для i-го узла введем следующие характеристики: aij = 1, если из i-го узла данные могут быть переданы непосредственно в j-й узел, и aij = 0 в противном случае; Cij - пропускная способность канала из i-го узла в j-й, если этот канал существует - измерять можно, например, в битах в секунду; γij - коэффициент тяготения i-го узла по отношению к j-му - измерять можно средним количеством бит информации, переданных за заданный регламентный промежуток времени из i-го узла j-й. Обозначим: A = - матрица смежности графа, описывающего топологическую структуру сети; C = - матрица пропускной способности каналов; - матрица тяготения между узлами сети. Тогда полный поток, циркулирующий в сети, равен . В качестве целевого критерия выбираем вероятность нарушения отдельного свойства передаваемой информации, описываемого определенным показателем информационной безопасности или их некоторой совокупности. В качестве возможных контролируемых качеств информации, безопасность которых обеспечивается, выберем следующие два, являющиеся наиболее важными и необходимыми: свойство конфиденциальности информации и свойство ее целостности. Предлагаемый нами метод распределения потоков относится к классу методов отклонения потоков [3]. Результат решения задачи маршрутизации на основе данного метода представляется в виде матрицы , описывающей величину потока по различным каналам при оптимальной маршрутизации потоков. Для завершения решения задачи маршрутизации необходимо, например, на основе матрицы , сформировать алгоритм управления потоками, который в каждый момент времени принимал бы решение о том, по какому маршруту направить каждый из потоков, имеющихся и возникающих в сети. Наиболее близкий (к рассматриваемому) вариант алгоритма маршрутизации по критерию минимума средней задержки пакета приведен в [3, с. 386]. При выводе результатов мы, по аналогии с [3], будем пользоваться методами и результатами теории массового обслуживания (ТМО) [4]. Введем следующие обозначения: pij(t, τ) - вероятность того, что при передаче пакета из i-го узла в j-й в пакете длиной τ бит за время t не произойдет нарушения информационной безопасности; - среднее время задержки пакета при его передаче из i-го узла в j-й. Если обозначить через τ случайную длительность пакета, то b = M(τ). Заметим, что, как будет следовать из приводимых ниже выражений, в вероятности pij(t, τ) зависимость от τ выражается в учете только первого и второго моментов случайной величины τ. Выведем выражение для вероятности Pij() того, что произойдет нарушение безопасности информации. Так как (i, j)-канал передачи (т. е. канал передачи из i-го узла в j-й) в среднем пропускает 1 бит информации за время 1/Сij, то среднее время непосредственно передачи пакета (обработки - в терминах ТМО) равно βij = b (1/Cij). Кроме того, пакет будет находиться в течение времени в режиме ожидания. Величина представляет собой среднее время ожидания обслуживания в системе типа M/M/1, для которой получено следующее выражение для среднего времени ожидания (формула Поллачека - Хинчина) [4]: , где - второй момент длительности передачи пакета из i-го узла в j-й; - интенсивность потока пакетов из i-го узла в j-й. Имеем: и b2 = M(τ2) - второй момент случайной длительности пакета. Тогда, после подстановки полученных выражений, получаем . (1) Отсюда выводим: вероятность того, что в процессе передачи одного пакета из i-го узла в j-й безопасность не будет нарушена, равна p(, τ). Поскольку интенсивность потока λij, то вероятность того, что в процессе передачи всех пакетов за заданное регламентное время T из i-го узла в j-й безопасность не будет нарушена, равна , где есть среднее число пакетов за время T, передаваемых из i-го узла в j-й, а наличие aij позволяет охватить как случай наличия прямой связи от i-го узла в j-й, так и случай ее отсутствия. Тогда вероятность того, что в процессе передачи за регламентное время T не будет нарушена безопасность ни одного из пакетов, . Тогда искомая задача может быть сформулирована следующим образом: найти такое распределение потоков по каналам передачи (с учетом наличия или отсутствия прямой связи между узлами, степени притяжения узлов), чтобы вероятность нарушения безопасности была бы минимальной; параметрами оптимизации являются интенсивности потоков по различным каналам передачи {λij}: . Однако величина при больших размерах сети, а также ввиду малости вероятностей p(, τ) принимает очень малые значения, поэтому сформулированную задачу минимизации вероятности нарушения безопасности предлагается заменить на следующую равносильную задачу: найти максимальное значение величины , (2) где знак «минус» добавлен для того, чтобы все числа были положительными, т. к. < 1. Именно решению задачи (2) и посвящен предлагаемый ниже алгоритм. Прежде чем описывать алгоритм маршрутизации, отметим следующий принципиальный момент, связанный с правомерностью использования приводимых ниже соотношений. Предполагается, что для каждого узла входной и выходной потоки не зависят от входных и выходных потоков других узлов. Данное предположение в принципе абсолютно неверно, т. к. при передаче сообщений выходной поток одного узла является входным для следующего по цепочке. Однако, как отмечено в [3, с. 253], результаты экспериментов и измерений в реальных сетях достаточно точно совпадали с теоретическими результатами, полученными на основе данного предположения; при этом отклонение в самых худших случаях не превышало 10 %. Этот факт дает основание рассматривать все узлы как независимые модели ТМО. Результаты экспериментов позволили также принять следующее предположение [3, с. 362]: можно считать, что длины сообщений в каждом узле заново моделируются на основе показательного распределения с параметром , хотя реально длина сообщения в процессе его передачи остается неизменной. Из сказанного следует, что случайная величина τ имеет показательное распределение с некоторым параметром μ. Отсюда выводим: b = 1/μ, b2 = 2/μ2, и соотношение (1) можно переписать в следующем виде: . (3) Соотношение (3) и будет использоваться в приводимом ниже алгоритме. Наконец, считая в первом приближении, что на пересекающихся интервалах вероятности нарушения информационной безопасности независимы, приходим к соотношению pij(nt, τ) = pij(t, τ)n для любых n и t, откуда нетрудно вывести равенство , где θ - интенсивность попыток нарушить показатели информационной безопасности передаваемых данных. Алгоритм маршрутизации В настоящее время разработан богатый набор алгоритмов маршрутизации, которые достаточно полно представлены в [5]. Однако с точки зрения критерия безопасности, выбранного нами, интерес представляет не конечная цель (конечный узел), как это имеет место при минимизации времени задержки, а состояние безопасности по маршруту движения документа (т. е. в промежуточных узлах движения пакета). Именно поэтому среди всех просмотренных алгоритмов был выбран один из алгоритмов отклонения потока - алгоритм Клейнрока [3, гл. 5]. Его основная особенность состоит в том, что в алгоритме осуществляется построение не непосредственно оптимальных маршрутов, соединяющих каждую пару вершин, а лишь находится матрица , описывающая объемы передаваемых данных для каждой пары смежных узлов сети при оптимальной маршрутизации процесса передачи. Тогда оптимальные маршруты для всех пар узлов строятся на основе такого перераспределения передаваемых потоков, при котором соблюдаются требования по объему передачи, задаваемые матрицей . Опишем этапы предлагаемого алгоритма. Этап I. Сформировать начальный вариант распределения потока следующим образом. 1. Введем матрицу весов отдельных каналов (эти веса назовем (относительными) длинами каналов), положив (см. (2) и (3)): . Если lij = 0, то полагаем . 2. Найти матрицу D кратчайших маршрутов для всех пар узлов на основе метода Флойда с матрицей расстояний между вершинами -L (взят знак «минус», т. к. нас интересуют (см. (2)) наиболее длинные маршруты, а не кратчайшие) следующим образом. Полагаем и последовательно, начиная с n = 1, строим матрицы на основе соотношений , (4) где есть длина наикратчайшего пути между i-м и j-м узлами (на основе введенных выше относительных длин отдельных каналов), и при этом промежуточные узлы принадлежат множеству {1, 2, …, n - 1}. Тогда D = DN. 3. Построим начальный вариант матрицы потоков по кратчайшим маршрутам следующим образом. Полагаем и для всех . Просматриваются произвольным образом все пары вершин (i, j) и для каждой пары (i, j) перебираются значения n, начиная от n = N и заканчивая n = 2 (если процесс поиска не закончился раньше) до тех пор, пока при некотором n = n(i, j) > 1 не будут выполнены следующие условия: , конечно (отметим, что в рассматриваемом случае минимум в (4) достигается на втором слагаемом, т. е. наикратчайший путь проходит через вершину n(i, j)); если же последнее неравенство ни при каком n не выполняется, но конечно, то полагаем n(i, j) = 1, в противном случае (т. е. неравенство не выполняется и ,) пути из i-й вершину в j-ю нет. Тогда полагаем: , и остается неизменным для остальных пар (i, j), . После просмотра всех пар вершин получим конечное значение для все пар (i, j), что и представляет собой результирующий поток, передаваемый по каналу (i, j) при пересылке по кратчайшим маршрутам. Однако построенный поток в принципе может быть нереализуем ввиду того, что мы не учитывали другие ограничения в задаче, в частности ограничения на пропускные способности каналов. Поэтому на основе построенного варианта распределения потоков необходимо получить реализуемый вариант матрицы потоков . В пункте 1 описана соответствующая процедура, которая также используется далее при отклонении потока в общей процедуре. Этап. II. Провести перенаправление части потоков в сети (отклонение потоков) следующим образом: 1. Выполнить следующую итерационную процедуру. Положим n = 0 - номер итерации, и вычислим коэффициент , описывающий степень превышения распределенного на n-й итерации потока по каналу (i, j) над пропускной способностью этого канала. Если ограничения по пропускной способности каналов не нарушены для всех каналов, т. е. , то процедура отклонения потока прекращается и полагаем , где для начального потока k = 0. Если же для некоторого канала (i, j) имеем , то условную длину канала (i, j) удлиняем в раз, т. е. полагаем , если , и , если для всех пар (i, j), где . Затем вновь решаем задачу распределения потока по кратчайшим маршрутам, рассмотренную на этапе I, где в качестве матрицы расстояний берется матрица и интенсивности потоков равны и . В результате получаем матрицу потоков , где есть интенсивность потока по каналу (i, j). Поскольку при построении матрицы перегруженные каналы были удлинены, то при поиске кратчайших путей эти каналы с большой вероятностью не войдут в состав кратчайших путей, и, как следствие, в потоке многие из каналов, которые были перегружены в потоке , перестанут быть перегруженными. Для получения потока смешиваем потоки и так, чтобы значение целевой функции π принимало максимально возможное значение, то есть полагаем , где 0 ≤ a ≤ 1 и a находится как решение одномерной задачи минимизации , в которой в качестве интенсивностей поступающих потоков (точнее, вместо них) берутся числа . Указанная задача одномерной минимизации может решаться любым из известных методов, в частности методом золотого сечения, либо Фибоначчи, либо деления пополам. Таким образом, в результате работы процедуры, описанной на данном этапе, получим начальный допустимый поток . Отметим важный факт: при всех описанных преобразованиях суммарная величина потока оставалась неизменной: для всех n. Этап III. Построить матрицу распределения потоков по различным каналам передачи следующим образом. Положить n = 0, . 1. Полагаем , если i-й и j-й узлы связаны непосредственно, и в противном случае; . Если lij = 0, то полагаем . 2. На основе процедуры, описанной на этапе I, находим оптимальный поток последовательно для всех n, начиная с n = 0. Если в процессе поиска, начиная с некоторого n0, значение целевой функции становится неизменным, т. е. , то процесс поиска прекращается и последняя матрица выдается в качестве решения задачи. Если в процессе поиска нарушается монотонный рост целевой функции, т. е. при некотором n выполнено , то задача не имеет решения, и процесс поиска также прекращается. Описание алгоритма закончено. Данный алгоритм достаточно просто может быть модифицирован для учета дополнительных ограничений; например, при ограниченном наборе допустимых маршрутов, наличии индивидуальных ограничений по отдельным каналам. Заключение Таким образом, рассмотрена задача маршрутизации потоков в сетях для случая, когда в качестве целевой функции берутся не показатели, связанные с эффективностью работы сети (время задержки сообщения, стоимость сети и др.), а показатели безопасности. Получены выражения, необходимые для вычисления вероятности обеспечения сохранности сообщений, разработан алгоритм нахождения оптимальных маршрутов передачи при данной целевой функции. Данный алгоритм достаточно просто может быть модифицирован для учета дополнительных ограничений; например, при ограниченном наборе допустимых маршрутов, наличии индивидуальных ограничений по отдельным каналам.
1. Робачевский А. Безопасность системы маршрутизации Интернета / А. Робачевский // URL: http:// www.ripn.net/articles/secure_routing.
2. Белов С. В. Процедура нахождения оптимального маршрута движения документа / С. В. Белов, Б. Р. Досмухамедов // Изв. Волгоград. гос. техн. ун-та. Сер.: Актуальные проблемы управления, вычислительной техники и информатики в технических системах. 2012. № 15 (102). С. 73-79.
3. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.
4. Олифер В. Г. Компьютерные сети. Принципы, технологии, протоколы: учеб. для вузов / В. Г. Олифер, Н. А. Олифер. СПб.: Питер, 2010. 943 с.
5. Клейнрок Л. Теория массового обслуживания / Л. Клейнрок. М.: Машиностроение, 1979. 432 с.
