WO2019241926A1 - Access control list management method and device - Google Patents

Abstract

Provided by the present application is an access control list management method and device, relating to the technical field of data processing. The method comprises: obtaining the number N of compressed node layers; the compressed node layers are formed by layers on a search tree corresponding to an access control list (ACL) and the compressed node layers include at least one compressed node; N is an integer greater than or equal to 1; storing the N compressed node layers in a number M of SRAMs, wherein M is an integer greater than 0 and less than N, and each SRAM in the M SRAMs stores at least one of the N compressed node layers. That is, in the embodiment of the present application, multiple compressed node layers can share one SRAM, which effectively avoids the problem of wasted storage space caused by storing only one compressed node layer in each SRAM, and improves the utilization of the storage space of the SRAM.

Description

Management method and device for access control list Technical field

The present application relates to the field of data processing technologies, and in particular, to a method and device for managing an access control list (Access Control List, ACL).

Background technique

ACL is a list of instructions configured in forwarding devices such as routers or switches. Among them, the ACL includes multiple rules. When a forwarding device receives a packet, it can extract keywords from the packet, and find rules that match the extracted keywords from the multiple rules included in the ACL. As a result, the received message is processed. Because the number of rules included in an ACL is extremely large, in order to facilitate searching, usually, a forwarding device can create a corresponding search tree according to the ACL, and then store the ACL according to the layers included in the search tree.

Specifically, the forwarding device may select multiple specific bits in the rule to divide the multiple rules according to the characteristics of the multiple rules included in the ACL, thereby dividing the multiple rules into multiple buckets. The maximum capacity of each of the multiple buckets is the same. The forwarding device may create a search tree according to the process of dividing the multiple rules, and each leaf node of the search tree eventually points to a bucket. For example, suppose the maximum capacity of the bucket is 3. As shown in Figure 1, the ACL includes 12 rules. The forwarding device can first divide the 12 rules into 2 groups according to the 6th bit. Among them, the rule with the value of the 6th bit is 0 is the first group, the rule with the value of 1 is the second group, and the value is the specified character. Rules need to be placed in two groups at the same time. After the first group and the second group are divided, since the number of rules in the first group and the second group are both greater than 3, that is, greater than the maximum capacity of the bucket, the first group and the second group can be continued Divided. Among them, for the first group, they are divided according to the third bit to obtain the third and fourth groups, and for the second group, they are divided according to the first bit to obtain the fifth and sixth groups. Among them, the number of rules included in the fourth group, the fifth group, and the sixth group are all less than 3. Therefore, the rules of the fourth group, the fifth group, and the sixth group can be stored in different buckets, respectively. The number of rules included in the three groups is still greater than three. Therefore, the third group can be further divided according to the 13th bit to obtain the seventh group and the eighth group. Because the number of rules included in the seventh and eighth groups is less than three, the rules included in the seventh and eighth groups may be stored in different buckets, respectively. It can be seen that through the above process, 12 rules can be divided into 5 buckets, and according to the division process, the search tree shown in FIG. 2 can be created. Each leaf node of the search tree stores the storage address of the corresponding bucket, and other nodes except the leaf nodes store the specific bits corresponding to the corresponding nodes that are used to indicate the division of the rule and the specific Segmentation information for the division method.

After the search tree is created, because the number of rules in the ACL is extremely large, the search tree created often includes many layers. In this case, the forwarding device can start from the first layer of the search tree and A preset number of layers is used as a compression node layer, and multiple nodes in the compression node layer are stored in at least one compression node, and then stored in each static random access memory (SRAM). A compression node layer includes at least one compression node.

When the above method is used to store the ACL, because the number of nodes in each layer of the search tree is different, the number of nodes in each compressed node layer is also different. In this way, the amount of occupied capacity in each SRAM is also different. For the SRAM corresponding to some compressed node layers with a small number of nodes, there will be a problem of wasted storage space.

Summary of the Invention

The present application provides an access control list management method, device, and computer storage medium, which can be used to solve the problem of wasted storage space caused by each SRAM storing a compressed node layer in the related art. The technical scheme is as follows:

In a first aspect, a method for managing an access control list is provided. The method includes:

Obtain the number N of compressed node layers. The compressed node layer is formed by a layer on the search tree corresponding to the access control list ACL, and the compressed node layer includes at least one compressed node, where N is greater than or equal to 1 An integer

Storing the N compression node layers in M SRAMs, where M is an integer greater than 0 and less than the N, and each of the M SRAMs stores the N compression node layers At least one compression node layer.

In the embodiment of the present application, the forwarding device may store N compression node layers in less than N SRAMs, that is, multiple compression node layers may share one SRAM, which effectively avoids storing only one in each SRAM. The problem of wasted storage space caused by compression of the node layer improves the utilization of the storage space of the SRAM.

Optionally, the storing the N compression node layers in the M SRAMs includes:

According to the sequence of the N compression node layers, starting from the first SRAM of the M SRAMs, and sequentially from the first SRAM to the Mth SRAM, one compression is stored in each SRAM in turn. Node layer

When it is stored in the Mth SRAM, it starts from the first SRAM in the Mth SRAM, and sequentially stores a compression node layer in each SRAM in the order from the first SRAM to the Mth SRAM. Until the N compressed node layers are stored.

Optionally, the method further includes:

When a message is received, extract keywords from the message;

Based on the keyword and the N compressed node layers stored in the M SRAMs, a rule matching the keyword is searched.

Optionally, the searching for a rule matching the keyword based on the keyword and the N compression node layers stored in the M SRAMs includes:

Let i = 1 and k = 1 to determine whether the k-th compressed node layer is stored in the i-th SRAM in the M-blocks;

If the k-th compressed node layer is stored in the i-th SRAM, based on the keyword, find the corresponding to the keyword from at least one compressed node included in the k-th compressed node layer. Leaf node

If a leaf node corresponding to the keyword is found, based on the address of the bucket stored in the found leaf node, a rule matching the keyword is found.

Optionally, after the determining whether the i-th SRAM in the M SRAMs stores at least one compression node included in the k-th compression node layer, the method further includes:

If the k-th compression node layer is not stored in the i-th SRAM, let i = i + 1, and return to determining whether the k-th SRAM is stored in the i-th SRAM in the M-th SRAM. Steps to compress the node layer.

Optionally, after searching for a leaf node corresponding to the keyword from at least one compressed node included in the k-th compressed node layer based on the keyword, the method further includes:

If no leaf node corresponding to the keyword is found, and the i is less than the M, then let i = i + 1, k = k + 1, and return to the judgment M Step of whether the k-th compressed node layer is stored in the i-th SRAM in the block SRAM.

Optionally, after searching for a leaf node corresponding to the keyword from at least one compressed node included in the k-th compressed node layer based on the keyword, the method further includes:

If a leaf node corresponding to the keyword is not found, and the i is equal to the M, then let i = 1, k = k + 1, and return to judge the M SRAMs. Whether the step of the k-th compressed node layer is stored in the i-th SRAM in.

Optionally, if a leaf node corresponding to the keyword is found, searching for a rule matching the keyword based on the address of a bucket stored in the found leaf node includes:

If a leaf node corresponding to the keyword is found, and the i is less than the M, then the address of a bucket stored in the found leaf node is obtained;

Passing the address of the bucket through each of the SRAMs from the i-th SRAM to the M-th SRAM in turn, until the M-th SRAM is output by the M-th SRAM Bucket address

Based on the bucket's address, find a rule that matches the keyword.

According to a second aspect, an access control list management device is provided, and the access control list management device has a function of implementing the behavior of the access control list management method in the first aspect. The apparatus for managing an access control list includes at least one module, and the at least one module is configured to implement the method for managing an access control list provided by the first aspect.

According to a third aspect, an access control list management device is provided. The structure of the access control list management device includes a processor and a memory, and the memory is configured to store the management device supporting the access control list to perform the first aspect. A program for a method for managing an access control list provided, and storing data related to the method for managing an access control list provided by the first aspect described above. The processor is configured to execute a program stored in the memory. The operating device of the storage device may further include a communication bus for establishing a connection between the processor and the memory.

According to a fourth aspect, a computer-readable storage medium is provided. The computer-readable storage medium stores instructions that, when run on a computer, cause the computer to execute the method for managing an access control list according to the first aspect. .

According to a fifth aspect, a computer program product containing instructions is provided, which when executed on a computer, causes the computer to execute the random access method described in the first aspect.

The technical effects obtained by the second aspect, the third aspect, the fourth aspect, and the fifth aspect are similar to the technical effects obtained by the corresponding technical means in the first aspect, and are not repeated here.

The technical solution provided by this application has the beneficial effect of: obtaining the number N of compressed node layers formed by each adjacent preset number of layers on the search tree corresponding to the ACL, and storing N compressed node layers in M blocks On the SRAM, where M is less than N, each SRAM stores at least one compression node included in at least one compression node layer of the N compression node layers. It can be seen that, in the embodiment of the present application, N compression node layers can be stored in less than N SRAMs. In this way, more than one compression node layer can be stored in each SRAM, which avoids only one SRAM in each SRAM. The problem of wasted storage space caused by storing a compressed node layer improves the utilization of the storage space of the SRAM.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram of dividing multiple rules included in an ACL provided by related technologies; FIG.

FIG. 2 is a schematic diagram of a search tree created according to an ACL division process in the related art; FIG.

FIG. 3 is a schematic diagram of an applicable implementation environment of an ACL management method according to an embodiment of the present application; FIG.

4 is a schematic structural diagram of a forwarding device according to an embodiment of the present application;

5 is a flowchart of an ACL management method according to an embodiment of the present application;

6 is a schematic diagram of a compressed node layer of a search tree corresponding to an ACL according to an embodiment of the present application;

7 is a schematic diagram illustrating storing N compression node layers on M SRAMs according to an embodiment of the present application;

8 is a flowchart of an ACL management method according to an embodiment of the present application;

FIG. 9 is a schematic diagram of a distribution of N compression node layers on M SRAMs provided by an embodiment of the present application; FIG.

FIG. 10 is a schematic structural diagram of an access control list management apparatus according to an embodiment of the present application.

detailed description

To make the objectives, technical solutions, and advantages of the present application clearer, the embodiments of the present application will be described in further detail below with reference to the accompanying drawings.

Before explaining the embodiments of the present application in detail, the implementation environment involved in the embodiments of the present application will be described first.

FIG. 3 is a schematic diagram of an implementation environment to which an access control list management method according to an embodiment of the present application is applied. As shown in FIG. 3, the implementation environment may include a transmitting device 301, a forwarding device 302, and a receiving device 303. The transmitting device 301 may communicate with the forwarding device 302 through a wireless network or a wired network, and the receiving device 303 and the forwarding device 302 may also communicate through a wireless network or a wired network.

Exemplarily, the sending-end device 301 may be used to send a message to the forwarding device 302, and the message may be a message sent by the sending-end device 301 to the receiving-end device 303.

The forwarding device 302 includes multiple SRAMs, and the forwarding device 302 may be configured with multiple ACLs. Among them, each ACL can include multiple rules configured by the user. The forwarding device 302 may divide multiple rules in each ACL into multiple buckets, and create a search tree for each ACL according to the division process. Since the number of layers of the ACL search tree may be large, the forwarding device 302 may divide multiple layers included in the search tree of each ACL into multiple compressed node layers, where each compressed node layer includes multiple nodes Stored in at least one compression node. The forwarding device 302 may store multiple compressed node layers included in each ACL in multiple SRAMs.

Optionally, the forwarding device 302 may further include a tri-state content addressable memory (TCAM). Among them, when the forwarding device 302 divides multiple rules in each ACL, it selects rules that can be divided into multiple buckets from among multiple rules included in each ACL, and stores such rules to TCAM. in.

The forwarding device 302 can be used to parse the received message sent by the sending-end device 301, extract a keyword from the message, and find the rule corresponding to the keyword through the search tree of each ACL, and according to the search As a result, the message is processed differently. For example, if found, the forwarding device 302 may forward the message to the receiving device 303; if not found, the forwarding device 302 may refuse to forward the message.

It should be noted that, in the embodiment of the present application, the sending-end device 301 and the receiving-end device 303 may be computer devices such as a smart phone, a tablet computer, a notebook computer, and a desktop computer. The forwarding device 302 may be a router, a switch, or another routing and switching access integrated device.

FIG. 4 is a schematic structural diagram of a forwarding device 302 in the foregoing implementation environment provided by an embodiment of the present application. As shown in FIG. 4, the forwarding device mainly includes a transmitter 3021, a receiver 3022, a memory 3023, a processor 3024, and Communication bus 3025. Those skilled in the art can understand that the structure of the forwarding device 302 shown in FIG. 4 does not constitute a limitation on the forwarding device 302, and may include more or less components than shown in the figure, or combine some components, or different The arrangement of components is not limited in the embodiment of the present application.

The transmitter 3021 may be configured to send data and / or signaling to the receiving device 103. The receiver 3022 may be used to receive data and / or signaling sent by the sending-end device 101.

The memory 3023 may be used to store multiple rules included in the ACL, the search tree of the ACL, and the data sent by the sending device 101 described above, and the memory 3023 may also be used to store the data used to execute the rules provided by the embodiments of the present invention. One or more running programs and / or modules of an ACL storage method. The memory 3023 may be a read-only memory (ROM) or other type of static storage device that can store static information and instructions, a random access memory (random access memory (RAM)), or a device that can store information and instructions. Other types of dynamic storage devices can also be Electrically Erasable Programmable Read-Only Memory (EEPROM), Compact Disc (Read-Only Memory, CD-ROM) or other optical disk storage, Optical disc storage (including compact discs, laser discs, optical discs, digital versatile discs, Blu-ray discs, etc.), magnetic disk storage media or other magnetic storage devices, or can be used to carry or store desired program code in the form of instructions or data structures and can Any other medium accessed by the integrated circuit, but is not limited thereto. The memory 3023 may exist independently, and is connected to the processor 3024 through a communication bus 3025. The memory 3023 may also be integrated with the processor 3024.

The processor 3024 is the control center of the forwarding device 302. The processor 3024 may be a general-purpose central processing unit (CPU), a microprocessor, and an application-specific integrated circuit (Application-Specific Integrated Circuit). , Hereinafter referred to as ASIC), or one or more integrated circuits used to control the execution of the program procedures. The processor 3024 can implement the ACL storage method provided by the embodiment of the present invention by running or executing software programs and / or modules stored in the memory 3023 and calling data stored in the memory 3023.

In addition, the processor 3024 and the memory 3023 can transmit information through a communication bus 3025.

The following describes the ACL management method provided in the embodiments of the present application.

FIG. 5 is a flowchart of an ACL management method according to an embodiment of the present application. The method can be applied to the forwarding device 302 in the implementation environment shown in FIG. 3. The method includes the following steps:

Step 501: Obtain the number N of compressed node layers.

Among them, because the number of rules in the ACL is huge, the search tree corresponding to the ACL often includes many layers. In this case, the forwarding device may start from the first layer of the search tree and treat each adjacent preset number of layers as a compressed node layer, thereby dividing the search tree into multiple compressed node layers, and then forward The device can count the number N of compressed node layers included in the search tree.

It should be noted that, since each compressed node layer includes multiple layers of a search tree, each compressed node layer will include multiple nodes, and the forwarding device can combine multiple nodes in each compressed node layer to store at least Within a compressed node.

FIG. 6 is a schematic diagram of a compressed node layer of a search tree corresponding to an ACL according to an embodiment of the present application. As shown in FIG. 6, assuming that the search tree includes n layers, the forwarding device may start from the first layer, and use the first layer to the fourth layer as the first compression node layer. The compression node layer may include multiple nodes. Stored in a compression node, that is, including a compression node in the first compression node layer. Starting from the fifth layer, the fifth to eighth layers are used as the second compression node layer. It should be noted that in the second compression node layer, the leaf nodes in the fifth layer can be stored in one compression node. In each node except the leaf node as a top node, each top node and the corresponding branch of the node are stored in a compressed node. For example, as shown in FIG. 6, assuming that the fifth layer includes two leaf nodes, the two leaf nodes can be stored in a compressed node, and the remaining 4 nodes other than the leaf nodes can be stored in the four nodes. Each node in the node serves as a top-level node, and each top-level node and the branch derived from each top-level node are stored in a compression node, thereby obtaining four compression nodes. For the ninth layer to the nth layer of the search tree, the forwarding device can process according to the above method, so as to obtain N compressed node layers.

Step 502: Store N compression node layers in M SRAMs, where M is a positive integer less than N, and each SRAM in the M SRAM stores at least one compression node layer of the N compression node layers.

In the related art, when the search tree corresponding to the ACL has N compression node layers, the forwarding device may store at least one compression node included in each compression node layer in a SRAM, that is, N compression node layers are to be stored Requires N blocks of SRAM. In this case, when the number of nodes included in a compressed node layer is small, the storage space of the SRAM storing the compressed node layer will be wasted. In the embodiment of the present application, the forwarding device may store N compression node layers in less than N SRAMs, that is, each SRAM may store at least one compression node layer. In other words, in this application, In the embodiment, a plurality of compression node layers can share a SRAM, which effectively avoids the problem of wasted space of the SRAM.

Exemplarily, in the embodiment of the present application, the forwarding device may store the N compressed node layers in M SRAMs in the following ways.

The first method: According to the sequence of the N compression node layers, starting from the first SRAM of the M SRAMs, and sequentially from the first SRAM to the Mth SRAM, one compression node is stored in each SRAM in order. When it is stored in the Mth SRAM, it starts from the first SRAM in the Mth SRAM and stores a compression node layer in each SRAM in order from the first SRAM to the Mth SRAM, until Until storing N compression node layers.

The forwarding device may determine the sequence of the compressed node layer according to the position of the compressed node layer on the search tree and in a top-down order. That is, the compressed node layer at the top of the search tree is the first compressed node layer, the next layer pointed to by the last node in the first compressed node layer is the second compressed node layer, and so on.

It should be noted that, in the embodiment of the present application, the M SRAMs may also be arranged in a certain order. When storing the N compression node layers, the forwarding device may sequentially store the first compression node layer to the Mth compression node layer in the order of the N compression node layers on the first SRAM to the Mth SRAM. . Among them, the first compression node layer is stored on the first SRAM, the second compression node layer is stored on the second SRAM, the i-th compression node layer is stored on the i-th SRAM, and so on until the Mth After each compression node layer is stored on the Mth SRAM, the forwarding device can return to the first SRAM, store the M + 1th compression node layer on the first SRAM, and store the M + 2th on the second SRAM. Compression node layers, and so on, until all N compression node layers are completely stored. Among them, the i-th SRAM of the M SRAMs will store the i-th compression node layer, the (M + i) -th compression node layer, the (2M + i) -th compression node layer, etc., among which 2M + i Less than or equal to N.

FIG. 7 is a schematic diagram of storing N compression node layers on M SRAMs according to an embodiment of the present application. Here, it is assumed that M = 4 and N = 10. Among them, SRAM1 is the first SRAM, SRAM2 is the second SRAM, and so on. Conde_stage_01 is the first compression node layer, Conde_stage_02 is the second compression node layer, and so on, and Conde_stage_10 is the tenth compression node layer. As shown in FIG. 7, when storing the 10 compression node layers, the forwarding device can store Conde_stage_01 on SRAM1, Conde_stage_02 on SRAM2, Conde_stage_03 on SRAM3, and Conde_stage_04 on SRAM4. After that, the forwarding device can return to SRAM1, store Conde_stage_5 on SRAM1, Conde_stage_6 on SRAM2, Conde_stage_7 on SRAM3, and Conde_stage_8 on SRAM4. After that, the forwarding device can return to SRAM1 again, store Conde_stage_9 on SRAM1, and store Conde_stage_10 on SRAM2. In this way, 10 compression node layers are stored on 4 SRAMs. Among them, Conde_stage_01, Conde_stage_05, and Conde_stage_09 are stored on SRAM1, Conde_stage_02, Conde_stage_06, and Conde_stage_10 are stored on SRAM2, Conde_stage_03, Conde_stage_07 are stored on SRAM3, and Conde_stage is stored on SRAM4. , Conde_stage_08. That is to say, Conde_stage_i, Conde_stage_M + i, Conde_stage_2M + i, Conde_stage_3M + i, etc. will be stored on the SRAMi in the M SRAMs.

The second method: According to the sequence of the N compressed node layers, the N compressed node layers are sequentially divided into Q groups, and the number of compressed node layers included in each of the first Q-1 groups in the Q group is The number of compressed node layers included in the last group in the M, Q groups is less than or equal to M; the i-th compressed node layer in the compressed node layers included in each group in the Q group is stored in the i-th in the M SRAMs In block SRAM, i is an integer greater than 0 and not greater than M.

The foregoing first method mainly introduces the implementation process of storing N compression node layers one by one into M SRAMs. In another possible implementation manner, the forwarding device may first divide the N compressed node layers into Q groups in order, and then store the compressed node layers included in each group in the Q group in parallel.

Exemplarily, the forwarding device may divide each adjacent M compression node layer into a group starting from the first compression node layer according to the sequence of the N compression node layers, thereby obtaining a Q group. If N is an integer multiple of M, each group in the Q group includes M compression node layers. If N is not an integer multiple of M, the number of compressed node layers included in the last group in the Q group will be less than M .

After the N compression node layers are divided into Q groups, the forwarding device can store the first compression node layer in each compression node layer included in each group on the first SRAM and the second compression node in the M SRAMs. The layers are stored on the second SRAM, and so on, until the compressed node layers included in each group are stored.

It can be seen that when the second method is used for storage, after the N compression node layers are divided into Q groups, the forwarding device can store the compression node layers included in each group in the Q group in parallel to speed up the storage. speed.

The third method: According to the sequence of the N compression node layers, starting from the first SRAM of the M SRAMs, and sequentially from the first SRAM to the Mth SRAM, one compression node is stored in each SRAM in order. Layer; when the storage in the Mth SRAM is completed, if the number of remaining compressed node layers is less than M, then according to the size of the remaining storage space of each SRAM in the M SRAM, select the remaining nodes from the M SRAM The number of SRAM layers is the same, and the remaining compression node layers are stored in the selected SRAM. If the number of remaining compression node layers is not less than M, the sequence of the N compression node layers is restarted, starting from the first SRAM in the M SRAMs, and in the order from the first SRAM to the Mth SRAM. A compression node layer is stored in turn on each SRAM.

In this implementation manner, the forwarding device may first store the first compression node layer to the Mth compression node layer of the N compression node layers in the corresponding storage on the first to the Mth SRAMs in sequence. After the block SRAM is stored, the forwarding device can count whether the number of remaining unstored compression node layers is less than M. If it is not less than M, it can start again from the first SRAM, from the first SRAM to the Mth SRAM. It stores the M + 1th compression node layer to the 2Mth compression node layer in turn. If it is less than M, the forwarding device can count the size of the remaining storage space of each SRAM in the M SRAMs, sort them according to the remaining storage space in descending order, and select the remaining storage space first from the sorting result W SRAMs, where W is equal to the number of remaining compressed node layers. The remaining compressed node layers are stored in W SRAMs.

For example, assuming M = 4 and the number of remaining compression node layers is two, the forwarding device can select the SRAM with the most remaining storage space from the four SRAMs and the remaining SRAM is ranked second. Assume that the SRAM with the most remaining storage space is the third SRAM of the 4 SRAMs, and the remaining SRAM is ranked the second SRAM as the first SRAM. One compression node layer is stored in the first SRAM, and the second compression node layer in the remaining compression node layers is stored in the third SRAM.

The above are the three implementation manners for storing N compression node layers on M SRAMs provided in the embodiments of the present application. Optionally, in a possible implementation manner, the forwarding devices may also be stored out of order, randomly. N compression node layers are stored on M SRAMs.

In the embodiment of the present application, the forwarding device may store N compression node layers in less than N SRAMs, that is, multiple compression node layers may share one SRAM, which effectively avoids storing only one in each SRAM. The problem of wasted storage space caused by compression of the node layer improves the utilization of the storage space of the SRAM.

After the N compression node layers are stored on the M SRAMs through the above embodiments, if the forwarding device receives a message, the rules provided by the following embodiments can be used to find the rules that match the message. Based on this, referring to FIG. 8, another ACL management method is provided. The method includes the following steps:

Step 801: Obtain the number N of compressed node layers.

For the implementation of this step, reference may be made to step 501 in the foregoing embodiment.

Step 802: Store N compression node layers in M SRAMs, where M is a positive integer less than N, and each SRAM in the M SRAM stores at least one compression node layer of the N compression node layers.

For the implementation of this step, reference may be made to step 502 in the foregoing embodiment.

Step 803: When a message is received, keywords are extracted from the message.

Among them, according to different rules in the ACL, when a message is received, the forwarding device may extract corresponding keywords from the message according to the rules in the ACL.

For example, the rules in the ACL are used to classify packets based on the source address of the packet, and the forwarding device can extract the source address information in the packet to obtain keywords. As another example, if the rules in the ACL are used to classify packets based on time period information, the forwarding device can obtain the time period information of the packet and use it as a keyword.

Step 804: Based on the keywords and the N compressed node layers stored in the M SRAMs, find a rule that matches the keywords.

After extracting the keywords, the forwarding device can find the leaf nodes that match the keywords from the N compressed node layers stored in the M SRAMs, and then obtain the corresponding nodes based on the addresses of the buckets stored in the found leaf nodes. The keyword matches the rule. If the forwarding device does not find a leaf node matching the keyword in the N compression node layers, the forwarding device may discard the message.

Among them, when looking for a rule that matches a keyword, let i = 1 and k = 1 to determine whether the k-th compressed node layer is stored in the i-th SRAM of the M SRAMs. The k-th compressed node layer, based on keywords, finds the leaf node corresponding to the keyword from at least one compressed node included in the k-th compressed node layer; if a leaf node corresponding to the keyword is found, then Based on the addresses of the buckets stored in the found leaf nodes, find rules that match the keywords.

Exemplarily, the forwarding device may search from the first SRAM to determine whether the first compression node layer is stored in the first SRAM, and if so, may search from at least one compression node included in the first compression node layer. Whether there is a leaf node matching the keyword. If a leaf node matching the keyword is found in the first compression node layer, the forwarding device can obtain the address of the bucket stored in the leaf node and The address of the bucket is transferred from the first SRAM to the second SRAM, from the second SRAM to the third SRAM, and so on, and until the M-th SRAM is passed, the bucket is output by the M-th SRAM. After that, the forwarding device can obtain a rule matching the keyword based on the bucket address to the corresponding bucket.

Optionally, if the k-th compression node layer is not stored in the i-th SRAM, the forwarding device may set i = i + 1, and return to determine whether the k-th is stored in the i-th SRAM in the M-th SRAM. Compact the node layer.

Exemplarily, if the first compression node layer is not stored in the first SRAM, the forwarding device may find the first compression node layer in the second SRAM, and if the second SRAM still does not store the second compression node layer, If there is a compression node layer, the forwarding device can continue to search to the next SRAM until it finds the first compression node layer, and then decides whether to search for the second compression node layer according to the search result in the first compression node layer.

It should be noted that if the forwarding device stores N compression node layers according to the first or second method in the foregoing embodiment, each compression node layer is stored in each SRAM one by one. Therefore, when When searching from the first SRAM, the first compression node layer is stored in the first SRAM, the second compression node layer is stored in the second SRAM, and the i-th compression is correspondingly stored in the i-th SRAM. The node layer does not store the case where the k-th compressed node layer is not stored in the i-th compressed node layer. In this case, the forwarding device may not perform the step of judging whether the k-th compression node layer is stored in the i-th SRAM, but may directly find and compare with the k-th compression node layer stored in the i-th SRAM. The leaf node corresponding to the keyword.

If the forwarding device stores the N compression node layers according to the third method in the foregoing embodiment or randomly, then since two adjacent compression node layers may be stored in two non-adjacent SRAMs, the forwarding device may First determine whether the k-th compressed node layer is stored in the i-th SRAM. If it is, then search for the leaf node corresponding to the keyword in the k-th compressed node layer. If not, continue to find the k-th compressed node in the next SRAM. k compressed node layers until found.

Optionally, if a leaf node corresponding to the keyword is not found, and i is less than M, then i = i + 1, k = k + 1, and return to determine whether the i-th SRAM in the M SRAMs is Steps for k-th compressed node layer are stored.

Specifically, if the k-th compressed node layer is stored in the i-th SRAM, but no leaf node corresponding to the keyword is found in the k-th compressed node layer, and the i-th SRAM is not in the M-th SRAM For the last SRAM, the forwarding device can go to the next SRAM of the i-th SRAM to find the next compression node layer of the k-th compression node layer. If the next compression node layer is stored in the next SRAM, the forwarding device can Find a leaf node corresponding to the keyword in a compressed node layer.

Optionally, if a leaf node corresponding to the keyword is not found, and i is equal to M, then i = 1, k = k + 1, and return to determine whether the i-th SRAM in the M SRAMs is stored in the i-th SRAM. The kth step of compressing the node layer.

Exemplarily, if the k-th compression node layer is stored in the i-th SRAM, but no leaf node corresponding to the keyword is found in the k-th compression node layer, and the i-th SRAM is in the M-th SRAM The last SRAM, the forwarding device needs to start again from the first SRAM, and find the next compression node layer of the kth compression node layer in the first SRAM.

Next, the searching processes corresponding to the foregoing different storage methods will be described by examples.

(1) The forwarding device stores the N compressed node layers according to the first method or the second method.

Assuming M = 4 and N = 10, whether it is stored in the first way or the second way, the distribution of the final N compressed node layers in the M SRAM is shown in FIG. 7. Taking this as an example, when performing a search, the forwarding device can start searching from SRAM1, and first find the leaf node corresponding to the keyword in Conde_stage_01 stored in SRAM1. If a leaf node is found, the forwarding device can pass the address of the bucket stored in the leaf node from SRAM1 to SRAM2, then from SRAM2 to SRAM3, from SRAM3 to SRAM4, and the forwarding device obtains the address of the bucket from the SRAM4. And according to the address of the bucket, the corresponding rule in the bucket is obtained.

If no leaf node is found in Conde_stage_02, the forwarding device can search in Conde_stage_02 stored in SRAM2. If found, it can be processed by referring to the foregoing method. If it is not found, it can continue to search downward. If the leaf node is not found until Conde_stage_04 in SRAM4, the forwarding device may return to SRAM1 and continue to find leaf nodes in order starting from Conde_stage_05.

(2) The forwarding device stores the N compressed node layers according to the third method.

Assuming M = 4 and N = 10, storage is performed according to the third method. The distribution of 10 compression node layers on 4 SRAMs is shown in FIG. 9. In this case, assuming that the forwarding device does not find any leaf nodes in Conde_stage_01 to Conde_stage_04 stored in SRAM1-SRAM4, the forwarding device returns to SRAM1 and determines whether Conde_stage_05 is stored on SRAM1. Because Conde_stage_05 is stored on SRAM1, then The forwarding device can find the leaf node in Conde_stage_05. If it is still not found, the forwarding device can determine whether Conde_stage_06 is stored on SRAM2. Since Conde_stage_06 is not stored on SRAM2, the forwarding device can continue to determine whether Conde_stage_06 is stored on SRAM3. , Conde_stage_06 is stored in SRAM3, then the forwarding device looks for the leaf node corresponding to the keyword in Conde_stage_06. If found, the forwarding device can obtain the address of the bucket from the found leaf node and pass the address of the bucket to SRAM4. The forwarding device can obtain the address of the bucket from SRAM4, and find the rule matching the keyword in the corresponding bucket according to the address of the bucket.

In the embodiment of the present application, the forwarding device can find the leaf nodes corresponding to the keywords in the N compressed node layers stored in the M blocks of SRAM. As long as the leaf nodes corresponding to the keywords are found, the forwarding device can The address of the bucket stored in the leaf node is passed to the Mth SRAM to end the search process. In the related technology, because N compression node layers are sequentially stored in N SRAMs, no matter which compression node layer among the N compression node layers the forwarding device finds the leaf node, the forwarding device can only be in the Nth block. Only the SRAM can obtain the address of the bucket stored in the leaf node. That is, for any rule in the ACL, the search delay is equal to the delay from the first compressed node layer to the last compressed node layer. It can be seen that, through the storage method and corresponding search method provided in the embodiments of the present application, when the forwarding device finds a leaf node corresponding to a keyword in a certain compressed node layer, the search process can be ended as early as possible, which is effective Reduced search delay.

FIG. 10 is a block diagram of an access control list management apparatus according to an embodiment of the present invention. The apparatus is applied to a forwarding device. As shown in FIG. 10, the apparatus 1000 includes an acquisition module 1001 and a storage module 1002.

The obtaining module 1001 is configured to execute step 501 in the foregoing embodiment;

The storage module 1002 is configured to execute step 502 in the foregoing embodiment.

Optionally, the storage module 1002 is specifically configured to:

According to the sequence of the N compression node layers, starting from the first SRAM of the M SRAMs, and sequentially from the first SRAM to the Mth SRAM, one compression node layer is stored in each SRAM in order;

