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 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. Figure 2.10 Multi-bit trie structure example