Динамическая маршрутизация внутри автономной системы: RIP и OSPF

В теме 8 маршрутизатор рассматривался как устройство, которое для каждого пакета находит в таблице маршрутизации запись с наибольшим совпадением префикса и пересылает пакет следующему переходу. Откуда берутся сами записи, там решалось просто: администратор вписывал их вручную командами ip route add. Для трёх маршрутизаторов в треугольнике это работает, но уже в той же лабораторной работе обнаружились слабые места статической маршрутизации: резервный путь приходилось заранее описывать «плавающим» маршрутом, а ошибка в одной записи порождала петлю, которую обрывал только счётчик TTL. Сеть из сотни маршрутизаторов, где каналы время от времени отказывают, вручную поддерживать невозможно.

Динамическая маршрутизация передаёт эту работу самим маршрутизаторам. Они обмениваются сообщениями протокола маршрутизации (англ. routing protocol), по этим сообщениям вычисляют пути и сами записывают результат в таблицу. Задача формулируется как классическая задача теории графов — поиск кратчайших путей, — но решается в необычных условиях: граф распределён по многим устройствам, никто не видит его целиком в момент изменения, а сообщения задерживаются и теряются. Именно эти условия, а не математика кратчайших путей, определяют устройство протоколов и их типичные проблемы.

Тема посвящена маршрутизации внутри одной организации, или автономной системы. Сначала задача формулируется на языке графов. Затем рассматриваются два семейства алгоритмов: дистанционно-векторные на основе уравнения Беллмана — Форда с протоколом RIP в качестве примера и алгоритмы состояния каналов на основе алгоритма Дейкстры с протоколом OSPF. Оба алгоритма разбираются по шагам на одной и той же учебной топологии, которая затем используется в лабораторной работе. Последний раздел посвящён тому, что превращает алгоритм в работающую сеть: областям, сходимости, обнаружению отказов и обмену маршрутами между протоколами. Маршрутизация между автономными системами — предмет темы 10.

Задача динамической маршрутизации

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

Как было показано в теме 8, в маршрутизаторе различают две плоскости. Плоскость данных (англ. data plane) пересылает пакеты по готовой таблице и должна работать со скоростью канала. Плоскость управления (англ. control plane) строит эту таблицу и может работать гораздо медленнее — за миллисекунды и секунды. Протокол маршрутизации целиком принадлежит плоскости управления: его сообщения не переносят пользовательский трафик, а описывают сеть. Результат его работы попадает сначала в таблицу маршрутов протокола, затем в общую базу маршрутов RIB (англ. Routing Information Base) и оттуда в таблицу пересылки FIB (англ. Forwarding Information Base) ядра.

В программном маршрутизаторе FRRouting, который используется в лабораторных работах курса, это разделение видно буквально: протоколы работают отдельными процессами (ripd, ospfd, bgpd), каждый передаёт свои лучшие маршруты процессу zebra, а тот выбирает среди маршрутов разных протоколов и устанавливает победителей в таблицу маршрутизации ядра Linux через интерфейс netlink ⁹. Когда к одному префиксу ведут маршруты от разных источников, выбор делается по административному расстоянию, знакомому по теме 8: в FRR у статического маршрута оно равно 1, у OSPF — 110, у RIP — 120. Внутри одного протокола сравниваются уже метрики.

От протокола маршрутизации требуется несколько свойств. Он должен находить пути, оптимальные по выбранному критерию; быстро перестраивать их после отказа или восстановления канала, то есть обладать малым временем сходимости (англ. convergence); не создавать петель даже в переходных состояниях или хотя бы ограничивать их время; масштабироваться на сотни и тысячи маршрутизаторов, не перегружая каналы и процессоры служебным трафиком. Эти требования противоречат друг другу, и каждый протокол представляет собой компромисс между ними.

Сеть как взвешенный граф

Для протокола маршрутизации сеть — это граф. Вершины (англ. nodes) — маршрутизаторы, рёбра — каналы между ними, а каждому ребру приписан вес, или стоимость (англ. cost). Стоимость пути равна сумме стоимостей его рёбер, и задача маршрутизации — для каждой пары вершин найти путь наименьшей стоимости. Сети назначения, к которым подключены хосты, изображаются либо отдельными вершинами, либо «листьями» маршрутизаторов; для алгоритма это не важно.

Что именно выражает стоимость, решает протокол или администратор. Простейшая метрика — число переходов (англ. hop count): каждое ребро весит 1, и лучшим считается путь через наименьшее число маршрутизаторов. Так устроен RIP. Метрика, учитывающая пропускную способность, назначает медленным каналам больший вес: в OSPF стоимость интерфейса по умолчанию вычисляется как отношение опорной скорости к скорости канала, и путь из двух каналов по 1 Гбит/с оказывается лучше одного канала 100 Мбит/с. Встречаются и метрики, учитывающие задержку, — их использовал, например, алгоритм маршрутизации ARPANET 1980 года, где вес канала пересчитывался по измеренной задержке пакетов ¹³. Опыт ARPANET показал и опасность такого подхода: если вес зависит от нагрузки, трафик уходит с загруженного канала на свободный, загружает его, и маршруты начинают колебаться. Поэтому в современных внутренних протоколах стоимость — статическая величина, которую задаёт администратор.

Учебная топология, используемая в разделах ниже и в лабораторной работе, показана на рисунке. Пять маршрутизаторов r1–r5 соединены шестью каналами; у каждого канала своя подсеть /24, а у каждого маршрутизатора — адрес на интерфейсе обратной связи (англ. loopback) 10.255.0.N/32, который служит ему именем.

Автономная система и внутренние протоколы

Интернет состоит из десятков тысяч сетей, принадлежащих разным организациям, и единый протокол маршрутизации для него невозможен ни технически, ни организационно. Поэтому маршрутизация разделена на два уровня. Автономная система (англ. autonomous system, AS) — совокупность сетей под единым административным управлением с единой политикой маршрутизации: сеть провайдера, университета, крупной компании. Внутри AS работает внутренний протокол маршрутизации (англ. Interior Gateway Protocol, IGP), задача которого — найти кратчайшие пути быстро и надёжно; владелец сети доверяет всем своим маршрутизаторам и сам назначает стоимости. Между автономными системами работает внешний протокол (англ. Exterior Gateway Protocol, EGP), в современном Интернете это BGP, и его главная задача — не кратчайший путь, а соблюдение договорных и экономических отношений между организациями. Внешней маршрутизации посвящена тема 10.

К внутренним протоколам относятся RIP, OSPF, IS-IS и фирменный EIGRP компании Cisco. Их можно разделить по алгоритму на два семейства, и это разделение — главная идея темы.

Два семейства алгоритмов

Алгоритмы маршрутизации различаются прежде всего тем, какой информацией о графе располагает каждый маршрутизатор ⁴. В децентрализованном, или дистанционно-векторном (англ. distance vector), алгоритме маршрутизатор знает лишь стоимости своих каналов к соседям и то, что соседи сообщают о своих расстояниях до всех сетей. Ни один маршрутизатор не видит граф целиком; кратчайшие пути возникают в результате итеративного обмена, как решение уравнения, которое все участники решают сообща. В алгоритме состояния каналов (англ. link state) каждый маршрутизатор рассылает всем остальным описание своих каналов, в результате у всех оказывается одна и та же полная карта сети, и каждый вычисляет кратчайшие пути самостоятельно, централизованным алгоритмом.

Из этого различия вытекают все остальные. Дистанционно-векторный протокол прост, требует мало памяти и вычислений, но сходится медленно и в переходных состояниях может создавать петли. Протокол состояния каналов сложнее, требует памяти под карту и процессорного времени на её обработку, зато сходится быстро и предсказуемо. Обе идеи появились в ARPANET: исходный алгоритм маршрутизации 1969 года был дистанционно-векторным, а в 1980 году его заменили алгоритмом состояния каналов именно из-за проблем со сходимостью и петлями ¹³.

Дистанционно-векторная маршрутизация

Уравнение Беллмана — Форда

Обозначим через D_x(y) стоимость кратчайшего пути от узла x до узла y, через c(x,v) — стоимость канала от x к соседу v. Кратчайший путь от x к y обязательно начинается с какого-то соседа v, а продолжается кратчайшим путём от v до y, иначе его можно было бы укоротить. Отсюда уравнение Беллмана — Форда ⁵:

D_x(y) = \min_{v} \big( c(x, v) + D_v(y) \big)

где минимум берётся по всем непосредственным соседям v узла x.

Уравнение замечательно тем, что для вычисления своего расстояния узлу x нужны лишь стоимости собственных каналов и расстояния, известные соседям. Сосед, на котором достигается минимум, и есть следующий переход (англ. next hop) — ровно то, что требуется записать в таблицу маршрутизации. Р. Беллман опубликовал этот подход в 1958 году как метод решения задачи о маршруте в графе ⁵; независимо к тому же алгоритму пришли Л. Форд и Э. Мур, отсюда двойное имя.

Вектор расстояний (англ. distance vector) узла x — это его текущие оценки D_x(y) до всех известных назначений. В распределённом алгоритме каждый узел хранит свой вектор и последние полученные векторы соседей, периодически или при изменении сообщает свой вектор соседям, а получив вектор соседа, пересчитывает собственный по уравнению. Если вектор изменился, узел рассылает его дальше. Доказано, что при неизменной топологии и положительных стоимостях такой асинхронный процесс сходится к истинным кратчайшим расстояниям при любом порядке обменов ⁴¹¹.

Распределённый алгоритм на учебной топологии

Проследим работу алгоритма на учебной топологии, начиная с момента, когда все маршрутизаторы одновременно включились. Будем считать обмен синхронным: в каждом раунде все узлы рассылают векторы соседям, затем все пересчитывают свои векторы. Перед первым раундом каждый узел знает только себя. Вектор узла r1 по раундам приведён в таблице; запись 4 (r2) означает «расстояние 4, следующий переход r2».

Таблица иллюстрирует две особенности. Во-первых, хорошие новости распространяются по сети со скоростью один переход за раунд: о пути до r4 стоимостью 7, проходящем через четыре канала, r1 узнаёт только в четвёртом раунде. Во-вторых, промежуточные результаты неоптимальны: в раунде 2 маршрутизатор использует путь до r4 стоимостью 8 через прямой канал r2—r4, хотя существует более дешёвый. Пакеты при этом доставляются, но не лучшим путём. Итоговые маршруты совпадают с результатом алгоритма Дейкстры, который будет получен в разделе о состоянии каналов. Таблицу можно воспроизвести учебным скриптом spf.py из окружения лабораторной работы:

python3 spf.py dv topology.txt --node r1

Сходимость с нуля (режим simple), узлы r1
раунд  1 | r1: r2=2(r2) r3=5(r3) r4=∞ r5=∞
раунд  2 | r1: r2=2(r2) r3=4(r2) r4=8(r2) r5=6(r3)
раунд  3 | r1: r2=2(r2) r3=4(r2) r4=8(r2) r5=5(r2)
раунд  4 | r1: r2=2(r2) r3=4(r2) r4=7(r2) r5=5(r2)
раунд  5 | r1: r2=2(r2) r3=4(r2) r4=7(r2) r5=5(r2)
сошлось: раунд 5 ничего не изменил

Счёт до бесконечности

Хорошие новости распространяются быстро, плохие — медленно, и в этом главный недостаток дистанционно-векторного подхода. Рассмотрим цепочку из трёх маршрутизаторов a—b—c с единичными стоимостями. После сходимости b достигает c за 1, а a — за 2 через b. Пусть канал b—c отказал. Маршрутизатор b обнаруживает это и помечает c недостижимым. Но если прежде, чем b успеет сообщить об этом, он получит очередной вектор от a, где по-прежнему записано «до c — 2», то по уравнению Беллмана — Форда b получит новый маршрут: до c — 1 + 2 = 3 через a. Маршрутизатор b не может знать, что путь a к c проходил через него самого: вектор расстояний сообщает только числа, но не пути.

Дальше процесс повторяется. Узел a получает от b расстояние 3 и обновляет свой маршрут: 4 через b. Узел b получает 4 и записывает 5 через a, и так далее. Метрики растут на 2 за каждый обмен, а пакеты для c всё это время бегают по петле a—b—a, пока не истечёт их TTL. Явление называется счётом до бесконечности (англ. count to infinity). Если бы в сети существовал другой, длинный путь до c, счёт остановился бы, когда метрика петли превысила его стоимость; если пути нет вовсе, счёт продолжается неограниченно. Единственная защита в самом алгоритме — объявить некоторое конечное число «бесконечностью». В RIP бесконечность равна 16 ¹, и рисунок ниже показывает, как два маршрутизатора доходят до неё: у a метрика достигает 16 на седьмом обмене, у b — на восьмом.

Время счёта зависит от периода обмена. В RIP векторы рассылаются раз в 30 секунд, и до восьми обменов без дополнительных механизмов заняли бы минуты, в течение которых сеть до c не просто недоступна, а образует петлю, нагружающую каналы. Небольшое значение бесконечности в RIP — прямое следствие этой проблемы: чем больше бесконечность, тем дольше счёт. Плата за малое значение — ограничение диаметра сети: путь длиннее 15 переходов в RIP непредставим.

Расщепление горизонта, отравленный обратный маршрут и триггерные обновления

Петлю из двух узлов устраняет правило расщеплённого горизонта (англ. split horizon): маршрутизатор не сообщает соседу о маршрутах, которые сам проложил через этого соседа ¹. В примере a достигает c через b, поэтому в векторе, отправляемом b, назначения c нет вовсе, и после отказа канала b не может «подхватить» устаревший путь. Усиленный вариант — расщеплённый горизонт с отравленным обратным маршрутом (англ. split horizon with poisoned reverse): такой маршрут не умалчивается, а сообщается соседу с метрикой 16, «недостижимо». Отравление надёжнее простого умолчания, потому что явно разрушает возможную петлю, а не ждёт, пока устаревшая запись истечёт по таймеру; цена — более длинные сообщения ².

python3 spf.py dv chain.txt --fail b-c --split-horizon none --sequential --node a,b
python3 spf.py dv chain.txt --fail b-c --split-horizon simple --sequential --node a,b

Обрыв канала b-c
раунд  0 | a: b=1(b) c=2(b) | b: a=1(a) c=∞
раунд  1 | a: b=1(b) c=4(b) | b: a=1(a) c=3(a)
раунд  2 | a: b=1(b) c=6(b) | b: a=1(a) c=5(a)
...
раунд  7 | a: b=1(b) c=∞ | b: a=1(a) c=15(a)
раунд  8 | a: b=1(b) c=∞ | b: a=1(a) c=∞
...
Обрыв канала b-c
раунд  0 | a: b=1(b) c=2(b) | b: a=1(a) c=∞
раунд  1 | a: b=1(b) c=∞ | b: a=1(a) c=∞

Расщеплённый горизонт не решает проблему полностью. Если три маршрутизатора образуют кольцо, а сеть назначения подключена к одному из них, после отказа возможна петля из трёх узлов: x узнаёт о маршруте от y, который проложил его через z, а z — через x; правило запрещает сообщать маршрут только тому соседу, через которого он проложен, а здесь каждый сообщает маршрут «третьему». В такой ситуации снова спасает только конечная бесконечность ¹¹.

Два других механизма ускоряют распространение плохих новостей. Триггерное обновление (англ. triggered update) — немедленная рассылка изменившейся записи, не дожидаясь очередного 30-секундного периода; RIPv2 требует отправлять такие обновления с небольшой случайной задержкой от 1 до 5 секунд, чтобы волна обновлений не захлестнула сеть ². Удержание (англ. hold-down) — период, в течение которого маршрутизатор после пометки маршрута недостижимым не принимает о нём сведений с худшей метрикой; механизм реализован у ряда производителей и упоминается в RFC 1058 (разд. 2.2.2), но не стандартизован и в FRR не используется.

Протокол RIP

Сообщения и формат записи

Протокол маршрутной информации (англ. Routing Information Protocol, RIP) — прямое воплощение распределённого алгоритма Беллмана — Форда. Он происходит из протокола GWINFO системы Xerox XNS и программы routed в BSD UNIX и был описан как стандарт в RFC 1058 в 1988 году, задним числом относительно уже широко распространённых реализаций ¹. Вторая версия, RIPv2, описанная в RFC 2453, добавила маску подсети в каждую запись (первая версия была классовой и масок не передавала), адрес следующего перехода, метку маршрута и аутентификацию; для IPv6 существует RIPng ².

Сообщения RIP передаются в датаграммах UDP на порт 520 от порта 520. Первая версия рассылала их широковещательно, RIPv2 — на групповой адрес 224.0.0.9, который слушают только маршрутизаторы RIP. Сообщение состоит из заголовка длиной 4 байта и до 25 записей о маршрутах по 20 байт; большая таблица передаётся несколькими сообщениями. Поля записи RIPv2 перечислены в таблице.

Метрика RIP — число переходов: маршрутизатор, получив запись с метрикой m от соседа, увеличивает её на стоимость входного интерфейса, по умолчанию на 1. Так выглядит ответ RIPv2 в выводе tcpdump с подробным разбором (адреса — из учебной топологии):

IP 10.0.12.2.520 > 224.0.0.9.520: RIPv2, Response, length: 64, routes: 3 or less
  AFI IPv4,      10.0.23.0/24, tag 0x0000, metric: 1, next-hop: self
  AFI IPv4,      10.0.24.0/24, tag 0x0000, metric: 1, next-hop: self
  AFI IPv4,     10.255.0.2/32, tag 0x0000, metric: 1, next-hop: self

Длина 64 байта — это 4 байта заголовка и три записи по 20 байт. Заметим, что r2 не сообщает r1 о сети 10.0.12.0/24, общей для них, и о маршрутах, проложенных через r1: действует расщеплённый горизонт.

Таймеры и жизненный цикл маршрута

Поведение RIP во времени задают три таймера ². Каждые 30 секунд маршрутизатор рассылает соседям полную таблицу (англ. update timer); чтобы обновления разных маршрутизаторов не синхронизировались, период слегка случайно варьируется. Если о маршруте 180 секунд не поступало сведений (англ. timeout), он считается устаревшим: метрика устанавливается в 16, маршрут удаляется из таблицы пересылки, но ещё 120 секунд (англ. garbage-collection timer) продолжает объявляться соседям как недостижимый, чтобы плохая новость наверняка до них дошла. Только после этого запись удаляется окончательно. Получается, что при молчаливом отказе соседа (канал физически «поднят», но маршрутизатор завис) RIP обнаруживает проблему только через три минуты.

В FRR протокол RIP настраивается командами, похожими на OSPF; таймеры по умолчанию задаются командой timers basic 30 180 120, а текущее состояние показывает show ip rip:

r1# show ip rip
Codes: R - RIP, C - connected, S - Static, O - OSPF, B - BGP
Sub-codes:
      (n) - normal, (s) - static, (d) - default, (r) - redistribute,
      (i) - interface

     Network            Next Hop         Metric From            Tag Time
C(i) 10.0.12.0/24       0.0.0.0               1 self              0
C(i) 10.0.13.0/24       0.0.0.0               1 self              0
R(n) 10.0.23.0/24       10.0.12.2             2 10.0.12.2         0 02:51
R(n) 10.0.24.0/24       10.0.12.2             2 10.0.12.2         0 02:51
R(n) 10.0.35.0/24       10.0.13.3             2 10.0.13.3         0 02:47
...

Столбец Time — оставшееся время до истечения 180-секундного таймера: при каждом обновлении от соседа он сбрасывается к 3:00. Метрика непосредственно подключённой сети равна 1, а не 0: в RIP стоимость входного интерфейса прибавляется уже при включении сети в таблицу.

Ограничения и область применения RIP

Ограничения RIP следуют из алгоритма. Диаметр сети не превышает 15 переходов. Метрика не учитывает скорости каналов: путь через два канала по 10 Гбит/с проигрывает одному каналу 10 Мбит/с. Периодическая рассылка полной таблицы расходует полосу пропорционально размеру таблицы, даже когда ничего не меняется. Сходимость после отказа измеряется десятками секунд при триггерных обновлениях и минутами при молчаливом отказе соседа, а в переходный период возможны петли.

Тем не менее RIP не исчез. Он прост в настройке, поддерживается практически любым оборудованием, включая бытовые маршрутизаторы, и вполне пригоден для маленьких сетей без резервных путей. Кроме того, он остаётся лучшим учебным примером: на нём видны все проблемы распределённого алгоритма в чистом виде. В производственных сетях организаций его место заняли OSPF и IS-IS, к которым мы переходим.

Маршрутизация по состоянию каналов

Идея: у каждого маршрутизатора полная карта

Протокол состояния каналов решает задачу в два независимых этапа. Сначала каждый маршрутизатор описывает своё непосредственное окружение: с какими соседями он соединён, какой стоимостью обладает каждый канал, какие сети к нему подключены. Это описание называется объявлением о состоянии каналов (англ. link-state advertisement, LSA). Маршрутизатор рассылает свои объявления всем маршрутизаторам сети — не только соседям, — и каждый собирает полученные объявления в базу данных состояния каналов (англ. link-state database, LSDB). Если рассылка работает правильно, базы всех маршрутизаторов одинаковы и представляют собой полный граф сети. На втором этапе каждый маршрутизатор независимо запускает над своей копией графа алгоритм поиска кратчайших путей и строит дерево кратчайших путей с собой в корне.

Важное отличие от дистанционно-векторного подхода: маршрутизатор распространяет не результаты своих вычислений («до сети X мне 5»), а исходные данные («у меня есть канал к Y стоимостью 2»). Ошибка или устаревшие сведения одного маршрутизатора не складываются с ошибками другого, как в цепочке a—b выше, потому что никто не строит свои выводы на чужих выводах. Расплата — объём: база содержит описание каждого маршрутизатора и каждого канала сети.

Алгоритм Дейкстры: пошаговый пример

Кратчайшие пути от одной вершины в графе с неотрицательными весами вычисляет алгоритм Э. Дейкстры, опубликованный в 1959 году ⁶. В маршрутизаторах его называют SPF (англ. Shortest Path First). Алгоритм поддерживает множество вершин, расстояние до которых уже известно окончательно, и для остальных вершин — текущие оценки расстояния. На каждом шаге:

1. среди вершин, не вошедших в окончательное множество, выбирается вершина u с наименьшей оценкой, и её оценка объявляется окончательной;
2. для каждого соседа v вершины u, ещё не закреплённого, проверяется, не короче ли путь через u: если D(u) + c(u,v) < D(v), оценка D(v) уменьшается, а первым переходом к v становится первый переход к u; эта операция называется релаксацией (англ. relaxation);
3. шаги повторяются, пока не будут закреплены все достижимые вершины.

Правильность алгоритма опирается на неотрицательность весов: если u имеет наименьшую оценку среди незакреплённых вершин, никакой путь через ещё не закреплённые вершины не может оказаться короче, потому что он уже в своей первой незакреплённой вершине стоит не меньше D(u), а дальше только дорожает. Для маршрутизатора важен не столько сам путь, сколько первый переход на нём, поэтому вместе с оценкой хранится сосед корня, через которого путь начинается.

Выполним алгоритм для маршрутизатора r1 на учебной топологии. В таблице на каждом шаге указаны оценки расстояний и первые переходы; звёздочкой отмечены закреплённые вершины.

На шаге 0 закрепляется корень, а его соседи получают оценки по стоимостям прямых каналов: r2 — 2, r3 — 5. На шаге 1 наименьшую оценку имеет r2; релаксация его каналов улучшает оценку r3 с 5 до 2 + 2 = 4 (теперь первый переход — r2, а не прямой канал) и даёт первую оценку r4: 2 + 6 = 8. На шаге 2 закрепляется r3 с расстоянием 4, его канал к r5 даёт оценку 4 + 1 = 5. На шаге 3 закрепляется r5, и через него путь к r4 стоит 5 + 2 = 7 < 8 — оценка снова улучшается. На шаге 4 закрепляется последняя вершина. Все маршруты r1 идут через r2; прямой канал к r3 стоимостью 5 не используется вовсе, потому что обход через r2 стоит 4. Получившееся дерево кратчайших путей изображено на рисунке.

Результаты совпадают с полученными распределённым алгоритмом Беллмана — Форда: оба алгоритма решают одну задачу и при неизменной топологии приходят к одному ответу. Различается путь к нему: Дейкстра выполняет пять шагов локально за микросекунды, а распределённому алгоритму понадобились четыре раунда обмена по сети. Если две вершины имеют равные оценки через разных соседей, маршрутизатор сохраняет оба первых перехода и делит трафик между ними — так возникают равноценные многопутевые маршруты (англ. Equal-Cost Multi-Path, ECMP), о которых шла речь в теме 8. Таблицу шагов печатает учебный скрипт:

python3 spf.py dijkstra topology.txt r1

шаг  закреплён           r2          r3          r4          r5
---------------------------------------------------------------
  0  r1                2/r2        5/r3           ∞           ∞
  1  r2               2/r2*        4/r2        8/r2           ∞
  2  r3               2/r2*       4/r2*        8/r2        5/r2
  3  r5               2/r2*       4/r2*        7/r2       5/r2*
  4  r4               2/r2*       4/r2*       7/r2*       5/r2*

Вычислительная сложность алгоритма Дейкстры с двоичной кучей — O((V + E) log V) для графа из V вершин и E рёбер. Для области OSPF из нескольких сотен маршрутизаторов расчёт занимает доли миллисекунды на современном процессоре, поэтому вычисление давно перестало быть узким местом; время сходимости определяется обнаружением отказа и рассылкой объявлений.

Надёжная лавинная рассылка

Чтобы базы всех маршрутизаторов совпадали, объявления должны доходить до каждого маршрутизатора, причём доходить надёжно и в правильном порядке. Для этого служит лавинная рассылка (англ. flooding): получив объявление, маршрутизатор проверяет, новее ли оно имеющейся копии; если новее — записывает в базу, подтверждает получение и пересылает во все интерфейсы, кроме того, откуда оно пришло; если не новее — только подтверждает, а если полученная копия старее имеющейся — отправляет соседу свою, более новую. Каждая отправка подтверждается отдельно, и неподтверждённое объявление повторяется, поэтому рассылка надёжна даже поверх ненадёжного IP ³.

Новизну определяют поля самого объявления. Порядковый номер (англ. sequence number) увеличивается при каждом изменении: из двух копий новее та, у которой номер больше. Контрольная сумма защищает содержимое. Возраст (англ. age) растёт с момента создания; объявление, не обновлявшееся слишком долго, удаляется из базы, а его автор обязан периодически переиздавать свои объявления, даже если ничего не изменилось. В OSPF период переиздания — 30 минут, а максимальный возраст — 1 час ³. Необходимость всех трёх механизмов показал инцидент в ARPANET 27 октября 1980 года: из-за аппаратного сбоя в сети одновременно оказались три копии объявления одного узла с номерами, сравнение которых давало циклический результат («каждая новее предыдущей»), и маршрутизаторы бесконечно пересылали их друг другу, пока сеть не была остановлена целиком. Разбор этого случая лёг в основу правил сравнения номеров и обязательного старения записей в последующих протоколах ¹¹.

Сравнение двух подходов

Ни один подход не свободен от петель в переходный период. В протоколе состояния каналов петля возникает, когда маршрутизаторы уже получили разные версии базы: один пересчитал маршруты, а другой ещё нет. Такие микропетли (англ. microloops) живут доли секунды — пока обновление не дойдёт до всех, — и не нарастают, как счёт до бесконечности.

OSPF: протокол состояния каналов в работе

Пакеты OSPF и протокол приветствия

Протокол OSPF (англ. Open Shortest Path First) разработан в IETF в конце 1980-х годов как открытая замена RIP; его вторая версия для IPv4 описана в RFC 2328 Дж. Моем ³, версия для IPv6 — OSPFv3 — в RFC 5340. Слово Open означает открытость спецификации, а не что-либо в алгоритме ¹². OSPF работает непосредственно поверх IP, без TCP и UDP: номер протокола в заголовке IP равен 89. Сообщения рассылаются на групповые адреса 224.0.0.5 (все маршрутизаторы OSPF, AllSPFRouters) и 224.0.0.6 (выделенные маршрутизаторы, AllDRouters) с TTL, равным 1, — пакеты OSPF никогда не покидают канал. Надёжность доставки обеспечивает сам протокол подтверждениями.

Всего в OSPFv2 пять типов пакетов: приветствие Hello (тип 1), описание базы данных Database Description, DBD (тип 2), запрос состояния каналов Link State Request, LSR (тип 3), обновление Link State Update, LSU (тип 4), содержащее сами объявления, и подтверждение Link State Acknowledgment, LSAck (тип 5). Все они начинаются с общего 24-байтного заголовка.

Идентификатор маршрутизатора (англ. Router ID) — 32-битное число, записываемое как адрес IPv4 и уникальное в пределах AS. Обычно его задают явно, равным адресу loopback, как в учебной топологии; без явного задания реализация выбирает один из адресов маршрутизатора, и смена этого адреса неожиданно меняет «имя» маршрутизатора для всей сети.

Пакет Hello выполняет три задачи: обнаруживает соседей, проверяет совместимость их параметров и служит сигналом жизни. Маршрутизатор отправляет его в каждый интерфейс, где включён OSPF, с интервалом HelloInterval, по умолчанию 10 секунд на широковещательных и точка-точка каналах. Если от соседа нет Hello в течение RouterDeadInterval, по умолчанию 40 секунд, то есть четырёх интервалов, сосед считается отказавшим ³. Так выглядит Hello от r2 в канале с r1, захваченный tcpdump -v:

IP (tos 0xc0, ttl 1, id 41210, offset 0, flags [none], proto OSPF (89), length 68)
    10.0.12.2 > 224.0.0.5: OSPFv2, Hello, length 48
	Router-ID 10.255.0.2, Backbone Area, Authentication Type: none (0)
	Options [External]
	  Hello Timer 10s, Dead Timer 40s, Mask 255.255.255.0, Priority 1
	  Designated Router 10.0.12.2, Backup Designated Router 10.0.12.1
	  Neighbor List:
	    10.255.0.1

Разберём размеры. Тело Hello состоит из маски сети (4 байта), HelloInterval (2), поля опций (1), приоритета (1), RouterDeadInterval (4), адресов выделенного и резервного выделенного маршрутизаторов (по 4) и списка соседей по 4 байта на каждого. Вместе с заголовком без соседей получается 24 + 20 = 44 байта, с одним соседом — 48, что и показывает tcpdump; добавив 20 байт заголовка IP, получим 68. Поле tos 0xc0 означает класс обслуживания CS6, которым по традиции помечается служебный трафик маршрутизации.

Соседство устанавливается, только если у двух маршрутизаторов совпадают: идентификатор области, маска сети на широковещательном канале, HelloInterval и RouterDeadInterval, флаг E в опциях (признак того, что область не является тупиковой) и параметры аутентификации. Несовпадение не вызывает никакого сообщения у соседа — его Hello просто отбрасываются, и в выводе show ip ospf neighbor сосед не появляется. Такие ошибки — одна из самых частых причин «OSPF не поднимается»; в лабораторной работе их предстоит найти по журналу и захвату трафика.

Состояния соседства и синхронизация баз

Установление соседства — это последовательность состояний конечного автомата, показанная на временной диаграмме. Маршрутизатор r1, получив Hello от r2, переводит соседа из состояния Down в Init: «я тебя слышу». Когда в списке соседей очередного Hello от r2 появляется идентификатор самого r1, связь подтверждена в обе стороны, и сосед переходит в состояние 2-Way. На этом этапе маршрутизаторы решают, нужна ли им полная синхронизация баз — смежность (англ. adjacency). На канале точка-точка она нужна всегда, на широковещательном — только с выделенным маршрутизатором, о чём речь ниже.

Синхронизация начинается в состоянии ExStart. Маршрутизаторы обмениваются пустыми пакетами DBD с установленными флагами I (Init), M (More) и MS (Master) и выясняют, кто будет ведущим (англ. master): им становится маршрутизатор с большим Router ID, в примере r2. Ведущий задаёт порядковые номера пакетов DBD, ведомый (англ. slave) повторяет номер в ответе — так обмен превращается в надёжный протокол «запрос — подтверждение». В состоянии Exchange стороны пересылают друг другу заголовки всех LSA своих баз; заголовок LSA занимает 20 байт и содержит тип, идентификатор, автора, порядковый номер, возраст и контрольную сумму — достаточно, чтобы понять, новее ли объявление имеющегося, не передавая его целиком. Каждый маршрутизатор составляет список объявлений, которых у него нет или которые у него устарели. При получении каждого DBD в состояниях ExStart и Exchange проверяется MTU: поле Interface MTU в пакете DBD сравнивается с собственным MTU интерфейса, и если сосед сообщает больший MTU, его DBD отвергаются — пакет LSU с большой базой мог бы не пройти через интерфейс. Соседство при этом «застревает» в состоянии ExStart или Exchange, что является классическим симптомом несовпадения MTU ³.

В состоянии Loading маршрутизатор запрашивает недостающие объявления пакетами LSR, получает их в пакетах LSU и подтверждает пакетами LSAck. Когда список запросов опустеет, соседство переходит в состояние Full: базы синхронизированы. Только после этого маршрутизатор включает канал к соседу в своё объявление, и сосед участвует в вычислении маршрутов.

Выделенный маршрутизатор на широковещательных сегментах

Если к одному сегменту Ethernet подключены n маршрутизаторов, полная смежность каждого с каждым дала бы n(n − 1)/2 пар, каждая из которых синхронизирует базы и пересылает объявления; при 10 маршрутизаторах это 45 смежностей и многократное дублирование лавинной рассылки. Кроме того, описывать сегмент как полный граф каналов между всеми маршрутизаторами было бы расточительно. OSPF решает обе проблемы, выбирая на каждом широковещательном сегменте выделенный маршрутизатор (англ. Designated Router, DR) и резервный (англ. Backup Designated Router, BDR) ³.

