1 ВОССТАНОВЛЕНИЕ МАРШРУТОВ В ОПОРНЫХ ИНФРАСТРУКТУРАХ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ НА БАЗЕ MPLS Кулаков Кирилл Александрович Корзун Дмитрий Жоржевич Богоявленский Юрий Анатольевич Петрозаводский государственный университет XIV Всероссийская научно-методическая конференция "Телематика'2007" г.Санкт-Петербург, 2007

2 Актуальность Приложения: Чувствительные к задержкам Чувствительные к потере связности Требования: Гарантированное время восстановления Учет дополнительных критериев число переходов загруженность линий связи и узлов

3 Восстановление соединений Сеть MPLS (мультипротокольная коммутация по меткам): управление маршрутами пакетов с помощью меток Потеря соединения: нарушение линии связи или выход из строя узла Задача построения обходного маршрута (поиск маршрута) Задача переключения соединения на новый маршрут (активация маршрута)

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

5 Локальное восстановление Преимущества Максимальное сохранение старого маршрута Быстрое восстановление Недостатки Ухудшение характеристик после нескольких восстановлений (локальная оптимизация)

6 Глобальное восстановление Преимущества Построение наилучших маршрутов Независимость от истории Недостатки Вычислительная сложность

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

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

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

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

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

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

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

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

15 Алгоритмы решения систем одАНЛДУ Псевдополиномиальный алгоритм нахождения базиса Гильберта Оценки алгоритма решения с помощью 2 алгоритмов генерации систем одАНЛДУ в web-системе Web-SynDic ( )

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

17 Заключение Диофантовы модели сети MPLS Более общий метод – учет дополнительных условий Применение эффективных алгоритмов для поиска маршрутов Использование модели для маршрутизации в других сетях

18 Спасибо за внимание!