[發明專利]多域流表的多級化方法及裝置、多級流表查找方法及裝置

有效

• 申請號: 201610935403.4
• 申請日: 2016-11-01
• 公開（公告）號: CN108011823B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 牛小兵;李險峰;林源鑫;柯楚
• 申請（專利權）人: 中興通訊股份有限公司;北京大學深圳研究生院
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/743;H04L12/721
• 代理公司: 上海晨皓知識產權代理事務所(普通合伙) 31260
• 代理人: 成麗杰

本發明公開了一種多域流表的多級化方法及裝置、多級流表的查找方法及裝置，其中，多域流表的多級流表的轉化所述方法包括：根據確定的參數α和所述多域流表的屬性信息生成第1級至第m級流表；根據所述多域流表，分別確定所述第1級至第m級流表中的第一匹配規則表，其中，所述第一匹配規則表為每一級流表中匹配域值在所述多域流表中出現次數為1的匹配域值信息的集合；根據所述多域流表，分別確定所述第1級至第m級流表中的第二匹配規則表，其中，所述第二匹配規則表為每一級流表中匹配域值在所述多域流表中出現次數大于1的匹配域值信息的集合；將所述第一匹配規則表和所述第二匹配規則表分別存儲到第1級至第m級流表中。

技術領域

本發明涉及軟件定義網絡(Software Defined Network，SDN)交換機的轉發技術領域，尤其涉及一種多域流表的多級化方法及裝置、多級流表查找方法及裝置。

背景技術

SDN流分類轉發是網絡設備中的基本功能。其實質是根據流表中預定義的分類規則集，為到達的網絡數據包找到所匹配的規則，其中分類規則集是一個包含一系列規則的集合，每條規則由多個與數據包頭中某些域相對應的匹配條件構成，并為每條規則指定相應的處理方法(Action)，從而根據所得到的不同匹配結果對數據包進行不同的處理，如丟棄或者轉發。

在OpenFlow1.0版本中，采用的是單流表設計，一律采用具有最大長度的流表項記錄代替，會使得流表項尺寸增大。其次，控制器程序員也難以寫出合理的控制程序來控制如此龐大的單流表，而采用多級流表結構可以獨立處理，極大簡化了問題。目前OpenFlow中已經定義41個關鍵字，對分類轉發提出了更高的要求，這就使得一個大的流表不能滿足查找時間的要求。

在OpenFlowv1.1設計了多級流表來減少流表的開銷，將匹配過程分解成多個步驟，形成流水線的處理形式，從而降低總的流表記錄條數。而對于多級流表每個步驟的匹配結果，采用傳統的交叉乘積方式，則需要維護一個龐大的表和做大量的交叉乘積，極大的影響了算法的空間復雜度，不能夠適應到OpenFlow1.4提出的41個域甚至是SDN協議無關轉發的更多的N個域中。

現有適合多級流表的方法如下：根據每一級流表的字段匹配類型，對需要精確匹配類型的字段采取基于靜態隨機存取存儲器(Static Random Access Memory，SRAM)存儲的哈希表算法，對需要前綴匹配的字段則采取基于三態內容尋址存儲器(Ternary ContentAddressable Memory，TCAM)的硬件并行匹配。

現有適合多級流表的方法存在的問題是：對于流表的特征提取較為粗糙，并且該方案對資源要求很高，需要一個巨大存儲容量的芯片才能正常工作，不太適合現實應用。如果采用傳統的交叉乘積聚合方式則需要維護一個龐大的表和做大量的交叉乘積，極大的影響了算法的空間復雜度，不能夠適應到OpenFlow1.4提出的41個域甚至是SDN協議無關轉發的更多的N個域中。

目前，多級流表相對于單流表在理論性能上頗具優勢。但多級流表技術在實際應用還有大量技術問題亟需解決，比如各級流表如何排序、各級流表的劃分方法，成為當下多級流表技術需要解決的重要問題。

發明內容

為解決現有存在的技術問題，本發明實施例提供一種多域流表的多級化方法及裝置、多級流表的查找方法及裝置，能夠有效降低傳統的交叉乘積表的規模，并且提高了存儲效率。

為達到上述目的，本發明實施例的技術方案是這樣實現的：

第一方面，本發明實施例提供一種多域流表的多級流表的轉化方法，所述方法包括：

根據確定的參數α和所述多域流表的屬性信息生成第1級至第m級流表，其中，m為大于1小于等于N的自然數，第1級至第m級流表中至少包括一個匹配域值，所述多域流表包括至少一條規則以及與所述至少一條規則對應的轉發動作，所述規則包括N個匹配域的匹配域值，N為大于1的自然數，每個匹配域包括至少一個匹配域值；