Выбор лучшего маршрута

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

Что я имею в виду? Попробуйте с ходу ответить на несколько вопросов. Допустим, у вас есть четыре маршрута, которые приходят на одну железку (Cisco, скажем).

• EIGRP: 10.0.0.0/26
• RIP: 10.0.0.0/24
• OSPF: 10.0.0.0/19
• Static: 10.0.0.0/24

Какую картину вы увидите в таблице маршрутизации? Сколько маршрутов и какие маршруты будут добавлены? Куда уйдет трафик на 10.0.0.1? 10.0.0.100?

Я вот ответил, но призадумался… Конечно, это не rocket science, но я решил разобрать эту тему на коротком примере роутера Cisco. Углубляться в эту тему можно до бесконечности глубоко (CEF, специфичные реализации платформ, вендоры, ASICи, PICи и понеслась…), пока вы не достигните того самого уровня rocket science. Я же сейчас хочу сделать некое первое приближение. 

В общем, что мы обычно имеем для выбора лучшего пути:
 

Protocol metric - механизм, с помощью которого выбирается лучший маршрут внутри одного отдельно взятого протокола маршрутизации. Это может быть простой hop count, навороченная метрика EIGRP или, скажем, логика которой следует BGP со всеми его атрибутами. 

Administrative distance (AD) - механизм, который позволяет определить лучший маршрут, если одинаковый префикс доступен через разные источники. Значения для каждого источника разнятся от вендора к вендору. 

Longest prefix match (LPM) - механизм, который помогает определить куда отправить трафик, если в таблице маршрутизации есть несколько подходящих маршрутов. В таком случае, выберется самый специфичный пусть с самым длинным префиксом (самой длинной маской).  

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

1. Внутри каждого процесса, который соответсвует тому или иному источнику получения маршрутной информации (OSPF, BGP, Static и все такое прочее), происходит выбор наилучших кандидатов для установки в таблицу маршрутизации на основе метрики. Если говорить об OSPF, например, то происходит анализ LSDB. Часто это один путь для каждого префикса, но не редки случаи, когда таких кандидатов может быть несколько. Скажем, префикс 10.10.10.0/24 в OSPFе равноудален от нашего маршрутизатора и достижим, через два роутера. В таком случае, процесс OSPF предложить установить в таблицу маршрутизации два маршрута.
2. Каждый такой процесс, передает свои данные в некий аналитический движок (Routing Table Manager в Cisco IOS). Результатом работы этого движка является заполненная таблица маршрутизации (Routing Information Base - RIB). На этом этапе, для решения конфликтов применяется Administrative Distance (AD). Допустим, 10.10.10.0/24 пришел из процесса OSPF и прописан статически. Обычно OSPF имеет более высокое значение AD (110 в Cisco) по сравнению со статикой (1). В этом примере "победит" статика. Важно, что в соперничестве участвуют только одинаковые префиксы. 
3. После того, как RIB сформирована, начинает формироваться некая сущность (обычно), которая ускоряет процесс прохождение трафика. Часто эту сущность называют Forwarding Information Base (FIB). Это выжимка из RIB, которая в том числе содержит и дополнительную информацию, которая призвана ускорить процесс принятия решения. Я говорю про, например, данные о MAC адресах и прочем таком. По сути, мы говорим про Adjacency table, которая формируется средствами ARP таблицы (опять же, не исключительно). 

Важно понимать, что это очень поверхностный алгоритм работы устройства. Оригинальный алгоритм в разы сложней и может довольно сильно отличаться от устройства к устройству, даже в пределах одного производителя. Как всегда, на linkmeup есть отличная статья на данную тему.  

Вернемся к примеру. Мы имеем

• EIGRP: 10.0.0.0/26
• RIP: 10.0.0.0/24 
• OSPF: 10.0.0.0/19 
• Static: 10.0.0.0/24 

Какую картину вы увидите в таблице маршрутизации? Сколько маршрутов и какие маршруты будут добавлены?

Итак, прям по пунктам.

1. Согласно метрике или другим показателям эти маршруты выбраны лучшими среди своих. 
2. Формируется RIB, в который попадают три пути - EIGRP, OSPF, Static. Маршрут RIP отсеялся, потому что его AD выше по сравнению с аналогичной у статического маршрута. Остальные маршруты не конкурировали, потому что имеют разную длину префикса. 
3. Формируется FIB, в который попадает вся необходимая информация для передачи пакета. 

Итого, в таблице маршрутизации мы должны увидеть три маршрута. 

• EIGRP: 10.0.0.0/26 
• OSPF: 10.0.0.0/19 
• Static: 10.0.0.0/24  

Так и есть. Ниже видно, как я добавил статический маршрут в конфигурации. В то же время, вы можете видеть как точно такой же префикс приходит к роутеру через RIP. Однако в таблице маршрутизации маршрута RIP нет, так как он имеет больший AD.

Куда уйдет трафик на 10.0.0.1? 10.0.0.100?

Здесь будет использоваться правило самого длинного префикса (LPM). Трафик до 10.0.0.1 уйдет через EIGRP. Потому что 26 > 24 > 19. Трафик до 10.0.0.100 уйдет через Static, все по той же причине 24 > 19. EIGRP в процессе не участвует, так как 10.0.0.100 в 10.0.0.0/26 (10.0.0.1 - 10.0.0.62) не входит.  

Проверяем просто спросив у CEFа. Как видно, 10.0.0.1 будет доступен через 10.4.4.4 (EIGRP), а вот трафик до 10.0.0.100 уйдет по статическому маршруту.

Как я и говорил, все довольно просто.