CN115190071A

CN115190071A - Cache method and integrated circuit

Info

Publication number: CN115190071A
Application number: CN202110361730.4A
Authority: CN
Inventors: 喻径舟; 刘杨; 杨斐然; 郭玲波; 邢豫盛; 周立伟
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2021-04-02
Filing date: 2021-04-02
Publication date: 2022-10-14
Anticipated expiration: 2041-04-02
Also published as: CN115190071B; WO2022206397A1

Abstract

The embodiments of the present application provide a caching method and an integrated circuit, which can avoid false hits. The caching method includes: acquiring a first packet, where the first packet includes a destination Internet Protocol IP address; searching a cache for a routing prefix matching the destination IP address; in response to not storing the destination IP address in the cache For routing prefix, look up the tree structure corresponding to the routing table according to the destination IP address, and determine the prefix node matching the destination IP address; in response to the prefix node not being a leaf node, the processor determines that the first prefix matches length, the first prefix matching length is equal to the length between the root node and the tail node of the tree structure; according to the first prefix matching length and the destination IP address, determine the first routing prefix; trigger the cache A first correspondence is stored, where the first correspondence is the first routing prefix and routing information corresponding to the prefix node.

Description

Cache method and integrated circuit

Technical Field

The present application relates to the field of communications technologies, and in particular, to a caching method and an integrated circuit.

Background

When network equipment such as a router or a switch forwards a message, a destination Internet Protocol (IP) address carried in the message can be acquired, and routing information corresponding to the destination IP address is searched from a routing table, so that the message is forwarded according to the searched routing information. The routing table is an entry for recording a routing prefix and routing information, and is pre-stored in the network device. The routing prefix is used to determine routing information that matches the destination IP address, and may be, for example, the first n bits of the IP address, where n is the length of the routing prefix. The routing information may be an identifier of a network interface, which indicates through which network interface the network device needs to forward the packet.

When searching the routing table, whether the destination IP address is matched with the routing prefix is judged. For example, assuming that the length of a certain routing prefix is m, and the first m bits of the destination IP address are consistent with the routing prefix, the destination IP address may be considered to be matched with the routing prefix, and the corresponding routing information is the routing information corresponding to the routing prefix. When the destination IP address matches two or more routing prefixes at the same time, the routing Prefix may be determined according to the Longest Prefix Match (LPM) principle. That is, the routing information of the routing prefix having the longest length among the plurality of routing prefixes matching the destination IP address can be used as the routing information corresponding to the destination IP address.

Since the lookup of the routing table requires comparing whether the routing prefix matches the destination IP address, the network device needs to lookup the routing table. Obviously, the faster the routing table is called, the faster the network device forwards the packet. Currently, in order to increase the speed of invoking the routing table by the network device, the correspondence between part of the routing prefix and the routing information may be stored in a cache. But this approach tends to have false hits.

Disclosure of Invention

The embodiment of the application provides a cache method and an integrated circuit, and the corresponding relation between a first routing prefix with the length longer than that of a destination IP address in a routing table and routing information is recorded in a cache, so that the occurrence of false hit is avoided.

In a first aspect, an embodiment of the present application provides a caching method, which may be applied to a processor in a network device. When the cache method is executed, the processor may first obtain the first packet, and determine a destination IP address carried in the first packet. The processor may then look up a routing prefix from the cache that matches the destination IP address. If the cache does not store the routing prefix matched with the destination IP address, the processor can search the tree structure corresponding to the routing table from other memories according to the destination IP address, so as to determine a prefix node matched with the destination IP address in the tree structure, namely a node of the routing prefix matched with the destination IP address in the tree structure corresponding to the routing table. When the prefix node is not a leaf node in the tree structure, i.e., the prefix node has children, the processor may determine a length from a root node to a tail node of the tree structure as the first prefix match length. And the tail node is the last node on the search path in the tree structure. The search path is a path from the root node to the leaf node in the tree structure corresponding to the routing table along the tree structure corresponding to the destination IP address in the tree structure corresponding to the routing table. After the first prefix matching length is obtained, the processor may determine, according to the destination IP address and the first prefix matching length, a first routing prefix, and trigger the cache to store a first correspondence relationship, where the first correspondence relationship is a correspondence relationship between the first routing prefix and routing information corresponding to the prefix node. That is, when the prefix node is not a leaf node, the routing prefix in the correspondence is different from the routing prefix described in the routing table. That is, when other routing prefixes whose lengths are greater than the routing prefix corresponding to the destination IP address exist in the routing table, the processor may determine a new first routing prefix according to the first prefix matching length, and store a correspondence between the new routing prefix and the routing information in the cache. In this way, the length of the first routing prefix may be greater than the length of the routing prefix in the memory routing table that matches the destination IP address. Thus, compared with the prior art, the method can play a role in reducing the probability of false hits.

In one possible implementation, the first routing prefix may be longer than the first prefix match length. It is readily understood that the longer the length of the first routing prefix, the less likely a false hit will occur. When the length of the first routing prefix is greater than the first prefix match length, the probability of a false hit is 0.

In one possible implementation, when the destination IP address is a leaf node in the tree structure corresponding to the routing table, the length of the first routing prefix may be equal to the first prefix matching length.

In one possible implementation, the tree structure corresponding to the routing table may be divided into a virtual tree structure and a plurality of sub-tree structures. The processor may determine a prefix node matching the destination IP address through the virtual tree structure and the sub-tree structure. The virtual tree structure may include any plurality of nodes in the tree structure corresponding to the routing table, and a root node of each of the plurality of sub-tree structures corresponds to one node in the virtual tree structure. Specifically, the processor may first search for a virtual tree structure corresponding to the routing table according to the destination IP address, and determine a virtual prefix longest matching the destination IP address. Then, the processor may determine, according to the virtual prefix, that a routing prefix corresponding to the root node is a sub-tree structure of the virtual prefix, and search, from the sub-tree structure, a prefix node that matches the destination IP address. Then, assuming that the first length is the length from the root node of the virtual book structure to the virtual prefix, and the second length is the length from the virtual prefix to the tail node on the search path of the subtree structure, the sum of the first length and the second length is the aforementioned first prefix matching length. Therefore, the tree structure corresponding to the routing table is divided into the virtual tree structure and the plurality of subtrees, and the searching efficiency of the routing prefix can be improved.

In some possible implementations, the processor may also store a correspondence of the second routing prefix and the routing information. The destination routing prefix is a routing prefix corresponding to a unique node on the forwarding path, and the unique node is a child node only having a left child node or a right child node. Specifically, when the prefix node matching the destination IP address is not a leaf node, the processor may determine a single node on the forwarding path according to the forwarding path of the destination IP address, and determine the second prefix matching length according to the belly node. The second prefix match length is equal to the length from the root node to the solitary node. After determining the second prefix match length, the processor may determine a second routing prefix according to the second prefix match length, thereby storing the second correspondence.

In some possible implementations, the processor may also trigger the cache to store the type of the first routing prefix. Then, after the processor receives another message, if the destination IP address of the message hits the first routing prefix, the processor may obtain, according to the indication of the type of the first routing prefix, the routing information corresponding to the first routing prefix from the cache according to the first correspondence relationship.

In some possible implementations, when the processor determines the prefix node through the virtual tree structure and the subtree structure, the processor may trigger the cache to store a third correspondence between the virtual prefix, the type of the virtual prefix, and the information of the subtree structure. Similarly, if the destination IP address of the packet hits the virtual prefix, the processor may search the sub-tree structure from the information of the sub-tree structure according to the indication of the type of the virtual prefix, so as to determine the routing information corresponding to the first routing prefix.

In some possible implementations, the processor may also trigger the cache to store the length of the first routing prefix, taking into account a maximum length matching principle.

In some possible implementations, the length of the first routing prefix is equal to the first prefix matching length plus 1.

In some possible implementations, the length of the first routing prefix is less than the length of the destination IP address.

In some possible implementations, the destination IP address includes the first routing prefix.

In some possible implementations, the cache includes at least one of: ternary Content Addressable Memory (TCAM), registers, line cards, and dies.

In a second aspect, an embodiment of the present application provides an integrated circuit, which is applied to a processor, and includes an interface circuit and a control circuit; the interface circuit is used for acquiring a first message, wherein the first message comprises a destination Internet Protocol (IP) address; the control circuit is used for searching a route prefix matched with the destination IP address from a cache; responding to the condition that the routing prefix is not stored in the cache, searching a tree structure corresponding to a routing table according to the destination IP address, and determining a prefix node matched with the destination IP address; in response to the prefix node not being a leaf node, determining a first prefix match length, the first prefix match length being equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure; determining a first routing prefix according to the first prefix matching length and the destination IP address; and triggering the cache to store a first corresponding relationship, wherein the first corresponding relationship is the first routing prefix and the routing information corresponding to the prefix node.

In some possible implementations, the first routing prefix has a length greater than or equal to the first prefix matching length.

In some possible implementations, the control circuit is configured to search a virtual tree structure corresponding to a routing table according to the destination IP address, and determine a virtual prefix longest matching with the destination IP address; searching a subtree structure corresponding to the virtual prefix according to the destination IP address, and determining a prefix node matched with the destination IP address, wherein the virtual prefix is a root node of the subtree structure; the first prefix matching length is equal to the sum of a first length and a second length, the first length is from a root node of the virtual tree structure to the virtual prefix, the second length is from the virtual prefix to a tail node, and the tail node is the last node on a search path of the sub-tree structure.

In some possible implementations, the control circuitry is further configured to determine a second prefix match length in response to the prefix node not being a leaf node, the second prefix match length being equal to a length between a root node of the tree structure and a dependent node, the dependent node being a node between the prefix node and the tail node that has only a left child node or only a right child node; determining a second routing prefix according to the second prefix matching length and the destination IP address, wherein the length of the second routing prefix is greater than the second prefix matching length; and triggering the cache to store a second corresponding relationship, wherein the second corresponding relationship is the second routing prefix and the routing information corresponding to the prefix node.

In some possible implementations, the control circuit is further configured to trigger the cache to store a type of the first routing prefix, where the type of the first routing prefix is used to indicate that, when the first routing prefix is hit, routing information corresponding to the first routing prefix is obtained in the cache according to the first corresponding relationship.

In some possible implementations, the control circuit is further configured to trigger the cache to store a third corresponding relationship, where the third corresponding relationship is a corresponding relationship between the virtual prefix, a type of the virtual prefix, and information of the subtree structure, and the type of the virtual prefix is used to indicate that, when the virtual prefix is hit, the subtree structure is searched according to the information of the subtree structure.

In some possible implementations, the control circuitry is further configured to trigger the cache to store the length of the first routing prefix.

In some possible implementations, the cache includes at least one of: TCAM, registers, wire-clamping board and die.

In a third aspect, an embodiment of the present application provides a cache apparatus, where the cache apparatus includes an obtaining unit and a processing unit. The acquiring unit is configured to acquire a first packet, where the first packet includes a destination internet protocol IP address. The processing unit is used for searching a route prefix matched with the destination IP address from a cache; responding to the condition that the routing prefix is not stored in the cache, searching a tree structure corresponding to a routing table according to the destination IP address, and determining a prefix node matched with the destination IP address; in response to the prefix node not being a leaf node, determining a first prefix match length, the first prefix match length being equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure; determining a first routing prefix according to the first prefix matching length and the destination IP address; and triggering the cache to store a first corresponding relation, wherein the first corresponding relation is the first routing prefix and the routing information corresponding to the prefix node.

In a fourth aspect, an embodiment of the present application provides a chip, where the chip includes a memory and a processor, where the memory is used to store instructions or program codes, and the processor is used to call and execute the instructions or program codes from the memory to perform the caching method according to the first aspect.

In a fifth aspect, an embodiment of the present application provides an apparatus, which includes a processor chip and a memory, where the memory is used to store instructions or program codes, and the processor chip is used to call and execute the instructions or program codes from the memory to execute the caching method according to the first aspect.

In a sixth aspect, an embodiment of the present application provides a computer-readable storage medium, which includes instructions, programs, or codes, and when executed on a computer, causes the computer to perform the caching method according to the foregoing first aspect.

Drawings

Fig. 1 is a schematic structural diagram of a processor according to an embodiment of the present application;

fig. 2 is a schematic structural diagram of a tree structure corresponding to a routing prefix according to an embodiment of the present application;

fig. 3-a is a schematic structural diagram of a network system 300 according to an embodiment of the present application;

fig. 3-b is a schematic structural diagram of a network device 350 according to an embodiment of the present application;

fig. 3-c is another schematic structural diagram of a network device 350 according to an embodiment of the present application;

fig. 3-d is a schematic structural diagram of a network device 350 according to an embodiment of the present application;

fig. 3-e is a schematic structural diagram of a network device 360 according to an embodiment of the present application;

fig. 3-f is a schematic structural diagram of a chip 370 of a network device according to an embodiment of the present application;

fig. 3-g is a schematic structural diagram of a virtual router 380 according to an embodiment of the present application;

fig. 4 is a schematic flowchart of a caching method according to an embodiment of the present application;

fig. 5 is a schematic structural diagram of a tree structure corresponding to a routing table according to an embodiment of the present application;

FIG. 6 is a schematic structural diagram of a subtree structure according to an embodiment of the present disclosure;

fig. 7 is a schematic structural diagram of a tree structure corresponding to a routing table according to an embodiment of the present application;

fig. 8 is a schematic diagram of an integrated circuit 800 according to an embodiment of the present application;

fig. 9 is a schematic structural diagram of a cache apparatus 900 according to an embodiment of the present disclosure;

fig. 10 is a schematic structural diagram of a chip 1000 according to an embodiment of the present disclosure;

fig. 11 is a schematic structural diagram of an apparatus 1100 according to an embodiment of the present disclosure;

fig. 12 is a schematic structural diagram of an apparatus 1200 according to an embodiment of the present disclosure.

Detailed Description

The following describes a conventional technique and a caching method provided in an embodiment of the present application with reference to the drawings.

First, the basic structure of the apparatus including the cache will be described. Referring to fig. 1, a schematic diagram of a configuration of an apparatus 100 is shown. The device 100 comprises a processor 110 and a memory 120, the processor 110 comprising a processing unit 111 and a cache 112. The buffer 112 may be used to load data from the memory 120, and the processing unit 111 may be used to read data from the buffer 112 and process the data. Alternatively, when the processor 110 is packaged as a chip, the chip may be referred to as a Central Processing Unit (CPU).

The cache, called a cache memory (cache), is mostly composed of storage devices with high data exchange speed. In the embodiments of the present application, the cache may also be referred to as a temporary memory (temporary memory) or a temporary storage (temporary storage). The cache is connected to a processing unit inside the processor and a memory outside the processor, respectively, and may store part or all of data stored in the memory.

The memory may be divided into an external memory such as a Hard Disk Drive (HDD) and an internal memory such as a Synchronous Dynamic Random Access Memory (SDRAM) or a Double Data Rate SDRAM (DDR). The cache is a storage device such as a Static Random Access Memory (SRAM). During data exchange with the processor, the data exchange speed of the SRAM is higher than that of the DDR (or SDRAM), and the data exchange speed of the DDR is higher than that of the hard disk. When the network device stores part or all of the routing table through the cache, a routing table with empty content can be created in the cache. In the embodiment of the present application, the routing table stored in the cache may be referred to as a cache routing table, and the routing table stored in the memory may be referred to as a memory routing table.

When the processor determines that the destination IP address matches a routing prefix in the memory routing table, the processor may store the routing prefix and the routing information in the cache routing table. Thus, when the network device receives a new message and the destination IP address of the new message matches the stored routing prefix in the cache routing table, the processor may obtain the corresponding routing information from the cache routing table. Therefore, the data exchange speed between the processor and the cache is high, and the lookup speed of the routing table is improved. When the first n bits of the IP address are respectively consistent with the routing prefix, the IP address can be said to be matched with the routing prefix

Alternatively, the Cache routing table may include a Cache Tag (Cache Tag) entry and a Cache Data (Cache Data) entry. The cache tag entry may include a route prefix, and the cache data entry may be used to store route information. Accordingly, the correspondence between the cache tag item and the cache data item may represent the correspondence between the routing prefix and the routing information.

Considering that the network device needs to determine a routing prefix matching with the destination IP address according to the longest matching rule, the cache tag entry may further include a length (length, hereinafter referred to as len) of the routing prefix. Thus, when the destination IP address matches multiple routing prefixes in the routing table in the cache at the same time, the processor may determine the routing prefix with the longest length as the routing prefix matching the destination IP address.

For example. Assume that the network device has a network interface a and a network interface B, and a memory of the network device records a corresponding relationship between a routing prefix 0001010 and the network interface a, and a corresponding relationship between a routing prefix 0 and the network interface B.

If the network device receives the message M, and the destination IP address of the message M is 0001010010100010. The processor of the network device may first look up the routing prefix and routing information matching the destination IP address from the memory routing table. After determining that destination IP address 0001010010100010 matches routing prefix 0001011, the processor may store routing information (i.e., network interface a) corresponding to routing prefix 0001010, routing prefix 0001010, and routing prefix 0001010 in the cache routing table. The cache routing table may be as shown in table 1.

TABLE 1

Cache tag	Cache data
		0001010*，len＝7	A

The first row in table 1 indicates that the routing prefix 000101101 corresponds to the network interface a, so that the packet with the first bit of the destination IP address of 0 may be forwarded through the network interface a, for example, the packet with the destination IP address of 0001010010100010 may be forwarded through the network interface a.

If the network device receives the message N again, the destination IP address of the message N is 0001011010010001. Since the first 7 bits of the destination IP address are 0001011, which is inconsistent with the routing prefix 0001010, the processor of the network device may look up the routing prefix matching the destination IP address 0001011010010001 from the memory routing table. After determining that destination IP address 0001011010010001 matches routing prefix 0, the processor may store routing information (i.e., network interface a) corresponding to routing prefix 0, the length of routing prefix 0, and routing prefix 0 in the cache routing table. The cache routing table may be as shown in table 2.

TABLE 1

Cache tag	Cache data
		0001010*，len＝7	A
0*，len＝1	B

If the network device receives a packet with destination IP address 0001011011110100, the processor may determine that the packet corresponds to the routing prefix 0 since the first bit of the destination IP address is consistent with the routing prefix 0 and the first seven bits of the destination IP address are inconsistent with the routing prefix 0001010, and forward the packet through the network interface B. Obviously, since the processor has a fast speed of acquiring data from the cache, storing the correspondence between part or all of the routing prefixes and the routing information in the cache routing table can improve the speed of forwarding the packet by the network device.

However, since the information in the cache routing table is gradually increased along with the forwarding of the packet, in this process, the cache routing table and the memory routing table are not consistent. Then, if the longer routing prefix of the two routes with higher similarity is not stored in the cache routing table, and the shorter routing prefix is stored in the cache routing table, the processor may erroneously determine the shorter routing prefix as the routing prefix matching the packet, so as to forward the packet according to the wrong routing information, which is called a false hit.

For example, assume that the destination IP address of a packet matches a routing prefix X and a routing prefix Y, and the routing prefix X is already stored in the cache routing table, and the routing prefix Y is not stored in the cache routing table. If the length of the routing prefix X is shorter than that of the routing prefix Y, the routing information corresponding to the message should theoretically be the routing information corresponding to the routing prefix Y. However, after receiving the message, the processor preferentially searches the route prefix matched with the destination IP address from the cache route table. Because the cache routing table comprises the routing prefix X, the processor can find the routing prefix X matched with the destination IP address from the cache routing table, so that the message is forwarded by utilizing the routing information corresponding to the routing prefix X. It can be seen that, because the cache routing table is different from the routing prefixes stored in the memory routing table, a false hit may occur when the network device forwards a packet whose destination IP address matches with multiple routing prefixes.

Still take the example that the network device receives the message M and the message N as an example for explanation. Assuming that the network device receives packet N first, the cache routing table may be as shown in table 3:

TABLE 3

Cache tag	Cache data
			0*，len＝1	B

If the network device receives the packet M again, since the destination IP address of the packet M is 0001010010100010 and the first bit thereof is 0, the packet M is consistent with the routing prefix 0 recorded in the cache routing table, and the processor may consider that the packet M matches with the routing prefix 0, so that the packet M is forwarded by using the network interface B. Obviously, the network interface to which the message M actually corresponds should be the network interface a. There are false hits due to the insufficiency of the information included in the cache routing table.

In order to solve the above problem, an embodiment of the present application provides a caching method, which may record, in a cache, a correspondence between a first routing prefix whose length is greater than a length of a routing table and a destination IP address and routing information, so as to avoid occurrence of false hit.

Hereinafter, the terms referred to in the present application will first be briefly described:

and (3) tree structure: a tree structure is a non-linear data structure. A tree structure may include a plurality of nodes, each of which may be used to store data. The connection relationship between the nodes of the tree structure indicates the relationship between the data stored in the nodes, and may indicate, for example, the order relationship or the dependency relationship of the data. The topmost node in the tree structure is called the root node. A tree structure may include a plurality of sub-tree structures, each of which may in turn include one or more sub-tree structures. The topmost node of each subtree structure may be referred to as the root node of the subtree structure. Typical tree structures may include binary trees, ternary trees, and quadtrees.

In this embodiment of the present application, the routing prefix may be represented by a tree structure such as a binary tree, and a specific value of each bit of the routing prefix is represented by a connection relationship between two adjacent layers of nodes in the tree structure. Similarly, the routing table may also be represented by a tree structure by similar rules. For example, each routing prefix in the routing table may be represented by a tree structure, and root nodes of the tree structures are superimposed together, so that the finally obtained tree structure is the corresponding tree structure of the routing table. In order to distinguish the routing prefixes in the routing table, the node corresponding to the last bit of each routing prefix may be marked as a prefix node. A tree structure corresponding to the routing table may be used to represent the distribution of prefix nodes in the routing table.

In the embodiment of the present application, the routing prefix and the routing table may be represented by a binary tree, or may be represented by a quadtree or a hexadecimal tree. The binary tree is described below. It should be noted that, for convenience of understanding, the description will be made by taking the tree structure of the routing table as a binary tree, which does not mean that the tree structures of the routing table in all embodiments of the present application are binary trees. When the routing prefix is represented by a quadtree structure, each child node corresponds to a two-digit number in the routing prefix, e.g., the four child nodes of the root node may represent "00", "01", "10", and "11", respectively. If the routing table is represented by a tree structure, the tree structure can be split into a virtual tree structure and a plurality of sub-tree structures. The description of the virtual tree structure can be referred to below and will not be described herein.

Binary tree (binary tree): binary tree refers to an ordered tree in which the degree of a node in the tree structure is not more than 2. That is, the binary tree has one root node, and any one node in the binary tree has at most two child nodes, and when one node has two child nodes, the child node on the left side may be referred to as a left child node, and the child node on the right side may be referred to as a right child node. Any one node in the binary tree. A binary tree may include a plurality of sub-binary trees.

When the routing prefix is represented by a binary tree, each bit of the IP address corresponds to a level of the binary tree, starting with a child node of the root node. If a bit of the IP address is 0, the binary tree extends to the left in this layer, and if a bit of the routing prefix is 1, the binary tree extends to the right in this layer. That is, if the first bit of a routing prefix is 0, then the root node of the binary tree to which the routing prefix corresponds has a left child node and does not have a right child node.

For example, the tree structure corresponding to the routing prefix 10010 may be as shown in fig. 2. Wherein, the node 2 is the right child node of the root node 1, and the first bit of the connection representation IP address is 1; node 3 is the left child node of node 2, and the second bit of the connection indicating the IP address is 0; node 4 is the left child node of node 3, and the third bit of the connection representation IP address is 0; node 5 is the right child node of node 4, and the fourth bit of the connection representation IP address is 1; node 6 is the left child of node 5 and the fifth bit of the connection indicates an IP address of 0.

Similarly, when the routing table is represented by a binary tree, the routing table may be as shown in fig. 5. For this part, reference may be made to the following text and will not be described in detail here.

The independent node: a solitary node is a node in the binary tree that has only a left child node or only a right child node.

Leaf node: a leaf node is a node in the tree structure that does not have child nodes.

Prefix node: the prefix node is a node corresponding to the routing prefix in the tree structure corresponding to the routing table.

Searching a path: the search path is a path from the root node to the leaf node in the tree structure corresponding to the routing table along the tree structure corresponding to the destination IP address in the tree structure corresponding to the routing table.

Tail nodes: the tail node is the last node in the search path.

The method provided by the embodiment of the application can be applied to the system 300 shown in fig. 3-a. The system 300 includes a network device 310, a network device 320, a network device 330, and a network device 340.

In the present embodiment, network device 320 includes a processor 321, a cache 322, and a memory 323. The processor 321 is a unit with data processing capability inside the network device 320, and may be, for example, a unit in a processor core (core) for data processing, the cache 322 may be a high-speed storage device such as an SRAM, and the storage 323 may include any one or more of an internal memory and an external memory.

It should be noted that the cache 320 in fig. 3-a is independent of the processor 321, and does not mean that the cache provided in the embodiment of the present application is necessarily packaged in the processor. In some possible implementations, the cache may also be a storage device encapsulated inside the processor. In addition, in the embodiment shown in fig. 1, the network device 320 includes one processor 321 and one cache 322, which does not mean that the device provided in the embodiment of the present application only includes one processor and one cache. In some possible implementations, a device may include one or more processors, which may include one or more processing units, and one or more caches. One cache may correspond to one processing unit or a plurality of processing units, and one processing unit may also correspond to one or a plurality of caches. The embodiment of the present application does not limit the specific architecture of the processor.

In some possible implementations, the network device may have a multi-level cache structure, that is, multiple caches with different levels are constructed by using multiple storage media, and a cache with a higher level exchanges data faster and has a smaller size. Then, for a computer with a multi-level cache structure, the cache in the embodiment of the present application may be a first-level cache (the first-level cache is the highest-level cache), and the memory may include other caches with lower levels than the first-level cache, such as a second-level cache, a third-level cache, and the like. That is, in the embodiment of the present application, the cache is a storage device with the highest data exchange speed, and the memory is a generic term of all other storage devices with data exchange speeds lower than that of the cache.

In this embodiment of the present application, in order to facilitate fast lookup of a routing table entry, the cache may further include a Ternary Content Addressable Memory (TCAM), a register, a line card version, a grain, and other hardware modules.

Some application scenarios of the caching method provided in the embodiment of the present application are introduced below. It should be noted that the application scenarios provided in the embodiment of the present application are only some typical application scenarios, and do not mean that the caching method provided in the embodiment of the present application can only be used in these application scenarios.

Referring to fig. 3-b, this figure is a schematic structural diagram of a network device according to an embodiment of the present application. In the embodiment shown in fig. 3-b, network device 350 includes a processor 351, a TCAM352, and a memory 353. The processor 351 is connected to the TCAM352 and the memory 353, respectively. Memory 353 may be used to store a master routing table; the TCAM352 may be used as a cache for storing a cache routing table, or for searching for corresponding routing information according to a destination IP address; the processor 351 may be configured to store the routing prefix and the routing information into the TCAM352 according to the destination IP address, or forward the packet according to the routing information found by the TCAM 352.

Alternatively, when the network device has multiple processors, each processor may correspond to a respective TCAM, and the multiple processors may correspond to the same memory. In particular, referring to fig. 3-c, when network device 350 further includes processor 354, network device 350 may further include TCAM355. Processor 351 is coupled to TCAM355 and memory 353, respectively. TCAM355 may be used as a cache to store routing tables used by processor 354. Similarly, TCAM352 may be used to store routing tables used by processor 351. Thus, each processor has a relatively independent TCAM for storing its own required routing table, without storing all routing tables. Therefore, the storage space is saved, and the speed of reading the routing table by the processor is improved because the content stored in the TCAM is less. 3-c, the processor 351 may read data from TCAM352 faster than the processor 351 reads data from memory 353.

For the operation of TCAM352, reference may be made to the description of the embodiment in table 7, which will not be described herein again.

Alternatively, the function of the aforementioned TCAM may be implemented by a parallel comparison logic circuit and a register. Specifically, referring to FIG. 3-d, the role of TCAM352 in the embodiment of FIG. 3-b can be implemented by parallel compare logic 356 and register 357. The processor 351 is connected to a parallel comparison logic 356, and the parallel comparison logic 356 is connected to a register 357. Where register 357 is used to store routing tables and parallel comparison logic is used to determine routing information corresponding to the destination IP address.

Alternatively, in the embodiments illustrated in FIGS. 3-b, 3-c, and 3-d, processor 351 and/or processor 352 may refer to a processor core (core).

Referring to fig. 3-e, this figure is a schematic structural diagram of a network device according to an embodiment of the present application. In the embodiment shown in fig. 3-e, the network device 360 comprises a line card board 361, a line card board 362, a line card board 363, a switching network board 364, and a switching network board 365. The switching network board 364 is connected to the line card board 361, the line card board 362 and the line card board 363, and the switching network board 365 is connected to the line card board 361, the line card board 362 and the line card board 363.

In the embodiment shown in fig. 3-e, each line card board may include a cache for storing a cache routing table that the line card board needs to use. For example, the line card board 361 includes a cache 361-1 for storing a cache routing table required by the line card board 361; the cable card board 362 includes a cache 362-1 for storing a cache routing table required to be used by the cable card board 362; the line card board 363 comprises a cache 363-1 for storing a cache routing table needed by the line card board 363. The switching network board may store a routing table containing all routing information, i.e. the aforementioned main routing table. The master routing table may be stored in the switch board 364 and/or the switch board 352, or may be divided into two parts and stored in the switch board 364 and the switch board 352, respectively. Optionally, the master routing table may be stored in a cache of the switching screen.

Referring to fig. 3-f, the figure is a schematic structural diagram of a chip of a network device according to an embodiment of the present application. In the embodiment shown in fig. 3-f, chip 370 includes die (die) 371, die 372, die 373, and die 374. Grain 371 is connected to grain 372 and grain 374, and grain 373 is connected to grain 372 and grain 374. Of course, in some other implementations, the dies in the chip may be connected in other ways.

A cache may be included in any die in the chip. For example, grain 371 may include cache 371-1, grain 372 may include cache 372-1, grain 373 may include cache 373-1, and grain 374 may include cache 374-1. Any one or more of cache 371-1, cache 372-1, cache 373-1, and cache 374-1 may be used to store the cache routing table, and any one or more of the caches may be used to store the master routing table.

In an actual application scenario, a plurality of network devices may serve as one virtual router to forward a packet. For example, refer to fig. 3-g, which is a schematic structural diagram of a virtual router provided in an embodiment of the present application. In the embodiment shown in fig. 3-g, virtual router 380 includes network device 381, network device 382, network device 383, network device 384, and network device 385. Network device 383 is connected to network device 381, network device 382, network device 384, and network device 385, respectively. In the virtual router 380, the network device 385 can be used to store a master routing table, and the network device 381, the network device 382, the network device 384, and the network device 385 can respectively store a required cache routing table. Optionally, network device 383 may store the master routing table in a cache of network device 383.

Referring to fig. 4, fig. 4 is a data interaction diagram of a caching method according to an embodiment of the present application. The caching method provided by the embodiment of the application comprises the following steps:

s401: the processor obtains a first message.

In the embodiment of the present application, the processor may be a processor in a network device. For example, the processor may be the processor 321 in the network device 320 in fig. 3-a, or may be a processing unit in the processor 321 for processing data. The processor may receive the first message sent by the other device through the network interface, for example, when the processor is the processor 321 in fig. 3-a, the processor 321 may receive the first message sent by the network device 310. Of course, in some possible implementations, the processor may also receive the first message sent by the terminal device. Of course, the cache described below may be a cache in a network device, such as cache 322 in FIG. 3-a. The memory may be a memory in a network device. Such as memory 323 in fig. 3-a.

The IP address of the destination device of the first packet is referred to as the destination IP address of the first packet and indicates to which device the first packet needs to be sent. Then, after receiving the first packet, the processor may parse the first packet, thereby determining a destination IP address of the first packet.

S402: the processor looks up the routing prefix matching the destination IP address from the cache.

After determining the destination address of the first packet, the processor may look up a routing prefix matching the destination IP address from the cache, for example, the processor may look up a routing prefix matching the destination IP address from a cache routing table. When a plurality of routing prefixes matching the destination IP address exist in the cache routing table, the processor may determine the routing prefix having the longest length as the routing prefix matching the destination IP address. In some possible implementations, the processor may further convert the cache routing table into a corresponding tree structure such as a binary tree or a multi-way tree, and determine a routing prefix matching the destination IP address through the tree structure.

If the processor can find the routing prefix matched with the destination IP address from the cache, the processor can acquire the routing information corresponding to the destination IP address from the cache, so that the first message is forwarded through the routing information. If the processor can not find the route prefix matched with the destination IP address from the cache, the route prefix corresponding to the destination IP address is not stored in the cache route table. The processor may look up the routing prefix and routing information matching the destination IP address from the memory and update the cache routing table according to the found routing prefix and routing information.

Optionally, before updating the cache routing table, the processor may determine whether a storage space for storing the routing prefix and the routing information exists in the cache routing table. If the storage space of the cache is full, the processor may not update the cache routing table, or delete the routing prefix and the routing information already stored in the cache, so as to store the new routing prefix and the routing information by using the new storage space.

A method for a processor to update a cache routing table in the case where no routing prefix matching the destination IP address is included in the slave cache is described below.

S403: in response to the cache not storing the routing prefix, the processor looks up a prefix node and routing information corresponding to the destination IP address from memory.

If the route prefix corresponding to the destination IP address is not stored in the cache, the processor can search the route prefix and the route information corresponding to the destination IP address from the memory. Alternatively, the processor may determine the routing prefix corresponding to the destination IP address through a tree structure corresponding to the routing table. Then, the processor may determine a prefix node corresponding to the destination IP address from the tree structure corresponding to the routing table and acquire routing information of the prefix node.

The method by which the processor determines the prefix node is described below.

Assume that the routing table stored in memory is as shown in table 4

TABLE 5

Routing prefix	Routing information
			0*	Network interface X
11*	Network interface A
		0000*	Network interface B
0001010*	Network interface C
		00010111*	Network interface D
0001011111*	Network interface E
		00010110000*	Network interface F
00010110010*	Network interface G

A schematic diagram of the attribute structure corresponding to the routing table can be shown in fig. 5. Wherein the numbers within each node in figure 5 represent the node's number. Then, node 2 is a prefix node corresponding to routing prefix 0 ″; the node 2 is a prefix node and corresponds to a routing prefix 11; the node 7 is a prefix node corresponding to the routing prefix 0000 ″; the node 11 is a prefix node corresponding to a routing prefix 0001010; the node 14 is a prefix node corresponding to the routing prefix 00010111; the node 19 is a prefix node corresponding to the routing prefix 0001011111; the node 20 is a prefix node corresponding to the routing prefix 00010110000; node 21 is a prefix node corresponding to a routing prefix 00010110010.

If the destination IP address of the first packet is 0001011010010001, since the destination IP address is only matched with the routing prefix 0, the processor may determine that the prefix node corresponding to the destination IP address is node 2, and the corresponding routing information is network interface X. If the destination IP address of the first packet is 0001010010100010, the destination IP is matched with the routing prefix 0 × and the routing prefix 0001010 × and the length of the routing prefix 0001010 is greater than the length of the routing prefix 0 × the processor may determine that the prefix node corresponding to the destination IP address is the node 11 and the corresponding routing information is the network interface C.

In an actual application scenario, the number of correspondence relationships stored in the routing table is often large, and the corresponding tree structure is also complex. Then, in order to quickly find a prefix node corresponding to the destination IP address, the tree structure corresponding to the routing table may be split into a plurality of sub-tree structures, and the tree structure composed of root nodes of the sub-tree structures is referred to as a virtual tree structure. The root node of each subtree structure corresponds to a virtual prefix. The routing prefix represented by each node in the subtree structure can be determined based on the virtual prefix and the position of the node in the virtual tree structure. For example, if the virtual prefix of a certain subtree structure is 1000, the routing prefix corresponding to the right child node of the root node of the subtree structure is 10001.

When searching for the routing prefix corresponding to the destination IP address, the processor may first search for the virtual prefix that matches the destination IP address longest from the virtual tree structure, and determine the virtual prefix with the longest length from the virtual prefixes that match the destination IP address. The processor may then determine a prefix node from the subtree structure corresponding to the virtual prefix that matches the destination IP address. If no prefix node matched with the destination IP address exists in the subtree corresponding to the virtual prefix, the processor can determine the prefix node corresponding to the virtual prefix as the prefix node of the destination IP address.

For example. For the binary tree shown in FIG. 5, it can be partitioned into three subtree structures. The root nodes of the three subtree structures are root node 1, node 6 and node 12, respectively, and the virtual prefixes are star, 00 star and 0001011, respectively. Then, when the virtual tree structure is represented in the form of a table, the table may be as shown in table 6. The three subtrees may be as shown in fig. 6.

TABLE 6

Virtual prefix	Prefix length	Sub-tree information
			*	0	Subtree 0
00*	2	Subtree 1
			0001011*	7	Subtree 2

In the case that the first row of table 6 indicates that the virtual prefix with the length of 0 corresponds to subtree 0, that is, the destination IP address does not match with other virtual prefixes in table 6, the processor may determine a prefix node determined by the destination IP address from subtree 0. The second row of table 6 indicates that a virtual prefix 00 of length 2 corresponds to subtree 1. The third row of table 6 indicates that a length-7 virtual prefix 0001011 corresponds to subtree 2.

When receiving the first packet with the destination IP address 0001010010100010, the processor may search the subtree 1 for a prefix node matching the destination IP address because the destination IP address matches the virtual prefix 00 × longest. Since the routing prefix of node 11 in subtree 1 is 0001010 that matches the destination IP address, and node 11 is a prefix node, the processor may determine the routing prefix 0001010 as the routing prefix that matches the destination IP address 0001010010100010, and node 11 is the corresponding prefix node.

When receiving the first packet with the destination IP address 0001011010010001, the processor may search the subtree 1 for a prefix node matching the destination IP address because the destination IP address matches the virtual prefix 00 × longest. Since subtree 1 does not have a prefix node with a matching destination IP address, the processor may determine the prefix node corresponding to virtual prefix 00 as the prefix node corresponding to the destination IP address. Then the processor may determine that the prefix node matching the destination IP address 0001011010010001 is node 2 and the matching routing prefix is 0 x.

S404: and the processor determines a corresponding relation set according to the prefix node and the routing information.

After determining the prefix node and the routing information corresponding to the destination IP address, the processor may determine a set of correspondences based on the prefix node and the routing information. The correspondence set may include a correspondence between a routing prefix of the prefix node and the routing information, or may include a correspondence between a first routing prefix and the routing information. In this embodiment of the present application, the correspondence between the first routing prefix and the routing information may be referred to as a first correspondence. Specifically, when the prefix node matched with the destination IP address is a leaf node, the correspondence may include a correspondence between a routing prefix of the prefix node and the routing information; when the prefix node matching the destination IP address is not a leaf node, the correspondence may include a first correspondence. Reference is made to the following description of the first routing prefix.

