In the unibit trie with examine only one bit at a time. In the worst case of unibit trie, a 32 memory accesses are required for IPv4 address. If the memory access time is 10 ns, the lookup operation will consume 320 ns. This implies a maximum forwarding speed of 3.125 million packets per second (mpps) (1/320ns). If we assume minimum sized 40-byte IP packets which is a TCP-acknowledgment packets, this can support links speed of at most 1 Gbps. However, networks these days require supporting link speeds as high as 10 Gbps and more. Clearly, achieving such a high data rate is not possible with unibit tries. The main principle of the multibit trie to examine several bits at a time (called a stride) in order to improve the performance. For example, if we examine 4 bits at a time, the lookup will finish in 8 memory accesses as compared to 32 memory accesses in a unibit trie.
Strides can be either fixed or variable-size. In the multibit trie structure, each node has a record of 2stride entries and each has two fields: one for the stored prefix and one for a pointer that points to the next child node. If all the nodes at the same level have the same stride size, we call it a fixed stride; otherwise, it is a variable stride. The multibit trie for the same sample database is shown in Fig. 5. To search a trie in strides of 3 bits, the main problem is dealing with prefixes like P2 = 1* whose lengths are not multiple of the chosen stride length. One solution is to expand a prefix like 1* into four equivalent prefixes of length 3 (100*, 101*, 110*, and 111*). However, the expanded prefixes may collide with an existing prefix at the new length. For example, P4 = 101* and P5 = 111*). In that case, the expanded prefix is discarded. The existing prefix is given priority because it captures the expansion prefix.
Fig. 1 shows an expanded trie with a fixed stride length of 3. Thus each trie node uses 3 bits. The replicated entries correspond exactly to the expanded prefixes. For example, P7 has two expansions (111010 and 111011). These two expanded prefixes are pointed by the 111 pointer in the root node (because both expanded prefixes start with 111) and are stored in 010 and 011 entries of node 2. Notice also that the entry 111 in the root node has a stored prefix P5 (besides the pointer pointing to P7 expansions), because P5 = 111 is itself an expanded prefix.
Fig. 1: “Fixed Stride Multibit Trie Example”
Route Lookup: For the example shown in Fig. 1, if the destination address begins with 1110100. The lookup process follows the 111 pointer in the root (and remembers P5 as BMP). This leads to Node 2, where 010 has no outgoing pointer buta corresponding entry contains P7’s next hop information. The search terminates with result P7.
Performance and evaluation: The main advantage of the k-bit trie is that it improves the lookup by k times. The disadvantage is that a large space is required. For example, note the waste of space in Node 1, Node 2, and Node 3.
The lookup is performed in strides of k bits. The lookup complexity is the number of bits in the prefix divided by k bits, O(W/k). For example, if W is 32 for IPv4 and k is 4, then 8 lookups in the worst case are required to access that node. An update requires a search through W/k lookup iterations plus access to each child node (2k). The update complexity is O(W/k + 2k). In the worst case, each prefix would need an entire path of length (W/k) and each node would have 2k entries. The space complexity would then be O((2k ∗ N ∗ W)/k).
Let us verify our fixed stride implementation java code using the sample prefixes shown in Fig. 1. The following java code is used to create a new fixed stride multibit trie, insert the prefixes, and find the longest matching prefix of the destination address 1110100.
FixedStrideMultiBit rami = new FixedStrideMultiBit();
rami.put("", "P1");
rami.put("1", "P2");
rami.put("00", "P3");
rami.put("101", "P4");
rami.put("111", "P5");
rami.put("1000", "P6");
rami.put("11101", "P7");
rami.put("111001", "P8");
rami.put("1000011", "P9");
System.out.println("Total number of non null entries created is "
+ rami.getNumberOfNodeCreated());
String destinationAddress = "1110100";
System.out.println("Longest prefix match for
the destination address " + destinationAddress + " is "
+ rami.longestPrefixOf(destinationAddress));
System.out.println("Number of nodes visited is " +
rami.getNumberOfNodesVisited());
Fig. 2 shows the console output after running the above code. Referring back to Fig. 1, we can see that there are 17 non null entries in total. The longest prefix match for the destination address 1110100 is P7 and 2 nodes needs to be accessed in order to find the BMP. The unibit trie example is simple as W in the worst case is 3 because the longest prefix stored is P9 of length 3.
Fig. 2: “Fixed Stride MultiBit Trie Example Output”
Choosing stride size: As we have seen before the number of memory accesses needed depends on the number of levels or the height of the trie (number of Levels = W/K where W in the worst case is 32 and K is the stride size). As we increase the stride size the number of levels will decrease and the number of memory access will also decrease. However, memory space consumed will be larger. Therefore, when choosing stride size a tradeoff happens between the memory accesses and space requirements. The designer needs to determine the proper number of levels based on the desired lookup speed. For example, if the maximum lookup speed should be 30ns and the designer is presented with memory chips at a cost of 10ns for access time, then the number of levels needs to be at max 3. Obviously, choosing the optimal stride size of each level in order to minimize the memory space varies and is highly dependent on the prefixes database.
Variable Stride Multibit Trie
If the nodes at the same level have different stride size, then the multibit trie is called a variable stride multibit trie. An example of a variable stride multibit trie of the same database exmple is shown in Fig. 3. We can see that the subtrie at level 1 has a stride of 3 bits. In level 2, node 1 subtrie has stride of 2 bits and node 2 subtrie has 3 bits.
Fig. 3: “Variable Stride Multibit Trie Example”
The use of prefix expansion in multibit tries introduces several new prefixes. These new prefixes have the same next-hop information as that of the original prefix. Moreover, the use of large strides creates a greater number of contiguous nodes that have the same BMP (Best Matching Prefix). For example, take a look at the fixed stride multibit trie in Figure 1. It shows, for example, that the prefixes P1, P2, and P3 in the first level are replicated, which means their next-hop information is repeated. Such redundant information can be compressed, saving memory and at the same time making the search faster because of the smaller height of the trie. After compression, the entire data structure can even fit into an L1 cache, which further speeds up the search as the access times are an order of magnitude faster than SRAM. In the next few pages, we discuss various compression schemes for multibit tries using bitmaps and compressed arrays.
IP Address Lookup TUTORIAL 