На что указывает префикс 32 содержащийся в таблице маршрутизации

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

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

Источник

Таблицы маршрутизации

Манипуляции с таблицей маршрутизации позволяют тонко настраивать работу ваших сетей. Чаще всего это не нужно, но иногда требуется сделать что-то необычное, особенно, когда на комрьютере несколько адаптеров, и тогда приходится браться за таблицы маршрутизации.

Просмотр таблицы маршрутизации

Приведу вывод команды route print на моем стаионарном компьютере:

Итак, давайте разберем описанные маршруты. На самом деле, самой важной является в данном случае первая строчка. Она говорит, что для любого адреса (адрес 0.0.0.0 с маской 0.0.0.0 задает полный диапазон) есть маршрут с использованием моей сетевой карты, и направить можно эти пакеты по адресу 192.168.1.1. Последний адрес является моим роутером, что все и объясняет. Любой адрес, который компьютер не сможет найти где-то рядом, он направит на роутер и предоставит тому с ним разбираться.

Команды таблицы маршрутизации

Я ничего не сказал про предпоследнюю строчку. А она самая интересная, ведь я ее добавил руками. В чем ее смысл? Адреса диапазона 10.1-32.*.* я отправляю на шлюз 10.22.220.1. Пакеты на эти адреса не пойдут в интернет, а останутся в локалке провайдера. Да, пакеты на диапазон 10.22.220. и так идут туда, но этого мало. Так я не получаю полноценного доступа к локальным ресурсам.

Статья и так уже получилась намного длинней обычных статей этого блога, так что я заканчиваю. Пишите свои вопросы здесь, а если же вы хотите разобрать какие-то спицифические случаи настройки, лучше обращайтесь на нашем форуме.

Источник

Выбор маршрута в маршрутизаторах Cisco

Параметры загрузки

Об этом переводе

Этот документ был переведен Cisco с помощью машинного перевода, при ограниченном участии переводчика, чтобы сделать материалы и ресурсы поддержки доступными пользователям на их родном языке. Обратите внимание: даже лучший машинный перевод не может быть настолько точным и правильным, как перевод, выполненный профессиональным переводчиком. Компания Cisco Systems, Inc. не несет ответственности за точность этих переводов и рекомендует обращаться к английской версии документа (ссылка предоставлена) для уточнения.

Содержание

Введение

Один из самых интересных аспектов маршрутизаторов Cisco, особенно для пользователей, малознакомых с маршрутизацией, — это метод, который маршрутизатор использует для выбора наилучшего из доступных маршрутов, созданных протоколами маршрутизации, при помощи ручной настройки и другими способами. Несмотря на то что процесс выбора маршрута проще, чем можно предположить, полное понимание этого процесса требует некоторых знаний принципа работы маршрутизаторов Cisco.

Предварительные условия

Требования

Для данного документа отсутствуют предварительные условия.

Используемые компоненты

Настоящий документ не имеет жесткой привязки к каким-либо конкретным версиям программного обеспечения и оборудования.

Условные обозначения

Связанные процессы

В создание и поддержку таблицы маршрутизации в маршрутизаторе Cisco вовлечены три процесса:

Различные процессы маршрутизации, которые фактически запускают сетевой протокол или протокол маршрутизации, такой как улучшенный протокол маршрутизации внутреннего шлюза (EIGRP), связь между промежуточными системами (IS-IS), первоочередное открытие кратчайших маршрутов (OSPF).

Сама таблица маршрутизации, которая получает сведения от процессов маршрутизации и отвечает на запросы данных от процесса переадресации.

Процесс переадресации, который запрашивает информацию из таблицы маршрутизации, чтобы принять решение о переадресации пакета.

Чтобы понять, как происходит построение таблицы маршрутизации, рассмотрим взаимодействие между протоколами маршрутизации и таблицей маршрутизации.

Построение таблицы маршрутизации

Основные вопроси при построении маршрутной таблицы:

Административное расстояние – Это мера надежности источника маршрута. Если маршрутизатор узнает о получателе из нескольких протоколов маршрутизации, то сравниваются административные расстояния и преимущество получают маршруты с меньшим административным расстоянием. Другими словами, это степень доверия источнику маршрута.

Метрики – это мера, используемая протоколом маршрутизации для вычисления лучшего пути к данному месту назначения, если известно множество путей к нему. Каждый протокол маршрутизации использует свою метрику.

Поскольку каждый процесс маршрутизации получает обновления и иную информацию, он выбирает наилучший путь к указанному пункту назначения и предпринимает попытку внедрить данный путь в таблицу маршрутизации. Например, если протокол EIGRP определяет наилучший путь к адресу 10.1.1.0/24, выполняется попытка установки данного пути в таблицу маршрутизации.

Маршрутизатор решает, устанавливать ли маршруты, представленные процессом маршрутизации, основанном на административном расстоянии маршрута. Если данный маршрут имеет наименьшую административную длину до цели (по сравнению с другими маршрутами таблицы), он будет прописан в таблице маршрутизации. Если этот маршрут не является маршрутом с лучшим административным расстоянием, он отклоняется.

Для лучшего понимания давайте обратимся к примеру. Предположим, что в маршрутизаторе работает 4 процесса маршрутизации —: EIGRP, OSPF, RIP и IGRP. Все 4 процесса получили данные о различных маршрутах к сети 192.168.24.0/24, и каждый выбрал наилучший путь к этой сети, используя внутренние метрики и процессы.

Каждый из четырех процессов пытается установить свой маршрут к сети 192.168.24.0/24 в таблицу маршрутизации. Каждый из процессов маршрутизации назначил административное расстояние, которое используется для определения маршрута, который следует установить.

Так как внутренний маршрут EIGRP имеет наилучшее административное расстояние (чем меньше административное расстояние, тем выше приоритет), он устанавливается в таблицу маршрутизации.

Резервные маршруты

Что другие протоколы, RIP, IGRP и OSPF, делают с неустановленными маршрутами? Что делать, если оптимальный маршрут, полученный от EIGRP, недоступен? ПО Cisco IOS® использует два похода к решению этой проблемы: Сначала каждый процесс маршрутизации должен периодически пытаться установить свои лучшие маршруты. Если наиболее предпочтительный маршрут недоступен, то на следующей попытке будет выбран следующий по приоритету маршрут (в соответствие с административным расстоянием). Другим решением для протокола маршрутизации, которому не удалось установить маршрут в таблице, является использование маршрута и передача процессу таблицы маршрутизации команды послать отчет, если лучший маршрут даст сбой.

Для протоколов, не имеющих своей информации таблиц маршрутизации, например IGRP, используется первый метод. Каждый раз, когда протокол IGRP получает обновление маршрута, он пытается установить обновленные данные в таблицу маршрутизации. Если в таблице маршрутизации на это направление уже назначен маршрут, попытка установки закончится неудачей.

Для протоколов, не имеющих БД маршрутной информации, например EIGRP, IS-IS, OSPF, BGP и RIP, резервный маршрут регистрируется при сбое первоначальной попытки установить маршрут. Если маршрут, установленный в таблице маршрутизации, отказывает по тем или иным причинам, процесс обслуживания таблицы маршрутизации вызывает процессы всех протоколов маршрутизации, которые зарегистрировали резервный маршрут, и просит установить этот маршрут в таблицу. Если резервный маршрут зарегистрировали несколько протоколов, предпочтительный маршрут выбирается на основе административного расстояния.

Настройка административного расстояния

Административное расстояние по умолчанию не всегда подходит для вашей сети; можно внести изменение, чтобы маршруты RIP были предпочтительны, например, по сравнению с маршрутами IGRP. Перед тем как объяснить, как регулировать административные расстояния, необходимо посмотреть на последствия изменения административного расстояния.

