CN119363659B

CN119363659B - Prefix tree construction method, routing entry search method, device and electronic device

Info

Publication number: CN119363659B
Application number: CN202411866680.5A
Authority: CN
Inventors: 潘文豪; 罗秦薇; 乔义松; 梁军; 祝顺民
Original assignee: Alibaba Cloud Computing Ltd
Current assignee: Alibaba Cloud Computing Ltd
Priority date: 2024-12-18
Filing date: 2024-12-18
Publication date: 2025-05-09
Anticipated expiration: 2044-12-18
Also published as: CN119363659A

Abstract

The application provides a prefix tree construction method, a route entry searching device and electronic equipment, and belongs to the field of cloud computing. The method comprises the steps of obtaining the number of layers of a prefix tree and a routing effective bit range of each layer according to the mask length of at least one effective routing item, determining nodes of each layer of the prefix tree according to the routing effective bit range of each layer of the prefix tree and a binary character string obtained after the mask processing of at least one effective routing item, wherein each node of each layer of the prefix tree comprises a leaf node and a branch node, each leaf node corresponds to one effective routing item, each branch node is used for jumping to a leaf node of the same layer or a branch node of the next layer, and connecting nodes corresponding to each effective routing item layer by layer from a root node until the leaf node, so as to obtain the prefix tree, wherein each root node corresponds to an empty character or the effective routing item with the mask length of 0. The application can reduce the calculation resources consumed in the tree building process.

Description

Prefix tree construction method, route entry searching device and electronic equipment

Technical Field

The present application relates to the field of cloud computing technologies, and in particular, to a method for constructing a prefix tree, a method and an apparatus for searching a route entry, and an electronic device.

Background

In large-scale data centers and multi-tenant environments, thousands of isolated virtual networks need to be supported. By means of network segmentation and isolation technology, combining virtual network identifier and destination IP (Internet Protocol ) address, large-scale virtual network route entry searching can be realized. Currently, route entry searching is mainly performed based on an LPM (Longest Prefix Match, longest prefix matching) algorithm, which compares a target IP address of a data packet with route entries supported by a router bit by bit until a route entry with the longest matching degree with the target IP address is found. To facilitate routing entry lookup based on the LPM algorithm, a prefix tree is typically built based on routing entries supported by the router, the prefix tree being a tree structure in which nodes may represent strings that match to the location of the node.

When constructing a prefix tree, the related technology builds sub-prefix trees step by taking 8 bits as a level according to the mask length of routing entries supported by a router and the order of the bits from high to low, wherein each sub-prefix tree can comprise at least one sub-prefix tree, each sub-prefix tree can comprise 256 nodes, and the prefix tree formed by cascading multi-level sub-prefix trees is finally obtained by storing node information of each node in each sub-prefix tree.

However, the related art requires the creation of multiple levels of sub-prefix trees, and each level of sub-prefix tree includes a large number of nodes, resulting in a large consumption of computing resources.

Disclosure of Invention

The embodiment of the application provides a prefix tree construction method, a route entry searching device and electronic equipment, by adopting the method, only one prefix tree needs to be constructed, and the constructed prefix tree contains fewer nodes, so that the consumption of computing resources is reduced. The technical scheme is as follows:

in a first aspect, a method for constructing a prefix tree is provided, where the method includes:

according to the mask length of at least one effective route item, the number of layers of the prefix tree and the route effective bit range of each layer are obtained;

Determining nodes of each layer of the prefix tree according to the routing valid bit range of each layer of the prefix tree and the binary character string obtained after the at least one valid routing entry masking operation, wherein the nodes of each layer of the prefix tree comprise leaf nodes and branch nodes, the leaf nodes correspond to one valid routing entry, and the branch nodes are used for jumping to leaf nodes of the same layer or branch nodes of the next layer;

And starting from a root node, connecting nodes corresponding to each effective route item layer by layer until the nodes reach leaf nodes to obtain the prefix tree, wherein the root node corresponds to an empty character or the effective route item with the mask length of 0.

In a second aspect, there is provided a routing entry lookup method, the method applying the prefix tree constructed in the first aspect, the method comprising:

When a target data packet is received, carrying out mask processing on a target address in the target data packet to obtain a target binary character string;

Searching a target item identification from a RAM based on the route valid bit range indicated by each layer of the target binary character string and the prefix tree, wherein the target item identification is an item identification of a valid route item which is longest matched with the prefix of the target binary character string;

and identifying the corresponding effective routing entry as the next hop routing entry of the target address.

In a third aspect, there is provided an apparatus for constructing a prefix tree, the apparatus comprising:

The acquisition module is used for acquiring the number of layers of the prefix tree and the route valid bit range of each layer according to the mask length of at least one valid route entry;

A determining module, configured to determine a node of each layer of the prefix tree according to a routing valid bit range of each layer of the prefix tree and a binary string obtained after the at least one valid routing entry mask operation, where the node of each layer of the prefix tree includes a leaf node and a branch node, the leaf node corresponds to one valid routing entry, and the branch node is used to jump to a leaf node of the same layer or a branch node of a next layer;

And the connection module is used for starting from a root node, connecting the nodes corresponding to each effective route item layer by layer until the leaf node, and obtaining the prefix tree, wherein the root node corresponds to an effective route item with the empty character or the mask length of 0.

In a fourth aspect, there is provided a route entry lookup apparatus applying the prefix tree constructed in the first aspect, the apparatus comprising:

the mask processing module is used for carrying out mask operation on a target address in the target data packet when the target data packet is received, so as to obtain a target binary character string;

The searching module is further used for searching a target item identifier from the RAM based on the route valid bit range indicated by each layer of the target binary character string and the prefix tree, wherein the target item identifier is an item identifier of a valid route item which is longest matched with the prefix of the target binary character string;

and the determining module is used for determining the effective route entry corresponding to the target entry identification as the next hop route entry of the target address.

In a fifth aspect, an electronic device is provided, including a processor and a memory, where the memory stores at least one program code, where the at least one program code is configured to be invoked and executed by the processor to implement the method for building a prefix tree according to the first aspect, or the method for searching for a routing entry according to the second aspect.

In a sixth aspect, there is provided a computer readable storage medium, in which at least one computer program is stored, the at least one computer program being capable of implementing the method for constructing a prefix tree according to the first aspect or the method for searching for a routing entry according to the second aspect when executed by a processor.

In a seventh aspect, a computer program product is provided, which comprises a computer program, which when executed by a processor is capable of implementing the method for building a prefix tree according to the first aspect, or the method for searching for a routing entry according to the second aspect.

The technical scheme provided by the embodiment of the application has the beneficial effects that:

The method comprises the steps of obtaining at least one effective route item supported by a router, carrying out mask processing on each effective route item based on the mask length of each effective route item to obtain a binary character string corresponding to each effective route item, determining a route effective bit range of each layer of a prefix tree to be constructed based on the mask length of each effective route item, and determining a node of each layer of the prefix tree according to the route effective bit range of each layer and the binary character string corresponding to at least one effective route item, wherein the node of each layer of the prefix tree comprises a leaf node and a branch node, the leaf node corresponds to one effective route item, and the branch node is used for jumping to the leaf node of the same layer or the branch node of the next layer. And taking the effective route entry or the null character with the mask length of 0 as a root node, and then starting from the root node, connecting the nodes corresponding to each effective route entry layer by layer until the leaf nodes to obtain the prefix tree. The number of the included nodes is small, so that the consumption of computing resources in the tree building process is greatly reduced.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present application, the drawings required for the description of the embodiments will be briefly described below, and it is apparent that the drawings in the following description are only some embodiments of the present application, and other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

FIG. 1 is a schematic diagram of a first level sub-prefix tree constructed using a related art method;

FIG. 2 is a schematic diagram of a related art process of finding a routing entry based on a constructed prefix tree;

FIG. 3 is a flowchart of a prefix tree construction method according to an embodiment of the present application;

FIG. 4 is a schematic diagram of a prefix tree structure constructed in accordance with an embodiment of the present application;

FIG. 5 is a flow chart for storing node information for each node in a prefix tree provided by an embodiment of the present application;

FIG. 6 is a schematic diagram of implementing node skipping using a hash algorithm according to an embodiment of the present application;

FIG. 7 is a schematic diagram of another prefix tree structure constructed in accordance with an embodiment of the present application;

FIG. 8 is a schematic diagram of another implementation of node hopping using a hash algorithm according to an embodiment of the present application;

FIG. 9 is a flowchart of a method for searching route entries according to an embodiment of the present application;

Fig. 10 is a schematic diagram of a structure of a prefix tree building apparatus according to an embodiment of the present application;

FIG. 11 is a schematic diagram of a route entry lookup device according to an embodiment of the present application;

Fig. 12 is a block diagram illustrating a structure of an electronic device according to an exemplary embodiment of the present application.

Detailed Description

For the purpose of making the objects, technical solutions and advantages of the present application more apparent, the embodiments of the present application will be described in further detail with reference to the accompanying drawings.

It will be understood that the terms "each," "plurality," and "any" and the like, as used in this embodiment of the application, include two or more, each referring to each of the corresponding plurality, and any one referring to any one of the corresponding plurality. For example, the plurality of words includes 10 words, and each word refers to each of the 10 words, and any word refers to any one of the 10 words.

