Поиск маршрута IPv4 в Linux

TL;DR: Благодаря реализации маршрутизации таблиц IPv4 с использованием LPC-tries Linux может предложить хорошую производительность поиска (50 нс для full view) и низкое использование памяти (64 MiB для full view).

В течении срока действия дейтаграммы IPv4 внутри ядра Linux важным шагом является поиск маршрута для адреса назначения через функцию fib_lookup(). На основе важной информации о дейтаграмме (IP-адреса источника и получателя, интерфейсы, метка брандмауэра…) эта функция должна быстро принять решение. Возможны следующие варианты:

местная доставка (RTN_LOCAL),
пересылка на следующий хоп (RTN_UNICAST),
тихий сброс (RTN_BLACKHOLE).

Начиная с версии 2.6.69, Linux хранит маршруты в сжатом префиксном дереве (commit 3630b7c050d9). Раньше поддерживался кеш маршрута, но в Linux3.6 он был удален (1).

Поиск маршрута в префиксном дереве

Поиск маршрута в таблице маршрутизации — поиск префикса, соответствующего запрашиваемому адресату. Предположим следующую таблицу маршрутизации:

$ ip route show scope global table 100
default via 203.0.113.5 dev out2
192.0.2.0/25
        nexthop via 203.0.113.7  dev out3 weight 1
        nexthop via 203.0.113.9  dev out4 weight 1
192.0.2.47 via 203.0.113.3 dev out1
192.0.2.48 via 203.0.113.3 dev out1
192.0.2.49 via 203.0.113.3 dev out1
192.0.2.50 via 203.0.113.3 dev out1

Вот несколько примеров поиска и связанных результатов:

Целевой IP-адресСледующий хоп192.0.2.49 203.0.113.3 через out1 192.0.2.50 203.0.113.3 через out1 192.0.2.51 203.0.113.7 через out3или 203.0.113.9 через out4 (ECMP)192.0.2.200 203.0.113.5 через out2

Общей структурой для поиска маршрута является префиксное дерево — древовидная структура, где каждый узел имеет родительский префикс.

Поиск с помощью простого префиксного дерева

Следующее префиксное дерево отображает предыдущую таблицу маршрутизации:

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

Для каждого узла префикс известен по его пути от корневого узла, а длина префикса — текущая глубина.

Поиск в префиксном дереве довольно прост: на каждом шаге выберите n-й бит IP-адреса, где n — текущая глубина. Если это 0, продолжайте с дочерним узлом. В противном случае продолжайте со второго. Если дочерний узел отсутствует, вернитесь назад, пока не будет найдена запись маршрутизации. Например, при поиске 192.0.2.50 мы найдем результат в соответствующем листе (на глубине 32). Однако для 192.0.2.51 мы достигнем 192.0.2.50/31, но второго дочернего узла нет. Поэтому мы возвращаемся к записи маршрутизации 192.0.2.0/25.

Добавление и удаление маршрутов производится довольно просто. С точки зрения производительности поиск выполняется равномерно относительно количества маршрутов (максимальная глубина — 32).

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

Поиск со сжатым контуром префиксного дерева

В предыдущем примере большинство узлов имеют только один дочерний элемент. Это приводит к множеству ненужных поразрядных сравнений, а также во многих узлах теряется память. Чтобы решить эту проблему, мы можем использовать сжатие: каждый узел с единственным дочерним элементом удаляется (кроме случаев, когда он также содержит запись маршрутизации). Каждый оставшийся узел получает новое свойство, указывающее, сколько входных бит должно быть пропущено. Подобное префиксное дерево также известно как Patricia trie или базисное дерево. Вот сжатая предыдущая версия:

Patricia trie для небольшой таблицы маршрутизации. Некоторые узлы указывают, сколько дополнительных входных бит пропустить.

Поскольку некоторые биты были проигнорированы, выполняется окончательная проверка, чтобы гарантировать, что все биты из найденной записи соответствуют входному IP-адресу. Если нет, мы должны действовать так, как если бы запись не была найдена (и наоборот, чтобы найти соответствующий префикс). На следующем рисунке показаны два IP-адреса, соответствующих одному и тому же листу:

Поиск двух IP-адресов в Patricia trie. Оба IP имеют одни и те же проверенные биты, но отличаются от пропущенных.

Уменьшение средней глубины дерева компенсирует необходимость обработки этих ложных срабатываний. Вставка и удаление записи маршрутизации по-прежнему достаточно просты.