Опасно изменять административное расстояние в протоколах маршрутизации! Изменение расстояний по умолчанию может привести к образованию петель маршрутизации. Рекомендуется изменять административное расстояние с осторожностью и с полным представлением о том, что требуется получить, и всех последствиях своих действий.

Для полных протоколов изменение расстояния относительно просто. Для этого необходимо ввести команду distance в режиме субконфигурации процесса маршрутизации. Также можно изменить расстояние маршрутов, полученных только из одного источника или расстояние только определенных маршрутов. Для получения дополнительной информации см. Изменение административного расстояния для выбора маршрута в примере настройки маршрутизаторов Cisco IOS.

Чтобы изменить расстояние для статических маршрутов, введите нужное расстояние после следующей команды ip route:

ip-маршрут подсеть сети маска следующий транзитный участок расстояние

Невозможно одновременно изменить административное расстояние для всех статических маршрутов.

Как метрика определяет процесс выбора маршрута

Маршрутизаторы выбираются и включаются в маршрутизационную таблицу на основании административного расстояния протокола маршрутизации. Маршруты с наименьшим административным расстоянием, полученные от протокола маршрутизации, устанавливаются в таблицу маршрутизации. Если с одного протокола маршрутизации существует несколько путей к одному и тому же получателю, то эти пути имеют одно административное расстояние, а оптимальный путь выбирается на основе метрики. Метрики представляют собой значения, связанные с определенными маршрутами, ранжирующие их в интервале от наиболее предпочитаемых до наименее предпочитаемых. Параметры, используемые для расчета метрик, зависят от протокола маршрутизации. Путь с самой низкой метрикой выбирается в качестве оптимального пути и устанавливается в таблице маршрутизации. Если существует несколько путей с равной метрикой до одного назначения, распределение нагрузки выполняется по этим путям эквивалентной стоимости. Дополнительные сведения о распределении нагрузки см. в разделе «Как работает средство распределения нагрузки»?

Длина префикса

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

EIGRP (внутренний): 192.168.32.0/26

Который из этих маршрутов будет установлен в таблице маршрутизации? Поскольку внутренний маршрут EIGRP имеет наилучшее административное расстояние, легко предположить, что он будет установлен первым. Однако, маршруты имеют разные длины префиксов (маски подсети) и, следовательно, считаются маршрутами к разным местам назначения. В этом случае в таблицу маршрутизации будут добавлены все маршруты.

Давайте посмотрим, как переадресующий инструмент использует информацию таблицы маршрутизации для принятия решений о пересылке.

Принятие решений о переадресации

Давайте взглянем на три маршрута, которые мы только что установили в таблице маршрутизации, и посмотрим, как они выглядят на маршрутизаторе.

Если пакет прибывает на интерфейс маршрутизатора с адресом назначения 192.168.32.1, какой маршрут выберет маршрутизатор? Это зависит от длины префикса или количества бит, установленного в маске подсети. При пересылке пакета более длинные префиксы всегда предпочтительнее коротких.

В этом примере, пакет, отправленный по адресу 192.168.32.1 направляется в сеть 10.1.1.1, так как адрес 192.168.32.1 находится в сети 192.168.32.0/26 (192.168.32.0–192.168.32.63). Адресу соответствуют еще два доступных маршрута, но у 192.168.32.0/26 наиболее длинный префикс в таблице маршрутизации (26 бит против 24 и 19).

Точно так же, если пакет, направленный на адрес 192.168.32.100, прибывает на один из интерфейсов маршрутизатора, он перенаправляется на 10.1.1.2, поскольку 192.168.32.100 не попадает в диапазон адресов 192.168.32.0/26 (от 192.168.32.0 до 192.168.32.63), но попадает в диапазон адресов 192.168.32.0/24 назначения (от 192.168.32.0 до 192.168.32.255). Опять, он также попадает в область, перекрытую 192.168.32.0/19, но 192.168.32.0/24 имеет более длинный префикс.