It should be noted that, the user information (including but not limited to user equipment information, user personal information, etc.) and the data (including but not limited to data for analysis, stored data, presented data, etc.) related to the present application are information and data authorized by the user or fully authorized by each party, and the collection, use and processing of the related data need to comply with the related laws and regulations and standards of the related country and region, and provide corresponding operation entries for the user to select authorization or rejection.

Before executing the embodiments of the present application, the terms related to the embodiments of the present application will be explained first.

The longest prefix matching algorithm is a method of selecting a preferred path in a network route. The method comprises the steps of comparing a target address of a data packet with network prefixes of routing entries supported by a router, and selecting a matching item with the longest prefix as a data packet transmission path.

Each bit of the TCAM (Ternary ContentAddressableMemory ) has a 0, 1, x state for fuzzy lookup.

A Prefix Bitmap (Prefix Bitmap) is used to indicate which nodes in the Prefix tree contain valid prefixes, including valid Prefix information for 255 intermediate nodes in the primary Prefix tree.

The child pointer bitmap (Child Pointer Bitmap) is used to indicate which of the 256 leaf nodes of the last layer of the primary prefix tree contain child prefix trees.

The mask is a string of binary numbers indicating the network address of one IP address and the split location of the host address. The length of the mask defines the size of the network address. A simple method of calculating the mask length is to count 1's in a left-to-right number mask, e.g., for 255.255.255.0, the first 24 digits from left-to-right are 1's, so the mask length is 24 bits. Also, for mask 255.255.0.0, the first 16 digits from left to right are 1, so the mask length is 16 bits.

CIDR (CLASSLESSINTER DOMAIN ROUTING, no class inter-domain routing) is a route allocation scheme, in which a diagonal line is followed by a number to indicate the mask length, e.g., 192.168.1.1/10, and the next hop of the route entry is followed in the routing table.

The Hash algorithm (Hash) is a compressed mapping that transforms an arbitrary length input into a fixed length output by the Hash algorithm.

In large-scale data centers and multi-tenant environments, thousands of isolated virtual networks need to be supported, and by means of network segmentation and isolation techniques, routing entry lookup of large-scale virtual networks can be achieved in combination with virtual network identifiers and target IP addresses. The virtual network identifier enables the routing equipment to quickly locate the virtual network, and then the routing equipment is combined with the target IP address to perform accurate routing searching in the virtual network. The routing entry lookup is typically based on a longest prefix matching algorithm that takes the longest matching routing entry as the next hop by bitwise comparison of the destination address in the current IP packet with the routing table entries supported by the local router.

As the network speed increases, the route searching frequency becomes higher and as the route searching frequency increases, the forwarding performance of the routing device decreases and the load of the CPU increases. For example, at an Ethernet rate of 40 Gbps, if a minimum Ethernet frame is used, the route lookup frequency per second is up to 6000 ten thousand, and at 100Gbps, the route lookup frequency will increase to 1.5 hundred million times per second. In order to improve the forwarding performance of the routing device and reduce the CPU load, a hardware FPGA (Field Programmable GATE ARRAY ) may be used to accelerate the LPM algorithm. When implementing LPM from the hardware architecture level, pipeline design and limited hardware resources need to be considered, and many algorithms deployed at the software level have a large limitation. In addition, the routing table supported by the router locally is not unchanged, and update operations such as adding, deleting, changing and the like can be performed on the routing entries, when the routing entries are updated, relevant routing forwarding can enter a locking period, and data packet forwarding is stopped, so that forwarding delay is caused, and even data packet loss is caused. Therefore, when the acceleration of the LPM algorithm by the hardware FPGA is considered, three indexes of resource consumption, search speed and update delay are required to be weighed.

When the hardware FPGA is used for LPM searching, the method can be divided into two types, one type is searching based on TCAM, and the other type is searching based on RAM. The lookup method based on the TCAM has higher lookup performance, but compared with the RAM, the lookup method based on the TCAM consumes more computing resources, memory resources and the like, is not suitable for a scene with tens of thousands of isolated virtual networks and hundreds of thousands of route entries, and the route table needs to be stored in the TCAM according to a specific sequence, and a single route entry update can cause most of TCAM content to be rewritten, so that larger update delay is caused. The RAM-based search method requires multiple accesses to the memory, and compared with the TCAM method, the method consumes much less resources such as computing resources and storage resources, has smaller update delay, but has slower search speed. In general, the two methods of performing LPM search by using a hardware FPGA at present have advantages and disadvantages, and if the inspection speed, the resource consumption and the update delay are to be considered at the same time, the method can be compensated by designing a proper search mechanism and an efficient memory structure. The searching method based on the RAM has become the mainstream searching method at present because of small resource consumption and update delay, and the searching method based on the RAM has great advantages by combining a hash algorithm, a prefix tree, a bloom filter and the like.

Taking prefix tree as an example, the related technology obtains a target address from an IP data packet after receiving the IP data packet by constructing the prefix tree, searches a routing entry with the maximum prefix matching degree with the target address by searching the prefix tree, and then sends the data packet to an address indicated by the routing entry. When the prefix tree is constructed in the related technology, a multi-level sub-prefix tree is constructed according to the order of bit from high to low by taking 8bit as a unit, and the multi-level sub-prefix tree is cascaded to form the prefix tree. The prefix tree has two properties, namely, a root node does not contain characters, each other node contains a node character and a node valid indicator bit, the value of the node valid indicator bit comprises 0 or 1, when the value of the node valid indicator bit is 0, the character string obtained by connecting node characters passing through the whole path from the root node to the node is invalid, the invalid character string is not matched with the prefix of each valid route item supported by a router, and the second property is that the character string obtained by connecting node characters passing through the whole path from the root node to a certain node is the character string corresponding to the node and used for representing one possible combination of 8bit binary numbers.

Referring to fig. 1, there is shown a schematic diagram of a related art construction of a first level sub-prefix tree based on the high 8 bits of five valid route entries including 0.0.0/0, 255.168.1.1/1, 12.168.20.16/2, 1.65.20.16/12, 255.20.16.1/8, wherein the entries of valid route entries 0.0.0/0 are identified as R1 and the corresponding binary string is;, the entries of valid route entry 255.168.1.1/1 are identified as R2 and the corresponding binary string is 1, the entries of valid route entry 12.168.20.16/2 are identified as R3 and the corresponding binary string is 00, the entries of valid route entry 1.65.20.16/12 are identified as R4 and the corresponding binary string is 00000001_0100, the entries of valid route entry 255.20.16.1/8 are identified as R5 and the corresponding binary string is 1111111110001_0100. The root node is set to be a null character, the left child node character of each node is set to be 0, and the right child node character is set to be 1. The process of constructing the first level sub-prefix tree based on the five valid route entries is as follows:

1. and constructing a root node. The node character of the root node is a null character and the node valid indicator bit is 1 (since the valid route entry 0.0.0.0/0 is a null character, the null character has a corresponding valid route entry with a node valid indicator bit of 1).

2. A left child node and a right child node are constructed for the root node, the left child node and the right child node belong to nodes of the first layer of the first-level sub-prefix tree, and correspond to the highest bit (namely the 1 st bit from left to right) in the upper 8 bits. The node character of the left child node is 0, the node valid indicator bit is 0 (the node valid indicator bit is 0 because 0 does not exist in the binary string of the five valid route entries), the node character of the right child node is 1, and the node valid indicator bit is 1 (the node valid indicator bit is 1 because 1 exists in the binary string of the five valid route entries).

3. And constructing a left child node and a right child node for the left child node of the root node, and constructing a left child node and a right child node for the right child node of the root node, wherein the constructed left child node and right child node belong to the nodes of the second layer of the first-level sub-prefix tree and correspond to the next highest bit (namely the 2 nd bit from right) in the 8 th bit. The node character of the left child node constructed for the left child node of the root node is 0, the node valid indicator bit is 1 (the character string obtained by connecting the node characters passing through the entire path from the root node to the child node is 00, the node valid indicator bit is 1 because of the 00 in the binary character strings of the five valid route entries), the node character of the right child node constructed for the left child node of the root node is 1, the node valid indicator bit is 0 (the character string obtained by connecting the node characters passing through the entire path from the root node to the child node is 01, and the node valid indicator bit is 0 because of the absence of 01 in the binary character strings of the five valid route entries). The node character of the left child node constructed for the right child node of the root node is 0, the node valid indicator bit is 0 (the character string obtained by connecting the node characters passing through the entire path from the root node to the child node is 10, the node valid indicator bit is 0 because 10 does not exist in the binary character string of the five valid route entries), the node character of the right child node constructed for the right child node of the root node is 1, the node valid indicator bit is 0 (the character string obtained by connecting the node characters passing through the entire path from the root node to the child node is 11, and the node valid indicator bit is 0 because 11 does not exist in the binary character string of the five valid route entries).

4. The method is adopted to sequentially construct the third layer to the eighth layer of the first-level sub-prefix tree, the node effective indication bits of the 00000001 and 11111111 node characters formed by the eighth layer are 1, and the node effective indication bits of other node characters are 0. The tree structure formed from the root node to the nodes of the eighth layer is referred to as a first level sub-prefix tree.

After the first-level sub-prefix tree is constructed, the structure of the first sub-prefix tree needs to be stored in the RAM. In order to facilitate storage, the related technology allocates a base address for a root node, constructs a prefix bitmap according to node effective indication bits corresponding to each node or sub-node, then accumulates all high bit bits before a current node based on the prefix bitmap to obtain an offset address of the current node relative to the root node, adds the offset address on the basis of the base address to obtain a storage address of the current node, and then stores an entry identifier of an effective route entry corresponding to a node character of the node or the sub-node according to the storage address, wherein the entry identifier indicates the next hop route of the router. When the prefix bitmap is constructed, the node effective indication bits of each node or sub-node are sequentially stored from the root node according to the sequence from top to bottom and from left to right, and finally the prefix bitmap with 255 bits is obtained. In fig. 1, the node valid indicator bit of the root node is 1, the node valid indicator bit of the left child node of the root node is 0, the node valid indicator bit of the right child node of the root node is 1, the node valid indicator bit of the left child node of the root node is 1, the node valid indicator bit of the right child node of the left child node of the root node is 0, the node valid indicator bit of the right child node of the root node is 1, and so on, until the next child node of the seventh layer sequentially fills the node valid indicator bits of the nodes or child nodes into corresponding spaces, thereby obtaining the prefix bitmap shown in fig. 1. According to the prefix bitmap shown in fig. 1, the 253 th bit offset address is equal to 255bit offset address+254 bit offset address, and the 253 th bit offset address in fig. 1 is 1. In addition, stored in the RAM is an entry identification of the valid route entry corresponding to the valid node.

In addition, as can be seen from analyzing the five valid route entries, if the mask length of the five route entries is 12 at the longest, two levels of sub-prefix trees need to be constructed, and fig. 1 only shows the construction process of the first level sub-prefix tree, and the construction process of the second level sub-prefix tree is similar to the construction process of the first level sub-prefix tree, and the specific construction process is not repeated. However, the second sub-level prefix tree is constructed based on the first sub-level prefix tree, after the eighth layer of the first sub-level prefix tree is constructed to obtain 256 kinds of binary strings with 8 bits, the related technology also constructs a sub-pointer bitmap, where the sub-pointer bitmap includes 256 bits, each bit is used to indicate validity of a binary string with 8 bits, if a binary string with 8 bits is a binary string with 8 bits corresponding to five valid routing entries, the binary string with 8 bits is valid, and then the binary string with 8 bits is filled with 1 at a position corresponding to the sub-pointer bitmap, and if a binary string with 8 bits is not a binary string with 8 bits corresponding to five valid routing entries, the binary string with 8 bits is invalid, and then the binary string with 8 bits is filled with 0 at a position corresponding to the sub-pointer bitmap. By adopting the method, the sub-pointer bitmap with 256 bits can be finally obtained. Referring to fig. 1, the binary string of the high 8 bits corresponding to the five valid route entries includes 00000001 and 11111111, so that the positions corresponding to 00000001 and 11111111 in the child pointer bitmap are 1, and the remaining positions are 0.

The following points can be seen by analyzing the construction process of the first level sub-prefix tree:

first, the number of mask length smaller than 8 in the effective route entries determines the effective number of root nodes and 1-7 layer nodes, and can be represented by a prefix bitmap of 255 bits, and the character string represented by the effective node is the effective route entry.

The second point, the number of mask length greater than 7 in the effective route entry, determines the effective number of the 8 th layer node, and can be represented by a sub pointer bitmap of 256 bits, and the effective node represents that the node contains a subtree, namely a next level sub prefix tree.

And the third point is that the content of the root node and the 1-7 layers of nodes stored in the RAM is the next-hop route, and the content of the eighth layers of nodes stored in the RAM is the root node address of the sub-prefix tree.

Fig. 2 shows a process of performing route entry lookup based on a constructed prefix tree, referring to fig. 2, the prefix tree includes 4 levels, the route valid bit of the first level sub-prefix tree is [ 31,24 ], the route valid bit of the second level sub-prefix tree is [ 23,16 ], the route valid bit of the third level sub-prefix tree is [ 15,8 ], the route valid bit of the fourth level sub-prefix tree is [ 7,0 ], after receiving an IP packet, a target address in the IP packet is matched with each valid route entry supported by a local router, when matching is performed, the first level sub-prefix tree is queried every 8 bits from a high level, a sub-pointer bitmap and a prefix bitmap are searched in parallel until the longest matching is found at a certain valid node, and a next route bitmap is fetched from a RAM according to an offset address indicated by a base address and the prefix bitmap.

Assuming that the router supports an active routing entry 255.20.16.1/25, masking 255.20.16.1/25 results in a secondary string of 11111111_00010100_00010000_0. The secondary system character string represented by the effective node of the first-stage sub-prefix tree is 11111111, the secondary system character string represented by the effective node of the second-stage sub-prefix tree is 00010100, the secondary system character string represented by the effective node of the third-stage sub-prefix tree is 00010000, and the secondary system character string represented by the effective node of the fourth-stage sub-prefix tree is 0. Based on the prefix tree, if a matching valid routing entry is to be found for the target address 255.20.16.10, a masking operation may be performed on the target address 255.20.16.10, and the obtained binary string is 11111111111_00010100_00010000_00001010, and the binary string is matched from the first-level sub-prefix tree to the valid node (the represented string is 0) of the fourth-level sub-prefix tree, where no longer matching exists later, which indicates that the valid routing entry is hit, and then the valid routing entry is taken as the next hop. The specific lookup of the target address 255.20.16.10 is exemplified by the following query procedure:

1. The method comprises the steps of obtaining a binary string 11111111 with 8 bits high of a target address 255.20.16.10, carrying out string matching on the binary string 11111111 at each layer of a first-level sub-prefix tree, wherein strings matched at 1-8 layers are 1, 11, 111 and 1111..11111, and based on the established prefix tree, 1, 11, 111 and 1111 and 1111111 (7 1) are invalid nodes, namely the valid bit of the node is 0. According to the sub-pointer bitmap and the prefix bitmap, the matching character strings in the valid node are 111111111 only.

2. Because the node with the character string of 11111111 is the 8 th layer node and is an effective node, the method jumps to the first level sub-prefix tree to search for the above, searches for the first level sub-prefix tree, and searches for the first level sub-prefix tree and the third level sub-prefix tree.

3. When searching in the fourth-level sub-prefix tree, the binary string 00001010 of the low 8bit of the target address 255.20.16.10 is obtained, then, the string matching is carried out at each layer of the fourth-level sub-prefix tree, the strings matched at 1-8 layers are respectively 0 (1 bit of 00001010), 00 (the first 2 bits of 00001010), 000 (the first 3 bits of 00001010), 0000 (the first 4 bits of 00001010), 00001 (the first 5 bits of 00001010), 000010 (the first 6 bits of 00001010), 0000101 (the first 7 bits of 00001010) and 00001010 (the first 8 bits of 00001010), and according to the sub-pointer bitmap and the prefix bitmap, the matched string in the effective node is only 0, so that the routing entry of 255.20.16.10 is determined to be 255.20.16.1/25, and the next-hop routing entry is fetched from the RAM according to the base address of the 4-level sub-prefix tree and the offset address indicated by the prefix bitmap.

Still taking the router as an example to support an effective routing entry 255.20.16.1/25, assuming that a matching effective routing entry is to be searched for the target address 255.20.16.128, the target address 255.20.16.128 may be first subjected to a masking operation, the obtained binary string is 11111111111_00010100_00000001_10000000, the binary string is matched from the first-stage sub-prefix tree to the fourth-stage sub-prefix tree, the fourth-stage sub-prefix tree has only one effective node, the represented binary string is 0, the low-order octal binary string of 255.20.16.128 is 10000000, and the effective node in the fourth-stage sub-prefix tree of the routing rule is missed, at this time, the fourth-stage node needs to be reversed from the fourth-stage node, the root node is found to be not the effective node, the node is reversed to the third-stage, the node found to be the eighth-stage, the second-stage and the first-stage are also the same, but no next-hop routing is performed in the eighth-stage, so that the target address 34 can be determined as the effective node in the fourth-stage sub-prefix tree of the routing rule (the first-stage node is the default node).

Further, if the routing rule is to be hit by 255.20.16.128, a new valid routing entry 255.20.16.11/24 needs to be newly added in the router, after the mask operation is performed on 255.20.16.11/24, the binary string is 11111111111_00010100_00010000, the valid routing entry establishes a valid node at the root node of the fourth-level sub-prefix tree, and when 255.20.16.128 rolls back in the fourth-level sub-prefix tree, the valid routing entry is hit by the pouring back to the root node, and then the valid routing entry 255.20.16.11/24 is used as a routing entry of the next hop.

Further, since the active nodes in the prefix tree are sequentially stored in the RAM, in order to support the update operations of adding, deleting, changing, etc. the active routing entries, the RAM of the related art needs to reserve RAM space for each level of sub-prefix tree. When an update operation is performed on valid route entries in the routing table, it is necessary to entirely rewrite the contents stored in the RAM of nodes subsequent to the node where the change occurs, to ensure the accuracy of the update operation.

Compared with the TCAM method, the method for searching the route entry by constructing the prefix tree in the related technology has obvious advantages in terms of resource consumption and searching speed, but the prefix tree constructed in the related technology still has the following problems:

The first problem is that the number of nodes is large

This problem is particularly pronounced when the mask length of the routing entry is discrete, since the related art builds a multi-level sub-prefix tree based on the mask length of the effective routing entry and concatenates the multi-level sub-prefix tree into a prefix tree, where each level of sub-prefix tree includes more nodes. For example, when there is a valid routing entry with a mask length exceeding 23, then a four level sub-prefix tree is constructed as needed. More importantly, the number of nodes included in the constructed prefix tree is large, but the number of effective nodes corresponding to the effective routing entries is not large, taking the first-stage sub-prefix tree constructed in fig. 1 as an example, the number of effective nodes is only 5, but the number of nodes included in the first-stage sub-prefix tree constructed reaches hundreds, and the waste of computing resources and storage resources is serious. And when the effective route entry is searched based on the constructed prefix tree, the searching efficiency is lower.

The RAM storage efficiency is low

Since the active nodes of the prefix tree are sequentially stored in the RAM, in order to support the increase of active routing entries, RAM space needs to be reserved for each level of sub-prefix tree, resulting in low RAM resource utilization. And when RAM reserved in a sub-prefix tree of a certain level is consumed, the updating of the effective routing entry is limited.

Problem three, update delay is large

Since the active nodes of the prefix tree are stored sequentially in RAM, when an active routing entry needs to be updated, a subsequent RAM content overwriting of a certain node will be caused, resulting in excessive update delay.

In order to solve the problems in the related art, the application provides a method for constructing a prefix tree based on a mask level, which can cover all effective route entries by constructing one prefix tree, and the constructed prefix tree only comprises effective nodes and no invalid nodes, thereby greatly reducing the number of nodes, saving computing resources and storage resources, and improving the searching efficiency when searching based on the constructed prefix tree. In addition, the application adopts the hash algorithm to realize the jump among the nodes, the node information of each node is stored in the RAM in a non-sequence mode, RAM space is not required to be reserved for the prefix tree of each level, RAM resource pooling scheduling is realized, and the resource utilization rate of the RAM is improved. Further, since the node information of each node is not sequentially stored in the RAM, when the valid route entry is updated, only the node information corresponding to the updated valid route entry needs to be stored in the RAM, and the storage location does not need to be concerned.

In summary, the application provides a mask level tree building mechanism with flexible tree building, high-efficiency memory structure and low update delay, which overcomes the problems of more nodes, low RAM storage efficiency and large update delay when the prefix tree is built and implemented in the FPGA as a search tree mechanism in the related art. The specific solution is embodied in the following three aspects:

In a first aspect, a mask level is determined based on a mask length range, and then a prefix tree is built based on the mask level, and all valid routing entries are built in one prefix tree without multi-level tree union. And the sparse the distribution of the mask level, the more concise the prefix tree is constructed, and the higher the searching efficiency is when searching is carried out based on the prefix tree in the follow-up process.

In the second aspect, the hash calculation is adopted to realize the jump among the nodes, and the node information is stored in the RAM in a non-sequence manner, so that the RAM resource pooling scheduling is realized. And when the effective routing entry is updated, pre-stored RAM resources can be shared, so that an efficient RAM storage structure is realized, and the RAM storage efficiency is improved.

In the third aspect, when the effective route entry is updated, only relevant nodes are updated, the nodes are not updated on a large scale, the updating range is smaller, and the updating delay is smaller. For example, when adding an active route entry, if the mask length of the newly added active route entry already exists, only the mask of the branch node and the storage location of the leaf node related to the newly added active route entry are changed, and if the mask length of the newly added active route entry does not exist, a new node needs to be added between the original branch node and the leaf node. When deleting an effective route entry, only node information related to the effective route entry is deleted.

The embodiment of the application provides a method for constructing a prefix tree, and takes an electronic device as an example for executing the embodiment of the application, wherein the electronic device can be a device with a network routing function, such as a router and the like. Referring to fig. 3, the method provided by the embodiment of the application includes:

301. And according to the mask length of at least one effective routing entry, the number of layers of the prefix tree and the routing effective bit range of each layer are obtained.

For any router, to implement the network address lookup function of the router, a prefix tree for performing a route lookup for the router may be constructed for the router based on at least one valid route entry supported by the router. Typically, the nature of the different routers is different, as are the valid route entries supported. To be able to distinguish between different valid route entries, a different entry identification may be set for each valid route entry, which is used to uniquely identify one valid route entry in the router, which may be R0, R1, R2. The mask length of each effective route item is different, the maximum mask length is 32, the minimum mask length is 0, and the mask length of the effective route item is between 0 and 32 according to the mask length rule. And carrying out mask processing on at least one effective route item according to the mask length of the at least one effective route item to obtain binary character strings corresponding to each effective route item, wherein the lengths of the binary character strings are between 0 and 32. For example, the router supports nine valid routing entries, 0.0.0.0/0、100.64.0.0/10、172.17.112.0/20、172.17.0.0/20、172.17.96.0/20、172.17.208.0/20、192.168.10.0/24、192.168.3.0/24、192.168.1.0/24, each, wherein an entry of 0.0.0.0/0 is identified as R0, its corresponding binary string is a null character, an entry of 100.64.0.0/10 is identified as R1, its corresponding binary string is 010010001, an entry of 172.17.112.0/20 is identified as R2, its corresponding binary string is 101010000_0100010111, an entry of 172.17.0/20 is identified as R3, its corresponding binary string is 101010000_0100010000, an entry of 172.17.96.0/20 is identified as R4, its corresponding binary string is 101010000_0100010110, an entry of 172.17.208.0/20 is identified as R5, its corresponding binary string is 101010000_0100110, an entry of 192.168.0/24 is identified as R6, its corresponding binary string is 101010000_0100000, an entry of 192.168.10.0/24 is identified as R1, and its corresponding binary string is 1010000_0000_0000, and an entry of 192.168.010.010.010.0000_0000 is identified as R1.

The routing valid bit range of each layer refers to the bit range of binary characters of the valid routing entries intercepted by each layer according to the sequence from high order to low order. The application can determine the number of non-zero mask lengths in at least one effective routing entry as the number of layers of the prefix tree when the number of layers of the prefix tree and the route effective bit range of each layer are obtained according to the mask length of at least one effective routing entry, for example, if the mask length of nine effective routing entries in the above example comprises 0,10,20 and 24, the mask length with the exclusion length of 0 is used, the number of non-zero mask lengths is 3, and the number of layers of the prefix tree is determined to be 3.

The application obtains the route valid bit range of each layer of the prefix tree according to the mask length of at least one valid route entry, sequences the mask length of at least one valid route entry according to the sequence from small to large, and determines the mask length range between two adjacent layers as the route valid bit range of one layer. Specifically, if there is no default route with a mask length of 0 in at least one valid route entry, the default route is placed in the root node, then the length range between 0 and the minimum mask length is taken as the route valid range of the first layer, the minimum prefix length is taken as the node of the first layer, the length range between the minimum mask length and the second minimum mask length is taken as the route valid range of the second layer, the next minimum prefix length is taken as the node of the second layer, and the length range between the next maximum mask length and the maximum mask length is taken as the route valid range of the last layer. If a default route with a mask length of 0 exists in at least one effective route entry, the default route is placed in a root node, then a length range between 0 and a non-zero minimum mask length is used as a route effective range of a first layer, a non-zero minimum prefix length is used as a node of a first layer, a length range between the non-zero minimum mask length and a secondary minimum mask length is used as a route effective range of a second layer, a secondary minimum prefix length is used as a node of the second layer, and the length range between the secondary maximum mask length and the maximum mask length is used as a route effective range of a final layer.

For example, the router supports nine valid route entries, the mask lengths of the nine valid route entries are sorted from small to large by 0.0.0.0/0、100.64.0.0/10、172.17.112.0/20、172.17.0.0/20、172.17.96.0/20、172.17.208.0/20、192.168.10.0/24、192.168.3.0/24、192.168.1.0/24,, the sorting result is 0, 10, 20, 24, based on the sorting result, 0.0.0/0 is placed at the root node, then the length range [ 0,9 ] between the minimum mask length 10 of 0 and non-zero is determined as the route valid range of the first layer, the length range [ 10,19 ] between the minimum mask length 10 and the second minimum mask length 20 of non-zero is determined as the route valid range of the second layer, and the length range [ 20,23 ] between the minimum mask length 20 and the maximum mask length 24 is determined as the route valid range of the third layer.

302. And determining the nodes of each layer of the prefix tree according to the routing valid bit range of each layer of the prefix tree and the binary character string obtained after the at least one valid routing entry mask is processed.

Wherein the nodes of each layer of the prefix tree comprise leaf nodes and branch nodes, the leaf nodes correspond to one effective route entry, and the branch nodes do not correspond to the effective route entry, but are used for jumping to the leaf nodes of the same layer or the branch nodes of the next layer. Each node of each layer corresponds to a routing valid bit, and the routing valid bit refers to a binary string intercepted from binary strings corresponding to at least one valid routing entry based on the routing valid bit range of each layer. Specifically, when determining the node of each layer of the prefix tree according to the routing valid bit range of each layer of the prefix tree and the binary character string obtained after at least one valid routing entry mask operation, a method may be adopted in which, according to the routing valid bit range corresponding to each layer, binary character strings located in the length range indicated by the routing valid bit range of each layer are intercepted from the binary character string obtained after at least one valid routing entry mask processing, at least one binary character string is obtained, and one binary character string corresponding to each layer is used as a node, so as to obtain the node of each layer of the prefix tree. That is, the number of nodes per layer depends on the kind of binary string, and there are several kinds of binary strings, that is, there are several nodes. In order to facilitate distinguishing nodes of the same layer from nodes of different layers, different node identifiers can be set for different nodes, and the node identifiers can be represented in at least one form of numbers, letters, symbols and the like. For example, node identification 0 may be set for the root node, and if the first layer includes three nodes, node identifications 1,2,3 may be set for the three nodes, respectively.

Taking the above example as an example, the router supports that the route effective range of the first layer of binary strings .、0110010001、1010110000_0100010111、1010110000_0100010000、1010110000_0100010110、1010110000_0100011101、1100000010_1010000000_1010、1100000010_1010000000_0011、1100000010_1010000000_0001. corresponding to nine effective route entries is [ 0,9 ], the binary strings from the high 1 bit to the high 10 bit need to be intercepted from the binary strings corresponding to the effective route entries, except for the default route, the binary strings intercepted from 0110010001 are 0110010001, the binary strings intercepted from 101010000_0100010111, 101010000_0100010000, 101010000_0100010110 and 101010000_0100011101 are 101010000, the binary strings intercepted from 1100000010_1010000000_1010, 1100000010_0011 and 1100000010_0000000_0001 are 1100000010, the node identified as ID2 is constructed for the binary string 0110010001, the node identified as ID1 is constructed for the binary string 1010000, the node identified as ID3 is constructed for the binary string 1010000, and the final node 1100000010 is constructed for the node of the third layer.

The effective route range of the second layer is [ 10,19 ], the binary string from 11 high bits to 20 high bits is required to be intercepted from the binary string corresponding to the effective route entry, the binary string intercepted from 101010000_0100010111 is 0100010111 except for the binary string with the default route and the mask length of 10, the node is identified as the node of ID4 is constructed for the binary string, the binary string intercepted from 101010000_0100010000 is 0100010000 and the node is identified as the node of ID5 is constructed for the binary string, the binary string intercepted from 101010000_0100010110 is 0100010110 and the node is identified as the node of ID6 is constructed for the binary string, the binary character intercepted from 101010000_0100011101 is 0100011101 and the node is identified as the node of ID7 is constructed for the binary string, and the node ID4, the node ID5, the node ID6 and the node ID7 are the node of the same order, in other words, the node ID1 is the node of high bit corresponding to the node ID2, and the node ID2 is the node of the same. Next, the binary character of the upper 11 bits to the upper 20 bits is truncated from 1100000010_1010000000_1010, 1100000010_1010000000_0011, 1100000010_1010000000_0001, the truncated binary character strings are 1010000000, the node identified as ID8 is constructed for the binary character string, the binary character string of the upper 1 bits to the upper 10 bits of the valid routing entry corresponding to the node ID8 is 1100000010, and thus the node is a child node of the node ID 3. At this time, it may be determined that the second layer includes five nodes, namely, node ID4, node ID5, node ID6, node ID7, and node ID8, where node ID4, node ID5, node ID6, and node ID7 have the same upper layer node, i.e., node ID1.

The route effective range of the third layer is [ 20,23 ], the binary character string from the upper 21 bits to the upper 24 bits is required to be intercepted from the binary character string corresponding to the effective route entry, the binary character string intercepted from 1100000010_1010000000_1010 is 1010 and the node is identified as the node of ID9, the binary character string intercepted from 1100000010_1010000000_0011 is 0011 and the node is identified as the node of ID10 except the binary character string with the default route and the mask length smaller than 20, and the binary character string intercepted from 1100000010_1010000000_0001 is identified as the node of ID 11. At this time, it can be determined that the third layer includes three nodes, namely, node ID9, node ID10, and node ID11, wherein node ID9, node ID10, and node ID11 have the same upper layer node, namely, node ID8.

303. And starting from the root node, connecting the nodes corresponding to each effective route entry layer by layer until the nodes reach the leaf nodes to obtain a prefix tree.

In the embodiment of the application, the constructed prefix tree has the following properties:

1) If the valid route item supported by the router comprises a default route, the root node is a default route with the mask length of 0, and if the valid route item supported by the router does not comprise the default route, the root node is null, that is, the root node corresponds to a null character or an valid route item with the mask length of 0.

2) The number of layers of the prefix tree is not fixed, the maximum number of layers is 32 layers plus the layer where the root node is located according to the rule that the mask length is 32 at maximum, and the total number of the layers is 33, wherein the nodes of each layer are of two types:

The first type is leaf nodes, and corresponds to an effective route entry;

The second type is a branch node, which does not necessarily correspond to an active route entry, for jumping to a leaf node.

3) The number of branch nodes is determined by the binary number type after the masking operation at the same level, the number of valid routing entries contained in the level determines the number of leaf nodes, and each node is assigned a node identifier.

Based on the specific properties of the prefix tree, after determining the nodes of each layer of the prefix tree, starting from a root node, connecting the nodes corresponding to each effective route entry layer by layer until the leaf nodes to obtain the prefix tree, wherein the prefix tree can represent the connection relation among the nodes of different layers, the node identification of each node, the route valid bit corresponding to each node and the entry identification of the effective route entry.

Taking the above example as an example, referring to fig. 4, if the router supports the default route with the mask length of 0, the node ID0 corresponding to the default route R0 is set as the root node, the route valid bit range of the node at the next layer of node ID0 is [ 0,9 ], the nodes at the next layer of node ID0 are node ID1, node ID2 and node ID3, and node ID2 is the leaf node and corresponds to the valid route entry R1. The node ID1 and the node ID3 are branch nodes, wherein the route valid bit range of the next-layer node of the node ID1 is [ 10,19 ], the next-layer node of the node ID1 is a node ID4, a node ID5, a node ID6 and a node ID7, the node ID4, the node ID5, the node ID6 and the node ID7 are leaf nodes, the node ID4 corresponds to a valid route item R2, the node ID5 corresponds to a valid route item R3, the node ID6 corresponds to a valid route item R4, the node ID7 corresponds to a valid route item R5, the route valid bit range of the next-layer node of the node ID3 is [ 10,19 ], the next-layer node of the node ID1 is a node ID8, the node ID8 is a branch node, the next-layer node of the node ID8 is a node ID9, the node ID10 and the node ID11, the node ID9, the node ID10 and the node ID11 are corresponding to the leaf nodes, the node ID10 and the node ID11 correspond to the valid route item R9, the prefix is constructed in the tree structure, and the valid route item R11 is indicated before the tree structure is constructed.

The embodiment of the application is a searching mechanism based on RAM, and after constructing the prefix tree, node information of each node in the prefix tree is stored in RAM, so that a subsequent router can search a next hop route for a data packet carrying a target address after receiving the data packet. The key of storing the node information of each node in the prefix tree is that the storage address of each node is determined, and then the node information of each node in the prefix tree is stored based on the determined storage address. Referring to fig. 5, which illustrates a storage flow of node information for each node in a prefix tree, the method flow includes:

501. And for the node corresponding to any one effective routing entry in the prefix tree, determining the storage address of the current layer node in the random access memory RAM according to the node identifier of the previous layer node and the routing effective bit of the current layer node.

Taking any effective route entry as an example, the storage address of the current layer node in the RAM can be determined based on the node corresponding to the effective route entry in the prefix tree according to the node identifier of the previous layer node and the route effective bit of the current layer node. Specifically, based on the upper and lower layer nodes indicated by the prefix tree, when determining the storage address of the current layer node in the random access memory RAM according to the node identifier of the upper layer node and the route valid bit of the current layer node, the node identifier of the upper layer node and the route valid bit of the current layer node can be spliced to obtain the search information of the upper layer node, and then hash calculation is performed on the search information of the upper layer node to obtain the storage address of the current layer node. The storage address of the current node is used for storing node information of the current layer node, and the node information of the current layer node may include a node identifier of the current layer node and an entry identifier of a valid route entry, or may include a node identifier of the current layer node and a route valid bit range of a next layer node. The node information of the current layer node specifically is an item identifier of a valid route item or a route valid bit range of a next layer node, and depends on the type of the current layer node, if the current layer node is a leaf node, the node information of the current layer node comprises the node identifier of the current layer node and the item identifier of the valid route item, and if the current layer node is a branch node, the node information of the current layer node comprises the node identifier of the current layer node and the route valid bit range of the next layer node.

It should be noted that, the foregoing description is given by taking one valid route entry as an example, and the storage address of each layer of nodes may be determined according to the foregoing method for other valid route entries. In addition, since the nodes corresponding to at least one effective route entry have the same node, when the storage address of a node is determined based on a certain effective route entry, the storage address of the node is not required to be determined based on other effective route entries later.

Referring to fig. 6, node ID0 is a root node, node IDs 1, 3 and 8 are branch nodes, and node IDs 2, 4, 5, 6, 7, 9, 10 and 11 are leaf nodes. The method comprises the steps that a node at the upper layer is a node ID0, a node at the current layer is a node ID1, a node identifier of the node at the upper layer is 0, a route valid bit of the node at the current layer is 101010000, the node identifier of the node at the upper layer is spliced with the route valid bit of the node at the current layer to obtain search information 0_101010000 of the node ID0, hash calculation is carried out on the search information of the node ID0 to obtain a storage address of the node ID1, and the storage address of the node ID1 is used for storing the node identifier 1 of the node ID1 and a route valid bit range [ 10,19 ] of the node at the next layer; the node of the upper layer is node ID0, the node of the current layer is node ID2, the node identifier of the node of the upper layer is node ID3, the route valid bit of the node of the current layer is 0110010001, the node identifier of the node of the upper layer is spliced with the route valid bit of the node of the current layer to obtain search information 0_010010001 of the node ID0, hash calculation is carried out on the search information of the node ID0 to obtain a storage address of the node ID2, the storage address of the node ID2 is used for storing the node identifier 2 of the node ID2 and an item identifier R1 of an effective route entry, the node of the upper layer is node ID0, the node of the current layer is node ID3, the node identifier of the node of the upper layer is 0, the route valid bit of the node of the current layer is 1100000010, the node identifier of the upper layer is spliced with the route valid bit of the node of the current layer to obtain search information 0_1100000010 of the node ID0, hash calculation is carried out on the search information of the node ID0 to obtain a storage address of the node ID3, and the storage address of the node ID3 is used for storing the node identifier 3 and a route valid bit range of the node ID3 and the node of the next layer is 10 and 19.

The method comprises the steps that a node at the upper layer is a node ID1, a node at the current layer is a node ID4, a node identifier of the node at the upper layer is 1, a route valid bit of the node at the current layer is 0100010111, the node identifier of the node at the upper layer and the route valid bit of the node at the current layer are spliced to obtain search information 1_0100010111 of the node ID1, hash calculation is carried out on the search information of the node ID1 to obtain a storage address of the node ID4, and the storage address of the node ID4 is used for storing a node identifier 4 of the node ID4 and an item identifier R2 of a valid route item; the method comprises the steps that a node at the upper layer is a node ID1, a node at the current layer is a node ID5, a node identifier of the node at the upper layer is 1, a route valid bit of the node at the current layer is 0100010000, the node identifier of the node at the upper layer is spliced with the route valid bit of the node at the current layer to obtain search information 1_0100010000 of the node ID1, hash calculation is carried out on the search information of the node ID1 to obtain a storage address of the node ID5, and the storage address of the node ID5 is used for storing a node identifier 5 of the node ID5 and an item identifier R3 of a valid route item; the upper layer node is node ID1, the current layer node is node ID6, the node identifier of the upper layer node is node ID1, the route valid bit of the current layer node is 0100010110, the node identifier of the upper layer node is spliced with the route valid bit of the current layer node to obtain the search information 1_0100010110 of the node ID1, the search information of the node ID1 is subjected to hash calculation to obtain the storage address of the node ID6, the storage address of the node ID6 is used for storing the node identifier 6 of the node ID6 and the item identifier R4 of the valid route entry, the upper layer node is node ID1, the current layer node is node ID7, the node identifier of the upper layer node is 1, the route valid bit of the current layer node is 010001101, the node identifier of the upper layer node is spliced with the route valid bit of the current layer node, obtaining search information 1_010001101 of the node ID1, performing hash calculation on the search information of the node ID1 to obtain a storage address of the node ID7, wherein the storage address of the node ID7 is used for storing a node identifier 7 of the node ID7 and an entry identifier R5 of an effective route entry.

The node of the upper layer is node ID3, the node of the current layer is node ID8, the node identifier of the upper layer is 3, the route valid bit of the node of the current layer is 1010000000, the node identifier of the upper layer and the route valid bit of the node of the current layer are spliced to obtain the search information 3_1010000000 of the node ID3, the search information of the node ID3 is subjected to hash calculation to obtain the storage address of the node ID8, and the storage address of the node ID8 is used for storing the node identifier 8 of the node ID8 and the route valid bit range [ 20,23 ] of the node of the lower layer.

The node at the upper layer is node ID8, the node at the current layer is node ID9, the node identifier of the node at the upper layer is 8, the route valid bit of the node at the current layer is 1010, the node identifier of the node at the upper layer and the route valid bit of the node at the current layer are spliced to obtain search information 8_1010 of the node ID8, hash calculation is carried out on the search information of the node ID8 to obtain a storage address of the node ID8, and the storage address of the node ID9 is used for storing the node identifier 9 of the node ID9 and an item identifier R6 of an effective route item; the method comprises the steps of enabling a node in the upper layer to be a node ID8, enabling a node in the current layer to be a node ID10, enabling a node identifier of the node in the upper layer to be 8, enabling a route valid bit of the node in the current layer to be 0011, enabling the node identifier of the node in the upper layer to be spliced with the route valid bit of the node in the current layer to obtain search information 8_0011 of the node ID8, carrying out hash calculation on the search information of the node ID8 to obtain a storage address of the node ID8, enabling the storage address of the node ID10 to be used for storing a node identifier 10 of the node ID10 and an item identifier R7 of an effective route item, enabling the node in the upper layer to be the node ID8, enabling the node identifier of the node in the current layer to be 8, enabling the route valid bit of the node in the current layer to be 0001, splicing the node identifier of the node in the upper layer with the route valid bit of the node in the current layer to obtain search information 8_0001, carrying out hash calculation on the search information of the node ID8 to obtain a storage address of the node ID11, and enabling the storage address of the node ID11 to be used for storing the node identifier 11 and the item identifier 11 of the effective route item R8.

It should be noted that, the nature of the hash algorithm is an algorithm that maps multiple bits to fewer bits, for example, after each number in 100-200 is hashed, it is represented by 0-10, and there is a possibility that the hash algorithm is adopted to calculate 101 to 5 and the hash algorithm is adopted to calculate 150 to 3. And because the hash algorithm is characterized by less numbers, hash conflicts may exist, for example, after the hash algorithm is adopted to process 151 and 189, the obtained results are 6, and after the hash algorithm is adopted to process node identifiers of a plurality of nodes, the same result, namely corresponding to the same node, may be obtained in the prefix tree, so that error inquiry is caused. In order to solve the hash conflict, the search information (key) of the hash algorithm comprises node ID_route valid bit, wherein the route valid bit is determined according to a to-be-supported route rule, and the rule is unchanged after the determination, but the node ID can be flexibly configured, and only the configured node ID and the route valid bit are required to be unique after combined calculation. For example, as the result of hash computation performed by 1_1001001 and 4_0100101, when the node is recreated, the node ID configured by 0100101 can be changed to 5, so that hash collision can be avoided.

502. And storing the node information of each layer of nodes corresponding to the at least one effective routing entry into the RAM based on the storage address of each layer of nodes corresponding to the at least one effective routing entry.

And after determining the storage address of each layer of node corresponding to at least one effective routing entry, storing the node information of each layer of node corresponding to the at least one effective routing entry into the RAM according to the storage address. Because different nodes have different storage addresses, and the storage addresses are obtained by hash calculation and possibly discontinuous, the node information of the nodes in the embodiment of the application can be stored in disorder without being stored in sequence as in the related technology, the storage of the node information is more flexible, and RAM resource pooling scheduling can be realized. When the effective route entry is updated, pre-stored RAM resources can be shared, the memory structure is more efficient, the RAM resource utilization rate is higher, large-scale updating of the content in the RAM is not needed, and the updating delay is smaller.

In another embodiment of the present application, for a branch node without a leaf node, the branch node may be combined with a node of a next layer, so as to save storage resources and increase a subsequent search speed. Taking any one of the above valid route entries as an example, if the number of next-layer nodes of the current-layer node is one and the next-layer node is not a leaf node, that is, the current-layer node is a branch node, merging the current-layer node with the next-layer node to obtain an updated next-layer node, wherein the route valid bit range of the updated next-layer node is obtained by splicing the route valid bit range of the current-layer node with the route valid bit range of the next-layer node, and then determining the storage address of the updated next-layer node according to the node identifier of the previous-layer node and the route valid bit of the current-layer node, and the storage address of the updated next-layer node is used for storing the node information of the updated next-layer node. Fig. 3 is a prefix tree constructed by using the method provided by the embodiment of the present application, it can be seen from an inspection of the tree structure shown in fig. 3 that the node ID3 is a branch node, and if the node ID3 has no leaf node, the node ID3 and the node ID8 may be combined to obtain an updated node ID8, the route effective range corresponding to the node ID8 before the update is [ 20,23 ], and the route effective range corresponding to the node ID8 after the update is [ 10,23 ]. After merging the node ID3 and the node ID8, a tree structure of the prefix tree shown in fig. 7 can be obtained.

Further, after the nodes in the prefix tree are combined, the calculation result of the hash algorithm changes, and the storage address of the updated node also changes. Before merging the node ID3 with the node ID8, referring to fig. 6, the node at the previous layer is the node ID0, the node at the current layer is the node ID3, the route valid bit of the node at the current layer is 1100000010, the search information of the node ID0 is obtained to be 0_1100000010, hash calculation is performed on the search information of the node ID0 to obtain the storage address of the node ID3, and the storage address of the node ID3 is used for storing the node identifier 3 of the node ID2 and the route valid bit range [ 10,19 ] of the node at the next layer. After the node ID3 and the node ID8 are combined, referring to fig. 8, the node at the upper layer is the node ID0, the node at the current layer is the node ID8, the search information of the node ID0 is still 0_1100000010, hash calculation is performed on the search information of the node ID0, and the storage address of the node ID8 is obtained, and the storage address of the node ID8 is used for storing the node identifier 8 of the node ID8 and the routing valid bit range [ 10,23 ] of the node at the next layer. Referring to fig. 6, when the previous layer node is node ID8 before node ID3 is combined with node ID8, the routing valid bit of the current layer node is 1010, 0011, or 0001, and when the previous layer node is node ID8 after node ID3 is combined with node ID8, referring to fig. 8, the routing valid bit of the current layer node is 1010000000_1010, 1010000000_0011, or 1010000000_0001.

The embodiment of the application provides a RAM-based search mechanism special for hardware acceleration, which builds a tree according to a mask level, solves the problems of large resource consumption, low storage efficiency, update delay and the like in the related art of building the tree, and particularly overcomes the defect of the RAM-based search mechanism in the table lookup efficiency for a scene with sparse distribution of the mask level of an effective routing entry. In addition, the hierarchical compression operation is performed on the basis of a mask hierarchical tree building mechanism, so that node overhead is further reduced. In addition, the jump between the nodes is completed through hash calculation, the nodes are insensitive to the storage sequence, and RAM resource pooling scheduling can be realized.

Any combination of the above optional solutions may be adopted to form an optional embodiment of the present application, which is not described herein.

The embodiment of the application provides a method for constructing a prefix tree, which is applied to the prefix tree constructed by the embodiment, and takes an electronic device as an example for executing the embodiment of the application, wherein the electronic device can be a device with a network routing function, such as a router and the like. Referring to fig. 9, the method provided by the embodiment of the application includes:

901. And when the target data packet is received, carrying out mask processing on a target address in the target data packet to obtain a target binary character string.

When receiving the target data packet, the router can analyze the target data packet to obtain a target address of the target data packet, and then mask the target address to obtain a target binary string corresponding to the target address. For example, the target address is 192.168.1.25, and the target address is masked, so that the target binary string is 11000000_10101000_00000001_00011001.

902. The target entry identification is looked up from RAM based on the route significance range indicated by each layer of the target binary string and prefix tree.

Specifically, when searching the target item identification from the RAM based on the route valid bit range indicated by each layer of the target binary string and the prefix tree, the method comprises the following steps:

9021. And intercepting a first character string positioned in the routing valid bit range indicated by the root node from the target binary character string according to the routing valid bit range indicated by the root node of the prefix tree.

For example, if the target binary string corresponding to the target address is 11000000_10101000_00000001_0001100 and the route valid bit range indicated by the root node is [ 0,9 ], the upper 10 bits of binary characters are intercepted from the target binary string, and the obtained first string is 1100000010.

9022. And determining a first storage address of the first node according to the node identification of the root node and the first character string.

Wherein the first node is the next layer node of the root node. After the first character string is obtained, the node identification of the root node and the first character string are spliced into the search information of the root node, and then hash calculation is carried out on the search information, so that the first storage address of the first node can be obtained. For example, the node identifier of the root node is 0, the first character string is 1100000010, the node identifier of the root node and the first character string are spliced to obtain the search information of the root node is 0_1100000010, and hash calculation is performed on the search information to obtain the first storage address of the first node.

9023. And acquiring the first node information corresponding to the first storage address from the RAM.

Based on the first storage address, first node information corresponding to the first storage address may be obtained from the RAM.

9024. And if the first node information does not comprise the entry identification of the valid route entry, acquiring the route valid bit range of the second node.

The second node is the node of the next layer of the first node. If the first node information does not include the entry identification of the valid route entry, it is indicated that the first node is a branch node, and there is no corresponding valid route entry, at this time, the route valid bit range of the second node may be obtained from the first node information, and then further searching is required.

In another possible implementation, if the first node information includes an entry identifier of a valid route entry, which indicates that the first node is a leaf node, the corresponding valid route entry may determine the entry identifier included in the first node information as the target entry identifier.

9025. And intercepting a second character string positioned in the routing valid bit range indicated by the second node from the target binary character string according to the routing valid bit range of the second node.

For example, if the target binary string corresponding to the target address is 11000000_10101000_00000001_0001100 and the route valid bit range indicated by the root node is [ 10,19 ], the binary character from the upper 11 bits to the upper 20 bits is intercepted from the target binary string, and the obtained second string is 1010000000.

9026. And processing the second character string according to the processing mode of the first character string until the target item identification is found out from the RAM.

After the second character string is obtained, the node identifier of the first node and the second character string can be spliced into the search information of the first node according to the processing mode of the first character string, then hash calculation is carried out on the search information, a second storage address of the second node can be obtained, second node information corresponding to the second storage address is obtained from the RAM, if the second node information comprises the item identifier of the effective route item, the item identifier contained in the second node information is determined to be the target item identifier, if the second node information does not comprise the item identifier of the effective route item, the route effective bit range of the third node is obtained, and then calculation is continued until the target item identifier is searched from the RAM. Of course, if the target entry identification cannot be obtained from the RAM, the method will return to the root node, and if the root node corresponds to the default route, the default route is used as the next-hop route entry.

903. And identifying the corresponding effective route entry as the next hop route entry of the target address.

Based on the target item identification obtained from the RAM, the effective route item corresponding to the target item identification can be used as the next-hop route item of the target address, and the target data packet is forwarded to the network equipment indicated by the next-hop route item, so that the forwarding of the data packet is completed.

For the above-mentioned process of searching for a route entry, taking the received packet with the destination address 192.168.1.25 as the destination address, the process of searching for the next-hop route entry of the destination address 192.168.1.25 from the route entries supported by the local router will be described in detail below, taking the prefix tree constructed based on the route entries supported by the local router as an example of the prefix tree shown in fig. 6, where the searching process is as follows:

First, a masking operation is performed on the destination address 192.168.1.25 to obtain a binary string 11000000_10101000_00000001_00011001 corresponding to the destination address 192.168.1.25. Then, starting from the root node, according to the routing valid bit range [0,9] indicated by the root node, acquiring a binary character string 1100000010 positioned in the routing valid bit range [0,9] from the binary character string, and then splicing the node identification 0 of the root node with the binary character string 1100000010 to obtain the search information 0_1100000010 of the root node.

Secondly, hash calculation is carried out on search information 0_1100000010 of a root node to obtain a storage address of the next node, node information of the next node is obtained from RAM based on the storage address, the node information comprises node identification 8 and route valid bit ranges [10,23] of the next node, then the route valid bit ranges [10,23] of the next node are obtained from binary character strings 11000000_10101000_00000001_00011001, a binary character string with 11 bits to 24 bits is obtained, 10100000000001 is obtained, the node identification 8 and the route valid bit 10100000000001 are spliced to obtain search information which is 8_10100000000001, hash calculation is carried out on the search information to obtain the storage address, the node information is obtained from the storage address to be node identification 11 and an item identification R8, and the fact that R8 is the longest prefix matching is achieved is explained, and therefore the valid route item corresponding to R8 is used as the next hop route item.

Referring to fig. 10, a schematic structural diagram of a prefix tree building apparatus according to an embodiment of the present application is provided, where the apparatus may be implemented by software, hardware, or a combination of both, and is all or a part of an electronic device, and the apparatus includes:

an obtaining module 1001, configured to obtain, according to the mask length of at least one valid routing entry, the number of layers of the prefix tree and a routing valid bit range of each layer;

A determining module 1002, configured to determine, according to a routing valid bit range of each layer of the prefix tree and the binary string obtained after the processing of the at least one valid routing entry mask, a node of each layer of the prefix tree, where the node of each layer of the prefix tree includes a leaf node and a branch node, the leaf node corresponds to one valid routing entry, and the branch node is used to jump to a leaf node of the same layer or a branch node of a next layer;

and a connection module 1003, configured to connect, from a root node, a node corresponding to each valid route entry layer by layer until a leaf node, to obtain the prefix tree, where the root node corresponds to a valid route entry with a null character or a mask length of 0.

In another embodiment of the present application, the obtaining module is configured to determine the number of non-zero mask lengths in the at least one valid routing entry as the number of layers of the prefix tree, order the mask lengths of the at least one valid routing entry in order from small to large, and determine a mask length range between two adjacent layers as a routing valid bit range of one layer.

In another embodiment of the present application, the determining module is configured to intercept, from the binary strings obtained after the processing of the at least one valid route entry mask, binary strings located within a length range indicated by the route valid bit range of each layer according to the route valid bit range corresponding to each layer to obtain at least one binary string, and take one binary string corresponding to each layer as a node to obtain a node of each layer of the prefix tree.

In another embodiment of the present application, the apparatus further comprises:

And the merging module is used for merging the current layer node with the next layer node to obtain an updated next layer node if the number of the next layer nodes of the current layer node is one and the next layer node is not a leaf node, wherein the updated routing valid bit range of the next layer node is obtained by splicing the routing valid bit range of the current layer node with the routing valid bit range of the next layer node.

In another embodiment of the present application, each node included in the prefix tree has a different node identification, and the apparatus further includes:

The determining module is further configured to determine, for a node corresponding to any one valid routing entry in the prefix tree, a storage address of the current layer node in the RAM according to a node identifier of a previous layer node and a routing valid bit of the current layer node, where the storage address of the current layer node is used to store node information of the current layer node, and the node information of the current layer node includes the node identifier of the current layer node and an entry identifier of the valid routing entry or a routing valid bit range of a next layer node;

And the storage module is used for storing the node information of each layer of node corresponding to the at least one effective routing entry into the RAM based on the storage address of each layer of node corresponding to the at least one effective routing entry.

The determining module is further configured to determine a storage address of the current layer node in the RAM according to the node identifier of the previous layer node and the route valid bit of the current layer node, where the determining module includes:

The splicing module is used for splicing the node identification of the previous layer of nodes and the route valid bit of the current layer of nodes to obtain the search information of the previous layer of nodes;

And the calculation module is used for carrying out hash calculation on the search information of the previous layer of nodes to obtain the storage address of the current layer of nodes.

