Александр Азимов [email protected]


The Presentation inside:

Slide 0

Некоторые аспекты влияния сходимости протокола BGP на доступность сетевых ресурсов Александр Азимов [email protected]loadlab.com


Slide 1

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


Slide 2

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


Slide 3

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


Slide 4

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


Slide 5

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


Slide 6

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


Slide 7

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


Slide 8

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


Slide 9

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


Slide 10

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


Slide 11

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


Slide 12

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


Slide 13

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


Slide 14

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


Slide 15

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


Slide 16

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


Slide 17

Flap Damping


Slide 18

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


Slide 19

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


Slide 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:


Slide 21

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


Slide 22

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


×

HTML:





Ссылка: