[發明專利]線速軟多元組報文分類方法

有效

• 申請號: 201410798193.X
• 申請日: 2014-12-19
• 公開（公告）號: CN104468344A
• 公開（公告）日: 2015-03-25
• 發明（設計）人: 黃騰;陳曙暉;趙國鴻;王寶生
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L12/70
• 分類號: H04L12/70
• 代理公司: 湖南兆弘專利事務所 43008
• 代理人: 周長清

技術領域

本發明主要涉及到網絡技術中報文轉發領域，特指一種線速軟多元組報文分類方法。

背景技術

數據包分類(Packet?Classification)是實現報文轉發的一項關鍵步驟，也是完成報文轉發的關鍵技術。數據包分類可描述為：針對IP數據包頭內的五元組信息(源目IP，源目端口，協議號)，找出匹配該數據包頭的最佳規則。其中，每一條規則由五段范圍組成(源目IP，源目端口，協議號)，源目IP以前綴形式表示，源目端口以區間形式表示，協議號一般為精確值。這里“最佳規則”是指所有匹配規則中掩碼最精確，區間最短的規則。

目前，大部分高端路由器的數據包分類算法都由TCAM實現。TCAM采用了線性查找的方式逐條判斷每一條規則是否匹配，并通過并行化、流水線等硬件技術獲得了接近一次訪存的查找效率。TCAM有著很高的能耗和價格，而且規則數不能太大(當前主流的TCAM容量一般為512K條規則)。此外，一些網絡設備在設計時沒有提供TCAM硬件，進一步限制了該算法的應用場景。

另外，相應的軟件分類方法也有很多，大概可分為基于叉乘(Cross?Producting)、組空間(Tuple?Space)、決策樹(Decision?Tree)的三種。基于叉乘的方法(如RFC)有著極高的內存開銷，基于組空間的方法(Tuple?Space?Search)只適用于掩碼種類不大的規則集，基于決策樹的方法(如EGT-PC)則有著很慢的規則更新速度。

發明內容

本發明要解決的技術問題就在于：針對現有技術存在的技術問題，本發明提供一種查找速度快、硬件開銷小、能耗低的線速軟多元組報文分類方法。

為解決上述技術問題，本發明采用以下技術方案：

一種線速軟多元組報文分類方法，其步驟為：

(1)將規則中的端口字段轉換為對應的前綴閉包，得到一個不連續掩碼前綴集；首先將端口字段轉為對應的前綴閉包，即形成一個覆蓋其區間且可以表示為前綴形式的最短的區間；然后將五維前綴集的各個維度連接起來，得到一個不連續掩碼的前綴集；

(2)通過上述不連續掩碼前綴集構造CMT數據結構；

(3)使用CMT結構查找算法實現高速報文分類。

作為本發明的進一步改進：所述步驟(2)的具體步驟為：

(2.a)將整個前綴集作為CMT結構的根節點；

(2.b)使用根節點的公共掩碼修剪前綴集中的每一項，如果修剪后的前綴集和之前不一致，該前綴將被移入該項的子節點中；

(2.c)對節點中的所有項進行排序，使前綴相同的項位于相鄰的位置；

(2.d)合并前綴相同的項，將這些項的子節點合并成一個大的子節點，并更新該子節點的公共掩碼。

作為本發明的進一步改進：所述步驟(2)還包括：步驟(2.e)：若子節點出現沖突，即子節點掩碼與父節點相等，則進行分表操作，否則對所有新生成的子節點遞歸的執行組織算法。

作為本發明的進一步改進：在進行分表算法時，將整個節點分為多個次級節點；即：針對節點N，取一個表項集合X，從N中第一項開始，若當前前綴加入X后，X的公共掩碼將與N的父節點掩碼相等，則將該前綴移入一個新的次級節點N’，否則將其加入X中；若之后N’仍處于沖突狀態，則遞歸的對N’進行分表操作。

作為本發明的進一步改進：所述步驟(1)的具體步驟為：

(1.1)將端口范圍轉化為二進制表示；

(1.2)對于上下界的二進制表示，從最高位開始，如果上界和下界相等，則前綴閉包在該位上取相應的值，否則之后無論上下界是否相等都取*。

作為本發明的進一步改進：所述步驟(3)的具體步驟為：搜索時，首先在CMT的根節點中根據第一次劃分的公共掩碼對五元組數據進行修剪，找到根節點中隊應的等價類；之后，使用該子節點的公共掩碼遞歸的對五元組數據進行后續的查找，直到不存在額外的子節點為止。

作為本發明的進一步改進：還包括步驟(4)：更新步驟，使用CMT插入、刪除和重構方法實現規則集更新操作。

作為本發明的進一步改進：所述插入操作是根據CMT的結構將新規則置入相應的節點中，若新規則不適應CMT已有的結構，則在其最后一次可置入的節點中新加一個線性表，將規則置于其中，并在每次查找到該節點時檢查這個線性表；在新規則數達到一定規模的時候可對CMT進行重構操作，即將每一個存在線性表的節點中的所有規則提出，將這些規則重新組織為一個新的節點，并替換原來的節點。