The Luleå algorithm, designed by Degermark et al. (1997), is a patented technique for storing and searching internet routing tables efficiently. It is named after the Luleå University of Technology, the home institute 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.

PropertyValue
dbpprop:abstract
  • The Luleå algorithm, designed by Degermark et al. (1997), is a patented technique for storing and searching internet routing tables efficiently. It is named after the Luleå University of Technology, the home institute 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. 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.
  • Lulealgoritmen är en algoritm som används för att representera de tabeller som används för routing på Internet tillräckligt kompakt för att man skall kunna implementera en sådan funktionalitet helt inom det cacheminne som ryms på en modern PC-processor. Att hela systemet ryms inom cacheminnet är ett krav för att få acceptabla prestanda hos systemet, då cacheminnet är väsentligt snabbare än externt RAM-minne. Algoritmen utvecklades hos SICS med tanken att kunna ersätta dyr specialhårdvara för routing med billiga standardkomponenter och företaget Effnet försökte sedan marknadsföra PC-baserade system som alternativ till klassisk routing, men med måttlig framgång.
dbpprop:harvtxtProperty
  • Brodnik
  • Carlsson
  • Degermark
  • Pink
  • 1997 (xsd:integer)
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • The Luleå algorithm, designed by Degermark et al. (1997), is a patented technique for storing and searching internet routing tables efficiently. It is named after the Luleå University of Technology, the home institute 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.
  • Lulealgoritmen är en algoritm som används för att representera de tabeller som används för routing på Internet tillräckligt kompakt för att man skall kunna implementera en sådan funktionalitet helt inom det cacheminne som ryms på en modern PC-processor. Att hela systemet ryms inom cacheminnet är ett krav för att få acceptabla prestanda hos systemet, då cacheminnet är väsentligt snabbare än externt RAM-minne.
rdfs:label
  • Luleå algorithm
  • Lulealgoritmen
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of