CN119003385B

CN119003385B - A table item storage, search method, device, network equipment and storage medium

Info

Publication number: CN119003385B
Application number: CN202411482797.3A
Authority: CN
Inventors: 杨逸
Original assignee: Gechuang Communication Zhejiang Co ltd
Current assignee: Gechuang Communication Zhejiang Co ltd
Priority date: 2024-10-23
Filing date: 2024-10-23
Publication date: 2025-02-25
Anticipated expiration: 2044-10-23
Also published as: CN119003385A

Abstract

The embodiment of the present application provides a table item storage, search method, device, network equipment and storage medium, which relates to the field of communication technology. The method includes: obtaining a first address to be stored and a first search result associated with the first address; storing the first address in a first table item in a first lookup table, the first lookup table is used to store addresses; searching for a second table item storing the first search result in a second lookup table, the second lookup table is used to store the search result; if the second table item is found, the second table item is associated with a third table item associated with the first address stored in the first table item in a third lookup table, the third lookup table is used to store the mapping relationship between the address and the search result. Applying the technical solution provided in the embodiment of the present application, more table items can be stored using limited SRAM capacity, providing larger table item specifications.

Description

Table entry storage and searching method and device, network equipment and storage medium

Technical Field

The present application relates to the field of communications technologies, and in particular, to a method and apparatus for storing and searching an entry, a network device, and a storage medium.

Background

In order to match the forwarding capability of the forwarding chip in the network device, static Random-Access Memory (SRAM) is mostly used to store entries, such as an entry for storing an address, and an entry for storing a search result. The limited capacity of SRAM is a problem to be solved, how to use the limited capacity of SRAM to store more entries and provide larger entry specification.

Disclosure of Invention

The embodiment of the application aims to provide a table entry storage and searching method, a device, network equipment and a storage medium, so that more table entries can be stored by using limited SRAM capacity, and larger table entry specifications can be provided. The specific technical scheme is as follows:

in a first aspect, an embodiment of the present application provides a method for storing an entry, where the method includes:

acquiring a first address to be stored and a first search result associated with the first address;

Storing the first address to a first entry in a first lookup table, the first lookup table being used to store the address;

searching a second table item storing the first searching result in a second searching table, wherein the second searching table is used for storing the searching result;

And if the second table entry is found, associating the second table entry with a third table entry associated with the first address stored in the first table entry in a third lookup table, where the third lookup table is used to store a mapping relationship between the address and the lookup result.

In some embodiments, the method further comprises:

if the second table entry is not found, creating the second table entry in the second lookup table;

storing the first search result to the second table entry;

And executing the step of associating the second table entry with a third table entry in a third lookup table, wherein the third table entry associates the second table entry with the first address stored in the first table entry.

In some embodiments, the first index corresponding to the first address is stored in the first table, and the step of associating the second table entry with a third table entry in a third lookup table associated with the first address stored in the first table entry comprises:

And storing a second index of the second table entry to a third table entry in the third lookup table at the first index.

In some embodiments, the second lookup table is further configured to store a summary of the lookup result, and the step of looking up a second entry in the second lookup table that stores the first lookup result includes:

Calculating a first abstract of the first search result;

Searching a candidate table item for storing the first abstract in a second lookup table;

if the candidate list item is found, judging whether the candidate list item stores the first search result or not;

And if the first search result is stored, taking the candidate table entry as a second table entry.

In some embodiments, the method further comprises:

And if the candidate list item is not searched, or the first search result is not stored in the candidate list item, determining that the second list item is not searched.

In some embodiments, the method further comprises:

Acquiring a deleting instruction, wherein the deleting instruction is used for indicating to delete the first address;

deleting the first address, and deleting the association relation between the second table item and the third table item.

In some embodiments, the method further comprises:

Acquiring a modification instruction, wherein the modification instruction is used for indicating modification of the search result associated with the first address into a second search result;

searching a fourth table item storing the second searching result in the second searching table;

And if the fourth table entry is found, deleting the association relation between the second table entry and the third table entry, and associating the fourth table entry with the third table entry associated with the first address in the third lookup table.

In some embodiments, the second lookup table is further used for storing the address number of the multiplexing lookup result, and the step of deleting the association relationship between the second table entry and the third table entry includes:

Acquiring the second table entry and the third table entry associated with the first address through the third lookup table and the second lookup table;

Deleting the third table entry;

if the number of the addresses stored in the second table entry is greater than 1, subtracting 1 from the number of the addresses stored in the second table entry; and deleting the second table entry if the number of addresses stored in the second table entry is equal to 1.

In a second aspect, an embodiment of the present application provides a method for searching an entry, where the method includes:

Acquiring a second address to be searched;

Searching a fifth table entry for storing a third address in a first lookup table, wherein the third address is matched with the second address, and the first lookup table is used for storing the address;

Obtaining a sixth table item associated with a third address stored in the fifth table item in a third lookup table, wherein the third lookup table is used for storing the mapping relation between the address and a lookup result;

Obtaining a seventh table item associated with the sixth table item in a second lookup table, wherein the second lookup table is used for storing a lookup result;

and taking the lookup result stored in the seventh table entry as a third lookup result associated with the second address.

The step of obtaining a sixth table entry associated with a third address stored in the fifth table entry in the third lookup table comprises obtaining a sixth table entry at the third index in the third lookup table;

The step of obtaining the seventh entry associated with the sixth entry in the second lookup table includes obtaining the seventh entry at a fourth index stored in the sixth entry in the second lookup table.

In a third aspect, an embodiment of the present application provides an entry storage apparatus, where the apparatus includes:

The first acquisition module is used for acquiring a first address to be stored and a first search result associated with the first address;

The storage module is used for storing the first address to a first table entry in a first lookup table, and the first lookup table is used for storing the address;

The first lookup module is used for looking up a second table item for storing the first lookup result in a second lookup table, and the second lookup table is used for storing the lookup result;

And the association module is used for associating the second table item with a third table item associated with the first address stored in the first table item in a third lookup table if the second table item is found, and the third lookup table is used for storing the mapping relation between the address and the lookup result.

In some embodiments, the association module is further configured to:

storing the first search result to the second table entry;

In some embodiments, the first table entry stores a first index corresponding to the first address, and the association module is specifically configured to:

In some embodiments, the second lookup table is further configured to store a summary of the lookup result, and the storage module is specifically configured to:

Calculating a first abstract of the first search result;

In some embodiments, the memory module is further configured to:

In some embodiments, the apparatus further comprises a deletion module for:

In some embodiments, the apparatus further comprises a modification module for:

In some embodiments, the second lookup table is further configured to store a number of addresses of the multiplexed lookup result, and the deletion module or the modification module is specifically configured to:

Deleting the third table entry;

In a fourth aspect, an embodiment of the present application provides an entry lookup apparatus, where the apparatus includes:

the second acquisition module is used for acquiring a second address to be searched;

The second lookup module is used for looking up a fifth table item for storing a third address in the first lookup table, the third address is matched with the second address, and the first lookup table is used for storing the addresses;

The third acquisition module is used for acquiring a sixth table item associated with a third address stored in the fifth table item in a third lookup table, and the third lookup table is used for storing the mapping relation between the address and the lookup result;

a fourth obtaining module, configured to obtain a seventh entry associated with the sixth entry in a second lookup table, where the second lookup table is used to store a lookup result;

and the obtaining module is used for taking the searching result stored in the seventh table entry as a third searching result associated with the second address.

In some embodiments, a third index corresponding to the third address is stored in the fifth table entry; the third obtaining module is specifically configured to obtain a sixth entry at the third index in the third lookup table;

The fourth obtaining module is specifically configured to obtain a seventh entry at a fourth index stored in the sixth entry in the second lookup table.

In a fifth aspect, an embodiment of the present application provides a network device, including a processor, a communication interface, a memory, and a communication bus, where the processor, the communication interface, and the memory complete communication with each other through the communication bus;

A memory for storing a computer program;

A processor, configured to implement the method according to any one of the first aspect or the second aspect when executing a program stored in a memory.

In a sixth aspect, embodiments of the present application provide a computer readable storage medium having a computer program stored therein, which when executed by a processor implements the method of any of the first or second aspects.

In a seventh aspect, embodiments of the present application provide a computer program product comprising instructions which, when run on a computer, cause the computer to perform the method of any of the first or second aspects of the embodiments described above.

The embodiment of the application has the beneficial effects that:

In the technical scheme provided by the embodiment of the application, after the first address is stored in the first table entry, the first search result related to the first address is searched in the stored search results, namely, the second table entry storing the first search result is searched. If the second table item is found, the first lookup result is stored in the second lookup table, the first lookup result can be directly multiplexed, the association relation between the second table item and a third table item associated with the first address is established, the association between the first address and the first lookup result is realized, and the table item storing the first lookup result does not need to be newly created. In the subsequent searching process, the searching result of the address association to be searched can be determined only according to the table items of the address association to be searched in the third searching table and the second searching table. By applying the technical scheme provided by the embodiment of the application, the search result to be stored is searched first, and whether the search result to be stored is stored in the second search table or not is determined. Therefore, the same search result is only required to be stored once in the second search table, the storage space required for storing the search result is saved, the second search table is compressed, the storage space waste caused by repeatedly storing the search result is reduced, more table items can be stored by using the limited SRAM capacity, and larger table item specifications are provided.

Of course, it is not necessary for any one product or method of practicing the application to achieve all of the advantages set forth above at the same time.

Drawings

In order to more clearly illustrate the embodiments of the application or the technical solutions in the prior art, the drawings used in the embodiments or the description of the prior art will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments of the application, and other embodiments may be obtained according to these drawings to those skilled in the art.

FIG. 1 is a first flowchart of a method for storing an entry according to an embodiment of the present application;

FIG. 2 is a second flowchart of a method for storing an entry according to an embodiment of the present application;

FIG. 3 is a third flowchart of a method for storing an entry according to an embodiment of the present application;

FIG. 4 is a schematic flow chart of a method for searching table entries according to an embodiment of the present application;

FIG. 5 is a schematic diagram of a first structure of an entry according to an embodiment of the present application;

FIG. 6 is a schematic diagram of a second structure of an entry according to an embodiment of the present application;

FIG. 7 is a schematic diagram of a structure of an entry storage device according to an embodiment of the present application;

FIG. 8 is a schematic diagram of a table entry searching device according to an embodiment of the present application;

fig. 9 is a schematic structural diagram of a network device according to an embodiment of the present application.

Detailed Description

The following description of the embodiments of the present application will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present application, but not all embodiments. Based on the embodiments of the present application, all other embodiments obtained by the person skilled in the art based on the present application are included in the scope of protection of the present application.

In order to match the forwarding capability of the forwarding chip in the network device, SRAM is mostly used to store entries, such as an entry for storing an address, and an entry for storing a search result. Currently, the table entry specification is larger and larger, for example, when the longest prefix matching (Longest Prefix Match, LPM) algorithm is adopted to forward the message, the table entry specification needs to reach 1.5 megameters (M) or even more than 2M. And the capacity of the SRAM is limited due to the area and cost of the forwarding chip. Therefore, how to store more entries with limited SRAM capacity and provide larger entry specifications is a problem to be solved.

In order to solve the above problems, the embodiment of the present application provides a method for storing an entry, which can be applied to network devices such as routers and switches, and can also be applied to forwarding chips in the network devices, and for convenience of description, the network devices are used as execution bodies in the following steps, and the method is not limited. Referring to fig. 1, a first flowchart of a table entry storage method according to an embodiment of the present application is shown. The table entry storage method comprises the following steps.

Step S11, a first address to be stored and a first search result associated with the first address are obtained.

Step S12, the first address is stored in a first table entry in a first lookup table, and the first lookup table is used for storing the address.

Step S13, a second table item for storing the first lookup result is searched in a second lookup table, and the second lookup table is used for storing the lookup result. If the second entry is found, step S14 is performed.

Step S14, the second table item is associated with a third table item associated with the first address stored in the first table item in a third lookup table, and the third lookup table is used for storing the mapping relation between the address and the lookup result.

In the technical scheme provided by the embodiment of the application, after the network equipment stores the first address into the first table entry, the first search result associated with the first address is searched in the stored search results, namely, the second table entry storing the first search result is searched. If the second table item is found, the network device can directly multiplex the first lookup result to establish an association relationship between the second table item and a third table item associated with the first address, so that the association between the first address and the first lookup result is realized, and the table item storing the first lookup result does not need to be newly created. In the subsequent searching process, the network equipment can determine the searching result of the address association to be searched only according to the table items of the address association to be searched in the third searching table and the second searching table. By applying the technical scheme provided by the embodiment of the application, the network equipment firstly searches the search result to be stored and determines whether the search result to be stored is stored in the second search table. Therefore, the same search result is only required to be stored once in the second search table, the storage space required for storing the search result is saved, the second search table is compressed, the storage space waste caused by repeatedly storing the search result is reduced, more table items can be stored by using the limited SRAM capacity, and larger table item specifications are provided.

In the step S11, the first address is any address to be stored by the network device. The address to be stored by the network device may be an internet protocol (Internet Protocol, IP) address, an IP address prefix (prefix), or other addresses such as a media access Control (MEDIA ACCESS Control, MAC) address, which is not limited herein. For convenience of description, the address to be stored is hereinafter described by taking an IP address prefix as an example, and the description is not limited thereto. The search result associated with the first address is the first search result.

The network equipment acquires the issued table entry to be stored, and acquires a first address to be stored and an associated first search result in the table entry to be stored. For example, the entry to be stored acquired by the network device may be an LPM entry, where the LPM entry includes an IP address prefix to be stored and an associated lookup result.

In the above step S12, the first lookup table is a hash (hash) table for storing addresses, and the addresses are stored in entries of the first lookup table, which are hereinafter referred to as address entries for convenience of distinction. The network device may preset the specification of the first lookup table according to the actual situation, for example, the specification of the first lookup table may be 1M, 2M, etc., which is not limited.

The network device may determine an address table entry in the first lookup table according to the obtained first address, where the determined address table entry is the first table entry storing the first address. The network device may store the first address in the first entry.

In the embodiment of the application, the network equipment can adopt a compressed or uncompressed first lookup table to store addresses. When the uncompressed first lookup table is used to store the address, only one address is stored in one address table, the network device may determine the index of the first table by using a hash algorithm, a Tree (Trie Tree), or a combination of the two, that is, determine the location where the first address is stored in the first lookup table, and store the first address into the first table through the index of the first table. For example, the network device may modulo the hash value corresponding to the first address according to the specification of the first lookup table, obtain the modulo value as the index of the first table entry, and store the first address in the first table entry.

In order to save storage resources, the network device may also store addresses using a compressed first lookup table, in which case one or more addresses may be stored in an address table entry, where the data of the first length of the one or more addresses is the same, and the data of the first length is a public address (a common prefix for an IP address prefix) of the one or more addresses, where the public address is stored in a public address field in the address table entry. And the other data than the public address in the one or more addresses is a special address (special prefix for IP address prefix) of the corresponding address, the one or more special addresses being stored in a special address field in the address table entry. That is, the common address of the one or more addresses is stored only once in the address table entry, reducing space wastage of the first lookup table.

The first length may be different for different address entries, i.e. the length of the public address of different address entries may be different. For example, for address entry 1, the first length is 12, indicating that the first 12 bits (bits) of data stored at the address of address entry 1 are identical. For another example, for address table entry 2, the first length is 14, which indicates that the first 14 bits of data stored in the address of address table entry 1 are identical. The value of the first length is merely exemplary, and is not limited thereto.

For example, for the 4 IP address prefixes {192.172.0.0/16,192.173.0.0/16,192.174.0.0/16,192.175.0.0/16}, the network device may be compressed into the format of common prefix (common_prefix) +special prefix (unique_prefix). The common prefix is {192.172.0.0/14}, the special prefix is {00,01,10,11}, that is, the 4 IP address prefixes can be compressed into {192.172.0.0/14|00,01,10,11}.

The network device may use any length as the first length, extract the data of the first length from the first address as the public address of the first address, use other data except the public address as the special address of the first address, calculate the index of the first table entry according to the public address of the first address through a hash algorithm, write the public address of the first address into the public address field of the first table entry through the index of the first table entry, and write the special address of the first address into the special address field of the first table entry. If other addresses are already stored in the first entry before the first address is stored, the network device may only write the special address of the first address to the special address field. The first lookup table employed by the network device and the manner in which the first address is stored to the first lookup table are not limited herein.

In the above step S13, the second lookup table is a hash table for storing the lookup result, and the lookup result is stored in the table entry of the second lookup table, which is hereinafter referred to as the result table entry for convenience of distinction. The network device may preset the specification of the second lookup table according to the number of outgoing interfaces and sub-interfaces and the forwarding behavior of each interface, for example, the specification of the second lookup table may be 32 kilos (K), 64K, etc., which is not limited. The network device may preset the length of the result table entry to any length greater than or equal to the length of the search result, for example, when the length of the search result is 5 bytes (B), the length of the result table entry may be 5B, 6B, or the like, which is not limited.

The network device may search the first lookup result in the lookup result stored in the result table entry of the second lookup table, where the result table entry storing the first lookup result is the second table entry. The network device determines whether the first lookup result is already stored in the second lookup table by looking up the second table entry.

If the network device finds the second table entry, i.e. determines that the first lookup result is already stored in the second lookup table, step S14 may be performed.

In step S14, the third lookup table is a hash table for storing a mapping relationship between the address and the lookup result, and the mapping relationship between the address and the lookup result is stored in an entry of the third lookup table, which is hereinafter referred to as an Identifier (ID) entry for convenience of distinction. The network device may preset the specification of the third lookup table according to the actual situation, where the specification of the third lookup table is the number of addresses that can be actually stored, for example, the specification of the third lookup table may be 1M, 2M, and the like, which is not limited. The network device may also preset the length of the identification table according to the specification of the second lookup table, for example, when the specification of the second lookup table is 64K, since 2 ¹⁶ >64K, the length of the identification table may be 2B, 3B, and so on, which is not limited.

In the embodiment of the application, each address stored in each address table entry is respectively associated with one identification table entry of the third lookup table. For example, the first lookup table includes an address table entry 1 and an address table entry 2, address 1 and address 2 are stored in address table entry 1, address 1 and address 2 are respectively associated with one identification table entry, address 1 is associated with identification table entry 1, address 2 is associated with identification table entry 2, address 3 is stored in address table entry 2, and address 3 is associated with identification table entry 3.

After the first address is stored in the first table entry, the network device may create a new identification table entry, and establish an association relationship between the first address and the newly created identification table entry, where the newly created identification table entry is the third table entry.

In the embodiment of the application, when the uncompressed first lookup table is adopted to store the address, the network equipment can allocate a free position to the first address from all the free positions of the third lookup table to create a new identification table item, wherein the newly created identification table item is the third table item, and the association relation between the first address and the third table item is established. For example, the network device may randomly select one empty location from among all empty locations to create a new identification entry. For another example, the network device may calculate a hash value from the first address, determine a null position indicated by the hash value, and create a new identification entry. The manner in which the third entry is allocated to the network device is not limited herein.

When the compressed first lookup table is adopted to store the addresses, the identification table items associated with the addresses stored in the address table items are continuous, and the address storage sequence is the sequence of the identification table items. Taking the 4 IP address prefixes in the step S12 as an example, if the order in which the 4 IP address prefixes are stored in the address table entry is {192.172.0.0/16}, {192.173.0.0/16}, {192.174.0.0/16}, and {192.175.0.0/16}, and the 4 IP address prefixes are respectively associated with the identification table entry a, the identification table entry b, the identification table entry c, and the identification table entry d, the special prefixes stored in the address table entry are {00,01,10,11}, the identification table entry a-the identification table entry d are consecutive, and the order is that the identification table entry a, the identification table entry b, the identification table entry c, and the identification table entry d. If the 4 IP address prefixes are stored in the address table in the sequence of {192.174.0.0/16}, {192.173.0.0/16}, {192.172.0.0/16}, and {192.175.0.0/16}, the special prefixes stored in the address table are {10,01,00,11}, the identification table a-the identification table d are consecutive, and the sequence is that the identification table c, the identification table b, the identification table a, and the identification table d.

If the number of addresses stored in the first table entry is greater than 1, that is, other addresses are already stored in the first table entry before the first address is stored, the network device may determine the third table entry according to the order of the first address in all addresses and the identification table entry associated with the other addresses, and establish the association relationship between the first address and the third table entry. Typically, after the first address is stored at the last address of the other addresses, the network device may determine the next identification entry of the identification entries associated with the last address as the third entry.

If the number of addresses stored in the first table entry is equal to 1, that is, the network device creates the first table entry and stores the first address in the newly created first table entry, the network device may allocate an identification table entry as a third table entry to the first address, and establish an association relationship between the first address and the third table entry, which is the same as the case of storing the address by adopting the uncompressed first lookup table, and will not be described herein.

After the network device determines the third table entry associated with the first address, an association relationship between the second table entry and the third table entry can be established, so that the second table entry stored with the first search result is associated with the first address, and further, the table entry is stored.

In the technical scheme provided by the embodiment of the application, in order to save storage resources, the network equipment can compress a lookup table (also called an address table) for storing addresses, and store a plurality of addresses in the same address table item. However, since the lookup result associated with each address is stored in a different result table entry in a lookup table (also referred to as a result table) for storing the lookup result, the number of result table entries is the same as the number of stored addresses, resulting in a large storage space required for storing the lookup result. By applying the technical scheme provided by the embodiment of the application, different search results are stored once in the result table, a plurality of addresses with the same associated search results can share one result table item, and under the condition that the forwarding behavior (namely the search results) of the network equipment is less than that of the addresses needing to be stored, the storage space required by storing the search results can be obviously reduced, the waste of the storage space is reduced, and the storage resource is further saved.

In some embodiments, the network device may establish the association using an index. The first index corresponding to the first address may be stored in the first table entry, and the step S14 may be implemented by storing the second index of the second table entry in the third table at the first index in the third lookup table.

In the embodiment of the application, the index of the identification table item associated with the address in the third lookup table can be stored in the address table item. The first index is an index of a third table item associated with the first address in a third lookup table, and the network equipment realizes association of the first address and the third table item by storing the first index in the first table item.

The network device may also store an index of the result table entry storing the lookup result in the second lookup table in the identification table entry. The second index is an index of the second table item in the second lookup table, after the network device obtains the second table item, the network device can determine the position of the third table item in the third lookup table according to the first index, write the second index into the third table item, and store the second index in the third table item to realize the association between the third table item and the second table item, and further realize the association between the first address and the second table item, that is, the association between the first address and the first lookup result.

In the embodiment of the application, after the third table entry is determined, the network device can write the first index into the first table entry to realize the association between the first address and the third table entry.

When the address is stored by using the uncompressed first lookup table, the index corresponding to the address stored in the address table entry is stored in the result index field of the address table entry, and the network device may directly write the first index into the result index field of the first table entry.

When storing addresses using a compressed first lookup table, the result index field of an address entry may be divided into a radix field and an index field. The radix field is used to store an index (referred to as a radix index) corresponding to a first address stored in the address table entry, and the index field sequentially stores offsets of indexes corresponding to all addresses with respect to the radix index. Taking the 4 IP address prefixes in the step S12 as an example, the index of the identification table item a to the identification table item d associated with the 4 IP address prefixes is 100, 101, 102 and 103, respectively, if the order in which the 4 IP address prefixes are stored in the address table items is {192.172.0.0/16}, {192.173.0.0/16}, {192.174.0.0/16} and {192.175.0.0/16}, the radix index is {100}, the content of the radix field is {100}, the offset corresponding to all addresses is {00,01,10,11}, and the content of the index field is {00,01,10,11}, as each field in the address table items shown in table 1.

TABLE 1

The key words are IP address prefixes, which are only examples and are not actually stored in the address table, the public prefixes are public address fields in the address table, the content of the public address fields is {192.172.0.0/14}, the special prefixes are special address fields in the address table, the content of the special address fields is {00,01,10,11}, the content of the public address fields and the content of the special address fields form IP address prefixes, the cardinal numbers are cardinal number fields in the address table, the content of the cardinal number fields is {100}, the indexes are index fields in the address table, the content of the index fields is {00,01,10,11}, and the content of the cardinal number fields and the content of the index fields form indexes for identifying table items a-d.

If the number of addresses stored in the first table entry is greater than 1, the network device may write an offset of the first index relative to the index corresponding to the first address into an index field of the first table entry according to the order in which the addresses are stored in the first table entry. Typically, the first address is stored after the last address of the other addresses, and the network device may write the corresponding offset after the offset corresponding to the last address.

If the number of addresses stored in the first entry is equal to 1, the network device may write the first index into the radix field of the first entry and an offset (e.g., 00) into the index field of the first entry.

In the embodiment of the application, the result index field may only include the base number field instead of the index field, that is, only the index corresponding to the first address is stored in the address table entry, and the indexes corresponding to other addresses may be determined according to the order in which the addresses are stored, so as to further save the storage space.

In some embodiments, referring to fig. 2, a second flowchart of a method for storing an entry according to an embodiment of the present application is shown. The above-described entry storage method may include the following steps.

Step S21, a first address to be stored and a first search result associated with the first address are obtained.

Step S22, the first address is stored in a first table entry in a first lookup table, and the first lookup table is used for storing the address.

Step S23, a second table item for storing the first lookup result is searched in a second lookup table, and the second lookup table is used for storing the lookup result. If the second entry is not found, step S24 is performed, and if the second entry is found, step S25 is performed.

Step S24, a second table item is created in the second lookup table, and the first lookup result is stored in the second table item.

Step S25, the second table item is associated with a third table item associated with the first address stored in the first table item in a third lookup table, and the third lookup table is used for storing the mapping relation between the address and the lookup result.

The steps S21 to S22 are the same as the steps S11 to S12, the step S23 is described in the section of the step S13, and the step S25 is the same as the step S14.

In the technical scheme provided by the embodiment of the application, when the network equipment does not find the second table entry, a new second table entry is created to store the first search result, so that the search results required to be stored are all stored in the second search table, and the search result associated with the address can be accurately found in the subsequent search.

In the step S24, since the network device does not find the second table entry, the network device determines that the first lookup result is not stored in the second lookup table, and then the network device may allocate a free location to create a new result table entry for the first lookup result in all the free locations of the second lookup table, where the newly created result table entry is the second table entry, and write the first lookup result into the second table entry.

In some embodiments, the second lookup table is further configured to store a digest of the lookup result, that is, the result table entry further stores a digest (digest) of the lookup result, where the length of the digest may be any length, for example, the length of the digest may be 1B, 2B, and the like, which is not limited. The step S13 may be implemented by calculating a first digest of the first search result and searching a second lookup table for a candidate table storing the first digest.

In the embodiment of the application, the network equipment can calculate the hash value corresponding to the first search result through a hash algorithm, and the hash value is used as the first abstract of the first search result. The network device may search the first digest in the digests stored in the result table entry of the second lookup table, where the result table entry storing the first digest is the candidate table entry. The candidate table indicates a result table in the second lookup table, where the result table may store the first lookup result, and the number of candidate tables may be one, may be multiple or may not exist, which is not limited herein.

According to whether the network device finds the candidate list item, the following two cases can be specifically classified.

In case 1, the network device finds the candidate entry. The network device obtains a candidate table item which can possibly store the first search result, searches the first search result in the search results stored in the candidate table item, and judges whether the first search result is stored in the candidate table item or not so as to judge whether the first search result is stored in the second search table or not.

If the network device finds the first lookup result in any candidate table, the network device may determine that the first lookup result is stored in the candidate table, that is, determine that the first lookup result is already stored in the second lookup table. The network device may take the candidate entry storing the first search result as the second entry, and execute step S25 to establish an association between the second entry and the third entry, which may be specifically referred to the description related to step S14.

If the network device does not find the first lookup result in all the candidate entries, the network device may determine that the first lookup result is not stored in the candidate entries, that is, determine that the second entry is not found, and determine that the first lookup result is not stored in the second lookup table. In this case, the network device may create a second table entry in the second lookup table, store the first lookup result in the newly created second table entry, and establish an association relationship between the second table entry and the third table entry, which may be specifically referred to in the related description of the step S24 and the step S14.

Case 2, the network device does not find a candidate entry. The network device determines that a candidate entry that may store the first lookup result does not exist, i.e., determines that the second entry is not looked up, and determines that the first lookup result is not already stored in the second lookup table. In this case, the network device may create a second table entry in the second lookup table, store the first lookup result in the newly created second table entry, and establish an association relationship between the second table entry and the third table entry, which may be specifically referred to in the related description of the step S24 and the step S14.

Based on the above description, referring to fig. 3, a third flowchart of the method for storing an entry according to an embodiment of the present application is shown. The above-described entry storage method may include the following steps.

Step S31, a first address to be stored and a first search result associated with the first address are obtained.

Step S32, storing the first address to a first table entry in a first lookup table, wherein the first lookup table is used for storing the address.

Step S33, a first abstract of the first search result is calculated.

Step S34, searching the candidate table item storing the first abstract in the second lookup table. If the candidate list item is not found, determining that the second list item is not found, and executing step S38;

Step S35, judging whether a first search result is stored in the candidate list item, if so, executing step S36, and if not, determining that a second list item is not found, executing step S38.

Step S36, taking the candidate table item as a second table item.

Step S37, the second table item is associated with a third table item associated with the first address stored in the first table item in a third lookup table, and the third lookup table is used for storing the mapping relation between the address and the lookup result.

Step S38, a second table item is created in the second lookup table, the first lookup result is stored in the second table item, and step S37 is executed.

The steps S31 to S32 are the same as the steps S11 to S12, the step S37 is the same as the step S14, the step S38 is the same as the step S24, and the steps S33 to S36 are specifically described in the section of the step S13.

In the technical scheme provided by the embodiment of the application, the network equipment searches candidate list items for storing the first abstract, screens out result list items which are possibly stored with the first search result by searching the candidate list items, and searches the first search result in the screened candidate list items. Because the length of the abstract is smaller than that of the search result, the network equipment can search the candidate list items more quickly, so that the search range is shortened quickly, and the efficiency of searching the second list item is improved. In addition, the network equipment directly determines that the second table item is not found under the condition that the candidate table item is not found, and does not carry out subsequent searching, so that the searching efficiency is further improved.

In some embodiments, the network device may also perform table entry deletion, that is, delete stored address table entries and identification table entries in the first lookup table and the third lookup table, and delete stored result table entries in the second lookup table according to circumstances. The network device may perform entry deletion by obtaining a deletion instruction, where the deletion instruction is used to instruct deletion of the first address, deleting the first address, and deleting an association relationship between the second entry and the third entry.

In the embodiment of the application, the network device may receive the deletion instruction from other devices, and the other devices may be other network devices, or may be electronic devices such as a computer, a server, etc., which is not limited. The network equipment determines the first address to be deleted from the deleting instruction, deletes the first address and the association relation between the first address and the third table item, and deletes the association relation between the second table item and the third table item.

When the address is stored using the uncompressed first lookup table, or when the address is stored using the compressed first lookup table and the number of addresses stored in the first entry is equal to1, the network device may delete the first entry directly to delete the first address.

When the compressed first lookup table is used for storing the addresses and the number of the addresses stored in the first table entry is greater than 1, the network device may delete the special address of the first address in the special address field, and delete the offset corresponding to the first address in the index field, that is, delete the first index corresponding to the first address in the first table entry, so as to realize deletion of the first address.

Before deleting the first address, the network device may first obtain, from the third lookup table, the third table associated with the first address through the first index corresponding to the first address stored in the first table, and delete the third table, so as to implement deleting the association relationship between the second table and the third table. By deleting unwanted addresses in the first lookup table, the network device may free up memory space to store other addresses.

In the embodiment of the application, the network device can also obtain the second table entry which is associated with the third table entry and stores the first search result from the second lookup table through the second index stored in the third table entry, and judge whether other addresses except the first address multiplex the first search result, that is, judge whether other addresses are associated with the first search result. And the network equipment does not delete the second table entry under the condition that other addresses are determined to multiplex the first searching result, and deletes the second table entry under the condition that other addresses are determined to multiplex the first searching result, so as to save storage resources.

In some embodiments, the second lookup table is further configured to store a number of addresses of the multiplexed lookup result, that is, the result entry also stores a number of addresses of the lookup result, indicating a number of addresses associated with the lookup result. The length of the number of addresses may be any length, for example, the length of the number of addresses may be 1B, 2B, or the like, which is not limited.

The network device may delete the association between the second table entry and the third table entry by acquiring the second table entry and the third table entry associated with the first address through the third lookup table and the second lookup table, deleting the third table entry, subtracting 1 from the number of addresses stored in the second table entry if the number of addresses stored in the second table entry is greater than 1, and deleting the second table entry if the number of addresses stored in the second table entry is equal to 1.

In the embodiment of the application, the network equipment acquires the third table item associated with the first address from the third lookup table through the first index stored in the first table item, acquires the second table item associated with the third table item from the second lookup table through the second index stored in the third table item, and deletes the third table item.

The network device may determine, according to the number of addresses, whether there are other addresses to multiplex the first search result. When the number of addresses stored in the second table entry is greater than 1, the network device determines that other addresses multiplex the first search result, and the network device does not delete the second table entry and subtracts 1 from the number of addresses. When the number of addresses stored in the second table entry is equal to 1, the network device determines that no other addresses multiplex the first search result, and the network device deletes the second table entry. By storing the address number of the multiplexing search result, the network device can quickly judge whether other address multiplexing search results exist, so that the efficiency of deleting the table entry is improved, and the storage resource is saved.

The network device may further determine, according to the second index stored in the third table entry, whether there are other identification table entries in the third lookup table other than the third table entry, which also stores the second index, to determine whether there are other addresses to multiplex the first lookup result, which is not limited.

In the embodiment of the application, when the network equipment searches the second table entry, after the second table entry is associated with the third table entry, the number of the addresses stored in the second table entry can be increased by 1, and when the network equipment does not search the second table entry, after the second table entry is created, the second table entry is associated with the third table entry, the number of the addresses stored in the second table entry can be set to be 1.

In some embodiments, the network device may also make table entry modifications, i.e., modify the lookup result stored in the corresponding result table entry in the second lookup table. The network device can modify the table entry by acquiring a modification instruction, wherein the modification instruction is used for indicating that the search result associated with the modified first address is a second search result, searching a fourth table entry for storing the second search result in the second search table, deleting the association relation between the second table entry and the third table entry if the fourth table entry is found, and associating the fourth table entry with the third table entry associated with the first address in the third search table.

In the embodiment of the application, the network device may receive the modification instruction from other devices, and the other devices may be other network devices, or may be electronic devices such as a computer, a server, etc., which is not limited. The network device determines from the modification instruction that the first search result associated with the first address is modified to be a second search result, so that the network device can delete the association relation between the second table entry and the third table entry, search the second search result in the search results stored in the result table entry of the second search table, and the result table entry storing the second search result is the fourth table entry. The network device determines whether the second lookup result is already stored in the second lookup table by looking up the fourth table entry.

If the network device finds the fourth table entry, that is, determines that the second search result is already stored in the second lookup table, the network device may establish an association relationship between the fourth table entry and the third table entry, that is, modify the second index stored in the third table entry into the index of the fourth table entry, so as to implement association between the fourth table entry storing the second search result and the first address.

If the network device does not find the fourth table entry, that is, determines that the second lookup result is not stored in the second lookup table, the network device may allocate a free location to the second lookup result in all the free locations of the second lookup table to create a new result table entry, where the newly created result table entry is the fourth table entry, and write the second lookup result into the fourth table entry. The network device may then establish an association between the fourth entry and the third entry.

The process of deleting the association relationship between the second entry and the third entry by the network device may be specifically referred to in the above description of deleting the entry portion, which is not described in detail herein.

In the technical scheme provided by the embodiment of the application, the network equipment realizes the modification of the search result through the first address, the third lookup table and the second lookup table, and deletes the corresponding result table entry under the condition that the search result is not associated with any address, so as to save storage resources.

In the embodiment of the present application, the network device may also modify the address stored in the address table entry, in which case the network device may first perform the step of deleting the table entry and then perform the step of storing the table entry.

The following describes the table entry storage method provided by the embodiment of the present application in detail.

In step 1, the network device receives a new LPM entry X (i.e., a first address) issued, where the entry X includes an IP address prefix and an associated lookup result (i.e., a first lookup result). The network device inserts the table entry X in the prefix table (i.e., the first lookup table, i.e., the address table) first, and assigns a corresponding unique ID (i.e., the first index) to the table entry X, and the corresponding index and the ID entry (i.e., the third entry) in the identification mapping table (i.e., the third lookup table, i.e., the identification table).

Step 2, the network device calculates a digest (i.e. a first digest) of the lookup result of length 5B included in the table entry X.

And 3, the network equipment searches the abstract as a keyword in a result table, and judges whether the abstract stored in the result table is the same as the abstract corresponding to the table item X.

And step 4, if the abstract stored in the result table is determined to be the same as the abstract corresponding to the table item X, the network equipment further accurately compares whether the search result stored in the result table is the same as the search result included in the table item X.

And step 5, if the search result stored in the result table is the same as the search result included in the table item X, the network device may directly multiplex the search result, add 1 to the multiplexing number (i.e., the address number) stored in the result table item (i.e., the second table item), and simultaneously return the index R (i.e., the second index) recorded in the result table by the result table item.

And 6, writing the index and the value of the ID bar table item of the identification mapping table into R, namely index_to_id [ ID ] =R.

And 7, if the abstract stored in the result table is not the same as the abstract corresponding to the table item X, that is, the abstract corresponding to the table item X cannot be searched in the result table, the network equipment allocates one table item in the result table newly according to the fact that the search result included in the table item X is a new search result which is not recorded, writes the search result included in the table item X, sets the multiplexing number stored in the newly allocated table item as 1, returns the index R' recorded in the result table by the newly allocated table item, and returns to execute the step 6.

And step 8, if the abstract stored in the result table is determined to be the same as the abstract corresponding to the table item X, and the search result stored in the result table is determined to be different from the search result included in the table item X, executing step 7, and processing according to a new result table item inserted.

By applying the technical scheme provided by the embodiment of the application, different search results are stored once in the result table, a plurality of addresses with the same associated search results can share one result table item, the storage space required for storing the search results is reduced, the compression of the result table is realized, the waste of the storage space is reduced, more table items are stored by utilizing the limited SRAM capacity, and larger table item specifications can be provided.

Corresponding to the above table entry storage method, the embodiment of the present application further provides a table entry searching method, which can be applied to network devices such as routers and switches, and can also be applied to forwarding chips in the network devices, and for convenience of description, the network devices are used as execution bodies in the following steps, and the table entry searching method is not limited. Referring to fig. 4, a flow chart of a table entry searching method according to an embodiment of the present application is shown. The table entry searching method comprises the following steps.

Step S41, obtaining a second address to be searched.

Step S42, a fifth table item for storing a third address is searched in a first lookup table, the third address is matched with the second address, and the first lookup table is used for storing the addresses.

Step S43, a sixth table item associated with a third address stored in a fifth table item in a third lookup table is obtained, and the third lookup table is used for storing a mapping relation between the address and a lookup result.

Step S44, a seventh table item associated with the sixth table item in a second lookup table is obtained, and the second lookup table is used for storing the lookup result.

Step S45, the searching result stored in the seventh table entry is used as a third searching result associated with the second address.

In the technical scheme provided by the embodiment of the application, after the network equipment stores the first address into the first table entry, the first search result associated with the first address is searched in the stored search results, namely, the second table entry storing the first search result is searched. If the second table item is found, the network device can directly multiplex the first lookup result to establish an association relationship between the second table item and a third table item associated with the first address, so that the association between the first address and the first lookup result is realized, and the table item storing the first lookup result does not need to be newly created. In the subsequent searching process, the network equipment can determine the searching result of the address association to be searched only according to the table items of the address association to be searched in the third searching table and the second searching table.

By applying the technical scheme provided by the embodiment of the application, the network equipment firstly searches the search result to be stored and determines whether the search result to be stored is stored in the second search table. Therefore, the same search result is only required to be stored once in the second search table, the storage space required for storing the search result is saved, the second search table is compressed, the storage space waste caused by repeatedly storing the search result is reduced, more table items can be stored by using the limited SRAM capacity, and larger table item specifications are provided. Meanwhile, the network equipment can accurately find the address-associated search result through the search result stored in the second search table and the mapping relation between the address and the search result stored in the third search table, so that the search accuracy is ensured.

In the step S41, the second address is any address to be searched by the network device. In the embodiment of the application, the address to be searched by the network equipment corresponds to the address stored in the first lookup table. For example, when the address stored in the first lookup table is an IP address or an IP address prefix, the address to be searched by the network device is an IP address. For another example, when the address stored in the first lookup table is another address such as a MAC address, the address to be searched by the network device is a corresponding other address. The address to be searched by the network device is not limited here.

The network device obtains the second address to be searched, and performs step S42 to match the second address in the first lookup table, that is, to search the address table entry matching the second address.

When the address stored in the first lookup table is an IP address prefix, the second address is an IP address, the network equipment adopts an LPM algorithm to match the second address with the IP address prefix stored in the address table entry, selects the IP address prefix with the longest length from the matched IP address prefixes as a third address matched with the second address, and takes the address table entry storing the third address as a fifth table entry.

When the address stored in the first lookup table is an IP address, the second address is also an IP address, the network equipment searches the second address in the addresses stored in the address table entries, the searched address is the third address, and the address table entries storing the third address are used as fifth table entries.

If the network device does not find the fifth table entry, the network device determines that the second address matching fails and returns a matching failure result.

In the embodiment of the application, when the uncompressed first lookup table is adopted to store the address, the network equipment can directly match the second address in the first lookup table and search the fifth table item.

When the compressed first lookup table is used for storing the address, the network device can match the second address with the public address stored in the public address field of the address table entry, and then match the remaining data of the second address with the special address stored in the special address field of the address table entry under the condition that the data of the first length before the second address is the same as the public address, and when the public address and the special address are matched, the network device determines that the second address is matched.

The network device may also disassemble the second address into a public address and a special address corresponding to each first length according to each first length adopted by the address table entry stored in the first lookup table, calculate an index of the address table entry according to the public address corresponding to each first length through a hash algorithm, and determine whether the address table entry exists at each index in the first lookup table. When the address table item is determined to exist, the network equipment further searches the corresponding special address to realize the matching of the second address. The manner in which the second addresses are matched is not limited herein.

In the step S43, since the address stored in the first lookup table is associated with the identification table entry in the third lookup table, the network device may determine the identification table entry associated with the third address stored in the fifth table entry after finding the fifth table entry, where the identification table entry is the sixth table entry.

In the step S44, since the identification entry in the third lookup table is associated with the result entry in the second lookup table, the network device may determine the result entry associated with the sixth entry after determining the sixth entry, where the result entry is the seventh entry.

In step S45, after the network device obtains the seventh entry, the network device may extract a search result from the seventh entry, where the extracted search result is the third search result associated with the second address.

In some embodiments, the network device may establish the association using an index. The fifth table entry stores a third index corresponding to the third address, and the step S43 may be implemented by obtaining a sixth table entry at the third index in the third lookup table. The step S44 may be implemented by acquiring a seventh entry at a fourth index stored in a sixth entry in the second lookup table.

In the embodiment of the application, the index of the identification table item associated with the address in the third lookup table is stored in the address table item, and the third index is the index of the sixth table item associated with the third address stored in the fifth table item in the third lookup table. The network device may obtain the third index from the fifth table entry, and obtain, through the third index, the identification table entry at the third index in the third lookup table as the sixth table entry.

When the address is stored using the uncompressed first lookup table, the network device may extract the contents of the result index field of the fifth entry to obtain a third index.

When the compressed first lookup table is used for storing the address, the network device may extract the content of the result index field of the fifth table entry, extract the radix index from the radix field, extract the offset corresponding to the third address from the index field, and obtain the third index through the radix index and the offset. If the result index field includes only the radix field, the network device may determine, according to the order of the third address in all the addresses stored in the fifth entry, an offset corresponding to the third address. The manner in which the network device obtains the third index is not limited herein.

In the embodiment of the application, the index of the associated result table item stored in the table item in the second lookup table is identified, and the fourth index is the index of the seventh table item stored in the sixth table item and associated with the sixth table item. The network device may obtain the fourth index from the sixth entry, and obtain, by using the fourth index, the result entry at the fourth index in the second lookup table as the seventh entry.

According to the technical scheme provided by the embodiment of the application, the network equipment realizes the association of the address and the identification table item by storing the index of the identification table item in the address table item so as to quickly find the identification table item associated with the address, and realizes the association of the identification table item and the result table item by storing the index of the result table item in the identification table item so as to quickly find the result table item associated with the identification table item, thereby improving the speed of table item searching.

The following describes in detail the table entry storage and table entry searching method provided by the embodiment of the present application through fig. 5 and fig. 6. The compressed first lookup table is used to store addresses, and the stored addresses are used as IP address prefixes, which are described by way of example and not limitation.

Such as the entry structure shown in fig. 5. In fig. 5, 2 lookup tables are included, namely a prefix table (i.e., a first lookup table, i.e., an address table) storing IP address prefixes and a result table (i.e., a second lookup table) storing lookup results. Taking the prefix table with 2 prefix entries (i.e. prefix group 1 and prefix group 2, i.e. address entries) stored therein, the result table with 5 result entries stored therein as an example.

3 IP address prefixes (i.e., prefix_a, prefix_b, and prefix_c) are stored in the prefix group 1, the search results (i.e., result_a, result_b, and result_c) associated with the 3 IP address prefixes are stored in 3 result table entries of the result table, and indexes (i.e., index_1, index_2, and index_3) of the 3 result table entries are stored in positions corresponding to the prefix group 1, so that association between the 3 IP address prefixes and the 3 search results is realized. The prefix group 2 stores 2 IP address prefixes (i.e., prefix_x and prefix_y), search results (i.e., result_x and result_y) associated with the 2 IP address prefixes are stored in 2 result table entries of the result table, and indexes (i.e., index_m and index_n) of the 2 result table entries are stored in positions corresponding to the prefix group 2, so that association of the 2 IP address prefixes with the 2 search results is realized.

When the specification of the result table is 2M and the length of each search result is 5B, the maximum number of stored addresses is 2M, and since the search result of each address needs to be stored, the storage of the search result needs to occupy a storage space of 2 mx5b=10mb. When there are identical search results in the result table entries of the result table, if the result_b and the result_c are identical, and the result_y and the result_a are identical, the waste of the storage space is caused.

Such as the entry structure shown in fig. 6. In fig. 6, 3 lookup tables are included, namely a prefix table storing IP address prefixes, an index and identity mapping table (i.e. a third lookup table, i.e. an identity table), and a result table storing lookup results. The index and identity mapping table stores 5 identity entries.

The indexes (i.e., index_1, index_2, index_3, index_m, and index_n) stored in the prefix table are indexes and indexes identifying the table entries in the mapping table, and are no longer indexes of the result table entries in the result table, and the IP address prefix is associated to the indexes and the identifying table entries in the mapping table through the corresponding indexes.

Since result_b is the same as result_c and result_y is the same as result_a, only the result table entry including result_a, result_b, and result_x need be stored in the result table. At this time, the search result associated with the prefix_a and the prefix_y is the result_a, the index of the result table entry storing the result_a is the id_a, the id_a is stored in the identification table entry associated with the prefix_a and the prefix_y, the search result associated with the prefix_b and the prefix_c is the result_b, the index of the result table entry storing the result_b is the id_b, the id_b is stored in the identification table entry associated with the prefix_b and the prefix_c, the search result associated with the prefix_x is the result_x, the index of the result table entry storing the result_x is the id_x, and the id_x is stored in the identification table entry associated with the prefix_x, thereby realizing the association of 5 IP address prefixes and 3 search results. The result table entry also includes a summary of each lookup result and the number of multiplexes (i.e., the number of addresses) of the lookup result.

When the number of addresses stored at maximum is still 2M, the length of each search result is 5B, the lengths of the summary and the multiplex number are 1B, respectively, the specification of the index and identification mapping table is 2M, and the length of the result table entry is 1+5+1=7b. Assuming that 64K different search results are supported at maximum, that is, in the case where the result table has a specification of 64K, the length of each identification table entry may be 2B, the index and identification mapping table needs to occupy a memory space of 2 mx2b=4mb, and the result table needs to occupy a memory space of 64 kx7b=448 KB. Furthermore, the total storage search result needs to occupy 4MB+448KB=4.4375 MB, and 4.4375MB/10 MB= 0.44375 is calculated, so that in the technical scheme provided by the embodiment of the application, the storage space occupied by the storage search result is only 44.375% of that of the existing scheme.

By applying the technical scheme provided by the embodiment of the application, the 2 lookup tables of the original scheme are expanded into 3 lookup tables, namely an address table, an index and identification mapping table and a result table, and the many-to-one mapping from a plurality of addresses to one lookup result is realized through the index and identification mapping table.

Corresponding to the above embodiment of the method for storing an entry, the embodiment of the present application further provides an entry storage device, and referring to fig. 7, a schematic structural diagram of the entry storage device provided by the embodiment of the present application is provided. The table entry storage device includes:

a first obtaining module 71, configured to obtain a first address to be stored and a first search result associated with the first address;

A storage module 72 for storing a first address to a first entry in a first lookup table, the first lookup table for storing addresses;

A first lookup module 73, configured to lookup a second table entry storing a first lookup result in a second lookup table, where the second lookup table is used to store the lookup result;

and the association module 74 is configured to associate the second entry with a third entry associated with the first address stored in the first entry in a third lookup table if the second entry is found, where the third lookup table is used to store a mapping relationship between the address and the lookup result.

In some embodiments, the association module 74 described above may also be used to:

storing the first search result to a second table entry;

the step of associating the second entry with a third entry in a third lookup table that associates the first address stored by the first entry is performed.

In some embodiments, the first table entry may store a first index corresponding to the first address, and the association module 74 may be specifically configured to:

the second index of the second entry is stored to a third entry in a third lookup table at the first index.

In some embodiments, the second lookup table may also be used to store a summary of the lookup result, and the storage module 72 may be specifically configured to:

calculating a first abstract of the first search result;

Searching candidate table items for storing the first abstract in a second lookup table;

if the candidate list item is found, judging whether a first search result is stored in the candidate list item;

In some embodiments, the storage module 72 described above may also be used to:

if the candidate list item is not searched, or the first search result is not stored in the candidate list item, determining that the second list item is not searched.

In some embodiments, the foregoing table entry storage device may further include a deletion module configured to:

deleting the first address and deleting the association relationship between the second table item and the third table item.

In some embodiments, the above table entry storage device may further include a modification module configured to:

acquiring a modification instruction, wherein the modification instruction is used for indicating a search result associated with the modified first address as a second search result;

searching a fourth table item storing a second searching result in the second searching table;

if the fourth table item is found, deleting the association relation between the second table item and the third table item, and associating the fourth table item with the third table item associated with the first address in the third lookup table.

In some embodiments, the second lookup table may also be used to store the address number of the multiplexed lookup result, and the deletion module or the modification module may be specifically configured to:

Acquiring a second table item and a third table item associated with the first address through a third lookup table and a second lookup table;

Deleting the third table entry;

And if the number of the addresses stored in the second table entry is greater than 1, subtracting 1 from the number of the addresses stored in the second table entry, and if the number of the addresses stored in the second table entry is equal to 1, deleting the second table entry.

Corresponding to the above table entry searching method embodiment, the embodiment of the present application further provides a table entry searching device, referring to fig. 8, which is a schematic structural diagram of the table entry searching device provided by the embodiment of the present application, where the table entry searching device includes:

A second obtaining module 81, configured to obtain a second address to be searched;

A second lookup module 82, configured to lookup a fifth entry storing a third address in a first lookup table, where the third address matches the second address, and the first lookup table is used to store the address;

A third obtaining module 83, configured to obtain a sixth table entry associated with a third address stored in a fifth table entry in a third lookup table, where the third lookup table is used to store a mapping relationship between the address and a lookup result;

A fourth obtaining module 84, configured to obtain a seventh entry associated with a sixth entry in a second lookup table, where the second lookup table is used to store a lookup result;

the obtaining module 85 is configured to use the lookup result stored in the seventh entry as a third lookup result associated with the second address.

In the technical scheme provided by the embodiment of the application, after the first address is stored in the first table entry, the first search result related to the first address is searched in the stored search results, namely, the second table entry storing the first search result is searched. If the second table item is found, the first lookup result is stored in the second lookup table, the first lookup result can be directly multiplexed, the association relation between the second table item and a third table item associated with the first address is established, the association between the first address and the first lookup result is realized, and the table item storing the first lookup result does not need to be newly created. In the subsequent searching process, the searching result of the address association to be searched can be determined only according to the table items of the address association to be searched in the third searching table and the second searching table.

By applying the technical scheme provided by the embodiment of the application, the search result to be stored is searched first, and whether the search result to be stored is stored in the second search table or not is determined. Therefore, the same search result is only required to be stored once in the second search table, the storage space required for storing the search result is saved, the second search table is compressed, the storage space waste caused by repeatedly storing the search result is reduced, more table items can be stored by using the limited SRAM capacity, and larger table item specifications are provided. Meanwhile, the search result associated with the address is accurately searched through the search result stored in the second search table and the mapping relation between the address and the search result stored in the third search table, so that the search accuracy is ensured.

