Luleå algorithm: Difference between revisions

Revision as of 07:28, 16 September 2007

Revision as of 07:40, 16 September 2007

Line 1:

The '''LuleaLuleå algorithm''', 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 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...]", Craig Partridge to IETF, May 1, 1997.</ref>

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 LuleaLuleå 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 LuleaLuleå 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.

==First level==

Line 17:

* 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 LuleaLuleå 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''

Line 24:

==Second and third levels==

The second and third levels of the data structure are structured similarly to each other; in each of these levels the LuleaLuleå algorithm must perform prefix matching on 8-bit quantities (bits 17–24 and 25–32 of the address, respectively). The data structure is structured in "chunks", each of which allows performing this prefix matching task on some subsequence of the address space; the data items from the first level data structure point to these chunks.

If there are few enough different pieces of routing information associated with a chunk, the chunk just stores the list of these routes, and searches through them by a single step of [[binary search]] followed by a [[sequential search]]. Otherwise, an indexing technique analogous to that of the first level is applied.

==Notes==

{{reflist}}

==References==