За родом своєї діяльності я займаюся проектуванням мереж і налаштуванням мережевого обладнання. У якийсь момент часу мені захотілося дізнатися як-же влаштовані мережеві пристрої, які завжди представляли для мене чорні ящики, що магічно реалізують мережеві протоколи. Оскільки пристрої від вендорів типу Cisco або Juniper закриті і не доступні для будь-якого вивчення, то мій вибір припав на програму Quagga - маршрутизатор з відкритими вихідними кодами, який досить широко використовується в реальному житті і досить успішно справляється з протоколами OSPF і BGP. Озброївшись вихідцями Quagga я приступив до дослідження. У даній статті я хочу розповісти як влаштована таблиця маршрутизації в Quagga, які структури і алгоритми використовуються для її реалізації.
Архітектура Quagga
Для початку декілька слів про загальну архітектуру Quagga. Quagga складається з декількох окремих програм, або демонів, кожен з яких виконує певну функцію. Наприклад, фонова служба ospfd реалізує протокол OSPF, а bgpd - протокол BGP. Центральну роль у Quagga виконує демон zebra. Одна з основних його ролей полягає в отриманні маршрутної інформації від демонів, що реалізують конкретні протоколи і відборі кращих маршрутів, отриманих з різних джерел. Після цього кращі маршрути передаються в ядро Linux, яке власне передає користувацький трафік (вважаємо, що Quagga встановлена на Linux). Таким чином реалізується класичний поділ «інтелекту» маршрутизатора (Control Plane) і передачі користувацького трафіку (Data Plane). У нашому випадку в якості Control Plane виступає Quagga, а в якості Data Plane - ядро Linux. Таблиця маршрутизації Quagga при цьому знаходиться всередині фонової служби zebra.
Зберігання маршрутної інформації
Кожен окремий маршрут у таблиці маршрутизації можна представити як префікс (зазвичай позначається як ip-адреса і довжина префікса, наприклад 192.168.0.0/24), з якими пов'язана різна маршрутна інформація: next-hop, адміністративна дистанція, метрика, протокол який повідомив про маршрут тощо. Таблиця маршрутизації - це просто безліч таких префіксів із пов'язаною з ними додатковою інформацією. Демон zebra зберігає всі маршрути, які їй були передані або були налаштовані в самій zebra. Наприклад, якщо був налаштований статичний маршрут 192.168.0.0/24 з next-hop 1.1.1.1, а також був отриманий маршрут з тим же префіксом з демона ospfd і з next-hop 2.2.2.2, то zebra буде зберігати обидва цих маршрути і покаже їх у виведенні команди show ip route. Зберігання всіх маршрутів дозволяє швидко вибрати новий кращий маршрут, якщо з якихось причин поточний кращий маршрут перестав існувати. Наприклад, у нашому прикладі, після видалення статичного маршруту, zebra відразу вибере в якості кращого маршрут OSPF без будь-якого звернення до демона ospfd. Маршрути для конкретного префікса зберігаються у вигляді зв'язкового списку, як показано на малюнку (в даному випадку для префікса 192.168.0.0/24). Зеленим позначено найкращий маршрут.
При отриманні чергового маршруту його маршрутна інформація додається до початку зв'язкового списку, після чого запускається процедура послідовного перегляду всіх маршрутів для даного префіксу і вибору найкращого. Найкращим маршрутом (за умови валідності next-hop) є маршрут з найменшою адміністративною дистанцією. Оскільки за замовчуванням у маршрутів від різних протоколів різна адміністративна дистанція (наприклад, у OSPF - 110, у статичного маршруту - 1), то саме адміністративна дистанція і є визначальним критерієм для вибору найкращого маршруту. У разі, якщо налаштування такі, що у різних маршрутів налаштована однакова адміністративна дистанція, то найкращим є маршрут з найменшою метрикою. Якщо ж у маршрутів збігаються і адміністративна дистанція і метрика, то кращим буде маршрут, який знаходиться ближче до кінця списку, тобто той, який був доданий раніше.
При видаленні маршруту, даний маршрут видаляється зі списку маршрутів для даного префікса і точно також запускається процедура вибору кращого маршруту. Наприклад, після видалення статичного маршруту картина виглядатиме наступним чином:
Після вибору найкращого маршруту інформація про нього передається в ядро Linux.
Зберігання префіксів
Як правило, маршрутів для одного префіксу небагато і переглянути їх все для вибору найкращого багато часу не займає. Набагато більш складне завдання - при додаванні або видаленні маршруту знайти сам префікс. Різних префіксів у таблиці маршрутизації може бути дуже багато - тисячі і десятки тисяч, і простий послідовний перебір всіх префіксів для знаходження потрібного буде вкрай неефективним. Для більш швидкого та ефективного пошуку всі префікси в таблиці маршрутизації зберігаються у вигляді структури, званої compact trie або стиснутим бінарним префіксним деревом.
Надалі префікси буде більш зручно представляти в двійковому вигляді, вказуючи при цьому тільки перші біти, в кількості рівній довжині префіксу. Інші біти префікса дорівнюють 0 і не важливі для пошуку. Наприклад, префікс 10.0.0.0/8 у двійковому вигляді виглядатиме як 00001010, префікс 128.0.0.0/1 виглядатиме як 1, 128.0.0.0/2 як 10 тощо.
Що таке trie або префіксне дерево і як воно працює можна почитати, наприклад, тут. Для наших цілей найпростіше його зрозуміти на прикладі. Наприклад, у нас є префікси 1, 111, 010, 0110000. Дані префікси будуть організовані у вигляді наступного префіксного дерева:
Білі вузли відповідають префіксам, які нас цікавлять. Жовті вузли є проміжними і служать для правильної організації структури дерева. Верхній вузол є коренем дерева і відповідає префіксу 0.0.0.0/0. Пошук потрібного префікса виконується наступним чином: Починається пошук з кореня дерева. Потім перевіряється перший біт шуканого префіксу. Якщо перший біт дорівнює 0, то спускаємося до лівого дочірнього елемента. Якщо перший біт дорівнює 1, то до правого дочірнього елемента. Потім повторюємо дану процедуру для другого біта шуканого префіксу, потім для третього і т. д. до тих пір, поки не дійдемо до шуканого префіксу або переконаємося що його немає. За відсутності потрібного префіксу він додається до дерева у відповідне місце. Видно, що число звернень до дерева дорівнює довжині шуканого префікса і для найдовшого префікса IPv4 дорівнює 32. Строго кажучи в кожному вузлі дерева необов'язково зберігати сам префікс, оскільки він однозначно визначається місцем розташування вузла, але я вказав його для наочності. Крім того, в реальній структурі Quagga префікс дійсно зберігається в кожному вузлі дерева.
Стиснуте префіксне дерево відрізняється від звичайного тим, що воно оптимізує довгі ланцюжки без гілок. Для нашого прикладу стиснуте префіксне дерево буде виглядати наступним чином:
Тепер при пошуку префікса в поточному вузлі перевіряємо, чи збігаються перші n біт шуканого префікса з бітами префіксу у вузлі, де n - довжина префіксу у вузлі. Якщо біти збігаються, то дивимося в шуканому префіксі n + 1 "й біт і залежно від того, дорівнює він 0 або 1 спускаємося до лівого або правого дочірнього елемента.
Наприклад, пошук префікса 011000 буде проводитися наступним чином. Починаємо як завжди з кореня дерева. Корінь у нашому випадку містить префікс довжини 0, тому перевіряємо перший біт шуканого префіксу. Оскільки він дорівнює 0, то спускаємося до лівого дочірнього елемента і потрапляємо на вузол з префіксом 01. Тут ми звіряємо шуканий префікс з префіксом у поточному вузлі, тобто чи збігаються перші 2 біта біля префіксу 011000 з префіксом 01. Оскільки біти збігаються, то рухаємося далі і перевіряємо 3-й біт шуканого префіксу. Третій біт дорівнює 1, тому спускаємося до правого дочірнього елементу і потрапляємо в потрібний нам префікс 011000. Для перебування префікса знадобилося три звернення до дерева замість семи у разі незжатого дерева. Якщо на якомусь етапі виявилося, що перші n біт префікса у вузлі не збігаються з битами шуканого префіксу, то це означає, що шуканого префіксу немає і він додається в дерево.
У Quagga префікс зберігається у вигляді ip-адреси і довжини префіксу. При цьому значення мають тільки перші n-біт, де n-довжина префіксу, а інші рівні 0 і не беруть участі в пошуку потрібного префіксу. Наприклад, префікс 192.168.1.0/24 виглядає як:
Для наочності я відображу його наступним чином:
Тут вгорі я вказую звичний вид префіксу в десятковому вигляді, а внизу - його двійкове уявлення, причому червоним відзначено кількість біт рівне довжині префіксу. У таких позначеннях таблиця маршрутизації, що складається з префіксів 0.0.0.0/0, 10.0.0.0/8, 172.16.0.0/16, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24 виглядатиме так:
Для прикладу, при пошуку префіксу 192.168.1.0/24 послідовно перевіряються його 1-й, 2-й, 23-й і 24-й біти для знаходження його місця розташування в дереві. Кожен з наших префіксів вказує також і на відповідну йому маршрутну інформацію. Префікси виділені жовтим є проміжними і для них маршрутна інформація відсутня.
Обхід префіксного дерева
На закінчення мені хотілося б розповісти яким образів виводяться маршрути при наборі команди show ip route. Для виведення маршрутів необхідно будь-яким чином перебрати всі префікси в дереві. Дана процедура називається обходом дерева і може реалізовуватися різними способами. У Quagga використовується метод обходу під назвою pre-ordered і який найпростіше визначити рекурсивно:
- Спочатку беремо вершину дерева.
- Потім обходимо ліве піддерево.
- Потім обходимо праве піддерево.
Для обходу піддерев використовуються ті ж самі правила. Для побудованої нами вище таблиці маршрутизації обхід префіксів буде виглядати наступним чином: Спочатку беремо вершину дерева, тобто префікс 0.0.0.0/0. Потім обходимо ліве піддерево. Воно у нас складається з єдиного префіксу 10.0.0.0/8. Потім обходимо праве піддерево, яке відобразимо на малюнку:
Для його обходу застосовуємо ті ж правила: спочатку беремо його корінь, тобто префікс 128.0.0.0/1, потім обходимо його ліве піддерево, тобто префікс 172.16.0.0/16, потім праве піддерево, зображене на малюнку:
Далі беремо вершину цього піддерева, тобто префікс 192.168.0.0/22, обходимо його ліве піддерево, отримуючи префікси 192.168.0.0/23, 192.168.0.0/24 і 192.168.1.0/24, і його праве піддерево, що складається з префіксу 192.168.2.0/24.
Таким чином, ми отримаємо префікси в наступному порядку: 0.0.0.0/0, 10.0.0.0/8, 128.0.0.0/1, 172.16.0.0/16, 192.168.0.0/22, 192.168.0.0/23, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24. Префікси 128.0.0.0/1, 192.168.0.0/22 та 192.168.0.0/23 є службовими та не показуються при виведенні таблиці маршрутизації. Префікси, що залишилися, відображаються в порядку: 0.0.0.0/0, 10.0.0.0/8, 172.16.0.0/16, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24.
Ув'язнення
На закінчення наведу список вихідних файлів Quagga, де реалізовані вищеописані структури та алгоритми:
Вихідники Quagga можна завантажити звідси: download.savannah.gnu.org/releases/quagga. Я брав версію 0.99.24.
Структури і функції для роботи з префіксами знаходяться у файлі lib/prefix.c.
Структури та функції для роботи з префіксним деревом знаходяться у файлі lib/table.c
Структури і функції для роботи з маршрутною інформацією знаходяться у файлі zebra/zebra_rib.c
