Таблиця маршрутизації в Quagga

За своєю діяльності я займаюся проектуванням мереж та налаштуванням мережевого обладнання. У якийсь момент часу мені захотілося дізнатися як влаштовані мережеві пристрої, які завжди представляли для мене чорні ящики, магічно реалізують мережеві протоколи. Оскільки пристрої від вендорів типу 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, а як Control Plane - ядро Linux. Таблиця маршрутизації Quagga у своїй перебуває усередині демона zebra.

Зберігання маршрутної інформації

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

Після вибору найкращого маршруту інформація про нього передається в ядро Linux.

Зберігання префіксів

Надалі префікси буде зручніше представляти в двійковому вигляді, вказуючи при цьому тільки перші біти, у кількості, що дорівнює довжині префікса. Інші біти префікса дорівнюють 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 біт префікса у вузлі не збігаються з бітами префікса, що шукається, то це означає, що шуканого префікса немає і він додається в дерево.

Для наочності я відобразю йогонаступним чином:

Тут угорі я вказую звичний вигляд префікса в десятковому вигляді, а внизу – його двійкове уявлення, причому червоним відзначено кількість біт дорівнює довжині префікса. У таких позначеннях таблиця маршрутизації, що складається з префіксів 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.

Наприклад, при пошуку префікса 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, та його праве поддерево, що складається.2. Отже, ми отримаємо префікси в наступному порядку: 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.123.8. .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 де реалізовані вищеописані структури та алгоритми: