Как маршрутизатор организует свою таблицу маршрутизации?

Question

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

• алгоритм и структуру данных для хранения записей таблицы маршрутизации для быстрого поиска (hash? Trie?)
• оптимизацияалгоритма (например, с использованием кешей) * бонус 1006 *
• : историческая эволюция этих алгоритмов (основанная на том факте, что память стала дешевле и т. д.)таблица (через протоколы маршрутизации, такие как RIP, OSPF или ручные записи) не имеет значения.

Answer 1

Вы можете использовать trie и кэшировать результаты поиска в хэше.См., Например, Linux ip_route_input() (который пытается найти запись в хэше) и ip_route_input_slow() (который пытается найти запись в базе пересылочной информации, три).