Восстановление соединений сети mpls с использованием линейных диофантовых моделей Кулаков Кирилл Александрович Петрозаводский государственный университет Москва

Актуальность Использование приложений Чувствительных к задержкам Чувствительных к потере связности сети Управление маршрутами в сети Гарантированное время восстановления Обеспечение качества сервиса Учет дополнительных критериев

Сеть MPLS Мультипротокольная коммутация по меткам Уровень 2,5 в модели OSI Набор меток определяет маршрут следования пакета Наличие информации о строении сети

Задача восстановления соединения Потеря соединения Нарушение линии связи Выход из строя узла Восстановление соединения Построение обходного маршрута Переключение соединения на новый маршрут

Базовые методы (RFC 3469) По моделям Перенаправление (rerouting, после потери соединения) Защитное переключение (protection switching, до потери соединения По топологиям Локальное восстановление Глобальное восстановление

Существующие методы восстановления short leap shared protection (SLSP) Разбиение маршрута на перекрывающиеся домены Построение резервного маршрута в пределах домена Использование комбинации базовых методов MPLS local protection (Fast reroute) Построение локального резервного маршрута Быстрое восстановление

SLSP Pin-Han Ho, Hussein T. Mouftah Разбиение маршрута на домены Построение резервного маршрута в домене Восстановление только для поврежденного домена Быстрое восстановление Меньшая деградация характеристик маршрута

SLSP 1. Построить множество простых циклов графа сети 2. Для каждого домена выбрать покрывающие маршрут циклы кандидаты 3. Из множества кандидатов выбрать наилучший резервный маршрут

Пример ABCA, BCDB, ABDCA, ACDEA, ABCDEA, ACBDEA, ABDEA ABDCA, ACDEA AED Граф сети MPLS 1. Множество простых циклов 2. Множество кандидатов 3. Резервный маршрут

Текущие проблемы восстановления Построение циклов – экспоненциальная задача Учет различных ограничений Выбор оптимального маршрута «Быстрый» поиск и построение резервного маршрута

Моделирование сети MPLS Ассоциированные с формальными грамматиками системы однородных неотрицательных линейных диофантовых уравнений системы одАНЛДУ Линии связи Число попыток Исходящие линии Количество линий связи Узлы сети

Моделирование сети MPLS Решения системы одАНЛДУ базис Гильберта контуры орграфа сети MPLS Общая модель Число попыток передачи Завершение пути следования

Модель топологии Основа матрица инцидентности Каждая линия связи YZ разделяется на 2 дуги xYZ и xZY Мера всех линий связи равна 1 Поиск всех циклов сети

Пример модели 21 элемент в базисе Гильберта

Модель с обратной связью Основа модель топологии сети MPLS Отсечение дуг входящих в начальный узел и исходящих из конечного Добавление дуги связывающей конечный и начальный узлы Поиск циклов проходящих через дугу

Пример модели 5 элементов в базисе Гильберта

Модель с мерой дуг Основа модель с обратной связью Каждой дуге назначается мера (стоимость) Мера дуги равна 1 В конечном узле существует сток Поиск маршрутов с минимальной стоимостью

Пример модели 3 элемента в базисе Гильберта

Анализ эффективности Сравнение моделей с классическим вариантом

Решение Классические алгоритмы нахождения циклов

Решение Модификации алгоритмов

Решение Таблица сравнения классических и модифицированных алгоритмов