[發明專利]一種基于自定義多級流表快速匹配方法

有效

• 申請號: 201310726035.9
• 申請日: 2013-12-25
• 公開（公告）號: CN103731354B
• 公開（公告）日: 2018-01-26
• 發明（設計）人: 潘恒;溫曙光;關洪濤;謝高崗
• 申請（專利權）人: 江蘇省未來網絡創新研究院
• 主分類號: H04L12/743
• 分類號: H04L12/743
• 代理公司: 南京蘇創專利代理事務所(普通合伙)32273
• 代理人: 王華

技術領域

本發明涉及一種基于自定義多級流表快速匹配方法。

背景技術

無論是firewall還是OpenFlow，在這種多表自定義查找中，多級流表流水線的概念已經被引入。一條完整的規則很可能被拆分多個部分，并以流表項的形式分別下發給不同的流表。而這些流表項之間需要通過一個標記連相互進行相互關聯。這個標記在不同的自定義的多級流表中可能稱謂不同，但其功能是相同的。在本發明中稱其為metadata。然而，這些自定義多級流表具有很強的靈活性，每個流表的匹配域類型和流表項數目都是可以根據需要進行自定義的。因此，現階段這些自定義多級流表匹配算法都是線性查找，即逐項進行匹配，其效率是比較低下，很難滿足當今網絡的需求。

發明內容

發明目的：本發明的目的是針對現有技術的不足而提供一種基于自定義多級流表快速匹配方法，有效減少數據包在整個匹配過程中對流表項的匹配次數。

技術方案：為了實現發明的目的，本發明公開了一種基于自定義多級流表快速匹配方法，包括以下步驟：

（1）將一個流表根據若干類型進行分類得到若干個不同的等價類集合，再將這些等價類集合根據其他類型分類得到若干的小等價類集合；

（2）將步驟（1）中的等價類按層次進行hash映射；

（3）數據包進行流表匹配時，通過鍵值查找到其所對應的等價類集合。

作為優選，為了進一步保證匹配效率并使得等價類的劃分更加簡單且具有效率，本發明步驟（1）中的若干類型為三類，第一類為數據包進入端口，第二類為metadata，第三類則為數據包的匹配域。

作為優選，為了在數據包進入等價類之后的查找效率更高，本發明的同一個等價類集合中的流表項按照優先級來排列。

作為優選，為了進一步提升查找匹配效率，本發明的步驟（3）包括以下步驟：

（3.1）數據包根據其metadata值通過所對應的hash函數來計算出其所對應的等價類集合的地址；

（3.2）通過數據包進入端口值查找到其步驟（3.1）中等價類集合所對應的小等價類集合，從而得到其匹配結果。

有益效果：本發明與現有技術相比：減少數據包在每個流表中流表項的匹配次數并且保證整個數據包查找結果的正確性。

附圖說明

圖1為等價類的劃分圖；

圖2為ingress port的hash函數映射圖；

圖3為本發明基于于自定義多級流表快速匹配方法的流程圖。

具體實施方式

下面結合附圖對本發明作更進一步的說明。

如圖1所示，根據metadata值將流表劃分成三個第一級等價類集合；再將第一個第一級等價類集合根據數據包進入端口劃分為兩個第二級等價類集合，其他第一級等價類集合按此原理劃分；第二級等價類集合根據流表項的優先級進行值排列。

如圖2所示，將等價類集合按層次進行hash映射，并且同一個等價類集合中的流表項按照優先級來排列，根據hash映射的鍵值查就能找到其所對應的等價類集合。

如圖3所示，整個匹配的過程為根據數據包的metadata匹配域值查找到相應的第一級等價類集合，再根據數據包進入端口值查找到所對應的第二級等價類集合，最后在該第二級等價類集合進行查找匹配；查找匹配完成，判斷是否跳轉至下一個流表，若跳轉則進入下一個循環，否則結束查找匹配。

根據以上的查找匹配方法減少了在整個流表匹配過程中流表項的匹配次數，加快整個自定義多級流表的查找速度。