30 IP ADDRESS LOOKUP Prefix database P1 P2 1$ Next hop information 00* (If a prefix node) P4 1018 Left pointer Right pointer P5 111* P6 1000* Data structure of a node in P7 11101* the binary trie P8 111001* 1000011* Figure 2.6 Data structure of a 1-bit binary trie. Route Lookup.Each IP lookup starts at the root node of the trie.Based on the value of each bit of the destination address of the packet,the lookup algorithm determines whether the left or the right node is to be visited.The next hop of the longer matching prefix found along the path is maintained while the trie is traversed.An example is shown in Figure 2.6. Suppose that a destination address 11101000 is given.The IP lookup starts at the root, traverses the path indicated by the destination address,and remembers the last time a gray node was visited.The first bit of 11101000 is 1,so we go to the right and get to the node 1*,which is a gray node,the longest prefix match so far.The 2nd-5th bits of the key are 1, 1,0,and 1,respectively.So,we turn right,right,left,and right in sequence,and come to a leaf node P7.It is a prefix node and its associated next hop information is returned. Performance.The drawback of using the binary trie structure for IP route lookup is that the number of memory accesses in the worst case is 32 for IPv4.To add a prefix to the trie,in the worst case it needs to add 32 nodes.In this case,the storing complexity is 32N.S,where N denotes the number of prefixes in the forwarding table and S denotes the memory space required for each node.In summary,the lookup complexity is O(W), so is the update complexity,where W is the maximum length of the prefix.The storage complexity is O(NW). Variants of Binary Tries.The 1-bit binary trie in Figure 2.6 can be expanded to a complete trie,where every bottom leaf node is a prefix.There will be 128 leaf nodes. The data structure will be a memory with 128 entries.Each stores a prefix and can be directly accessed by a memory lookup using the seven bits of the destination address.One drawback is that the memory size becomes too big to be practical when the address has 32 bits,requiring a memory with 232 entries. One way to avoid the use of the longest prefix match rule and still find the most specific forwarding information is to transform a given set of prefixes into a set of disjoint prefixes. Disjoint prefixes do not overlap,and thus no address prefix is itself a prefix of another.A trie representing a set of disjoint prefixes will have prefixes at the leaves but not at internal nodes.To obtain a disjoint-prefix binary trie,we simply add leaves to nodes that have only one child.These new leaves are new prefixes that inherit the forwarding information of the closest ancestor marked as a prefix.Finally,internal nodes marked as prefixes are unmarked.30 IP ADDRESS LOOKUP Figure 2.6 Data structure of a 1-bit binary trie. Route Lookup. Each IP lookup starts at the root node of the trie. Based on the value of each bit of the destination address of the packet, the lookup algorithm determines whether the left or the right node is to be visited. The next hop of the longer matching prefix found along the path is maintained while the trie is traversed. An example is shown in Figure 2.6. Suppose that a destination address 11101000 is given. The IP lookup starts at the root, traverses the path indicated by the destination address, and remembers the last time a gray node was visited. The first bit of 11101000 is 1, so we go to the right and get to the node 1*, which is a gray node, the longest prefix match so far. The 2nd–5th bits of the key are 1, 1, 0, and 1, respectively. So, we turn right, right, left, and right in sequence, and come to a leaf node P7. It is a prefix node and its associated next hop information is returned. Performance. The drawback of using the binary trie structure for IP route lookup is that the number of memory accesses in the worst case is 32 for IPv4. To add a prefix to the trie, in the worst case it needs to add 32 nodes. In this case, the storing complexity is 32N · S, where N denotes the number of prefixes in the forwarding table and S denotes the memory space required for each node. In summary, the lookup complexity is O(W), so is the update complexity, where W is the maximum length of the prefix. The storage complexity is O(NW). Variants of Binary Tries. The 1-bit binary trie in Figure 2.6 can be expanded to a complete trie, where every bottom leaf node is a prefix. There will be 128 leaf nodes. The data structure will be a memory with 128 entries. Each stores a prefix and can be directly accessed by a memory lookup using the seven bits of the destination address. One drawback is that the memory size becomes too big to be practical when the address has 32 bits, requiring a memory with 232 entries. One way to avoid the use of the longest prefix match rule and still find the most specific forwarding information is to transform a given set of prefixes into a set of disjoint prefixes. Disjoint prefixes do not overlap, and thus no address prefix is itself a prefix of another. A trie representing a set of disjoint prefixes will have prefixes at the leaves but not at internal nodes. To obtain a disjoint-prefix binary trie, we simply add leaves to nodes that have only one child. These new leaves are new prefixes that inherit the forwarding information of the closest ancestor marked as a prefix. Finally, internal nodes marked as prefixes are unmarked