NETWORK TRAFFIC ROUTING ALGORITHM TAKING INTO ACCOUNT SAFETY REQUIREMENTS
Authors:
1.
Astrakhan Technical State University
2.
Astrakhan Technical State University
(Senior Lecturer of the Department of Information Security)
Russian Federation
Russian Federation
Type:
Article
Pages:
from 35
to 41
Status:
Published
Received:
05.04.2016
Accepted:
25.04.2016
Published:
25.04.2016
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.738.3:004.056.5
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.738.3:004.056.5
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
network flows, data security, routing algorithm, deviation of flows, time of packet delay
Abstract (English):
The paper presents the solution of the classical task of optimal routing of network flow, when as a criterion for optimizing not the delay time but the probability of information security breaches in the process of data transfer is taken. Thus, unlike many other works on routing comprising security restrictions, the proposed criterion of safety also depends on the delay time. This criterion relates to the probability of service security breach of the data packet during its transmission through the channels. The initial data of the model are the adjacency matrix of the graph describing the topology of the network, channel capacity and the matrix of gravitation, which describes the relative volume of data transmitted for various network couples. The proposed routing method is a method of deflection of flow, when the final result of the implementation of the method is not a listing of specific transmission routes but the volume of data transmitted for each channel at an optimum routing. In the process of the formation of alternative transmission methods Floyd’s method, a method of formation of shortest route matrix, is used. This formulation of the routing problem is mostly adequate to the requirements of security of data transmission in the network. The preliminary analysis is made and the correlations for all characteristics, used when implementing the method in the network, such as time delay for each channel, the length of the packet (message) and the desired target function, are obtained. Direct routing algorithm is similar to the algorithm of Kleinrock routing. The algorithm can be simply modified, if necessary, taking into account additional restrictions of any kind - the composition of the transmission routes, the transmission conditions and individual limits for each channel.
The paper presents the solution of the classical task of optimal routing of network flow, when as a criterion for optimizing not the delay time but the probability of information security breaches in the process of data transfer is taken. Thus, unlike many other works on routing comprising security restrictions, the proposed criterion of safety also depends on the delay time. This criterion relates to the probability of service security breach of the data packet during its transmission through the channels. The initial data of the model are the adjacency matrix of the graph describing the topology of the network, channel capacity and the matrix of gravitation, which describes the relative volume of data transmitted for various network couples. The proposed routing method is a method of deflection of flow, when the final result of the implementation of the method is not a listing of specific transmission routes but the volume of data transmitted for each channel at an optimum routing. In the process of the formation of alternative transmission methods Floyd’s method, a method of formation of shortest route matrix, is used. This formulation of the routing problem is mostly adequate to the requirements of security of data transmission in the network. The preliminary analysis is made and the correlations for all characteristics, used when implementing the method in the network, such as time delay for each channel, the length of the packet (message) and the desired target function, are obtained. Direct routing algorithm is similar to the algorithm of Kleinrock routing. The algorithm can be simply modified, if necessary, taking into account additional restrictions of any kind - the composition of the transmission routes, the transmission conditions and individual limits for each channel.
Keywords:
network flows, data security, routing algorithm, deviation of flows, time of packet delay
network flows, data security, routing algorithm, deviation of flows, time of packet delay
Введение Задача маршрутизации сетевых потоков достаточно известна. Эта задача возникла почти одновременно с созданием глобальных сетей, и ее решению посвящено достаточно много работ. В настоящее время имеются достаточно совершенные алгоритмы ее решения, основные из которых приведены в [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. Robachevskiy A. Bezopasnost' sistemy marshrutizacii Interneta / A. Robachevskiy // URL: http:// www.ripn.net/articles/secure_routing.
2. Belov S. V. Procedura nahozhdeniya optimal'nogo marshruta dvizheniya dokumenta / S. V. Belov, B. R. Dosmuhamedov // Izv. Volgograd. gos. tehn. un-ta. Ser.: Aktual'nye problemy upravleniya, vychislitel'noy tehniki i informatiki v tehnicheskih sistemah. 2012. № 15 (102). S. 73-79.
3. Kleynrok L. Vychislitel'nye sistemy s ocheredyami. M.: Mir, 1979. 600 s.
4. Olifer V. G. Komp'yuternye seti. Principy, tehnologii, protokoly: ucheb. dlya vuzov / V. G. Olifer, N. A. Olifer. SPb.: Piter, 2010. 943 s.
5. Kleynrok L. Teoriya massovogo obsluzhivaniya / L. Kleynrok. M.: Mashinostroenie, 1979. 432 s.
