Content deleted Content added
Citation bot (talk | contribs) Add: publisher. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
m link [mM]emory footprint |
||
Line 5:
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}}).
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.
| |||