 to the hth symbol in a word composed of elements of A(p). The generic element of the trie represents all the words that have the prefix indicated by the route from the trie root to the considered element. If the node does not have p leafs and represents a valid prefix it is a so-called terminating node, a node coding a prefix that, for some acceptable words is the longest matching. In this case, a forwarding port addresses is stored in the data field of the record. When the longest matching elements contained in the set of words represented in the trie with a given word in A(p) have to be searched, it can be done spanning the trie levels in ascending order and moving from level hth to the next following the pointer that cor- responds to the given word symbol in the hth position. In the router case, p=2 SO that we have to consider a binary trie. A very simple example of binary trie is shown in Figure 7.57, where both the tabular form and the trie form of a very small forwarding table are shown. To understand the meaning of the figure, let us image that an incoming IP packet has an address equal to 000. By visual inspection of the table on the left of the figure it is Telecommunication Networks Five addresses Maximum 00111 length 3 bits Output port AABCC Root 01 FIGURE 7.57 Example of binary trie, on the left the corresponding prefix table is reported. immediately determined that the packet has to be sent toward port A since the longest matching is provided by 001 in the table. Using the trie, the first bit is "0," thus from the root we move left, the second bit is zero again, thus we move left again, the third bit is a third "0," that it is not present as a pointer in the present record. Thus, the search is ended and the output port is determined by read- ing the data in the last accessed record, that is A. This is surely a fast algorithm with respect to a tabular search; moreover it is quite easy to update a trie, especially if the update consists in adding new addresses. The algorithm complexity is on the order