CN111988231A - Mask five-tuple rule matching method and device - Google Patents

Abstract

A mask five-tuple rule matching method is applied to a Ternary Content Addressable Memory (TCAM) chip and comprises the following steps: merging bit feature recognition is carried out on suffix masks in mask quintuple rules in the Database part, and a plurality of mask quintuple rules containing recognized merging bits are merged into one rule; storing the matching results corresponding to the merged rules into the UserData part corresponding to the merged rules together, and distributing the merged bits as indexes to the corresponding matching results respectively; and after the five-tuple information of the data message is matched with the merged rule, indexing a final matching result based on the merging bit. In addition, the embodiment of the invention also provides a rule matching device. By the method and the device provided by the embodiment of the invention, the mask quintuple rule capacity which can be stored by TCAM table item resources can be effectively increased, the utilization rate is increased, and the cost is saved.

Description

Mask five-tuple rule matching method and device

Technical Field

The invention relates to the field of network data processing, in particular to a mask five-tuple rule matching method.

Background

In the field of communication technology, an access control entry of a mask quintuple includes a quintuple field and a mask field. The quintuple is a necessary attribute tuple of a data packet in a TCP/IP protocol, and comprises five elements including a source IP address (SIP), a Source Port (SP), a destination IP address (DIP), a Destination Port (DP) and a protocol type (P). And the mask field is the same as the five-tuple field in length, corresponds to the five-tuple field one by one and supports masking according to any bit.

In the existing network data traffic processing device, the mask quintuple function is usually implemented by a ternary content addressable memory TCAM chip. Each bit in general memory can only represent two values: 0 or 1, while TCAM can represent three values per bit: 0. 1 and X, X being indifferent, this X is actually controlled by a corresponding mask bit, in fact the TCAM is physically 2 bits per bit. Just by means of the state bit which is not concerned about, matching based on any mask becomes possible, and the purpose of fuzzy searching matching is achieved.

Mask table entry resources based on TCAM can be divided into two parts, namely Database and User Data, wherein the Database stores table entry matching contents, and the User Data stores results returned after matching. Particularly, Database storage space is a TCAM tri-state storage resource with high price, and User Data storage space is a high-speed memory resource, supports plug-in and has sufficient space capacity.

In the prior art, a mode that 1 mask quintuple rule corresponds to 1 TCAM table entry is adopted, and with the explosive growth of data traffic in the era of big data of the internet, a large number of mask quintuple rules need to be stored to process the received traffic. However, limited by the memory capacity of the TCAM, the number of mask quintuple rules that can be stored in the TCAM entry resource is limited; meanwhile, since TCAMs are very energy consuming and expensive, it is impractical to increase the capacity of TCAMs to accommodate more mask quintuple rules in order to adapt to large-scale traffic scenarios, and at this time, the TCAM storage space has become a bottleneck.

Disclosure of Invention

The invention provides a mask quintuple rule matching method and device, aiming at the problems of high overhead of mask quintuple rule TCAM storage space, low rule capacity expansion and the like in the conventional network data traffic processing equipment.

In one aspect, an embodiment of the present invention provides a mask quintuple rule matching method, which includes the following specific steps:

firstly, merging bit feature recognition is carried out on a suffix mask in a mask quintuple rule in a Database part, and a plurality of mask quintuple rules containing recognized merging bits are merged into one rule;

secondly, storing the matching results corresponding to the merged rules into the User Data part corresponding to the merged rules together, and distributing the merging bits as indexes to the corresponding matching results respectively;

and thirdly, after the quintuple information of the data message is matched with the merging rule, indexing a final matching result based on the merging bit.

On the other hand, the first step in the method for matching a mask five-tuple rule provided by the embodiment of the present invention specifically includes the following steps:

2.1 identifying that the changed bit in the SIP suffix mask field in the mask quintuple rules is set to be in a don't care state;

2.2 the bit with change is used as merging bit, and a plurality of mask quintuple rules containing the merging bit are merged into a rule which occupies a rule storage space.

On the other hand, in the method for matching mask five-tuple rules provided in the embodiment of the present invention, a rule valid flag is set in a matching result portion corresponding to each rule, and the flag is set when a mask rule table entry is created, so as to indicate whether a corresponding mask five-tuple rule exists.

In another aspect, an embodiment of the present invention provides a mask quintuple rule matching apparatus applied in a TCAM chip of a ternary content addressable memory, including:

the rule merging module is used for carrying out merging bit feature identification on a suffix mask in a mask quintuple rule in the Database part and merging a plurality of mask quintuple rules containing identified merging bits into one rule;

a matching result indexing module for storing matching results corresponding to the merged rules in the User Data part corresponding to the merged rules together, and allocating the merged bits as indexes to the corresponding matching results;

and the matching module is used for indexing a final matching result based on the merging bit after the five-tuple information of the data message is matched with the merging rule.

On the premise of meeting the merging characteristics, the number and the size of merging bits, the number of mask rules which can be merged into 1 rule, and the number and the size of result parts can be flexibly adjusted and mastered, so that the method is not only suitable for the IPv4 mask quintuple rule, but also suitable for the IPv6 mask quintuple rule.

By combining the invention, when a large amount of mask quintuple rules need to be stored to process the received flow, on the basis of not increasing the TCAM memory capacity, the invention effectively improves the mask quintuple rule capacity which can be stored by TCAM table item resources, improves the utilization rate and saves the cost, thereby achieving two purposes.

Additional aspects, features and/or advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.

Drawings

These and/or other aspects, features and advantages of the present invention will become apparent and more readily appreciated from the following description of the embodiments, taken in conjunction with the accompanying drawings of which:

FIG. 1 is a schematic diagram of an IPv4 mask quintuple rule in the prior art provided by the present invention

FIG. 2 is a diagram illustrating a data structure of a SIP field in an IPv4 mask quintuple rule in the prior art according to the present invention

FIG. 3 is a schematic diagram of a rule of a merged mask quintuple according to the present invention

FIG. 4 is a flowchart of an IPv4 mask quintuple rule matching method provided by the invention

Detailed Description

Reference will now be made in detail to exemplary embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the concept of the invention to those skilled in the art. The exemplary embodiments are described below in order to explain the present invention by referring to the figures.

The embodiment of the invention provides a mask quintuple rule matching method, which combines a plurality of rules to share a Database in an algorithm-assisted mode by using a suffix mask mode and is matched with User Data for auxiliary search, namely physical resources are utilized to the maximum extent by elaborately designing and optimizing TCAM table items, so that the aim of improving rule capacity is fulfilled.

The general TCAM chip has the requirement of minimum bit number alignment for the Database part. Referring to fig. 1, the minimum entry matching length of the TCAM is 80bits (10 bytes), the maximum entry matching length is 640bits (80 bytes), and the configurable entry matching length is 10 bytes, 20 bytes, 40 bytes, 60 bytes, and 80 bytes.

Taking the IPv4 mask quintuple rule as an example, the length of the SIP + DIP + SP + DP + P quintuple is 13 bytes, and according to the requirement of minimum bit number alignment, a single IPv4 mask quintuple rule actually occupies 20 bytes in length, which results in 7-byte space waste.

Taking the IPv6 mask quintuple rule as an example, the length of the SIP + DIP + SP + DP + P quintuple is 37 bytes, and according to the requirement of minimum bit number alignment, a single IPv6 mask quintuple rule actually occupies 40 bytes in length, which results in 3 bytes of space waste.

Example 1

Taking an example of a network data traffic processing device, there are 3 IPv4 mask quintuple rules, whose SIP and DIP address fields are expressed in the form of suffix masks, and SP, DP and P fields are all masked 0 and are not concerned, and the result length is fixed 4 bytes, as shown in table 1:

Database	User Data
		SIP＝1.1.1.0/24，DIP＝2.2.2.0/24，SP＝10000，DP＝80，P＝6	Result A
SIP＝1.1.2.0/24，DIP＝2.2.2.0/24，SP＝10000，DP＝80，P＝6	Result B
		SIP＝1.1.3.0/24，DIP＝2.2.2.0/24，SP＝10000，DP＝80，P＝6	Result C

TABLE 1

According to the conventional storage mode, 3 regular storage spaces are occupied, the don't care part is represented by X, the TCAM storage space consumed by the 3 mask quintuple rule matching part in table 1 is 20 × 3-60 bytes, and as a result, the storage space consumed by the part is 4 × 3-12 bytes, as shown in fig. 1.

The rule matching method provided by the embodiment comprises the following steps:

firstly, merging bit feature recognition is carried out on a suffix mask in a mask quintuple rule in a Database part, and a plurality of mask quintuple rules containing recognized merging bits are merged into one rule;

secondly, storing the matching results corresponding to the merged rules into the User Data part corresponding to the merged rules together, and distributing the merging bits as indexes to the corresponding matching results respectively;

and thirdly, after the quintuple information of the data message is matched with the merging rule, indexing a final matching result based on the merging bit.

The first step specifically comprises: firstly, merging bit feature recognition is carried out on a suffix mask in a mask quintuple rule in a Database part, referring to table 1 and fig. 1, the change rule of the quintuple part of 3 rules is observed, and the change of 2 bits exists only in a SIP field, as shown in fig. 2.

And then, rule merging is carried out, and according to the change rule of 2 bits from '01' to '10' to '11', 3 rules are found to be capable of being merged actually, and the merging position of 2 bits is set to be in a state of no concern. After merging, the value of the 2-bit merging bit is used as the offset of the result part to index the result corresponding to each rule. The merged result takes one rule space, but User Data will contain the results of 3 rules. The change in the rule storage space is shown in fig. 3.

The currently adopted mode that 3 mask quintuple rules correspond to 1 TCAM table entry can improve the capacity of the TCAM rule by 3 times, the use of general storage resources is not increased, and the capacity of the IPv4 mask quintuple rule is effectively improved.

Example 2

In the rule matching method provided by this embodiment, a rule valid flag is introduced into a result portion corresponding to each rule, and occupies a 1-bit storage space, and the flag is set when a mask rule table entry is created, so as to indicate whether a corresponding mask quintuple rule exists.

The merged rule uses the value of the 2-bit merging bit as the offset of the result part to index the result corresponding to each rule, and judges whether the rule exists according to whether the rule valid flag in the result is set, the specific rule matching process is shown in fig. 4, and the specific steps include:

step 4.1, the procedure starts;

step 4.2, inputting a data message;

step 4.3, extracting quintuple information according to the data message, and sending the quintuple information into the TCAM for searching the rule table items;

step 4.4, the merged rule uses the value of the merging bit as the offset of the result part to index the result corresponding to each rule;

step 4.5, judging whether the rule exists according to whether the rule valid flag in the result is set, if so, executing step 11.6, otherwise, executing step 11.7;

step 4.6, outputting a rule table item matching result;

step 4.7, the procedure is ended;

example 3

The mask quintuple rule matching device applied to the ternary content addressable memory TCAM chip provided by the embodiment specifically includes:

the rule merging module is used for carrying out merging bit feature identification on a suffix mask in a mask quintuple rule in the Database part and merging a plurality of mask quintuple rules containing identified merging bits into one rule;

a matching result indexing module for storing matching results corresponding to the merged rules in the User Data part corresponding to the merged rules together, and allocating the merged bits as indexes to the corresponding matching results;

and the matching module is used for indexing a final matching result based on the merging bit after the five-tuple information of the data message is matched with the merging rule.

In a rule matching apparatus provided in this embodiment, the rule merging module further includes: a merging bit identification module for identifying the changed bit in the SIP suffix mask field in the mask quintuple rules to be set as a don't care state; and the merging operation module is used for merging a plurality of mask quintuple rules containing the merging bit into a rule by taking the bit with the change as the merging bit, and the rule storage space is occupied by the merging operation module.

In the rule matching apparatus provided in this embodiment, the mask quintuple rule may be an IPv4 mask quintuple rule, and the merge bit is 2-bit information with a change in an SIP suffix mask field, and the 2-bit information included in the original rule is used as an index and is respectively allocated to a plurality of corresponding matching results after merge storage.

The rule matching apparatus provided in this embodiment further includes a rule validity checking module, configured to set a rule validity flag in a matching result portion corresponding to each rule, where the flag is set when a mask rule table entry is created, and is used to indicate whether a corresponding mask quintuple rule exists.

In the rule matching apparatus provided in this embodiment, the matching result indexing module specifically includes:

the extraction module is used for extracting quintuple information according to the data message and sending the quintuple information into the TCAM for searching the rule table items;

the offset index module is used for matching the quintuple information of the data message with the merged rule, and then the merged rule uses the value of the merging bit as the offset of the result part to index the matching result corresponding to each rule;

and the validity verification module is used for judging whether the rule exists according to the rule validity mark, outputting a matching result if the rule exists, and ending if the rule does not exist.

Although a few exemplary embodiments of the present invention have been shown and described, it would be appreciated by those skilled in the art that changes may be made in these exemplary embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the claims and their equivalents.

Claims (10)

1. A mask five-tuple rule matching method is applied to a Ternary Content Addressable Memory (TCAM) chip and specifically comprises the following steps:

firstly, merging bit feature recognition is carried out on a suffix mask in a mask quintuple rule in a Database part, and a plurality of mask quintuple rules containing recognized merging bits are merged into one rule;

secondly, storing the matching results corresponding to the merged rules into the User Data part corresponding to the merged rules together, and distributing the merging bits as indexes to the corresponding matching results respectively;

and thirdly, after the quintuple information of the data message is matched with the merging rule, indexing a final matching result based on the merging bit.

2. The method of claim 1, wherein the first step specifically comprises the steps of:

2.1 identifying that the changed bit in the SIP suffix mask field in the mask quintuple rules is set to be in a don't care state;

2.2 the bit with change is used as merging bit, and a plurality of mask quintuple rules containing the merging bit are merged into a rule which occupies a rule storage space.

3. The method as claimed in claim 1 or 2, wherein when the mask quintuple rule is IPv4 mask quintuple rule, the merge bit is 2-bit information with change in SIP suffix mask field, and the 2-bit information included in the original rule is used as index to be respectively allocated to a plurality of corresponding match results after merge storage.

4. The method as claimed in claim 3, wherein a rule valid flag is set in the matching result portion corresponding to each rule, and the flag is set when the mask rule table entry is created, so as to indicate whether the corresponding mask quintuple rule exists.

5. The method for matching a mask quintuple rule according to claim 4, wherein the third step specifically comprises the steps of:

3.1 extracting quintuple information according to the data message, and sending the quintuple information into a TCAM (ternary content addressable memory) for searching a rule table item;

3.2 after the five-tuple information of the data message is matched with the merged rule, the merged rule uses the value of the merging bit as the offset of the result part to index the matching result corresponding to each rule;

3.3 judging whether the rule exists according to the rule valid mark, if so, outputting a matching result, and if not, ending.

6. A mask five-tuple rule matching device applied to a Ternary Content Addressable Memory (TCAM) chip is characterized by comprising the following components:

the rule merging module is used for carrying out merging bit feature identification on a suffix mask in a mask quintuple rule in the Database part and merging a plurality of mask quintuple rules containing identified merging bits into one rule;

a matching result indexing module for storing matching results corresponding to the merged rules in the User Data part corresponding to the merged rules together, and allocating the merged bits as indexes to the corresponding matching results;

and the matching module is used for indexing a final matching result based on the merging bit after the five-tuple information of the data message is matched with the merging rule.

7. The mask quintuple rule matching device of claim 6, wherein the rule merge module further comprises:

a merging bit identification module for identifying the changed bit in the SIP suffix mask field in the mask quintuple rules to be set as a don't care state;

and the merging operation module is used for merging a plurality of mask quintuple rules containing the merging bit into one rule by taking the bit with the change as the merging bit, and the rule storage space is occupied by the merging operation module.

8. The mask quintuple rule matching device of claim 6 or 7, wherein when the mask quintuple rule is the IPv4 mask quintuple rule, the merge bit is 2-bit information with a change in an SIP suffix mask field, and the 2-bit information included in the original rule is respectively allocated as an index to a plurality of corresponding matching results after the merge storage.

9. The mask quintuple rule matching device of claim 8, further comprising a rule validity checking module for setting a rule valid flag in a matching result portion corresponding to each rule, wherein the flag is set when the mask rule table entry is created, so as to indicate whether the corresponding mask quintuple rule exists.

10. The mask quintuple rule matching device according to claim 9, wherein the matching result indexing module specifically comprises:

the extraction module is used for extracting quintuple information according to the data message and sending the quintuple information into the TCAM for searching the rule table items;

the offset index module is used for matching the quintuple information of the data message with the merged rule, and then the merged rule uses the value of the merging bit as the offset of the result part to index the matching result corresponding to each rule;

and the validity verification module is used for judging whether the rule exists according to the rule validity mark, outputting a matching result if the rule exists, and ending if the rule does not exist.

Images