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
2.2 TRIE-BASED ALGORITHMS 31 P2a P2b )P6a P6b )P5b○P8 ○P6c (P9 Figure 2.7 Disjoint-prefix binary trie. For example,Figure 2.7 shows the disjoint-prefix binary trie that corresponds to the trie in Figure 2.6.Prefixes P2a and P2b have inherited the forwarding information of the original prefix P2,similar to other nodes such as Pla,P5b,P6a,P6b,and P6c.Since prefixes at internal nodes are expanded or pushed down to the leaves of the trie,this technique is called 'leaf pushing'by Srinivasan and Varghese [7]. 2.2.2 Path-Compressed Trie Path compression technique was first adopted in the Patricia trees [8].A path-compressed trie is based on the observation that each internal node of the trie that does not contain a route prefix and has only one child node can be removed in order to shorten the path from the root node. Data Structure.By removing some internal nodes,the technique requires a mechanism to record which nodes are missing.A simple mechanism is to store in each node: .A number,the skip value,that indicates how many bits have been skipped on the path. A variable-length bit-string,segment,that indicates the missing bit-string from the last skip operation. The path-compressed version of the binary trie in Figure 2.6 is shown in Figure 2.8.The node structure has two more fields-skip value and segment.Note that some gray nodes have a skip value 1 or >1.For instance,for node P9,its skip value =2 and the segment is '11'.As compared to P9 in Figure 2.6,the P9 node in Figure 2.8 moved up the level by 2 and missed the examination of two bits'11'.Therefore,when we traverse the trie in Figure 2.8 and reach P9,the immediate two bits of the key need to be checked with the 2-bit segment. Route Lookup.Suppose that a destination address 11101000(i.e.,the key)is given.The route lookup starts at the root and traverses the path based on the destination address bits. It also records the last gray node that was visited.The first bit of 11101000 is 1,so we go to the right and get to the prefix node P2.As the second bit of the key is 1,we go right again
2.2 TRIE-BASED ALGORITHMS 31 Figure 2.7 Disjoint-prefix binary trie. For example, Figure 2.7 shows the disjoint-prefix binary trie that corresponds to the trie in Figure 2.6. Prefixes P2a and P2b have inherited the forwarding information of the original prefix P2, similar to other nodes such as P1a, P5b, P6a, P6b, and P6c. Since prefixes at internal nodes are expanded or pushed down to the leaves of the trie, this technique is called ‘leaf pushing’ by Srinivasan and Varghese [7]. 2.2.2 Path-Compressed Trie Path compression technique was first adopted in the Patricia trees [8]. A path-compressed trie is based on the observation that each internal node of the trie that does not contain a route prefix and has only one child node can be removed in order to shorten the path from the root node. Data Structure. By removing some internal nodes, the technique requires a mechanism to record which nodes are missing. A simple mechanism is to store in each node: • A number, the skip value, that indicates how many bits have been skipped on the path. • A variable-length bit-string, segment, that indicates the missing bit-string from the last skip operation. The path-compressed version of the binary trie in Figure 2.6 is shown in Figure 2.8. The node structure has two more fields – skip value and segment. Note that some gray nodes have a skip value = 1 or >1. For instance, for node P9, its skip value = 2 and the segment is ‘11’. As compared to P9 in Figure 2.6, the P9 node in Figure 2.8 moved up the level by 2 and missed the examination of two bits ‘11’. Therefore, when we traverse the trie in Figure 2.8 and reach P9, the immediate two bits of the key need to be checked with the 2-bit segment. Route Lookup. Suppose that a destination address 11101000 (i.e., the key) is given. The route lookup starts at the root and traverses the path based on the destination address bits. It also records the last gray node that was visited. The first bit of 11101000 is 1, so we go to the right and get to the prefix node P2. As the second bit of the key is 1, we go right again
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
2.2 TRIE-BASED ALGORITHMS 33 2.2.3 Multi-Bit Trie The lookup performance can be improved by using a multi-bit trie structure [7].The multi- bit trie structure examines several bits at a time,called the lookup stride,while the standard binary trie only examines one bit at a time. Data Structure.A multi-bit trie example is shown in Figure 2.10.Its prefix database is the same as the one in Figure 2.6.Suppose we examine the destination address three bits at a time,that is,the lookup stride is 3.Then a problem arises for the prefixes like P2 =1* that do not fit evenly in multiples of three bits.One solution is to expand a prefix like 1* into all possible 3 bit extensions (100,101,110,and 111).However,prefixes like P4 =101 and P5 =111 are selected because they have longer length matches than those of expanded prefixes of P2.In other words,prefixes whose lengths do not fit into the stride length are expanded into a number of prefixes that fit into the stride length.However,expanded prefixes that collide with an existing longer length prefix are discarded. Figure 2.10 shows an expanded trie with a fixed stride length of 3 (i.e.,each trie node examines three bits).Notice that each trie node has a record of eight entries and each has two fields:one for the next hop information of a prefix and one for a pointer that points to the next child node.Consider,for example,entry 100 in the root node.It contains a prefix(P2=100)and a pointer to the trie node containing P6.The P6 pointer also points to another trie containing P9. Node I Root node Prefix Ptr Prefix database Prefix Ptr 000 Node 3 P6 P1* Prefix Ptr 000P3 001 P6 P21多 =000 P300* 001P3 010 P6 001 P4101* 010 PI 011 P6 P5111* 010 P61000 011P1 100 011 P711101* 100P2 101 P8111001 100P9 P91000011* 101 P4 110 101 110 P2 P9 111 110 111 P5 P9 111 P9 Node 2 Prefix Ptr 000 001 P8 010 P7 011 P7 100 101 110 111 Figure 2.10 Multi-bit trie structure example
2.2 TRIE-BASED ALGORITHMS 33 2.2.3 Multi-Bit Trie The lookup performance can be improved by using a multi-bit trie structure [7]. The multibit trie structure examines several bits at a time, called the lookup stride, while the standard binary trie only examines one bit at a time. Data Structure. A multi-bit trie example is shown in Figure 2.10. Its prefix database is the same as the one in Figure 2.6. Suppose we examine the destination address three bits at a time, that is, the lookup stride is 3. Then a problem arises for the prefixes like P2 = 1∗ that do not fit evenly in multiples of three bits. One solution is to expand a prefix like 1* into all possible 3 bit extensions (100, 101, 110, and 111). However, prefixes like P4 = 101 and P5 = 111 are selected because they have longer length matches than those of expanded prefixes of P2. In other words, prefixes whose lengths do not fit into the stride length are expanded into a number of prefixes that fit into the stride length. However, expanded prefixes that collide with an existing longer length prefix are discarded. Figure 2.10 shows an expanded trie with a fixed stride length of 3 (i.e., each trie node examines three bits). Notice that each trie node has a record of eight entries and each has two fields: one for the next hop information of a prefix and one for a pointer that points to the next child node. Consider, for example, entry 100 in the root node. It contains a prefix (P2 = 100) and a pointer to the trie node containing P6. The P6 pointer also points to another trie containing P9. Figure 2.10 Multi-bit trie structure example
34 IP ADDRESS LOOKUP Node I Prefix/Ptr Root node Prefix/Ptr 000 P6 000 P3 001 Ptr3. Node 3 001 P3 010 P6 Prefix/Ptr 010 P1 011 P6 000 P6 011 P1 100 P2 001 P6 100 Ptrl 101 P2 010 P6 101 P4 110 P2 011 P6 110 P2 111 P2 100 P9 111 Pr2、 101 P9 Node 2 Prefix/Ptr 110 P9 000 P5 111 P9 001 P8 010 P7 011 P7 100 P5 101 P5 110 P5 111 P5 Figure 2.11 Multi-bit trie structure example with each entry a prefix or a pointer to save memory space. Route Lookup.Let us use the example in Figure 2.10 and again suppose that the desti- nation address is 11101000.The IP lookup starts at the root and traverses the path using three address bits at a time while remembering the last prefix that was visited.The first three bits of the key 111 are used as the offset address in the root node to find if the corresponding entry contains a prefix (in this case,it contains P5).We then follow the pointer and move to the next node.Then the 4-6th bits of the key 010 are used as an offset in the second node.The corresponding entry contains P7's next hop information and a pointer pointing to a NULL address,indicating the end of the lookup. Performance.The advantage of the k-bit trie structure is that it improves the lookup by k times.The disadvantage is that a large memory space is required.One way to reduce the memory space is to use a scheme called 'leaf pushing'described in Section 2.2.1.Leaf pushing can cut the memory requirements of the expanded trie in half by making each node's entry contain either a pointer or next hop information but not both (as shown in Figure 2.11 versus the one shown in Figure 2.10).The trick is to push down the next hop information to the leaf nodes of the trie.The leaf nodes only have the next hop information, since they do not have a pointer.For instance,P6's next hop information at the entry 001 of the top middle node is pushed down to the vacant locations of its child node(i.e.,the right most node)
34 IP ADDRESS LOOKUP Figure 2.11 Multi-bit trie structure example with each entry a prefix or a pointer to save memory space. Route Lookup. Let us use the example in Figure 2.10 and again suppose that the destination address is 11101000. The IP lookup starts at the root and traverses the path using three address bits at a time while remembering the last prefix that was visited. The first three bits of the key 111 are used as the offset address in the root node to find if the corresponding entry contains a prefix (in this case, it contains P5). We then follow the pointer and move to the next node. Then the 4–6th bits of the key 010 are used as an offset in the second node. The corresponding entry contains P7’s next hop information and a pointer pointing to a NULL address, indicating the end of the lookup. Performance. The advantage of the k-bit trie structure is that it improves the lookup by k times. The disadvantage is that a large memory space is required. One way to reduce the memory space is to use a scheme called ‘leaf pushing’ described in Section 2.2.1. Leaf pushing can cut the memory requirements of the expanded trie in half by making each node’s entry contain either a pointer or next hop information but not both (as shown in Figure 2.11 versus the one shown in Figure 2.10). The trick is to push down the next hop information to the leaf nodes of the trie. The leaf nodes only have the next hop information, since they do not have a pointer. For instance, P6’s next hop information at the entry 001 of the top middle node is pushed down to the vacant locations of its child node (i.e., the right most node)