Luleå algorithm (original) (raw)
The Luleå algorithm of computer science, designed by , 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.
| Property | Value |
|---|---|
| dbo:abstract | The Luleå algorithm of computer science, designed by , 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. 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. (en) Lulealgoritmen är en algoritm som används för att göra de tabeller som används för routing på Internet tillräckligt kompakta för att hela funktionaliteten ska rymmas inom det cacheminne som finns på en modern PC-processor (ursprungligen Pentium III). 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 av forskare, år 1996. (bland annat docent Andrej Brodnik, doktor Mikael Degermark, professor Stephen Pink och professor Svante Carlsson) på Luleå tekniska universitet (därav namnet) med syftet att kunna ersätta dyr specialhårdvara för routing med billiga standardkomponenter. Företaget (skapades 1997 och var på 90-talet samt början av 2000-talet ett av börsens hetaste företag) försökte sedan marknadsföra PC-baserade system som alternativ till klassisk routing, men med måttlig framgång. (sv) |
| dbo:wikiPageExternalLink | http://urn.kb.se/resolve%3Furn=urn:nbn:se:ltu:diva-24248 |
| dbo:wikiPageID | 13284467 (xsd:integer) |
| dbo:wikiPageLength | 7351 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1045246571 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Luleå_University_of_Technology dbr:Internet dbr:Prefix dbr:Node_(computer_science) dbr:Luleå_University_of_Technology dbr:Computer_science dbc:Internet_architecture dbc:Routing_algorithms dbc:Routing_software dbr:Trie dbr:Data dbr:Internet_Engineering_Task_Force dbc:Networking_algorithms dbr:Craig_Partridge dbr:IPv4 dbr:IP_address dbr:Routing_table dbr:Word_(data_type) dbr:Binary_search dbr:Bit_vector dbr:Sequential_search |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Reflist dbt:Harvnb dbt:Cite_patent |
| dcterms:subject | dbc:Luleå_University_of_Technology dbc:Internet_architecture dbc:Routing_algorithms dbc:Routing_software dbc:Networking_algorithms |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:WikicatNetworkingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | The Luleå algorithm of computer science, designed by , 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. (en) Lulealgoritmen är en algoritm som används för att göra de tabeller som används för routing på Internet tillräckligt kompakta för att hela funktionaliteten ska rymmas inom det cacheminne som finns på en modern PC-processor (ursprungligen Pentium III). 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. (sv) |
| rdfs:label | Luleå algorithm (en) Lulealgoritmen (sv) |
| owl:sameAs | freebase:Luleå algorithm wikidata:Luleå algorithm dbpedia-fa:Luleå algorithm dbpedia-sv:Luleå algorithm https://global.dbpedia.org/id/4r9DA |
| prov:wasDerivedFrom | wikipedia-en:Luleå_algorithm?oldid=1045246571&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Luleå_algorithm |
| is dbo:wikiPageRedirects of | dbr:Lulea_algorithm dbr:Lulea_Algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Content-addressable_memory dbr:Luleå dbr:Radix_tree dbr:Routing_table dbr:Lulea_algorithm dbr:Lulea_Algorithm |
| is rdfs:seeAlso of | dbr:Trie |
| is foaf:primaryTopic of | wikipedia-en:Luleå_algorithm |