Tablas de reenvío pequeñas para búsquedas de enrutamiento rápidas

Durante algún tiempo, la comunidad de redes ha asumido que es imposible realizar búsquedas de enrutamiento IP en software lo suficientemente rápido como para soportar velocidades de gigabit. Las búsquedas de enrutamiento IP deben encontrar la entrada de enrutamiento con el prefijo más largo coincidente, una tarea que se ha pensado que requiere soporte de hardware a frecuencias de búsqueda de millones por segundo. Presentamos una estructura de datos de tabla de reenvío diseñada para búsquedas de enrutamiento rápidas. Las tablas de reenvío son lo suficientemente pequeñas como para caber en la caché de un procesador convencional de propósito general. Con la tabla en caché, un Pentium Pro de 200 MHz o un Alpha 21164 de 333 MHz pueden realizar unos pocos millones de búsquedas por segundo. Esto significa que es factible realizar una búsqueda de enrutamiento completa para cada paquete IP a velocidades de gigabit sin hardware especial. Las tablas de reenvío son muy pequeñas; una gran tabla de enrutamiento con 40,000 entradas de enrutamiento se puede compactar a una tabla de reenvío de 150-160 Kbytes. Una búsqueda típicamente requiere menos de 100 instrucciones en un Alpha, utilizando ocho referencias de memoria que acceden a un total de 14 bytes.