These two cases will be described separately below.

In a first possible implementation, the prefix node matched with the destination IP address is a leaf node, that is, the tail node of the lookup path is a prefix node, and then the processor may determine that the correspondence is a correspondence between a routing prefix of the prefix node and the routing information.

Since a leaf node is a node that does not have a child node, the prefix node also does not have a child node. That is, among the one or more routing prefixes described in the routing table, there is no other routing prefix whose first n bits match the routing prefix and whose length is longer than n. Where n is the length of the routing prefix.

Still taking fig. 5 as an example for explanation, assuming that the destination IP address is 0001010010100010, the prefix node matching the destination IP address is node 11. Node 11 acts as a leaf node and has no children. If node 11 has a left child node or a right child node, then the left child node of node 11 corresponds to a routing prefix of 00010100 and the right child node of node 11 corresponds to a queue routing prefix of 00010101. Since these two child nodes do not exist, it is indicated that the routing table does not include two routing prefixes 00010100 and 00010101, and naturally does not include other routing prefixes with the first 7 bits being 0001010 and the length being greater than 7.

It can be seen that there are no other routing prefixes with the first n bits consistent with the routing prefix of the prefix node and the length greater than n (n is the length of the routing prefix) in the routing table. Naturally, the destination IP address that matches the routing prefix of the prefix node cannot match other routing prefixes of length greater than n. Therefore, after the routing prefix of the prefix node is stored in the cache routing table, a false hit condition can not occur, that is, a condition that the destination IP address should match a routing prefix with a length larger than n but the routing prefix stored in the cache routing table does not completely match the routing prefix can not occur.

Then, the processor may obtain, from the memory, the routing information corresponding to the routing prefix of the prefix node, so as to store, in a subsequent step, a correspondence between the routing prefix and the routing information in the cache.

In a second possible implementation, the prefix node matching the destination IP address is not a leaf node, i.e. the tail node of the lookup path is not a prefix node, and then the set of correspondences may include the first correspondences. In determining the first correspondence, the processor may first determine a first routing prefix. The first routing prefix is matched with the destination IP address, the length of the first routing prefix is determined according to the first prefix matching length, and the first prefix matching length is the length from a root node of the tree structure to a tail node of the search path, namely the number of nodes between the tail node and the root node of the search path is added with 1.

In this embodiment of the present application, the length of the first routing prefix may be greater than the first prefix matching length, may also be equal to the first prefix matching length, and may also be smaller than the first prefix matching length. The following description is made separately.

First, a case where the first routing prefix is larger than the first prefix matching length will be described.

In the tree structure corresponding to the routing table, because the prefix node corresponding to the destination IP address is not a leaf node, it indicates that the subtree of the prefix node includes other prefix nodes, that is, other routing prefixes including the routing prefix corresponding to the destination IP address exist in the cache routing table, and these routing prefixes are not matched with the destination IP address. Therefore, to avoid false hits, the processor may determine a routing prefix that matches the destination IP address, other than the tree structure to which the routing table corresponds, as the first routing prefix.

Specifically, the processor may select a portion having a length greater than the first prefix matching length from the destination IP address as the first routing prefix. The first prefix matching length is the length of a tail node of a search path from a root node of the tree structure to the destination IP address, that is, the length of a routing prefix corresponding to the tail node. Because the prefix node corresponding to the destination IP address is not a leaf node, and the tail node in the lookup path is not a prefix node, it is described that the tree structure corresponding to the destination IP address and the tree structure corresponding to the forwarding table are different from the position of the tail node. Therefore, the part with the length larger than the matching length of the first prefix is selected from the destination IP address as the first routing prefix, so that the tail node corresponding to the first routing prefix is ensured to be outside the tree structure corresponding to the forwarding table, namely the first routing prefix is not overlapped with any routing prefix in the tree structure corresponding to the routing table. In this way, the first routing prefix is not recorded in the routing table, and naturally, it is not possible to record other routing prefixes having a length longer than and including the first routing prefix. That is, assuming that the length of the first routing prefix is n, there are no other routing prefixes in the routing table whose first n bits are consistent with the destination IP address and whose length is greater than n. Naturally, any IP address that includes the first routing prefix may not match a routing prefix of length greater than n in the destination routing table. Therefore, after the routing prefix of the prefix node is stored in the cache routing table, a false hit condition can not occur, that is, a condition that the destination IP address should match a routing prefix with a length larger than n but the routing prefix stored in the cache routing table does not completely match the routing prefix can not occur.

The description is given by way of example in fig. 5. Assuming that the destination IP address is 0001011010010001, the routing prefix matching with the destination IP address is 0, and the lookup path of the destination IP address in the tree structure is "1-2-4-6-8-9-10-12-13". The tail node is node 13, and the first prefix matching length is 8. The part of the destination IP address outside the routing table is represented by a tree structure, and the resulting tree structure can be as shown in fig. 7. On the basis of the embodiment shown in fig. 5, the tree structure shown in fig. 7 is added with a node 22, a node 23, a node 24, a node 25, a node 26, a node 27, a packet node 28, and a node 29. These nodes correspond to bits 9-16, respectively, of the destination IP address. These nodes may also be referred to as virtual nodes since they do not exist in the corresponding tree structure of the routing table.

Because the virtual node is positioned at the part of the tree structure corresponding to the destination IP address, which is outside the tree structure of the routing table, the routing prefix corresponding to the virtual node is greater than the first prefix matching length. Therefore, when determining the first routing prefix, the processor may determine a routing prefix corresponding to any one of the virtual nodes as the first routing prefix. For example, the processor may determine a routing prefix corresponding to a virtual node directly connected to the tail node as the first routing prefix. In the embodiment shown in fig. 6, the processor may determine routing prefix 000101101 corresponding to node 22 as the first routing prefix having a length equal to the first prefix match length plus one. Of course, in some possible implementations, the processor may also determine a routing prefix corresponding to any other virtual node as the first routing prefix. For example, the routing prefix 00010110100 corresponding to the node 24 may be determined as the first routing prefix.

As can be seen from the foregoing description, when determining a prefix node matching a destination IP address, the processor may first determine a virtual prefix and a subtree structure corresponding to the destination IP address according to the virtual tree structure, and then determine the prefix node matching the destination IP address according to the subtree structure. Similarly, the processor may determine the first routing prefix through a virtual tree structure.

Specifically, it is assumed that the first length is a length from a root node of the virtual tree structure to a virtual prefix corresponding to the destination IP address, that is, a length of a virtual prefix matching the destination IP address, and the second length is a length from the virtual prefix to a tail node of the lookup path, that is, a length from the root node to the tail node in the subtree structure corresponding to the destination IP address. Since the search path of the destination IP address is from the root node of the virtual tree structure to the root node of the sub-tree structure corresponding to the virtual prefix, and then from the root node of the sub-tree structure to the tail node, the sum of the first length and the second length is the first prefix matching length. When determining the first routing prefix, the processor may determine the virtual prefix as a first half of the first routing prefix, and then select a part having a length greater than the second length from the destination IP address to determine as a second half of the first routing prefix.

Taking the embodiment shown in fig. 6 as an example, assuming that the destination IP address is 0001011010010001, the virtual prefix matching the destination IP address is the virtual prefix corresponding to the node 12, i.e., 0001011. The processor may determine the first 7 bits of the first routing prefix as 0001011. Since the end node of the destination IP address in the subtree 2 is the node 13, and the length from the node 12 to the node 13 is 1, that is, the second length is 1, the processor may intercept a portion with a length greater than 1 from the 8 th bit of the destination IP address as the second half of the first routing prefix. For example, the processor may use the 8 th bit and the 9 th bit of the destination IP address as the second half of the first routing prefix, and the resulting first routing prefix is 000101101.

The following describes the case where the length of the first routing prefix is equal to the first prefix match length.

In an actual application scenario, since the modification of the routing table may not be synchronized with the modification of the tree structure, the leaf nodes in the tree structure may not be prefix nodes. Then, when the prefix node corresponding to the destination IP address is not a leaf node, and the tail node of the lookup path of the destination IP address in the tree structure is a leaf node, the processor may determine the routing prefix corresponding to the leaf node as the first routing prefix. Thus, the length of the first routing prefix may also be equal to the first prefix match length.

Specifically, after a certain routing prefix in the routing table is deleted, a node (hereinafter referred to as node a) corresponding to the routing prefix in the tree structure may not be deleted yet. But node a is not a prefix node since the routing table has been modified. If node A does not have children, then node A is a leaf node in the tree structure that is not a prefix node.

For example, in the embodiment shown in fig. 5, it is assumed that route prefix 0000 is deleted from the routing table, but node 7 may still remain in the tree structure. Then the node 7 is a leaf node of the non-prefix node.

After receiving the first packet, if the destination IP address of the first packet is 0000101010101010, the routing prefix matched with the destination IP address is 0, the corresponding prefix node is node 2, the tail node of the lookup path is node 7, the routing prefix of node 7 is 0000, and the first prefix matching length is 4. Then the processor may determine the route prefix 0000 of node 7 as the first route prefix. It can be seen that in this case, the length of the first routing prefix coincides with the first prefix match length.

The following describes a case where the length of the first routing prefix is smaller than the first prefix matching length.

In some possible implementations, the length of the first routing prefix may also be smaller than the first prefix matching length and larger than the length of the routing prefix corresponding to the prefix node, that is, the length of the routing prefix matching the destination IP address in the memory routing table. That is, the nodes corresponding to the first route prefix in the tree structure are the nodes on the lower layer of the prefix node and the upper layer of the tail node in the search path. In this way, although the length of the first routing prefix is smaller than the first prefix matching length, since the length of the first routing prefix is still larger than the length of the routing prefix matching the destination IP address in the memory routing table, compared to the prior art, the cache stores the correspondence between the first routing prefix and the routing information, and the cache still can play a role in reducing the probability of false hits. It is readily understood that the longer the length of the first routing prefix, the less likely a false hit will occur. When the length of the first routing prefix is greater than the first prefix match length, the probability of a false hit is 0.

For example. Assuming that the destination IP address is 0001011010010001, the prefix node matched with the destination IP address is node 2, the length of the corresponding routing prefix is 1, the tail node is node 12, and the corresponding first prefix matching length is 8. Then the processor may use the first m bits of the destination IP address as the first routing prefix, where m is a positive integer greater than 1 and less than 8. For example, the processor may determine routing prefix 00010110 as the first routing prefix.

After determining the first routing prefix, the processor may search for routing information from a routing table stored in the memory according to the routing prefix matching the destination IP address, and determine a correspondence between the routing information and the first routing prefix as a first correspondence.

Optionally, when the processor determines a prefix node matching the destination IP address through the virtual tree structure, the correspondence relationship set may further include a third correspondence relationship. Wherein the third corresponding relationship may include the virtual prefix, the type of the virtual prefix, and information of the sub-tree structure. The virtual prefix is a virtual prefix matched with the destination IP address, and the information of the subtree structure is used for indicating which subtree the destination IP address corresponds to. The type of the virtual prefix is used for indicating that when the virtual prefix is hit, the corresponding sub-tree structure is searched according to the information of the sub-tree structure.

That is, after receiving a new packet, if the destination IP address of the packet matches the virtual prefix stored in the cache, the processor may search for the sub-tree structure corresponding to the virtual prefix according to the type of the virtual prefix, thereby determining the sub-tree structure corresponding to the virtual prefix according to the third correspondence, and further determining the routing prefix matching the destination IP address according to the sub-tree structure.

In order to improve the search efficiency, in some possible implementations, the set of correspondences may further include a second correspondence. The second correspondence is a correspondence between the second routing prefix and the routing information. The routing information is routing information of a routing prefix corresponding to the destination IP address of the first packet.

The method by which the processor determines the second routing prefix is described below.

After determining that the prefix node corresponding to the destination IP address is not a leaf node, the processor may determine, according to the tree structure, all dependent nodes subsequent to the prefix node in the lookup path, that is, nodes having only left child nodes or right child nodes. The processor may then determine the length of the routing prefix corresponding to the unique node as a second prefix match length. I.e., the second prefix match length is equal to the length from the root node of the tree structure to the solitary node. The processor may then determine a second routing prefix based on the second prefix match length and the destination IP address. Assuming that the second prefix match has a length of n, the processor may determine the first n of the destination IP address as the second routing prefix.

Because the unique node is a node behind the prefix node in the search path of the destination IP address, it is indicated that the routing prefix corresponding to any unique node is not in the cache routing table, and the prefix nodes corresponding to the packet matched with the unique node are all prefix nodes of the destination IP address. Therefore, the routing prefixes of the IP addresses matching the unique nodes are all the routing prefixes of the prefix nodes. And because the exclusive node is positioned on the searching path of the destination IP address, the destination IP address comprises the routing prefix of each exclusive node. Therefore, the second prefix matching length is determined according to the unique node, then the second routing prefix is selected from the destination IP address according to the second prefix matching length, and the obtained second routing prefix is matched with the routing information corresponding to the prefix node of the destination IP address. Therefore, the processor may record a correspondence between the second routing prefix and the routing information as a second correspondence, and add the set of correspondences for cache storage.

The embodiment shown in fig. 5 is still used as an example for illustration. After receiving the first packet with the destination IP address 0001011010010001, the processor may determine that the prefix node is node 2. The tail node is node 13, and the exclusive nodes between the prefix node and the tail node comprise node 4, node 8 and node 9. Wherein the second prefix matching length corresponding to the node 4 is 2, the second prefix matching length of the node 8 is 4, and the second prefix matching length of the node 9 is 5. Then, the processor may determine the first 2 bits, the first 4 bits, and the first 5 bits of the destination IP address as the second routing prefix, i.e., routing prefix 00, and both routing prefix 0001 and routing prefix 00010 are the second routing prefix. Next, the processor may determine a correspondence between the three routing prefixes and the routing information "network interface X" corresponding to the routing prefix 0 ×, as a second correspondence.

S405: and the processor triggers the cache to store the corresponding relation set.

After the correspondence set is obtained, the processor may trigger the cache to store the correspondence set. Optionally, the processor may further trigger the cache to store the length of the first routing prefix in consideration of a longest prefix matching principle.

In addition, when the first corresponding relation is included in the corresponding relation set, the processor may further trigger the cache to store the type of the first routing prefix. The type of the first routing prefix is used for indicating the processor to obtain routing information corresponding to the first routing prefix in the cache according to the first corresponding relation when the first routing prefix is hit. That is, after receiving a new packet, if the destination IP address of the packet matches the first routing prefix stored in the cache, the processor may search for the routing information corresponding to the first routing prefix from the cache routing table according to the type of the first routing prefix, without searching for the routing information corresponding to the first routing prefix from the memory.

The following describes a process of searching for corresponding routing information by using a TCAM destination IP address.

Assume that TCAM as a cache routing table stores a correspondence between a routing prefix 000101101 and a network interface X, and a correspondence between a routing prefix 0001011 and a routing prefix 0000 and a network interface B. Then the entries stored in the TCAM may be as shown in table 7.

TABLE 7

TCAM key	TCAM mask	TCAM AD
			000101101*	1111111110000000	Network interface X
0000*	1111000000000000	Network interface B

The first item of the header in table 7 is a TCAM mask (TCAM key) for recording a route prefix to be matched. The first entry in the header of table 7 is a TCAM mask (TCAM mask) for detecting the matching degree of the destination IP address and the TCAM key. The first entry in the header of table 7 is TCAM Associated Data (AD) for recording routing information corresponding to the TCAM key.

The first row in table 7 indicates that the TCAM can determine, through the TCAM mask 1111111110000000, whether the destination IP address of the packet matches the TCAM keyword 000101101, and send the packet through the network interface X after determining that the destination IP address matches the TCAM keyword 000101101. The second row in table 7 indicates that the TCAM can determine, through the TCAM mask 1111000000000000, whether the destination IP address of the packet matches the TCAM keyword 0000 ×, and send the packet through the network interface B after determining that the destination IP address matches the TCAM keyword 0000 ×.

When judging whether the destination IP address of the packet matches the TCAM keyword, the TCAM may perform a bit-by-bit and operation on the TCAM mask and the destination IP address, and perform a bit-by-bit and operation on the TCAM keyword and the TCAM mask. Finally, comparing the results obtained by the two operations bit by bit to determine whether the results are completely consistent. If the results obtained by the two operations are completely consistent, the TCAM can determine that the target IP address is matched with the TCAM keyword, so that the message is sent according to the routing information recorded in the TCAM associated data.

For example. Assuming that the network device receives a packet with a destination IP address of 0001011010010001, the processor may perform a bitwise and operation on the destination IP address 0001011010010001 and a TCAM keyword 1111111110000000 and a TCAM mask 11110000000000000000, respectively.

When carrying out bitwise AND operation, if the values of the destination IP address and the TCAM mask on a certain bit are both 1, the obtained result is 1, and if not, the obtained result is 0. For example, the first bit of the destination IP address is 0, the first bit of the tcam mask 1111111110000000 is 1, and the and operation between the two results in 0. The fourth bit of the destination IP address is 1, the fourth bit of the TCAM mask 1111111110000000 is 1, and the AND operation between the two results in 1.

By analogy, the result of performing a bitwise and operation on the destination IP address 0001011010010001 and the TCAM mask 1111111110000000 is 0001011010000000. The result of performing a bitwise and operation on the destination IP address 0001011010010001 and the TCAM mask 11110000000000000000 is 0001000000000000. Similarly, the result of performing a bitwise and operation on the TCAM keyword 000101101 and the TCAM mask 1111111110000000 is 0001011010000000. The result of performing a bitwise and operation on the TCAM keyword 0000 and the TCAM mask 1111111110000000 is 0000000000000000.

Then, because the result obtained by the operation of the destination IP address is completely consistent with the result obtained by the operation of the TCAM keyword 000101101, the TCAM can determine that the destination IP address matches with the routing prefix 000101101, and thus the message is sent through the network interface X. Because the result obtained by the operation according to the destination IP address is inconsistent with the result obtained by the operation according to the TCAM keyword 0000, the TCAM can determine that the destination IP address is not matched with the routing prefix 0000, and thus the message is not sent through the network interface B.

Referring to fig. 8, an embodiment of the present application further provides an integrated circuit 800, where the integrated circuit 800 may implement the functions of the processor in the embodiment shown in fig. 4. The integrated circuit includes an interface circuit 801 and a control circuit 802. The control circuit 801 and the interface circuit 802 are connected by a communication line 803. Interface circuit 802 is used to couple chip 800 to other devices via a communication link. The interface circuit 601 is configured to implement S401, S402, S403, and S405 in the embodiment shown in fig. 4, and the control circuit 802 is configured to implement S402, S403, S404, and S405 in the embodiment shown in fig. 4.

Specifically, the interface circuit 801 is configured to obtain a first packet, where the first packet includes a destination internet protocol IP address.

The control circuit 802 is configured to search a cache for a routing prefix matching the destination IP address; responding to the condition that the routing prefix is not stored in the cache, searching a tree structure corresponding to a routing table according to the destination IP address, and determining a prefix node matched with the destination IP address; in response to the prefix node not being a leaf node, determining a first prefix match length, the first prefix match length being equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure; determining a first routing prefix according to the first prefix matching length and the destination IP address; and triggering the cache to store a first corresponding relation, wherein the first corresponding relation is the first routing prefix and the routing information corresponding to the prefix node.

For a specific execution process, please refer to the detailed description of the corresponding steps in the embodiment shown in fig. 4, which is not repeated here.

Optionally, the integrated circuit 800 provided in this embodiment of the present application may further include a cache. The interface circuit 801 and the control circuit 802 in the integrated circuit 800 may be one or more.

For example, the integrated circuit 600 may be an FPGA (field programmable gate array), an ASIC (application specific integrated circuit), a system on chip (SoC), a CPU (central processing unit), an NP (NP), a Digital Signal Processing (DSP), a Micro Controller Unit (MCU), a Programmable Logic Device (PLD), or other integrated chips.

Referring to fig. 9, an embodiment of the present application further provides an apparatus 900, where the cache apparatus 900 may implement the function of the processor in the embodiment shown in fig. 4. The caching apparatus 900 includes an acquisition unit 901 and a processing unit 902. Wherein, the acquiring unit 901 is used to implement S401 in the embodiment shown in fig. 4, and the processing unit 402 is used to implement S402, S403, S404 and S405 in the embodiment shown in fig. 4.

Specifically, the obtaining unit 901 is configured to obtain a first message, where the first message includes a destination internet protocol IP address.

A processing unit 902, configured to search a cache for a routing prefix matching the destination IP address; responding to the condition that the routing prefix is not stored in the cache, searching a tree structure corresponding to a routing table according to the destination IP address, and determining a prefix node matched with the destination IP address; in response to the prefix node not being a leaf node, determining a first prefix match length equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure; determining a first routing prefix according to the first prefix matching length and the destination IP address; and triggering the cache to store a first corresponding relationship, wherein the first corresponding relationship is the first routing prefix and the routing information corresponding to the prefix node.

It should be noted that, in the embodiment of the present application, the division of the unit is schematic, and is only one logic function division, and when the actual implementation is realized, another division manner may be provided. Each functional unit in the embodiments of the present application may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit. For example, in the above embodiments, the acquiring unit and the processing unit may be the same unit or different units. The integrated unit may be implemented in the form of hardware, or may also be implemented in the form of a software functional unit.

Referring to fig. 10, an embodiment of the present application further provides a chip 1000, where the chip 1000 may implement the function of the processor in the embodiment shown in fig. 4. The chip includes a memory 1001 and a processor 1002. The memory 1001 is used for storing instructions or program codes, and the processor 1002 is used for calling and executing the instructions or program codes from the memory 1001 to implement S401, S402, S403, S404, and S405 in the embodiment shown in fig. 4.

Alternatively, the processor 1002 may be the integrated circuit 800 shown in fig. 8. The processor 1002 may include a cache. When the processor 1002 does not include a cache, the memory 1001 may include a cache.

Fig. 11 is a schematic structural diagram of an apparatus 1100 according to an embodiment of the present application. The apparatus in which the processor is located above may be implemented by an apparatus located as shown in fig. 11. Referring to fig. 11, the device 11900 includes at least one processor chip 1101 and at least one memory 1102. Optionally, the device 1100 may also include a communication bus 1103 and at least one network interface 1104.

The processor chip 1101 may be a general processing unit (CPU), an application-specific integrated circuit (ASIC), or one or more Integrated Circuits (ICs) for controlling the execution of programs according to the present disclosure. The processor chip 901 may be used to implement the data caching method provided in the embodiment of the present application.

For example, when the network device in fig. 1 is implemented by the device shown in fig. 11, the processor may be configured to obtain a first packet, where the first packet includes a destination internet protocol IP address; searching a route prefix matched with the destination IP address from a cache; responding to the condition that the routing prefix is not stored in the cache, searching a tree structure corresponding to a routing table according to the destination IP address, and determining a prefix node matched with the destination IP address; in response to the prefix node not being a leaf node, determining a first prefix match length, the first prefix match length being equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure; determining a first routing prefix according to the first prefix matching length and the destination IP address; and triggering the cache to store a first corresponding relationship, wherein the first corresponding relationship is the first routing prefix and the routing information corresponding to the prefix node.

Alternatively, the processor chip 1101 may be the chip 1000 in the embodiment shown in fig. 10, or may be the integrated circuit 800 in the embodiment shown in fig. 8. When the processor chip 1001 does not include a cache, the memory 1102 may include a cache, a memory, and an external memory; when processor chip 1101 includes a cache, the memory 1102 may include both memory and external memory.

Memory 1102 may be, but is not limited to, a read-only Memory (ROM) or other type of static storage device that may store static information and instructions, memory 902 may also be a Random Access Memory (RAM) or other type of dynamic storage device that may store information and instructions, a compact disk read-only Memory (CD-ROM) or other optical disk storage, optical disk storage (including compact disk, laser disk, optical disk, digital versatile disk, blu-ray disk, etc.), a magnetic disk storage medium or other magnetic storage device, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. The memory 1102, which may be self-contained, is coupled to the processor 1101 by a communication bus 1103. The memory 1102 may also be integrated with the processor 1101. Optionally, memory 1102 may include a cache.

Optionally, the memory 1102 is used for storing program codes or instructions for executing the present application, and is controlled by the processor 1101 for execution. The processor 1101 is used to execute program code or instructions stored in the memory 1102. One or more software modules may be included in the program code. Alternatively, the processor 1101 may also store program code or instructions for performing aspects of the present application, in which case the processor 1101 need not read the program code or instructions into the memory 1102.

Alternatively, memory 1102 may be used to implement the functions of memory 120 in the device shown in FIG. 1.

The communication bus 1103 is used to transfer information between the processor chip 1101, the network interface 1104 and the memory 1102.

Network interface 1104 may be a transceiver or the like for communicating with other devices or a communication network, such as an ethernet, radio Access Network (RAN), or Wireless Local Area Network (WLAN), etc. In this embodiment, the network interface 904 may be configured to receive packets sent by other nodes in the segment routing network, and may also send packets to other nodes in the segment routing network. The network interface 1104 may be an ethernet (ethernet) interface, a Fast Ethernet (FE) interface, a Gigabit Ethernet (GE) interface, or the like.

In particular implementations, device 1100 may include multiple processor chips, such as processor chip 1101 and processor chip 1105 as shown in FIG. 9, for example, as an embodiment. Each of these processor chips may be a single-core (single-CPU) processor or a multi-core (multi-CPU) processor. Alternatively, different steps in the caching method shown in fig. 4 may be performed by different processor chips. A processor chip herein may refer to one or more devices, circuits, and/or processing cores for processing data (e.g., computer program instructions).

Fig. 12 is a schematic structural diagram of an apparatus 1200 according to an embodiment of the present disclosure. The apparatus 100 in fig. 1 may be implemented by the apparatus shown in fig. 12. Referring to the schematic diagram of the device structure shown in fig. 12, the device 1200 includes a main control board and one or more interface boards. The main control board is in communication connection with the interface board. The main control board is also called a Main Processing Unit (MPU) or a route processor card (route processor card), and includes a CPU and a memory, and is responsible for controlling and managing each component in the device 1000, including routing calculation, device management, and maintenance functions. An interface board is also called a Line Processing Unit (LPU) or a line card (line card) and is used for receiving and transmitting messages. In some embodiments, the master control board communicates with the interface board or the interface board communicates with the interface board through a bus. In some embodiments, the interface boards communicate with each other through a switch board, in which case the apparatus 1200 also includes a switch board, the switch board is communicatively connected to the main control board and the interface boards, the switch board is used to forward data between the interface boards, and the switch board may also be referred to as a Switch Fabric Unit (SFU). An interface board includes a CPU, memory, forwarding engine, and Interface Cards (ICs), which may include one or more network interfaces. The network interface can be an Ethernet interface, an FE interface or a GE interface. The CPU is in communication connection with the memory, the forwarding engine and the interface card respectively. The memory is used for storing a forwarding table. The forwarding engine is configured to forward the received message based on a forwarding table stored in the memory, and if a destination address of the received message is the IP address of the device 1200, send the message to a CPU of the main control board or the interface board for processing; if the destination address of the received message is not the IP address of the device 1200, the forwarding table is searched according to the destination, and if the next hop and the outbound interface corresponding to the destination address are found from the forwarding table, the message is forwarded to the outbound interface corresponding to the destination address. The forwarding engine may be a Network Processor (NP). The interface card, also called a daughter card, may be installed on the interface board, and is responsible for converting the photoelectric signal into a data frame, and forwarding the data frame to the forwarding engine for processing or the CPU of the interface board after performing validity check on the data frame. In some embodiments, the CPU may also perform the functions of a forwarding engine, such as implementing soft forwarding based on a general purpose CPU, so that no forwarding engine is required in the interface board. In some embodiments, the forwarding engine may be implemented by an ASIC or a Field Programmable Gate Array (FPGA). In some embodiments, the memory storing the forwarding table may also be integrated into the forwarding engine as part of the forwarding engine.

Optionally, the system on a chip may have one or more processors. The processor may be implemented by hardware or by software. When implemented in hardware, the processor may be a logic circuit, an integrated circuit, or the like. When implemented in software, the processor may be a general-purpose processor implemented by reading software code stored in a memory. Optionally, the memory in the system-on-chip may also be one or more. The memory may be integrated with the processor or may be separate from the processor, which is not limited in this application. For example, the memory may be a non-transitory processor, such as a read only memory ROM, which may be integrated with the processor on the same chip or separately disposed on different chips, and the type of the memory and the arrangement of the memory and the processor are not particularly limited in this application.

The system on chip may be, for example, an FPGA, an ASIC, a system on chip (SoC), a CPU, an NP, a digital signal processing circuit (DSP), a Micro Controller Unit (MCU), a Programmable Logic Device (PLD) or other integrated chips.

It should be understood that the steps of the above method embodiments may be performed by integrated logic circuits of hardware in a processor or instructions in the form of software. The steps of the method disclosed in connection with the embodiments of the present application may be directly implemented by a hardware processor, or may be implemented by a combination of hardware and software modules in a processor.

