'

Александр Азимов aa@highloadlab.com

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





Слайд 0

Некоторые аспекты влияния сходимости протокола BGP на доступность сетевых ресурсов Александр Азимов aa@highloadlab.com


Слайд 1

Автономные системы AS1 AS2 AS3 AS1 AS2 AS3 AS1 AS2


Слайд 2

Протокол BGP Border Gateway Protocol (RFC 1771, 4271) Де-факто стандартный протокол внешней маршрутизации Дистанционно-векторный протокол Политика маршрутизации Набор атрибутов маршрутов LOCAL_PREF AS_PATH …


Слайд 3

Политика маршрутизации 200 100 AS1 AS2 AS3 100 200


Слайд 4

Формальная модель Представим модель сети автономных систем, как ориентированный граф ?? ??, ?? : V – автономные системы ???? 1 , ???? 2 ??? тогда и только тогда, когда АС ???? 1 будет анонсировать маршрут к префиксу I BGP АС ???? 2 Вес дуги состоит из двух частей: Prepend – политика AS_PATH АС ???? 1 Pref – политика LOCAL_PREF ???? 2 Pref = 100 AS1 AS2 Prepend = 2


Слайд 5

Транзитные АС Пусть ??????????? – множество, состоящие из всех существующих значений атрибута маршрута BGP AS_PATH в текущий момент времени. Тогда признаком транзитной автономной системы будет: ?????????????????????-????????????????????, ???< ??????? : ??= ??????? ??


Слайд 6

«Ядро» Интернета Множество транзитных АС неоднородно: Пропускают только трафик клиентов Имеют пиринговые отношения с соседями ?????????? 0 =?????????????? ?????????? ??+1 = ????????????? ?? | ????????????????????, ???<??< ??????? : ??= ??????? ?? & ??????? ?? ??????????? ?? lim ??>? ?????????? ?? = CORE


Слайд 7

Пример нахождения CORE ??????????????={ ???? 2 , ???? 3 , ???? 4 , ???? 5 , ???? 6 } ???????? 1 ={ ???? 3 , ???? 4 , ???? 5 } ???????? 2 ={ ???? 3 , ???? 4 }=???????? AS3 AS2 AS4 AS5 AS1 AS6 AS7


Слайд 8

Свойства CORE Лемма Предел lim ??>? ?????????? ?? существует и отличен от пустого множества. ?? ? ?? ? , ?? ? ??? ??,?? : ???? ?? ? >???????????, ? ?? 1 , ?? 2 ? ?? ? >max? ???????? ?? ?? , ?? 2 =???????? ?? 1 , ?? 2 Теорема Для любой вершины в графе ?? ? существует путь из вершины Origin.


Слайд 9

Прикладное применение Хостингам: выбор сервис провайдера Reverse Traceroute Обнаружение LOCAL_PREF циклов Определение времени сходимости Моделирование механизмов самого BGP


Слайд 10

Время сходимости Псевдо-транзитные АС AS1 AS2 AS3 10 АС до CORE = До 5 минут задержки AS1 AS2 AS3 Являются ли AS1 и AS2 транзитными? AS3 многоинтерфейсная? AS4


Слайд 11

Reverse Traceroute АС – единая политика маршрутизации Reverse Traceroute – знание, как к тебе идет трафик от других АС Если знать, как идет трафик, можно его балансировать – profit!


Слайд 12

LOCAL_PREF циклы Причина сетевой нестабильности для целевого префикса Создание постоянного «шума» из BGP сообщений Замедление времени сходимости по всей сети АС AS3 AS2 AS4 AS5 AS1 AS6 AS7


Слайд 13

Время сходимости Рассматриваемые события: Объявление маршрута к префиксу I автономной системой X Удаление маршрута к префиксу I автономной системой Х ?? ?? ???? = ?? ????? ?? ???????? , где d – диаметр относительно вершины Х в графе G ?? ?? ???????? = ?? ????? ?? ???????? , где D – длина гамильтонова пути относительно вершины Х в графе G


Слайд 14

Система моделирования


Слайд 15

Проверка распределений Удаление маршрута Объявление маршрута ?? 1 2 ?????? ?? ???( ?? ???????? )????? ???????? ? ?? ?????? ?? ??? ?? ???????? +?? ?? max? ?? ???( ?? ???????? )????? ???? ? ?? max? ?? ??? ?? ???????? +??


Слайд 16

Flap Damping Зачем? Снижение нагрузки на сеть BGP маршрутизаторов от нестабильных маршрутов, не оказывая влияния на время сходимости в стабильных участках сети.


Слайд 17

Flap Damping


Слайд 18

Flap Damping Вероятность появления мигающего маршрута в кольце маршрутизаторов длины n: 2? Ф 7? 3 ??+1 ?Ф 2? 3 ??+1 , при ?? четном, 2? Ф 6? 3 ??+1 ?Ф 3 ??+1 , при ?? нечетном


Слайд 19

Flap Damping DoS? Yes! Не блокируется ни одним существующим расширением BGP S-BGP


Слайд 20

Данные для экспериментов List of router registries http://www.irr.net/docs/list.html BGP dumps http://www.ripe.net/projects/ris/rawdata.html Автономных систем: 36200 Транзитных систем: 5876 CORE: 1757 Prepends:


Слайд 21

Результаты Разработана модель BGP маршрутизации Сформулированы оценки времени сходимости протокола BGP Разработана система моделирования для проверки теоретических оценок Рассмотрены механизмы BGP LOCAL_PREF и Flap Damping и их влияние на доступность сетевых ресурсов Предложен метод для построения Reverse Traceroute


Слайд 22

Спасибо за внимание! Вопросы?


×

HTML:





Ссылка: