ecific integrated circuit [ASIC], or other CPU for that matter) will have to traverse the trie looking for the LPM. The radix trie, Patricia trie, and leaf-pushed binary trees are some common data tree structures used to produce the best match. Any good data structure book explains them in detail. Without going into details here, we will say that they are inverted trees. Each parent node represents a partial string of the packet addresses and each child node represents one possible single-component extension. The leaves represent the strings that are stored in the trie. Readers who have experience using tree-tra- versal algorithms in pattern-matching programs from the artificial intelligence realm or those who have experience with database tree parsing algorithms will immediately understand this principle. In the example shown in Figure 13.4, where only some of the leaves are shown, an incoming packet with the destination address 154.32.4.57 will be routed to the correct interface after only four match- ing operations. 6. Donald E. Knuth, "Sorting and Searching," The Art of Computer Programming, vol. 3 (Reading, Massachusetts: Addison- Wesley, 1973). Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. CLASSIFICATION PROCESSORS NETWORK PROCESSORS (75.*) (123.*) (196.*) (154.32.17.*) (154.41.3.*) (154.41.11.*) (154.32.4.57) (154.32.4.63) (154.32.4.44) FIGURE 13.4 A trie is a data structure used in a router to efficiently produce the best matching route for the forwarding of the packet to the correct destination.7 Radix tries are simple to implement but they suffer from a potential performance disadvantage- namely, that a lookup may take O(m) (polynomial time depending on m, the number of bits in the pre- fix, which in the case of IPv4 is 32). In an interesting variation on performance-fine-tuning this trie-traversal algorithm documented by Radia P