Content deleted Content added
proper swedish spelling; eponym |
JimJJewett (talk | contribs) also point to the much smaller original reference at the "how the algorithm works" section. |
||
| (43 intermediate revisions by 30 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 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 ({{harvnb|Sundström|2007}}). (Note that is a complete PhD thesis; {{harvtxt|Degermark|Brodnik|Carlsson|Pink|1997}} is probably a better starting source.)
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.▼
▲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.
==First level==
Line 9 ⟶ 13:
The first level of the data structure consists of
* A [[bit vector]] consisting of 2<sup>16</sup> =
* An array of
* An array of "base indexes", one for each consecutive subsequence of 64 bits in the bit vector, pointing to the first
* An array of "code words", one for each consecutive subsequence of 16 bits in the bit vector. Each code word is 16 bits, and consists of a 10-bit "value" and a 6-bit "offset". The sum of the offset and the associated base index gives a pointer to the first
* A maptable. Because the prefix tree is required to be complete, there can only exist a limited amount of possible 16-bit bitmask values in the bit vector, 678. The maptable rows correspond to these 678 16-bit combinations, and columns the number of set bits in the bitmask at the bit ___location corresponding to the column, minus 1. So column 6 for the bitmask 1010101010101010 would have the value 2. The maptable is constant for any routing table contents.
To look up the
▲* An array of sixteen-bit data items for each nonzero bit in the bit vector. Each data item either supplies an index that points to the second-level data structure object for the corresponding prefix, or supplies the routing information for that prefix directly.
▲* An array of "base indexes", one for each consecutive subsequence of 64 bits in the bit vector, pointing to the first data item associated with a nonzero bit in that subsequence.
▲* An array of "code words", one for each consecutive subsequence of 16 bits in the bit vector. Each code word is 16 bits, and consists of a 10-bit "value" and a 6-bit "offset". The sum of the offset and the associated base index gives a pointer to the first data item associated with a nonzero bit in the given 16-bit subsequence. The 10-bit value gives an index into a "maptable" from which the precise position of the appropriate data item can be found.
▲To look up the data item for a given address ''x'' in the first level of the data structure, the Luleå algorithm computes three values:
#the base index at the position in the base index array indexed by the first 10 bits of ''x''
#the offset at the position in the code word array indexed by the first 12 bits of ''x''
#the value in maptable[''y''][''z''], where ''y'' is the maptable index from the code word array and ''z'' is bits 13–16 of ''x''
The sum of these three values provides the index to use for ''x'' in the array of
==Second and third levels==
Line 32 ⟶ 34:
==References==
*{{citation
| first1 = Mikael | last1 = Degermark
| first2 = Andrej | last2 = Brodnik
| first3 = Svante | last3 = Carlsson
| first4 = Stephen | last4 = Pink
| 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 | publisher = Luleå tekniska universitet
| 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
| inventor1-first = Mikael | inventor1-last = Degermark
| inventor2-first = Andrej | inventor2-last = Brodnik
| inventor3-first = Svante | inventor3-last = Carlsson
| inventor4-first = Stephen | inventor4-last = Pink
| title = Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams
| issue-date = 2001
| patent-number = 6266706
| country-code = US}}.
*{{citation
| first1 = Deepankar | last1 = Medhi
| first2 = Karthikeyan | last2 = Ramasamy
| title = Network Routing: Algorithms, Protocols, and Architectures
| publisher = Elsevier
| year = 2007
| isbn = 978-0-12-088588-6
| pages = 510–513}}.
*{{citation
| 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
}}.
{{DEFAULTSORT:Lulea Algorithm}}
[[Category:Internet architecture]]
[[Category:Routing software]]
[[Category:
[[Category:Routing algorithms]]
[[Category:Luleå University of Technology]]
| |||