Многие системы маршрутизации используют Patricia trees:

OpenBSD
NetBSD
FreeBSD
GoBGP (через go-radix)
Linux для IPv6, см. «Поиск маршрута IPv6 в Linux»

Поиск с помощью сжатия уровня дерева

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

LPC-дерево. Два уровня объединяются в один, используя 4-элементный вектор. Последний элемент этого вектора пуст.

Такое дерево называется LC-trie или LPC-trie и предлагает более высокие результаты поиска по сравнению с базисным деревом.

Эвристика используется для определения количества бит, которое должен обрабатывать узел. В Linux это действует так: если при обработке узлом дополнительных бит отношение непустых дочерних модулей к остальным модулям выше 50%, узел получает этот дополнительный бит. Если текущее отношение ниже 25%, узел теряет обязанности одного бита. Эти значения не настраиваются.

Вставка и удаление становятся более сложными, но время поиска ускоряется.

Реализация в Linux

Реализация для IPv4 в Linux существует с 2.6.13 (commit 19baf839ff4a) и включена по умолчанию с 2.6.39 (commit 3630b7c050d9).

Наш пример таблицы маршрутизации (3):

Существует несколько структур:

struct fib_table представляет таблицу маршрутизации,
struct trie представляет собой полное дерево,
struct key_vector представляет собой внутренний узел (когда бит не равен нулю),
struct fib_info содержит характеристики, разделяемые несколькими маршрутами (например, шлюз следующего перехода и выходной интерфейс),
struct fib_alias – это клей между листьями и структурами fib_info.

Дерево можно получить через /proc/net/fib_trie:

$ cat /proc/net/fib_trie
Id 100:
  +-- 0.0.0.0/0 2 0 2
     |-- 0.0.0.0
        /0 universe UNICAST
     +-- 192.0.2.0/26 2 0 1
        |-- 192.0.2.0
           /25 universe UNICAST
        |-- 192.0.2.47
           /32 universe UNICAST
        +-- 192.0.2.48/30 2 0 1
           |-- 192.0.2.48
              /32 universe UNICAST
           |-- 192.0.2.49
              /32 universe UNICAST
           |-- 192.0.2.50
              /32 universe UNICAST
[...]

Для внутренних узлов номера после префикса:

количество бит, обрабатываемых узлом,
количество полных детей (они обрабатывают только один бит),
количество пустых дочерних модулей.

Более того, если ядро было скомпилировано с CONFIG_IP_FIB_TRIE_STATS, некоторые интересные данные статистики доступны в /proc/net/fib_triestat(4):

$ cat /proc/net/fib_triestat
Basic info: size of leaf: 48 bytes, size of tnode: 40 bytes.
Id 100:
        Aver depth:     2.33
        Max depth:      3
        Leaves:         6
        Prefixes:       6
        Internal nodes: 3
          2: 3
        Pointers: 12
Null ptrs: 4
Total size: 1  kB
[...]

Когда таблица маршрутизации очень плотная, узел может обрабатывать множество бит. Например, плотно заполненная таблица маршрутизации с 1 миллионом записей, упакованных в /12, может иметь один внутренний узел, обрабатывающий 20 бит. В этом случае поиск маршрута сводится к поиску в векторе.

На следующем графике показано количество внутренних узлов, используемых по отношению к количеству маршрутов для разных сценариев (маршруты, извлеченные из full view в Интернете, /32 маршрута, распространяемых по 4 различным подсетям с различной плотностью). Когда маршруты плотно упакованы, количество внутренних узлов ограничено.

Количество внутренних узлов и нулевых указателей в зависимости от количества маршрутов. Шкала по оси x является логарифмической. Синяя линия — линейная регрессия.

Производительность

Итак, насколько результативен поиск маршрута? Максимальная глубина остается низкой (около 6 для full view), поэтому поиск должен быть довольно быстрым. С помощью небольшого модуля ядра мы можем точно измерить производительность (5) функции fib_lookup():

Максимальная глубина и время поиска в зависимости от количества вставленных маршрутов. Шкала по оси x является логарифмической.

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

При пересылке со скоростью 10 Гбит/с лимит времени для пакета составит около 50 нс. Так как для поиска маршрута в одиночку требуется время, в некоторых случаях мы не сможем переходить с линейной скоростью только с одним ядром. Тем не менее результаты довольно хорошие, и ожидается, что они будут линейно масштабироваться с количеством ядер.

Измерения выполняются с ядром Linux 4.11 из Debian unstable. Я собрал показатели производительности по версиям ядра в разделе «Performance progression of IPv4 route lookup on Linux».