Embodiments of the present application further provide a computer-readable storage medium, which includes instructions that, when executed on a computer, cause the computer to perform the caching method provided by the above method embodiments and executed by a processor.

Embodiments of the present application further provide a computer program product containing instructions, which when run on a computer, cause the computer to execute the caching method provided by the above method embodiments and executed by a processor.

The terms "first," "second," "third," "fourth," and the like in the description and in the claims of the present application and in the drawings described above, if any, are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It will be appreciated that the data so used may be interchanged under appropriate circumstances such that the embodiments described herein may be practiced otherwise than as specifically illustrated or described herein. Furthermore, the terms "comprises," "comprising," and "having," and any variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method, system, article, or apparatus that comprises a list of steps or elements is not necessarily limited to those steps or elements expressly listed, but may include other steps or elements not expressly listed or inherent to such process, method, article, or apparatus.

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

In the several embodiments provided in the present application, it should be understood that the disclosed system, apparatus and method may be implemented in other manners. For example, the above-described apparatus embodiments are merely illustrative, and for example, the division of the units is only one type of logical module division, and other division manners may be available in actual implementation, for example, a plurality of units or components may be combined or may be integrated into another system, or some features may be omitted, or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or units, and may be in an electrical, mechanical or other form.

The units described as separate parts may or may not be physically separate, and parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units can be obtained according to actual needs to achieve the purpose of the solution of the present embodiment.

In addition, each module unit in the embodiments of the present application may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit. The integrated unit can be realized in a hardware mode, and can also be realized in a software module unit mode.

The integrated unit, if implemented as a software module unit and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on such understanding, the technical solutions of the present application, which are essential or part of the technical solutions contributing to the prior art, or all or part of the technical solutions, may be embodied in the form of a software product, which is stored in a storage medium and includes several instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods described in the embodiments of the present application. And the aforementioned storage medium includes: various media capable of storing program codes, such as a usb disk, a removable hard disk, a Read-Only Memory (ROM), a Random Access Memory (RAM), a magnetic disk, or an optical disk.

Those skilled in the art will recognize that, in one or more of the examples described above, the functions described in this invention may be implemented in hardware, software, firmware, or any combination thereof. When implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Computer-readable media includes both computer storage media and communication media including any medium that facilitates transfer of a computer program from one place to another. A storage media may be any available media that can be accessed by a general purpose or special purpose computer.

The above-described embodiments are intended to explain the objects, aspects and advantages of the present invention in further detail, and it should be understood that the above-described embodiments are merely exemplary embodiments of the present invention.

The above embodiments are only used for illustrating the technical solutions of the present application, and not for limiting the same; although the present application has been described in detail with reference to the foregoing embodiments, it should be understood by those of ordinary skill in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some technical features may be equivalently replaced; and the modifications or the substitutions do not make the essence of the corresponding technical solutions depart from the scope of the technical solutions of the embodiments of the present application.

Claims

1. A caching method, the method comprising:

a processor acquires a first message, wherein the first message comprises a destination Internet Protocol (IP) address;

the processor searches a route prefix matched with the destination IP address from a cache;

in response to the fact that the routing prefix is not stored in the cache, the processor searches a tree structure corresponding to a routing table according to the destination IP address, and determines a prefix node matched with the destination IP address;

in response to the prefix node not being a leaf node, the processor determining a first prefix match length, the first prefix match length equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure;

the processor determines a first routing prefix according to the first prefix matching length and the destination IP address;

and the processor triggers the cache to store a first corresponding relation, wherein the first corresponding relation is the first routing prefix and the routing information corresponding to the prefix node.

2. The method of claim 1, wherein the length of the first routing prefix is greater than or equal to the first prefix match length.

3. The method of claim 1 or 2, wherein the processor searches a tree structure corresponding to a routing table according to the destination IP address, and wherein determining a prefix node matching the destination IP address comprises:

the processor searches a virtual tree structure corresponding to a routing table according to the destination IP address, and determines a virtual prefix which is longest matched with the destination IP address;

the processor searches a subtree structure corresponding to the virtual prefix according to the destination IP address, and determines a prefix node matched with the destination IP address, wherein the virtual prefix is a root node of the subtree structure;

the first prefix matching length is equal to the sum of a first length and a second length, the first length is from a root node of the virtual tree structure to the virtual prefix, the second length is from the virtual prefix to a tail node, and the tail node is the last node on a search path of the sub-tree structure.

4. The method according to claim 1 or 2, characterized in that the method further comprises:

responsive to the prefix node not being a leaf node, the processor determining a second prefix match length, the second prefix match length equal to a length between a root node of the tree structure to a dependent node, the dependent node being a node between the prefix node to the tail node having only a left child node or only a right child node;

the processor determines a second routing prefix according to the second prefix matching length and the destination IP address, wherein the length of the second routing prefix is greater than the second prefix matching length;

and the processor triggers the cache to store a second corresponding relationship, wherein the second corresponding relationship is the second routing prefix and the routing information corresponding to the prefix node.

5. The method according to any one of claims 1-4, further comprising:

the processor triggers the cache to store the type of the first routing prefix, where the type of the first routing prefix is used to indicate that, when the first routing prefix is hit, routing information corresponding to the first routing prefix is obtained in the cache according to the first corresponding relationship.

6. The method of claim 3, further comprising:

the processor triggers the cache to store a third corresponding relationship, where the third corresponding relationship is a corresponding relationship among the virtual prefix, the type of the virtual prefix, and information of the sub-tree structure, and the type of the virtual prefix is used to indicate that the sub-tree structure is searched according to the information of the sub-tree structure when the virtual prefix is hit.

7. The method according to any one of claims 1-6, further comprising:

the processor triggers the cache to store the length of the first routing prefix.

8. The method of claim 2, wherein the length of the first routing prefix is equal to the first prefix match length plus 1.

9. The method according to any of claims 1-8, wherein the length of the first routing prefix is smaller than the length of the destination IP address.

10. The method according to any of claims 1-9, wherein said destination IP address comprises said first routing prefix.

11. The method of any of claims 1-10, wherein the caching comprises at least one of:

ternary content addressable memory TCAM, registers, wire-bound board and die.

12. An integrated circuit, comprising an interface circuit and a control circuit;

the interface circuit is used for acquiring a first message, wherein the first message comprises a destination Internet Protocol (IP) address;

the control circuit is used for searching a route prefix matched with the destination IP address from a cache; responding to the condition that the routing prefix is not stored in the cache, searching a tree structure corresponding to a routing table according to the destination IP address, and determining a prefix node matched with the destination IP address; in response to the prefix node not being a leaf node, determining a first prefix match length, the first prefix match length being equal to a length between a root node to a tail node of the tree structure, the tail node being a last node on a lookup path of the tree structure; determining a first routing prefix according to the first prefix matching length and the destination IP address; and triggering the cache to store a first corresponding relation, wherein the first corresponding relation is the first routing prefix and the routing information corresponding to the prefix node.

13. The integrated circuit of claim 12, wherein the length of the first routing prefix is greater than or equal to the first prefix matching length.

14. The integrated circuit of claim 12 or 13,

the control circuit is used for searching a virtual tree structure corresponding to a routing table according to the destination IP address and determining a virtual prefix which is longest matched with the destination IP address; searching a subtree structure corresponding to the virtual prefix according to the destination IP address, and determining a prefix node matched with the destination IP address, wherein the virtual prefix is a root node of the subtree structure; the first prefix matching length is equal to the sum of a first length and a second length, the first length is the length from a root node of the virtual tree structure to the virtual prefix, the second length is the length from the virtual prefix to a tail node, and the tail node is the last node on a search path of the sub-tree structure.

15. The integrated circuit of claim 12 or 13,

the control circuitry further to determine a second prefix match length in response to the prefix node not being a leaf node, the second prefix match length equal to a length between a root node of the tree structure and a dependent node, the dependent node being a node between the prefix node and the tail node that has only a left child node or only a right child node; determining a second routing prefix according to the second prefix matching length and the destination IP address, wherein the length of the second routing prefix is greater than the second prefix matching length; and triggering the cache to store a second corresponding relationship, wherein the second corresponding relationship is the second routing prefix and the routing information corresponding to the prefix node.

16. The integrated circuit of any of claims 12-15,

the control circuit is further configured to trigger the cache to store a type of the first routing prefix, where the type of the first routing prefix is used to indicate that, when the first routing prefix is hit, routing information corresponding to the first routing prefix is obtained in the cache according to the first corresponding relationship.

17. The integrated circuit of claim 14,

the control circuit is further configured to trigger the cache to store a third corresponding relationship, where the third corresponding relationship is a corresponding relationship among the virtual prefix, a type of the virtual prefix, and information of the sub-tree structure, and the type of the virtual prefix is used to indicate that the sub-tree structure is searched according to the information of the sub-tree structure when the virtual prefix is hit.

18. The integrated circuit of any of claims 12-17,

the control circuit is further configured to trigger the cache to store the length of the first routing prefix.

19. The integrated circuit of claim 13, wherein the length of the first routing prefix is equal to the first prefix matching length plus 1.

20. The integrated circuit of any of claims 12-19, wherein a length of the first routing prefix is less than a length of the destination IP address.

21. The integrated circuit of any of claims 12-20, wherein the destination IP address comprises the first routing prefix.

22. The ic of any one of claims 12-21 wherein the cache includes at least one of:

ternary content addressable memory TCAM, registers, wire-bound board and die.

23. A chip, characterized in that it comprises a memory for storing instructions or program code and a processor for calling up and running said instructions or program code from the memory to perform the caching method according to any one of claims 1 to 11.

24. A device comprising a processor chip and a memory for storing instructions or program code, the processor chip being adapted to retrieve from the memory and execute said instructions or program code to perform a caching method according to any one of claims 1 to 11.

25. A computer-readable storage medium comprising instructions, programs or code which, when executed on a computer, cause the computer to perform a caching method according to any one of claims 1 to 11.