 and updating only the end result. This eliminates most route flaps. Still, tens of updates per second may be required in backbone routers, SO a fast update algorithm is necessary. Several proposals have been done and the problem can be considered almost solved. It is not the scope of this brief section to review the relevant algorithms in this sec- tor, the reader is encouraged to read the specific literature, starting from the following references [87-89]. 7.8.3.3 Comparison between Forwarding Table Lookup Algorithms In Table 7.5 the various forwarding table lookup algorithms are compared under different points of view. The characteristics of trie search algorithms to scale complexity with the number of bits of the address render them suitable, practically, only for small capacity routers having bus- based architecture and software implemented table lookup. In this case, algorithms based on multi-bit trie are often used for their reduced complexity. Almost all public network routers, first of all core routers where the forwarding speed is a key, use TCAM-based forwarding engines with several design particularities intended to reduce either the TCAM required dimension or the number of different TCAM used in each line card. Switching Systems: Architecture and Performances TABLE 7.5 Complexity of the Different Algorithms for the Forwarding of IP Packets Algorithm Worst Case Lookup Storage Update 1 bit trie O(Mb) PC-trie k bit-trie O(b/k) O(2k Mb/k) O(b/k + 2k) LC-trie O(b/k) O(2k Mb/k) O(b/k + 2k) The symbol O(x) indicates that the number of required operations tends to infinity increasing the dimension of the forwarding table as X, O(1) indicates that the number of required operations is independent from the dimensions of the forwarding table. 7.8.4 Broadband Remote Access Servers and Edge Routers Up to now we have described router functionalities and hardware architecture with a par- ticular attention to core routers. Core routers are the highest capacity routers and for this reason, the routers where new techno