Введение 3
1. Обзор 5
1.1. Представление сети в маршрутизаторе 5
1.2. Неформальная постановка задачи 7
1.3. Алгоритмы, использующиеся современными маршрутизаторами 7
1.4. Алгоритмы поиска кратчайшего пути для многокритериального случая 8
2. Формальная постановка задачи 11
2.1. Задача поиска кратчайшего пути 11
2.2. Частная задача маршрутизации 12
2.3. Общая задача маршрутизации 12
3. Методы 14
3.1. Базовые принципы работы алгоритмов поиска кратчайшего пути 14
3.2. Методы решения задачи многокритериального поиска кратчайшего пути 16
3.2.1 NAMOA* 16
3.2.2 NAMOA*dr 17
3.2.3 BOA* 20
3.2.4 BOD 21
3.3. Маршрутизация 21
3.3.1 Случаи, когда ограниченность решения не может быть
достигнута 21
3.3.2 Метод моделирования поведения узлов 23
3.3.3 Метод жадной маршрутизации 26
4. Эксперименты 29
5. Результаты экспериментов 31
6. Заключение 33
6.1. Результаты работы 33
6.2. Дальнейшие направления исследования 33
Список литературы 35
Пользователи ожидают от них высоких пропускных способностей, стабильности соединения и предсказуемости поведения. Эти параметры сети зависят от множества факторов. Одним из ключевых является выбор алгоритма маршрутизации пакетов. Алгоритм работает на устройствах (маршрутизаторах), составляющих инфраструктуру сети и именно он определяет по какому маршруту данные попадут от одного пользователя к другому.
Пакет данных, отправленный по сети Интернет, в среднем совершает 8 переходов, чтобы добраться до конечной точки (см. рисунок №1). Каждый такой переход добавляет задержку и увеличивает риск возникновения ошибок в передаваемых данных. Поэтому важно, чтобы из всех доступных маршрутов передачи был выбран оптимальный.
Протоколы маршрутизации используют различные показатели соединения для определения наилучшего маршрута передачи данных. Но даже современные протоколы, способные учитывать несколько характеристик сети, ограничены алгоритмами поиска кратчайших путей, применяемыми в них. В современных решениях используются алгоритмы Дейкс- тры [2] или Беллмана-Форда [3], которые работают с графами, где каждое ребро описывается лишь одной величиной. В результате метрика соединений представляется как взвешенная сумма учитываемых параметров. Такая упрощенная модель может снижать точность выбора оптимального маршрута в сложных сетевых сценариях.
Появление оптимизированных версий алгоритмов многокритериального поиска кратчайшего пути открывает перспективы для их использования в протоколах маршрутизации. Целью данной ВКР является рассмотрение применимости современных алгоритмов MOSP (Multiobjective Shortest Path) для решения задачи децентрализованной маршрутизации.
Для достижения данной цели необходимо выполнить следующие задачи:
1. Провести анализ актуальных научных исследований по темам многокритериальных алгоритмов поиска кратчайшего пути, а также маршрутизации в компьютерных сетях.
2. Реализовать State of the Art MOSP алгоритмы.
3. Разработать методы решения задачи децентрализованной многокритериальной маршрутизации на основе исследованных алгоритмов.
4. Подготовить среду для тестирования и провести бенчмаркинг полученных методов.
Реализация алгоритмов в рамках данной работы предполагает создание открытого репозитория, который будет доступен другим исследователям для анализа SOTA алгоритмов. Кроме того, мы предоставляем среду для создания наборов данных для тестирования алгоритмов многокритериальной оптимизации.
В ходе выполнения работы были исследованы методы маршрутизации в компьютерных сетях, а также методы решения задачи поиска кратчайшего пути для случая одного и многих критериев поиска. Была сформулирована постановка задачи маршрутизации и критерии оценки её решения. Также было приведено доказательство невозможности нахождения ограниченного решения задачи маршрутизации при условии, что функция перехода должна зависеть только от адресата пакета.
На основе научных статей было разработано два метода маршрутизации, которые используют State of the Art алгоритмы многокритериального поиска. Первый метод основывается на моделировании поведения узлов и позволяет найти ограниченное и детерминированное решение для любой сети, но при этом требует учёта узла-отправителя при принятии решения о передаче пакета. Второй метод использует информацию только об адресате пакета, но при этом не гарантирует ограниченности и детерминированности решения в общем случае. Был подготовлен репозиторий с кодом данных методов: https://github.com/heartmarshall/decentralized- biobjective-routing. Также в репозитории были размещены разработанные для тестирования инструменты генерации тестовых карт для задачи многокритериального поиска.
Были проведены эксперименты, в результате которых были получены данные об ограниченности решений при использовании второго метода маршрутизации, а также о ресурсозатратности первого метода. Эксперименты подтвердили эффективность оптимизаций, использованных в первом методе и позволили определить оптимальную функцию выбора решения для второго метода.