Все маршрутизаторы сегмента устанавливают полную смежность только с DR и BDR, а между собой остаются в состоянии 2-Way. Маршрутизатор, у которого изменилось состояние, отправляет LSU на адрес 224.0.0.6, который слушают DR и BDR; DR пересылает объявление всем на 224.0.0.5. Кроме того, DR создаёт объявление о сети (LSA типа 2), описывающее сегмент как отдельную вершину графа, соединённую со всеми подключёнными маршрутизаторами. Выборы проходят по полю приоритета в Hello: побеждает наибольший приоритет (по умолчанию 1; приоритет 0 означает «никогда не быть DR»), при равенстве — наибольший Router ID. Выборы не вытесняющие (англ. non-preemptive): маршрутизатор с большим приоритетом, включённый позже, не отнимает роль у действующего DR; BDR становится DR только при отказе последнего.

Механизм рассчитан на сегменты с многими маршрутизаторами. На канале между двумя маршрутизаторами DR не нужен, но если канал имеет тип broadcast — а именно такой тип OSPF присваивает интерфейсам Ethernet, в том числе виртуальным в Docker, — выборы всё равно проводятся, и в базе появляются лишние объявления типа 2. Поэтому на двухточечных каналах Ethernet принято задавать тип сети явно: ip ospf network point-to-point. Это убирает выборы, ускоряет установление смежности (не требуется ждать окончания выборов, длящихся до RouterDeadInterval) и упрощает граф.

Типы LSA и база данных состояния каналов

LSDB OSPF состоит из объявлений нескольких типов. В объёме курса нужны четыре ³:

• LSA типа 1, объявление маршрутизатора (англ. Router LSA), — его создаёт каждый маршрутизатор для каждой своей области; перечисляет каналы маршрутизатора: к соседям точка-точка, к транзитным сегментам (через их DR), к тупиковым сетям (англ. stub networks, например loopback или сегменты без соседей OSPF) — каждый со своей стоимостью;
• LSA типа 2, объявление сети (англ. Network LSA), — создаёт DR широковещательного сегмента; перечисляет все маршрутизаторы сегмента и маску сети;
• LSA типа 3, сводное объявление (англ. Summary LSA), — создаёт пограничный маршрутизатор области; сообщает в одну область префиксы другой со стоимостью до них, без топологии;
• LSA типа 5, внешнее объявление (англ. AS-External LSA), — создаёт пограничный маршрутизатор AS; описывает маршрут, полученный извне OSPF, например статический или из BGP; распространяется по всей AS.

Существуют и другие типы: 4 (сводка о пограничном маршрутизаторе AS, нужна, чтобы маршрутизаторы другой области знали, как до него добраться) и 7 (внешние маршруты в областях NSSA, RFC 3101); их достаточно знать по названию. Объявления типов 1 и 2 вместе образуют граф области, по которому работает алгоритм Дейкстры. Базу можно увидеть командой show ip ospf database; в учебной топологии с одной областью и широковещательными каналами она выглядит так:

r1# show ip ospf database

       OSPF Router with ID (10.255.0.1)

                Router Link States (Area 0.0.0.0)

Link ID         ADV Router      Age  Seq#       CkSum  Link count
10.255.0.1     10.255.0.1       312 0x80000006 0x4b1e 3
10.255.0.2     10.255.0.2       305 0x80000008 0x9a07 4
10.255.0.3     10.255.0.3       306 0x80000008 0x1d5c 4
10.255.0.4     10.255.0.4       298 0x80000005 0xe2a3 3
10.255.0.5     10.255.0.5       297 0x80000006 0x37f1 3

                Net Link States (Area 0.0.0.0)

Link ID         ADV Router      Age  Seq#       CkSum
10.0.12.2      10.255.0.2       316 0x80000001 0x6c35
10.0.13.3      10.255.0.3       316 0x80000001 0x5a43
10.0.23.3      10.255.0.3       309 0x80000001 0x0e86
10.0.24.4      10.255.0.4       301 0x80000001 0xb2d8
10.0.35.5      10.255.0.5       300 0x80000001 0x96ee
10.0.45.5      10.255.0.5       299 0x80000001 0x7c09

Пять объявлений типа 1 — по одному на маршрутизатор; число каналов Link count у r1 равно 3: два транзитных сегмента и loopback как тупиковая сеть. Шесть объявлений типа 2 соответствуют шести сегментам; Link ID объявления сети — адрес интерфейса DR на этом сегменте, поэтому по нему сразу видно, кто стал DR: на сегменте 10.0.12.0/24 это r2 с большим Router ID. Порядковые номера начинаются с 0x80000001 — наименьшего допустимого значения, ведь номер трактуется как знаковое 32-битное число, — и увеличиваются при каждом переиздании. Возраст в секундах растёт до 1800, после чего объявление переиздаётся. Подробное содержимое одного объявления выводит команда show ip ospf database router 10.255.0.1:

  LS age: 312
  Options: 0x2  : *|-|-|-|-|-|E|-
  LS Flags: 0x3
  Flags: 0x0
  LS Type: router-LSA
  Link State ID: 10.255.0.1
  Advertising Router: 10.255.0.1
  LS Seq Number: 80000006
  Checksum: 0x4b1e
  Length: 60

   Number of Links: 3

    Link connected to: a Transit Network
     (Link ID) Designated Router address: 10.0.12.2
     (Link Data) Router Interface address: 10.0.12.1
      Number of TOS metrics: 0
       TOS 0 Metric: 2

    Link connected to: a Transit Network
     (Link ID) Designated Router address: 10.0.13.3
     (Link Data) Router Interface address: 10.0.13.1
      Number of TOS metrics: 0
       TOS 0 Metric: 5

    Link connected to: Stub Network
     (Link ID) Net: 10.255.0.1
     (Link Data) Network Mask: 255.255.255.255
      Number of TOS metrics: 0
       TOS 0 Metric: 0

Длина объявления — 60 байт: 20 байт заголовка LSA, 4 байта флагов и числа каналов и три описания каналов по 12 байт. Стоимости 2 и 5 — те самые веса рёбер учебного графа. Стоимость задаётся на исходящем интерфейсе каждого маршрутизатора отдельно, поэтому в OSPF возможны несимметричные стоимости: из r1 в r2 — 2, а из r2 в r1 — 10. Тогда и пути в двух направлениях могут различаться — это нормальное, хотя и затрудняющее диагностику, свойство протокола.

Масштабирование, сходимость и обмен маршрутами

Области OSPF и межобластная маршрутизация

Полная карта сети — достоинство протокола состояния каналов, но в большой сети она становится обузой. Каждое изменение любого канала рассылается всем маршрутизаторам и заставляет каждого пересчитывать дерево; база растёт пропорционально размеру сети. OSPF вводит двухуровневую иерархию: AS делится на области (англ. areas), и топология каждой области видна только её маршрутизаторам ³. Одна область, с номером 0, называется магистральной (англ. backbone area), и все остальные области обязаны с ней соединяться.

Маршрутизатор, интерфейсы которого принадлежат нескольким областям, называется пограничным маршрутизатором области (англ. Area Border Router, ABR). Он хранит отдельную базу для каждой своей области и в каждую область сообщает сводными объявлениями типа 3 префиксы других областей вместе со стоимостью от себя до них. Маршрутизатор внутри области видит, таким образом, свою область как граф, а остальную AS — как набор префиксов «за ABR со стоимостью X». Это уже не состояние каналов, а вектор расстояний: межобластная маршрутизация OSPF устроена по дистанционно-векторному принципу, и от петель её защищает правило, что сводки передаются между немагистральными областями только через магистраль. Схема показана на рисунке на примере учебной топологии, разделённой на две области.

Маршрутизатор, вносящий в OSPF внешние маршруты, называется пограничным маршрутизатором AS (англ. AS Boundary Router, ASBR); на рисунке это r1, которому известен статический маршрут во внешнюю сеть. ABR дополнительно сообщает в другие области, как добраться до ASBR (LSA типа 4), а само внешнее объявление типа 5 рассылается по всем областям без изменений. Области, куда внешние объявления не допускаются, называются тупиковыми (англ. stub area); их маршрутизаторы получают вместо внешних маршрутов маршрут по умолчанию от ABR. Разновидности тупиковых областей и виртуальные каналы, которыми восстанавливают связность магистрали, выходят за рамки курса.

Области дают ещё одно преимущество — суммаризацию на границе. ABR может объявлять в магистраль вместо десятков префиксов области один суммарный (команда area 1 range 10.0.0.0/16), и тогда изменения внутри области вовсе не выходят за её пределы. Расплата за иерархию — потеря оптимальности: маршрутизатор другой области не видит внутренней топологии и выбирает ABR по сумме стоимостей, известной лишь приближённо.

Стоимость интерфейса и выбор маршрута

Стоимость интерфейса OSPF — целое число от 1 до 65535. Если она не задана явно, реализация вычисляет её по скорости интерфейса: стоимость равна опорной скорости, делённой на скорость канала, с округлением вниз и не менее 1. RFC 2328 не фиксирует опорную скорость, но традиционное значение — 100 Мбит/с, и в FRR это значение по умолчанию ⁹. Отсюда известная проблема: каналы 100 Мбит/с, 1 Гбит/с и 10 Гбит/с получают одинаковую стоимость 1, и протокол перестаёт их различать. Поэтому опорную скорость повышают на всех маршрутизаторах одинаково, например командой auto-cost reference-bandwidth 100000 (в Мбит/с, то есть 100 Гбит/с), либо назначают стоимости вручную командой ip ospf cost на интерфейсе. Виртуальные интерфейсы veth, через которые соединены контейнеры в лабораторной работе, сообщают скорость 10 Гбит/с, и при опорной скорости по умолчанию их стоимость равна 1.

Когда к одному префиксу ведут несколько маршрутов OSPF, сначала сравнивается их тип, а затем стоимость. Внутриобластной маршрут (англ. intra-area) предпочитается межобластному (англ. inter-area) независимо от стоимостей, а оба — внешним. Внешние маршруты бывают двух типов: у типа 1 (E1) стоимость складывается из внешней метрики и внутренней стоимости до ASBR, у типа 2 (E2) учитывается только внешняя метрика, а внутренняя стоимость используется лишь для выбора между равными. В FRR перераспределённые маршруты по умолчанию получают тип E2 и метрику 20. Маршруты с равной итоговой стоимостью устанавливаются как ECMP, по умолчанию FRR допускает до 64 следующих переходов на префикс (зависит от параметров сборки). Итог виден в таблице маршрутизации; число в квадратных скобках — административное расстояние и метрика:

r1# show ip route ospf
Codes: K - kernel route, C - connected, L - local, S - static,
       R - RIP, O - OSPF, I - IS-IS, B - BGP, E - EIGRP, N - NHRP,
       T - Table, v - VNC, V - VNC-Direct, A - Babel, F - PBR,
       f - OpenFabric, t - Table-Direct,
       > - selected route, * - FIB route, q - queued, r - rejected, b - backup
       t - trapped, o - offload failure

O   10.0.12.0/24 [110/2] is directly connected, eth0, weight 1, 00:05:12
O   10.0.13.0/24 [110/5] is directly connected, eth1, weight 1, 00:05:12
O>* 10.0.23.0/24 [110/4] via 10.0.12.2, eth0, weight 1, 00:05:02
O>* 10.0.24.0/24 [110/8] via 10.0.12.2, eth0, weight 1, 00:05:02
O>* 10.0.35.0/24 [110/5] via 10.0.12.2, eth0, weight 1, 00:04:55
O>* 10.0.45.0/24 [110/7] via 10.0.12.2, eth0, weight 1, 00:04:55
O>* 10.255.0.2/32 [110/2] via 10.0.12.2, eth0, weight 1, 00:05:02
O>* 10.255.0.3/32 [110/4] via 10.0.12.2, eth0, weight 1, 00:05:02
O>* 10.255.0.4/32 [110/7] via 10.0.12.2, eth0, weight 1, 00:04:55
O>* 10.255.0.5/32 [110/5] via 10.0.12.2, eth0, weight 1, 00:04:55

Стоимости совпадают с расчётом по алгоритму Дейкстры: до r4 — 7, до r5 — 5, до r3 — 4, всё через r2. Интересны две первые строки. Маршруты к 10.0.12.0/24 и 10.0.13.0/24 не отмечены символом >: эти сети подключены к r1 непосредственно, и маршрут типа C с административным расстоянием 0 побеждает маршрут OSPF. Стоимость маршрута OSPF к 10.0.13.0/24 равна 5, а не 4 через r2: стоимость пути до сети — это стоимость до маршрутизатора, к которому сеть подключена, плюс стоимость его интерфейса в эту сеть, и для собственной сети r1 она равна стоимости собственного интерфейса. Номера интерфейсов eth0 и eth1 в контейнере могут отличаться от приведённых: Docker не гарантирует их порядок.

Сходимость, таймеры и BFD

Время сходимости OSPF после отказа складывается из четырёх слагаемых: обнаружения отказа, создания и рассылки новых LSA, ожидания и выполнения SPF, обновления таблицы пересылки. Первое слагаемое обычно наибольшее. Если отказ виден на физическом уровне — пропала несущая, интерфейс перешёл в состояние down, — маршрутизатор узнаёт о нём за миллисекунды. Но часто отказ невидим: канал проходит через коммутатор, который продолжает поддерживать линк, или сосед завис, не выключив интерфейс. Тогда остаётся ждать RouterDeadInterval — 40 секунд по умолчанию. Уменьшить интервалы Hello можно, но пакеты обрабатываются плоскостью управления, и интервалы меньше секунды становятся источником ложных срабатываний при загрузке процессора.

Остальные слагаемые FRR контролирует таймерами. Новое объявление рассылается немедленно, но повторное изменение того же LSA принимается не чаще раза в секунду (MinLSArrival). Перед запуском SPF маршрутизатор ждёт, чтобы обработать сразу пачку объявлений от одного события; в FRR по умолчанию действует адаптивная задержка timers throttle spf 0 50 5000: первый расчёт без задержки, повторные — с удвоением паузы от 50 мс до 5 с при частых изменениях ⁹. В сумме при видимом отказе OSPF сходится примерно за секунду, при невидимом — за время RouterDeadInterval.

Для быстрого обнаружения невидимых отказов служит протокол двунаправленного обнаружения пересылки (англ. Bidirectional Forwarding Detection, BFD), описанный в RFC 5880 ⁷. Два соседа обмениваются короткими контрольными пакетами UDP (порт 3784 для BFD в пределах одного перехода) с интервалом в сотни или десятки миллисекунд; если подряд пропущено заданное число пакетов (множитель обнаружения, англ. detect multiplier), сессия объявляется упавшей, и BFD немедленно сообщает об этом протоколу маршрутизации. BFD прост, поэтому его можно реализовать в аппаратуре или в быстром пути ядра, независимо от загрузки процессора. В FRR BFD работает отдельным процессом bfdd, по умолчанию с интервалами 300 мс и множителем 3, то есть обнаруживает отказ за 0,9 с; для OSPF он включается командой ip ospf bfd на интерфейсе.

r1# show bfd peers brief
Session count: 2
SessionId  LocalAddress                             PeerAddress                             Status
=========  ============                             ===========                             ======
3418829173 10.0.12.1                                10.0.12.2                               up
1739420557 10.0.13.1                                10.0.13.3                               up

Перераспределение маршрутов и IS-IS

На практике в одной сети работают несколько источников маршрутов: статические маршруты, OSPF, BGP на границе с провайдером. Передача маршрутов из одного протокола в другой называется перераспределением (англ. redistribution). В FRR она задаётся в конфигурации принимающего протокола: redistribute static или redistribute connected в разделе router ospf превращает маршрутизатор в ASBR, и перераспределённые маршруты появляются в OSPF как LSA типа 5. Метрику и тип можно задать явно: redistribute static metric 100 metric-type 1. Частный случай — анонс маршрута по умолчанию командой default-information originate: пограничный маршрутизатор с выходом в Интернет сообщает остальным, что всё неизвестное следует отправлять ему.

Перераспределение — частый источник ошибок. Метрики разных протоколов несопоставимы: число переходов RIP ничего не говорит о стоимости OSPF, и при передаче метрика назначается заново, а информация о пути теряется. Особенно опасно взаимное перераспределение в двух точках: маршрут, переданный из RIP в OSPF на одном маршрутизаторе, возвращается из OSPF в RIP на другом, и при неудачном сочетании административных расстояний возникает устойчивая петля маршрутизации. Поэтому перераспределение ограничивают фильтрами (route-map) и помечают перенесённые маршруты метками (поле Route Tag в RIP, метка внешнего LSA в OSPF), чтобы не принимать их обратно.

Наконец, о третьем распространённом внутреннем протоколе. IS-IS (англ. Intermediate System to Intermediate System) разработан для стека протоколов OSI и стандартизован как ISO/IEC 10589; его применение для маршрутизации IP описано в RFC 1195 ⁸. Это тоже протокол состояния каналов с алгоритмом Дейкстры, но с иными решениями: он работает непосредственно поверх канального уровня, а не IP, его объявления (LSP) расширяются полями «тип — длина — значение», что упростило добавление IPv6 и новых возможностей без смены версии, а иерархия строится из уровней 1 и 2 вместо областей вокруг магистрали. IS-IS популярен в сетях крупных провайдеров и в центрах обработки данных; OSPF — в корпоративных сетях. Принципиальных различий в качестве маршрутизации между ними нет ¹⁰.

Итоги темы

Динамическая маршрутизация сводит задачу построения таблиц к поиску кратчайших путей во взвешенном графе, но решает её в распределённой системе, где граф меняется, а сведения о нём запаздывают. Два семейства протоколов по-разному распределяют работу. В дистанционно-векторном подходе маршрутизаторы сообща решают уравнение Беллмана — Форда, обмениваясь только расстояниями; это просто и экономно, но хорошие новости распространяются на один переход за обмен, а плохие порождают счёт до бесконечности, который смягчают расщеплённый горизонт, отравленный обратный маршрут, триггерные обновления и малая «бесконечность» 16 в RIP.

В подходе состояния каналов маршрутизаторы обмениваются не выводами, а исходными фактами — описаниями своих каналов, — и надёжная лавинная рассылка с порядковыми номерами и старением записей обеспечивает всем одинаковую карту. Кратчайшие пути каждый вычисляет сам алгоритмом Дейкстры, что исключает счёт до бесконечности и даёт быструю предсказуемую сходимость. На учебной топологии оба алгоритма дали одинаковые маршруты: все пути r1 проходят через r2, а самый дорогой — до r4 стоимостью 7.

OSPF превращает алгоритм в инженерный протокол: Hello обнаруживает соседей и проверяет совместимость параметров, обмен DBD, LSR и LSU синхронизирует базы, выделенный маршрутизатор сокращает число смежностей на общих сегментах, типы LSA разделяют описание маршрутизаторов, сегментов, межобластных и внешних маршрутов. Области ограничивают размер базы и распространение изменений ценой оптимальности, а время сходимости определяется в первую очередь обнаружением отказа, для ускорения которого служит BFD.

Внутренний протокол исходит из того, что все маршрутизаторы принадлежат одному владельцу и цель одна — кратчайший путь. Между автономными системами это допущение неверно: у каждой системы свои интересы, договоры и политика, и кратчайший путь не обязательно желателен. Как устроена маршрутизация в таких условиях — предмет темы 10, посвящённой BGP.

Литература

1. Hedrick C. Routing Information Protocol. — RFC 1058, IETF, 1988. https://www.rfc-editor.org/rfc/rfc1058
2. Malkin G. RIP Version 2. — RFC 2453, IETF, 1998. https://www.rfc-editor.org/rfc/rfc2453
3. Moy J. OSPF Version 2. — RFC 2328, IETF, 1998. https://www.rfc-editor.org/rfc/rfc2328
4. Kurose J. F., Ross K. W. Computer Networking: A Top-Down Approach. 8th ed. — Pearson, 2021.
5. Bellman R. On a Routing Problem. — Quarterly of Applied Mathematics, 1958, Vol. 16, No. 1, P. 87–90, DOI: 10.1090/qam/102435.
6. Dijkstra E. W. A Note on Two Problems in Connexion with Graphs. — Numerische Mathematik, 1959, Vol. 1, P. 269–271, DOI: 10.1007/BF01386390.
7. Katz D., Ward D. Bidirectional Forwarding Detection (BFD). — RFC 5880, IETF, 2010. https://www.rfc-editor.org/rfc/rfc5880
8. Callon R. Use of OSI IS-IS for Routing in TCP/IP and Dual Environments. — RFC 1195, IETF, 1990. https://www.rfc-editor.org/rfc/rfc1195
9. FRRouting Project. FRRouting User Guide: OSPFv2. — 2025. https://docs.frrouting.org/en/latest/ospfd.html
10. Doyle J., Carroll J. Routing TCP/IP, Volume 1. 2nd ed. — Cisco Press, 2005.
11. Perlman R. Interconnections: Bridges, Routers, Switches, and Internetworking Protocols. 2nd ed. — Addison-Wesley, 1999.
12. Moy J. T. OSPF: Anatomy of an Internet Routing Protocol. — Addison-Wesley, 1998.
13. McQuillan J. M., Richer I., Rosen E. C. The New Routing Algorithm for the ARPANET. — IEEE Transactions on Communications, 1980, Vol. 28, No. 5, P. 711–719, DOI: 10.1109/TCOM.1980.1094721.

Дополнительные материалы

Вопросы для самопроверки

1. Чем плоскость управления отличается от плоскости данных и почему протокол маршрутизации может работать на порядки медленнее пересылки пакетов?
2. Запишите уравнение Беллмана — Форда и объясните, почему для его решения маршрутизатору достаточно знать только стоимости своих каналов и векторы соседей.
3. Почему в дистанционно-векторном протоколе «хорошие новости распространяются быстро, а плохие — медленно»? Проиллюстрируйте на цепочке из трёх маршрутизаторов.
4. Какую проблему решает расщеплённый горизонт и почему он не спасает от петли из трёх маршрутизаторов?
5. Почему бесконечность в RIP равна именно 16 и какое ограничение это накладывает на сеть?
6. Сколько времени пройдёт, прежде чем RIP с таймерами по умолчанию удалит маршрут через молча отказавшего соседа? Из каких таймеров складывается это время?
7. Выполните алгоритм Дейкстры для корня r5 учебной топологии темы. Какие первые переходы получатся до остальных маршрутизаторов?
8. Почему в протоколе состояния каналов не возникает счёта до бесконечности, но возможны кратковременные микропетли?
9. Какие три поля заголовка LSA определяют, какая из двух копий объявления новее, и зачем объявлению возраст?
10. Перечислите состояния соседства OSPF от Down до Full. В каком состоянии останавливается соседство при несовпадении MTU и почему?
11. Зачем на широковещательном сегменте выбирается DR и почему на канале между двумя маршрутизаторами его лучше отключить?
12. Какие объявления создаёт пограничный маршрутизатор области и какие — пограничный маршрутизатор AS? Какое из них распространяется по всем областям без изменений?
13. Почему маршрутизатор OSPF предпочитает внутриобластной маршрут межобластному даже при большей стоимости?
14. Почему каналы 1 Гбит/с и 10 Гбит/с при настройках OSPF по умолчанию имеют одинаковую стоимость и как это исправить?
15. Чем BFD ускоряет сходимость и почему его интервалы можно сделать короче интервалов Hello?

Глоссарий темы

Шпаргалка по инструментам

Управление стендом лабораторной работы:

docker compose up -d                          # поднять топологию
./tools/ifmap.sh                              # какие интерфейсы в каких подсетях
docker compose exec r1 vtysh                  # консоль FRR
docker compose exec r1 vtysh -c "show ip ospf neighbor"
docker compose logs --tail 50 r4              # журнал FRR
./tools/base.sh --p2p                         # OSPF в одной области, стоимости, точка-точка
docker compose down                           # удалить топологию

Просмотр состояния OSPF в vtysh:

show ip ospf                              ! процесс: Router ID, таймеры SPF, области, число LSA
show ip ospf interface eth0               ! область, стоимость, тип сети, таймеры, DR/BDR
show ip ospf neighbor                     ! соседи, состояние, роль, Dead Time
show ip ospf neighbor detail              ! подробно: счётчики, время в состоянии
show ip ospf database                     ! заголовки всех LSA по типам и областям
show ip ospf database router 10.255.0.1   ! LSA типа 1 указанного маршрутизатора
show ip ospf database network             ! LSA типа 2
show ip ospf database summary             ! LSA типа 3
show ip ospf database asbr-summary        ! LSA типа 4
show ip ospf database external            ! LSA типа 5
show ip ospf route                        ! результат SPF: внутриобластные, IA, E1/E2
show ip ospf border-routers               ! известные ABR и ASBR
show ip route ospf                        ! маршруты OSPF в общей таблице
show bfd peers brief                      ! сессии BFD
show ip rip                               ! таблица RIP (если включён ripd)

Настройка (в режиме configure terminal):

router ospf
 ospf router-id 10.255.0.1
 network 10.0.12.0/24 area 0               ! включить OSPF на интерфейсах из префикса
 network 10.0.24.0/24 area 1
 auto-cost reference-bandwidth 100000      ! опорная скорость, Мбит/с
 redistribute static metric-type 1         ! внешние маршруты типа E1
 default-information originate             ! объявить маршрут по умолчанию
 area 1 range 10.255.0.4/31                ! суммаризация на ABR
 timers throttle spf 0 50 5000             ! задержка SPF: начальная, мин. и макс. пауза, мс
exit
!
interface eth0
 ip ospf cost 2
 ip ospf passive                          ! объявлять сеть, но не искать соседей
 ip ospf network point-to-point
 ip ospf hello-interval 1
 ip ospf dead-interval 4
 ip ospf mtu-ignore                        ! не сравнивать MTU в DBD (лучше исправить MTU)
 ip ospf authentication message-digest
 ip ospf message-digest-key 1 md5 SECRET
 ip ospf bfd
exit
!
router rip                                 ! RIPv2 для сравнения
 version 2
 network 10.0.0.0/16
 timers basic 30 180 120                   ! обновление, устаревание, удаление, с
exit

Перезапуск и отладка: clear ip ospf process — перезапуск процесса OSPF; debug ospf packet hello, debug ospf nsm, debug ospf ism — отладочные сообщения о пакетах Hello, автомате соседа и автомате интерфейса (вывод — в журнал FRR); no debug ospf ... — выключить.

Захват и анализ:

Что почитать и посмотреть

• RFC 2328. OSPF Version 2 — первоисточник. Стоит прочитать разделы 7 (соседство и DR), 10 (автомат соседа и обмен DBD), 12 (форматы LSA) и 16 (расчёт таблицы маршрутизации, включая проверку двусторонней связи); приложение A содержит форматы всех пакетов.
• RFC 2453. RIP Version 2 — короткий и очень ясный документ: в разделе 3 разобраны счёт до бесконечности, расщеплённый горизонт и триггерные обновления; хорошее чтение до лекции.
• FRR User Guide: OSPFv2 — все команды ospfd с умолчаниями (таймеры, опорная скорость, задержки SPF), примеры конфигураций и описание вывода show; в соседних разделах — BFD и RIP.
• Kurose J. F., Ross K. W. Computer Networking: A Top-Down Approach, разделы 5.2 «Routing Algorithms» и 5.3 «Intra-AS Routing in the Internet: OSPF» — компактное изложение обоих алгоритмов с задачами; интерактивные упражнения на сайте книги генерируют задачи на Дейкстру и Беллмана — Форда.
• Moy J. T. OSPF: Anatomy of an Internet Routing Protocol. — Addison-Wesley, 1998 — книга автора RFC 2328 о том, почему протокол устроен именно так: история решений, ошибки ранних версий, опыт развёртывания.
• Perlman R. Interconnections. 2nd ed., главы о маршрутизации — классическое сравнение дистанционно-векторных протоколов и протоколов состояния каналов, разбор инцидента ARPANET 1980 года и обоснование правил сравнения порядковых номеров LSA.
• Rosen E. C. Vulnerabilities of Network Control Protocols: An Example. RFC 789 — отчёт об отказе ARPANET 27 октября 1980 года из первых рук; редкий пример подробного разбора сбоя протокола маршрутизации.
• RFC 5880. Bidirectional Forwarding Detection — устройство BFD: формат пакета, согласование интервалов, режимы работы; для практики достаточно разделов 1–6.
• Википедия: Open Shortest Path First — сжатый обзор с таблицами типов пакетов и LSA, удобный как справочник.
• Видео: доклады серии «OSPF/IS-IS deep dive» и «Fast convergence» на конференциях NANOG и RIPE Meeting (каналы NANOG и RIPE NCC на YouTube) — как провайдеры добиваются сходимости за доли секунды.

Углубление (по желанию)

Быстрое восстановление: LFA и TI-LFA

Даже с BFD сходимость OSPF занимает сотни миллисекунд: отказ надо обнаружить, разослать LSA, пересчитать SPF и обновить таблицу пересылки. Для голосового и видеотрафика этого много. Механизм бесконфликтных альтернатив (англ. Loop-Free Alternates, LFA, RFC 5286) заранее, ещё до отказа, вычисляет для каждого назначения резервный следующий переход — соседа, чей собственный кратчайший путь к назначению не проходит через защищаемый канал. Резервный переход загружается в таблицу пересылки заранее, и при отказе маршрутизатор переключается на него локально, за десятки миллисекунд, не дожидаясь сходимости протокола. LFA существует не для всех топологий; его развитие TI-LFA (англ. Topology-Independent LFA) использует сегментную маршрутизацию, чтобы направить пакет по заранее рассчитанному пути восстановления в любой двусвязной сети. В FRR классический LFA реализован для IS-IS, а TI-LFA — для IS-IS и OSPF.

OSPF и IS-IS в центрах обработки данных и почему там победил BGP

В сетях центров обработки данных с топологией Клоза (тема 21) тысячи коммутаторов соединены множеством равноценных путей. Лавинная рассылка LSA в такой сети становится дорогой: каждый отказ канала вызывает пересчёт на всех узлах. Многие операторы перешли на eBGP как единственный протокол маршрутизации внутри ЦОД (RFC 7938): каждый коммутатор — отдельная AS, политика проста, а отказ затрагивает лишь соседей. В ответ IETF развивает расширения протоколов состояния каналов, сокращающие лавинную рассылку в плотных топологиях (динамическая лавинная рассылка, RFC 9667), и новые протоколы, такие как RIFT. Это хороший пример того, что выбор протокола определяется не «качеством алгоритма», а свойствами конкретной топологии.

Babel: дистанционно-векторный протокол без счёта до бесконечности

Дистанционно-векторный подход не обречён на счёт до бесконечности. Протокол Babel (RFC 8966), созданный для беспроводных ячеистых сетей, использует условие допустимости, восходящее к алгоритму DUAL протокола EIGRP: маршрутизатор принимает от соседа маршрут, только если заявленная соседом метрика строго меньше лучшей метрики, которую сам маршрутизатор когда-либо имел для этого назначения. Такой маршрут гарантированно не ведёт обратно через самого маршрутизатора, поэтому петли не образуются даже в переходных состояниях. Если допустимых маршрутов нет, маршрутизатор запрашивает у источника новый порядковый номер, «обнуляющий» историю. Babel реализован в FRR (babeld) и используется в общественных беспроводных сетях.

Лабораторная работа 9. OSPF на FRRouting

• Раздел курса: тема 9 «Динамическая маршрутизация внутри автономной системы: RIP и OSPF»

Введение

В лабораторной работе 8 таблицы маршрутизации трёх маршрутизаторов заполнялись вручную, а резервный путь приходилось заранее описывать плавающим статическим маршрутом. В настоящей работе ту же задачу решает протокол OSPF: пять маршрутизаторов FRRouting в контейнерах Docker сами обнаруживают соседей, обмениваются объявлениями о состоянии каналов и вычисляют кратчайшие пути алгоритмом Дейкстры. Учебная топология совпадает с топологией из теории темы 9, поэтому все расчёты, выполненные там на бумаге, можно сравнить с поведением настоящего протокола.

Работа проходит путь от включения протокола к его диагностике. Сначала устанавливается соседство и изучается база состояния каналов, затем в захвате трафика разбираются пакеты Hello, DBD и LSU. После этого задаются стоимости каналов, предсказываются маршруты по алгоритму Дейкстры и проверяется предсказание, измеряется время сходимости при видимом и «тихом» отказе канала, ищутся внесённые неисправности соседства, сеть делится на две области. Продвинутая часть посвящена BFD, многопутевой маршрутизации и асимметричным стоимостям.

Части 1–6 составляют базовую часть работы. Часть 7 — продвинутая, выполняется по желанию.

Цель работы

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

После выполнения работы можно будет:

• включить OSPF на маршрутизаторах FRR и по выводу show ip ospf neighbor определить состояние соседства и роль DR/BDR;
• прочитать базу состояния каналов, сопоставить объявления типов 1 и 2 с графом сети и выделить в захвате трафика пакеты Hello, DBD, LSR, LSU, LSAck;
• предсказать таблицу маршрутизации по алгоритму Дейкстры для заданных стоимостей и проверить предсказание;
• измерить время сходимости при видимом и невидимом отказе канала и объяснить, какие таймеры его определяют;
• найти причину, по которой соседство не устанавливается: несовпадение интервалов Hello, MTU или аутентификации;
• разделить сеть на области, объяснить появление объявлений типов 3, 4, 5 и потерю оптимальности путей на границе областей.

Теоретический минимум

Граф сети, алгоритм Дейкстры и его пошаговый пример — тема 9, раздел «Маршрутизация по состоянию каналов»; пакеты, соседство, DR/BDR и типы LSA — раздел «OSPF: протокол состояния каналов в работе»; области, стоимости, таймеры, BFD и перераспределение — раздел «Масштабирование, сходимость и обмен маршрутами».

Учебная топология показана на рисунке ниже. Каждый канал — отдельная сеть Docker /24, маршрутизатор rN имеет в ней адрес с последним октетом N, а на интерфейсе lo — адрес 10.255.0.N/32, он же идентификатор маршрутизатора.

