#algorithm #optimization #data-structures
#алгоритм #оптимизация #структуры данных
Вопрос:
Как маршрутизатор организует свою таблицу маршрутизации, чтобы быстро обслуживать входящие пакеты? Это скорее вопрос программирования, и я ищу:
- алгоритм и структура данных для хранения записей таблицы маршрутизации для быстрого поиска (хэш? пример?)
- оптимизация алгоритма (например, с использованием кэшей)
- бонус: историческая эволюция этих алгоритмов (основанная на том факте, что память стала дешевле и т.д.)
Примечание: фактическое создание таблицы маршрутизации (с помощью протоколов маршрутизации, таких как RIP, OSPF или ручные записи) не имеет значения.
Ответ №1:
У вас может быть trie и кэшировать поисковые запросы в хэше. Посмотрите, например, на Linux ip_route_input() (который пытается найти запись в хэше) и ip_route_input_slow() (который пытается найти запись в информационной базе пересылки, trie).