路由器如何组织其路由表？
路由器如何组织其路由表以便快速为传入数据包提供服务？这更多的是一个编程问题，我正在寻找：
- 存储路由表条目以进行快速查找（哈希？特里？）
- 的算法和数据结构优化算法（例如使用缓存）
- 奖励：这些算法的历史演变（基于内存变得更便宜等事实）
注意：路由表的实际创建（通过路由协议，如 RIP、OSPF 或手动条目）是无关紧要的。
How does a router organize its routing table in order to service the incomming packets fast? This is more of a programming question, and I am looking for:
- algorithm and data structure to store the routing table entries for fast look up (hash? trie?)
- optimization of the algorithm (e.g. using caches )
- bonus: historical evolution of these algorithms (based on the fact that memory got cheaper etc.)
Note: the actual creation of the routing table (via routing protocols such as RIP, OSPF or manual entries) is irrelevant.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以拥有一个 trie 并将查找缓存到哈希上。例如，请参阅 Linux 的
ip_route_input()（它尝试在哈希上查找条目）和ip_route_input_slow()（它尝试在转发信息库中查找条目，a特里）。You can have a trie and cache the lookups on a hash. See for example Linux's
ip_route_input()(which tries to find the entry on a hash) andip_route_input_slow()(which tries to find the entry in the Forwarding Information Base, a trie).