Моделирование поиска заданного числа оптимальных маршрутов в переограниченных случаях

9. Sahinoglu Z., Tekinay S. On Multimedia Networks: Self-Similar Traffic and Network Performance // IEEE Communications Magazine. January 1999. № 48. Р. 52.

10. Wisitpongphan N., Peha J. M. Effect of TCP on Self-Similarity of Network Traffic // Proceedings of 12th IEEE International Conference on Computer Communications and Networks (ICCCN). 2003.

11. Levakov A. K., Sokolov A. N., Sokolov N. A. Models of incoming traffic in packet networks // T-Comm. 2015. Vol. 9, № 5. Р. 91-94.

12. Зайцев В., Соколов Н. Особенности мультисервисного трафика с учетом сообщений, создаваемых устройствами IoT // Первая миля. 2017. № 4. С. 44-47.

УДК 519.179.2

МОДЕЛИРОВАНИЕ ПОИСКА ЗАДАННОГО ЧИСЛА ОПТИМАЛЬНЫХ МАРШРУТОВ

В ПЕРЕОГРАНИЧЕННЫХ СЛУЧАЯХ

MODELING MULTIPLE PATHS FOR QOS-AWARE ROUTING IN THE OVER-CONSTRAINED CASE

Е. В. Щерба, Г. А. Литвинов

Омский государственный технический университет, г. Омск, Россия

E. V. Shcherba, G. A. Litvinov

Omsk State Technical University, Omsk, Russia

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

Ключевые слова: многопутевая маршрутизация, маршрутизация с ограничениями, алгоритм Йена, булевозначные сети

DOI: 10.25206/2310-9793-7-4-226-231

I. Введение

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

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

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

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

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

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

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

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

II. Постановка задачи

Существует множество различных вариантов задачи поиска к кратчайших путей (KSP) от исходного узла s до конечного узла t в сети с неотрицательными весами дуг, каждый из которых имеет свой уровень сложности. Для KSP без ограничений, где возможен поиск путей с циклами, теоретически самым быстрым алгоритмом на сегодня является алгоритм Эппштейна [3] с временной сложностью O(m + n log n + к log к), где n - число узлов, а m - число ребер. Проблема KSP, для которой разрешены только простые пути (без циклов), намного сложнее. Алгоритм, предложенный Йеном для решения указанной проблемы [4], имеет сложность O(kn3), при условии, что для поиска одного кратчайшего пути используется классический алгоритм Дейкстры с временной сложностью O(n2). Отдельно рассматривается задача поиска к вершинно-непересекающихся или реберно-непересекающихся путей с минимальной совокупной стоимостью, для которой в работе [5] на базе алгоритма Дейкстры был предложен алгоритм с временной сложностью O(kn2).

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

Для решения задачи MCP (Multi-Constrained Path) заключается для заданной пары вершин требуется найти хотя бы один путь, все метрики которого лежат в пределах заданных ограничений, а задача MCOP (Multi-Constrained Optimal Path) состоит в том, чтобы для заданной пары вершин найти путь с наименьшей стоимостью, удовлетворяющий всем ограничениям. Указанные задачи являются NP-полными и не имеют точных эффективных алгоритмов решения [6]. Кроме того, в динамически организуемых сетях, как правило, возникают дополнительные ограничения, связанные с ожидаемым «временем жизни» маршрута, уровнем мобильности узлов, энергетическими затратами на передачу пакета и др. Таким образом, общее количество ограничений значительно возрастает, и задача MCOP в данных условиях часто становится переограниченной [7].

В работе [8] был сформулирован новый подход для решения указанных задач в переограниченном случае и предложен алгоритм для реализации указанного подхода в случае, когда все используемые метрики, кроме стоимости маршрута, являются вогнутыми. Суть указанного подхода заключается в предварительной классификации ограничений на «мягкие» и «жесткие». При этом задача MC(O)P обобщается, как задача поиска маршрутов, удовлетворяющих всем «жестким» ограничениями и максимальному количеству «мягких» ограничений одновременно. В рамках указанного подхода, для случая, когда все рассматриваемые метрики (кроме стоимости маршрута) являются вогнутыми, был предложен алгоритм для поиска заданного числа маршрутов. Указанный алгоритм представляет собой модификацию алгоритма Йена для булевозначных сетей и имеет теоретиче-

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

III. Среда моделирования

Основное назначение разработанной системы состоит в имитационном моделировании процесса выбора заданного числа оптимальных маршрутов для передачи пакета в соответствии с заданными ограничениями, отражающими требования к качеству обслуживания. Для моделирования указанного процесса на вход системы поступает топология сети, представленная посредством графа. Интерфейс системы позволяет создать данный граф в режиме реального времени, либо загрузить его из файла. Система поддерживает стандартный язык разметки графов GraphML, что позволяет сохранять совместимость с такими системами, как Gephi, yEd Graph Editor, graphonline.ru и др. Формат GraphML, используемый в системе, был расширен за счет дополнительных атрибутов в целях моделирования.

Основной этап моделирования предваряет выбор пользователем количества и наименования используемых метрик, рассматриваемых в процессе обеспечения качества обслуживания. Пользователь определяет их тип и значения данных метрик для каждого канала связи. Указанные значения используются для формирования векторной метки для каждой дуги в обрабатываемом графе. В рассматриваемом примере (рис. 1), для каждого канала связи пользователем были установлены значения четырех вогнутых маршрутных метрик: «Пропускная способность», «Безопасность», «Остаточная емкость», «Текущее время жизни».