In some embodiments, a third index corresponding to a third address may be stored in the fifth entry; the third obtaining module 83 may be specifically configured to obtain a sixth entry at a third index in a third lookup table;

The fourth obtaining module 84 may be specifically configured to obtain the seventh entry at the fourth index stored in the sixth entry in the second lookup table.

The embodiment of the application also provides a network device, as shown in fig. 9, which comprises a processor 91, a communication interface 92, a memory 93 and a communication bus 94, wherein the processor 91, the communication interface 92 and the memory 93 complete communication with each other through the communication bus 94;

a memory 93 for storing a computer program;

the processor 91 is configured to implement any one of the above-mentioned entry storage methods or entry lookup methods when executing the program stored in the memory 93.

The communication bus mentioned by the above network device may be a peripheral component interconnect standard (PERIPHERAL COMPONENT INTERCONNECT, PCI) bus or an extended industry standard architecture (Extended Industry Standard Architecture, EISA) bus, etc. The communication bus may be classified as an address bus, a data bus, a control bus, or the like. For ease of illustration, the figures are shown with only one bold line, but not with only one bus or one type of bus.

The communication interface is used for communication between the network device and other devices.

The Memory may include random access Memory (Random Access Memory, RAM) or may include Non-Volatile Memory (NVM), such as at least one disk Memory. Optionally, the memory may also be at least one memory device located remotely from the aforementioned processor.

The Processor may be a general-purpose Processor including a central processing unit (Central Processing Unit, CPU), a network Processor (Network Processor, NP), etc., or may be a digital signal Processor (DIGITAL SIGNAL Processor, DSP), application SPECIFIC INTEGRATED Circuit (ASIC), field-Programmable gate array (Field-Programmable GATE ARRAY, FPGA) or other Programmable logic device, discrete gate or transistor logic device, discrete hardware components.

In yet another embodiment of the present application, a computer readable storage medium is provided, in which a computer program is stored, which when executed by a processor implements any of the above-mentioned method for storing or searching table entries.

In a further embodiment of the present application, there is also provided a computer program product containing instructions which, when run on a computer, cause the computer to perform the steps of any of the table entry storage methods or table entry lookup methods of the above embodiments.

In the above embodiments, it may be implemented in whole or in part by software, hardware, firmware, or any combination thereof. When implemented in software, may be implemented in whole or in part in the form of a computer program product. The computer program product includes one or more computer instructions. When loaded and executed on a computer, produces a flow or function in accordance with embodiments of the present application, in whole or in part. The computer may be a general purpose computer, a special purpose computer, a computer network, or other programmable apparatus. The computer instructions may be stored in or transmitted from one computer-readable storage medium to another, for example, by wired (e.g., coaxial cable, optical fiber, digital Subscriber Line (DSL)), or wireless (e.g., infrared, wireless, microwave, etc.). The computer readable storage medium may be any available medium that can be accessed by a computer or a data storage device such as a server, data center, etc. that contains an integration of one or more available media. The usable medium may be a magnetic medium (e.g., floppy disk, hard disk, tape), an optical medium (e.g., DVD), or a semiconductor medium (e.g., solid state disk (Solid STATE DISK, SSD)), etc.

It is noted that relational terms such as first and second, and the like are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Moreover, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises an element.

In this specification, each embodiment is described in a related manner, and identical and similar parts of each embodiment are all referred to each other, and each embodiment mainly describes differences from other embodiments. In particular, for an apparatus, network device, computer storage medium, computer program product embodiment, since it is substantially similar to a method embodiment, the description is relatively simple, and reference is made to the description of a method embodiment for relevant points.

The foregoing description is only of the preferred embodiments of the present application and is not intended to limit the scope of the present application. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present application are included in the protection scope of the present application.

Claims

1. A method for storing an entry, the method comprising:

Calculating a first abstract of the first search result;

Searching candidate table items for storing the first abstract in a second lookup table, wherein the second lookup table is used for storing search results and abstracts of the search results;

if the first search result is stored, the candidate table entry is used as a second table entry;

and if the second table entry is found, associating the second table entry with a third table entry in a third lookup table to associate the second table entry with the first address, wherein the third lookup table is used for storing a mapping relation between an address and a lookup result, and the third table entry is associated with the first address stored in the first table entry.

2. The method according to claim 1, wherein the method further comprises:

storing the first search result to the second table entry;

And executing the step of associating the second table entry with a third table entry in a third lookup table.

3. The method according to claim 1 or 2, wherein a first index corresponding to the first address is stored in the first entry;

The step of associating the second entry with a third entry in a third lookup table comprises:

4. The method according to claim 1, wherein the method further comprises:

5. The method according to claim 1, wherein the method further comprises:

6. The method according to claim 1, wherein the method further comprises:

7. The method according to claim 5 or 6, wherein the second lookup table is further used for storing the number of addresses of the multiplexed lookup result;

the step of deleting the association relationship between the second table item and the third table item comprises the following steps:

Deleting the third table entry;

8. A method for table entry lookup, the method comprising:

Acquiring a second address to be searched;

Searching a fifth table item for storing a third address in a first lookup table, wherein the third address is matched with the second address, the first lookup table is used for storing addresses, the addresses stored in the first lookup table are associated with table items in the third lookup table, the third address stored in the fifth table item is associated with a sixth table item in the third lookup table, and the third lookup table is used for storing mapping relation between the addresses and lookup results;

Obtaining a sixth table entry in a third lookup table, wherein the table entry in the third lookup table is associated with a table entry in a second lookup table, the sixth table entry is associated with a seventh table entry in the second lookup table, and the second lookup table is used for storing a lookup result;

acquiring a seventh table entry in the second lookup table;

9. The method of claim 8, wherein a third index corresponding to the third address is stored in the fifth entry;

the step of obtaining the sixth entry associated with the third address stored in the fifth entry in the third lookup table includes:

Obtaining a sixth table entry at the third index in the third lookup table;

the step of obtaining the seventh entry associated with the sixth entry in the second lookup table includes:

and acquiring a seventh table entry at a fourth index stored in the sixth table entry in the second lookup table.

10. An entry storage device, the device comprising:

the device comprises a first search module, a second search module, a first search module, a candidate table, a second search module, a first search module, a second search module and a second search module, wherein the first search module is used for calculating a first abstract of the first search result;

And the association module is used for associating the second table item with a third table item in a third lookup table if the second table item is found, so as to associate the second table item with the first address, wherein the third lookup table is used for storing the mapping relation between the address and the lookup result, and the third table item is associated with the first address stored by the first table item.

11. An entry lookup apparatus, the apparatus comprising:

the second lookup module is used for looking up a fifth table item for storing a third address in a first lookup table, the third address is matched with the second address, the first lookup table is used for storing the address, the address stored in the first lookup table is associated with a table item in the third lookup table, the third address stored in the fifth table item is associated with a sixth table item in the third lookup table, and the third lookup table is used for storing the mapping relation between the address and a lookup result;

a third obtaining module, configured to obtain a sixth entry in a third lookup table, where the entry in the third lookup table is associated with an entry in a second lookup table, the sixth entry is associated with a seventh entry in the second lookup table, and the second lookup table is configured to store a lookup result;

a fourth obtaining module, configured to obtain a seventh entry in the second lookup table;

12. The network equipment is characterized by comprising a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface and the memory are communicated with each other through the communication bus;

A memory for storing a computer program;

a processor for implementing the method of any one of claims 1 to 7 or the method of any one of claims 8 to 9 when executing a program stored on a memory.

13. A computer readable storage medium, characterized in that the computer readable storage medium has stored therein a computer program which, when executed by a processor, implements the method of any of claims 1-7 or the method of any of claims 8-9.