Таблица маршрутизации в 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 и который проще всего определить рекурсивно:

• Сначала берем вершину дерева.
• Затем обходим левое поддерево.
• Затем обходим правое поддерево.

Для его обхода применяем те же правила: сначала берем его корень, т.е. префикс 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 где реализованы вышеописанные структуры и алгоритмы: