¿Cómo organiza un enrutador su tabla de enrutamiento?

Question

¿Cómo organiza un enrutador su tabla de enrutamiento para poder procesar rápidamente los paquetes entrantes? Esto es más de una cuestión de programación, y yo estoy buscando:

• algoritmo y estructura de datos para almacenar las entradas de la tabla de enrutamiento para buscar rápidamente hacia arriba (hash de trie??)
• optimización del algoritmo (por ejemplo, utilizando cachés)
• bonificación: evolución histórica de estos algoritmos (basado en el hecho de que la memoria tiene más barato etc.)

Nota: la creación real de la tabla de enrutamiento (a través de los protocolos de enrutamiento como RIP, OSPF o manual entradas) es irrelevante.

Answer 1

Puede tener un trie y almacenar en caché las búsquedas en un hash. Ver por ejemplo Linux ip_route_input() (que trata de encontrar la entrada en un hash) y ip_route_input_slow() (que intenta encontrar la entrada en la Base de información de reenvío, un trie).