Content deleted Content added
The algorithm itself, in rough form. Now to go look for secondary sources that evaluate it (there must be some among the 377 cites in Google scholar). |
add a little bit of evaluation (space bounds from orig paper; disadvantage repeated throughout the literature, so I'm not sure where to source it to, but it's sourcable). |
||
Line 2:
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 Lulea 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 Lulea 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==
| |||