Рис. 1. Пример поиска оптимальных маршрутов в разработанной среде моделирования

Также пользователь задает количество путей, которые необходимо найти, узел отправителя и узел получателя пакета и набор ограничений по маршрутным метрикам, отражающих требования к искомому маршруту. В рассматриваемом примере (рис. 1) был произведен поиск 7 маршрутов из узла 0 в узел 10 с ограничениями {7, 8, 9, 10} по четырем ранее заданным метрикам, причем все ограничения были заданы как мягкие, т. е. необязательные к исполнению.

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

В представленном примере (рис. 1), маршрута из узла 0 в узел 10, удовлетворяющего всем заданным ограничениям одновременно, не существует. В результате поиска было найдено 7 маршрутов, удовлетворяю-

щих максимально возможному количеству ограничений, включая маршрут Р = (0, 4, 9, 15, 14, 13, 19), удовлетворяющий ограничениям «Пропускная способность» и «Остаточная емкость». В случае изменения сетевой топологии, количества метрик или набора задаваемых ограничений требуется повторить поиск.

IV. Результаты экспериментов

Ранее нами была получена теоретическая оценка временной сложности разработанной модификации алгоритма Йена для булевозначных сетей как 0(кп4), при условии применения алгоритма поиска одного оптимального пути в булевозначной сети со сложностью 0(п3). В данной работе была произведена экспериментальная проверка полученного результата. Чтобы оценить зависимость времени, затрачиваемого на поиск к оптимальных маршрутов, от количества узлов, количества искомых маршрутов и количества ограничений, для каждого этапа моделирования были сгенерированы по 10 случайных сетей с фиксированным числом узлов и используемых маршрутных метрик. Генерация сетей производилась в соответствии с моделью Эрдеша-Реньи [9], расширенной для решения задач проекта. В рамках данной расширенной модели каждая пара узлов сети связана каналом связи, метрика ^^ которого удовлетворяет ограничению и с вероятностью р¡. Таким образом, произвольный канал удовлетворяет всем поставленным ограничениям с вероятностью р1р2...рп и не удовлетворяет ни одному ограничению с вероятностью (1 -р!) (1-р2)... (1-рп).

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

В целях экспериментальной оценки времени, затрачиваемого на поиск маршрута, были проведены три серии испытаний в случайных геометрических сетях, сгенерированных по модели Эрдеша-Реньи. В первой серии испытаний производился поиск разного количества маршрутов (1, 3, 5, 7, 9) в сетях с фиксированным количеством узлов (500), фиксированным количеством ограничений (3 и вероятностью удовлетворения ограничений (0,5). Было получено экспериментальное подтверждение линейной зависимости между количеством искомых маршрутов и временем, затрачиваемым на поиск этих маршрутов (рис. 2).

Рис. 2. Зависимость ср. времени поиска маршрутов от числа искомых маршрутов

В ходе второй серии испытаний (рис. 3) поиск маршрутов производился в сетях от 100 до 500 узлов, в условиях фиксированного количества ограничений (3), вероятности удовлетворения ограничений (0,5), при этом количество искомых маршрутов варьировалось от 1 до 9 с усреднением результатов. В ходе третьей серии испытаний (рис. 4) производился поиск маршрутов в сетях с различным количеством ограничений (от 3 до 9).

Рис. 3. Зависимость ср. времени поиска маршрутов от количества узлов сети

Рис. 4. Зависимость ср. времени поиска маршрутов от количества ограничений

V. Заключение

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

Источник финансирования. Благодарности

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 18-37-00160.

Список литературы

1. Tsai J., Moors T. A Review of Multipath Routing Protocols: From Wireless Ad Hoc to Mesh Networks // ACoRN ECR Workshop on Multihop Wireless Networks. 2006. Vol. 30. P. 1-6.

2. Шувалов В. П., Вараксина И. Ю. Классификация методов многопутевой маршрутизации // T-COMM: телекоммуникации и транспорт. 2014. Т. 8, № 1. С. 29-32.

3. Eppstein D. Finding the k shortest paths // SIAM Journal on Computing (SICOMP). 1998. Vol. 28 (2). P. 652-673.

4. Yen J. Y. Finding the k shortest loopless paths in a network // Management Science. 1971. Vol. 17 (11). P. 712-716.

5. Suurballe J. W. Disjoint Paths in a Network // Networks. 1974. Vol. 4 (2). P. 125-145.

6. Kuipers F., Mieghem P. V., Korkmaz T., Krunz M. An overview of constraint-based path selection algorithms for QoS routing // IEEE Communications Magazine. 2002. Vol. 40 (12). P. 50-55.

7. Щерба Е. В., Литвинов Г. А., Щерба М. В. Задача обеспечения качества обслуживания на базе протокола маршрутизации OLSR: подходы, алгоритмы, решения // Доклады ТУСУР. 2019. Т. 22, № 1. С. 55-65.

8. Shcherba E. V., Litvinov G. A. On an optimal solution for multi-constrained routing problem in the over-constrained case // In Proc. of 2018 Moscow Workshop on Electronic and Networking Technologies. 2018. P. 1-5.

9. Erdos P., Rényi A. On the Evolution of Random Graphs // Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 1960. Vol. 5. P. 17-61.