Method for traversing multi-branch Trie tree

Abstract

The invention relates to a network technique, especially an IP address searching method. In order to solve the problem of traversal performance and memory consumption of multi-branch Trie tree, the invention discloses a traversal method of multi-branch Trie tree for increasing traversal performance and reducing memory consumption. The technical scheme is that: when a node is treating, firstly, a treated record last time is compared with the node, if the node has been treated already, then, next node is traversal, if not, the node is treated by processing function; after the node has been treated, the node position information, IP prefix information corresponding to the position, block pointer and IP prefix information of its each level ancestor are recorded. The method provided by the invention has advantages that memory capacitance is reduced, distributing and releasing memory are not needed, other IP prefix information of the level needs not cached, comparison with other IP prefix of the level is not needed and traversal performance is increased. Because of employing preorder traversal method, treating order can be ensured.

Description

technical field [0001] The invention relates to network technology, in particular to an IP address search method. Background technique [0002] With the rapid development of the Internet, the interface rate of core routers used for backbone network interconnection has reached 2.5Gbit / s to 10Gbit / s. This rate requires the core router to be able to forward millions to tens of millions of packets per second. An important step in packet forwarding is to look up the routing table, so a fast IP address lookup algorithm is the key technology to achieve high packet forwarding. IP address lookup needs to achieve the longest prefix match. The disadvantage of the traditional binary Trie tree and path compression Trie tree is that the search process requires a large number of memory access operations. In recent years, with the gradual deepening of router research and the continuous improvement of router performance requirements, people have proposed a multi-branch Trie tree search al...

AI Technical Summary

Problems solved by technology

The disadvantage of the traditional binary Trie tree and path compression Trie tree is that the search process requires a large number of memory access operations

The general method of traversal is to record the prefix items that have been processed and compare them with the prefixes in the nodes that need to be processed later, which usually consumes a lot of memory and has low performance

Another method is to add fields in the specific information of each IP prefix, so that the IP prefixes in the entire table are linked to form a linear table. This method has high traversal performance, but it will occupy the already huge m-trie tree. More memory, and another problem with this method is that there is no order when processing prefixes, and they are processed in the order they were added. When displaying prefix items, the output IP prefix items are out of order, which is not conducive to checking and problems Positioning, if you want to improve its unordered problem, it will increase the complexity of updating the m-trie tree

Images