unterbalanced by the fact that searching for the longest prefix match- ing the address is much harder than searching for a perfect match between the address and the routing table entry. As a matter of fact, the incoming packet does not bring the information on how long is the longest prefix matching its address; thus, the research has to span all the table up to the end or up to the discovery of a perfect matching, that is necessary also the longest possible. In order to have an idea of the speed at which this operation has to be performed, let us assume that our router has five 40 Gbit/s interfaces and that the average length of an incoming IP packet is 100 bit (the minimum value is 40 bit). Let us also to assume that there are eight parallel forwarding engines and that perfect contemporary operation can be attained in the forwarding table lookup. In these conditions, and in the high traffic approximation, each forwarding engine has to perform 250 millions accesses to the forwarding table in a second. This is a huge number also for a specialized processor, showing the critical nature of the forwarding table access algorithm. Besides lookup speed, it is also important to look at what kind of database organization the algorithm requires. As a matter of fact, not only the memory occupancy has to be reduced as much as pos- sible, but it has also to be possible to update the structure fast and without interfering with the search process. It has to be considered that many core routers have about one thousand border gateway protocol (BGP) updates per second and, due to the growth of the address space, forward- ing tables growth is forecasted to be about 40 kB/year. 7.8.3.1 Binary Trie-Based Algorithms A wide class of algorithms are based on the organization of the forwarding table like a data structure called binary trie. In general a trie defined on the finite alphabet A(p) is a tree where every tree element has a number of pointers to the attached leafs comprised from 0 to p - 1. The hth level of the tree corresponds