Таблица маршрутизации в 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, а в качестве Data Plane – ядро Linux. Таблица маршрутизации Quagga при этом находится внутри демона zebra.

    image

    Хранение маршрутной информации


    Каждый отдельный маршрут в таблице маршрутизации можно представить как префикс (обычно обозначается как 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
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 11

      0
      Это опечатка или в квагге действительно смотрится вначале административаная дистанция а потом только длина префикса? Во всем сетевом оборудовании с которым я работал все в точности до наоборот — вначале сравнивается дина префика и выбирается более точный маршрут, если префиксы равны, то в дела вступает административная дистанция.
        0
        Извиняюсь, я невнимательно просмотрел диаграмму. В статье корректно написано.
        0
        «В нашем случае в качестве Control Plane выступает Quagga, а в качестве Control Plane – ядро Linux» — поправьте опечатку пожалуйста
          0
          Исправил, спасибо!
          0
          Интересно, зачем демоны bgpd, ospfd и пр. передают значение метрики демону zebra? По идее, выбор лучшего маршрута в рамках каждого протокола динамической маршрутизации должен осуществляться внутри соответствующего демона. Так как для каждого протокола вопрос выбора лучшего маршрута уникален (различные алгоритмы, метрики, правила борьбы с зацикливаними и пр.). А сравнивать метрики разных протоколов вообще бессмысленно. У того же BGP вместо метрики используется целый набор атрибутов.

          маршрутов для одного префикса немного (не более одного для каждого протокола)

          В случае наличия маршрутов с одинаковой метрикой мы можем иметь балансировку трафика. А значит в таблице маршрутизации может быть несколько маршрутов от одного протокола.
            0
            Лучший маршрут в рамках одного протокола действительно осуществляется внутри соответствующего демона. Но можно административную дистанцию (AD) у разных протоколов маршрутизации настроить так, что у них она будет совпадать. Тогда, чтобы хоть как-то сравнить такие маршруты от разных протоколов но с одинаковой AD используется метрика. Случаи из жизни, когда нужно было настраивать разные протоколы с одинаковой AD я не могу вспомнить, но, возможно, бывают и такие извращения.

            > В случае наличия маршрутов с одинаковой метрикой мы можем иметь балансировку трафика. А значит в таблице маршрутизации может быть несколько маршрутов от одного протокола.

            Возможно, Вы действительно правы. По идее, это зависит от конкретных демонов (ospfd, bgpd), будут ли они слать в zebra несколько маршрутов с одинаковой метрикой но с разными next-hop, с ними я еще не разбирался.
            Другой вопрос, будет ли zebra все эти маршруты посылать в linux для балансировки трафика. Мне казалось, что она посылает только один из них. В общем, нужно будет с ECMP разобраться повнимательнее, постараюсь посмотреть как оно реализовано.

              0
              Вот, к примеру, OSPF. ECMP вполне себе работает:
              $ vtysh -c «show ip route 172.16.163.12/30»
              Routing entry for 172.16.163.12/30
              Known via «ospf», distance 110, metric 20, best
              Last update 04:52:00 ago
              * 172.16.172.77, via eth2.700
              * 172.16.172.90, via eth2.700
              $ ip route list 172.16.163.12/30
              172.16.163.12/30 proto zebra metric 20
              nexthop via 172.16.172.77 dev eth2.700 weight 1
              nexthop via 172.16.172.90 dev eth2.700 weight 1
                0
                Вроде бы разобрался.

                В том, что я называл маршрутной информацией (т.е. структуре, где хранится тип протокола, метрика, AD и т.д., в zebra данная структура называется rib) на самом деле может храниться не один next-hop, а несколько разных next-hop'ов (в виде связного списка). При этом если данная маршрутная информация выбирается лучшей, то в ядро linux (FIB) попадают все ее next-hop'ы (если они валидны). Получается, что лучшая маршрутная информация (rib) выбирается одна, но в ядро linux действительно может попасть несколько маршрутов, поскольку у rib может быть несколько next-hop'ов.

                При выводе команды show ip route хорошо видно rib с несколькими next-hop. Например, в следующем примере для префикса 10.0.0.1/32 имеются два rib — один статический и другой ospf. При этом у ospf имеется два next-hop — 10.158.47.30 и 172.16.1.30.



                При этом, как минимум, для статических маршрутов с разной AD действительно может быть несколько разных rib для одного префикса. Поэтому убрал из текста "(не более одного для каждого протокола)"
                0
                На оборудовании Cisco, если AD совпадает для разных протоколов, выберется только тот, который является более приоритетным для AD по умолчанию. Предположу, что в Quagga реализация будет аналогичной, так как сравнивать разные типы метрик, не самая удачная идея.
                Возможно, передавать значение метрики демону zebra нужно в информационных целях. Чтобы администратор видел всю картину.
                  0
                  Нет, в Quagga при одинаковой AD сравниваются метрики. В этом действительно отличие от Cisco.

              0
              > В нашем случае в качестве Control Plane выступает Quagga, а в качестве Control Plane – ядро Linux.
              Опечатка

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое