路由器如何组织路由表？

Question

路由器如何组织其路由表以快速服务于崩溃的数据包？这更像是一个编程问题,我正在寻找:

• 算法和数据结构存储路由表条目以便快速查找(hash？trie？)
• 优化算法(例如使用缓存)
• 奖励:这些算法的历史演变(基于内存变得更便宜的事实等)

注意:实际创建路由表(通过RIP,OSPF或手动条目等路由协议)是无关紧要的.

Answer 1

您可以拥有一个 trie 并将查找缓存到哈希上。例如，参见Linux ip_route_input()（它尝试在散列上查找条目）和ip_route_input_slow()（它尝试在转发信息库（trie）中查找条目）。