CN119011470A

CN119011470A - Route searching method and device

Info

Publication number: CN119011470A
Application number: CN202310572888.5A
Authority: CN
Inventors: 陈佳杰; 黄硕; 邵志远; 金海�
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2023-05-19
Filing date: 2023-05-19
Publication date: 2024-11-22

Abstract

The present application discloses a routing search method and device, belonging to the field of IP technology. The method comprises: obtaining the destination network protocol IP address of a data packet to be forwarded; obtaining a routing information set for performing routing search, the routing information set indicating the correspondence between the prefix item of the IP address and the next hop information, the routing information set including N routing information subsets, the N routing information subsets being obtained based on the length distribution law of the prefix item and the data volume of the prefix item, N being an integer greater than 1 and less than 6; based on the destination IP address and the routing information set, sequentially executing N search stages in the search pipeline to obtain the destination next hop information indicating forwarding of the data packet, the N search stages corresponding to the N routing information subsets one by one, and any search stage being used to match the destination IP address with the prefix item in the routing information subset corresponding to any search stage. The present application can improve the search performance.

Description

Route searching method and device

Technical Field

The present application relates to the field of IP technologies, and in particular, to a method and apparatus for searching a route.

Background

The route searching is a process of searching a route table in a route node according to the destination internet protocol (internet protocol, IP) address of the message to obtain the next hop information of the message. The route searching algorithm is one of the most core basic algorithms in the network routing scene, and is used for comparing the IP address of the data packet to be forwarded with the IP address prefix stored in the routing table so as to map to the next hop information.

Currently, a route search algorithm capable of meeting the high-speed network and the ultra-large scale route scene is needed in the future.

Disclosure of Invention

The application provides a route searching method and device. The application can improve the overall searching performance, so that the route searching method can meet the high requirements on the searching performance and the storage capacity under the high-speed network environment and the ultra-large scale route. The technical scheme provided by the application is as follows:

In a first aspect, the present application provides a route searching method. The method comprises the following steps: acquiring a destination network protocol (IP) address of a data packet to be forwarded; acquiring a routing information set for route searching, wherein the routing information set indicates the corresponding relation between a prefix item of an IP address and next hop information, the routing information set comprises N routing information subsets, the N routing information subsets are obtained based on the length distribution rule of the prefix item and the data quantity division of the prefix item, and N is an integer which is more than 1 and less than 6; and based on the destination IP address and the route information set, N search stages in the search pipeline are sequentially executed to obtain destination next-hop information indicating forwarding of the data packet, the N search stages are in one-to-one correspondence with the N route information subsets, and any one search stage is used for matching the destination IP address with a prefix item in the route information subset corresponding to any one search stage.

By dividing the routing information set into a plurality of routing information subsets based on the length distribution rule of the prefix items and the data volume of the prefix items, the prefix items can be ensured to be searched orderly in the routing searching stage. The division mode also provides basis for storage implementation of the routing information subsets, considering that the size of the number of the routing information subsets can correspondingly influence the storage capacity. And by dividing the set of routing information into a plurality of subsets of routing information in this division, and matching the destination IP address in any one of the lookup stages of the lookup pipeline with the prefix entries in the subset of routing information corresponding to that lookup stage, since this division reduces the total number of subsets of routing information, and each searching stage needs to read the route information subset corresponding to the stage from the memory, so that the access times to the memory can be reduced, the route searching time delay is reduced, the purpose of improving the searching performance is achieved, and the method is beneficial to coping with the route searching requirement under the high-speed network.

In one implementation, based on a destination IP address and a set of routing information, N lookup stages in a lookup pipeline are sequentially performed to obtain destination next-hop information indicating forwarding of a packet, including the following stages:

In the first searching stage, the k 1-bit of the target IP address is matched with a prefix item included in a first routing information subset corresponding to the first searching stage, when the first prefix item matched with the k 1-bit exists in the first routing information subset, if a second prefix item to be matched taking the first prefix item as a prefix exists in the prefix item included in a second routing information subset corresponding to the second searching stage, information of the second prefix item to be matched is provided for the second searching stage, and if the second prefix item to be matched does not exist in the prefix item included in the second routing information subset, the first next-hop information corresponding to the first prefix item is used as the next-hop information of the target, and k1 is the range width of the length of the prefix item in the first routing information subset.

In the first searching stage of the second to N-1 searching stages, the Imin to Imax bits of the destination IP address are matched with all I to-be-matched prefix items included in the I routing information subset corresponding to the first searching stage, when the destination I prefix item matched with the Imin to Imax bits exists in all the I to-be-matched prefix items, if the I+1 to-be-matched prefix item taking the destination I prefix item as a prefix exists in the prefix items included in the I+1 routing information subset corresponding to the first searching stage, the I+1 to-be-matched prefix item information is provided for the I+1 searching stage, if the I+1 to-be-matched prefix item does not exist in the prefix items included in the I+1 routing information subset, the I next hop information corresponding to the destination I to-be-matched prefix item is used as the next hop information of the destination, I is an integer which is larger than 1 and smaller than N, the Imin is the minimum length of the prefix item included in the I routing information subset is the maximum length of the prefix item included in the I+1 to be-to-be-matched prefix item.

In the N-th searching stage, the Nmin-Nmax bits of the destination IP address are matched with all N-th prefix items to be matched included in the N-th routing information subset corresponding to the N-th searching stage, when the N-th prefix items matched with the Nmin-Nmax bits exist in all the N-th prefix items to be matched, the N-th next-hop information corresponding to the N-th prefix items is used as the destination next-hop information, nmin is the minimum length of the prefix items included in the N-th routing information subset, and Nmax is the maximum length of the prefix items included in the N-th routing information subset.

Optionally, based on the destination IP address and the set of routing information, performing any one of N lookup stages in the lookup pipeline, including: acquiring a storage address of routing information required by any one searching stage; reading the routing information from the memory based on the memory address, wherein the process of reading the routing information from the memory based on the memory address comprises: the method comprises the steps that an address reading process of a storage address is sent to a memory and a data reading process of the storage memory based on storage address feedback route information is received, wherein the address reading process and the data reading process are realized through mutually independent memory access channels; and matching the destination IP address with the prefix item in the routing information subset corresponding to any one of the searching stages based on the routing information.

That is, the memory access logic module is split into a read address channel and a read data channel which are independent of each other, and the read address channel is used for sending a memory address of the content to be read to the memory, namely, realizing the read address process. The read data channel receives the feedback content of the memory based on the memory address, namely, the read data process is realized. The read address channel and the read data channel are mutually independent: after the read address channel sends a storage address to the memory, the read data channel can continue to send the next storage address to the memory without waiting for the read data channel to return the data stored in the storage address. In this way, the time delay of multiple data reading by the memory access logic module can be reduced.

In one implementation scenario, the method is applied to a route lookup chip configured with an on-chip memory and an off-chip memory, the on-chip memory storing a subset of route information having a total data amount less than or equal to a data amount threshold, and the off-chip memory storing a subset of route information having a total data amount greater than the data amount threshold. The memory used for storing the route information subset is determined according to the specific condition of the route information subset, so that on the basis of meeting storage requirements, factors such as access delay, memory cost and bandwidth can be comprehensively considered, on the basis of ensuring route searching efficiency, the cost of route searching is controlled, and the method is beneficial to coping with the storage capacity requirements under a large or even ultra-large-scale route scene.

In one implementation, any subset of routing information includes bitmap information and address offset block information, any on-chip memory stores address offset information or bitmap information having a total data amount less than or equal to a data amount threshold, and any off-chip memory stores bitmap information having a total data amount greater than the data amount threshold.

In one implementation, the off-chip memory is a memory having a plurality of channels, the plurality of channels corresponding to a plurality of lookup pipelines, any of the plurality of channels being used to provide routing information to the corresponding pipeline. Therefore, the multi-access channel can be utilized to realize high bandwidth and reduce access delay, and the purpose of further improving the route searching efficiency is achieved.

Optionally, the plurality of channels each store a full amount of routing information stored by the off-chip memory, or the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory.

When the multiple channels respectively store the full routing information stored in the off-chip memory, after the multiple routing information subsets are distributed to the multiple access channels, when the pipeline corresponding to each access channel in the multiple access channels performs route searching, only the routing searching task corresponding to the routing information subset stored in the corresponding access channel is required to be processed, the routing information subsets stored in other access channels are not required to be accessed, and the route searching can be independently performed, so that the route searching efficiency is further ensured.

In one implementation, the portion of the routing information stored by the plurality of channels is partitioned based on prefix bits of a specified number of bits. By dividing the routing information subsets according to the prefix bits as indexes, a plurality of disjoint routing information subsets can be obtained, and the independence of data division is ensured.

Optionally, when the plurality of channels each store a portion of the full amount of routing information stored in the off-chip memory, before sequentially performing N lookup stages in the lookup pipeline based on the destination IP address and the set of routing information to obtain destination next-hop information indicating forwarding of the data packet, the method further includes: and determining a target searching pipeline for carrying out route searching on the target IP address, and providing the target IP address for the target searching pipeline.

In one implementation scenario, the length range of the prefix item of the routing information set is 1 to 32 bits, the routing information set includes a first routing information subset, a second routing information subset, a third routing information subset, and a fourth routing information subset, and the length ranges of the prefix items of the first routing information subset, the second routing information subset, the third routing information subset, and the fourth routing information subset are respectively: 1 to 8 bits, 9 to 16 bits, 17 to 24 bits, and 25 to 32 bits.

At this time, the total number of prefix items included in the first routing information subset, the total number of prefix items included in the second routing information subset, and the total number of prefix items included in the fourth routing information subset are all smaller than a preset total number, and the total number of prefix items included in the third routing information subset is larger than or equal to the preset total number.

Correspondingly, any route information subset comprises bitmap information and address offset block information, the map information and the address offset block information of the first route information subset are respectively stored in two on-chip memories corresponding to the first route information subset, the map information and the address offset block information of the second route information subset are respectively stored in two on-chip memories corresponding to the second route information subset, the map information of the third route information subset is stored in an off-chip memory corresponding to the third route information subset, the address offset block information of the third route information subset is stored in an on-chip memory corresponding to the third route information subset, and the map information and the address offset block information of the fourth route information subset are respectively stored in two on-chip memories corresponding to the fourth route information subset.

In a second aspect, the present application provides a route searching device. The device comprises: the acquisition module is used for acquiring a destination network protocol (IP) address of a data packet to be forwarded; the acquisition module is further used for acquiring a routing information set for carrying out routing searching, the routing information set indicates the corresponding relation between the prefix item of the IP address and the next hop information, the routing information set comprises N routing information subsets, the N routing information subsets are obtained by dividing the N routing information subsets based on the length distribution rule of the prefix item and the data volume of the prefix item, and N is an integer which is more than 1 and less than 6; the processing module is used for sequentially executing N searching stages in the searching pipeline based on the destination IP address and the routing information set to obtain destination next-hop information for indicating forwarding of the data packet, the N searching stages are in one-to-one correspondence with the N routing information subsets, and any one searching stage is used for matching the destination IP address with a prefix item in the routing information subset corresponding to any one searching stage.

Optionally, the processing module is specifically configured to: in a first searching stage, matching the k 1-bit of the target IP address with a prefix item included in a first routing information subset corresponding to the first searching stage, when the first prefix item matched with the k 1-bit exists in the first routing information subset, if a second prefix item to be matched taking the first prefix item as a prefix exists in a prefix item included in a second routing information subset corresponding to the second searching stage, providing information of the second prefix item to be matched for the second searching stage, and if the second prefix item to be matched does not exist in the prefix item included in the second routing information subset, taking first next-hop information corresponding to the first prefix item as target next-hop information, wherein k1 is the range width of the length of the prefix item in the first routing information subset; in an I searching stage in the second to N-1 searching stages, matching Imin to Imax bits of a target IP address with all I to-be-matched prefix items included in an I routing information subset corresponding to the I searching stage, when the target I prefix item matched with the Imin to Imax bits exists in all the I to-be-matched prefix items, if the I+1 to-be-matched prefix item taking the target I prefix item as a prefix exists in the prefix items included in the I+1 routing information subset corresponding to the I+1 searching stage, providing information of the I+1 to-be-matched prefix item for the I+1 searching stage, and if the I+1 to-be-matched prefix item does not exist in the prefix items included in the I+1 routing information subset, taking the I next hop information corresponding to the target I to be the target I prefix item as the next hop information, wherein I is an integer which is larger than 1 and smaller than N, and Imin is the minimum length of the prefix item included in the I to be the I routing information subset is the maximum length of the prefix item included in the I+1 to be the prefix item; in the N-th searching stage, the Nmin-Nmax bits of the destination IP address are matched with all N-th prefix items to be matched included in the N-th routing information subset corresponding to the N-th searching stage, when the N-th prefix items matched with the Nmin-Nmax bits exist in all the N-th prefix items to be matched, the N-th next-hop information corresponding to the N-th prefix items is used as the destination next-hop information, nmin is the minimum length of the prefix items included in the N-th routing information subset, and Nmax is the maximum length of the prefix items included in the N-th routing information subset.

Optionally, the processing module is specifically configured to: acquiring a storage address of routing information required by any one searching stage; reading the routing information from the memory based on the memory address, wherein the process of reading the routing information from the memory based on the memory address comprises: the method comprises the steps that an address reading process of a storage address is sent to a memory and a data reading process of the storage memory based on storage address feedback route information is received, wherein the address reading process and the data reading process are realized through mutually independent memory access channels; and matching the destination IP address with the prefix item in the routing information subset corresponding to any one of the searching stages based on the routing information.

Optionally, the device is applied to a route searching chip, the route searching chip is configured with an on-chip memory and an off-chip memory, the on-chip memory stores a route information subset with total data quantity smaller than or equal to a data quantity threshold, and the off-chip memory stores a route information subset with total data quantity larger than the data quantity threshold.

Optionally, any subset of the routing information includes bitmap information and address offset block information, any on-chip memory stores the address offset information or bitmap information with a total data amount less than or equal to a data amount threshold, and any off-chip memory stores bitmap information with a total data amount greater than the data amount threshold.

Optionally, the off-chip memory is a memory having a plurality of channels, the plurality of channels corresponding to a plurality of lookup pipelines, any of the plurality of channels being configured to provide routing information to the corresponding pipeline.

Optionally, the partial routing information stored by the plurality of channels is partitioned based on prefix bits of a specified number of bits.

Optionally, when the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory, the processing module is further configured to: and determining a target searching pipeline for carrying out route searching on the target IP address, and providing the target IP address for the target searching pipeline.

Optionally, the length range of the prefix item of the routing information set is 1 to 32 bits, the routing information set includes a first routing information subset, a second routing information subset, a third routing information subset and a fourth routing information subset, and the length ranges of the prefix items of the first routing information subset, the second routing information subset, the third routing information subset and the fourth routing information subset are respectively: 1 to 8 bits, 9 to 16 bits, 17 to 24 bits, and 25 to 32 bits.

Optionally, the total number of prefix items included in the first routing information subset, the total number of prefix items included in the second routing information subset, and the total number of prefix items included in the fourth routing information subset are all smaller than a preset total number, and the total number of prefix items included in the third routing information subset is greater than or equal to the preset total number.

Optionally, the map information and the address offset block information of the first routing information subset are respectively stored in two on-chip memories corresponding to the first routing information subset, the map information and the address offset block information of the second routing information subset are respectively stored in two on-chip memories corresponding to the second routing information subset, the map information of the third routing information subset is stored in an off-chip memory corresponding to the third routing information subset, the address offset block information of the third routing information subset is stored in an on-chip memory corresponding to the third routing information subset, and the map information and the address offset block information of the fourth routing information subset are respectively stored in two on-chip memories corresponding to the fourth routing information subset.

In a third aspect, the application provides a computing device comprising a memory storing program instructions and a processor executing the program instructions to perform the method provided in the first aspect of the application and any one of its possible implementations.

In a fourth aspect, the present application provides a computer readable storage medium, the computer readable storage medium being a non-volatile computer readable storage medium comprising program instructions which, when run on a computing device, cause the computing device to perform the method provided in the first aspect of the present application and any one of its possible implementations.

In a fifth aspect, the application provides a computer program product comprising instructions which, when run on a computer, cause the computer to perform the method provided in the first aspect of the application and any one of its possible implementations.

Drawings

FIG. 1 is a schematic illustration of a RIB provided by an embodiment of the present application;

FIG. 2 is a schematic diagram of a binary prefix tree provided by an embodiment of the present application;

Fig. 3 is a schematic structural diagram of a communication system according to an embodiment of the present application;

fig. 4 is a distribution rule of prefix entries in a routing table according to an embodiment of the present application;

FIG. 5 is a schematic diagram of a first routing sub-table, a second routing sub-table, a third routing sub-table, and a fourth routing sub-table, which may be represented by prefix sub-trees, according to an embodiment of the present application;

FIG. 6 is a schematic diagram of a data structure of the prefix tree node shown in FIG. 4 according to an embodiment of the present application;

FIG. 7 is a schematic diagram of a prefix sub-tree provided by an embodiment of the present application;

FIG. 8 is a schematic diagram of a memory implementation of a lookup pipeline provided by an embodiment of the present application;

FIG. 9 is a schematic diagram of a storage implementation of a first lookup stage provided by an embodiment of the present application;

FIG. 10 is a schematic diagram of a storage implementation of a second lookup stage provided by an embodiment of the present application;

FIG. 11 is a schematic diagram of a third search stage storage implementation provided by an embodiment of the present application;

FIG. 12 is a schematic diagram of a fourth lookup stage storage implementation provided by an embodiment of the present application;

FIG. 13 is a schematic diagram of a plurality of lookup pipelines provided by an embodiment of the present application;

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

FIG. 15 is a flowchart of another route lookup method provided by an embodiment of the present application;

FIG. 16 is a schematic diagram of a process for finding a pipeline according to an embodiment of the present application;

FIG. 17 is a schematic diagram of a search stage according to an embodiment of the present application;

FIG. 18 is a schematic diagram of an internal implementation of a lookup stage provided by an embodiment of the present application;

FIG. 19 is a schematic diagram of a storage capacity analysis model provided by an embodiment of the present application;

Fig. 20 is a schematic diagram of a change of access bandwidth along with the number of access channels of an HBM according to an embodiment of the present application;

Fig. 21 is a schematic diagram of a route searching device according to an embodiment of the present application;

FIG. 22 is a schematic diagram of a computing device according to an 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.

For ease of understanding, the following description first refers to the technology and the background to which embodiments of the present application relate.

The main task of the routing node is to forward the IP message, i.e. forward the message arriving at the input port of the routing node to the correct output port according to the destination IP address in the message header.

The route searching is a process of searching a route table in a route node according to the destination IP address of the message to obtain the next hop information of the message. The next hop information typically indicates a port number of a port that forwards the packet. The route searching algorithm is one of the most core basic algorithms in the network routing scene, and is used for comparing the IP address of the data packet to be forwarded with the IP address prefix stored in the routing table so as to map to the next hop information. Route lookup algorithms have a wide range of application scenarios in computer networks. The routing node may be not only a router, but also a switch, a firewall, a network processor (network processor, NP), a smart network card (smart network INTERFACE CARD, smartNIC), a data processing unit (data process unit, DPU), and other network devices. For example, traditional application scenarios are prefix matching in backbone routers or switches, address filtering in firewalls, etc. In the emerging application scenarios in the fields of acceleration data centers, cloud computing and the like, the intelligent network card or the data processing unit can optimize and accelerate the route searching algorithm, so that the rapid forwarding of the network data packet is realized.

The routing table is stored in a routing node such as a router and is used for recording information of route forwarding. The routing table stores routes and metrics associated with the routes, indicating correspondence of prefix entries of the IP addresses to next hop information. The prefix item of the IP address is an address portion corresponding to a network portion thereof, i.e., a network address of the IP address, which indicates a network number of one network connected to the Internet (Internet). The routing table is a generic name of a routing information table (routing information base, RIB) and a forwarding information table (forward information base, FIB). The RIB is used to decide routing and the FIB is used to forward the packet. As shown in FIG. 1, the RIB IS constructed from various routing procedures based on information provided by routing protocols, such as the open shortest Path first (open shortest PATH FIRST, OSPF) routing protocol, intermediate System-to-intermediate System (INTERMEDIATE SYSTEM-to-INTERMEDIATE SYSTEM, IS-IS) routing protocol, border gateway protocol (border gateway protocol, BGP) tables, and the like. In general, the routing node selects the best route from all the route information of the RIB, copies them to the FIB, and guides the forwarding of the packet by the FIB. It follows that the routing node does not match the destination IP address in the RIB but in the FIB when performing the route lookup algorithm, and therefore the routing tables referred to herein are FIBs.

Routing tables come in a variety of forms. In one implementation, as shown in FIG. 2, all elements in the routing table are represented in the form of a binary prefix tree based on prefix entries. The prefix tree, also called a word look-up tree (trie) or dictionary tree, is a tree-like structure typically used for longest prefix matching, statistics, ordering and storing a large number of strings. A binary prefix tree is a special form of binary tree, default route 0.0....0.0 is the root node of the binary prefix tree, starting from the root node, each node in the tree divides into two child nodes according to prefix bits 0 and 1, the child node divided according to the prefix bit 0 represents that the prefix value of the current bit is 0, and the child node divided according to the prefix bit 1 represents that the prefix value of the current bit is 1. Each child node and all nodes arranged before the child node represent a prefix item. When a child node is accessed from the root node of the binary prefix tree, prefix values represented by all nodes passing through in the way are arranged in the order from left to right, and the obtained result is the prefix item represented by the child node and all nodes arranged in front of the child node. For example, the access starts from the root node of the binary prefix tree shown in fig. 2, and sequentially passes through the left branch of the second layer, the left branch of the third layer and the right branch of the fourth layer in the binary prefix tree, prefix values represented by nodes corresponding to the three branches are respectively 0, 0 and 1, prefix items represented by the three branches are 001, and a node corresponding to the prefix item is node S1 in fig. 2. Fig. 2 is a schematic diagram of a prefix tree of a routing table, and a schematic diagram of an actual routing table is more complex. Also, fig. 2 does not show all child nodes of a partial node.

The basic task of the routing table lookup algorithm is the longest prefix match (longest prefix match, LPM). The longest prefix match refers to when a route is selected for a destination IP address of a packet, because the routing table includes a plurality of entries, each entry indicates an IP address range represented by a prefix item and a next hop, if an IP address of a packet can match a plurality of prefix items, an entry corresponding to a prefix item having the longest length among the plurality of prefix items is the most accurate entry for forwarding the packet, and the entry is used as a matching item and the next hop is determined. In the longest prefix route, the next hop index of the packet is given by the entry corresponding to the longest prefix that matches its destination IP address.

For example, the longest prefix match is illustrated with the destination IP address= 01011100 of the packet. As shown in table 1, during route lookup, each bit of the destination IP address is matched from front to back, and the destination IP address is matched with all entries in table 1 to obtain a plurality of prefix entries P1, P3 and P5, each of which is matched with the destination IP address, the prefix length of P1 is 1, the prefix length of P3 is 3, and the prefix length of P5 is 5, so that P5 is the longest prefix match of destination IP address= 01011100, and at this time, the next hop port 3 corresponding to P5 is determined as the next hop port of the data packet.

TABLE 1

Numbering device	Prefix item	Next hop port number
			P1	0*	0
P2	000*	1
			P3	010*	2
P4	01001*	3
			P5	01011*	4
P6	011*	5
			P7	110*	6
P8	111*	7

The fourth version of the internet communication protocol (internet protocol version, ipv 4) is the first widely used, forming the base protocol for today's internet technology.

The memory inside the chip is called on-chip memory. The memory that extends off-chip is referred to as off-chip memory. Compared with the off-chip memory, the on-chip memory has the advantages of high access speed, low access delay, small capacity and high cost. For example, the cache of the central processing unit (central processing unit, CPU), the static random access memory (static random access memory, SRAM), and the ternary content addressable memory (ternary content addressable memory, TCAM) are all on-chip memories. Considering the storage capacity requirement for very large scale routing in the future routing scenario, the on-chip memory can meet the existing requirement for route searching speed, but has limited storage capacity and performance expansion, and has higher and higher cost in real router and DPU deployment.

Although the off-chip memory has large storage capacity and low cost, the storage bandwidth is low, and the requirement for network performance of the route searching algorithm in the future high-speed network environment is difficult to meet. For example, dynamic random access memory (dynamic random access memory, DRAM) is off-chip memory.

In order to improve the storage bandwidth, recently, new storage technologies, such as high bandwidth memory (high bandwidth memory, HBM), have also been proposed. HBM is a high performance DRAM based on a 3-dimensional (3 d) stack process. Compared to DDR4 (a memory) or GDDR5 (a memory), HBM has a higher density, smaller volume, lower power consumption, and greater bit width and bandwidth. For a developer, the HBM is a parallel DRAM capable of providing multiple access channels, and can provide higher bandwidth. At the same time, its large capacity advantage can meet the demands of the data packet buffer on capacity caused by complex network applications on the DPU. The HBM may be integrated onto a platform such as a CPU, a graphics processor (graphics processing unit, GPU), a field-programmable gate array (FPGA), or the like. HBM is suitable for applications requiring high memory bandwidth, such as graphics processors, network switching and forwarding devices (e.g., routers, switches), etc.

The following describes the technical scheme of the present application in detail from various angles such as implementation scenario, method flow, hardware device, software device, etc.

The application scenario of the embodiment of the present application is first illustrated below. The implementation scenario involved in the route searching method provided by the embodiment of the application can comprise a communication system. Fig. 3 is a schematic structural diagram of a communication system according to an embodiment of the present application. As shown in fig. 3, the communication system includes: routing node 10 and serving node 20. One routing node 10 may be connected to one or more serving nodes 20 or routing nodes 10. The routing node 10 may be used to send data packets sent by the user equipment to the serving node 20 or other routing nodes 10. It should be appreciated that fig. 3 is merely an exemplary illustration and is not intended to limit the number of routing nodes 10 and service nodes 20 included in a communication system in any particular manner. And, the communication system may further include other network devices, which are not limited in particular by the embodiment of the present application. The service node 20 establishes a communication connection with the routing node 10. For example, a communication connection may be established between the service node 20 and the routing node 10 via a network. Alternatively, the network may be a local area network, or may be the internet, or may be another network, which is not limited by the embodiment of the present application.

When the routing node 10 receives a data packet sent by the user equipment, the routing searching method provided by the embodiment of the application can be executed to perform routing searching to obtain the next-hop information of the destination IP address of the data packet, thereby obtaining the routing node 10 or the service node 20 for the next transmission of the data packet.

In one implementation, routing node 10 may be a network device such as a router, switch, firewall, NP, smartNIC, and DPU. Alternatively, the route searching method provided by the embodiment of the present application may be implemented by running an executable program through the routing node 10. For example, the executable program of the route searching method may be presented in the form of an application installation package, and the route searching method can be implemented by running the executable program after the application installation package is installed in the routing node 10. Or the route searching method may be implemented by hardware. For example, the routing node 10 may be a device implemented with an application-specific integrated circuit (ASIC) or a programmable logic device (programmable logic device, PLD), or the like. The PLD may be implemented as a complex program logic device (complex programmable logical device, CPLD), a field-programmable gate array (FPGA) GATE ARRAY, a general-purpose array logic (GENERIC ARRAY logic, GAL), or any combination thereof.

Service node 20 may be a server, or a cluster of servers, or a cloud computing service center. Among them, a large amount of basic resources owned by cloud service providers are deployed in a cloud computing service center. For example, a cloud computing service center is deployed with computing resources, storage resources, network resources, and the like. The cloud computing service center may utilize the large amount of base resources to provide services to users.

It should be understood that the foregoing is illustrative of the implementation scenario of the route searching method provided by the embodiment of the present application, and does not constitute a limitation on the implementation scenario of the route searching method, and those skilled in the art will recognize that, as the service requirement changes, the implementation scenario may be adjusted according to the application requirement, which is not specifically recited in the embodiment of the present application.

In order to facilitate understanding, the route searching method provided by the embodiment of the application is described in terms of a route information set used by the route searching method, a storage mode of the route information set, an overall flow of the route searching method, an internal implementation process of each stage in a searching pipeline, hardware implementation thereof and the like.

The following describes a route information set used in the route searching method according to the embodiment of the present application.

In the process of route searching, the destination IP address of the data packet to be forwarded needs to be matched with the route information set to obtain the next hop information of the destination IP address (hereinafter referred to as destination next hop information for convenience of description). And if the route information set indicates the corresponding relation between the prefix item of the IP address and the next-hop information, the destination next-hop information is the next-hop information corresponding to the prefix item matched with the destination IP address.

In the embodiment of the application, the routing information set comprises N routing information subsets, and the lengths of prefix items in the N routing information subsets are different. In the embodiment of the application, a search pipeline is used for route search. The search pipeline comprises N search stages which are sequentially executed, wherein the N search stages are in one-to-one correspondence with N route information subsets. Any one of the lookup stages is used to match the destination IP address with a prefix item in the subset of routing information corresponding to the lookup stage. Wherein N is an integer greater than 1 and less than 6. In one implementation, the set of routing information is a routing table, and the subset of routing information is a routing sub-table obtained by splitting the routing table.

N routing information subsets are divided based on the length distribution rule of the prefix items. In this way, in any searching stage, all prefix items with the lengths conforming to the lengths of prefix items included in the route information subset corresponding to the searching stage can be searched, so that orderly searching of the prefix items is realized, and the route searching efficiency can be ensured. In one implementation, for an i-th routing information subset of the N routing information subsets, the lengths of the prefix entries in the i-th routing information subset are each greater than the lengths of the prefix entries in the i-1-th routing information subset, and the lengths of the prefix entries in the i-th routing information subset are each less than the lengths of the prefix entries in the i+1-th routing information subset, i being a positive integer less than or equal to N. For example, for a maximum length of 32 bits of the prefix item, the set of routing information includes: the first subset of routing information, the second subset of routing information, the third subset of routing information, and the fourth subset of routing information. The length ranges of the prefix items of the first routing information subset, the second routing information subset, the third routing information subset and the fourth routing information subset are respectively as follows: 1 to 8 bits, 9 to 16 bits, 17 to 24 bits, and 25 to 32 bits. That is, the first routing information subset, the second routing information subset, the third routing information subset, and the fourth routing information subset are all routing information subsets with a prefix item length step of 8.

The routing node needs to store a set of routing information. To ensure the lookup delay of different lookup phases, the routing information subsets corresponding to the different lookup phases may be stored in different memories. Accordingly, the N routing information subsets may also be partitioned based on the data amount of the prefix item. In one implementation, for multiple prefix entries having different lengths, all prefix entries of one or more lengths for which the total data size satisfies the specified data size range may be partitioned into the same subset of routing information. The total data volume of the one or more prefix entries is a sum of the data volumes of the routing information of the one or more prefix entries. For example, when the total data amount of all prefix entries having a length within a certain length range is greater than the maximum capacity of the specified on-chip memory, all prefix entries within the length range may be divided into the same subset of routing information, and when the total data amount of all prefix entries having a length within a certain length range is less than the maximum capacity of the specified on-chip memory, all prefix entries within the length range may be divided into another subset of routing information. The division corresponds to dividing the set of routing information into a plurality of routing information subsets according to the capacity of the memory for storing the routing information subsets and the data amount of the prefix item, which can facilitate determining the memory for storing the routing information subsets according to the capacity of the routing information subsets.

In contrast, on-chip memory generally has the characteristics of larger bandwidth, smaller capacity, higher cost and lower latency, and off-chip memory generally has the characteristics of smaller bandwidth, larger capacity, lower cost and higher latency. When dividing the routing information subsets in combination with the capacity of the memory and the data amount of the routing information, the routing information subsets with total data amount smaller than or equal to the capacity threshold may be stored in the on-chip memory, and the routing information subsets with total data amount larger than the capacity threshold may be stored in the off-chip memory, so as to ensure the routing search performance in terms of bandwidth, capacity, cost and time delay. The route searching method provided by the embodiment of the application can be applied to a route searching chip, and the on-chip memory and the off-chip memory can be memories configured for the route searching chip.

Typically, the total amount of data for any length prefix item is positively correlated with the number of prefix items having that length. The total data amount of the prefix entries may be estimated based on the number of prefix entries and the prefix entries may be partitioned into the subset of routing information based on the estimated total data amount. Illustratively, it is assumed that partitioning the set of routing information according to this principle includes: the first routing information subset, the second routing information subset, the third routing information subset and the fourth routing information subset, wherein the first routing information subset comprises a total number of prefix items, the second routing information subset comprises a total number of prefix items, the fourth routing information subset comprises a total number of prefix items which is smaller than a preset total number, the third routing information subset comprises a total number of prefix items which is larger than or equal to the preset total number, and the total data size of the third routing information subset is larger than the total data size of the first routing information subset, the second routing information subset and the fourth routing information subset. For example, taking the public network routing table information of the internet registered network coordination center (the re seaux IP europ e ens network coordination centre, RIPE NCC) in the european area in the last ten years from 2011 to 2022 as a data set for analysis, taking the 2022 core network routing table data as an example, the maximum length of the prefix item is 32 bits, and fig. 4 is a distribution rule of the prefix item in the routing table. As can be seen from fig. 4, the prefix entries with a length of 1-15 bits are very unevenly distributed, the number of prefix entries with a length of 95% or more are very small, and the prefix entries with a prefix length of 24 bits occupy 16-24 bits or more, wherein the number of prefix entries in the complete routing table is half or more. According to the distribution rule and the data quantity of the prefix items, it can be estimated that the total data quantity of the prefix items with the length of 16-24 bits is larger than that of the prefix items with the length of 1-15 bits and that of the prefix items with the length of 25-32 bits, then the routing information set is divided into a first routing information subset comprising the prefix items with the length of 1-8 bits, a second routing information subset comprising the prefix items with the length of 9-16 bits, a third routing information subset comprising the prefix items with the length of 17-24 bits, a fourth routing information subset comprising the prefix items with the length of 25-32 bits, and the total data quantity of the third routing information subset is larger than that of the first routing information subset, the second routing information subset and the fourth routing information subset.

When the routing information set and the routing information subset are represented by prefix trees, the process of dividing the routing information set into a plurality of routing information subsets is equivalent to the process of dividing an H-layer prefix tree of the routing information set into a plurality of prefix sub-trees, and the tree height of each prefix sub-tree j is Hj. The plurality of prefix sub-trees are respectively located in multiple layers, and the layer of each prefix sub-tree is determined by the number of bits of the prefix item included in the prefix sub-tree. The number of prefix tree nodes of each layer depends on the number of child nodes of the prefix tree node of the previous layer. The tree height Hj of each prefix sub-tree is determined by the width of the range of lengths of the prefix entries comprised by the prefix sub-tree. The prefix subtree includes a range width of the length of the prefix item that is the difference between the maximum length and the minimum length of the prefix item that it includes. Each prefix sub-tree can be seen as a new prefix tree node in the original H-level prefix tree. The new prefix tree node may be regarded as merging all nodes originally distributed in the prefix tree in layers 1 to H into one layer, and the prefix tree nodes located in the same layer all include information of all nodes in layers 1 to H.

Taking the routing table shown in fig. 4 as an example, the routing table may be represented by a prefix tree with a tree height of 33. The routing table comprises a first routing sub-table, a second routing sub-table, a third routing sub-table and a fourth routing sub-table. The first routing table includes prefix entries of length 1 to 8 bits. The second routing table includes prefix entries of 9 to 16 bits in length. The third routing sub-table includes prefix entries ranging in length from 17 to 24 bits. The fourth routing sub-table includes prefix entries ranging in length from 25 to 32 bits. As shown in fig. 5, the first routing sub-table, the second routing sub-table, the third routing sub-table, and the fourth routing sub-table may each be represented by a prefix sub-tree, and the second routing sub-table, the third routing sub-table, and the fourth routing sub-table may each be represented by a plurality of prefix sub-trees. The prefix bits that the first routing sub-table, the second routing sub-table, the third routing sub-table and the fourth routing sub-table can be matched with are all 8, and the step sizes of the corresponding prefix sub-trees can be considered to be 8. The structure within each dashed box in fig. 5 represents a routing sub-table. It should be noted that, due to limited space, fig. 5 is only a simplified schematic diagram of a prefix tree, and each prefix subtree may have a higher tree height and more prefix entries.

It can be seen that this division corresponds to dividing the prefix tree with a tree height of 33 into a plurality of prefix sub-trees at the first to fourth levels, respectively. This partitioning corresponds to compressing the routing table into 4 layers. A prefix sub-tree for representing prefix entries of length 1 to 8 bits is located at the first layer. A prefix sub-tree for representing prefix entries of length 9 to 16 bits is located at the second layer. A prefix sub-tree for representing prefix entries of 17 to 24 bits in length is located at the third level. A prefix sub-tree for representing prefix entries of length 25 to 32 bits is located at the fourth layer. For each of the second, third, and fourth layers, the number of prefix sub-trees in that layer depends on the total number of most significant child nodes in the layer immediately above that layer. The tree heights of the prefix subtrees of each layer should be 8, 8 and 8, but since the root node of the prefix subtree of the first layer represents the default route, the prefix subtree needs to represent the prefix item with the length of 1 to 8 bits, and also needs to represent the default route, so that the height of the prefix subtree is 1 more than the number of prefix bits that the prefix subtree can match, the tree height of the prefix subtree of the first layer is 9, and the tree heights of the prefix subtrees of the second, third and fourth layers are 8.

According to the method, the steps of the prefix subtrees positioned at the first layer are 9, and the steps of the prefix subtrees of the second layer are 8, so that the situation that the storage data size of the root node is large due to the increase of the steps can be avoided, and the storage space is small due to the fact that the number of the prefix tree stages of the first stage and the second stage is small. For 17-24 bits in the most concentrated distribution of the remaining prefixes, the embodiment of the application uses a layer of prefix subtrees, and as each layer of prefix subtrees needs to access and store for obtaining the routing information once, more than 95% of prefix items in the routing table can be matched only by 3 times of access and store. In an environment facing a high-speed network, when a routing node performs route searching, the time delay of access is high, and the efficiency of route searching is mainly determined by the number of access times. Therefore, the embodiment of the application divides the four-layer prefix subtree, adjusts the step length of the four-layer prefix subtree by taking 8 as a standard, can effectively reduce the access times in the route searching process, improves the efficiency of route searching and improves the performance of route searching.

From the above, the routing information set is divided into a plurality of routing information subsets based on the length distribution rule of the prefix item and the data volume of the prefix item, so that the prefix item can be ensured to be searched orderly in the routing searching stage. The division mode also provides basis for storage implementation of the routing information subsets, considering that the size of the number of the routing information subsets can correspondingly influence the storage capacity. And by dividing the set of routing information into a plurality of subsets of routing information in this division, and matching the destination IP address in any one of the lookup stages of the lookup pipeline with the prefix entries in the subset of routing information corresponding to that lookup stage, since this division reduces the total number of subsets of routing information, and each searching stage needs to read the route information subset corresponding to the stage from the memory, so that the access times to the memory can be reduced, the route searching time delay is reduced, the purpose of improving the searching performance is achieved, and the method is beneficial to coping with the route searching requirement under the high-speed network.

The following describes a storage manner of the routing information set according to the embodiment of the present application.

The route lookup chip may be configured with on-chip memory and off-chip memory. In one implementation, the on-chip memory may be SRAM. The off-chip memory may be HBM. When the route lookup chip is configured with an on-chip memory and an off-chip memory, the memory for storing the subset of routing information may be determined based on the amount of data of the subset of routing information. For example, the on-chip memory is used to store a subset of the routing information for which the total data amount is less than or equal to the data amount threshold, and the off-chip memory is used to store a subset of the routing information for which the total data amount is greater than the data amount threshold. The memory used for storing the route information subset is determined according to the specific condition of the route information subset, so that the cost of route searching can be controlled on the basis of comprehensively considering factors such as access delay, memory cost and bandwidth on the basis of meeting storage requirements and on the basis of guaranteeing route searching efficiency.

From the foregoing description, it is apparent that, for a plurality of prefix entries having different lengths, all prefix entries of one or more lengths whose total data amount satisfies a specified data amount range may be divided into the same subset of routing information. For example, when the total data amount of all prefix entries having a length within a certain length range is greater than the maximum capacity of the specified on-chip memory, all prefix entries within the length range may be partitioned into the same subset of routing information. When the total amount of all prefix entries having a length within a certain length range is less than the maximum capacity of the specified on-chip memory, all prefix entries within the length range may be partitioned into another subset of routing information. The specified on-chip memory may be an on-chip memory configured by the route lookup chip and the data amount threshold may be equal to or slightly less than the maximum capacity of the specified on-chip memory. That is, when the total amount of all prefix entries having a length within a certain length range is greater than the maximum capacity of the on-chip memory of the route search chip configuration, all prefix entries within the length range may be divided into the same route information subset, and the route information subset may be stored using the off-chip memory of the route search chip configuration. When the total amount of all prefix entries having a length within a certain length range is smaller than the maximum capacity of the on-chip memory of the route lookup chip configuration, all prefix entries within the length range may be divided into another route information subset and the route information subset may be stored using the on-chip memory of the route lookup chip configuration.

For example, according to the distribution rule and the data amount of the prefix items shown in fig. 4, it is known that the total data amount of the first routing information subset including the prefix items ranging in length from 1 to 8 bits, the second routing information subset including the prefix items ranging in length from 9 to 16 bits, and the fourth routing information subset including the prefix items ranging in length from 25 to 32 bits is smaller, and the total data amount of the third routing information subset including the prefix items ranging in length from 17 to 24 bits is larger, the first routing information subset, the second routing information subset, and the fourth routing information subset may be stored using the on-chip memory, and the third routing information subset may be stored using the off-chip memory.

It should be noted that, considering that the number of prefix items included in the fourth routing information subset may increase, and that the theoretical bound of the storage occupation of the fourth routing information subset (occupation of routing information) is highest, in order to face the future larger-scale routing forwarding scenario, an off-chip memory (such as HBM) may also be used to store the fourth routing information subset. Similarly, if the first routing information subset and the second routing information subset have similar conditions, the on-chip memory or the off-chip memory can be selectively used for storing the corresponding routing information subset according to specific conditions.

In one implementation, any subset of routing information may include bitmap information and address offset block information. The bitmap information and the address offset block information are in one-to-one correspondence. The bitmap information is used to indicate a prefix item, and to indicate whether a prefix tree node has a child node. The bitmap information may be represented using an external bitmap and an internal bitmap, respectively. The external bitmap is used to indicate whether a prefix tree node has a child node. The internal bitmap is used to indicate prefix entries included by the prefix tree node. The address offset block information indicates a start address of the child node array, a start address of the next hop information, and a start address of an address offset block of a next prefix tree node of the current prefix tree node. The child node array is used to store information of all child nodes belonging to the same prefix tree node. In the embodiment of the application, the starting addresses of all child nodes of each prefix tree node are stored continuously. For example, information of all child nodes in any layer is stored in a continuous address area, the start address of which is recorded in the parent node of the previous layer. Since the contiguous address area stores information of all child nodes in a layer, the starting address of the contiguous address area is also referred to as the starting address of the child node array of the layer. The storage address block of the information of all child nodes of the next layer can be accessed through the start address. Based on the start address, any one of the child nodes can be accessed in combination with the external bitmaps described in the parent nodes of the child nodes. In one implementation, an offset address of any child node of a parent node can be determined from an external bitmap recorded in the parent node, and an absolute address of the child node can be obtained based on the offset address and a start address of the child node array. For example, the starting address of the child node plus the offset address of the child node is the absolute address of the child node.

In the embodiment of the application, the address offset block information is used for recording the starting address of the child node array, the starting address of the next hop information and the starting address of the address offset block of the next prefix tree node used for finding the current prefix tree node. And bitmap information is used to describe the internal bitmap and the external bitmap. Fig. 6 is a schematic diagram of a data structure of the prefix tree node shown in fig. 4, the data structure including bitmap information and address offset block information.

The external bitmap is information indicating whether child nodes of the prefix tree node exist in the form of a bitmap. According to the order of bits arranged from left to right in the external bitmap, when a certain bit in the external bitmap is a valid bit (for example, the value is 1), the child node indicating that the prefix tree node is at the position exists, and when a certain bit in the external bitmap is an invalid bit (for example, the value is 0), the child node indicating that the prefix tree node is at the position does not exist. And the offset address of the child node in the child node array can be obtained through calculation according to the sequence of the bit in the external bitmap, so that the information of the child node can be accessed by combining the offset address and the initial address of the child node array, and the next stage of access in the route searching process is realized. As shown in fig. 7, the last layer of nodes in the prefix subtree is at most 4, and the number of child nodes in the prefix subtree is at most 8, so that the external bitmap of the prefix subtree can be obtained to be 8 bits. Assuming the external bitmap is 00001101, in which bits 5, 6, and 8 from left to right are set to 1, it is explained that the current prefix tree node exists at the 5, 6, and 8 child nodes of the next layer. Wherein at most the maximum range that the prefix tree can represent is represented in theory, according to the structure of the prefix tree. However, depending on the actual routing situation, some prefix entries may not exist, and thus the range actually represented by the prefix tree may not reach the maximum range. For example, the prefix tree in fig. 7 can theoretically represent 7 nodes, but the actual routing case indicates that there is no prefix item represented by the second node from left to right in the third layer in the prefix tree, and thus the node to which the prefix item corresponds is not shown in the prefix tree.

The internal bitmap is that the prefix items inside the prefix tree node are represented in the form of a bitmap. The order of the bits in the internal bitmap is in order from top to bottom for the different layers in the prefix subtree representing the prefix tree node, and the nodes representing the prefix items in the same layer are arranged in order from left to right. As shown in fig. 7, for a prefix tree node with a step size of 3, the prefix tree node can represent 7 prefix items at most, and then the internal bitmap is composed of 7 bits, where the first layer is represented by 1 bit, the second layer is represented by 2 bits, and the third layer is represented by 4 bits, and then each bit of the internal bitmap from left to right sequentially corresponds to a prefix item (default route) represented by a first layer node in a prefix subtree representing the prefix tree node, a prefix item (0, 1) represented by the second layer, and a prefix item (00, 01, 10, 11) represented by the third layer. A bit set to 1 in the internal bitmap indicates that the actual routing case indicates that the prefix item corresponding to the corresponding location exists, and a bit set to 0 indicates that the actual routing case indicates that the prefix item corresponding to the corresponding location does not exist. Let's assume that the internal bitmap is 1011000, which indicates that three prefix entries (default route, 1, 00) are recorded in the prefix tree node, and the three prefix entries are P1, P2, and P3 in fig. 7, respectively, and the rest of the prefix entries do not exist.

From the above, it can be seen that for a prefix tree node with a step size of 3, the internal bitmap is 7 bits and the external bitmap is 8 bits. Then for a prefix tree node of step size k, its internal bitmap is 2 ^k -1 bits and the external bitmap is 2 ^k bits.

As is clear from the foregoing description of bitmap information and address offset block information, the bitmap information is generally large in data amount due to the need to store prefix items and the like, and the address offset block information is mainly used for storing addresses and is generally small in data amount. Accordingly, all address offset block information may be stored in the on-chip memory, with bitmap information stored in the on-chip memory when the total data amount of bitmap information is less than or equal to the data amount threshold, and bitmap information stored in the off-chip memory when the total data amount of bitmap information is greater than the data amount threshold.

Alternatively, the bitmap information and the address offset block information may be stored separately in consideration of the total data amount characteristics of the bitmap information and the address offset block information, so as to reduce the memory requirements. In one implementation, two memories may be used to store bitmap information and address offset block information, respectively. Alternatively, as shown in fig. 8, the map information and the address offset block information of the first routing information subset are respectively stored in two on-chip memories (SRAM in fig. 8) corresponding to the first routing information subset, the map information and the address offset block information of the second routing information subset are respectively stored in two on-chip memories corresponding to the second routing information subset, the bitmap information of the third routing information subset is stored in an off-chip memory (HBM in fig. 8) corresponding to the third routing information subset, the address offset block information of the third routing information subset is stored in an on-chip memory corresponding to the third routing information subset, and the map information and the address offset block information of the fourth routing information subset are respectively stored in two on-chip memories corresponding to the fourth routing information subset.

Taking the routing table shown in fig. 4 as an example, the routing table is represented by a prefix tree, the bitmap information and the address offset block information are used for storing the routing information, and the total data amount of the bitmap information and the address offset block information of the four routing information subsets of the routing table is tested, and the test results are shown in table 2. From table 2, it can be seen that the total data amount of each of the bitmap information and the address offset block information of the four route information subsets, and the theoretical boundaries thereof. And the storage capacity demand is mainly distributed in a third routing information subset, which is caused by that prefix items are distributed in 16-24 bits in a concentrated way, and the current storage capacity distance of the third routing information subset still has a certain space from the theoretical boundary, which means that the storage capacity of a routing table can continue to be increased along with the increase of IPv4 prefix items, and the total demand reaches more than 10 MB.

TABLE 2

Hierarchy level	Number of nodes	Address offset block information	Bitmap information	Theoretical upper bound
					First subset of routing information	1	61b	1.1Kb	1.1Kb
Second subset of routing information	416	25Kb	210Kb	262Kb
					Third routing information subset	85213	2.7Mb	24Mb	61.7Mb
Fourth subset of routing information	8145	38Kb	300Kb	-

Thus, the address offset block information of each of the first, second, third, and fourth routing information subsets may be stored in one on-chip memory, respectively, based on the total data amount shown in table 2. Bitmap information of each of the first, second, and fourth subsets of routing information may be stored in an on-chip memory, respectively, and bitmap information of the third subset of routing information may be stored in an off-chip memory. Or the bitmap information of each of the first routing information subset and the second routing information subset may be stored in one on-chip memory, respectively, and the bitmap information of each of the third routing information subset and the fourth routing information subset may be stored in one off-chip memory, respectively. It should be noted that, through investigation, based on the cost consideration of the mainstream intelligent network card, the deployment capacity of the SRAM generally does not exceed 10MB, so it has important meaning to deploy the routing information subset with large storage capacity occupied by the routing table on the off-chip memory.

The storage method shown in fig. 8 will be further described below by taking the routing table shown in fig. 4 as an example. The routing table includes a first subset of routing information, a second subset of routing information, a third subset of routing information, and a fourth subset of routing information, each subset of routing information including bitmap information and address offset block information. The lookup pipeline includes four lookup stages, and fig. 9 to 12 are schematic diagrams of storage manners of the four routing information subsets.

In the first searching stage, the number of prefix tree nodes included in the corresponding first routing information subset is 1, namely the prefix tree nodes serving as prefix tree root nodes. Because the first routing information subset is special and comprises default routes, the first routing information subset comprises prefix items with the length of 1-8 bits, the tree height of the prefix tree node is 9, the second, third and fourth routing information subsets do not comprise default routes, and the tree heights of corresponding prefix subtrees are 8. Thus the first subset of routing information has an internal bitmap of 511 bits (bit), an external bitmap of 512 bits, and a total of 1023 bits of bitmap information. While the second, third and fourth subsets of routing information have an internal bitmap of 255 bits, an external bitmap of 256 bits, and bitmap information each having a total of 511 bits in bit width. Since each routing query requires access to the first layer, considering the fast access speed of the on-chip memory (e.g., SRAM), as shown in fig. 9, the bitmap information of the first subset of routing information is stored using 128 bytes (B) of SRAM. Since the bitmap information requires less space, the storage method does not increase the cost significantly. Similarly, for the addresses in the address offset block information of the first to fourth lookup stages, each address is 20 bits, so the address offset block information of the corresponding subset of the routing information is stored using 60-bit SRAM, respectively.

In the second search phase, the corresponding second subset of routing information includes prefix tree nodes that are increased compared to the prefix tree nodes included in the first subset of routing information. For example, the second subset of routing information includes 416 prefix tree nodes, calculated from the most current routing table. The prefix tree node of the second routing information subset has a tree height of 8, and prefix matching can be performed on prefix items with lengths of 9 th to 16 th bits, so that an internal bitmap thereof is 255 bits, and an external bitmap thereof is 256 bits. Since this second subset of routing information requires less memory, only 0.2 Megabytes (MB), in order to increase the route lookup rate, SRAM is still used to store its bitmap information and address offset blocks, as shown in fig. 10.

And for a third routing information subset corresponding to the third searching stage, calculating according to a routing table to obtain that the routing information subset comprises 85212 prefix tree nodes, wherein the total storage occupation is about 24MB. The prefix tree node of the third routing information subset has a tree height of 8, and prefix matching can be performed on prefix items with lengths of 17 th to 24 th bits, so that an internal bitmap of the prefix tree node has 255 bits, and an external bitmap has 256 bits. Through the analysis of uneven distribution of the prefixes of the routing table, the maximum pressure of the storage capacity of the routing table can be known to be the third routing information subset, so that in order to cope with the increase of the size of the future core network and the data center routing table, the storage architecture of the third routing information subset is divided into two scheme discussions of on-chip storage and off-chip storage. Because the on-chip memory (such as SRAM) can provide high access memory bandwidth and low access memory delay, but has small memory capacity and high cost, it is difficult to satisfy the development of IPv4 or IPv6 routing tables with larger scale in the future. The same problem can be found with SRAM for other applications on the DPU where memory locality is poor or memory usage is high. Therefore, the third searching stage adopts an off-chip memory (such as an HBM with a single access channel) to test on the basis of the on-chip memory, explores the access bandwidth and capacity occupation requirements of the third searching stage, and discusses the memory architecture scheme of the off-chip memory in the future ultra-large scale routing scene. From this test it is possible to obtain: as shown in fig. 11, in the third routing information subset, for address offset block information with small bit width (60 bits), SRAM storage is adopted, and for bitmap information with large bit width (511 bits), HBM storage with a single memory channel is adopted in order to cope with future super-large-scale routing scenarios.

The fourth search stage mainly matches prefix entries of 25-32 bits in length. The inquiry pressure of the inquiry phase is obviously reduced compared with the previous inquiry phase. However, the number of prefix tree nodes in the searching stage is small, and if the node bitmap information is stored by using an on-chip memory (such as SRAM), the routing table in the present stage at least needs to store a storage space with 300 Kilobytes (KB) in a chip. Meanwhile, as the number of prefixes is still continuously increasing, two schemes can be considered for the storage mode of bitmap information and address offset block information corresponding to the searching stage. One approach is to store both bitmap information and address offset block information using SRAM. For example, as shown in fig. 12, since most of the route searches are completed in the third stage and the memory capacity in the fourth stage is relatively small, both bitmap information and address offset block information are stored in SRAM as the SRAM is available. The second scheme is to use SRAM to store address offset block information and off-chip memory (e.g., HBM with single access channel) to store bitmap information. For example, since the number of prefix entries in the fourth lookup stage is increasing and the memory footprint (the footprint of the routing table) of the fourth lookup stage is theoretically the highest, it is also feasible to use HBM to store bitmap information for future larger-scale route forwarding scenarios.

The above is an example of a storage method of the route information subset when the route information subset is divided into bitmap information and address offset block information. The storage means may also be adapted as desired by a person skilled in the art when storing the subset of routing information. For example, the present application divides the routing information subset into bitmap information and address offset block information based on the total data amount of the bitmap information and address offset block information and the capacity of the memory. When the application scenario changes, one or more of the internal bitmap, the external bitmap, the starting address of the child node array, the starting address of the next hop information, and the starting address of the address offset block of the next prefix tree node of the current prefix tree node may be stored in one memory as required, or the internal bitmap, the external bitmap, the starting address of the child node array, the starting address of the next hop information, and a part of the starting address of the address offset block of the next prefix tree node of the current prefix tree node may be stored in one memory, and the rest may be stored in another memory, or even more memories may be used to store the starting address of the internal bitmap, the external bitmap, the child node array, the starting address of the next hop information, and the starting address of the address offset block of the next prefix tree node of the current prefix tree node. In addition, the routing information subset may be divided by reference to other bases, which are not listed in the embodiment of the present application.

When the off-chip memory is used for storing the routing information, the off-chip memory can be configured in order to ensure the routing searching delay in consideration of the large delay of the off-chip memory. For example, when the off-chip memory is an HBM with a single access channel, it may be configured to access the HBM through an advanced extensible interface (advanced eXtensible interface, AXI) and optimize the equivalent access latency of the off-chip memory through the significant transfer (outstanding) characteristics in the AXI protocol, improving the equivalent bandwidth. Because the AXI is channel-separated, when the obvious transmission in the AXI protocol is utilized to provide the route information, the next operation can be started without waiting for the completion of the previous transmission, so that the utilization rate of a channel can be effectively improved, and the route searching performance is improved.

Considering that in future high-speed and ultra-large scale routing scenarios, an off-chip memory with a single access channel may not meet the access bandwidth requirement, the off-chip memory used in the embodiment of the present application may also be a memory with multiple access channels. The access channels correspond to the search pipelines, and any access channel in the access channels is used for providing route information for the corresponding pipeline, so that the purposes of realizing high bandwidth and reducing access delay by utilizing the access channels are achieved, and the route search efficiency is further improved. For example, consider that in future high-speed, very large scale routing scenarios, an HBM with a single memory channel may not meet the memory bandwidth requirements of a DPU, requiring at least 8 memory channels to meet the lookup performance requirements under a 400GbE high-speed network. Therefore, the single pipeline mode of the route searching can be laterally expanded to be expanded into a multi-pipeline mode, and the route searching is realized by adopting a multi-pipeline parallel execution mode and a parallel memory access mode through a multi-memory access channel of the HBM. For example, FIG. 13 is a schematic diagram of 8 parallel lookup pipelines. As shown in fig. 13, after the routing node receives the data packet sent by the sender, IP decoding is performed on the data packet, and then a target search pipeline for performing route search on the IP address of the data packet is determined, and the IP address is provided to the target search pipeline to search and determine the next hop information of the IP address. The routing node is also provided with an HBM controller for controlling access operation of the HBM with a plurality of access channels. HBM [1] to HBM [8] in fig. 13 are a plurality of memory channels of HBM having a plurality of memory channels, respectively. It should be noted that, the number of the lookup pipelines and the number of the access channels of the memory can be flexibly configured according to the network speed and the size of the routing table in the network environment, which is not particularly limited in the embodiment of the present application.

Alternatively, multiple access channels of off-chip memory may each store the full amount of routing information stored by off-chip memory. For example, where the routing table size is not large, each memory channel of off-chip memory may store a full amount of routing tables. Or multiple access channels of off-chip memory may each store a portion of the full amount of routing information stored by off-chip memory. For example, when the off-chip memory has M memory channels, the routing information set may be divided into M routing information subsets by using a division policy, and the M routing information subsets are stored in the M memory channels in a one-to-one correspondence, where M is a positive integer greater than 1. Alternatively, the routing information may be partitioned with prefix bits of a specified number of bits as an index, and all prefix entries having the same prefix bits on the specified number of bits may be partitioned into the same subset of routing information. For example, when the off-chip memory is an HBM with eight access channels, the first to third prefix bits may be used as indexes, all prefix entries with the same first to third prefix bits may be divided into the same routing information subset, so as to obtain 8 disjoint routing information subsets, and the 8 routing information subsets may be distributed to the 8 access channels. By dividing the routing information subsets according to the prefix bits as indexes, a plurality of disjoint routing information subsets can be obtained, and the independence of data division is ensured. After the route information subsets are distributed to the access channels, when the pipeline corresponding to each access channel in the access channels performs route searching, only the route searching task corresponding to the route information subset stored in the access channel corresponding to the pipeline is required to be processed, and the route searching can be independently performed without accessing the route information subsets stored in other access channels, so that the route searching efficiency is further ensured.

According to the method, the access speed of the on-chip memory is high, the access delay is low, the capacity of the on-chip memory is low, the cost is high, the storage capacity of the off-chip memory is large, the cost is low, the storage bandwidth is low, the memory for storing the route information subset is determined according to the specific condition of the route information subset, the factors such as the access delay, the memory cost and the bandwidth can be comprehensively considered on the basis of meeting the storage requirement, the cost of route searching is controlled on the basis of guaranteeing the route searching efficiency, and the method is beneficial to coping with the storage capacity requirement under a large or even ultra-large scale route scene.

The following describes the overall flow of the route searching method according to the embodiment of the present application by taking the route node executing the route searching method as an example. As shown in fig. 14, the implementation process of the route searching method includes the following steps:

step 101, obtaining the destination IP address of the data packet to be forwarded.

After receiving the data packet to be forwarded, the routing node can decode the data packet to obtain the destination IP address of the data packet.

Step 102, obtaining a routing information set for performing routing lookup, wherein the routing information set indicates a corresponding relation between a prefix item of an IP address and next-hop information, the routing information set comprises N routing information subsets, the lengths of the prefix items in the N routing information subsets are different, N is an integer greater than 1 and less than 6, and the N routing information subsets are obtained based on the length distribution rule of the prefix item and the data volume division of the prefix item.

Before the route searching for the destination IP address, the route node needs to acquire a route information set for searching the route for the destination IP address. The process of obtaining the routing information set refers to the routing node determining which information set is the routing information set used for performing the route lookup, i.e. obtaining the set name of the routing information set, and does not refer to the routing node needing to read the routing information set from the memory.

Step 103, based on the destination IP address and the routing information set, sequentially executing N search stages in the search pipeline to obtain destination next-hop information indicating forwarding of the data packet, where the N search stages are in one-to-one correspondence with the N routing information subsets, and any one search stage is used to match the destination IP address with a prefix item in the routing information subset corresponding to any one search stage.

After the routing node obtains the destination IP address and the set of routing information, a lookup pipeline may be performed based on the destination IP address and the set of routing information to obtain next hop information for the destination IP address. In order to ensure the readability of the embodiment, the implementation process of the lookup pipeline is not described herein, and will be described later.

From the foregoing, it will be appreciated that the routing method can be extended to use multiple lookup pipelines in parallel for route lookup.

At this time, as shown in fig. 15, before step 103, the route searching method further includes:

step 104, determining a target searching pipeline for carrying out route searching on the target IP address, and providing the target IP address for the target searching pipeline.

When a plurality of parallel search pipelines are deployed in the routing node, the routing node needs to determine a target search pipeline for performing route search on the destination IP address before executing the search pipeline, and provide the destination IP address to the target search pipeline so that the target search pipeline searches for next hop information of the destination IP address.

When all the multiple access channels of the off-chip memory store the full-quantity routing information stored by the off-chip memory, because the routing search can be performed based on the full-quantity routing information stored by any one of the multiple access channels, one access channel can be randomly selected from the multiple access channels, or one access channel can be directly selected from the multiple access channels based on policies such as load balancing, and then a search pipeline corresponding to the selected access channel is determined as a target search pipeline. For example, when there are eight lookup pipelines, the eight lookup pipelines may be assigned numbers. When determining the target search pipeline, the first three bits of the target IP address can be taken, the first three bits are subjected to remainder extraction, and the search pipeline with the number of remainder is determined as the target search pipeline.

When the multiple access channels of the off-chip memory respectively store the full amount of routing information stored in the off-chip memory, a mode of matching with a partitioning strategy for partitioning the routing information set can be adopted to determine a target search pipeline in multiple search pipelines. For example, when dividing the routing information by using the prefix bit of the specified bit as an index, the prefix bit of the specified bit may be obtained from the destination IP address, then the routing information subset prefixed by the prefix bit of the specified bit is searched for in the routing information subsets corresponding to the plurality of search pipelines, and then the search pipeline corresponding to the access channel for storing the routing information subset of the search channel is determined as the target search pipeline.

The implementation of the lookup pipeline is described below. Based on the destination IP address and N routing information subsets, N searching stages in the searching pipeline are sequentially executed to obtain destination next-hop information indicating forwarding of the data packet, and the method comprises the following steps:

In the first searching stage, the k 1-bit of the target IP address is matched with a prefix item included in a first routing information subset corresponding to the first searching stage, when the first prefix item matched with the k 1-bit exists in the first routing information subset, if a second prefix item to be matched taking the first prefix item as a prefix exists in a prefix item included in a second routing information subset corresponding to the second searching stage, information of the second prefix item to be matched is provided for the second searching stage, and if the second prefix item to be matched does not exist in the prefix item included in the second routing information subset, the first next-hop information corresponding to the first prefix item is used as the next-hop information of the target. Where k1 is the range width of the length of the prefix item in the first subset of routing information. The first k1 bits of the IP address refer to the first k1 bits of the IP address starting from the first bit from the left. In one implementation, when the routing information set is represented by a prefix tree, the second prefix item to be matched using the first prefix item as a prefix may be a child node of the first prefix item, and the information of the second prefix item to be matched may be an address of bitmap information of the child node and an address of an address offset block.

In the I searching stage in the second to N-1 searching stages, the Imin to Imax bits of the target IP address are matched with all I to-be-matched prefix items included in the I routing information subset corresponding to the I searching stage, when the target I prefix item matched with the Imin to Imax bits exists in all the I to-be-matched prefix items, if the I+1 to-be-matched prefix item taking the target I prefix item as a prefix exists in the prefix items included in the I+1 routing information subset corresponding to the I+1 searching stage, the information of the I+1 to-be-matched prefix item is provided for the I+1 searching stage, and if the I+1 to-be-matched prefix item does not exist in the prefix items included in the I+1 routing information subset, the I next hop information corresponding to the target I to be the target I prefix item is used as target next hop information, wherein I is an integer which is larger than 1 and smaller than N. Imin is the minimum length of the prefix item included in the I-th routing information subset, imax is the maximum length of the prefix item included in the I-th routing information subset, and Imin is an integer greater than k1 and less than Imax.

In the N-th searching stage, the Nmin-Nmax bits of the target IP address are matched with all N-th prefix items to be matched included in the N-th routing information subset corresponding to the N-th searching stage, and when the N-th prefix items matched with the Nmin-Nmax bits exist in all the N-th prefix items to be matched, N-th next hop information corresponding to the N-th prefix items is used as target next hop information. Wherein Nmin is the minimum length of the prefix item included in the nth routing information subset, nmax is the maximum length of the prefix item included in the nth routing information subset, and Nmin is an integer greater than Imax and less than Nmax.

When the set of routing information is represented by a prefix tree and the subset of routing information may include bitmap information and address offset block information, each lookup stage corresponds to: determining an external bitmap and an internal bitmap corresponding to the searching stage according to bitmap information, then performing prefix item matching according to the internal bitmap, determining whether child nodes of a current prefix tree node exist according to the external bitmap, determining that the current route searching process is finished when the child nodes do not exist, taking next-hop information corresponding to the matching items of the searching stage as a route searching result, determining offset addresses of the child nodes based on the external bitmap when the child nodes exist, obtaining addresses of bitmap information and addresses of address offset block information of the next searching stage according to the offset addresses and the addresses indicated by the address offset block information, and then providing the addresses of the address of the matching items, the addresses of the bitmap information and the addresses of the address offset block information to the next searching stage. The next searching stage continues to perform route searching according to the process, when the next searching stage searches for a longer matching item, an address corresponding to the longer matching item is provided for the next searching stage, when the next searching stage does not find a longer matching item, the current searching stage takes the longest prefix matching result of the previous searching stage as the longest prefix matching result of the current searching stage, the matching result of the previous searching stage is provided for the next searching stage, and the like until all searching stages of the searching pipeline are executed, and global longest prefix matching is obtained.

It should be noted that, in any lookup stage, if the internal bitmap is not successfully matched, it is indicated that the destination IP address is not matched in the prefix item corresponding to the lookup stage, and it cannot be indicated that the longest prefix match is completed, whether the child stage belonging to the next lookup stage exists needs to be continuously determined according to the external bitmap, and if the child node belonging to the next lookup stage exists, the route lookup process of the next lookup stage needs to be continuously performed.

As can be seen from the foregoing description, there may be a plurality of subsets of routing information in other levels than the first level of subsets of routing information, such as the second subset of routing information, the third subset of routing information, and the fourth subset of routing information. When there are a plurality of the routing information subsets of any one of the other stages, a mismatch may occur in a portion of the plurality of routing information subsets of any one of the other stages in the route search process based on the routing information subsets of any one of the other stages. In addition, because the route searching process adopts a pipeline form, each searching stage can provide a matching item for the next searching stage, if the current searching stage does not have child nodes of the stage, bubbles are inserted in the next stage, so that the pipeline utilization rate is improved, and backtracking searching is not needed.

The following description will proceed with the example of the routing table shown in fig. 4, where the lookup pipeline includes four lookup stages, and the lookup pipeline of the routing lookup method is illustrated. As shown in fig. 16, the implementation procedure of the four search stages is as follows:

In the first search phase: the method comprises the steps of inputting a destination IP address carried by a route searching instruction, when the route searching instruction arrives, accessing an internal bitmap, an external bitmap and a corresponding address offset block of a root prefix tree node in a memory, then carrying out route searching according to the first 1-8 bits of the destination IP address, obtaining the address of next hop information of the longest prefix matching item and the address of the accessed bitmap information and address offset block information in a second searching stage through a matching process of the internal bitmap and the external bitmap, and then outputting the three and the destination IP address to the second searching stage simultaneously. Wherein when it is determined from the external bitmap that the child node belonging to the second lookup stage exists, the address of the bitmap information to be accessed by the second lookup stage and the address of the address offset block information are acquired. When the child node belonging to the second searching stage does not exist according to the external bitmap, the fact that the longer prefix item is matched in the later searching stage is not needed is indicated, and the route searching process is ended.

In the second search phase: when the second searching stage receives the output of the first searching stage, the route searching process of the second searching stage is started, the internal bitmap, the external bitmap and the corresponding address offset block of the current prefix tree node in the memory can be accessed through the address of the bitmap information of the prefix tree node corresponding to the current searching stage and the address of the address offset block information, then the internal bitmap and the external bitmap of the current prefix tree node are respectively matched with the internal bitmap and the external bitmap of the searching stage according to the 9 th-16 th bit of the target IP address, the address of the next hop information of the longest prefix matching item of the second searching stage, the address of the accessed bitmap information and the address of the address offset block information of the third searching stage are obtained, and then the three are output to the third searching stage together with the target IP address. Wherein when it is determined from the external bitmap that the child node belonging to the third lookup stage exists, the address of the bitmap information to be accessed by the third lookup stage and the address of the address offset block information are acquired. When the child node belonging to the third searching stage does not exist according to the external bitmap, the fact that the later searching stage does not have longer prefix item matching is indicated, and the route searching process is ended.

In the third search phase: the method comprises the steps of firstly accessing an internal bitmap, an external bitmap and an address offset block corresponding to a prefix tree node corresponding to a current searching stage in a memory according to an address of bitmap information and an address of address offset block information provided by a previous searching stage, then respectively matching the internal bitmap and the external bitmap of the searching stage according to bits 17-24 of a destination IP address to obtain an address of next hop information of a longest prefix matching item of a third searching stage and an address of the accessed bitmap information and address of address offset block information of a fourth searching stage, and then outputting the three and the destination IP address to the fourth searching stage simultaneously. When it is determined that the child node belonging to the fourth lookup stage exists according to the external bitmap, the address of the bitmap information to be accessed by the fourth lookup stage and the address of the address offset block information are acquired. When the child node belonging to the fourth searching stage does not exist according to the external bitmap, the fact that the longer prefix item is matched in the later searching stage is not needed is indicated, and the route searching process is ended.

In the fourth search phase: when the fourth searching stage receives the output of the third searching stage, the route searching process of the fourth searching stage is started, firstly, the internal bitmap of the prefix tree node corresponding to the current searching stage and the address offset block corresponding to the internal bitmap are accessed according to the bitmap information address and the address offset block information address provided by the third searching stage, then the internal bitmap of the prefix tree node corresponding to the current searching stage in the memory is matched with the internal bitmap of the searching stage according to the 25 th to 32 th bits of the destination IP address, the address of the next hop information of the longest prefix matching item of the fourth searching stage, namely the route searching final longest prefix matching, is output to a memory (such as a DRAM) for storing the next hop information together with the destination IP address. Because the matching of the external bitmap is used for obtaining the information of the child stage to be accessed in the next searching stage, and the fourth searching stage is the last searching stage of the whole route searching process, the fourth searching stage does not need to match the external bitmap.

It can be seen that the lookup flow of any lookup stage can be divided into memory access logic and computation logic. The access logic is to read the subset of routing information from the memory. The memory logic includes two parts, read address offset block information and read bitmap information. The calculation logic is used for matching with the destination IP address segment corresponding to the current searching stage through the internal and external bitmap information. The calculation logic includes calculating an address offset of the child node, calculating an address offset of next hop information, calculating an address of bitmap information corresponding to a next lookup stage, and calculating an address of address offset block information corresponding to the next lookup stage.

The following describes the way in which the address of bitmap information, the address of address offset block information, and the address of next-hop information are obtained in the search stage.

As shown in fig. 17, the input of each search stage is the address of the bitmap information of the previous search stage, the address of the corresponding address offset block information, the destination IP address, and the address of the next hop information found in the previous search stage. And each searching stage reads the internal bitmap and the external bitmap corresponding to the current searching stage according to the address of the bitmap information, and calculates the address offset of the child node and the address offset of the next hop information by combining the destination IP address. According to the address of the corresponding address offset block information, three initial addresses in the address offset block, namely the initial address of the address offset block information corresponding to the next searching stage, the initial address of the child node belonging to the next searching stage and the initial address of the next hop information, can be obtained. Then, based on the address offset of the child node, the address offset of the next hop information, and the three start addresses, the address of the bitmap information to be accessed in the next lookup stage and the address of the corresponding address offset block information, and the address of the next hop information in the lookup stage are obtained, respectively. The destination IP address used in any one of the search stages is actually the bit corresponding to the search stage in the destination IP address. For example, the destination IP address used in the second lookup stage is actually the 9 th to 16 th bits of the destination IP address corresponding to the lookup stage. When the routing information set is represented by a prefix tree, the address offset block and bitmap information of the first lookup stage default to the position of the root node because the prefix tree has only the root node in the first lookup stage.

In one implementation, the address offset of the child node belonging to the next lookup stage is obtained from the external bitmap and the destination IP address. And matching the internal bitmap with the destination IP address to obtain the address offset of the next hop information. And reading the address offset block information corresponding to the next searching stage, the child node and the starting address of the next hop information from the address offset block through the address offset block information. Alternatively, the address of the address offset block information corresponding to the next search stage may be obtained based on the start address of the address offset block information corresponding to the next search stage and the address offset of the child node belonging to the next search stage. The address of the bitmap information corresponding to the next search stage may be obtained based on the starting address of the child node belonging to the next search stage and the address offset of the child node belonging to the next search stage. The address of the next-hop information corresponding to the matching item in the current searching stage can be obtained based on the starting address of the next-hop information and the address offset of the next-hop information.

When the address offset of the child node belonging to the next searching stage is acquired, because the child node is continuously stored in the child node array, the number of the child node belonging to the next searching stage can be determined according to the address field of the destination IP address to be matched in the current searching stage, then the bit used for representing the child node in the external bitmap corresponding to the current searching stage is determined according to the number, and the total number of valid bits (optionally including the valid bit of the child node) positioned on the left of the bit representing the child node in the external bitmap is counted according to the sequence of the bits from left to right in the external bitmap, and the total number is recorded as the offset I1 of the child node. Assuming that the starting address of the child node array corresponding to the current search stage is C1, that is, the starting address of the bitmap information is C1, and the size of each prefix tree node is S1, it can be calculated that the address A1 of the child node in the next search stage satisfies: a1 =c1+i1 x S1. Assuming that the starting address of the address offset block information corresponding to the next search stage is C2, and the size of each address offset block information is S2, it can be calculated that the address A2 of the address offset block information corresponding to the next search stage satisfies: a2 =c1+i1 x S2.

When the address offset of the next hop information is acquired, the calculation method is similar to the method for acquiring the address offset of the child node belonging to the next lookup stage, the address segment of the destination IP address to be matched according to the current lookup stage is matched with the internal bitmap, the total number of valid bits (optionally including the valid bit itself of the next hop information) positioned on the left of the bit representing the next hop information in the internal bitmap is counted, and the total number is recorded as the offset I2 of the next hop information. Assuming that the starting address of the next-hop information array corresponding to the current searching stage is C3, and the size of each next-hop information is S3, it can be calculated that the address A3 of the next-hop information in the next stage satisfies: a3 =c3+i2 x S3.

In the above description of the manner of acquiring the address of the bitmap information, the address of the address offset block information, and the address of the next hop information, it is assumed that the address offset block information and the bitmap information have the same address offset (i.e., the address offset of the child node in the above description) as an example. In other implementations, if the address offset block information and the bitmap information have different address offsets, the address offset of the address offset block information needs to be obtained in the search stage.

The implementation of each lookup stage in the lookup pipeline is described below.

In one implementation, as shown in fig. 18, to increase the efficiency of the lookup pipeline, a single lookup stage may be implemented cooperatively by the following 5 sub-modules: the memory access logic module, the memory access buffer queue, the internal buffer queue, the calculation logic module and the inter-stage buffer queue.

The access logic module is used for reading the address offset block information and the bitmap information. The process of reading the address offset block information and the process of reading the bitmap information may each include the following two processes: and sending the read address process of the storage address of the content to be read to the memory, and receiving the read data process of the content fed back by the memory based on the storage address. In the memory access logic module, the address reading process and the data reading process are realized through mutually independent memory access channels. That is, the memory access logic module is split into a read address channel and a read data channel which are independent of each other, and the read address channel is used for sending a memory address of the content to be read to the memory, namely, realizing the read address process. The read data channel receives the feedback content of the memory based on the memory address, namely, the read data process is realized. The read address channel and the read data channel are mutually independent: after the read address channel sends a storage address to the memory, the read data channel can continue to send the next storage address to the memory without waiting for the read data channel to return the data stored in the storage address. For example, when the read address channel and the read data channel are independent of each other, if any subset of the routing information includes the first routing information and the second routing information, in the access logic, the first routing information and the second routing information need to be read respectively, and after the first storage address of the first routing information is sent to the memory through the read address channel, the second storage address of the second routing information can be sent to the memory through the read address channel continuously without waiting for the memory to feed back the first routing information based on the first storage address. In this way, the time delay of multiple data reading by the memory access logic module can be reduced.

To further reduce the latency, the transmitted data stream may also be controlled within each access channel using an efficient transport protocol. For example, the control of the data flow may be performed within the memory channel by a Ready-Vaild handshake protocol. The Ready-Valid handshake protocol is applicable to very high throughput data stream structures. When data transmission is carried out through a Ready-Valid handshake protocol, a data Valid (Vaild) signal of a data channel is pulled up when a data transmitting end is Ready for data, and a data receiving end pulls up a data idle (Ready) signal after the last data is processed. And the data transmitting end and the data receiving end perform data transmission when the Vaild signal and the Ready signal are both high bits. Such setting corresponds to designing an operation to access the memory as a data bypass.

Compared with the prior logic for controlling by adopting a finite state machine (FINITE STATE MACHINE, FSM) on hardware, the FSM processes the sending request in the memory through a plurality of processing states, waits for and receives data and other operations, and the stable memory control can be realized, but the memory process using the FSM is equivalent to the complete receiving and transmitting process of the memory behavior and the data path process of the pipeline because the plurality of processing states all need to occupy time delay, so the processing time delay of the memory process is difficult to achieve 1 period. For example, when using an on-chip memory SRAM, although the memory latency of the SRAM is 1 cycle, so that the FSM does not need to wait time, the sub-operations of the FSM that send requests and receive data may result in the sub-operation latency of the memory logic always being 2 cycles. And FSM schemes are extremely inefficient when off-chip memory is employed. Therefore, the implementation mode of the access logic module provided by the embodiment of the application can effectively reduce the access time delay and improve the efficiency of searching the pipeline.

The memory buffer queue can control the capacity in the buffer zone of the sending queue through a back pressure mechanism, and prevent packet loss caused by the buffer zone of the sending queue being full. Because the time delay of the memory is not fixed, and the real-time sending rate of the real network traffic under the high-speed network is also not fixed, the access and storage behavior of the data bypass cannot be predicted. Therefore, a memory buffer queue can be added between the memory logic module and the memory, and the data flow rate between the memory logic module and the memory is controlled through the memory buffer queue so as to balance the data pressure of the calculation logic and the memory logic. Particularly, under a high-speed network, the access bandwidth of the off-chip memory may not meet the requirement of high search performance, and at this time, the packet loss caused by the full buffer area of the sending queue can be prevented by the back pressure mechanism of the access buffer queue. Under the normal load balancing condition, bitmap information and address offset block information obtained from a memory can be cached in a memory buffer queue, when data exists in the memory buffer queue, a destination IP address belonging to the same route searching operation is aligned with the bitmap information and the address offset block information, and the three information and the bitmap information and the address offset block information are simultaneously sent to a calculation logic for calculation, so that searching errors which occur because the plurality of IP addresses cannot correspond to the bitmap information and the address offset block information when a plurality of IP addresses to be searched exist are prevented.

Based on a starting point similar to the memory buffer queue, an internal buffer queue can be added between the memory logic module and the calculation logic module, so that the data flow rate between the memory logic module and the calculation logic module is controlled, and the condition that the memory efficiency and the calculation logic efficiency are inconsistent under a high-speed network is avoided.

The computation logic module is divided into an internal bitmap computation module and an external bitmap computation module. The implementation logic of the internal bitmap calculation module and the external bitmap calculation module can refer to the related description of the external bitmap and the internal bitmap respectively. On this basis, since the external bitmap calculation module needs to count the total number of valid bits located on the left of the bits representing the child nodes to be queried in the external bitmap, in order to improve the calculation efficiency, the calculation logic of the total number of the valid bits can be optimized from serial logic to parallel logic. In this way, a space-time-shifting strategy can be employed, reducing the latency of counting the total number of valid bits. Illustratively, the parallel logic of the statistically significant bits may be implemented in an FPGA, which may increase resource consumption and layout and routing costs, but may implement a computational efficiency that may process a route lookup once per clock cycle, i.e., a packet (PACKET PER clock cycle) =1 per clock cycle.

Based on a similar starting point as the memory buffer queue, inter-phase buffer queues may be added between different lookup phases. Under the flow pressure caused by a high-speed network, different pipeline efficiency can appear in different search stages, a back pressure mechanism can be facilitated by adding an inter-stage buffer queue between the different search stages, the data flow rate between the different search stages can be controlled, and whether the flow is blocked or not is judged through a Ready-Valid handshake protocol, so that the packet loss caused by pipeline blocking is avoided.

The pipeline mechanism provided by the embodiment of the application can ensure that the processing period of each sub-operation in a single searching stage is 1 period, and can ensure that each period of each sub-operation can process one route searching instruction under the condition of relatively large pipeline load, such as network flow facing a high-speed network, so that the equivalent time delay of the whole pipeline in the single searching stage is 1 period. And then through the efficient handshake protocol between the search stages, the transmission delay of the pipeline data stream between the search stages can be ensured to be 1 period. Therefore, by the pipeline mechanism provided by the embodiment of the application, the processing of route searching once per clock period, namely ppc=1, can be realized, and the theoretically optimal pipeline efficiency can be realized.

The following are some experimental analysis and verification results of the route lookup method provided by the embodiment of the present application.

(1) Storage capacity analysis

As shown in fig. 19, the present application establishes a system storage capacity analysis model by taking a DPU as an example for experimental analysis. It is considered that there are mainly two phases of message buffering and message processing on the DPU. The memory occupation in the route searching process is mainly embodied in the occupation of a data packet buffer area and a route table. Wherein, because the IP searching algorithm processes the packet header of the data packet, the time of the data packet in the buffer area is not long. However, for other applications in the DPU that require processing of the packet payload (payload), the latency may be very high, so the current analysis of the data buffer size is limited to the application in the DPU being an IP lookup application. The following is an analysis of the memory occupancy in the route lookup process as the occupancy in the packet buffer and the routing table, respectively.

After the DPU receives the data packet from the portal, the data packet needs to be buffered in the packet buffer. After the next hop information of the destination IP address is found, the data packet is taken out from the data packet buffer, the packet head is updated based on the next hop information, and the data packet with the updated packet head is sent out from the network port. Thus, the capacity of the packet buffer is affected by both the network traffic rate and the packet buffering time. The calculation relationship is as follows: packet buffer capacity = network speed (Gbps) x delay (ns) of a single IP lookup. The delay of a single IP lookup was found to be 633.3ns (95 clock cycles/0.15 GHz) by testing.

The size of the routing table is generally determined by the scale of the application scenario of the routing table and is not affected by the high-speed network. The size of the routing table is determined, for example, by the size of the core network or data center. Taking a core network as an example, the scale change of a routing table of the European backbone network in the last ten years is observed, the scale of the routing table steadily increases every year, but the scale of prefix tree node information in the first searching stage, the second searching stage and the fourth searching stage is basically stable and unchanged and has smaller absolute value, and the scale of the prefix tree node in the third searching stage linearly increases along with the scale increase of the routing table. Considering that the structure of the prefix tree determines that the number of prefix tree nodes to be accessed in a later searching stage in the pipeline is larger than the number of prefix tree nodes to be accessed in a former searching stage, and because the prefix items of the routing table are unevenly distributed and mainly distributed in a third searching stage, the fourth searching stage is stable and smaller than the third searching stage, and therefore the third searching stage has a great possibility of expanding in the future.

Table 3 shows the change in memory usage of the route lookup method with increasing network speed. From this table 3 it can be seen that the routing table does not increase with increasing network speed, whereas the size of the packet buffer increases linearly with network speed. In a 400GbE network environment, the routing table occupies 27.2Mb, the packet buffer occupies 253.2Kb, and the total memory occupied is 27.5Mb. Some accelerator cards are currently capable of providing 41MB of SRAM, and if data from this table is used, it can be determined that the memory footprint requirements are currently met. This however mainly builds on two preconditions. One is based on performing only IP lookup operations on the DPU without other complex network applications. The actual DPU packet processing flow needs to perform a series of complex packet processing operations, which results in an increase in the buffering time of the packet in the DPU, and thus, an increase in the size of the packet buffer. Secondly, only 32-bit searching of IPv4 is carried out at present, and 128-bit searching of IPv6 is not involved. After the routing table entry of IPv6 is converted into a prefix tree, its size is greatly expanded compared with IPv 4. In addition, if other applications (such as KVS) with poor memory locality or high memory occupation on the DPU are considered, the on-chip memory SRAM may not meet the memory requirement of the DPU, so the embodiment of the present application has important significance in deploying the off-chip memory. And by analyzing the data such as access bandwidth, search performance and the like of the off-chip memory scheme, the advantages and disadvantages of the scheme for deploying and not deploying the off-chip memory can be obtained.

TABLE 3 Table 3

(II) memory access bandwidth analysis

At the random access peak of the HBM with a single access channel, the access bandwidth is only 4.98GB/s. Considering that the access bandwidth may become a development bottleneck for limiting future routing search algorithm oriented to the high-speed network, the application establishes an access bandwidth analysis model. The access bandwidth of the route searching process mainly comprises a data packet buffer access memory and a route searching access memory. The data packet buffer memory is used for reading and writing the data packet buffer memory. The route lookup memory is used for reading the route table. The analysis is performed from these two aspects separately.

In the route searching access memory, only the third stage is carried out on the access memory of the off-chip memory, and each route searching corresponds to one access of the off-chip memory, so the bandwidth of the route searching access memory is actually affected by the searching performance and the data bit width of the access memory, and the calculation relation is as follows: memory bandwidth = lookup performance x data bit width. The lookup performance may be represented by millions of route forwarding packets per second (millions of PACKETS PER second, MPPS).

After the DPU receives the data packet from the network port, the data packet needs to be cached, after the IP searches the next hop information, the data packet is taken out from the buffer area and the packet header is updated, and then the data packet with the updated packet header is sent out from the network port. Therefore, in the packet buffer access, the bandwidth of the packet buffer is actually affected by the network traffic rate, and the following relation is calculated: packet buffer access bandwidth = network speed (Gbps) x 2 (two procedures for ingress write data and egress read data are shown).

Table 4 shows the change in demand for the route lookup memory bandwidth and the packet buffer memory bandwidth as network speeds continue to increase. As can be seen from table 4, the route lookup memory bandwidth exhibits a linear increase with increasing network speed. In a high-speed network environment of 400GbE, the demand of the route searching access memory bandwidth is 38GB/s. Similarly, the memory bandwidth requirements of packet buffers may also exhibit a linear increase with network speed. In a high-speed network environment of 400GbE, the access memory bandwidth requirement of a data packet buffer area is 100GB/s. At present, the HBM with a single access channel on some accelerator cards can support 4.98GB/s at most, and cannot meet the memory access requirement of route searching. So in future high speed very large scale routing scenarios HBMs with a single memory channel may not meet the memory bandwidth requirements of the DPU.

TABLE 4 Table 4

Fig. 20 is a schematic diagram showing the variation of access bandwidth with the number of access channels of the HBM. As shown in fig. 20, the random access bandwidth of the HBM with a single access channel is 4.98GB/s, and the access bandwidth required for route searching is calculated according to the analysis in table 4, because the capacity occupation of the data packet buffer is smaller, the access bandwidth of the data packet buffer is temporarily not considered, and the access bandwidth requirement is larger, and the HBM can be stored by using an on-chip memory SRAM. And the HBM of at least 2 access channels is required to meet the access bandwidth requirement in the environment of 100GbE, the HBM of at least 8 access channels is required to meet the access bandwidth requirement in the environment of 400GbE, and the HBM of at least 16 access channels is required in the environment of 800 GbE. Therefore, after the number of access channels of the off-chip memory is increased, the access bandwidth is correspondingly increased.

In summary, it is considered that the larger the step size of the prefix tree, the fewer the number of accesses required to complete the single route search procedure. However, since the prefix items of the routing table are unevenly distributed and mainly concentrated in 17-24 bits, for example, by setting a proper prefix tree step length, the searching steps and the access times in the actual route searching process can be reduced. And through relevant modeling analysis, the whole memory space occupation of the prefix tree can be increased under the condition of increasing the step length, and the excessively high step length can reduce the access times and improve the searching efficiency, but is not beneficial to supporting the deployment of a larger-scale routing table. At the same time, the step size increases, which causes the compressed prefix tree nodes to expand, and the node widths of the accesses of each search step increase. This increases the bit width requirements for the memory.

Therefore, the embodiment of the application optimizes the route information set and the route searching method by combining the factors such as the access times, the data bit width, the storage capacity occupation and the like, can reduce the access times, reduce the access time delay and improve the overall searching performance, so that the route searching method can meet the high requirement on the searching performance in a high-speed network environment.

And by combining the characteristics of different memories and the distribution condition of the routing table, aiming at the access bandwidth requirement and the storage capacity requirement of different stages of the routing lookup method, different memories are adopted to store corresponding routing information subsets in different lookup stages, so that the problem of occupation of the routing table storage in a large-scale or even ultra-large-scale routing scene is solved, and the routing lookup performance can be further improved.

Meanwhile, by using a memory with a plurality of access channels, the route searching method is expanded into a plurality of searching pipelines, the characteristic that the memory with a plurality of access channels has high bandwidth can be fully utilized, the problem of small access bandwidth of the off-chip memory is solved, the expansibility is provided for the route searching method facing to a high-speed network and a super-large-scale route scene, and the condition is provided for supporting a future larger-scale route table and a network route scene with higher link speed.

It should be noted that, the sequence of the steps of the route searching method provided by the embodiment of the application can be properly adjusted, and the steps can be correspondingly increased or decreased according to the situation. Any method that can be easily conceived by those skilled in the art within the technical scope of the present disclosure should be covered in the protection scope of the present application, and thus will not be repeated.

The virtual device according to the embodiment of the present application is illustrated below.

The route searching method of the embodiment of the application is introduced above, and the embodiment of the application also provides a route searching device corresponding to the method. Fig. 21 is a schematic structural diagram of a route searching device according to an embodiment of the present application. The route search device shown in fig. 21 is capable of performing all or part of the operations shown in fig. 14 or 15 described above based on the following modules shown in fig. 21. It should be understood that the apparatus may include additional modules than those shown or omit some of the modules shown therein, and embodiments of the present application are not limited in this respect. As shown in fig. 21, the route searching device 210 may include:

the acquiring module 2101 is configured to acquire a destination network protocol IP address of a data packet to be forwarded.

The obtaining module 2101 is further configured to obtain a routing information set for performing routing lookup, where the routing information set indicates a correspondence between a prefix item of an IP address and next-hop information, and the routing information set includes N routing information subsets, where N is an integer greater than 1 and less than 6, and the N routing information subsets are obtained by dividing the routing information subsets based on a length distribution rule of the prefix item and a data size of the prefix item.

The processing module 2102 is configured to sequentially execute N search stages in a search pipeline based on the destination IP address and the set of routing information to obtain destination next-hop information indicating forwarding of the data packet, where the N search stages are in one-to-one correspondence with the N routing information subsets, and any one search stage is configured to match the destination IP address with a prefix item in the routing information subset corresponding to any one search stage.

Optionally, the processing module 2102 is specifically configured to:

In a first searching stage, matching the k 1-bit of the target IP address with a prefix item included in a first routing information subset corresponding to the first searching stage, when the first prefix item matched with the k 1-bit exists in the first routing information subset, if a second prefix item to be matched taking the first prefix item as a prefix exists in a prefix item included in a second routing information subset corresponding to the second searching stage, providing information of the second prefix item to be matched for the second searching stage, and if the second prefix item to be matched does not exist in the prefix item included in the second routing information subset, taking first next-hop information corresponding to the first prefix item as target next-hop information, wherein k1 is the range width of the length of the prefix item in the first routing information subset;

In an I searching stage in the second to N-1 searching stages, matching Imin to Imax bits of a target IP address with all I to-be-matched prefix items included in an I routing information subset corresponding to the I searching stage, when the target I prefix item matched with the Imin to Imax bits exists in all the I to-be-matched prefix items, if the I+1 to-be-matched prefix item taking the target I prefix item as a prefix exists in the prefix items included in the I+1 routing information subset corresponding to the I+1 searching stage, providing information of the I+1 to-be-matched prefix item for the I+1 searching stage, and if the I+1 to-be-matched prefix item does not exist in the prefix items included in the I+1 routing information subset, taking the I next hop information corresponding to the target I to be the target I prefix item as the next hop information, wherein I is an integer which is larger than 1 and smaller than N, and Imin is the minimum length of the prefix item included in the I to be the I routing information subset is the maximum length of the prefix item included in the I+1 to be the prefix item;

Optionally, the processing module 2102 is specifically configured to: acquiring a storage address of routing information required by any one searching stage; reading the routing information from the memory based on the memory address, wherein the process of reading the routing information from the memory based on the memory address comprises: the method comprises the steps that an address reading process of a storage address is sent to a memory and a data reading process of the storage memory based on storage address feedback route information is received, wherein the address reading process and the data reading process are realized through mutually independent memory access channels; and matching the destination IP address with the prefix item in the routing information subset corresponding to any one of the searching stages based on the routing information.

Optionally, when the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory, the processing module 2102 is further configured to: and determining a target searching pipeline for carrying out route searching on the target IP address, and providing the target IP address for the target searching pipeline.

Therefore, the embodiment of the application optimizes the route information set and the route searching process by combining the factors such as the access times, the data bit width, the storage capacity occupation and the like, can reduce the access times, reduce the access time delay and improve the overall searching performance, so that the route searching process can meet the high requirement on the searching performance in a high-speed network environment.

And by combining the characteristics of different memories and the distribution condition of the routing table, aiming at the access bandwidth requirement and the storage capacity requirement of different stages in the routing searching process, different memories are adopted to store the corresponding routing information subsets in different searching stages, so that the problem of occupied storage of the routing table in a large-scale or even ultra-large-scale routing scene is solved, and the routing searching performance can be further improved.

Meanwhile, by using the memory with a plurality of access channels, the route searching process is expanded into a plurality of searching pipelines, the characteristic that the memory with a plurality of access channels has high bandwidth can be fully utilized, the problem of small access bandwidth of the off-chip memory is solved, the expansibility is provided for the route searching process facing to a high-speed network and a super-large-scale route scene, and the condition is provided for supporting a future larger-scale route table and a network route scene with higher link speed.

It will be clear to those skilled in the art that, for convenience and brevity of description, the specific operation of the apparatus and modules described above may refer to the corresponding content in the foregoing embodiment, which is not described in detail herein.

The following illustrates the basic hardware structure involved in an embodiment of the present application.

Embodiments of the present application provide a computing device. The computing device is used for realizing part or all of the functions in the route searching method provided by the embodiment of the application. FIG. 22 is a schematic diagram of a computing device according to an embodiment of the present application. As shown in fig. 22, the computing device 2200 includes a processor 2201, a memory 2202, a communication interface 2203, and a bus 2204. The processor 2201, the memory 2202 and the communication interface 2203 are connected to each other by a bus 2204.

The processor 2201 may include a general purpose processor and/or a dedicated hardware chip. The general purpose processor may include: a central processing unit (central processing unit, CPU), a microprocessor, or a graphics processor (graphics processing unit, GPU). The CPU is, for example, a single-core processor (single-CPU), and is, for example, a multi-core processor (multi-CPU). The special-purpose hardware chip is a high-performance processing hardware module. The special purpose hardware chip includes at least one of a digital signal processor, an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA) or a network processor (network processer, NP). The processor 2201 may also be an integrated circuit chip with signal processing capabilities. In implementation, some or all of the functions of the route lookup method of the present application may be performed by hardware integrated logic circuitry in the processor 2201 or by instructions in the form of software.

The memory 2202 is used to store a computer program that includes an operating system 2202a and executable code (i.e., program instructions) 2202b. The memory 2202 is, but is not limited to, a read-only memory or other type of static storage device that can store static information and instructions, a random access memory or other type of dynamic storage device that can store information and instructions, an electrically erasable programmable read-only memory, a read-only optical or other optical storage, an optical storage (including compact discs, laser discs, optical discs, digital versatile discs, blu-ray discs, etc.), a magnetic disk storage medium or other magnetic storage device, or any other medium that can be used to carry or store desired executable code in the form of instructions or data structures and that can be accessed by a computer. Such as memory 2202, for storing an egress port queue or the like. The memory 2202 is, for example, independent and is connected to the processor 2201 via a bus 2204. Or the memory 2202 and the processor 2201 may be integrated together. The memory 2202 may store executable code that, when executed by the processor 2201, the processor 2201 is operable to perform some or all of the functions of the route lookup method provided by embodiments of the present application. The implementation of the process performed by the processor 2201 is referred to correspondingly in the description of the previous embodiments. The memory 2202 may also include software modules and data necessary for other operating systems and other processes to run.

The communication interface 2203 enables communication with other devices or communication networks using a transceiver module such as, but not limited to, a transceiver. For example, the communication interface 2203 may be any one or any combination of the following devices: network interfaces (e.g., ethernet interfaces), wireless network cards, and the like having network access functionality.

Bus 2204 is any type of communication bus used to interconnect internal components of a computing device (e.g., memory 2202, processor 2201, communication interface 2203). Such as a system bus. While embodiments of the application have been described in terms of the devices internal to computing device being interconnected by bus 2204, the devices internal to computing device 2200 may alternatively be communicatively coupled to each other using other means of connection than bus 2204. For example, the aforementioned devices within computing device 2200 are interconnected by internal logic interfaces.

The plurality of devices may be provided in separate chips, or may be provided at least partially or entirely in the same chip. Whether the individual devices are independently disposed within different chips or integrally disposed within one or more chips is often dependent upon the needs of the product design. The embodiment of the application does not limit the specific implementation form of the device. And the descriptions of the processes corresponding to the drawings are focused on, and the descriptions of other processes can be referred to for the parts of a certain process which are not described in detail.

In the above embodiments, it may be implemented in whole or in part by software, hardware, firmware, or any combination thereof. When implemented in software, may be implemented in whole or in part in the form of a computer program product. The computer program product providing the program development platform includes one or more computer instructions that, when loaded and executed on a computing device, implement, in whole or in part, the functions of the route lookup method provided by embodiments of the present application.

Moreover, the computer instructions may be stored in a computer-readable storage medium or transmitted from one computer-readable storage medium to another computer-readable storage medium, for example, the computer instructions may be transmitted from one website, computer, server, or data center to another website, computer, server, or data center by a wired (e.g., coaxial cable, optical fiber, digital subscriber line), or wireless (e.g., infrared, wireless, microwave, etc.) means. The computer readable storage medium stores computer program instructions that provide a program development platform.

The embodiment of the application also provides a computer readable storage medium, which is a nonvolatile computer readable storage medium, and the computer readable storage medium comprises program instructions, when the program instructions run on the computing device, the computing device is caused to implement the route searching method provided by the embodiment of the application.

The embodiment of the application also provides a computer program product containing instructions, which when run on a computer, cause the computer to realize the route searching method provided by the embodiment of the application.

It will be understood by those skilled in the art that all or part of the steps for implementing the above embodiments may be implemented by hardware, or may be implemented by a program for instructing relevant hardware, where the program may be stored in a computer readable storage medium, and the storage medium may be a read-only memory, a magnetic disk or an optical disk, etc.

It should be noted that, the information (including but not limited to user equipment information, user personal information, etc.), data (including but not limited to data for analysis, stored data, presented data, etc.), and signals related to the present application are all authorized by the user or are fully authorized by the parties, and the collection, use, and processing of the related data is required to comply with the relevant laws and regulations and standards of the relevant countries and regions. For example, the original data and the executable code and the like involved in the present application are all acquired with sufficient authorization.

In embodiments of the present application, the terms "first," "second," and "third" are used for descriptive purposes only and are not to be construed as indicating or implying relative importance. The term "at least one" means one or more, the term "plurality" means two or more, unless expressly defined otherwise.

The term "and/or" in the present application is merely an association relation describing the association object, and indicates that three kinds of relations may exist, for example, a and/or B may indicate: a exists alone, A and B exist together, and B exists alone. In addition, the character "/" herein generally indicates that the front and rear associated objects are an "or" relationship.

The foregoing description of the preferred embodiments of the present application is not intended to limit the application, but is intended to cover any modifications, equivalents, alternatives, and improvements within the spirit and principles of the application.

Claims

1. A route lookup method, the method comprising:

acquiring a destination network protocol (IP) address of a data packet to be forwarded;

acquiring a route information set for route searching, wherein the route information set indicates the corresponding relation between a prefix item of an IP address and next-hop information, the route information set comprises N route information subsets, the N route information subsets are obtained by dividing based on the length distribution rule of the prefix item and the data volume of the prefix item, and N is an integer greater than 1 and less than 6;

and based on the destination IP address and the routing information set, sequentially executing N search stages in a search pipeline to obtain destination next-hop information for indicating forwarding of the data packet, wherein the N search stages are in one-to-one correspondence with the N routing information subsets, and any one search stage is used for matching the destination IP address with a prefix item in the routing information subset corresponding to the any one search stage.

2. The method of claim 1, wherein the sequentially performing N lookup stages in a lookup pipeline based on the destination IP address and the set of routing information to obtain destination next-hop information indicating forwarding of the data packet comprises:

in a first searching stage, matching a first k1 bit of the destination IP address with a prefix item included in a first routing information subset corresponding to the first searching stage, when a first prefix item matched with the first k1 bit exists in the first routing information subset, if a second prefix item to be matched with the first prefix item exists in a prefix item included in a second routing information subset corresponding to a second searching stage, providing information of the second prefix item to be matched to the second searching stage, and if the second prefix item to be matched does not exist in the prefix item included in the second routing information subset, taking first next hop information corresponding to the first prefix item as the destination next hop information, wherein k1 is the range width of the length of the prefix item in the first routing information subset;

In the first searching stage of the second to N-1 searching stages, the Imin to Imax bits of the destination IP address are matched with all I prefix items to be matched included in the I routing information subset corresponding to the first searching stage, when the destination I prefix item matched with the Imin to Imax bits exists in all the I prefix items to be matched, if the I+1 prefix item to be matched taking the destination I prefix item as a prefix exists in the prefix items included in the I+1 routing information subset corresponding to the I+1 searching stages, providing the information of the I+1st prefix item to be matched to an I+1st searching stage, if the prefix item to be matched of the I+1st prefix item does not exist in the prefix items included in the I+1st routing information subset, taking the I next hop information corresponding to the target I prefix item as the target next hop information, wherein I is an integer greater than 1 and less than N, imin is the minimum length of the prefix items included in the I routing information subset, and Imax is the maximum length of the prefix items included in the I routing information subset;

In an nth lookup stage, the Nmin-Nmax bits of the destination IP address are matched with all the nth to-be-matched prefix items included in the nth routing information subset corresponding to the nth lookup stage, when the destination Nth prefix item matched with the Nmin-Nmax bits exists in all the nth to-be-matched prefix items, the Nth next hop information corresponding to the destination Nth prefix item is used as the destination next hop information, the Nmin is the minimum length of the prefix items included in the nth routing information subset, and the Nmax is the maximum length of the prefix items included in the nth routing information subset.

3. The method of claim 1 or 2, wherein performing any one of N lookup stages in a lookup pipeline based on the destination IP address and the set of routing information comprises:

acquiring a storage address of the routing information required by any one of the searching stages;

Reading the routing information from the memory based on the storage address, wherein the process of reading the routing information from the memory based on the storage address comprises the following steps: the method comprises the steps of sending a read address process of a storage address to a memory and receiving a read data process of the memory for feeding back routing information based on the storage address, wherein the read address process and the read data process are realized through mutually independent access channels;

And matching the destination IP address with a prefix item in the routing information subset corresponding to any one of the searching stages based on the routing information.

4. A method as claimed in any one of claims 1 to 3, wherein the method is applied to a route look-up chip configured with an on-chip memory storing a subset of route information having a total data amount less than or equal to a data amount threshold and an off-chip memory storing a subset of route information having a total data amount greater than the data amount threshold.

5. The method of claim 4, wherein any subset of routing information includes bitmap information and address offset block information, any on-chip memory stores the address offset information or bitmap information having a total data amount less than or equal to the data amount threshold, and any off-chip memory stores bitmap information having a total data amount greater than the data amount threshold.

6. The method of claim 4, wherein the off-chip memory is a memory having a plurality of channels, the plurality of channels corresponding to a plurality of lookup pipelines, any of the plurality of channels to provide routing information to the corresponding pipeline.

7. The method of claim 6, wherein the plurality of channels each store a full amount of routing information stored by the off-chip memory or the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory.

8. The method of claim 7, wherein the portion of the routing information stored by the plurality of lanes is partitioned based on prefix bits of a specified number of bits.

9. The method of claim 7 or 8, wherein when the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory, before sequentially performing N lookup stages in a lookup pipeline based on the destination IP address and the set of routing information to obtain destination next hop information indicating forwarding of the data packet, the method further comprises:

And determining a target searching pipeline for carrying out route searching on the target IP address, and providing the target IP address for the target searching pipeline.

10. The method of any of claims 1 to 9, wherein the prefix entries of the set of routing information are in the range of 1 to 32 bits in length, the set of routing information including a first subset of routing information, a second subset of routing information, a third subset of routing information, and a fourth subset of routing information, the prefix entries of the first subset of routing information, the second subset of routing information, the third subset of routing information, and the fourth subset of routing information being in the range of: 1 to 8 bits, 9 to 16 bits, 17 to 24 bits, and 25 to 32 bits.

11. The method of claim 10, wherein the first subset of routing information includes a total number of prefix items, the second subset of routing information includes a total number of prefix items, the fourth subset of routing information includes a total number of prefix items that is less than a preset total number, and the third subset of routing information includes a total number of prefix items that is greater than or equal to the preset total number.

12. The method of claim 11, wherein any one of the routing information subsets includes bitmap information and address offset block information, wherein the map information and address offset block information of the first routing information subset are stored in two on-chip memories corresponding to the first routing information subset, wherein the map information and address offset block information of the second routing information subset are stored in two on-chip memories corresponding to the second routing information subset, wherein the map information of the third routing information subset is stored in an off-chip memory corresponding to the third routing information subset, wherein the address offset block information of the third routing information subset is stored in an on-chip memory corresponding to the third routing information subset, and wherein the map information and address offset block information of the fourth routing information subset are stored in two on-chip memories corresponding to the fourth routing information subset.

13. A route lookup apparatus, the apparatus comprising:

The acquisition module is used for acquiring a destination network protocol (IP) address of a data packet to be forwarded;

the acquisition module is further used for acquiring a routing information set for carrying out routing searching, wherein the routing information set indicates the corresponding relation between a prefix item of an IP address and next-hop information, the routing information set comprises N routing information subsets, the N routing information subsets are obtained by dividing based on the length distribution rule of the prefix item and the data volume of the prefix item, and N is an integer greater than 1 and less than 6;

And the processing module is used for sequentially executing N searching stages in a searching pipeline based on the destination IP address and the routing information set to obtain destination next-hop information for indicating forwarding of the data packet, the N searching stages are in one-to-one correspondence with the N routing information subsets, and any one searching stage is used for matching the destination IP address with a prefix item in the routing information subset corresponding to any one searching stage.

14. The apparatus of claim 13, wherein the processing module is specifically configured to:

15. The apparatus according to claim 13 or 14, wherein the processing module is specifically configured to:

16. The apparatus according to any of claims 13 to 15, wherein the apparatus is applied to a route look-up chip configured with an on-chip memory storing a subset of route information having a total data amount less than or equal to a data amount threshold and an off-chip memory storing a subset of route information having a total data amount greater than the data amount threshold.

17. The apparatus of claim 16, wherein any subset of routing information comprises bitmap information and address offset block information, wherein any on-chip memory stores the address offset information or bitmap information having a total data amount less than or equal to the data amount threshold, and wherein any off-chip memory stores bitmap information having a total data amount greater than the data amount threshold.

18. The apparatus of claim 16, wherein the off-chip memory is a memory having a plurality of channels, the plurality of channels corresponding to a plurality of lookup pipelines, any of the plurality of channels to provide routing information to the corresponding pipeline.

19. The apparatus of claim 18, wherein the plurality of channels each store a full amount of routing information stored by the off-chip memory or the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory.

20. The apparatus of claim 19, wherein the portion of the routing information stored by the plurality of lanes is partitioned based on prefix bits of a specified number of bits.

21. The apparatus of claim 19 or 20, wherein when the plurality of channels each store a portion of the full amount of routing information stored by the off-chip memory, the processing module is further to:

22. The apparatus of any of claims 13 to 21, wherein a length of a prefix item of the set of routing information ranges from 1 to 32 bits, the set of routing information including a first subset of routing information, a second subset of routing information, a third subset of routing information, and a fourth subset of routing information, the length of the prefix items of the first subset of routing information, the second subset of routing information, the third subset of routing information, and the fourth subset of routing information ranging from: 1 to 8 bits, 9 to 16 bits, 17 to 24 bits, and 25 to 32 bits.

23. The apparatus of claim 22, wherein a total number of prefix items included in the first subset of routing information, a total number of prefix items included in the second subset of routing information, and a total number of prefix items included in the fourth subset of routing information are each less than a preset total number, and wherein a total number of prefix items included in the third subset of routing information is greater than or equal to the preset total number.

24. The apparatus of claim 23, wherein any subset of routing information comprises bitmap information and address offset block information, wherein the map information and address offset block information for the first subset of routing information are stored in two on-chip memories corresponding to the first subset of routing information, wherein the map information and address offset block information for the second subset of routing information are stored in two on-chip memories corresponding to the second subset of routing information, wherein the map information for the third subset of routing information is stored in off-chip memories corresponding to the third subset of routing information, wherein the address offset block information for the third subset of routing information is stored in on-chip memories corresponding to the third subset of routing information, and wherein the map information and address offset block information for the fourth subset of routing information are stored in two on-chip memories corresponding to the fourth subset of routing information, respectively.

25. A computing device comprising a memory storing program instructions and a processor executing the program instructions to perform the method of any one of claims 1 to 12.

26. A computer readable storage medium comprising program instructions which, when run on a computing device, cause the computing device to perform the method of any of claims 1 to 12.