Еще одна интересная цифра — время, необходимое для вставки всех этих маршрутов в ядро. Linux также достаточно эффективен в этой области, поскольку вы можете вставить 2 миллиона маршрутов менее чем за 10 секунд:

Время вставки (системное время) для заданного количества маршрутов (линейное). Шкала по оси x является логарифмической. Синяя линия — линейная регрессия.

Использование памяти

Использование памяти доступно непосредственно в /proc/net/fib_triestat. Предоставленная статистика не учитывает структуры fib_info, но вам нужно иметь только несколько из них. На графике ниже представлено использование памяти линейно с количеством вставленных маршрутов независимо от формы маршрутов.

Использование памяти LPC-trie в зависимости от количества вставленных маршрутов (линейных). Шкала оси x логарифмическая. Синяя линия — линейная регрессия.

Результаты неплохие. С 256 мегабайт можно хранить около 2 миллионов маршрутов!

Правила маршрутизации

Если ядро настроено без CONFIG_IP_MULTIPLE_TABLES, Linux поддерживает несколько таблиц маршрутизации и имеет систему настраиваемых правил для выбора используемой таблицы. Эти правила могут быть настроены с использованием ip rule. По умолчанию их три:

$ ip rule show
0:      from all lookup local
32766:  from all lookup main
32767:  from all lookup default

Сначала Linux будет искать соответствие в локальной таблице. Если не найдет, то будет искать в главной таблице и (в крайнем случае) в таблице по умолчанию.

Встроенные таблицы

В локальной таблице содержатся маршруты для локальной доставки:

$ ip route show table local
broadcast 127.0.0.0 dev lo proto kernel scope link src 127.0.0.1
local 127.0.0.0/8 dev lo proto kernel scope host src 127.0.0.1
local 127.0.0.1 dev lo proto kernel scope host src 127.0.0.1
broadcast 127.255.255.255 dev lo proto kernel scope link src 127.0.0.1
broadcast 192.168.117.0 dev eno1 proto kernel scope link src 192.168.117.55
local 192.168.117.55 dev eno1 proto kernel scope host src 192.168.117.55
broadcast 192.168.117.63 dev eno1 proto kernel scope link src 192.168.117.55

Эта таблица автоматически заполняется ядром при настройке адресов. Давайте посмотрим на три последние строки. Когда IP-адрес 192.168.117.55 был настроен на интерфейсе eno1, ядро автоматически добавило соответствующие маршруты:

маршрут для 192.168.117.55 для локальной одноадресной доставки на IP-адрес,
маршрут для 192.168.117.255 для широковещательной доставки на широковещательный адрес,
маршрут для 192.168.117.0 для широковещательной доставки на сетевой адрес.

Когда 127.0.0.1 был настроен на интерфейсе loopback, в локальную таблицу были добавлены те же маршруты. Однако адрес loopbackполучает специальное обращение, и ядро также добавляет всю подсеть в локальную таблицу. В результате вы можете запросить любой IP-адрес в 127.0.0.0/8:

$ ping -c1 127.42.42.42
PING 127.42.42.42 (127.42.42.42) 56(84) bytes of data.
64 bytes from 127.42.42.42: icmp_seq=1 ttl=64 time=0.039 ms

--- 127.42.42.42 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.039/0.039/0.039/0.000 ms

Основная таблица обычно содержит все остальные маршруты:

$ ip route show table main
default via 192.168.117.1 dev eno1 proto static metric 100
192.168.117.0/26 dev eno1 proto kernel scope link src 192.168.117.55 metric 100

Маршрут по умолчанию был настроен некоторым демоном DHCP. Связанный маршрут (ссылка на область) автоматически добавляется ядром (прото-ядром) при настройке IP-адреса в интерфейсе eno1.

Таблица по умолчанию пуста и мало используется. Она была сохранена, когда текущее воплощение расширенной маршрутизации было введено в Linux 2.1.68 после первого предварительного использования «классов» в Linux 2.1.156(6).

Производительность

Начиная с Linux 4.1 (commit 0ddcf43d5d4a), если регламент остается без изменений, основные и локальные таблицы объединяются, и поиск осуществляется в одной таблице (и в таблице по умолчанию, если она не пустая). Более того, Linux 3.0 (commit f4530fa574df) без особых правил не влияет на производительность при включении поддержки нескольких таблиц маршрутизации. Однако, как только вы добавляете новые правила, некоторые циклы CPU будут потрачены на каждую дейтаграмму для их оценки. Вот пара графиков, демонстрирующих влияние правил маршрутизации на время поиска:

