Design And Verification Of Network Tree Search Engine

With the rapid development of Internet, the line speed of network processor (NP) has reached 2.5Gbps and even lOGbps beyond. This speed orders NP to be able to support fast IP address searching, so search engine is the key to packet fast forwarding.Based on the architecture, performance and cost of network processor, author compared all the search algorithms in NP, including PATRICIA tree, CAM (Content-Addressable Memory), Cache/Cascade., Binary trie tree, Multibit trie and Binary search based on the length of address prefix, etc. Then a tree search engine based on Patricia tree was proposed, and the principle of TSE was presented in this paper. TSE supports exact matching scheme (Full Match), longest pattern matching (LPM) and SMT for user definition; it supports binary Patricia tree and multibit Patricia tree; it also supports Cache/Cascade and Hashing algorithm; in addition, it supports binary search for trunking.Considering the NP performance, author implemented the TSE with RTL code. Three main blocks performing the TSE commands were descripted in this paper, such as FMLPM, FMSMT and MISC.In order to assure the correctness and to meet the functional testing and verification, a verification platform of TSE was presented. In addition, the paper also introduced our verification methodology, verification flow and verification result in this project.