32 IP ADDRESS LOOKUP Prefix database PI P2 1* P3 00* 0 P4 101* P2 P5 111* P3 0 P6 1000* Skip=1 P5 P7 11101* 0 Skip 1 P8 111001* 0 P9 1000011# P4 0 P6 Skip 1 0 Next hop information (If a prefix node) Skip value Segment (p9 P8 P7 Skip=2 Left pointer Right pointer Skip=1 Data structure of a node in the path-compressed trie Figure 2.8 Path-compressed trie example. and reach node P5.This node has a skip value of 1,meaning that a node is skipped on the path.We then use the 3rd bits of the key to compare with the segment field'1'(to verify we have arrived at the correct node in the path).If a match is found,it indicates that we have arrived at P5 correctly.As the 4th bit of the key is 0,we tumn left;no skip value is found so we move on.With the 5th bit a 1,we again turn right and get to node P7.Here,we reach a leaf and no skip value is found.So,the lookup stops here,and the next hop information corresponding to P7 is returned. Performance.Path compression reduces the height of a sparse binary trie.When the tree is full and there is no compression possible,a path-compressed trie looks the same as a regular binary trie.Thus,its lookup and update complexity (the worst case)is the same as a binary trie,O(W).Considering a path-compressed trie as a full binary trie with N leaves, there can be N-1 internal nodes between the root and each leaf node (including the root node),as shown in Figure 2.9.Since the path can be significantly compressed to reduce the internal nodes,the space complexity becomes O(N),independent of W. 7 internal nodes 8 prefix nodes Figure 2.9 Example of path-compressed trie with N leaves.32 IP ADDRESS LOOKUP Figure 2.8 Path-compressed trie example. and reach node P5. This node has a skip value of 1, meaning that a node is skipped on the path. We then use the 3rd bits of the key to compare with the segment field ‘1’ (to verify we have arrived at the correct node in the path). If a match is found, it indicates that we have arrived at P5 correctly. As the 4th bit of the key is 0, we turn left; no skip value is found so we move on. With the 5th bit a 1, we again turn right and get to node P7. Here, we reach a leaf and no skip value is found. So, the lookup stops here, and the next hop information corresponding to P7 is returned. Performance. Path compression reduces the height of a sparse binary trie. When the tree is full and there is no compression possible, a path-compressed trie looks the same as a regular binary trie. Thus, its lookup and update complexity (the worst case) is the same as a binary trie, O(W). Considering a path-compressed trie as a full binary trie with N leaves, there can be N − 1 internal nodes between the root and each leaf node (including the root node), as shown in Figure 2.9. Since the path can be significantly compressed to reduce the internal nodes, the space complexity becomes O(N), independent of W. Figure 2.9 Example of path-compressed trie with N leaves