отмена
Отображаются результаты для 
Вместо этого искать 
Вы имели в виду: 
cancel
Объявления
Community Live

648
Просмотры
25
Полезный материал
8
Ответы
Chingiz
Beginner

Как роутер ищет нужный маршрут в таблице маршрутизации?

     Здравствуйте. Не смог найти в интернете информацию, как именно роутер ищет нужный ему маршрут в таблице маршрутизации. Везде говорится, что он сверяет адрес назначения из полученного пакета с записями в таблице маршрутизации, но не уточняется как именно это делает. То есть логика поиска и сверения такая же, как и у АCL - тупо сверху вниз, сверяя каждую строчку, или же есть какие-то свои методы поиска? Если как с АСL, то в случае с сотнями или тысячами непросуммированных маршрутов это займет время и загрузит процессор. В общем, главный вопрос - как роутер ищет нужный маршрут в таблице маршрутизации?

1 УТВЕРЖДЕННОЕ РЕШЕНИЕ

Утвержденные решения

С точки зрения логики работы, считайте что маршрутизатор/L3 коммутатор просматривает все записи от начала до конца. То есть он не останавливается при нахождении подходящего маршрута, а просматривает все. Иначе бы longest prefix match не работал. Плюс не забывайте про рекурсию.

По факту эта операция конечно не последовательная. Если устройство имеет аппаратную маршрутизацию (внутри TCAM), то оно делает этот поиск за "одну" итерацию (естественно условно, назовём это за очень малое количество действий).

Если говорить про софт-роутеры, то там опять же реализован алгоритм (как писал выше Михаил), при котором поиск маршрута происходит не последовательно по всем записям, а за минимальное количество итераций. Иначе, как вы правильно заметили, поиск бы занимал непредсказуемое количество времени. Но по факту, в современной реализации, оно всегда +/- одинаковое не зависимо от размера таблицы маршрутизации.

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

________________________________________________________
Если ответ понравился, ставь звёздочку. Если ответ помог решить твою проблему, утверди его в качестве решения

Просмотреть решение в исходном сообщении

8 ОТВЕТ 8
vamikhai
Cisco Employee

Добрый день.

Аппаратные устройства выполняют аппаратный поиск с помощью т.н. TCAM.

Программные устройства (типа CSR1KV) используют высокоэффективные алгоритмы (основаны на деревьях), которые / конечно/ не сопоставимы по скорости с аппаратным поиском, однако приближаются к ним довольно близко.

 

PS: ACL работает по тому же принципу.

В моем случае устройсвто - физический коммутатор уровня 3. ТСАМ помогает выбрать нужный маршрут из нескольких маршрутов с разной маской, меня же интересует сама логика подбора маршрута. То есть допустим таблица имеет вид:

  1.0.0.0 ...................

  2.0.0.0....................

  3.0.0.0....................

  4.0.0.0....................

    * * * * * * * * * 

    * * * * * * * * * 

100.0.0.0,

  маршруты получены из разных источников, хотя это не суть важно. На маршрутизатор поступил пакет с адресом назначения 99.1.1.1. Как он будет подбирать нужный маршрут? Будет сверять адресс 99.1.1.1 с каждой сетью на случай совпадения как действует в случае с ACL, либо тут есть какая-то другая логика, избавляющая маршрутизатор от просмотра лишних 98 строк в таблице?

Leonid Voronkin
VIP Collaborator

https://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/8651-21.html

________________________________________________________
Если ответ понравился, ставь звёздочку. Если ответ помог решить твою проблему, утверди его в качестве решения

Эту статью я читал, там подробно написано о том, как роутер выбирает маршрут, который он ДОБАВЛЯЕТ в таблицу, а ак же пару слов о тому, как выбирает на какой именно маршрут послать с учетом длины преффикса. Мне же нужно понять как роутер СРАВНИВАЕТ адресс в пакете с маршрутами в уже готовой таблице, где лучший маршрут есть и прописан. Начинает ли с первой строчки и идет сравнивая по ней дальше, что в случае большой таблицы занимает время, либо же он иеемт какие-то методы обхода данной проблемы

С точки зрения логики работы, считайте что маршрутизатор/L3 коммутатор просматривает все записи от начала до конца. То есть он не останавливается при нахождении подходящего маршрута, а просматривает все. Иначе бы longest prefix match не работал. Плюс не забывайте про рекурсию.

По факту эта операция конечно не последовательная. Если устройство имеет аппаратную маршрутизацию (внутри TCAM), то оно делает этот поиск за "одну" итерацию (естественно условно, назовём это за очень малое количество действий).

Если говорить про софт-роутеры, то там опять же реализован алгоритм (как писал выше Михаил), при котором поиск маршрута происходит не последовательно по всем записям, а за минимальное количество итераций. Иначе, как вы правильно заметили, поиск бы занимал непредсказуемое количество времени. Но по факту, в современной реализации, оно всегда +/- одинаковое не зависимо от размера таблицы маршрутизации.

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

________________________________________________________
Если ответ понравился, ставь звёздочку. Если ответ помог решить твою проблему, утверди его в качестве решения

Просмотреть решение в исходном сообщении

Выходит, что большая таблица маршрутизации плоха только с точки зрения занимаемой ею памяти, но не с точки зрения скорости маршрутизации, так как маршрутизация происходит за счет механизма CEF? А в чем смысл суммаризации маршрутов, если роутер итак просматривает всю таблицу?


Выходит, что большая таблица маршрутизации плоха только с точки зрения занимаемой ею памяти, но не с точки зрения скорости маршрутизации, так как маршрутизация происходит за счет механизма CEF?

В целом да. Но ещё есть момент удобства эксплуатации.


А в чем смысл суммаризации маршрутов, если роутер итак просматривает всю таблицу?

Маршрутизация процесс комплексный. Выбор маршрута по которому отправить пакет это последний этап. Этот маршрут надо откуда-то взять. Обычно это какой нибудь протокол динамической маршрутизации, у которого есть свой алгоритм работы. Скорость работы этого протокола будет зависеть в том числе и от количества маршрутов. А чем быстрее протокол обработает маршруты, тем быстрее он наполнит таблицу маршрутизации. Так что сумаризация очень полезная штука. Ну и опять же удобство эксплуатации никто не отменял.

________________________________________________________
Если ответ понравился, ставь звёздочку. Если ответ помог решить твою проблему, утверди его в качестве решения

Понял, почитаю на тему Форвадинга, спасибо большое!

Создать
Выразить признание своим коллегам
Опросы
Какой контент Вы хотели бы чаще видеть в Сообществе?
Content for Community-Ad

Сообщество Cisco

Помощь по сообществу