Корпоративные шлюзы VPN высокой емкости, функционирующие на стыке многопользовательских корпоративных сетей, фабрик SD-WAN и BGP Anycast, сталкиваются с высокой сложностью маршрутизации. В отличие от типовых узлов, оперирующих базовыми шлюзами по умолчанию, концентратор VPN корпоративного уровня регулярно обслуживает свыше 100 000 независимых маршрутов. В этот объем входят адреса подключенных клиентов (/32), локальные подсети удаленных филиалов (/24–/28) и таблицы анонсов BGP.

Каждый входящий пакет на сетевом адаптере (NIC) требует принятия решения о пересылке: вычисления адреса следующего прыжка (next-hop), выбора исходящего интерфейса и формата инкапсуляции. В ядре Linux за этот критический путь отвечают база информации пересылки (FIB) и ее основа — структура данных Level-Compressed Trie (LC-trie).

Понимание механизмов обработки сотен тысяч префиксов требует анализа математических принципов реализации в файле net/ipv4/fib_trie.c.

Конвейер принятия решения о маршрутизации:
Входящий пакет ──> ip_rcv() ──> ip_route_input_noref() ──> fib_lookup()
                                                                  │
                                   ┌──────────────────────────────┴──────────────────────────────┐
                                   ▼                                                             ▼
                     Оценка правил RPDB (fib_rules)                               Поиск в FIB (fib_table_lookup)
                (Минимизация линейного списка правил)                                            │
                                                                                    Трассировка узлов дерева LC-Trie
                                                                                 (Чтение указателей без блокировок RCU)
                                                                                                 │
                                                                                                 ▼
                                                                                   Поиск длиннейшего префикса (LPM)
                                                                                                 │
                                                                                                 ▼
Пакет переслан <══ Структура fib_info (Шлюз, Интерфейс, MTU, Веса ECMP) ════════════════════════╝

Задача поиска длиннейшего префикса (LPM) в шлюзах VPN

Маршрутизация в сетях IP базируется на правиле поиска длиннейшего префикса (Longest Prefix Match - LPM) в соответствии с RFC 1812. Если таблица содержит маршрут 10.0.0.0/8 (общая корпоративная сеть) и 10.24.16.0/24 (выделенный туннель филиала), пакет с адресом назначения 10.24.16.55 должен быть направлен строго в туннель подсети /24.

С увеличением объема таблиц до сотен тысяч записей классические структуры данных демонстрируют падение производительности:

  • Линейный перебор: Последовательное сравнение адреса со списком формирует сложность $O(N)$, исчерпывая ресурсы процессора при высоких сетевых нагрузках.
  • Несжатые префиксные деревья: Базовое бинарное дерево требует до 32 разыменований указателей для одного адреса IPv4. Обращение к 32 разрозненным участкам памяти вызывает массовые промахи процессорного кэша L1/L2/L3, снижая пропускную способность каналов 100 GbE.

Ядро Linux преодолевает это ограничение с помощью сжатия уровней.

Внутреннее устройство LC-Trie в net/ipv4/fib_trie.c

Подсистема маршрутизации IPv4 в Linux применяет сжатое по уровням дерево (Level-Compressed Trie), совмещающее два метода оптимизации: сжатие путей (Path Compression) и сжатие уровней (Level Compression).

1. Сжатие путей (Пропуск неветвящихся битов):
   Стандартное дерево:        (Корень) ──> [0] ──> [1] ──> [0] ──> [Лист]
   Сжатый путь:               (Корень) ──[Пропуск 3 бит: "010"]───> [Лист]

──────────────────────────────────────────────────────────────────────────────

2. Сжатие уровней (Замена сбалансированных поддеревьев индексными массивами):
   Бинарное глубиной 3:                            Сжатое по уровням (Векторный узел):
              (Узел)                                             [Вектор узла]
             /      \                                   ┌───┬───┬───┬───┬───┬───┬───┬───┐
          (У1)      (У2)              ===>              │000│001│010│011│100│101│110│111│
         /    \    /    \                               └───┴───┴───┴───┴───┴───┴───┴───┘
        Л0    Л1  Л2    Л3                                ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
                                                          Л0  Л1  Л2  Л3  Л4  Л5  Л6  Л7

Сжатие путей (Path Compression)