Адрес .254 в каждой подсети занимает мост на хосте (шлюз Docker). Сети помечены как внутренние, поэтому маршрута по умолчанию у контейнеров нет и пакеты между маршрутизаторами идут только по маршрутам OSPF.

Docker не гарантирует, что интерфейс eth0 контейнера подключён к определённой сети, поэтому соответствие «интерфейс — подсеть» определяется в начале работы, а в командах ниже имя интерфейса обозначено как <if12> — «интерфейс маршрутизатора в сети 10.0.12.0/24».

Команды FRR, используемые в работе (вводятся в vtysh; режим настройки — configure terminal, выход — end):

Полезные фильтры Wireshark: ospf — все пакеты OSPF; ospf.msg == 1 — Hello; ospf.msg == 2 — DBD; ospf.msg == 3 — LSR; ospf.msg == 4 — LSU; ospf.msg == 5 — LSAck; ip.dst == 224.0.0.6 — пакеты для DR и BDR.

Перечень оснащения

• Ubuntu 24.04 (физическая или виртуальная машина, WSL2) с Docker Engine и плагином compose: sudo apt install docker.io docker-compose-v2, пользователь добавлен в группу docker (sudo usermod -aG docker $USER, затем повторный вход). Альтернатива — Docker Desktop.
• Wireshark и tcpdump (установлены в ЛР 1), Python 3.
• Архив окружения lr-env: compose.yaml, начальные конфигурации FRR пяти маршрутизаторов, учебный калькулятор маршрутов spf.py с файлами топологий, вспомогательные сценарии в каталоге tools/, README.md.
• Образ quay.io/frrouting/frr:10.2.1 и образ с сетевыми утилитами nicolaka/netshoot (для захвата, ping с отметками времени и имитации отказов); оба скачиваются при первом запуске, требуется доступ в Интернет.
• Права sudo для захвата трафика на мостах хоста.

Порядок выполнения работы

Распакуйте архив и перейдите в каталог lr-env. Топология поднимается командой docker compose up -d и удаляется командой docker compose down. Начальные конфигурации содержат только имена, адреса lo и, у r1, статический маршрут для части 6; протокол OSPF настраивается в ходе работы в консоли vtysh и при docker compose down теряется. Если стенд пришлось пересоздать, состояние после части 3 восстанавливается сценарием tools/base.sh --p2p (без ключа — состояние после части 1 со стоимостями).

Консоль маршрутизатора открывается командой docker compose exec r1 vtysh, одиночная команда — docker compose exec r1 vtysh -c "show ip ospf neighbor". Для краткости ниже команды vtysh приводятся без этой обёртки, с указанием маршрутизатора.

В заданиях со словом «предсказать» ответ записывается в журнал до выполнения команды. Неверное предсказание не страшно, если в журнале объяснено, почему результат оказался иным. В журнал помещаются выводы команд (неважные строки можно сокращать многоточием), выдержки из захватов и ответы на вопросы.

Часть 1. Запуск топологии и соседство в одной области

Задание

1. Поднимите топологию и убедитесь, что запущены пять контейнеров:

   docker compose up -d
   docker compose ps
   

2. Определите соответствие интерфейсов подсетям на каждом маршрутизаторе и заполните таблицу «маршрутизатор — интерфейс — подсеть»:

   ./tools/ifmap.sh
   

   Сценарий выполняет в каждом контейнере ip -o -4 addr show и печатает имя интерфейса и адрес. Проверьте связность соседей: docker compose exec r1 ping -c 2 10.0.12.2. Проверьте, что r1 не достигает адреса 10.0.24.4, и объясните почему.

3. Включите OSPF на r1:

   configure terminal
   router ospf
    ospf router-id 10.255.0.1
    network 10.0.0.0/16 area 0
    network 10.255.0.0/24 area 0
   end
   show ip ospf interface
   

   Какие интерфейсы вошли в OSPF и почему, хотя ни один из них не назван явно? Какую стоимость FRR назначил интерфейсам? Объясните значение, исходя из опорной скорости 100 Мбит/с и скорости интерфейса, которую показывает show interface <if12> (поле speed, в Мбит/с).

4. Предсказать: в каком состоянии окажется сосед r2 на r1 через минуту, если OSPF включён только на r1? Проверьте командой show ip ospf neighbor.

5. Включите OSPF на r2–r5 теми же командами со своими идентификаторами. Включайте маршрутизаторы по порядку, от r2 к r5, с паузой не менее минуты. Через минуту после включения последнего выполните на r1 и r3 команду show ip ospf neighbor. Ожидается вывод вида:

   Neighbor ID     Pri State           Up Time         Dead Time Address         Interface                        RXmtL RqstL DBsmL
   10.255.0.2        1 Full/Backup     3m41s             33.112s 10.0.12.2       eth1:10.0.12.1                       0     0     0
   10.255.0.3        1 Full/Backup     2m40s             37.904s 10.0.13.3       eth0:10.0.13.1                       0     0     0
   

6. Выпишите для каждого из шести каналов, кто стал DR и кто BDR. Совпадает ли результат с правилом «побеждает больший Router ID»? Если нет, объясните расхождение свойством выборов, описанным в теории (подсказка: порядок включения).

7. Проверьте связность между интерфейсами обратной связи: docker compose exec r1 ping -c 3 -I 10.255.0.1 10.255.0.4 и docker compose exec r1 traceroute -n -s 10.255.0.1 10.255.0.4 (если в образе нет traceroute, воспользуйтесь способом из README.md). Сколько переходов в пути и почему путь именно такой, если стоимости всех интерфейсов одинаковы?

Что должно получиться

Таблица соответствия интерфейсов; вывод show ip ospf interface с объяснением стоимости; состояние соседа при одностороннем включении; выводы show ip ospf neighbor на r1 и r3; таблица «канал — DR — BDR» с объяснением; трассировка r1 → r4.

Часть 2. База состояния каналов и пакеты OSPF

Задание

