Tiếng Việt
English
中文
Español
हिन्दी
Français
Português
Русский
Deutsch
日本語
한국어
Italiano
Bahasa Indonesia
ไทย
বাংলা
ລາວ
မြန်မာ
العربية
فارسی
اردو
Українська
Română
Azərbaycan
Корпоративні шлюзи 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 та ваги ECMP). Маршрути зі спільними шлюзами використовують єдиний екземпляр структури завдяки підрахунку посилань.
Усі операції читання у fib_table_lookup() відбуваються без блокувань завдяки RCU (Read-Copy-Update). Оновлення застосовуються атомарно через rcu_assign_pointer().
Діагностика стану маршрутного дерева
Ядро надає детальну телеметрію щодо характеристик дерева через інтерфейс /proc/net/fib_triestat.
Перевірка параметрів головної таблиці:
cat /proc/net/fib_triestat
Основні показники:
- Середня глибина (
Aver depth): Середня кількість кроків звернення до пам'яті на один пакет. У збалансованому дереві на 100 000 маршрутів значення становить 2,5–3,2. - Максимальна глибина (
Max depth): Найгірший випадок проходження дерева. Показник понад 8 вказує на структурну асиметрію. - Порожні покажчики (
Null ptrs / Pointers): Співвідношення вільних комірок у векторних масивах.
Стратегії оптимізації для 100K+ маршрутів
Для збереження стабільної продуктивності на великих таблицях маршрутизації варто дотримуватися кількох правил.
1. Зменшення навантаження на базу правил RPDB
Правила маршрутизації (ip rule) дозволяють спрямовувати пакети за певними критеріями, але ядро перевіряє їх послідовно.
Перевірка активних правил:
ip rule show
Велика кількість окремих правил збільшує затримку. Рекомендовано:
- Зберігати мінімальну кількість правил.
- Об'єднувати умови за допомогою міток fwmark або VRF-доменів.
2. Налаштування багатопутевого хешування L4 (ECMP)
Стандартне балансування трафіку між декількома тунелями VPN у Linux враховує лише IP-адреси відправника та отримувача.
Для розподілу потоків з урахуванням портів активуйте режим L4 у /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
Надійна мережева безпека поєднує оптимізацію ядра з криптографічними гарантіями протоколів. Розроблений VPNRice протокол RiceGuard застосовує маршрутизацію за криптографічними ключами (Cryptokey Routing / AllowedIPs), яка діє узгоджено з таблицею FIB у ядрі Linux.
Поки LC-trie ядра спрямовує інкапсульовані пакети UDP у фізичні інтерфейси, внутрішній механізм RiceGuard верифікує розшифровані дані з ключами клієнтів. Такий підхід запобігає утворенню петель маршрутизації та гарантує мінімальні затримки передавання даних у масштабах усієї глобальної мережі.