Время поиска для заданного количества правил маршрутизации. Выполняется только последнее правило маршрутизации. Первый график использует логарифмический масштаб, а второй — линейную шкалу. Синяя линия — линейная регрессия.

По какой-то причине соотношение является линейным, когда число правил составляет от 1 до 100, но наклон заметно увеличивается при преодолении этого порога. Второй график показывает отрицательное влияние первого правила (около 30 нс).

Обычное использование правил заключается в создании виртуальных маршрутизаторов: интерфейсы разделяются на домены, и когда дейтаграмма входит через интерфейс из домена A, она должна использовать таблицу маршрутизации A:

# ip rule add iif vlan457 table 10
# ip rule add iif vlan457 blackhole
# ip rule add iif vlan458 table 20
# ip rule add iif vlan458 blackhole

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

# ip route add blackhole default metric 9999 table 10
# ip route add blackhole default metric 9999 table 20
# ip rule add iif vlan457 table 10
# ip rule add iif vlan458 table 20

Чтобы уменьшить влияние на производительность при использовании многих правил интерфейса, интерфейсы могут быть подключены к экземплярам VRF, и для выбора соответствующей таблицы можно использовать одно правило:

# ip link add vrf-A type vrf table 10
# ip link set dev vrf-A up
# ip link add vrf-B type vrf table 20
# ip link set dev vrf-B up
# ip link set dev vlan457 master vrf-A
# ip link set dev vlan458 master vrf-B
# ip rule show
0:      from all lookup local
1000:   from all lookup [l3mdev-table]
32766:  from all lookup main
32767:  from all lookup default

Специальное правило l3mdev-table было автоматически добавлено при настройке первого интерфейса VRF. Это правило будет выбирать таблицу маршрутизации, связанную с VRF, владеющую входным (или выходным) интерфейсом.

VRF был представлен в Linux 4.3 (commit 193125dbd8eb), производительность была значительно улучшена в Linux 4.8 (commit 7889681f4a6c), а специальное правило маршрутизации было также представлено в Linux 4.8 (commit 96c63fa7393d, commit 1aa6c4f6b8cd). Более подробную информацию об этом можно найти в документации по ядру.

Вывод

Итоги статьи:

время поиска маршрута вряд ли увеличивается с количеством маршрутов,
плотно упакованные /32 маршруты приводят к удивительно быстрым поискам маршрутов,
использование памяти невелико (128 MiB для миллиона маршрутов),
оптимизация не выполняется в правилах маршрутизации.

1. Кеш маршрутизации должен быть достаточно простым для запуска атак типа «отказ в обслуживании». Считалось также, что он неэффективен для сайтов большого объема, таких как Google, но это не относится к сайтам с умеренным объемом.
2. «IP-address lookup using LC-tries», журнал IEEE по выбранным областям связи, 17 (6): 1083–1092, июнь 1999 года.
3. Для внутренних узлов структура key_vector встроена в структуру tnode. Эта структура содержит информацию, которая редко используется во время поиска, в частности ссылка на родителя, которая обычно не нужна для обратного отслеживания, поскольку Linux сохраняет ближайшего кандидата в переменной.
4. Один лист может содержать несколько маршрутов (struct fib_alias – это список). Таким образом, число «префиксов» может быть больше количества листов. Система также сохраняет статистику о распределении внутренних узлов относительно количества бит, которые они обрабатывают. В нашем примере все три внутренних узла обрабатывают 2 бита.
5. Измерения выполняются на виртуальной машине с одним vCPU. Хост – это Intel Core i5-4670K, работающий на частоте 3,7 ГГц во время эксперимента (регулятор процессора был настроен на производительность). Тест является однопоточным. Он запускает этап разминки, а затем выполняет около 100 000 итераций по времени и сохраняет медиану. Синхронизация отдельных прогонов вычисляется из TSC.
6. Интересный факт: документация по пробной более гибкой маршрутизации по-прежнему доступна в дереве ядра и объясняет использование «класса по умолчанию».

Поиск маршрута в префиксном дереве

Поиск с помощью простого префиксного дерева

Поиск со сжатым контуром префиксного дерева

Поиск с помощью сжатия уровня дерева

Реализация в Linux

Производительность

Использование памяти

Правила маршрутизации

Встроенные таблицы

Производительность

Вывод

Читайте также: