Metraipolis › archive › dc_d4b04520339c
Luleå algorithm — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Lule%C3%A5_algorithm
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T13:03:54.435Z
- SHA-256 of the archived text
202dd166e99d80b803db261e2d1804fcd302110623996f65989e1e96cfaf7c9e- Stable URL of this page
https://metraipolis.com/documento/dc_d4b04520339c
How to cite
Luleå algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Lule%C3%A5_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d4b04520339c (Metraipolis archive dc_d4b04520339c, sha256 202dd166e99d80b803db261e2d1804fcd302110623996f65989e1e96cfaf7c9e)
BibTeX
@misc{dcd4b04520339c,
title = {Luleå algorithm — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Lule%C3%A5_algorithm},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d4b04520339c; sha256 202dd166e99d80b803db261e2d1804fcd302110623996f65989e1e96cfaf7c9e},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Lule%C3%A5_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Luleå algorithm of computer science, designed by Degermark et al. (1997), is a technique for storing and searching internet routing tables efficiently. It is named after the Luleå University of Technology, the home institute/university of the technique's authors. The name of the algorithm does not appear in the original paper describing it, but was used in a message from Craig Partridge to the Internet Engineering Task Force describing that paper prior to its publication. The key task to be performed in internet routing is to match a given IPv4 address (viewed as a sequence of 32 bits) to the longest prefix of the address for which routing information is available. This prefix matching problem may be solved by a trie, but trie structures use a significant amount of space (a node for each bit of each address) and searching them requires traversing a sequence of nodes with length proportional to the number of bits in the address. The Luleå algorithm shortcuts this process by storing only the nodes at three levels of the trie structure, rather than storing the entire trie. Before building the Luleå trie, the routing table entries need to be preprocessed. Any bigger prefix that overlaps a smaller prefix must be repeatedly split into smaller prefixes, and only the split prefixes which does not overlap the smaller prefix is kept. It is also required that the prefix tree is complete. If there is no routing table entries for the entire address space, it must be completed by adding dummy entries, which only carries the information that no route is present for that range. This enables the simplified lookup in the Luleå trie (Degermark et al. (1997)). See also Sundström 2007 - Note that is a complete PhD thesis that includes a description of the original Luleå Algorithm and a 2x speedup of the Luleå Algorithm, as well as two Hybrid Tree LPM algorithms supporting both dynamic updates and IPv6 lookups. The main advantage of the Luleå algorithm for the routing task is that it uses very little memory, averaging 4–5 bytes per entry for large routing tables. This small memory footprint often allows the entire data structure to fit into the routing processor's cache, speeding operations. However, it has the disadvantage that it cannot be modified easily: small changes to the routing table may require most or all of the data structure to be reconstructed. A modern home-computer (PC) has enough hardware/memory to perform the algorithm. Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»). Fonte: Wikipedia in inglese, voce «Luleå algorithm» — https://en.wikipedia.org/wiki/Lule%C3%A5_algorithm Wikidata Q6702792 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q6702792 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Lule%C3%A5_algorithm?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1350431563, consultata il 2026-10-07T12:34:33.977Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 234f40a5217929e139b43043173139f9d1c8b28feace7f86371aecae466918c1