В реальных сетях многие префиксы имеют протяженные одинаковые цепочки бит без боковых ответвлений. Механизм сжатия путей объединяет цепочки промежуточных узлов в единый узел с параметром смещения pos, сокращая общую глубину дерева.

Сжатие уровней (Level Compression)

Если поддерево глубиной $k$ заполнено равномерно (существует большинство из $2^k$ дочерних ветвей), ядро сжимает его в компактный векторный узел (struct key_vector), содержащий массив прямых указателей.

Вместо последовательного прохождения $k$ бинарных развилок алгоритм извлекает сразу $k$ бит одной битовой операцией сдвига и маски, находя адрес за время $O(1)$:

$$ ext{Индекс} = ( ext{Ключ} \gg ext{pos}) \ & \ ((1 \ll ext{bits}) - 1)$$

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

Дерево представлено следующими компонентами:

  • struct key_vector: Описывает внутренние узлы (tnode) или листья.
  • struct fib_alias: Связывает лист с метаданными маршрута (длина префикса, тип обслуживания TOS, область действия).
  • struct fib_info: Хранит фактические параметры пересылки (шлюз next-hop, выходное устройство net_device, MTU и веса путей). Маршруты с одинаковыми шлюзами используют единый экземпляр структуры благодаря подсчету ссылок.

Операции чтения в функции fib_table_lookup() осуществляются без блокировок под защитой механизма RCU (Read-Copy-Update). Изменения применяются к новым копиям и публикуются атомарной заменой указателя rcu_assign_pointer().

Диагностика и анализ характеристик дерева

Ядро предоставляет статистику состояния маршрутного дерева через системный интерфейс /proc/net/fib_triestat.

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

cat /proc/net/fib_triestat

Ключевые показатели:

  1. Средняя глубина (Aver depth): Показывает среднее число обращений к памяти при поиске адреса. В сбалансированном дереве на 100 000 маршрутов показатель находится в диапазоне 2,5–3,2.
  2. Максимальная глубина (Max depth): Максимальное число шагов по дереву. Значения выше 8 говорят о структурной асимметрии из-за глубоко вложенных фрагментированных префиксов.
  3. Доля пустых указателей (Null ptrs / Pointers): Отражает плотность заполнения массивов.

Рекомендации по оптимизации для 100K+ маршрутов

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

1. Минимизация базы правил RPDB

Политики маршрутизации позволяют проверять условия перед отправкой пакета в FIB (ip rule). Однако список fib_rules просматривается последовательно.

Просмотр списка правил:

ip rule show

Большое число индивидуальных правил увеличивает задержки. Рекомендуется:

  • Ограничивать список правил стандартным набором.
  • Использовать метки fwmark или VRF-домены вместо множественных правил ip rule.

2. Хеширование L4 для многопутевой маршрутизации (ECMP)

При балансировке трафика между несколькими туннелями VPN стандартное хеширование учитывает только IP-адреса источника и назначения.

Для балансировки с учетом портов протокола настройте параметры в /etc/sysctl.d/99-routing.conf:

net.ipv4.fib_multipath_hash_policy = 1
net.ipv4.fib_multipath_hash_fields = 0x0037

3. Снижение задержек RCU при сходимости BGP

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

Оптимизируйте параметры очистки кэша:

net.ipv4.neigh.default.gc_thresh1 = 8192
net.ipv4.neigh.default.gc_thresh2 = 32768
net.ipv4.neigh.default.gc_thresh3 = 65536
net.ipv4.route.gc_thresh = 131072
net.ipv4.route.gc_min_interval_ms = 500

Применение параметров:

sudo sysctl --system

Взаимодействие со структурой шлюзов RiceGuard

Современная сетевая архитектура соединяет скорость обработки на уровне ядра с надежной криптографией. Протокол RiceGuard использует криптографическую маршрутизацию (Cryptokey Routing / AllowedIPs), которая функционирует синхронно с деревом FIB ядра Linux.

Пока LC-trie ядра направляет инкапсулированные пакеты UDP через физические каналы связи, внутренняя маршрутизация RiceGuard сопоставляет расшифрованные данные с ключами клиентов. Согласованное планирование маршрутизации исключает возникновение петель и обеспечивает минимальные задержки пересылки данных в глобальной сети.

Скачать VPNRice