 of b, the number of bits constituting the address (i.e., 32 for IPv4 and 128 for IPv6); also the complexity implied by the addition of a new pre- fix is on the order of b (exactly equal to b in the worst case). The memory space required is Mb in the worst case, where M is the number of stored prefixes. A huge amount of work has been done to simplify from some point of view the trie algorithm [74-76]. Many attempts have been done to simplify the search in the trie starting from the obser- vation that the forwarding table is almost every time a sparse structure, with a big number of elements with an empty data field. A first method, particularly effective for very sparse tries is the so-called path com- pression that consists in eliminating from the trie all the nodes having no associated forwarding information and only one child. These nodes do exist due to the fact that not all the prefixes are possible as the first part of an IP address and they represent a forbid- den prefix. Naturally, since the trie has to be updated, the canceled nodes have to be recorded, for example, in the data field of the father nodes. Another possibility is to shorten the trie depth by using values of p greater than 2. For example, the bits can be joined three by three and each three bit group can be considered an element of an alphabet A(8) with eight elements. Naturally, this representation of the routing table causes a decrease in the number of operations and an increase in the complexity of the single operation. Switching Systems: Architecture and Performances 7.8.3.2 Hardware-Based Algorithms Whatever search algorithm is used, it can be implemented a specialized hardware that runs it much faster than a general purpose processor. However, if a specialized hardware has to be used, it is also possible to study algorithms that optimize the hardware speed. This has been extensively done in the case of forwarding table lookup. The most used specialized hardware is the so-called content addressable memory (CAM) (see Chapter 5). A CAM is