Многокритериальная многопутевая маршрутизация в mesh-сетях.

Авторы: Афанасьев А.Л., Гармонов А.В.

Источник: http://www.govvrn.ru

Ключевые слова: маршрутизация, меш-сети, многокритериальность.

Key words: routing, mesh-networks, multicriteria.

Введение

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

Mesh-сети — это сети, топология которых получена из полносвязной топологии за счет удаления некоторого количество связей. Особенно интересны мобильные mesh — радио сети (MANET) (рисунок 1). Это самоорганизующиеся сети, узлы которых равноправны и могут выступать в роле маршрутизаторов. Топология таких сетей изменяется во времени. Следовательно, маршрутизация должна осуществляться динамически.

Рисунок 1 – мобильная mesh-сеть

Протоколы маршрутизации. Сравнительная характеристика.

Протоколы маршрутизации — это протоколы 3-4 уровня модели взаимодействия открытых систем, отвечающие за поиск пути по которому будет передаваться информация. Протоколы маршрутизации, используемые для MANET сетей можно разделить в два больших класса: проактивные и реактивные. Однако существуют протоколы, объединяющие методы обоих классов, например гибридный протокол HWMP. Рассмотрим подробней оба класса и их представителей.

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

К проактивным протаколам относятся – Fisheye State Routing (FSR) Link State Routing Protocol (OLSR) [1], Topology Broadcast based on Reverse Path Forwarding (TBRPF); Принцип действия проактивных протоколов проиллюстрирован на примере протокола OLSR (рисунок 2).

Рисунок 2 – работа алгоритма OLSR.

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

К реактивным маршрутам относятся – Ad-hoc On demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR), Lightweight Mobile Routing (LMR), Temporally-Ordered Routing Algorithms (TORA) . Принцип действия реактивных протоколов проиллюстрирован на примере протокола AODV (рисунок 3). Сравнительная характеристика проактивных и реактивных алгоритмов представлена в таблице 1. Здесь N – число узлов в сети, e – число открытых сеансов, M – число смежных узлов.

Рисунок 3 – работа алгоритма AODV

Таблица 1 - Сравнение реактивых и проактивных алгоритмов.

Гибридный протокол маршрутизации HWMP (Hybrid Wireless Mesh Protocol) использует стандартный набор служебных пакетов, правил их создания и обработки, наподобие хорошо известного протокола дистанционно-векторной маршрутизации по запросу (Ad Hoc On Demand Distance Vector, AODV)[2].

Однако HWMP адаптирован для работы с адресами MAC уровня и метриками путей. Гибридным он назван потому, что объединяет в себе два режима построения путей, которые могут быть использованы как по отдельности, так и одновременно в одной сети:

- реактивный режим – построение маршрутных таблиц в узлах mesh-сети непосредственно перед передачей данных - по запросу;

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

Основное преимущество алгоритмов, разработанных для сетей MANET – полностью децентрализованный характер, а также поддержка Multicast (множественной адресации) и QoS (качества обслуживания). В то же время, начиная с некоторого размера сети, эти алгоритмы обладают плохой масштабируемостью. В проактивных методах это проявляется в росте объемов рассылаемых оповещений. В реактивных – в росте объемов поисковых запросов при увеличении мобильности узлов. Реактивные алгоритмы менее требовательны к памяти, но обладают большей вычислительной сложностью. Однако все существующие алгоритмы, даже если и имеют функцию контроля качества маршрута, используют не полную информацию о маршруте, а следовательно будут неоптимальными.

Многокритериальная много путевая маршрутизация.

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

