rites for CAO_OPT, PLO_OPT, and L-Solution has been shown by Shah and Gupta to be roughly a propor- tion of 1 to 4 to 7, respectively. Some people have conjectured that CAO_OPT is an optimal algo- rithm, as it consistently allows updates to occur within one to two clock cycles. This is different from the L-Solution, which according to extensive simulations of the authors of that paper, seems to require seven clock cycles on average. ALGORITHMS AND DATA STRUCTURES TO SUPPORT LOOKUP AND FORWARDING We learned that routers parse the destination address of every incoming packet and then match it with some entry into a routing table in order to determine to which port or next-hop address the packet should be forwarded. This matching function is not trivial given the context of optimized real-time behavior in the router. The router cannot just find any match; it must be the best match possible. For example, if an incoming packet has the destination address 154.32.4.57 and the routing table contains the following relevant entries-154.32.*, 154.32.4.*, and 154.32.4.57-only the last entry should be matched. This problem can be better understood if we consider that the routing table may contain hundreds of thousands of entries. One of the most favored algorithms for this kind of classi- fication is the LPM algorithm, which is thoroughly discussed in The Art of Computer Programming by Donald E. Knuth. 6 For example, a specific routing decision (layer 3) may have to be made for some packet based on a specific routing protocol. This protocol may use the LPM algorithm based on a trie, which we dis- cuss in this section. With address prefix matching algorithms, the forwarding database (lookup table), which must be consulted, generally contains a dictionary of address prefixes. The algorithm finds the longest initial substring of the destination address that is included in the forwarding database. During a classification (lookup and forwarding) operation, the network processor (or classification proces- sor, custom application-sp