Кулаков Кирилл Александрович Корзун Дмитрий Жоржевич Богоявленский Юрий Анатольевич Петрозаводский государственный университет


Презентация изнутри:

Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


×

HTML:





Ссылка: