CN-122027557-A - High-speed routing table searching method

CN122027557ACN 122027557 ACN122027557 ACN 122027557ACN-122027557-A

Abstract

The invention particularly relates to a high-speed routing table searching method, which aims to solve the problems of limited searching efficiency and high dynamic updating cost in the prior art. The method comprises the steps of firstly constructing a binary search tree taking prefix length as a keyword and optimizing node positions according to using frequency. Next, a hash table is configured for each node in the tree for storing the routing prefix and a jump flag that points to a better search path. When searching, starting from the tree root, searching the matching item or the mark in the node hash table in parallel, and realizing the fast sub-tree jump by using the mark so as to avoid step-by-step traversal. When the routing prefix is inserted or deleted, the relevant label is only required to be updated locally along the tree path, and global reconstruction is not required. The invention obviously reduces average access times and inquiry time delay, supports dynamic update of the routing table with lower cost, and is suitable for network forwarding scenes with high requirements on throughput, delay and update frequency.

Inventors

HUANG HEQING
ZHANG BING
QIU ZHILIANG
ZHAO TIANXING

Assignees

西安电子科技大学

Dates

Publication Date: 20260512
Application Date: 20260204

Claims (8)

1. A method for high-speed routing table lookup, the method comprising: constructing a binary search tree based on prefix lengths, namely constructing the binary search tree by taking the prefix lengths as keywords according to the use frequency of each prefix length in the search traffic, so that a node corresponding to the prefix length with high use frequency is positioned at a position closer to a root node in the binary search tree; Configuring a hash table for each node of the binary search tree, wherein the hash table is used for storing a routing prefix table item and a jump mark table item of the corresponding prefix length of the node, and the jump mark table item is used for indicating subtree nodes with possibly longer matched prefixes and caching the currently determined longest searching prefix information; The routing list item is inserted and maintained, when a new routing prefix needs to be inserted, the new routing prefix is inserted into a hash table of a node corresponding to the length of the prefix in the binary search tree, and related jump marks are created or updated along the paths of ancestor nodes of the new routing prefix; The longest prefix searching comprises the steps of starting from a root node of the binary search tree for a given target IP address, searching node by node, carrying out mask calculation on the target IP address according to the prefix length corresponding to the node in a current node, searching in a hash table of the node, taking a matched routing prefix table item as a searching result and ending searching if the matched routing prefix table item is searched, jumping to a designated subtree node according to the jump type mark table item if the jump type mark table item is searched, continuing searching, updating the longest searching prefix information recorded currently, and turning to a next node according to the sequence of the binary search tree, continuing searching until traversing is finished, and returning the recorded longest matching prefix if the jump type mark table item is searched.
2. The method according to claim 1, wherein the step of constructing the prefix length based binary search tree comprises: counting the occurrence frequencies of different prefix lengths in historical or expected lookup traffic, and generating a prefix length frequency table; Taking a node corresponding to the prefix length with the highest occurrence frequency as a root node of the binary search tree; Dividing the rest prefix length nodes into two groups according to the prefix length smaller or larger than the prefix length of the root node, and respectively selecting the node with the highest frequency in each group as a left child node and a right child node of the root node; the above procedure is performed recursively for the left and right subtrees until all prefix length nodes are placed in the tree.
3. The method of claim 1, wherein the hash table is divided into a plurality of sub-tables with exponentially increasing lengths by a segmented hash structure, wherein the insertion of the routing prefix and the jump mark is performed by a batch strategy, and the inserted target sub-table and the probing position are dynamically selected according to the current load condition of each sub-table.
4. The method of claim 1, wherein the skip tag table entries include at least a prefix fragment mapped from a longer prefix, a skip target node identification to which the tag points, current longest-lookup prefix information cached by the tag, and a source prefix node list or reference count to create the tag.
5. The method of claim 1, wherein the step of updating the hop mark upon insertion of the routing table entry comprises: Starting from the node where the newly inserted prefix is located, backtracking to the direction of the father node; for each node on the backtracking path, checking whether a jump mark matched with a plurality of bits in the prefix of the new prefix exists in the hash table; if not, creating a new jump mark, and setting a jump target of the jump mark as a node where a new prefix is located; If so, adding the node where the new prefix is located into the marked source node list, and updating the marked jump target to the nearest common ancestor node of all source nodes.
6. The method of claim 1, wherein the step of updating the jump flag when a routing entry is deleted comprises: backtracking from the node where the deleted prefix is located to the parent node direction; for relevant jump marks on the backtracking path, removing the node where the deleted prefix is located from the source node list, and updating the reference count; if the reference count of a certain mark is zero, deleting the mark; The jump target of the update-related marker is the most recent common ancestor node of its remaining source nodes.
7. The method of claim 1, wherein the step of updating the longest-lookup prefix information cached in the associated hop tag after the routing entry is inserted or deleted comprises: Determining a newly inserted or just deleted routing prefix associated with the affected hop mark; Searching the longest sub-prefix of the routing prefix; And transferring the part of the affected jump marks, the prefix fragments of which are matched with the longest sub-prefix, to an associated mark list of the longest sub-prefix, and correspondingly updating the longest searching prefix information cached in the marks.
8. The method of claim 1, wherein a default routing node with a prefix length of 0 is set in the binary search tree, and default routing information stored in the default routing node is returned when no matching routing prefix is found in the tree by the lookup process.

Description

High-speed routing table searching method Technical Field The invention relates to the technical field of Internet, in particular to a high-speed routing table searching method. Background The internet has become an indispensable key component in human production and life, has realized the transmission of various information convenient and fast to along with the popularization and the technological development of internet, the flow that bears in the network also presents explosive growth, the performance demand to network equipment is strengthened thereupon, especially to key network node equipment such as router, it has greatly influenced the transmission speed of whole computer network to handle the efficiency of various data package, in addition, novel network architecture-software defined network, aim at realizing the control face and the forwarding face separation of network, the equipment of forwarding layer needs to receive and look for the flow table that looks for the control face down fast, carry out various actions according to looking for the structure, throughput, delay and the indicator such as shake of the equipment that is located the forwarding layer have also put forward higher demands. The method has the advantages that the method is widely required to be used in network equipment such as routers and switches, and is divided into accurate searching and longest prefix searching, label forwarding in an MPLS protocol, flow table searching of an OpenFlow protocol and the like are adopted for scenes of accurate searching, the longest prefix searching is mainly used for searching an IP routing table, the decision of which port a packet is forwarded to is important in the forwarding process, the advantages and disadvantages of a table item searching algorithm directly influence the forwarding speed and become bottlenecks of network transmission capacity, so that the optimization of the routing table searching method is a long-term research topic, and a few routing table searching methods and different realization modes are developed until today at the beginning of the birth of the Internet. In the early stage of Internet development, a class-based address structure is adopted, the whole address space is divided into A, B, C parts, the searching process is simpler, the class to which the IP address belongs can be distinguished by the first several bits of the IP address, then the accurate searching is carried out in a forwarding table of each class, and the searching implementation mode can be various, and can be realized by adopting a hash table or a binary searching tree. However, as devices accessing the internet gradually increase, and the network structure becomes more and more complex, the class-based address structure cannot meet the requirements, because this approach brings about huge address space waste, the available IP addresses are gradually exhausted, and the size of the routing table is continuously increasing, so in order to improve the utilization rate of the address space, the internet engineering task group proposes an address structure without class inter-domain routing, and changes the original class-based address allocation manner, thereby creating the concept of routing prefix, and the router needs to look up the routing table and perform the longest prefix lookup to determine which port to forward the packet to in order to find a suitable destination address to forward the packet. Although the process of address exhaustion is delayed by the technology of non-class inter-domain routing and address conversion, the problem is not solved fundamentally, an IPv6 protocol is designed for the problem, the whole address space is still a hierarchical structure, the routing table searching process also needs longest prefix searching, the original algorithm applied to IPv4 can still be used for searching of IPv6, and the longer prefix length brings higher requirements to the searching speed of the algorithm. The prior art scheme is as follows: The widely adopted searching strategy is a linear searching method, the routing table is classified into a plurality of different tables according to different prefix lengths, searching is carried out simultaneously during searching, and finally the longest prefix searched is selected, the process can be implemented in parallel by using a TCAM (ternary content addressable memory), and the TCAM is developed on the basis of CAM. The state of each bit in the common CAM memory is only two '0' or '1', while each bit in the TCAM has three states, except '0' and '1', and an irrelevant state, so the three states are called as 'tri-states', which are realized through masks, and the third state characteristic of the TCAM enables the TCAM to perform both precise lookup and fuzzy lookup, and is particularly suitable for the longest prefix lookup of an IP routing table. The technology has a large amount of application in practice, but compared with the techn