Algoritmo de Luleå

El algoritmo de Luleå de informática , diseñado por Degermark et al. (1997) , es una técnica para almacenar y buscar eficientemente tablas de enrutamiento de Internet . Recibe su nombre de la Universidad Tecnológica de Luleå , la institución de origen de sus autores. El nombre del algoritmo no aparece en el artículo original que lo describe, pero se utilizó en un mensaje de Craig Partridge al Grupo de Trabajo de Ingeniería de Internet (IETF) antes de su publicación. ^{[ 1 ]}

La tarea clave en el enrutamiento de internet consiste en asociar una dirección IPv4 (considerada como una secuencia de 32 bits) con el prefijo más largo de la dirección para el que se dispone de información de enrutamiento. Este problema de asociación de prefijos puede resolverse mediante un trie , pero las estructuras trie consumen una cantidad considerable de espacio (un nodo por cada bit de cada dirección) y su búsqueda requiere recorrer una secuencia de nodos cuya longitud es proporcional al número de bits de la dirección. El algoritmo de Luleå simplifica este proceso almacenando únicamente los nodos de tres niveles de la estructura trie, en lugar de almacenar el trie completo.

Antes de construir el árbol de Luleå, es necesario preprocesar las entradas de la tabla de enrutamiento. Cualquier prefijo mayor que se solape con uno menor debe dividirse repetidamente en prefijos más pequeños, y solo se conservan los prefijos divididos que no se solapen con el prefijo menor. También es necesario que el árbol de prefijos esté completo. Si no hay entradas en la tabla de enrutamiento para todo el espacio de direcciones, debe completarse añadiendo entradas ficticias, que solo contienen la información de que no existe ninguna ruta para ese rango. Esto permite la búsqueda simplificada en el árbol de Luleå ( Degermark et al. (1997) ). Véase también Sundström 2007 : tenga en cuenta que se trata de una tesis doctoral completa que incluye una descripción del algoritmo original de Luleå y una aceleración de 2x del mismo, así como dos algoritmos LPM de árbol híbrido que admiten actualizaciones dinámicas y búsquedas IPv6.

La principal ventaja del algoritmo de Luleå para la tarea de enrutamiento es que utiliza muy poca memoria, con un promedio de 4 a 5 bytes por entrada para tablas de enrutamiento grandes. Este bajo consumo de memoria suele permitir que toda la estructura de datos quepa en la caché del procesador de enrutamiento, lo que acelera las operaciones. Sin embargo, tiene la desventaja de que no se puede modificar fácilmente: pequeños cambios en la tabla de enrutamiento pueden requerir la reconstrucción de la mayor parte o la totalidad de la estructura de datos. Un ordenador doméstico moderno (PC) tiene suficiente hardware y memoria para ejecutar el algoritmo.

El primer nivel de la estructura de datos consta de

• Un vector de bits compuesto por ^2¹⁶ = 65 536 bits, con una entrada para cada prefijo de 16 bits de una dirección IPv4 . Un bit en esta tabla se establece en uno si existe información de enrutamiento asociada a ese prefijo o a una secuencia más larga que comience con ese prefijo, o si el prefijo dado es el primero asociado a información de enrutamiento en algún nivel superior del árbol de prefijos; de lo contrario, se establece en cero.
• Una matriz de palabras de 16 bits para cada bit distinto de cero en el vector de bits. Cada dato proporciona un índice que apunta al objeto de estructura de datos de segundo nivel para el prefijo correspondiente, o bien proporciona directamente la información de enrutamiento para ese prefijo.
• Una matriz de "índices base", uno para cada subsecuencia consecutiva de 64 bits en el vector de bits, que apunta al primer dato asociado con un bit distinto de cero en esa subsecuencia.
• Un conjunto de "palabras clave", una por cada subsecuencia consecutiva de 16 bits en el vector de bits. Cada palabra clave tiene 16 bits y consta de un "valor" de 10 bits y un "desplazamiento" de 6 bits. La suma del desplazamiento y el índice base asociado proporciona un puntero al primer dato asociado a un bit distinto de cero en la subsecuencia de 16 bits dada. El valor de 10 bits proporciona un índice en una "tabla de asignación" a partir de la cual se puede encontrar la posición precisa del dato correspondiente.
• Una tabla de mapeo. Dado que el árbol de prefijos debe estar completo, solo puede existir una cantidad limitada de posibles valores de máscara de bits de 16 bits en el vector de bits, 678. Las filas de la tabla de mapeo corresponden a estas 678 combinaciones de 16 bits, y las columnas al número de bits activados en la máscara de bits en la posición de bit correspondiente a la columna, menos 1. Por lo tanto, la columna 6 para la máscara de bits 1010101010101010 tendría el valor 2. La tabla de mapeo es constante para cualquier contenido de la tabla de enrutamiento.

Para buscar el dato para una dirección x dada en el primer nivel de la estructura de datos, el algoritmo de Luleå calcula tres valores:

1. el índice base en la posición en la matriz de índices base indexada por los primeros 10 bits de x
2. el desplazamiento en la posición en la matriz de palabras de código indexada por los primeros 12 bits de x
3. el valor en maptable[ y ][ z ], donde y es el índice de la tabla mapeable del array de palabras de código y z son los bits 13–16 de x

La suma de estos tres valores proporciona el índice que se debe usar para x en el arreglo de elementos.

El segundo y tercer nivel de la estructura de datos tienen una estructura similar; en cada uno de estos niveles, el algoritmo de Luleå debe realizar la coincidencia de prefijos en cantidades de 8 bits (bits 17-24 y 25-32 de la dirección, respectivamente). La estructura de datos está organizada en "fragmentos", cada uno de los cuales permite realizar esta tarea de coincidencia de prefijos en alguna subsecuencia del espacio de direcciones; los elementos de datos de la estructura de datos de primer nivel apuntan a estos fragmentos.

Si un fragmento contiene pocas y suficientes piezas diferentes de información de enrutamiento, simplemente almacena la lista de estas rutas y las busca mediante una única búsqueda binaria seguida de una búsqueda secuencial . En caso contrario, se aplica una técnica de indexación análoga a la del primer nivel.

• Degermark, Mikael; Brodnik, Andrej; Carlsson, Svante; Pink, Stephen (1997), "Tablas de reenvío pequeñas para búsquedas de enrutamiento rápidas", Actas de la conferencia ACM SIGCOMM '97 sobre aplicaciones, tecnologías, arquitecturas y protocolos para la comunicación informática , Universidad Tecnológica de Luleå, pp. 3–14 , doi : 10.1145/263105.263133 , ISBN  0-89791-905-X, S2CID 17232414 , archivado del original el 07/04/2025 .

• US 6266706 , Degermark, Mikael; Brodnik, Andrej y Carlsson, Svante et al., "Sistema de búsqueda de enrutamiento rápido que utiliza un árbol de prefijos completo, un vector de bits y punteros en una tabla de enrutamiento para determinar dónde enrutar datagramas IP", publicado en 2001  .

• Medhi, Deepankar; Ramasamy, Karthikeyan (2007), Enrutamiento de redes: algoritmos, protocolos y arquitecturas , Elsevier, págs. 510–513 , ISBN  978-0-12-088588-6.

• Sundström, Mikael (2007), Algoritmos eficientes en tiempo y espacio para la clasificación y el reenvío de paquetes (Tesis doctoral), Universidad Tecnológica de Luleå.