Referring to fig. 11, a schematic structural diagram of a routing entry lookup apparatus according to an embodiment of the present application is provided, where the prefix tree constructed in the foregoing embodiment of the present application may be implemented by software, hardware, or a combination of both, and the apparatus may be all or a part of an electronic device, and includes:

An obtaining module 1101, configured to, when a target data packet is received, perform mask processing on a target address in the target data packet, to obtain a target binary string;

A lookup module 1102, further configured to, based on the route valid bit ranges indicated by each layer of the target binary string and the prefix tree, lookup a target entry identifier from the RAM, where the target entry identifier is an entry identifier of a valid route entry that matches the prefix of the target binary string longest;

A determining module 1103 is configured to determine the valid route entry corresponding to the destination entry as the next hop route entry of the destination address.

In another embodiment of the present application, a search module 1102 is configured to intercept a first string located in a route valid bit range indicated by a root node of the prefix tree from the target binary string according to the route valid bit range indicated by the root node, determine a first storage address of the first node, where the first node is a node of a next layer of the root node, acquire first node information corresponding to the first storage address from the RAM, acquire a route valid bit range of a second node, where the second node is a node of a next layer of the first node, according to the route valid bit range of the second node, intercept a second string located in the route valid bit range indicated by the second node from the target binary string, and process the second string from the RAM according to a manner of processing the first string until the second string is processed by processing the first string.

In another embodiment of the present application, the determining module 1103 is further configured to determine the entry identifier included in the first node information as the target entry identifier if the first node information includes an entry identifier of a valid routing entry.

Fig. 12 shows a block diagram of an electronic device 1200 according to an exemplary embodiment of the application. In general, the electronic device 1200 includes a processor 1201 and a memory 1202.

The processor 1201 may be implemented in at least one hardware form of DSP (DIGITAL SIGNAL Processing), FPGA (Field-Programmable gate array), PLA (Programmable Logic Array ). Processor 1201 may also include a main processor, which is a processor for processing data in a wake-up state, and a coprocessor, which is a low-power processor for processing data in a standby state. In some embodiments, the processor 1201 may integrate a GPU (Graphics Processing Unit, image processor) for rendering and drawing of content required to be displayed by the display screen. In some embodiments, the processor 1201 may also include an artificial intelligence processor for processing computing operations related to machine learning.

Memory 1202 may include one or more computer-readable storage media, which may be non-transitory computer-readable storage media, such as CD-ROM (Compact Disc Read-Only Memory), ROM, RAM (Random Access Memory ), magnetic tape, floppy disk, optical data storage device, and the like. The computer readable storage medium stores at least one computer program, which when executed, is capable of implementing the prefix tree construction method or the route entry lookup method.

Of course, the electronic device described above may necessarily also include other components, such as input/output interfaces, communication components, and the like. The input/output interface provides an interface between the processor and a peripheral interface module, which may be an output device, an input device, etc. The communication component is configured to facilitate wired or wireless communication between the electronic device and other devices, and the like.

Those skilled in the art will appreciate that the structure shown in fig. 12 is not limiting of the electronic device 1200 and may include more or fewer components than shown, or may combine certain components, or may employ a different arrangement of components.

The embodiment of the application provides a computer readable storage medium, wherein at least one computer program is stored in the computer readable storage medium, and the at least one computer program can realize the method for constructing the prefix tree or the method for searching the routing entry when being executed by a processor.

Embodiments of the present application provide a computer program product comprising a computer program which, when executed by a processor, enables the above-described prefix tree construction method, or route entry lookup method, to be implemented.

It will be clear to those skilled in the art that, for convenience and brevity of description, specific working procedures of the above-described systems, apparatuses and units may refer to corresponding procedures in the foregoing method embodiments, which are not repeated herein.

The foregoing embodiments are merely for illustrating the technical solution of the present application, but not for limiting the same, and although the present application has been described in detail with reference to the foregoing embodiments, it will be understood by those skilled in the art that modifications may be made to the technical solution described in the foregoing embodiments or equivalents may be substituted for parts of the technical features thereof, and that such modifications or substitutions do not depart from the spirit and scope of the technical solution of the embodiments of the present application in essence.

Claims

1. A method for constructing a prefix tree, characterized in that the method comprises:

Determine the number of non-zero mask lengths in at least one valid routing entry as the number of layers of the prefix tree;

Sort the mask lengths of the at least one valid routing entry in ascending order, and determine the mask length range between two adjacent layers as the routing valid bit range of one layer;

Determine the nodes of each layer of the prefix tree according to the route valid bit range of each layer of the prefix tree and the binary string obtained after mask processing of the at least one valid route entry, wherein the nodes of each layer of the prefix tree include leaf nodes and branch nodes, the leaf nodes correspond to a valid route entry, and the branch nodes are used to jump to the leaf nodes of the same layer or the branch nodes of the next layer;

Starting from the root node, the nodes corresponding to each valid routing entry are connected layer by layer until the leaf node, to obtain the prefix tree, wherein the root node corresponds to a valid routing entry with a null character or a mask length of 0.

2. The method according to claim 1, characterized in that the step of determining the nodes at each layer of the prefix tree according to the route valid bit range at each layer of the prefix tree and the binary string obtained after the mask operation of the at least one valid route entry comprises:

According to the route valid bit range corresponding to each layer, from the binary string obtained after the mask processing of the at least one valid route entry, intercept the binary string within the length range indicated by the route valid bit range of each layer to obtain at least one binary string;

A binary string corresponding to each layer is taken as a node to obtain the node of each layer of the prefix tree.

3. The method according to claim 1, characterized in that the method further comprises:

If the number of next-layer nodes of the current-layer node is one, and the next-layer node is not a leaf node, the current-layer node and the next-layer node are merged to obtain an updated next-layer node, and the routing valid bit range of the updated next-layer node is obtained by concatenating the routing valid bit range of the current-layer node and the routing valid bit range of the next-layer node.

4. The method according to any one of claims 1 to 3, characterized in that each node included in the prefix tree has a different node identifier, and the method further comprises:

For any node corresponding to a valid routing entry in the prefix tree, a storage address of the current layer node in a random access memory RAM is determined according to a node identifier of a previous layer node and a routing valid bit of a current layer node, wherein the storage address of the current layer node is used to store node information of the current layer node, wherein the node information of the current layer node includes a node identifier of the current layer node, and an entry identifier of the valid routing entry or a routing valid bit range of a next layer node, wherein the routing valid bit refers to a binary string intercepted from a binary string corresponding to at least one valid routing entry based on a routing valid bit range of each layer;

Based on the storage address of each layer of nodes corresponding to the at least one valid routing entry, the node information of each layer of nodes corresponding to the at least one valid routing entry is stored in the RAM.

5. The method according to claim 4, characterized in that the step of determining the storage address of the current layer node in the random access memory RAM according to the node identifier of the previous layer node and the route valid bit of the current layer node comprises:

Concatenate the node identifier of the previous layer node and the route valid bit of the current layer node to obtain the search information of the previous layer node;

A hash calculation is performed on the search information of the previous layer node to obtain the storage address of the current layer node.

6. A method for searching a routing entry, characterized in that the method applies the prefix tree constructed according to any one of claims 1 to 5, and the method comprises:

When a target data packet is received, a target address in the target data packet is masked to obtain a target binary string;

Based on the target binary string and the route valid bit range indicated by each layer of the prefix tree, searching the RAM for a target entry identifier, the target entry identifier being the entry identifier of the valid route entry that has the longest match with the prefix of the target binary string;

The valid routing entry corresponding to the target entry identifier is determined as the next-hop routing entry of the target address.

7. The method according to claim 6, characterized in that searching the target entry identifier from the RAM based on the target binary string and the route valid bit range indicated by each layer of the prefix tree comprises:

According to the route valid bit range indicated by the root node of the prefix tree, intercepting from the target binary string a first string located within the route valid bit range indicated by the root node;

Determine a first storage address of a first node according to the node identifier of the root node and the first character string, where the first node is a node in a next layer of the root node;

Obtaining first node information corresponding to the first storage address from the RAM;

If the first node information does not include an entry identifier of a valid routing entry, obtaining a routing valid bit range of a second node, where the second node is a node in a next layer of the first node;

According to the routing valid bit range of the second node, intercepting a second character string located in the routing valid bit range indicated by the second node from the target binary character string;

The second character string is processed in the same manner as the first character string until a target entry identifier is found in the RAM.

8. The method according to claim 7, characterized in that the method further comprises:

If the first node information includes an entry identifier of a valid routing entry, the entry identifier included in the first node information is determined as the target entry identifier.

9. An electronic device, characterized in that it includes a processor and a memory; the memory stores at least one program code; the at least one program code is used to be called and executed by the processor to implement the prefix tree construction method described in any one of claims 1 to 5, or the routing entry search method described in any one of claims 6 to 8.

10. A computer-readable storage medium, characterized in that at least one computer program is stored in the computer-readable storage medium, and when the at least one computer program is executed by a processor, it can implement the prefix tree construction method described in any one of claims 1 to 5, or the routing entry search method described in any one of claims 6 to 8.

11. A computer program product, characterized in that the computer program product comprises a computer program, and when the computer program is executed by a processor, it can implement the method for constructing a prefix tree as described in any one of claims 1 to 5, or the method for searching a routing entry as described in any one of claims 6 to 8.