Investigadores de la
Universidad de Luleå en Suecia han desarrollado un algoritmo para los
routers que garantiza un tiempo constante de búsqueda –una de las
tareas que más tiempo consume– utilizando un pequeño dispositivo
de datos o tarjeta adaptadora.
Durante los últimos años, los
routers se ha enfrentado a una especie de crisis de identidad
provocada por el constante afán de los fabricantes por encontrar
nuevas respuestas al explosivo crecimiento de Internet. Por suerte, un
grupo de investigadores de la Universidad de la ciudad sueca de Luleå
han desarrollado un nuevo algoritmo que ayuda a los routers a
multiplicar su rendimiento.
Utilizando el método de Luleå, es posible
transformar una gran tabla de routing con más de 40.000 registros en
una tabla de reenvío de unos 375 KB, un volumen que encaja
perfectamente en la memoria cache de muchos microprocesadores
modernos. Con el método de Luleå, la búsqueda sólo requiere una
pequeña parte de los accesos a memoria que precisan las técnicas
habituales.
Los routers IP realizan una búsqueda de
encaminamiento en una tabla de routing, donde se almacena información
referente a la topología de la red, para determinar dónde deben ser
reenviados los paquetes IP. Cada entrada o registro de la tabla
incluye, como mínimo, la dirección de red de destino (de 8 a 32 bits
de longitud), información sobre el siguiente salto en el camino hacia
el destino final y el número de interfaz. Para encaminar
correctamente un paquete, el router debe buscar en la cabecera de
dicho paquete, en concreto en la dirección IP de destino. El tamaño
y la estructura de la tabla de búsqueda generalmente dan como
resultado un complejo y lento proceso de búsqueda.
Utilizando el algoritmo Luleå y el tiempo de
acceso a memoria cache de un microprocesador común, los
investigadores suecos contabilizaron la media aproximada del tiempo de
búsqueda más probable y en el peor caso posible. El algoritmo
demostró ser capaz de realizar más de un millón de búsquedas por
segundo sobre un procesador Pentium a 200 MHz, ahora ya obsoleto.
Gracias al nuevo algoritmo, los fabricantes
pueden ahora desarrollar métodos de construcción de tablas de
routing mejores que los convencionales. También pueden superar los
problemas adicionales de la longitud variable de las direcciones y los
complejos campos de etiquetas de calidad de servicio que requiere el
tráfico IP cuando se quiere soportar voz sobre IP y gestión de
calidad de servicio (QoS). Estos y otros servicios IP de valor añadido
están dando como resultado tablas de encaminamiento mucho mayores
que, por lo general, ralentizan el rendimiento del router, a veces
hasta niveles inaceptables.
SUBSISTEMAS
En una implementación práctica, un
sistema Luleå se divide en tres subsistemas:
- El kernel de reenvío, denominado
Slow Path o “ruta lenta”.
- El kernel de encaminamiento,
denominado Fast Path o “ruta rápida”.
- El subsistema de gestión.
El kernel de reenvío maneja el procesamiento
y las transferencias de datos por cada paquete; también se encarga
del filtrado de paquetes, de la seguridad y de la gestión de la
calidad de servicio para los productos de cortafuegos. El kernel de
encaminamiento, por su parte, maneja paquetes complejos o especiales
que requieren más computación y que podrían ralentizar el flujo
principal de paquetes si son manejados por el kernel de reenvío;
asimismo, maneja los paquetes que requieren atención por otras
razones, como los mensajes de protocolo de encaminamiento. Además, el
kernel de encaminamiento sirve al kernel de reenvío actualizando las
estructuras de datos, como la tabla de reenvío, el motor de filtrado
y las tablas de traducción de direcciones de red.
Complementariamente, las características que
no son críticas para el rendimiento, como la gestión, la configuración
o el mantenimiento del sistema, se implementan fuera del kernel en el
sistema de gestión.
Encaminar, reenviar y filtrar el tráfico de
datos requiere tantas tareas de computación que resulta compresible
que los routers se hayan convertido en los cuellos de botella de
Internet. Y son las búsquedas en las tablas de encaminamiento,
especialmente cuando son de grandes dimensiones, las que más
contribuyan a la latencia.
Como es bien conocido, existen diversas técnicas
para mejorar el rendimiento de los routers. Algunas funcionan bien
dentro del marco de trabajo de la Internet actual implementando
hardware especial. Otras requieren nuevos protocolos y arquitecturas
de switching/routing. Pero los nuevos algoritmos y las técnicas
basadas en software, como las aquí comentadas, han demostrado ofrecer
rendimiento de gigabits sin requerir hardware especial ni nuevos
protocolos de switching/routing.
