[發明專利]一種流分類方法及裝置

有效

• 申請號: 201910294640.0
• 申請日: 2019-04-12
• 公開（公告）號: CN111817978B
• 公開（公告）日: 2022-10-04
• 發明（設計）人: 胡晶;田書貞;張正義
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L47/2441
• 分類號: H04L47/2441
• 代理公司: 北京龍雙利達知識產權代理有限公司 11329
• 代理人: 時林;毛威

本申請提供了一種流分類方法和裝置，該方法包括：根據第一規則集中多條規則的關心位的分布特征確定與第一規則集對應的有效位，所述有效位包括用于區分所述多條規則中不同規則的數值所在的比特位；根據第一規則集中各條規則的有效位的數值確定各條規則的哈希鍵值，根據哈希鍵值將所述第一規則集中各條規則存儲于S個存儲單元中的至少一個存儲單元內，其中，第一規則集是N個規則集中的任意一個，該N個規則集存儲于該S個存儲單元內，N、S為大于或者等于1的整數，該S個存儲單元中的每個存儲單元存儲的規則的有效位相同；當進行流分類時，根據查找關鍵字的哈希鍵值在所述S個存儲單元中的每個存儲單元內查找對應的規則。

技術領域

本申請涉及計算機技術，尤其涉及一種流分類方法及裝置。

背景技術

當前網絡中流分類功能已經是路由器和交換機中的關鍵功能之一，給網絡提供包過濾、服務質量(quality of service,QoS)、流量統計等功能特征。流分類的原理是提取報文頭中各個域段的信息構造查找關鍵字，然后根據每條規則相應的設置信息進行匹配。若滿足規則的設置就執行規則相關聯的動作。配置的每一個規則都會關聯一個優先級信息，若有多個規則都能匹配的話就執行優先級最高的規則的動作。

目前廣泛使用的流分類解決方案有基于三態內容可尋址存儲器(ternarycontent addressable memory，TCAM)的硬件方案和基于決策樹算法的規則集切分方案。對規則集進行切分的決策樹算法的基本思想是根據規則集的特征，將規則集進行遞歸切分，直到每個子規則集中規則個數小于某個事先設定好的閾值為止。目標是流查找的時候只需要對某一個規則子集進行匹配即可，這樣可以極大的減少需要匹配的規則個數，從而達到高速的流查找功能?；跊Q策樹的預處理算法在當前得到廣泛應用，經典的算法有HiCuts、HyperCuts或者Modular等。

目前，由于哈希(hash)算法具有極高的插入和查找性能，也有相關研究將哈希算法作為流分類查找算法。目前的基于哈希算法的流分類方法在規則的插入以及查找時需要的計算資源較大，規則的插入以及查找效率低下。

發明內容

本申請提供一種流分類方法及裝置，具有高查找性能、低資源消耗、低查找時延的特性。

第一方面，提供了一種流分類方法，該方法可以由網絡設備執行，或者，也可以由配置于網絡設備中的芯片或電路執行，本申請對此不作限定。例如，該網絡設備可以是路由器或者交換機等，不做限定。

該方法包括：根據第一規則集中多條規則的關心位的分布特征確定與第一規則集對應的有效位，該有效位包括用于區分多條規則中不同規則的數值所在的比特位；根據第一規則集中各條規則的有效位的數值確定各條規則的哈希鍵值，根據哈希鍵值將第一規則集中各條規則存儲于S個存儲單元中的至少一個存儲單元內，其中，第一規則集是N個規則集中的任意一個，N個規則集存儲于該S個存儲單元內，N、S為大于或者等于1的整數，該S個存儲單元中的每個存儲單元存儲的規則的有效位相同；當進行流分類時，根據查找關鍵字的哈希鍵值在該S個存儲單元中的每個存儲單元內查找對應的規則。

具體地，該有效位包括用于區分多條規則中不同規則的數值所在的比特位。確定第一規則集對應的有效位可以理解為確定第一規則集中包含的多條規則所對應的共同的有效位?；蛘咭部梢岳斫鉃椋_定第一規則集中每一條規則的有效位，各條規則的有效位是相同的。每條規則通常包括多個比特位，規則的有效位可以是指在下一步的哈希存儲運算中所“有效”的比特位，是參與下一步哈希存儲運算的比特位，根據規則的有效位的數值來進行哈希存儲運算，而規則的有效位之外的比特位的數值則不參與下一步的哈希存儲運算。