When it is stored in the Mth SRAM, it starts from the first SRAM in the Mth SRAM, and sequentially stores a compression node layer in each SRAM in the order from the first SRAM to the Mth SRAM, until the storage is completed. N compression node layers.

Optionally, the device further includes:

An extraction module for extracting keywords from a message when a message is received;

A search module is used to find rules matching keywords based on keywords and N compressed node layers stored in M SRAMs.

Optionally, the search module includes:

A judging sub-module, for setting i = 1 and k = 1 to judge whether the k-th compressed node layer is stored in the i-th SRAM in the M SRAMs;

A first search submodule, configured to find, if there is a k-th compressed node layer in the i-th SRAM, at least one compression node included in the k-th compressed node layer based on a keyword, Leaf node

The second search submodule is configured to, if a leaf node corresponding to the keyword is found, find a rule matching the keyword based on the address of a bucket stored in the found leaf node.

Optionally, the search module further includes:

The first trigger sub-module is used to set i = i + 1 if the k-th compression node layer is not stored in the i-th SRAM and trigger the judgment sub-module to determine whether the i-th SRAM in the M-block SRAM is stored There is a k-th compression node layer.

Optionally, the search module further includes:

The second triggering sub-module is used to determine i = i + 1 and k = k + 1 if no leaf node corresponding to the keyword is found and i is less than M, and trigger the judging sub-module to judge the M SRAMs. Whether the k-th compressed node layer is stored in the i-th SRAM of the.

Optionally, the search module further includes:

The third triggering sub-module is used to determine if the leaf node corresponding to the keyword and i is equal to M, then i = 1, k = k + 1, and trigger the judging sub-module to judge the first Whether the k-th compressed node layer is stored in the i SRAM.

Optionally, the second search submodule is specifically configured to:

If a leaf node corresponding to the keyword is found, and i is less than M, the address of the bucket stored in the found leaf node is obtained;

Pass the address of the bucket through each of the SRAMs from the i-th SRAM to the M-th SRAM in turn, until the M-th SRAM outputs the bucket address;

Based on the bucket address, find rules that match the keywords.

In summary, in the embodiment of the present application, the forwarding device can store N compression node layers in less than N SRAMs, that is, multiple compression node layers can share one SRAM, which effectively avoids each block. The problem of wasted storage space caused by storing only one compression node layer in the SRAM improves the utilization of the storage space of the SRAM. In addition, in the embodiment of the present application, the leaf nodes corresponding to the keywords can be found in the N compressed node layers stored in the M blocks of SRAM. As long as the leaf nodes corresponding to the keywords are found, the forwarding device can The address of the bucket stored in the leaf node is passed to the Mth SRAM to end the search process. That is, with the storage method and corresponding search method provided in the embodiments of the present application, when the forwarding device finds a leaf node corresponding to a keyword in a certain compressed node layer, the search process can be ended as early as possible, effectively reducing Search delay.

The management device of the access control list provided in the foregoing embodiment, when managing the access control list, uses only the division of the functional modules as an example for illustration. In actual applications, the above functions can be allocated by different functional modules as needed. The internal structure of the device is divided into different functional modules to complete all or part of the functions described above. In addition, the device for managing an access control list provided by the foregoing embodiment belongs to the same concept as the method embodiments shown in FIG. 5 and FIG. 8, and the specific implementation process thereof is detailed in the method embodiment, and details are not described herein again.

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, it 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 the computer instructions are loaded and executed on a computer, the processes or functions according to the embodiments of the present invention are wholly or partially generated. The computer may be a general purpose computer, a special purpose computer, a computer network, or other programmable device. The computer instructions may be stored in a computer-readable storage medium or transmitted from one computer-readable storage medium to another computer-readable storage medium, for example, the computer instructions may be transmitted from a website site, computer, server, or data center through a cable (For example: coaxial cable, optical fiber, Digital Subscriber Line (DSL)) or wireless (for example: infrared, wireless, microwave, etc.) to another website, computer, server or data center for transmission. 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, a data center, or the like that includes one or more available medium integration. The usable medium may be a magnetic medium (for example, a floppy disk, a hard disk, a magnetic tape), an optical medium (for example, a Digital Versatile Disc (DVD)), or a semiconductor medium (for example, a solid state disk (Solid State Disk) (SSD)) Wait.

That is, in the embodiment of the present invention, a computer-readable storage medium is provided. When the computer-readable storage medium runs on the computer, the computer is caused to execute the steps of the method for managing an access control list shown in FIG. 5 or FIG.

A person of ordinary skill in the art may understand that all or part of the steps for implementing the foregoing embodiments may be implemented by hardware, or may be instructed by a program to complete related hardware. The program may be stored in a computer-readable storage medium. The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk.

The above-mentioned embodiments provided by this application are not intended to limit this application. Any modification, equivalent replacement, or improvement made within the spirit and principle of this application shall be included in the protection scope of this application. Inside.

Claims (16)

An access control list management method is characterized in that the method includes: Obtain the number N of compressed node layers. The compressed node layer is formed by a layer on the search tree corresponding to the access control list ACL, and the compressed node layer includes at least one compressed node, where N is greater than or equal to 1 An integer Storing the N compression node layers in M SRAMs, where M is an integer greater than 0 and less than the N, and each of the M SRAMs stores the N compression node layers At least one compression node layer. The method according to claim 1, wherein the storing the N compression node layers in the M SRAMs comprises: According to the sequence of the N compression node layers, starting from the first SRAM of the M SRAMs, and sequentially from the first SRAM to the Mth SRAM, one compression is stored in each SRAM in turn. Node layer When it is stored in the Mth SRAM, it starts from the first SRAM in the Mth SRAM, and sequentially stores a compression node layer in each SRAM in the order from the first SRAM to the Mth SRAM. Until the N compressed node layers are stored. The method according to claim 1 or 2, further comprising: When a message is received, extract keywords from the message; Based on the keyword and the N compressed node layers stored in the M SRAMs, a rule matching the keyword is searched. The method according to claim 3, wherein the finding a rule matching the keyword based on the keyword and the N compression node layers stored in the M SRAMs comprises: Let i = 1 and k = 1 to determine whether the k-th compressed node layer is stored in the i-th SRAM in the M-blocks; If the k-th compressed node layer is stored in the i-th SRAM, based on the keyword, find the corresponding to the keyword from at least one compressed node included in the k-th compressed node layer. Leaf node If a leaf node corresponding to the keyword is found, based on the address of the bucket stored in the found leaf node, a rule matching the keyword is found. The method according to claim 4, wherein after determining whether the i-th SRAM in the M SRAMs stores at least one compression node included in the k-th compression node layer, further comprising: If the k-th compression node layer is not stored in the i-th SRAM, let i = i + 1, and return to determining whether the k-th SRAM is stored in the i-th SRAM in the M-th SRAM. Steps to compress the node layer. The method according to claim 4 or 5, characterized in that, based on the keyword, searching for a leaf corresponding to the keyword from at least one compressed node included in the k-th compressed node layer. After the node, it also includes: If a leaf node corresponding to the keyword is not found, and the i is smaller than the M, then let i = i + 1, k = k + 1, and return to judge the M Step of whether the k-th compressed node layer is stored in the i-th SRAM in the block SRAM. The method according to claim 5 or 6, wherein, based on the keyword, searching for a leaf corresponding to the keyword from at least one compressed node included in the k-th compressed node layer. After the node, it also includes: If a leaf node corresponding to the keyword is not found, and the i is equal to the M, then let i = 1, k = k + 1, and return to judge the M SRAMs. Whether the step of the k-th compressed node layer is stored in the i-th SRAM in. The method according to any one of claims 4 to 7, characterized in that, if a leaf node corresponding to the keyword is found, based on the address of a bucket stored in the found leaf node, the search and the The keywords match the rules, including: If a leaf node corresponding to the keyword is found, and the i is less than the M, then the address of a bucket stored in the found leaf node is obtained; Passing the address of the bucket through each of the SRAMs from the i-th SRAM to the M-th SRAM in turn, until the M-th SRAM is output by the M-th SRAM Bucket address Based on the bucket's address, find a rule that matches the keyword. An access control list management device is characterized in that the device includes: An obtaining module, configured to obtain a number N of compressed node layers, where the compressed node layer is formed by a layer on a search tree corresponding to an access control list ACL, and the compressed node layer includes at least one compressed node, the N Is an integer greater than or equal to 1; A storage module, configured to store the N compression node layers in M SRAMs, where M is an integer greater than 0 and less than the N, and each of the M SRAMs stores the N At least one of the compression node layers. The apparatus according to claim 9, wherein the storage module is specifically configured to: According to the sequence of the N compression node layers, starting from the first SRAM of the M SRAMs, and sequentially from the first SRAM to the Mth SRAM, one compression is stored in each SRAM in turn. Node layer When it is stored in the Mth SRAM, it starts from the first SRAM in the Mth SRAM, and sequentially stores a compression node layer in each SRAM in the order from the first SRAM to the Mth SRAM. Until the N compressed node layers are stored. The device according to claim 9 or 10, wherein the device further comprises: An extraction module, configured to extract keywords from a message when a message is received; A search module, configured to search for a rule matching the keyword based on the keyword and the N compression node layers stored in the M SRAMs. The apparatus according to claim 11, wherein the search module comprises: A judging sub-module, configured to make i = 1 and k = 1 to judge whether the k-th compressed node layer is stored in the i-th SRAM in the M SRAMs; A first searching sub-module, configured to search, from the at least one compression node included in the k-th compression node layer, if the k-th compression node layer is stored in the i-th SRAM; Leaf nodes corresponding to the keywords; A second search submodule is configured to, if a leaf node corresponding to the keyword is found, find a rule matching the keyword based on the address of a bucket stored in the found leaf node. The apparatus according to claim 12, wherein the search module further comprises: A first triggering sub-module configured to make the i = i + 1 if the k-th compression node layer is not stored in the i-th SRAM, and trigger the judging sub-module to judge the M-SRAM Whether the k-th compressed node layer is stored in the i-th SRAM of the. The apparatus according to claim 12 or 13, wherein the search module further comprises: A second triggering sub-module configured to make i = i + 1 and k = k + 1 if no leaf node corresponding to the keyword is found and i is smaller than M And triggering the judging sub-module to judge whether the k-th compression node layer is stored in the i-th SRAM in the M SRAMs. The apparatus according to claim 13 or 14, wherein the search module further comprises: The third triggering sub-module is configured to: if no leaf node corresponding to the keyword is found, and the i is equal to the M, let i = 1, k = k + 1, and trigger The judging sub-module judges whether the k-th compressed node layer is stored in the i-th SRAM in the M-blocks of SRAM. The apparatus according to any one of claims 12 to 15, wherein the second search submodule is specifically configured to: If a leaf node corresponding to the keyword is found, and the i is less than the M, then the address of a bucket stored in the found leaf node is obtained; Passing the address of the bucket through each of the SRAMs from the i-th SRAM to the M-th SRAM in turn, until the M-th SRAM is output by the M-th SRAM Bucket address Based on the bucket's address, find a rule that matches the keyword.

Images