We saw from previous sections that hierarchical tries are on one end of the design spectrum and require large amounts of time while utilizing storage proportional to the number of rules and number of bits in the prefixes. On the other end of the design spectrum are the set pruning tries, which consume a large amount of storage but provide a time complexity proportional to the number of bits in the prefixes. Now the obvious question is, can we do the best of both?
The grid-of-tries data structure, described in [662], is an attempt in this direction; it reduces the storage space by storing a rule only once as in hierarchical tries and still achieves the same time complexity as set pruning tries, i.e.,O(W).
A closer observation of the search algorithm for hierarchical tries indicates attempts to backtrack several times that are not necessary. To understand this better, let us revisit the search on hierarchical tries shown in Figure 16.4 with the following example.
Example 16.4 Backtracking in hierarchical tries.
Let us start the search using a packet header with values F1=000 and F2=110 (see Figure 16.4). We start by looking this up in the F1 trie, which gives00 as the best match.
Using the next-trie pointer, we start the search for the matchingF2 prefix in the associated trie, containing the rule R1. However, the search fails in the first bit 1. Hence, the search would have to back up on theF1trie and restart in theF2trie of0∗, which is the parent of
00∗.
Such a backup in search is an attempt to find a matching rule that is shorter in theF1prefix, in this case0∗, and it should include all the bits inF2examined so far, including the failed bit. If the search algorithm could anticipate a priori such a sequence of bits, it could jump directly to the parent ofR7from the failed point, the root of theF2trie associated with theF1prefix00.
The grid-of-tries approach uses the key ideas of precomputation and switch pointers to speed up the search by jumping from the failedF2trie to anotherF2trie. The preprocessing algorithm that builds the trie identifies all the failure points in theF2tries and precomputes a switch pointer that allows the search to jump directly to the next possible ancestorF2trie that contains a matching rule. The jump occurs at the lowest point in the ancestorF2trie that has at least as good anF2prefix match as the current node. Furthermore, such a jump allows skipping over all rules in the next ancestorF2trie with shorter prefixes in theF2field.
A grid-of-tries data structure for the example classifier is shown in Figure 16.6. The switch pointers are illustrated by dashed arrows. Notice that theF2trie corresponding toF1prefix 00contains two switch pointers: one from nodeAto nodeCand the other from nodeBto the
F I G U R E 16.6 Using switch pointers to speed up search in grid-of-tries data structure.
node representing ruleR2. Note that nodeCand the node representing ruleR2are in theF2 trie corresponding to theF1prefix0. Similarly, there is a switch pointer connecting nodeCto the node representing ruleR8, which is on theF2trie for theF1prefix∗. The failed search for bit1in theF2trie containing ruleR4is continued by introducing a switch pointer from node Dto the node representing ruleR8.
Example 16.5 Classifying a packet using grid-of-tries.
Let us continue with the aforementioned example of classifying a packet with the header valuesF1=000andF2=110(Figure 16.6). The search when it fails while examining the first bit ofF2 uses the switch pointer to jump directly to nodeCin the F2trie containing rules R2,R3, andR7. Similarly, when the search on the next bit fails again, we jump to the node containing ruleR8in theF2trie associated with theF1prefix∗. Hence the best matching rule
for the packet isR8.
As can be seen, the switch pointer eliminates the need for backtracking in a hierarchical trie without the storage of a set pruning trie. Essentially, it allows us to increase the length of the matchingF2prefix without having to restart the search from the root of the next ancestorF2 trie.
Now we can formally define a switch pointer as follows. Look at Figure 16.7. Letvbe a node in theF1trie that represents anF1prefix,P(v). The lowest ancestor ofP(v)is the longest prefix match forP(v)in theF1trie. Let udenote the node corresponding to the lowest an- cestor ofP(v)in theF1trie. LetT(u)andT(v)be theF2tries associated with nodesuandv, respectively. Assume thatxis a node in trieT(v)that represents the prefixsand there is no node representing the prefixs0, i.e., the search fails on a0bit at nodex. If theF2 trie corre-
F I G U R E 16.7 Formal definition of switch pointers in grid-of-tries (based on [273]).
sponding to the lowest ancestorT(u)contains a nodeythat represents the prefixs0, then a switch pointer is placed at nodexthat points toy.
While the use of switch pointers speeds up the search, it has the disadvantage of some- times missing best matches rules. We will give an example that illustrates this.
Example 16.6 Missing the best matching rules in grid-of-tries.
Consider classifying a packet with the header values of F1=000 and F2=010 (Fig- ure 16.6). The search for000in theF1trie results in00∗as the best match. Using its next-trie pointer, the search continues on theF2 trie for 010. However, it fails in the second bit 1at nodeB. Hence, the switch pointer at nodeBis used to jump to the node representing rule R2. The search terminates as it has reached the leaf node andR2is declared the best matching rule. Observe that the search has completely missed ruleR3, which also matches the packet header. While ruleR2is the correct answer as it is lower in cost than ruleR3, according to our definition, in general the missed rule could have lower cost.
To avoid missing the best matching least-cost rules, each node in the F2 trie maintains an additional variable calledstoredRule. For a better explanation about what needs to be stored in the variable, let us consider a nodexin theF2trie corresponding to theF1prefixPand the F2prefixQ. The variablestoredRulein nodex, denoted bystoredRule(x), is assigned the best matching rule whoseF1prefix is a prefix ofPandF2prefix is a prefix ofQ. For instance, in the node representing ruleR2this variable will store ruleR3if ruleR3is lower in cost than ruleR2.
Now let us analyze the worst-case time complexity and space complexity for the grid- of-tries. In the worst case, the number of memory accesses required is 2W, which can be calculated as follows. First, traversing theF1 trie to find the longest prefix match will con- sume at mostW accesses. Next, the traversal ofF2 tries will consume at mostW accesses.
This is because in theF2tries we either traverse further down in the same trie or follow the switch pointer to jump to another trie. The maximum length of theF2field is alsoWbits, and hence the number of memory accesses required is bounded byW. Hence the total number of accesses isW+W=2W, which isO(W). To calculate the space complexity, observe that each rule is stored only once and each rule requiresO(W)of space. Hence, the amount of storage required isO(NW).