[發明專利]一種多域網包分類方法

有效

• 申請號: 201110425385.2
• 申請日: 2011-12-16
• 公開（公告）號: CN102420831A
• 公開（公告）日: 2012-04-18
• 發明（設計）人: 王翔;亓亞烜;李軍
• 申請（專利權）人: 清華大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L12/56
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩

1.一種多域網包分類方法，其特征在于，包括步驟：

A：根據分類規則生成網包分類的查找數據結構的中間結果；在所述查找數據結構的中間結果中，內部節點采用位圖壓縮存儲其所對應的子節點的索引信息；

B：對所述查找數據結構的中間結果進行歸一化壓縮，生成網包分類的查找數據結構的最終結果；

C：根據所述查找數據結構的最終結果，進行多域網包分類處理。

2.如權利要求1所述的方法，其特征在于，所述步驟A具體包括步驟：

A1：定義分類規則全集R0，對應所述分類規則全集R0的全空間S0和根節點N0，并且將所述分類規則全集R0、全空間S0和根節點N0作為三元組放入待處理隊列；

A2：從所述待處理隊列中取出當前第一個三元組，所述當前第一個三元組包括：當前分類規則集合R、當前待切分空間S和當前節點N；

A3：判斷當前分類規則集合R中的每個分類規則對應的空間是否均包含當前待切分空間S，如果是，執行步驟A8；否則，執行步驟A4；

A4：判定當前節點N為內部節點，在當前切分維度上將當前待切分空間S均勻切分為預定值個子空間，將當前分類規則集合R對應切分為所述預定值個規則子集合；

A5：判斷所述預定值個子空間中是否存在滿足以下條件的兩個或者多個子空間：所述兩個或者多個子空間對應的規則子集合中的分類規則相同，并且每個子空間對應的規則子集合中的各個分類規則在當前切分維度上的投影相同；如果是，合并所述兩個或者多個子空間為一個子空間，合并所述兩個或者多個子空間對應的規則子集合為一個規則子集合，執行步驟A6；否則，直接執行步驟A6；

A6：依次生成對應最終得到的各子空間的子節點作為所述當前節點N的子節點，將最終得到各規則子集合、對應所述規則子集合的子空間和子節點組成的新的三元組依次放入所述待處理隊列中；

A7：記錄當前節點N的切分維度為當前切分維度，記錄當前節點N的第一個子節點的地址，采用位圖數組和偏移信息數組壓縮存儲當前節點N的其他子節點相對所述第一子節點的地址偏移信息，執行步驟A2；

A8：判定當前節點N為葉節點，記錄當前節點N的切分維度為保留值，記錄對應當前節點N的分類規則為當前分類規則集合R中的分類規則，根據當前節點N的分類規則記錄對應當前節點N的操作信息，執行步驟A9；

A9：判斷所述待處理隊列是否為空，如果是，將最終得到的樹形結構作為查找數據結構的中間結果，執行步驟B，否則執行步驟A2。

3.如權利要求2所述的方法，其特征在于，所述當前切分維度滿足：按照當前切分維度對當前待切分空間S切分后，得到的所有子空間對應的規則子集合中的所有分類規則重復出現的次數最少。

4.如權利要求2所述的方法，其特征在于，所述預定值為256。

5.如權利要求2所述的方法，其特征在于，所述步驟B具體包括步驟：

B1：將所有所述內部節點的位圖數組作為位圖集合中的元素，將所有所述內部節點的偏移信息數組作為偏移信息集合中的元素，將所述偏移信息數組中非最長元素補齊至最長；

B2：刪除所述位圖集合中的重復元素，對所述位圖集合中的剩余元素進行排序；刪除所述偏移信息集合中的重復元素，對所述偏移信息集合中的剩余元素進行排序；

B3：按照廣度優先方式遍歷查找數據結構的中間結果對應的樹形結構，按照遍歷順序在最終結果數組中記錄每個內部節點的切分維度、每個內部節點對應的位圖數組在所述位圖集合中的序號、每個內部節點對應的偏移信息數組在所述偏移信息集合中的序號、每個內部節點的第一子節點在所述最終結果數組中的序號，記錄每個葉節點對應的切分維度、分類規則和操作信息，將所述最終結果數組、位圖集合和偏移信息集合作為生成網包分類的查找數據結構的最終結果。

6.如權利要求5所述的方法，其特征在于，所述步驟C具體包括步驟：

C1：令所述最終結果數組中的第一個節點為當前參考節點；

C2：判斷當前參考節點對應的切分維度是否為保留值，如果是，返回當前參考節點對應的分類規則和操作信息，分類結束；否則，執行步驟C3；

C3：選擇待分類網包在與當前參考節點對應的切分維度相同的維度上的取值，確定所述取值對應的當前參考節點的子節點序號i；

C4：計算當前參考節點對應的位圖數組中前i個位之和s，查找當前參考節點對應的偏移信息數組中序號s對應的值O_s，將當前參考節點的第一子節點在所述最終結果數組中的序號b與O_s做和，得到下一跳節點的地址；

C5：根據下一跳節點的地址找到下一跳節點，將下一跳節點作為當前參考節點，執行步驟C2。