گیت‌وی‌های VPN در ابعاد سازمانی که در نقطه تلاقی شبکه‌های محلی، ساختارهای SD-WAN و شبکه‌های BGP Anycast فعالیت می‌کنند، با حجم بسیار بالایی از مسیرهای مسیریابی مواجه هستند. بر خلاف مسیریاب‌های خانگی با چند مسیر ساده، یک سرور متمرکز VPN معمولا بیش از ۱۰۰ هزار مسیر شبکه مجزا را هدایت می‌کند. این مسیرها شامل آدرس کاربران (/32)، زیرشبکه‌های شعب سازمانی (/24 تا /28) و جداول تبادل BGP هستند.

ورود هر بسته از کارت شبکه (NIC) نیازمند تصمیمی سریع برای تعیین گام بعدی (next-hop)، رابط خروجی و نوع کپسوله‌سازی است. در هسته لینوکس، این فرآیند حیاتی توسط پایگاه اطلاعات هدایت (FIB) و ساختار داده Level-Compressed Trie (یا LC-trie) مدیریت می‌شود.

درک توانایی هسته در حفظ سرعت خطی روی صدها هزار پیشوند شبکه، نیازمند بررسی اصول ریاضی در فایل net/ipv4/fib_trie.c است.

مسیر تصمیم‌گیری برای هدایت بسته:
بسته ورودی ──> ip_rcv() ──> ip_route_input_noref() ──> fib_lookup()
                                                              │
                               ┌──────────────────────────────┴──────────────────────────────┐
                               ▼                                                             ▼
                 بررسی قوانین مسیریابی (RPDB)                                  جستجو در جدول FIB (fib_table_lookup)
              (کاهش بررسی‌های خطی و زنجیره‌ای)                                                │
                                                                                 پیمایش گره‌های درخت LC-Trie
                                                                             (خواندن اشاره‌گرها بدون قفل با RCU)
                                                                                             │
                                                                                             ▼
                                                                             انطباق طولانی‌ترین پیشوند (LPM)
                                                                                             │
                                                                                             ▼
هدایت نهایی بسته <══ ساختار fib_info (گیت‌وی، رابط خروجی، MTU، وزن‌های ECMP) ═══════════════╝

چالش انطباق طولانی‌ترین پیشوند (LPM) در شبکه‌های پرظرفیت

مسیریابی در شبکه‌های IP بر اساس قاعده انطباق طولانی‌ترین پیشوند (Longest Prefix Match - LPM) مطابق با RFC 1812 انجام می‌شود. چنانچه در جدول، هم مسیر کلان 10.0.0.0/8 و هم مسیر جزئی 10.24.16.0/24 وجود داشته باشد، بسته‌ای با مقصد 10.24.16.55 حتما باید به سمت تونل اختصاصی /24 هدایت گردد.

با افزایش تعداد مسیرها به صدها هزار مورد، الگوریتم‌های سنتی با افت کارایی مواجه می‌شوند:

  • پیمایش خطی: مقایسه ترتیبی آدرس مقصد دارای پیچیدگی $O(N)$ بوده و پردازنده را به سرعت اشباع می‌کند.
  • درخت‌های باینری فشرده‌نشده: یک درخت استاندارد برای هر آدرس IPv4 نیازمند ۳۲ مرحله رجوع به حافظه است. پرش بین ۳۲ نقطه مجزا در حافظه باعث افت شدید کش پردازنده (L1/L2/L3) شده و گذردهی درگاه‌های پرسرعت 100 GbE را محدود می‌سازد.

هسته لینوکس با بهره‌گیری از فشرده‌سازی سطحی، این مانع را برطرف نموده است.

ساختار درونی LC-Trie در net/ipv4/fib_trie.c

زیرسیستم مسیریابی IPv4 در لینوکس از یک درخت فشرده ترکیبی بهره می‌برد که دو شیوه بهینه‌سازی را همگام می‌سازد: فشرده‌سازی مسیر (Path Compression) و فشرده‌سازی سطحی (Level Compression).

۱. فشرده‌سازی مسیر (حذف بیت‌های بدون انشعاب):
   درخت باینری معمولی:        (ریشه) ──> [0] ──> [1] ──> [0] ──> [برگ]
   مسیر فشرده‌شده:           (ریشه) ──[پرش از ۳ بیت: "010"]────> [برگ]

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

