LC TRIES

We have seen previously how the compressed unibit trie (Patricia trie) can be a good choice when the nodes are sparsely populated. The level compressed  (LC) trie can be effective when the nodes are densely populated. The main principle of this algorithm is to combine path compression and multibit concept together in order to improve the performance. Recall that the multibit improves the lookup by k times but the main drawback is that large memory space is required. However, if we only perform mulibit lookup wherever the sub-trie structures are full sub-trees, then no redundant memory space is required in those nodes. The construction of LC trie is, in fact, a process of finding the full sub-trie of a path compressed trie, and transform them into multibit lookup nodes.

The LC-trie algorithm starts with a disjoint-prefix unibit trie (only leaf nodes contain prefixes). Fig. 1 shows three different tries: (a) unibit trie where prefixes at leaf nodes; (b) path-compressed trie; and (c) LC-trie. The first three levels of the path-compressed trie that form a full sub-trie are converted to a single-level 3-bit sub-trie in the LC-trie. The LC-trie needs only three levels instead of the six required in the path-compressed trie.

Fig. 1: (a) unibit trie (b) compressed unibit trie (c) LC trie [3]

Route Lookup: For the example shown in Fig. 1c, if the destination address begins with 1110001. The lookup process follows the 111 pointer in the root because the multi-bit and path-compression trie lookup information shows ‘stride = 3’ means there will be 2³ = 8 branches and ‘skip = 0’ means no path compression is involved here. This leads to the node where ‘stride = 1’ means there will be 2¹ = 2 branches and ‘skip = 3’ means the following path of the trie is path-compressed, and we should compare with the stored segment, and if it matches then skip the next three bits of the IP address. We skip the next three bits 000 and examine the fourth bit, 1. The bit 1 indicates that we should take the right branch of this node, and then we come to node 14. On finding that node 14 is a leaf node, the lookup stops here, and the next hop information corresponding to node 14 is returned.

Performance [3]: “An LC-trie searches in strides of k bits, and thus the lookup complexity of a k-stride LC-trie is O(W/k). To update a particular node, we would have to go through W/k lookups and then access each child of the node (2^k). Thus, the update complexity is O(W/k + 2^k). The memory consumption increases exponentially as the stride size (k) increases. In the worst case, each prefix would need an entire path of length (W/k) and each node has 2^k entries. The space complexity would then be O((2^k ∗ N ∗ W)/k). The LC-trie can be considered a special case of a variable stride trie. The algorithm for a variable stride trie using dynamic programming would indeed result in an LC-trie if it were the optimal solution for a given set of prefixes”.