Ip classless

Для тех адресов, для которых команда ip classless configuration попадает в данный диапазон, возможно возникновение сбоев в процессе маршрутизации и пересылки. В реальности команда «IP classless» влияет только на работу процессов переадресации IOS, но не влияет на построение таблицы маршрутизации. Если функция «IP classless» не настроена (с помощью команды no ip classless), маршрутизатор не будет переадресовать пакеты в подсети. Для примера снова поместим три маршрута в таблицу маршрутизации и проведем пакеты через маршрутизатор.

Примечание: Если суперсеть или маршрут по умолчанию получены через IS-IS или OSPF, то команда no ip classless configuration игнорируется. В этом случае режим коммутация пакетов работает так, как если бы команда ip classless была настроена.

Помня о том, что сеть 172.30.32.0/24 включает адреса с 172.30.32.0 по 172.30.32.255, а сеть 172.30.32.0/20 включает адреса с 172.30.32.0 по 172.30.47.255, мы можем выполнить коммутацию трех пакетов с использованием этой таблицы маршрутизации и проанализировать результаты.

Пакет, направленный по адресу 172.30.33.1, переадресуются на 10.1.1.2, так как этот маршрут имеет наибольший префикс.

Пакет, предназначенный для адреса 172.30.33.1, пересылается на 10.1.1.2, из-за совпадения самого длинного префикса.

Пакет, направленный по адресу 192.168.10.1 переадресуются на 10.1.1.3. Так как сеть отсутствует в таблице маршрутизации, пакет переадресуется на маршрут по умолчанию.

Пакет, отправленный по адресу 172.30.254.1, отбрасывается.

Удивительно, что из этих четырех пакетов был отброшен последний. Он отброшен потому, что его место назначения 172.30.254.1 находится внутри известной крупной сети 172.30.0.0/16, но маршрутизатор не знает об этой отдельной подсети внутри этой крупной сети.

На этом основана маршрутизация типа classful: Если одна часть основной сети известна, но подсеть в этой основной сети, для которой предназначен пакет, не известна, пакет отбрасывается.

Самым сложным для понимания аспектом этого правила является то, что маршрутизатор использует только маршрут по умолчанию, если крупная сеть назначения вообще не существует в таблице маршрутизации.

Это может вызвать проблемы в сети, когда удаленный участок с одной связью к остальной части сети не выполняет никаких протоколов маршрутизации, как проиллюстрировано.

Маршрутизатор удаленного сайта настраивается следующим образом:

В такой конфигурации узлы на удаленном узле могут достичь назначения через Интернет (через облако 10.x.x.x), но не назначений в облаке 10.x.x.x, которое является корпоративной сетью. Поскольку удаленный маршрутизатор обладает информацией о части сети 10.0.0.0/8, двух напрямую подключенных подсетях и ничего не знает о другой подсети диапазона 10.x.x.x, то он предполагает, что таких подсетей не существует, и сбрасывает предназначенные для них пакеты. Однако трафик, направленный в Интернет, не имеет получателя в диапазоне адресов 10.x.x.x и поэтому правильно направляется по стандартному маршруту.

Настройка бесклассового IP на удаленном маршрутизаторе позволяет решить эту проблему, так как она позволяет удаленному маршрутизатору игнорировать границы класса сетей в таблице маршрутизации и выполнять маршрутизацию просто по совпадению с наибольшей длиной префикса.

Сводка

В общих словах, переадресация состоит из трех наборов процессов: протоколы маршрутизации, таблица маршрутизации и процесс переадресации, который принимает решения о переадресации и коммутирует пакеты. Ниже иллюстрируются эти три набора процессов, а также их взаимосвязь.

Совпадение с наибольшей длиной префикса всегда выигрывает у маршрутов, установленных в таблице маршрутизации, в то время как протокол маршрутизации с самым коротким административным расстоянием всегда выигрывает при установке маршрутов в таблицу маршрутизации.

Источник