۲. فشرده‌سازی سطحی (جایگزینی زیردرخت‌ها با آرایه‌های برداری مستقیم):
   زیردرخت باینری با عمق ۳:                       فشرده‌سازی سطحی (گره برداری):
              (گره)                                             [بردار گره]
             /     \                                    ┌───┬───┬───┬───┬───┬───┬───┬───┐
          (گ۱)     (گ۲)               ===>              │000│001│010│011│100│101│110│111│
         /    \   /    \                                └───┴───┴───┴───┴───┴───┴───┴───┘
        ب۰    ب۱ ب۲    ب۳                                 ▲   ▲   ▲   ▲   ▲   ▲   ▲   ▲
                                                          ب۰  ب۱  ب۲  ب۳  ب۴  ب۵  ب۶  ب۷

فشرده‌سازی مسیر (Path Compression)

در شبکه‌های واقعی، بخش زیادی از پیشوندها فاقد انشعاب‌های جانبی در بیت‌های ابتدایی هستند. الگوریتم فشرده‌سازی مسیر، گره‌های بدون انشعاب را در یک گره منفرد ادغام کرده و با متغیر pos عمق درخت را به حداقل می‌رساند.

فشرده‌سازی سطحی (Level Compression)

هرگاه زیردرختی با عمق $k$ به شکلی متوازن پر شده باشد، هسته لینوکس کل آن زیردرخت را به یک گره آرایه‌ای برداری (struct key_vector) تبدیل می‌کند که شامل $2^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: ذخیره‌کننده مشخصات انتقال (آدرس گیت‌وی بعدی، رابط net_device، مشخصه MTU). مسیرهایی با گیت‌وی مشترک از یک ساختار واحد استفاده کرده و مصرف حافظه رم را کاهش می‌دهند.

تمامی عملیات خواندن در تابع fib_table_lookup() بدون قفل‌گذاری و تحت محافظت RCU اجرا می‌شود و به‌روزرسانی‌ها به شکل اتمیک منتشر می‌گردند.

تحلیل کارایی و بررسی وضعیت درخت مسیریابی

هسته لینوکس داده‌های تله‌متری درخت را در مسیر /proc/net/fib_triestat نمایش می‌دهد.

مشاهده وضعیت جدول اصلی:

cat /proc/net/fib_triestat

معیارهای مهم در ارزیابی:

۱. عمق میانگین (Aver depth): بیانگر متوسط دسترسی به حافظه به ازای هر بسته است. در درختی بهینه با ۱۰۰ هزار مسیر، این مقدار بین ۲.۵ تا ۳.۲ قرار دارد. ۲. عمق حداکثر (Max depth): طولانی‌ترین مسیر پیمایش را نشان می‌دهد. مقادیر بالای ۸ نشانه وجود زیرشبکه‌های ناپیوسته و تودرتو است. ۳. اشاره‌گرهای خالی (Null ptrs / Pointers): نرخ فضاهای رزرو نشده در آرایه‌های برداری را مشخص می‌کند.

توصیه‌های پیکربندی برای بیش از ۱۰۰ هزار مسیر

دستیابی به بالاترین کارایی در شبکه‌های پرمسیر مستلزم تنظیم دقیق گزینه‌های سیستمی است.

۱. ساده‌سازی قوانین سیاست مسیریابی (RPDB)

قوانین مسیریابی سفارشی (ip rule) امکانات مفیدی فراهم می‌کنند، اما لیست fib_rules به صورت خطی بررسی می‌شود.

مشاهده قوانین فعال:

ip rule show

تعریف قوانین متعدد و جزئی باعث افزایش تاخیر می‌شود. بهتر است:

  • تعداد قوانین در کمترین حد نگه داشته شود.
  • منطق‌های شرطی با برچسب‌های fwmark یا دامنه‌های VRF مدیریت گردند.

۲. فعال‌سازی هش چندمسیره L4 در توزیع بار (ECMP)

در حالت پیش‌فرض، توزیع ترافیک بین چند تونل VPN تنها بر اساس آدرس‌های IP مبدا و مقصد لایه ۳ انجام می‌شود.

برای توزیع متوازن‌تر ترافیک با احتساب پورت‌ها، تنظیمات زیر را در /etc/sysctl.d/99-routing.conf اعمال کنید:

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

۳. کنترل تاخیرهای RCU در زمان همگرایی BGP

دریافت حجم انبوهی از تغییرات مسیر در ثانیه از طریق 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 trie لینوکس هماهنگ است.

در حالی که درخت LC-trie بسته‌های رمزنگاری‌شده را به سوی رابط‌های فیزیکی هدایت می‌کند، سازوکار داخلی RiceGuard تطابق بسته‌های رمزشکنی‌شده با کلیدهای معتبر را تایید می‌نماید. این تفکیک هوشمندانه مانع از ایجاد حلقه‌های مسیریابی شده و سرعت تبادل پایدار داده‌ها را در سراسر شبکه تضمین می‌کند.

دریافت VPNRice