CN-122027695-A - TCAM rule matching method, device, equipment and readable storage medium

CN122027695ACN 122027695 ACN122027695 ACN 122027695ACN-122027695-A

Abstract

The invention discloses a TCAM rule matching method, a device, equipment and a readable storage medium, which are applied to the technical field of communication and comprise the steps of carrying out matching search on a data packet in a first-level TCAM and a second-level TCAM in sequence to determine whether a corresponding target rule is found, executing actions corresponding to the target rule on the data packet if the corresponding target rule is matched in any one-level TCAM, and executing actions corresponding to the target rule in RAM if the corresponding target rule is not matched in double-level TCAM. According to the invention, by designing the double-layer TCAM, part of rule dependence is isolated by physical layering, the dependence processing pressure of the single-layer TCAM is reduced, the logic correctness is ensured, and the concrete number of wildcards is reduced to the greatest extent, so that the space utilization rate of the TCAM is remarkably improved, and the cache rate of the hotness rule is improved.

Inventors

LI QING
GUO LEI
LUAN ZEYU
LI KEJUN
XU HAIDONG
WANG YU

Assignees

鹏城实验室

Dates

Publication Date: 20260512
Application Date: 20260206

Claims (10)

1. A TCAM rule matching method, comprising: The method comprises the steps of obtaining a double-layer TCAM constructed based on a heat value of a rule, wherein the double-layer TCAM comprises a first-level TCAM storing a first priority rule and a second-level TCAM storing a second priority rule, the priority of the first priority rule is higher than that of the second priority rule, and no dependency exists between the rules in the first-level TCAM and between the rules in the second-level TCAM; Carrying out matching search on the data packet in the first-level TCAM and the second-level TCAM in sequence, and determining whether a corresponding target rule is found; If the corresponding target rule is matched in any level of TCAM, executing the action corresponding to the target rule on the data packet; And if the double-layer TCAM is not matched with the corresponding target rule, matching the target rule with a full rule table in the RAM, and executing the action corresponding to the target rule in the RAM on the data packet.
2. The TCAM rule matching method of claim 1, further comprising, prior to obtaining a dual layer TCAM constructed based on the rule hotness value: The method comprises the steps of obtaining a first rule heat determined based on a sudden heat prediction model and a second rule heat determined based on a steady-state heat prediction model, wherein the sudden heat prediction model is a heat prediction model determined by a ternary matching rule obtained by processing sudden flow training data by using a density-based clustering algorithm; performing edge truncation processing on the rule graph by utilizing a partitionable dependency graph based on heat driving based on the first rule heat and the second rule heat to obtain a target dependency sub-graph, wherein the edge truncation processing comprises edge truncation processing on edges of a parent rule belonging to a secondary TCAM, edge truncation processing on edges corresponding to a low-heat rule, and edge truncation processing on rules with depth exceeding 2, and the low-heat rule is a rule with heat lower than a set value; And determining the double-layer TCAM based on the relation of the rules in the target dependency subgraph.
3. The rule matching method of claim 2, further comprising, prior to obtaining the first rule heat determined based on the burst heat prediction model and the second rule heat determined based on the steady state heat prediction model: Determining a target table, wherein the target table comprises a main table and a sub-table, hash functions corresponding to the main table and the sub-table are different, the main table is divided into a T period and a T period according to a time period, the value of T is smaller than T, the attribute of the T period comprises a stream ID recorded in the T period and a corresponding characteristic, and the attribute of the T period comprises the stream ID recorded in the T period, the number of data packets arrived by the stream and a time interval parameter between current arrival and last arrival; Determining whether a timestamp in a currently arrived packet is within a t period; If the time period is within the time period, the attributes of the time period and the time period of the target table are synchronously updated, and if the time period is outside the time period, the attributes of the time period are only updated; After the whole T period is finished, judging whether the stream ID recorded in the T period in each table item in the main table is consistent with the stream ID recorded in the T period; and if the data are consistent, taking the stream data in the table entry as the burst flow training data of the burst heat prediction model, and if the data are inconsistent, not collecting the stream data.
4. The TCAM rule matching method of claim 2, further comprising, prior to obtaining the first rule heat determined based on the burst heat prediction model and the second rule heat determined based on the steady state heat prediction model: Determining a characteristic space range based on the burst flow training data, and determining a core point position based on a clustering algorithm in the characteristic space range; performing binary cutting on the characteristic dimension corresponding to each burst flow training data based on the core point position to form a plurality of rectangles; Calculating the distance between four vertexes of the rectangle and each core point based on the nearest neighbor criterion, and classifying the four vertexes of the rectangle based on the distance, wherein if the four vertexes of the rectangle are different, the category of the current rectangle is undetermined, and the next round of cutting is waited; And when the iteration number threshold is reached or all rectangular areas are determined to be classified, stopping iteration, and determining the burst heat prediction model according to the classification result.
5. The TCAM rule matching method of claim 2, further comprising, prior to obtaining the first rule heat determined based on the burst heat prediction model and the second rule heat determined based on the steady state heat prediction model: Based on the rules and Gong Re coefficients of all currently known historical moments, determining a kernel function of the inherent heat value at the current moment by using the kernel function; determining an exponential function of the intrinsic heat value at the current moment based on the function of the intrinsic heat value at the current moment; And determining the relation between the intrinsic heat value at the current time and the intrinsic heat value at the last time based on the exponential function of the intrinsic heat value at the current time, and determining the steady-state heat prediction model based on the relation between the intrinsic heat value at the current time and the intrinsic heat value at the last time.
6. The TCAM rule matching method of claim 2, in which performing edge truncation processing on a rule graph based on the first rule hotness and the second rule hotness using a partitionable dependency graph driven based on hotness to obtain a target dependency graph, includes: Performing edge truncation processing on edges corresponding to rules of the parent rule belonging to the second-level TCAM in the current rule diagram to obtain a first processing rule diagram; Determining the heat corresponding to each rule based on the first rule heat and the second rule heat, and determining a low heat rule along the father rule direction of each high-hot point rule, wherein the high heat rule is a rule except the low heat rule; Performing edge truncation processing on edges between the high-hot-point rule and the low-heat father rule, stopping depth transformation in the current father rule direction, and continuing depth traversal from other directions until all low-heat rules in the first processing rule diagram are eliminated, so as to obtain a second processing rule diagram; and if the rule with the depth exceeding 2 exists in the second processing rule graph, performing edge cutting operation on the edge corresponding to the rule exceeding 2 to obtain the target dependency subgraph.
7. The TCAM rule matching method of claim 1, further comprising, before matching and searching data packets in the primary TCAM and the secondary TCAM in order to determine whether to find a corresponding target rule: Updating a counter and a time stamp according to the flow header characteristics when the flow arrives, the counter being used to determine the type of the current flow; if the type of the current flow is burst flow, determining heat based on the burst flow, and updating rules in the double-layer TCAM according to the heat; And when the time stamp exceeds a set time threshold, performing timeout operation on the current flow.
8. A TCAM rule matching apparatus, comprising: The double-layer TCAM acquisition module is used for acquiring a double-layer TCAM constructed based on a rule heat value, wherein the double-layer TCAM comprises a first-level TCAM for storing a first priority rule and a second-level TCAM for storing a second priority rule, the priority of the first priority rule is higher than that of the second priority rule, and no dependency exists between the rules in the first-level TCAM and between the rules in the second-level TCAM; The rule searching module is used for carrying out matching searching on the data packet in the first-level TCAM and the second-level TCAM in sequence and determining whether a corresponding target rule is searched or not; the first matching module is used for executing actions corresponding to the target rules on the data packet if the corresponding target rules are matched in any level of TCAM; And the second matching module is used for matching the target rule in the RAM according to the total rule table in the RAM if the corresponding target rule is not matched in the double-layer TCAM, and executing the action corresponding to the target rule in the RAM on the data packet.
9. A TCAM rule matching device, comprising: A memory for storing a computer program; a processor for executing the computer program to implement the steps of the TCAM rule matching method of any one of claims 1 to 7.
10. A readable storage medium, characterized in that the readable storage medium has stored thereon a computer program which, when executed by a processor, implements the steps of the TCAM rule matching method of any of claims 1 to 7.

Description

TCAM rule matching method, device, equipment and readable storage medium Technical Field The present invention relates to the field of communications technologies, and in particular, to a TCAM rule matching method, apparatus, device, and readable storage medium. Background Currently, TCAM (Ternary Content Addressable Memory ) is used to store "hot rules", while "cold rules" are stored in RAM (memory) with larger capacity but slower speed, and under this hybrid cache frame, TCAM cache hits are not searched in RAM again after matching. This results in the Fwd (2) (rule-corresponding action) acting as the Fwd (2) (cold rule stored in RAM) that would have been the result of the error in forwarding Fwd (1) in accordance with r1 (hot rule stored in TCAM) for packet P (1000, 0000) being forwarded. In order to keep semantics correct, it is currently required that when caching a popular rule, all high priority rules on its dependency chain must be cached at the same time, and when caching a popular rule, its immediate dependency rule must be cached at the same time, and the action of the immediate dependency rule is modified to point to the RAM software look-up table method. Therefore, a large number of rules which are not hot spots are forcedly loaded into the TCAM, valuable storage space is occupied, and the cache rate of the effective hot spot rules is reduced. Therefore, how to increase the cache rate of the heat rule is a technical problem that needs to be solved by those skilled in the art. Disclosure of Invention Accordingly, the present invention is directed to a TCAM rule matching method, apparatus, device, and computer readable storage medium, which solve the technical problem of low cache rate of hot rules in the prior art. In order to solve the technical problems, the invention provides a TCAM rule matching method, which comprises the following steps: The method comprises the steps of obtaining a double-layer TCAM constructed based on a heat value of a rule, wherein the double-layer TCAM comprises a first-level TCAM storing a first priority rule and a second-level TCAM storing a second priority rule, the priority of the first priority rule is higher than that of the second priority rule, and no dependency exists between the rules in the first-level TCAM and between the rules in the second-level TCAM; Carrying out matching search on the data packet in the first-level TCAM and the second-level TCAM in sequence, and determining whether a corresponding target rule is found; If the corresponding target rule is matched in any level of TCAM, executing the action corresponding to the target rule on the data packet; And if the double-layer TCAM is not matched with the corresponding target rule, matching the target rule with a full rule table in the RAM, and executing the action corresponding to the target rule in the RAM on the data packet. Optionally, before obtaining the dual-layer TCAM constructed based on the rule-based hotness value, the method further includes: The method comprises the steps of obtaining a first rule heat determined based on a sudden heat prediction model and a second rule heat determined based on a steady-state heat prediction model, wherein the sudden heat prediction model is a heat prediction model determined by a ternary matching rule obtained by processing sudden flow training data by using a density-based clustering algorithm; performing edge truncation processing on the rule graph by utilizing a partitionable dependency graph based on heat driving based on the first rule heat and the second rule heat to obtain a target dependency sub-graph, wherein the edge truncation processing comprises edge truncation processing on edges of a parent rule belonging to a secondary TCAM, edge truncation processing on edges corresponding to a low-heat rule, and edge truncation processing on rules with depth exceeding 2, and the low-heat rule is a rule with heat lower than a set value; And determining the double-layer TCAM based on the relation of the rules in the target dependency subgraph. Optionally, before acquiring the first regular heat determined based on the burst heat prediction model and the second regular heat determined based on the steady-state heat prediction model, the method further includes: Determining a target table, wherein the target table comprises a main table and a sub-table, hash functions corresponding to the main table and the sub-table are different, the main table is divided into a T period and a T period according to a time period, the value of T is smaller than T, the attribute of the T period comprises a stream ID recorded in the T period and a corresponding characteristic, and the attribute of the T period comprises the stream ID recorded in the T period, the number of data packets arrived by the stream and a time interval parameter between current arrival and last arrival; Determining whether a timestamp in a currently arrived packet is within a t period; If the time p