路由器如何組織其路由表？

Question

路由器如何組織它的路由表以便快速處理包裹包？這更是一個編程的問題，我在尋找：

• 算法和數據結構來存儲路由表項快速查找（哈希線索？）算法的
• 優化（例如使用高速緩存）
• 獎金：這些算法的歷史演變（基於一個事實，即內存得了便宜等）

注：實際創建路由表（通過路由協議，如RIP，OSPF或手動條目）是無關緊要的。

Answer 1

您可以擁有一個trie並在散列上緩存查找。例如，參見Linux的ip_route_input()（它試圖在哈希上查找條目）和ip_route_input_slow()（它試圖在轉發信息庫中找到條目，一個trie）。