В предыдущей статье я описал общую архитектуру Quagga и устройство таблицы маршрутизации, которая находится в демоне zebra. В этой статье я хочу рассказать об устройстве демона bgpd, ответственного за реализацию протокола BGP.

Я не буду описывать общие сведения о протоколе BGP. Про него имеется огромное количество хороших статей и книг, и ознакомиться с логикой его работы можно, например, здесь. Я же сосредоточусь на механизме его реализации в демоне bgpd. Для удобства, описание работы демона bgpd можно разделить на две части.

Первую часть назовем таблицей BGP (по аналогии с таблицей маршрутизации). Здесь хранятся все известные маршруты BGP с их атрибутами, делаются сравнения различных маршрутов BGP и выбираются наилучшие.

Вторую часть назовем обвязкой. Обвязка – это многочисленные настройки, которые влияют на то, какие маршруты попадут в таблицу BGP, какие маршруты будут анонсированы соседям, каким образом изменяются атрибуты маршрутов BGP и т.д. Т.е. это различные distribute-list, prefix-list, route-map, redistribute и прочее.

Таблица BGP

Таблица BGP по своему устройству очень похожа на таблицу маршрутизации в zebra. Точно так же каждому префиксу соответствует несколько различных маршрутов, полученных от разных источников. Только вместо административной дистанции и метрики используются различные атрибуты BGP, как показано на рисунке.



Здесь показаны только атрибуты, влияющие на выбор наилучшего маршрута. Например, атрибут community напрямую на выбор наилучшего маршрута не влияет и на рисунке не показан.

Также у каждого маршрута хранится указатель на соседа BGP (BGP Peer) от которого маршрут был получен, что позволяет использовать соответствующие данные о соседе, а именно: тип соседа (IBGP или EBGP), его router-id и ip-адрес. При получении или удалении очередного маршрута запускается процедура, которая при помощи последовательного попарного сравнения маршрутов выбирает наилучший для данного префикса.

Алгоритм сравнения двух маршрутов BGP

Из двух маршрутов лучшим считается у которого (критерии перечислены в порядке уменьшения приоритета):

1. Большее значение Weight.
2. Большее значение Local Preference.
3. Маршрут создан локально (при помощи команды network, redistribute или aggregate-address).
4. Более короткий AS-PATH.
5. Меньшее значение Origin (IGP < EGP < INCOMPLETE)
6. Меньшее значение MED.
7. Тип соседа, от которого получен маршрут (eBGP лучше чем iBGP)
8. Меньшая метрика IGP до указанного в маршруте next-hop.
9. Если оба маршрута eBGP, то ранее выбранный в качестве лучшего (т.е. более старый) маршрут более предпочтителен.
10. Меньшее Router-ID соседа.
11. Более короткий Cluster list.
12. Меньший IP-адрес соседа.

В вышеприведённом примере маршрут, помеченный зеленым цветом является лучшим, поскольку у него наибольший Local Preference.

Если у каких-либо маршрутов совпали первые 8 пунктов с лучшим маршрутом, то они (при настройке maximum-paths больше 1) запоминаются и далее могут быть обработаны и переданы в zebra в качестве multi-path маршрута.

Точно так же, как и в zebra все используемые в таблице BGP префиксы организованы в виде префиксного дерева, и используется тот-же самый алгоритм для быстрого поиска нужного префикса.

Обвязка

Обвязка вокруг таблицы BGP показана на рисунке.



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

Получение маршрута BGP от соседа

До того, как маршруты попадут в таблицу BGP, они проходят несколько этапов, на которых они могут отфильтроваться или измениться. Путь маршрута от получения его от соседа до попадания в таблицу BGP показан на рисунке. Жирным шрифтом показаны команды, включающие соответствующий функционал.



Первым делом, при получении пакета, происходит его парсинг, т.е. содержимое пакета анализируется, проверяется на корректность и из данных, содержащихся в пакете формируется внутренняя структура, представляющая маршрут BGP.

Далее выполняется проверка aspath loop, т.е. проверка того, что в AS-PATH не содержится номер автономной системы, которой принадлежит маршрутизатор. Данная проверка является ключевой для предотвращения петель маршрутизации в протоколе BGP.

Затем, выполняются различные механизмы фильтрации маршрута, если они настроены для соседа BGP, от которого был получен пакет. Distribute-list фильтрует маршрут на основании ip-адреса префикса, prefix-list на основании ip-адреса префикса и его длины, filter-list фильтрует на основании содержимого AS-PATH маршрута BGP.

Если маршрут успешно прошел все этапы фильтрации, то к нему применяется входящий route-map. Здесь, можно достаточно гибко модифицировать атрибуты полученного BGP маршрута. В зависимости от префикса и различных атрибутов маршрута BGP, таких как AS-PATH, community, MED, next-hop, origin, ip-адреса соседа BGP можно менять weight, AS-PATH, community, next-hop, local preference, MED, origin или также отфильтровывать маршрут.

