'

Диофантовы модели сети MPLS для восстановления соединений

Понравилась презентация – покажи это...





Слайд 0

Диофантовы модели сети MPLS для восстановления соединений Кулаков Кирилл Александрович Петрозаводский государственный университет Москва - 2007


Слайд 1

Актуальность Специфика сетевых приложений чувствительные к задержкам чувствительные к изменениям топологии Управление маршрутами гарантированное время восстановления качество сервиса дополнительные критерии маршрутизации


Слайд 2

Сеть MPLS Мультипротокольная коммутация по меткам Уровень 2,5 в модели OSI Коммуникация вида «точка-точка» (соединение) Набор меток определяет маршрут следования пакета Информация о топологии сети хранится на маршрутизаторе в виде набора маршрутов


Слайд 3

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


Слайд 4

Классификация методов восстановления (RFC 3469) Подготовка восстановления Перенаправление (rerouting, после потери соединения) Защитное переключение (protection switching, до потери соединения) Масштаб восстановления Локальное восстановление (обход точки разрыва) Глобальное восстановление (построение нового маршрута между конечными точками)


Слайд 5

Известные методы восстановления MPLS local protection (Fast reroute) Построение локального резервного маршрута Быстрое восстановление MPLS global path protection Построение глобального резервного маршрута Short Leap Shared Protection (SLSP) Разбиение маршрута на перекрывающиеся участки Построение резервного маршрута в пределах участка


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

Орграф сети MPLS Узел – вершина Линия связи AB – две дуги xAB и xBA Вес дуги


Слайд 11

Линейная диофантова модель Ассоциированные с формальными грамматиками системы однородных неотрицательных линейных диофантовых уравнений — системы одАНЛДУ


Слайд 12

Вес дуги Число попыток передачи Коэффициент загруженности Число переходов Приоритет линии связи Источник Сток Недостижимый узел Интерпретация модели


Слайд 13

Интерпретация решений Решение системы одАНЛДУ = циклический маршрут Множество всех решений Базис Гильберта – конечное описание всех решений Базисные решения – кандидаты на резервные маршруты


Слайд 14

Основа – матрица инцидентности Вес дуг Базисное решение – простой контур Поиск всех простых контуров Простейшая модель


Слайд 15

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


Слайд 16

Фиктивная дуга Наличие начального и конечного узла Удаление неиспользуемых дуг Добавление дуги связывающей конечный узел с начальным Поиск контуров проходящих через дугу Базисное решение – простой контур


Слайд 17

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


Слайд 18

Модель с мерой дуг Каждая дуга имеет меру Мера дуги равна 1 В конечном узле существует сток Поиск маршрутов с минимальной мерой Базисное решение – циклический маршрут


Слайд 19

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


Слайд 20

Преимущества модели Орграф сети Меры дуг Учет дополнительных ограничений Поиск базисных решений – кандидатов Известные алгоритмы решения систем одАНЛДУ


Слайд 21

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


Слайд 22

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


×

HTML:





Ссылка: