[發明專利]一種基于多層迭代的改進遞歸數據流匹配方法

在審

• 申請號: 201710773342.0
• 申請日: 2017-08-31
• 公開（公告）號: CN107577756A
• 公開（公告）日: 2018-01-12
• 發明（設計）人: 程實;王則林;文萬志;張曉峰;江寧
• 申請（專利權）人: 南通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06K9/62
• 代理公司: 南京經緯專利商標代理有限公司32200
• 代理人: 朱小兵

1.一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：具體包含如下步驟；

步驟1，將規則庫分割成幾個規則子集；

步驟2，將每個規則子集中的規則存儲在一個RFC數據結構中，每個規則子集用一個索引規則來進行描述，將所有的索引規則存儲在一個RFC索引中，將RFC索引指向相應的RFC數據結構。

2.根據權利要求1所述的一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：通過決策樹將規則庫分割成幾個規則子集。

3.根據權利要求2所述的一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：所述決策樹的生成方法具體如下：

首先生成一棵平衡二叉樹，每個內部節點的關聯規則被分為兩個子集，在構造決策樹的過程，刪除任何重復規則，所有從第一個決策樹刪除的規則都被存儲在第二個決策樹；然后基于上述過程構造第二個決策樹，在第二個決策樹構造過程中的任何重復規則被搬到第三個決策樹，如此迭代，生成所有決策樹。

4.根據權利要求3所述的一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：所述步驟1將規則庫分割成幾個規則子集的具體過程如下：

步驟1.1，定義一個閾值去限制存儲在一個RFC數據結構中的規則的數量，將所有規則都與第一個決策樹的根節點相關聯；

步驟1.2，若規則的數量大于閾值，則把規則分為兩個子集；

步驟1.3，選擇一個有效區分RFC數據結構中的規則的字段，計算規則庫每個字段不同的前綴的數量，選擇前綴數量最多的字段來分割，對選定的字段，進一步確定將規則平衡劃分成兩個部分的一個點，針對選擇的字段，統計小于等于選擇點的端點規則數量，對每個端點分別統計大于選擇點的起始點的規則數量，和選擇點相比，數字最接近被選中；根據選擇的點將規則集劃分為三個子集：規則的范圍低于所選點，規則的范圍高于所選點和范圍在選定的點的未分類的規則；

步驟1.5，重復步驟1.3，把前兩個規則集進一步劃分，直到每個子集生成的規則數量小于閾值，決策樹中所有未分類的規則插入到下一個決策樹的根節點進行進一步的劃分。

5.根據權利要求3所述的一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：在步驟1中，設計一個閾值，當某個子集的規則數小于這個閾值時，就把它和別的子集合并。

6.根據權利要求3所述的一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：在步驟1中，將不同RFC數據結構，且相同快的索引數組進行合并，進而獲取RFC數據結構相同快的eqIDs。

7.根據權利要求6所述的一種基于多層迭代的改進遞歸數據流匹配方法，其特征在于：在步驟1中，用二進制搜索數組替換索引數組，對于每個索引數組，存儲在相鄰實體中的eqIDs是相同的，將它們合并為一個區間，從第一個實體到最后一個實體eqID相同。