По роду своей деятельности я занимаюсь проектированием сетей и настройкой сетевого оборудования. В какой-то момент времени мне захотелось узнать как-же устроены сетевые устройства, которые всегда представляли для меня черные ящики, магически реализующие сетевые протоколы. Поскольку устройства от вендоров типа 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