Trie searching method and device applied to network processor

Abstract

The invention provides a Trie searching method applied to a network processor. The Trie searching method applied to the network processor is characterized by comprising the following steps that firstly, a multi-level storage structure is established, wherein the storage structure comprises a register file, an internal RAM, an external SRAM and an external SDRAM, and the priority of the register file, the priority of the internal RAM, the priority of the external SRAM and the priority of the external SDRAM are gradually reduced; secondly, a balance tree is established, wherein each bit of all routing tables is traversed, the bit of which the number of values 0 and the number of values 1 are roughly equal is found, set as a current root node and marked as a used bit, the process is repeated, and the relative balance tree is established; thirdly, data storage is conducted, wherein every time data storage is conducted, a plurality of adjacent bits of data are organized into a sub-tree structure to conduct data storage. The hierarchical storage structure is adopted for the Trie structure, the time for a key to have access to the external memories is shortened, and high searching speed is obtained at low memory cost.

Description

technical field [0001] The invention relates to a network processor, in particular to a Trie search method applied in the network processor. Background technique [0002] Due to its fast speed and good programmable performance, the network processor has become the core device of the next-generation network products. With the continuous improvement of network requirements, the line speed requirements of network processors are getting higher and higher, and the required data packet forwarding rate is also increasing. The higher the value, the faster the route lookup becomes the main bottleneck restricting the performance of the network processor. [0003] There are many routing lookup algorithms used in the core period of the network. Among them, the algorithm based on the Trie tree not only has better search speed, space complexity and time complexity, but also can continuously improve the performance of routers. Therefore, the novel modern fast routing lookup algorithms are ...

AI Technical Summary

Problems solved by technology

The path compression Trie tree algorithm is the same as the binary tree algorithm, which requires a large number of memory access operations in the search process; while the multi-branch Trie tree algorithm uses a search step width greater than 1, which improves the memory access speed, but the memory bandwidth utilization is not high.

Images