Algorisme de Luleå

Algoritme de Lulea Exemple d'un trie de Lulea

L'algorisme de Luleå de ciències computacionals, dissenyat per Degermark et al. (1997), és una tècnica per emmagatzemar i cercar de manera eficient les taules d'encaminament d'Internet. Porta el nom de la Universitat Tecnològica de Luleå, l'institut/universitat d'origen dels autors de la tècnica. El nom de l'algoritme no apareix al document original que el descriu, però es va utilitzar en un missatge de Craig Partridge al grup de treball d'enginyeria d'Internet (IETF) que descrivia aquest document abans de la seva publicació.

La tasca clau que s'ha de realitzar en l'encaminament d'Internet és fer coincidir una adreça IPv4 determinada (vista com una seqüència de 32 bits) amb el prefix més llarg de l'adreça per a la qual hi ha informació d'encaminament disponible. Aquest problema de concordança de prefix es pot resoldre amb un trie, però les estructures trie utilitzen una quantitat important d'espai (un node per a cada bit de cada adreça) i cercar-los requereix travessar una seqüència de nodes amb una longitud proporcional al nombre de bits de l'adreça.. L'algoritme de Luleå drecera aquest procés emmagatzemant només els nodes a tres nivells de l'estructura del trie, en lloc d'emmagatzemar el trie sencer.

Abans de crear la prova de Luleå, les entrades de la taula d'encaminament s'han de processar prèviament. Qualsevol prefix més gran que se superposi a un prefix més petit s'ha de dividir repetidament en prefixos més petits, i només es conserven els prefixos dividits que no se superposen al prefix més petit. També cal que l'arbre de prefix estigui complet. Si no hi ha entrades de taula d'encaminament per a tot l'espai d'adreces, s'ha de completar afegint entrades simulades, que només porta la informació que no hi ha cap ruta per a aquest interval. Això permet la cerca simplificada a la prova de Luleå (Sundström 2007).

El principal avantatge de l'algorisme de Luleå per a la tasca d'encaminament és que utilitza molt poca memòria, amb una mitjana de 4-5 bytes per entrada per a taules d'encaminament grans. Aquesta petita empremta de memòria sovint permet que tota l'estructura de dades encaixi a la memòria cau del processador d'encaminament, accelerant les operacions. Tanmateix, té l'inconvenient que no es pot modificar fàcilment: els petits canvis a la taula d'encaminament poden requerir la reconstrucció de la majoria o de tota l'estructura de dades. Un ordinador domèstic (PC) modern té prou maquinari/memoria per dur a terme l'algorisme.

Primer nivell

El primer nivell de l'estructura de dades consta de

• Un vector de bits format per 2¹⁶ = 65.536 bits, amb una entrada per cada prefix de 16 bits d'una adreça IPv4. Un bit d'aquesta taula s'estableix en un si hi ha informació d'encaminament associada amb aquest prefix o amb una seqüència més llarga que comença amb aquest prefix, o si el prefix donat és el primer associat a la informació d'encaminament en algun nivell superior de l'intent; en cas contrari es posa a zero.
• Una matriu de paraules de 16 bits per a cada bit diferent de zero del vector de bits. Cada dada proporciona un índex que apunta a l'objecte d'estructura de dades de segon nivell per al prefix corresponent o proporciona directament la informació d'encaminament d'aquest prefix.
• Una matriu d'"índexs de base", un per a cada subseqüència consecutiva de 64 bits en el vector de bits, que apunta a la primera dada associada a un bit diferent de zero en aquesta subseqüència.
• Una matriu de "paraules de codi", una per a cada subseqüència consecutiva de 16 bits en el vector de bits. Cada paraula de codi té 16 bits i consta d'un "valor" de 10 bits i un "offset" de 6 bits. La suma del desplaçament i l'índex base associat dona un punter a la primera dada associada amb un bit diferent de zero en la subseqüència de 16 bits donada. El valor de 10 bits dona un índex en un "mapable" des del qual es pot trobar la posició precisa de la dada adequada.
• Una taula de mapes. Com que cal que l'arbre de prefix estigui complet, només pot existir una quantitat limitada de possibles valors de màscara de bits de 16 bits al vector de bits, 678. Les files de la taula de mapes corresponen a aquestes 678 combinacions de 16 bits i columnes el nombre de bits establerts a la màscara de bits a la ubicació de bits corresponent a la columna, menys 1. Així, la columna 6 per a la màscara de bits 1010101010101010 tindria el valor 2. La taula de mapes és constant per a qualsevol contingut de la taula d'encaminament.

Per buscar la dada d'una adreça x donada al primer nivell de l'estructura de dades, l'algorisme de Luleå calcula tres valors:

1. l'índex base a la posició de la matriu d'índexs base indexada pels primers 10 bits de x
2. el desplaçament a la posició de la matriu de paraules de codi indexada pels primers 12 bits de x
3. el valor de maptable[y][z], on y és l'índex de mapable de la matriu de paraules de codi i z és els bits 13-16 de x

La suma d'aquests tres valors proporciona l'índex a utilitzar per a x a la matriu d'elements.

Segon i tercer nivells

El segon i el tercer nivells de l'estructura de dades s'estructuren de manera similar entre ells; en cadascun d'aquests nivells, l'algoritme de Luleå ha de realitzar la concordança de prefix en quantitats de 8 bits (bits 17–24 i 25–32 de l'adreça, respectivament). L'estructura de dades s'estructura en "trossos", cadascun dels quals permet realitzar aquesta tasca de concordança de prefix en alguna subseqüència de l'espai d'adreces; els elements de dades de l'estructura de dades de primer nivell apunten a aquests fragments.

Si hi ha poques peces diferents d'informació d'encaminament associades a un fragment, el tros només emmagatzema la llista d'aquestes rutes i les cerca mitjançant un sol pas de cerca binària seguida d'una cerca seqüencial. En cas contrari, s'aplica una tècnica d'indexació anàloga a la del primer nivell.