Сформулируем задачу многокритериальной маршрутизации в беспроводной mesh-сети на графе между узлом-источником и узлом-назначением. Введем систему частных критериев, которая характеризует качество передачи информации от узла-источника к узлу-назначения на каждом промежуточном узле. Предположим, что канальная скорость передачи на которой ведется передача данных с последующим узлом (например для стандарта 802.11g возможны скорости 54, 48, 36, 24, 18, 12, 9, 6 Мбит/сек) оценивается частным критерием I₁, загруженность узла I₂, время задержки узлом I₃, заряд батареи узла I₄ . Отметим, что критерии I₁ и I₄ максимизируются, а критерии I₂ и I₃ минимизируются. Приведем все к минимизационнуму виду, для этого заменим критерии I₁ критерием I₁ = I_1м — I₁. Где I_1м — максимальное возможное значение параметра. Аналогично поступим с критерием I₄. Далее переходим к системе относительных частных критериев I₁/ I_1м, I₂/ I_2м, I₃/ I_3м, I₄/ I_4м. Очевидно, что диапазон изменения этих параметров лежит в пределах от нуля до единицы.

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

_ , _ , _ (1)

Где I_i – i-й частный критерий качества; α_i– весовые коэффициенты; I_im – предельно-допустимое значение частного критерия качества I_i.

При использовании протокола маршрутизации предлагается присваивать связям между узлами метрику пропорциональный скалярной величине, которая определяется по нелинейной схеме компромиссов (1). J

Математическая модель mesh-сети в виде графа, веса (длина) ветвей которого рассчитываются по выражению (1) позволяет реализовать многокритериальную оптимизацию маршрутов передачи информации от узла-источника к узлe-назначения путем минимизации критерия качества:

_ , _ , _ (2)

где I_ij – i-й частный критерий качества в j-й ветви графа; I_ijm – предельно-допустимое значение i-го частного критерия качества в j-й ветви графа; α_ij – весовые коэффициенты; n – количество частных критериев качества; r – количество ветвей графа вдоль маршрута от узла-источника к узлу-назначения.

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

Задача минимизации критерия качества (2) известна как задача о кратчайшем пути между узлом-источником и узлом-назначения. Следовательно, применение для расчета весов графа математической модели компьютерной сети свертки по нелинейной схеме компромиссов (2) сводит задачу многокритериальной маршрутизации к известной задачи о кратчайшем пути, которая может быть решена алгоритмом Дейкстры либо параллельными средствами маршрутизации [3]. Однако при использование реактивных протоколов, когда каждый узел не имеет полной информации о полном графе сети воспользоваться алгоритмом Дейкстры не представляется возможным, Но в этом случае мы все же имеем большую вероятность что построенный маршрут окажется кратчайшим путем.

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

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

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

1. Однопутевая маршрутизация при помощи какого-либо протокола маршрутизации.

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

3. Переход к пункту 1, если количество маршрутов меньше требуемого количества.

Однако, для определенных алгоритмов существуют методики параллельного поиска нескольких маршрутов. Например для протокола AODV такие методики предлагаются в [3].

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

Заключение

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

Рисунок4 – схема узла многопутевой многокритериальной маршрутизации.

Список источников:

1. Jacquet, P. Optimized Link State Routing Protocol for Ad Hoc Networks / P. Jacquet et al. // Proc. IEEE Int’l MultiTopic Conf., 2001. — IEEE Press, 2001. — P. 62-68.

2. В.Вишневский, д.т.н.; Д.Лаконцев, к.т.н.; А.Сафонов, к.т.н; С.Шпилев, к.т.н.: Mesh-сети стандарта IEEE 802.11s: Протоколы маршрутизации – Первая Миля, Янв. 2009

3. Multi-path Routing Protocols in Wireless Mobile Ad Hoc Networks: A Quantitative Comparison Georgios Parissidis, Vincent Lenders, Martin May, and Bernhard Plattner Swiss Federal Institute of Technology Communications Systems Group Gloriastrasse 35, 8092 Zurich, Switzerland

4. О.П. Мартынова1, А.А.Засядько2, В.Л. Баранов3 «ПОВЫШЕНИЕ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ КОМПЬЮТЕРНЫХ СЕТЕЙ МЕТОДАМИ МНОГОКРИТЕРИАЛЬНОЙ И МНОГОПУТЕВОЙ МАРШРУТИЗАЦИИ»