1. Предсказать: сколько объявлений типа 1 и типа 2 будет в базе каждого маршрутизатора и одинаковы ли базы у всех пяти? Каким будет поле Link count объявления r2? Проверьте:

   show ip ospf database
   show ip ospf database router 10.255.0.2
   

   Сравните заголовки объявлений (Link ID, ADV Router, Seq#, CkSum) на r1 и r5. Что изменилось бы, если бы базы различались?

2. По выводу show ip ospf database router и show ip ospf database network для всех маршрутизаторов нарисуйте граф, который видит алгоритм Дейкстры: вершины-маршрутизаторы, вершины-сети (объявления типа 2) и рёбра со стоимостями. Почему сеть 10.0.12.0/24 изображается отдельной вершиной, а не ребром между r1 и r2?

3. Запустите захват на канале r1 — r2:

   sudo tcpdump -i br-n12 -w ospf-n12.pcap 'ip proto 89'
   

   Без доступа к мостам хоста (Docker Desktop) используйте вспомогательный контейнер:

   docker run --rm --network container:lr09-r1 nicolaka/netshoot \
       tcpdump -i any -U -w - 'ip proto 89' > ospf-r1.pcap
   

4. Во второй консоли перезапустите процесс OSPF на r2 командой clear ip ospf process (в vtysh маршрутизатора r2) и через минуту остановите захват.

5. Откройте захват в Wireshark с фильтром ospf. Заполните таблицу «время — отправитель — получатель — тип пакета — назначение» для первых 15–20 пакетов после перезапуска и сопоставьте её с состояниями соседства Init, 2-Way, ExStart, Exchange, Loading, Full на временной диаграмме из теории.

6. В пакете Hello найдите поля HelloInterval, RouterDeadInterval, Network Mask, Router Priority, DR, BDR и список соседей; проверьте длину пакета по расчёту из теории (24 + 20 + 4 байта на соседа). Поясните, почему TTL в заголовке IP равен 1 и почему адрес получателя — групповой.

7. В первых пакетах DBD найдите флаги I, M, MS и поле Interface MTU. Кто стал ведущим (master) и почему? В пакете LSU определите, какие объявления в нём переданы (тип, Link State ID, Advertising Router, порядковый номер).

8. Выясните, на какой адрес отправляет LSU маршрутизатор, не являющийся DR, и на какой — DR (фильтр ospf.msg == 4). Объясните различие.

Что должно получиться

Ответы на предсказания пункта 1 и выдержки из базы; схема графа со стоимостями; файл захвата (приложить к журналу); таблица обмена при установлении смежности с отметкой состояний; разбор полей Hello, DBD и LSU; ответ на вопрос пункта 8.

Часть 3. Стоимости каналов и алгоритм Дейкстры

Задание

1. Задайте стоимости интерфейсов в соответствии с таблицей адресного плана, на обоих концах каждого канала, например на r1:

   configure terminal
   interface <if12>
    ip ospf cost 2
   exit
   interface <if13>
    ip ospf cost 5
   end
   

2. Предсказать: выполните вручную алгоритм Дейкстры для корня r3 (не r1, разобранного в теории): таблица шагов с оценками и первыми переходами, итоговое дерево кратчайших путей и таблица маршрутов r3 до адресов 10.255.0.N. Проверьте ручной расчёт учебным калькулятором:

   python3 spf.py dijkstra topology.txt r3
   

3. Сравните предсказание с выводом show ip route ospf и show ip ospf route на r3 и с трассировкой от r3 до 10.255.0.4 (с адреса 10.255.0.3). Объясните каждое расхождение. Почему стоимость маршрута до 10.255.0.4/32 равна стоимости пути до r4, а стоимость до сети 10.0.24.0/24 — нет?

4. Предсказать: как изменится маршрут r1 к r4, если стоимость канала r4 — r5 увеличить с 2 до 4 на обоих концах? Измените файл topology.txt (сохраните копию исходного), получите ответ калькулятором, затем внесите изменение в FRR и проверьте. Верните исходную стоимость.

5. Переведите все интерфейсы каналов на всех маршрутизаторах в тип «точка-точка» командой ip ospf network point-to-point. Предсказать: что произойдёт с объявлениями типа 2 и с полем Link count объявления r1? Проверьте show ip ospf database и show ip ospf database router 10.255.0.1. Объясните, почему для каждого канала в объявлении теперь две записи — к соседу и к тупиковой сети.

6. Сравните время установления смежности на канале «точка-точка» и на широковещательном: перезапустите процесс OSPF на r4 и засеките по show ip ospf neighbor на r2, через сколько секунд сосед достигает Full. Затем на обоих концах канала r2 — r4 верните тип ip ospf network broadcast и повторите опыт; после измерения снова задайте тип «точка-точка». В чём причина разницы? Почему при широковещательном типе результат может зависеть от того, успел ли r2 заметить уход соседа?

Что должно получиться

Ручной расчёт алгоритма Дейкстры для r3 и вывод калькулятора; таблица маршрутов r3 из FRR и трассировка; ответы на вопросы пунктов 3–6 с выводами команд; изменённая база при типе «точка-точка».

Часть 4. Отказ канала и время сходимости

В этой части путь от r1 к r4 проходит через r2, r3, r5 (стоимость 7), а резервный — через прямой канал r2 — r4 (стоимость 8). Измерение выполняется непрерывным ping с интервалом 0,1 с: число пропущенных номеров icmp_seq, умноженное на интервал, даёт длительность перерыва связи.

Задание

1. Запустите в отдельной консоли измерение и оставьте его работать:

   docker run --rm --network container:lr09-r1 nicolaka/netshoot \
       ping -D -i 0.1 -I 10.255.0.1 10.255.0.4
   

2. Видимый отказ. Предсказать: через сколько секунд восстановится связь, если на r5 выключить интерфейс в сторону r4? Выключите его и через полминуты включите обратно:

   ./tools/fail.sh link r5 10.0.45 down
   ./tools/fail.sh link r5 10.0.45 up
   

   Определите длительность перерыва при отказе и при восстановлении. Заметим, что выключен интерфейс только на r5, а r4 подключён к мосту и потери несущей не видит. Объясните, почему r1 всё равно перестаёт использовать канал r4 — r5 почти сразу (подсказка: проверка двусторонней связи при построении графа, тема 9).

3. Невидимый отказ. Сценарий fail.sh silent запускает вспомогательный контейнер в пространстве имён r5 и правилами iptables отбрасывает все пакеты через интерфейс в сторону r4; интерфейсы при этом остаются включёнными. Предсказать длительность перерыва, затем проверить:

   ./tools/fail.sh silent r5 10.0.45 on
   

   Пока связь отсутствует, несколько раз выполните на r4 show ip ospf neighbor и следите за столбцом Dead Time. Зафиксируйте длительность перерыва, затем снимите отказ (./tools/fail.sh silent r5 10.0.45 off). Объясните, почему перерыв лежит в интервале от 30 до 40 секунд, а не равен ровно 40.

4. Уменьшите таймеры на обоих концах канала r4 — r5:

   interface <if45>
    ip ospf hello-interval 1
    ip ospf dead-interval 4
   

   Повторите опыт пункта 3. Как изменилась длительность перерыва? Подсчитайте, во сколько раз вырос служебный трафик Hello на этом канале. Почему уменьшать интервалы до долей секунды на всех каналах крупной сети не рекомендуется?

5. Посмотрите текущие настройки задержки SPF (show ip ospf, строки Initial SPF scheduling delay, Minimum hold time between consecutive SPFs, Maximum hold time between consecutive SPFs) и объясните, какая часть измеренного перерыва приходится на обнаружение отказа, а какая — на расчёт и установку маршрутов.

6. Верните таймеры канала r4 — r5 к значениям по умолчанию (no ip ospf hello-interval, no ip ospf dead-interval).

Что должно получиться

Предсказания и измеренные длительности перерыва для видимого отказа, невидимого отказа с таймерами по умолчанию и с уменьшенными таймерами (таблица); выдержки ping с пропущенными номерами; выводы show ip ospf neighbor во время отказа; объяснения пунктов 2–5.

Часть 5. Поиск неисправности: соседство не устанавливается

Сценарий tools/break.sh вносит в работающую сеть одну из трёх скрытых неисправностей. Не читайте сценарий до завершения диагностики: в этой части важен путь к ответу, а не ответ.

Задание

1. Убедитесь, что все соседства в состоянии Full и путь r1 → r4 имеет стоимость 7. Внесите первую неисправность:

   ./tools/break.sh 1
   

2. Симптом: «через минуту после работ на одном из маршрутизаторов путь к r4 стал длиннее». Найдите причину, двигаясь от симптома: сравнение show ip route ospf с ожидаемым, поиск пропавшего соседства на всех маршрутизаторах, сравнение параметров интерфейсов двух концов канала (show ip ospf interface), захват Hello на мосту этого канала и сравнение полей двух сторон. Сообщение о несовпадении параметров Hello FRR пишет в журнал и без отладки; для подробностей включите на подозреваемом маршрутизаторе отладку: в vtysh выполните configure terminal, log stdout debugging, exit (по умолчанию журнал выводится с уровнем informational, и отладочные строки в него не попадают), затем debug ospf packet hello, и найдите в журнале (docker compose logs --tail 30 <имя>) сообщение о причине отказа в соседстве. Устраните неисправность и подтвердите восстановление.

3. Повторите диагностику для неисправностей ./tools/break.sh 2 и ./tools/break.sh 3. Для каждой в журнал записываются: симптом; гипотезы в порядке проверки; команда, подтвердившая или опровергнувшая каждую гипотезу; причина; исправление. Одна из неисправностей проявляется не исчезновением соседа, а «застреванием» соседства в промежуточном состоянии: определите, в каком именно, и объясните, на каком шаге синхронизации баз останавливается процесс.

4. Ответьте письменно: почему при несовпадении параметров маршрутизатор не сообщает соседу об ошибке, а молча отбрасывает его Hello? Какой из трёх случаев невозможно обнаружить без захвата трафика или отладочного журнала?

Что должно получиться

Для каждой из трёх неисправностей — таблица «симптом — гипотезы — проверки — причина — исправление» с выводами команд; выдержки из журнала и захвата, подтверждающие причину; ответы на вопросы пункта 4.

Часть 6. Две области, межобластные и внешние маршруты

Сеть делится так, как показано на схеме областей в теории: каналы r1 — r2, r1 — r3, r2 — r3 и интерфейсы lo маршрутизаторов r1–r3 остаются в магистральной области 0; каналы r2 — r4, r3 — r5, r4 — r5 и интерфейсы lo маршрутизаторов r4, r5 переходят в область 1. Маршрутизаторы r2 и r3 становятся пограничными (ABR).

Задание

1. Предсказать: какова будет стоимость пути от r1 до 10.255.0.4 и от r2 до 10.255.0.4 после разделения? Сравните с одной областью. Учтите правило: внутриобластной маршрут предпочитается межобластному независимо от стоимости.

2. Перенастройте r2 (на r3 — аналогично со своими сетями):

   configure terminal
   router ospf
    no network 10.0.0.0/16 area 0
    network 10.0.12.0/24 area 0
    network 10.0.23.0/24 area 0
    network 10.0.24.0/24 area 1
   end
   

   На r4 и r5 замените обе команды network на те же префиксы с area 1. Дождитесь состояния Full всех соседств.

3. Сравните базы r1 и r4 (show ip ospf database). Какие типы LSA есть в каждой? Объявления типа 1 каких маршрутизаторов отсутствуют в базе r1 и почему? Найдите в базе r1 объявления типа 3, созданные r2 и r3, для префикса 10.255.0.4/32 и сравните указанные в них стоимости (show ip ospf database summary 10.255.0.4). Объясните выбор r1.

4. Проверьте предсказание пункта 1 командой show ip ospf route на r1 и r2. Найдите в выводе метки IA (межобластной маршрут). Почему r2 теперь достигает r4 по прямому каналу стоимостью 6, хотя путь через r3 и r5 стоит 5?

5. Перераспределение. На r1 уже задан статический маршрут 198.51.100.0/24 blackhole, имитирующий внешнюю сеть. Внесите его в OSPF:

   router ospf
    redistribute static
   

   Найдите на r4 объявление типа 5 (show ip ospf database external) и объявление типа 4 (show ip ospf database asbr-summary). Кто создал каждое из них и зачем r4 нужно объявление типа 4? Как маршрут выглядит в show ip route на r4: тип, административное расстояние, метрика? Объясните, почему метрика равна 20 независимо от положения r4 в сети.

6. Суммаризация. На обоих ABR задайте area 1 range 10.255.0.4/31 в режиме router ospf. Предсказать, затем проверить: сколько объявлений типа 3 о префиксах 10.255.0.4/32 и 10.255.0.5/32 останется в базе r1? Какой маршрут появится в его таблице и с какой стоимостью? Удалите на r5 адрес обратной связи (interface lo, no ip address 10.255.0.5/32) — изменится ли что-нибудь в базе и таблице маршрутизации r1? Объясните, чем это полезно и чем опасно. Верните адрес командой ip address 10.255.0.5/32.

Что должно получиться

Предсказания и наблюдения стоимостей; сравнение баз r1 и r4 по типам LSA; выдержки объявлений типа 3, 4 и 5 с пояснением, кто и зачем их создал; маршрут O E2 на r4; результат суммаризации и ответ о выключении lo.

Часть 7. BFD, многопутевая маршрутизация и асимметрия (продвинутая)

Перед частью верните стенд к одной области: docker compose down && docker compose up -d && ./tools/base.sh --p2p.

Задание

1. Включите BFD для OSPF на обоих концах каналов r3 — r5 и r4 — r5 (интерфейсная команда ip ospf bfd). Проверьте сессии командами show bfd peers и show bfd peers brief на r5. Найдите в выводе интервалы передачи и приёма и множитель обнаружения; рассчитайте время обнаружения отказа.

2. Повторите опыт с невидимым отказом из части 4, п. 3, с таймерами Hello по умолчанию. Измерьте длительность перерыва и сравните с тремя предыдущими измерениями. Захватите на мосту br-n45 пакеты BFD (udp port 3784) и определите по захвату фактический интервал их передачи.

3. Многопутевая маршрутизация. Предсказать: какие маршруты r1 станут многопутевыми, если стоимость интерфейса r1 в сторону r3 уменьшить с 5 до 4? Проверьте калькулятором (измените копию topology.txt) и в FRR: show ip route ospf должен показать два следующих перехода у части маршрутов. Как ядро Linux распределяет трафик между ними (тема 8)?

4. Асимметрия. Верните стоимость 5 и задайте на r2 стоимость интерфейса в сторону r1, равную 10 (на r1 оставьте 2). Предсказать пути r1 → r2 и r2 → r1. Проверьте трассировками между адресами lo в обе стороны. Как асимметрия путей связана с правилом rp_filter из темы 8 и почему в контейнерах стенда он отключён?

Что должно получиться

Вывод show bfd peers с расчётом времени обнаружения; сводная таблица длительностей перерыва для четырёх способов обнаружения отказа; маршруты ECMP в FRR и в ядре (ip route); трассировки в обе стороны при асимметричных стоимостях с объяснением.

Журнал работы

Ведите для себя журнал: для каждой части записывайте предсказание, сделанное до эксперимента, команду, фактический вывод и объяснение расхождений. Таблицы, графики и файлы захватов, перечисленные в разделах «Что должно получиться», удобно хранить там же. В конце полезно сформулировать несколько предложений собственных выводов по работе.

Контрольные вопросы

1. Почему OSPF работает непосредственно поверх IP, а не поверх TCP, и как он при этом обеспечивает надёжную доставку объявлений?
2. Какие параметры должны совпадать у двух маршрутизаторов, чтобы они стали соседями, и почему несовпадение MTU проявляется иначе, чем несовпадение интервала Hello?
3. В широковещательном сегменте из шести маршрутизаторов сколько будет смежностей в состоянии Full с DR и без него? Какую роль играет BDR?
4. Почему выборы DR не вытесняющие и к какому неожиданному результату это привело в части 1?
5. Маршрутизатор r1 использует путь до r3 через r2, хотя у него есть прямой канал к r3. Объясните это по алгоритму Дейкстры и предложите изменение стоимостей, при котором будет использован прямой канал.
6. Отказ, видимый только одной стороне канала, обрабатывается OSPF быстро. Какое правило построения графа это обеспечивает?
7. Из каких слагаемых складывается время сходимости OSPF после невидимого отказа и какое из них устраняет BFD?
8. Почему объявления типа 3 делают межобластную маршрутизацию OSPF похожей на дистанционно-векторную и какое правило защищает её от петель?
9. Почему маршрут O E2 имеет одинаковую метрику на всех маршрутизаторах AS, а O E1 — разную? Когда предпочтителен каждый тип?
10. Чем полезна и чем опасна суммаризация area range на ABR?
11. Чем будет отличаться поведение RIP на той же топологии при невидимом отказе канала r4 — r5? Оцените время сходимости по таймерам RIP.