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

Содержание

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

Слайд 1Диофантовы модели сети MPLS для восстановления соединений
Кулаков Кирилл Александрович

Петрозаводский государственный университет
Москва

- 2007

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

сервиса
дополнительные критерии маршрутизации

Слайд 3Сеть MPLS
Мультипротокольная коммутация по меткам
Уровень 2,5 в модели OSI
Коммуникация вида «точка-точка»

(соединение)
Набор меток определяет маршрут следования пакета
Информация о топологии сети хранится на маршрутизаторе в виде набора маршрутов

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

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

Слайд 5Классификация методов восстановления (RFC 3469)
Подготовка восстановления
Перенаправление (rerouting, после потери соединения)
Защитное переключение

(protection switching, до потери соединения)
Масштаб восстановления
Локальное восстановление (обход точки разрыва)
Глобальное восстановление (построение нового маршрута между конечными точками)

Слайд 6Известные методы восстановления
MPLS local protection (Fast reroute)
Построение локального резервного маршрута
Быстрое восстановление
MPLS

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

Слайд 7SLSP: Обзор
Pin-Han Ho, Hussein T. Mouftah
Разбиение маршрута на домены
Построение резервного маршрута в

домене
Восстановление только для поврежденного домена
Быстрое восстановление
Меньшая деградация характеристик маршрута

Слайд 8SLSP: Алгоритм
Построить множество простых циклов графа сети
Для каждого домена выбрать покрывающие

маршрут циклы — кандидаты
Из множества кандидатов выбрать наилучший — резервный маршрут

Слайд 9SLSP: Пример
ABCA, BCDB, ABDCA,
ACDEA, ABCDEA, ACBDEA, ABDEA
ABDCA, ACDEA
AED
Граф сети MPLS


1. Множество

простых циклов

2. Множество кандидатов

3. Резервный маршрут

Слайд 10Проблемы известных методов восстановления
Построение всех простых циклов – экспоненциальный перебор
Учет дополнительных

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

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

и xBA
Вес дуги

Слайд 12Линейная диофантова модель
Ассоциированные с формальными грамматиками системы однородных неотрицательных линейных диофантовых

уравнений — системы одАНЛДУ

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

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

конечное описание всех решений
Базисные решения – кандидаты на резервные маршруты

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

простых контуров

Простейшая модель

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

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

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

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

Слайд 19Модель с мерой дуг
Каждая дуга имеет меру
Мера дуги равна

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

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

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

решения систем одАНЛДУ

Слайд 22Решение
Псевдополиномиальный алгоритм нахождения базиса Гильберта

Оценки алгоритма решения с помощью
2 алгоритмов генерации

систем одАНЛДУ
в web-системе Web-SynDic (http://websyndic.cs.karelia.ru/)

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

алгоритмов для поиска маршрутов
Использование модели для маршрутизации в других сетях

Похожие презентации

Использование заданий в форме ГИА на уроках физикив 7-9 классах 212
Работа с трудными детьми 246
ТВОИ ВОЗМОЖНОСТИ 273
Бестраншейная прокладка трубопровода с применением чугунных труб 230
Дополнение 288
Главное Идея праздника и оптимизма; Первая в Украине юмористическая радиостанция; Самая полная коллекция юмора; Яркая индивидуальность, уникальный формат. 196

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика