Content deleted Content added
No edit summary |
JimJJewett (talk | contribs) also point to the much smaller original reference at the "how the algorithm works" section. |
||
| (15 intermediate revisions by 11 users not shown) | |||
Line 1:
{{Short description|Technique for storing and searching internet routing tables}}
The '''Luleå algorithm''' of [[computer science]], designed by {{harvtxt|Degermark|Brodnik|Carlsson|Pink|1997}}, is a technique for storing and searching [[internet]] [[routing table]]s 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.<ref>"[http://www1.ietf.org/mail-archive/web/ietf/current/msg01795.html second Europe trip for IETFers...] {{Webarchive|url=https://web.archive.org/web/20120819061509/http://www.ietf.org/mail-archive/web/ietf/current/msg01795.html |date=2012-08-19 }}", Craig Partridge to IETF, May 1, 1997.</ref>
The key task to be performed in internet routing is to match a given [[IPv4]] [[IP address|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 (computer science)|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
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)
==First level==
Line 41:
| contribution = Small forwarding tables for fast routing lookups
| title = Proceedings of the ACM SIGCOMM '97 conference on Applications, Technologies, Architectures, and Protocols for Computer Communication
| pages = 3–14 | year = 1997 |
| doi = 10.1145/263105.263133| s2cid = 17232414
| url = http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-24248
| doi-access = free
| isbn = 0-89791-905-X
| archive-url = https://dl.acm.org/doi/pdf/10.1145/263109.263133
| archive-date = 2025-04-07
}}.
*{{cite patent
Line 59 ⟶ 66:
| publisher = Elsevier
| year = 2007
| isbn = 978-0-12-088588-
| pages = 510–513}}.
Line 65 ⟶ 72:
| first1 = Mikael | last1 = Sundström
| title = Time and Space Efficient Algorithms for Packet Classification and Forwarding
| type= PhD Thesis
| publisher=Luleå University of Technology
| year = 2007
}}.
Line 74 ⟶ 83:
[[Category:Networking algorithms]]
[[Category:Routing algorithms]]
[[Category:Luleå University of Technology]]
| |||