Теперь наш маршрут практически готов для добавления в таблицу BGP, и последним шагом остается запросить у zebra валидность next-hop и метрику до него.

Локальное создание маршрута BGP

Маршрут BGP может также создаваться локально при помощи команд network или redistribute. На рисунке приведены схемы добавления таких маршрутов.



Добавление маршрута при помощи команды network довольно просто. В отличие от Cisco, Quagga не проверяет наличие данного маршрута в таблице маршрутизации zebra. Поэтому данный маршрут заполняется значениями по-умолчанию, применяется route-map для изменения его атрибутов и маршрут добавляется в таблицу BGP.

При вводе команды redistribute демон bgpd обращается к демону zebra с просьбой подписать (пометить) его на добавления или удаления маршрутов определенного типа (например, OSPF) в таблице маршрутизации. Когда в таблице маршрутизации добавляется новый маршрут, zebra последовательно проверяет какие демоны подписаны на маршруты данного типа и отсылает подписавшимся демонам этот маршрут. После получения нового маршрута из zebra демон bgpd меняет MED, применяет route-map и добавляет его в таблицу BGP.

Отсылка нового маршрута соседям BGP

После выбора нового лучшего маршрута BGP данный маршрут отсылается соседям BGP. При этом последовательно перебираются все соседи BGP и проверяется, нужно ли данному соседу отсылать маршрут. Данная процедура, выполняемая для каждого соседа BGP показана на рисунке.



Первым делом проверяется, что получатель маршрута не является соседом, от которого данный маршрут был получен.

Далее проверяется community маршрута. Если community содержит значение no-advertise, то маршрут не анонсируется. Также маршрут не анонсируется, если тип получателя eBGP, а community содержит значение no-export.

Затем идет фильтрация при помощи исходящих distribute-list, prefix-list и filter-list аналогично, как это делалось для входящих маршрутов BGP.

Проверяется, что маршрут, полученный от соседа iBGP не должен передаваться другому соседу iBGP (предполагаем, что не используется Route Reflector).

Для маршрутов, у которых не было Local Preference устанавливается Local Preference по-умолчанию. Если имеется настройка neighbor 1.1.1.1 next-hop-self, либо сосед является eBGP, то next-hop заменяется на собственный ip-адрес.

Применяется исходящий route-map, позволяющий менять атрибуты анонсируемого маршрута, либо отфильтровать его на последнем этапе.

После успешного прохождения всех предыдущих шагов из маршрута BGP формируется пакет BGP Update который отсылается соседу.

Отсылка нового маршрута в zebra

Помимо отсылки нового маршрута BGP своим соседям, маршрутизатор также отсылает данный маршрут в zebra. Данная процедура показана на рисунке.



Перед отсылкой маршрута в zebra для него устанавливается Административная Дистанция в зависимости от типа маршрута (iBGP или eBGP). Из BGP маршрута берутся все нужные поля: тип маршрута (BGP), next-hop (или несколько next-hop, если используется multi-path) и метрика, после чего маршрут отсылается в zebra и начинает конкурировать с маршрутами от других протоколов маршрутизации.

Заключение

Безусловно, в данной статье описаны не все возможности BGP в Quagga. Я не рассматривал функционал route-reflector, конфедераций, IPv6 и т.д. Тем не менее вышеприведенная архитектура демона bgpd в основном сохраняется и с учетом этого функционала. Ниже приведено краткое описание реализации некоторых дополнительных возможностей демона bgpd.

Для использования IPv6 создается отдельная таблица BGP, в которой вместо префиксов IPv4 используются префиксы IPv6. Вся остальная логика работы таблицы BGP для IPv6 и ее обвязки остается более-менее аналогичной вышеописанной логике работы для IPv4.

При использовании Route-Reflector немного меняется логика проверки каким соседям отсылать маршруты BGP, а при получении маршрута появляются дополнительные проверки для исключения петель (проверки атрибутов Originator ID и Cluster List).

Небольшие изменения в работе алгоритма выбора лучшего маршрута в таблице BGP (так сказать его тонкая настройка) могут быть сделаны при помощи следующих глобальных настроек BGP:

• bgp bestpath as-path ignore — пропускает п.4 (сравнение длин AS-PATH)
• bgp bestpath compare-routerid – пропускает п.9 (выбор более старого маршрута)
• bgp bestpath med missing-as-worst – в случае, если у маршрута отсутствует MED, то данная настройка считает, что у маршрута настроен максимально возможный MED. Без данной настройки отсутствующий MED считается равным 0.
• bgp always-compare-med – позволяет сравнивать MED у маршрутов, полученных из разных AS. Без данной настройки п.6 для маршрутов, полученные из разных AS пропускается.
• bgp deterministic-med – меняет порядок сравнения маршрутов. Вместо последовательного сравнения маршрутов друг с другом, сначала сравниваются друг с другом маршруты, полученные от одной и той-же AS. Подробнее про данную настройку можно почитать здесь.