報文分類方法和裝置與流程
2023-06-11 10:14:56 1
本發明涉及通信領域，尤其涉及一種報文分類方法和裝置。
背景技術：
：：在路由器、防火牆等網絡設備中，通常根據規則集合的優先級進行報文分類，從而實現對應的業務功能。其中，規則集合包括IP(internetprotocol，網際網路協議)路由表、ACL(accesscontrollist，訪問控制列表)過濾表、Filter(過濾)表等等，它們都由多條規則組成，每條規則通常包含多個不同的域值(也被稱為匹配域)，例如MAC(媒體訪問控制，mediaaccesscontrol)地址、IP位址、埠號、協議號等，每條規則還對應優先級和相應的動作。報文分類，即在上述規則集合中查找所有匹配該報文的規則，並選出優先級最高的一條規則，根據該規則對應的動作，對該報文進行處置，例如轉發、丟棄、修改報文頭部欄位等。目前已有的報文分類算法，主要有Hash(哈希)、Hi-Cuts、TSS(tuplespacesearch，元組空間查找)、TCAM(ternarycontentaddressablememory，三態內容尋址存儲器)、RFC(recursiveflowclassification)等。但是隨著SDN技術的不斷推廣和發展，其中南向接口當中廣泛被採用的OpenFlow(開放流)協議中定義的轉發表，要求報文分類算法在快速報文分類同時，還要支持動態更新。Hash算法特別適用於精確匹配，支持大維度、大容量的報文分類，當規則的所有匹配域都是精確值類型時，Hash算法是最優的選擇。但大部分的報文分類都不是簡單的精確匹配問題，因此適用性不廣。Hi-Cuts算法採用每域切割的方式，構建一個樹形查找結構，一棵樹包含兩種類型的節點組成：葉子節點及內部節點。葉子節點存儲一條規則或者一個最佳匹配規則集合，內部節點不存儲規則而是存儲選擇分支的判斷條件。為了進行報文分類，根據報文的匹配域構建成查找鍵值。在未到達葉子節點之前，將查找鍵值和內部節點的分支判斷條件進行比較以選擇分支。如果葉子節點僅包含一條規則，就認為是最佳匹配規則，但是如果葉子節點存儲了多個規則，還需要進行小規模的線性遍歷。該算法當規則中存在大量全通配的匹配域值時，存在大量規則複製，不僅內存開銷大，而且也會很大程度上降低查找速度，同時由於規則在各個葉子節點上被大量複製，因此不具備動態更新功能，僅能通過重建樹實現規則的增加和刪除。TSS算法，其基本的思想是通過哈希表將分類索引值分成若干個精確匹配的索引值問題，可以應用在具有前綴規則的多維流分類問題上。以IPv4中的分類問題為例，SIP和DIP中都存在許多不同的前綴長度，理論上的前綴長度組合種類為32*32種，每一種前綴長度組合都對應一個元組，每個元組中利用哈希算法進行查找，因此每個元組中的規則查找速度極快。但是由於報文頭部欄位中並不包含表徵前綴長度的信息，因此需要針對每條報文都必須查找所有的元組，因此查詢性能較低。RFC在某種程度上可以認為是改進版的BV算法，通過把本應該在查詢過程中做的按比特位與運算提前到初始化階段，犧牲一定的預處理性能，提升查找速度。該算法查找性能極快，但是預處理速度和存儲開銷較大，同時屬於靜態算法，但需要新增一條規則時，需要重構查找數據結構，耗時無法接受，因此僅能應用於幾乎不更新的場景。目前採用較多的算法還有基於TCAM實現的報文分類算法，較一般軟體算法，TCAM屬於硬體實現，因此其查詢性能極快，但是受限於TCAM容量，同時還具有更新緩慢、功耗極大等缺點。技術實現要素：本發明的實施例提供一種報文分類方法和裝置，用於實現快速報文分類。為達到上述目的，本發明的實施例採用如下技術方案：第一方面，提供了一種報文分類方法，包括：在查找階段，根據報文的匹配域查找得到對應的第一層查找結構的IT表表項，並得到所述對應的第一層查找結構的IT表表項中存儲的ET表表項索引值；根據得到的前一層查找結構的ET表表項索引值計算得到當前層查找結構的IT表表項的索引值，並得到對應的當前層查找結構的IT表表項中存儲的ET表表項索引值，如果當前層查找結構為最後一層查找結構，則根據得到的當前層查找結構的IT表表項中存儲的ET表表項索引值得到當前層查找結構的ET表表項，其中，得到的當前層查找結構的ET表表項中存儲的比特位圖的生效比特位所對應的規則為所述報文所屬類型的目標規則。第二方面，提供了一種報文分類裝置，包括：查找單元，用於根據報文的匹配域查找得到對應的第一層查找結構的IT表表項，並得到所述對應的第一層查找結構的IT表表項中存儲的ET表表項索引值；所述查找單元，還用於根據得到的前一層查找結構的ET表表項索引值計算得到當前層查找結構的IT表表項的索引值，並得到對應的當前層查找結構的IT表表項中存儲的ET表表項索引值，如果當前層查找結構為最後一層查找結構，則根據得到的當前層查找結構的IT表表項中存儲的ET表表項索引值得到當前層查找結構的ET表表項，其中，得到的當前層查找結構的ET表表項中存儲的比特位圖的生效比特位所對應的規則為所述報文所屬類型的目標規則。本發明實施例提供的報文分類方法和裝置，在查找過程中，根據報文的匹配域對應第一層查找結構的IT表表項索引，得到IT表表項中存儲的ET表表項索引，然後逐層根據前一層查找結構的ET表表項索引值計算得到當前層查找結構的IT表表項的索引值，如果當前層查找結構為最後一層查找結構，則可得到該IT表表項中存儲的ET表表項索引值對應的ET表表項，該ET表表項中存儲的比特位圖的生效比特位所對應的規則為目標規則，通過對報文的匹配域按照索引值逐層查找匹配規則，不斷縮小查找範圍，可以實現對報文快速分類。附圖說明為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。圖1為本發明的實施例提供的報文分類方法的流程示意圖；圖2為本發明的實施例提供的查找結構的示意圖；圖3為本發明的實施例提供的分層塊壓縮結構的示意圖；圖4為本發明的實施例提供的根據規則集合中各個規則的匹配域生成第一層查找結構的流程示意圖；圖5為本發明的實施例提供的前一層查找結構中包含偶數個查找結構的示意圖；圖6為本發明的實施例提供的前一層查找結構中包含奇數個查找結構的示意圖；圖7為本發明的實施例提供的根據前一層查找結構的ET表表項的索引和比特位圖生成當前層查找結構的流程示意圖；圖8為本發明的實施例提供的根據前一層查找結構的ET表表項的索引和比特位圖生成當前層查找結構的示意圖；圖9為本發明的實施例提供的確定對第一層查找結構的ET表中比特位圖的更新策略的流程示意圖；圖10為本發明的實施例提供的新增匹配域與已有匹配域屬於第一種情況的示意圖；圖11為本發明的實施例提供的新增匹配域與已有匹配域屬於第二種情況的示意圖；圖12為本發明的實施例提供的新增匹配域與已有匹配域屬於第三種情況的示意圖；圖13為本發明的實施例提供的新增匹配域與已有匹配域屬於第四種情況的示意圖；圖14為本發明的實施例提供的一種對第一層查找結構更新的示意圖；圖15為本發明的實施例提供的一種對非第一層查找結構更新的示意圖；圖16為本發明的實施例提供另一種對非第一層查找結構更新的示意圖；圖17為本發明實施例提供的報文分類裝置的結構示意圖。具體實施方式下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。一個報文分類器C由T條規則組成規則集合R，R＝{Rj|1<＝j<＝T}，T也被稱為報文分類容量，規則是有三個方面的內容組成：1)規則Rj中的每一項Rj[i]，其中1<＝i<＝d，和報文頭中的d個域相對應，其中d也被稱為報文分類問題的維度；2)用一個數Pri(Rj)表達規則在分類器中的優先級；3)一條規則對應一個動作Action(Rj)。對於一個報文P，若且唯若報文頭中的d-tuple(P1,P2,…Pd)和規則Rj當中的Rj[i]一一匹配時(即滿足Rj[i]的限定範圍時)，則稱報文P匹配規則Rj，其中1<＝i<＝d；Rj[i]的具體形式有精確匹配、範圍、前綴(最長匹配，包含全通配)、非域匹配等，每一個Rj[i]稱為匹配域。最後從報文P所匹配的所有規則集合中，找到具有最高優先級的規則Rj，既命中規則Rj。本發明實施例提供的報文分類方法，分為初始化階段、查找階段和更新階段，參照圖1中所示，包括：S101、在初始化階段，根據規則集合中各個規則的匹配域生成第一層查找結構(lookupstructure，LS)。示例性的，假設規則集合中包含一條規則：[SP：(0,1024)DP：(18,18)優先級：x動作：Y]，其中，SP(sourceport，源埠)對應一個匹配域，該SP匹配域的取值範圍是[0,1024]；DP(destinationport，目的埠)對應另一個匹配域，該DP匹配域的取值範圍是[18,18]。本發明實施例提供的存儲方式按功能分層，其包括至少一層查找結構，每層查找結構包括至少一個查找結構。本發明實施例如無特別說明，提及的第T層查找結構指的是該第T層查找結構的一個查找結構，T≥1。不論位於第幾層查找結構，每個查找結構均包括IT(indextable，索引表)表和ET(extendedbitvectortable，擴展比特向量表)表。示例性的，參照圖2中所示，其中的LS11表示第一層查找結構中的第一個查找結構，類似的LS21表示第二層查找結構中的第一個查找結構。需要說明的是，本發明實施例如無特別說明，IT表對應的ET表或者IT表表項對應的ET表表項等論述均指同一個查找結構中的IT表和ET表。每個匹配域對應第一層查找結構中的至少一個查找結構。具體的，對於某個匹配域來說，根據其不同的位寬具有不同取值範圍，因此需要根據各個匹配域的位寬確定第一查找結構的IT表中的長度。常見的匹配域包括IP(internetprotocol，網際網路協議)地址(佔32bit)、埠號(佔16bit)、協議號(佔8bit)、標識符(佔8bit)等，假設以16bit為基準寬度確定一個查找結構的IT表長度，則每個第一層查找結構的IT表的最大表長是216＝65536，即IT表表項的索引可對應於匹配域為0-65535的值。此時，當報文頭部查找欄位大於16bit時，需要對其進行拆分，例如源IP位址的32bit需要拆分成兩個查找結構SIP-LO(sourceIPlow，源IP低字節)和SIP-HI(sourceIPhigh，源IP高字節)；當報文頭部查找欄位寬度小於16bit時，可以選擇組合或者不組合，例如協議號8bit和標識符8bit可以組合成16bit的一個查找結構；或者不組合時分別對應的IT表長分別為28＝256。圖2中示例性的示出了第一個匹配域的位寬為16bit，對應的第一層查找結構LS11的IT表長65536。在第一層查找結構中，IT表表項a的索引a與該匹配域取值為a時相對應，即當匹配域取值為a時，向第一層查找結構的IT表表項a賦值。示例性的，參照圖2中所示，假設LS11表示源埠匹配域對應的第一層查找結構。假設源埠匹配域的取值範圍為0-65535，當該匹配域取值為0時即對應於第一層查找結構的IT表表項0(IT表索引為0)。IT表表項a中存儲第一層查找結構的ET表表項b的索引b，示例性的，參照圖2中所示，假設IT表中表項0中存儲值為1，則對應於ET表中的表項1的索引(ET表索引為1)。ET表表項b中的比特位圖的取值用於標識在所述規則集合中對應位置的規則的匹配域是否包含取值a，其中，a≥0，b≥0。示例性的，參照圖2中所示，假設ET表表項1中的比特位為0011000，從左到右每個比特位對應於規則集合中的一個規則，第一個比特位對應於規則0，第二個比特位對應於規則1，依此類推，當置1時表示包含取值a時，則0011000表示規則集合中的規則2和3的源埠匹配域包含取值0，規則0、1、4、5和6的源埠匹配域不包含取值0，此時生效比特位指置1的比特位。本領域技術人員可以想到，也可以設置當置0時表示包含取值a，此時生效比特位指置0的比特位，本發明實施例僅以當置1時表示包含取值a進行說明。當規則集合容量小時ET表中每個表項的比特位圖可以直接採用長比特串(例如001110101...等)進行存儲，比特位圖長度和規則集合容量一致，第0位代表規則0，第1位代表規則1，如此一一對應，置1時，表示能通過匹配域找到該規則，反之無法找到該規則，具體如圖2中所示。而當規則容量大時如果依然採用長比特串形式，不僅存儲空間開銷大，而且大量的時間要耗費在與運算上，因為通過實驗，發現比特位圖中存在大量連續的值為0的比特位。所以上述比特位圖可以採用分層塊壓縮結構，分層塊壓縮結構的層數和每層比特位圖長度由規則集合的容量決定。分層塊壓縮結構可以包含S層的比特串，其中，第s層比特串的每一位對應於第s+1層的一個比特串，當第s層中一個比特串全為0時，該全為0比特串及對應的s+1層的比特串均不存儲，對於每個比特串的長度不進行限定，0<s<S。示例性的，參照圖3中所示，假設該分層塊壓縮結構可以包含三層，層1的每個比特串長度為64bit，層2的每個比特串長度為128bit，層3的每個比特串長度為128bit，此時，層1中的一個比特位對應層2中的128個位圖結構，同時對應層3中的128*128個比特串，因此該結構最大可支持1M條規則。如圖中虛線部分所示，當層2中的一個比特串128bit都為0時，該比特串以及該比特串在層3中對應的128個比特串均不存儲。採用這樣的分層結構，將極大的壓縮存儲空間，同時由於大量0不參與計算也會減少與運算的次數。具體的，參照圖4中所示，步驟S101包括：S1011、創建臨時比特位圖，其中，臨時比特位圖的存儲形式與ET表的存儲形式相同。臨時比特位圖可以是如上所述的長比特串或者分層塊壓縮結構，只需保證與ET表的存儲形式一致即可。S1012、判斷規則集合中各個規則的匹配域中是否包含取值a，如果包含，則將臨時比特位圖中與該各個規則在規則集合中的位置相對應的比特位置1，否則置0。遍歷規則集合，將每條規則的匹配域轉換成閉包範圍的表示形式，例如假設規則1的源埠匹配域的取值範圍為0-65535，則該匹配域對應的閉包範圍為[0,65535]。從頭開始遍歷第一查找結構中的IT表，針對每一個IT索引值a，遍歷規則集合中的所有規則，判斷每條規則對應的匹配域值是否包含該IT索引值a，如果包含，則在臨時比特位圖中通過置比特位進行標記，如果不包含則不標記。S1013、判斷ET表的各個表項中是否已經存在與臨時比特位圖相同的比特位圖，如果存在，則將對應表項的索引填入IT表表項a中，如果不存在，則將臨時比特位圖存儲至ET表中第一個空閒表項，並將該第一個空閒表項的索引填入IT表表項a中。為了快速確定ET表中是否存在臨時比特位圖，避免遍歷ET表，本發明實施例可以引入哈希算法，計算當前比特位圖的哈希值，使得ET表中包含一個哈希表結構，如果存在哈希值相同，則需要詳細比較比特位圖，如果比較結果都完全一致，則說明ET表中已經存在了該臨時比特位圖。需要說明的是，很多情況下，在將前一層查找結構的兩個ET表做按位與運算，經常會得到全0比特位圖(即不包含任何規則)。因此為了進一步提高初始化速度，本發明實施例中，可以將每個ET表中的第一個表項(ET索引為0)初始化為全0的比特位圖，這樣當要引用全0比特位圖時不必再查找ET表。S102、根據前一層查找結構的ET表表項的索引和比特位圖生成當前層查找結構，直到當前層查找結構中的查找結構數目為1。其中，當前層查找結構的IT表表項k的索引與前一層查找結構的T個ET表表項的索引增加更新裕量後計算得到，這T個ET表表項分別屬於前一層查找結構的T個查找結構之一，當前層查找結構的IT表表項k中存儲當前層查找結構的ET表表項f的索引，當前層查找結構的ET表表項f中的比特位圖為上述T個ET表表項中的比特位圖按位與的結果，k≥0，f≥0，T≥2。T的取值可以為2、3、4，優選的，參照圖5和圖6中所示，T取值為2，相當於前一層查找結構中2個查找結構對應於當前層查找結構中的一個查找結構，其中，圖5中所示為前一層查找結構中包含偶數個查找結構時，圖6中所示為前一層查找結構中包含奇數個查找結構時。具體的，當T＝2時，參照圖7中所示，步驟S102包括：S1021、根據前一層查找結構中第2i-1個查找結構的ET表表項c以及第2i個查找結構的ET表表項d，確定當前層查找結構中第i個查找結構的IT表中的一個表項索引為c*(D+ΔD)+d，其中，i≥1，0≤c≤C+ΔC，0≤d≤D+ΔD，C為前一層查找結構中第2i-1個查找結構的ET表表長，D為前一層查找結構中第2i個查找結構的ET表表長，ΔC≥0，ΔD≥0。當前層查找結構中第i個查找結構的IT表表長為(D+ΔD)*(C+ΔC)。參照圖8中所示，ΔC和ΔD表示更新裕量，當ΔC和ΔD均為0時，所生成的當前層查找結構固化了IT表和ET表，所以不支持更新；當ΔC和ΔD不全為0時，所生成的當前層查找結構預留了IT表和ET表，所以支持更新。S1022、將前一層查找結構中第2i-1個查找結構的ET表表項c的比特位圖以及第2i個查找結構的ET表表項d的比特位圖進行與操作，得到第二臨時比特位圖。S1023、判斷當前層查找結構的ET表的各個表項中是否已經存在與第二臨時比特位圖相同的比特位圖，如果存在，則將對應表項的索引填入當前層查找結構的IT表表項c*(D+ΔD)+d中，如果不存在，則將第二臨時比特位圖存儲至當前層查找結構的ET表中第一個空閒表項，並將該第一個空閒表項的索引填入當前層查找結構的IT表表項c*(D+ΔD)+d中。S103、在查找階段，根據報文的匹配域查找得到對應的第一層查找結構的IT表表項，並得到該對應的第一層查找結構的IT表表項中存儲的ET表表項索引值。示例性的，從報文頭部中取出對應匹配域的欄位信息，比如源IP欄位、目的IP欄位、埠欄位等，當查找結構位寬為16bit時，對於大於16bit的欄位需要按照位寬進行拆分，例如將源IP位址的32bit對應兩個查找結構SIP-LO和SIP-HI。從SIP-LO對應的第一層查找結構中，SIP-LO欄位值作為匹配域，該匹配域對應的第一層查找結構的IT表表項索引值即命中對應的IT表表項，進而得到該對應的IT表表項中存儲的ET表表項索引值。從SIP-HI對應的第一層查找結構中，SIP-HI欄位值作為匹配域，該匹配域對應的第一層查找結構的IT表表項索引值即命中對應的IT表表項，進而得到該對應的IT表表項中存儲的ET表表項索引值。S104、根據得到的前一層查找結構的ET表表項索引值計算得到當前層查找結構的IT表表項的索引值，並得到對應的當前層查找結構的IT表表項中存儲的ET表表項索引值，如果所述當前層查找結構為最後一層查找結構，則根據得到的當前層查找結構的IT表表項中存儲的ET表表項索引值得到當前層查找結構的ET表表項，其中，得到的當前層查找結構的ET表表項中存儲的比特位圖的生效比特位所對應的規則為報文所屬類型的目標規則。具體的，對於除了第一層查找結構以外的其他層，都是根據前一層查找結構的ET表索引值計算得到本層查找結構的IT表表項索引值。具體的，與圖7中所示過程相對應的，根據c*(D+ΔD)+d得到當前層查找結構的IT表表項索引值。噹噹前層查找結構為最後一層查找結構時，根據得到的當前層查找結構的IT表表項中存儲的ET表表項索引值得到當前查找結構的ET表表項，該ET表表項中存儲的比特位圖的生效比特位所對應的規則為目標規則.如果各個規則是按照優先級從高到低排序時，則該比特位圖中第一個非0的比特對應的規則即為命中的規則。S105、在更新階段，根據新增匹配域與已有匹配域具有的公共匹配域的範圍，確定對第一層查找結構的ET表中比特位圖的更新策略。本發明實施例所述的更新指在規則集合中增加規則，假設在當前規則集合中新增一條如下所示的規則：[SP：(1000,2000)DP：(21,21)優先級：x動作：Y]。對於新增加的上述規則，首先需要分別更新與源埠SP和目的埠DP欄位對應的第一層查找結構中的IT表，其中源埠SP匹配域對應的第一層查找結構IT表更新範圍是[1000,2000]，目的埠DP匹配域對應的第一層查找結構IT表更新範圍是[21,21]，IT表更新範圍所引用的ET表表項中的比特位圖的更新比特位相應也進行更新，但是由於ET表表項通常被多個IT表表項所引用，因此不能簡單對ET表表項中的比特位圖中更新比特位進行置1操作，需要判斷是否存在共享。另一方面，當第一層查找結構發生改變時，其他層查找結構也需要更新，因此更新過程實質上是從第一層查找結構開始向後逐步更新的過程。本發明實施例所述的更新比特位是指ET表的比特位圖中與新增規則在規則集合中位置相對應的比特位。對於第一層查找結構，參照圖9中所示，包括：S1051、首先判斷新增匹配域與已有匹配域是否具有公共匹配域及公共匹配域範圍，如果新增匹配域包含已有匹配域(即相當於公共匹配域為已有匹配域)，則跳轉步驟S1052；如果新增匹配域被包含於已有匹配域(即相當於公共匹配域為新增匹配域)，則跳轉步驟S1053；如果新增匹配域與已有匹配域部分重疊，則跳轉步驟S1054；如果新增匹配域與已有匹配域不具有公共匹配域，則跳轉步驟S1055。示例性的，假設未更新前規則集合中僅有一條規則，該規則為：[SP：(0,1024)DP：(18,18)優先級：x動作：Y]。從中可以看出，該規則對應兩個匹配域：源埠SP匹配域和目的埠DP匹配域，該規則對應於源埠SP匹配域為[0,1024]，對應於目的埠DP匹配域為[18,18]，該規則在規則集合中的位置為1。為便於描述，僅針對源埠SP匹配域進行說明。第一種情況：假設新增規則為：[SP：(0,1500)DP：(18,18)優先級：x動作：Y]，對於源埠SP匹配域來說新增匹配域為[0,1500]，該新增匹配域[0,1500]與已有匹配域[0,1024]具有公共匹配域[0,1024]，屬於新增匹配域包含已有匹配域的情況，因此跳轉步驟S1052。第二種情況：假設新增規則為：[SP：(100,1000)DP：(18,18)優先級：x動作：Y]，對於源埠SP匹配域來說新增匹配域為[100,1000]，該新增匹配域[100,1000]與已有匹配域[0,1024]具有公共匹配域[100,1000]，屬於新增匹配域被包含於已有匹配域的情況，因此跳轉步驟S1053。第三種情況：假設新增規則為：[SP：(1000,2000)DP：(18,18)優先級：x動作：Y]，對於源埠SP匹配域來說新增匹配域為[1000,2000]，該新增匹配域[1000,2000]與已有匹配域[0,1024]具有公共匹配域[1000,1024]，屬於新增匹配域與已有匹配域部分重疊的情況，因此跳轉步驟S1054。第四種情況：假設新增規則為：[SP：(2000,3500)DP：(18,18)優先級：x動作：Y]，對於源埠SP匹配域來說新增匹配域為[2000,3500]，該新增匹配域[2000,3500]與已有匹配域[0,1024]不具有公共匹配域，因此跳轉步驟S1055。S1052、將公共匹配域對應的IT表表項所引用的ET表表項中的比特位圖的更新比特位置1，新建全0臨時比特位圖，將臨時比特位圖的更新比特位置1，並將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將該第一個空閒表項的索引填入第一層查找結構的IT表的非公共匹配域對應的表項中，非公共匹配域為新增匹配域減去已有匹配域後剩餘的匹配域。參照圖10中所示，針對第一種情況，將公共匹配域[0,1024]對應的IT表表項所引用ET表表項1的比特位圖中的第2比特位置1(即從1000000變成為1100000)，將全0的臨時比特位圖的第2比特位置1(即從0000000變成為0100000)，然後將該臨時比特位圖存儲至ET表中第一個空閒表項2中，同時將索引2填入IT表的非公共匹配域[1025,1500]對應的表項中。S1053、複製已有匹配域對應的IT表表項所引用的ET表表項中的比特位圖作為臨時比特位圖，將臨時比特位圖的更新比特位置1，並將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將該第一個空閒表項的索引填入第一層查找結構的IT表的與公共匹配域對應的表項中。參照圖11中所示，針對第二種情況，複製已有匹配域對應的IT表表項所引用的ET表表項中的比特位圖(1000000)作為臨時比特位圖，將臨時比特位圖的第2比特位置1(即從1000000變成為1100000)，然後將該臨時比特位圖存儲至ET表中第一個空閒表項2中，同時將索引2填入IT表的公共匹配域[100,1000]對應的表項中。S1054、複製已有匹配域的比特位圖作為第一臨時比特位圖，將第一臨時比特位圖的更新比特位置1，並將第一臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將該第一個空閒表項的索引填入第一層查找結構的IT表的與公共匹配域對應的表項中；新建全0第二臨時比特位圖，將第二臨時比特位圖的更新比特位置1，並將第二臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將該第一個空閒表項的索引填入第一層查找結構的IT表與非公共匹配域對應的表項中。參照圖12中所示，針對第三種情況，複製已有匹配域對應的IT表表項所引用的ET表表項中的比特位圖(1000000)作為第一臨時比特位圖，將第一臨時比特位圖的第2比特位置1(即從1000000變成為1100000)，然後將該第一臨時比特位圖存儲至ET表中第一個空閒表項2中，同時將索引2填入IT表的公共匹配域[1000,1024]對應的表項中；新建全0第二臨時比特位圖，將第二臨時比特位圖的第2比特位置1(即從0000000變成為0100000)，並將第二臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項3中，並將該第一個空閒表項的索引3填入第一層查找結構的IT表與新增匹配域[1000,2000]減去公共匹配域[1000,1024]後的匹配域[1025,2000]對應的表項中。S1055、新建全0臨時比特位圖，將臨時比特位圖的更新比特位置1，並將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將該第一個空閒表項的索引填入第一層查找結構的IT表的與非公共匹配域對應的表項中。參照圖13中所示，針對第四種情況，將全0臨時比特位圖的第2比特位置1(即從0000000變成為0100000)，然後將該臨時比特位圖存儲至ET表中第一個空閒表項2中，同時將索引2填入IT表的非公共匹配域[2000,3500]對應的表項中。S106、根據前一層查找結構中更新的比特位圖對當前層查找結構的IT表和ET表進行更新。第一層查找結構的更新使得第一層查找結構所有的ET表都產生變化，由於ΔC和ΔD均不為零時已經在初始化階段預留了足夠大的ET表表長，因此在更新過程中並不需要重新初始化其他層查找結構的整個ET表，僅需將新增表項填入ET表的空閒表項。以圖14所示的更新實施例為例進行說明，在第一層查找結構的第一個查找結構LS11如(1)所示，增加了一個ET表表項後如(2)所示，在第一層查找結構的第二個查找結構LS12如(3)所示，增加了一個ET表表項變如(4)所示，在更新之前作為下一層查找結構ET表表項的LS11&LS12按位與(LS11&LS12)結果如(5)所示，更新之後LS11&LS12按位與(LS11&LS12)結果如(6)所示，可見更新後下一層查找結構ET表表項中的表項0、2依舊使用更新前的ET表表項，因此可以利用這一特點減少下一層查找結構IT表和ET表的更新計算量。根據實際應用統計，在每次更新過程中，對於本層查找結構來說，上一層查找結構中未更新的ET表佔大多數，當前層查找結構的ET表是由前一層的兩個ET表按位與而來。參照圖15中所示，假設前一層查找結構的兩個ET表分別是ET表1和ET表2，在ET表1中，新增表項G，其更新自同一ET表中的表項g；在ET表2中，新增表項H，其更新自同一ET表中的表項h。對於當前層查找結構的ET表來說，有表項p和新增表項P，表項p的比特位圖＝表項g的比特位圖&表項h的比特位圖，表項P的比特位圖＝表項G的比特位圖&表項H的比特位圖；若且唯若表項G和表項H均為新更新的表項時，各自的更新比特位進行按位與操作後，表項P的更新比特位才需要置1，其他情況下都置0。可以在更新上一層查找結構的ET表時，為ET表表項增加兩個索引值，第一索引值指示本表項的更新源表項的索引，第二索引值指示本表項的更新目的表項的索引，例如，在更新表項G時，在表項G的第一索引值中填入表項g的索引，在表項g的第二索引值中填入表項G的索引；在更新表項H時，在表項H的第一索引值中填入表項h的索引，在表項h的第二索引值中填入表項H的索引。假設前一層查找結構的ET表更新之後，在更新本層查找結構的IT表和ET表時，不需要根據前一層查找結構的所有IT表和ET表來求得本層查找結構更新的IT表表項和ET表表項，在計算表項P的比特位圖＝表項G的比特位圖&表項H的比特位圖之前，只需要根據前一層查找結構中兩個ET表表項的第一索引值找到本層查找結構的ET表的更新源表項p，對表項p的比特位圖複製為臨時比特位圖，對比特位圖的更新比特位置1後填入本層查找結構ET表第一個空閒表項(圖中索引為17)即可，然後將該第一個空閒表項的索引填入對應的IT表表項中。這樣可以實現快速更新。另外，還可以在更新源表項p的第二索引值中寫入更新目的表項P的索引(17)，這樣當下次更新如果更新源表項恰好為p時，可以通過第二索引值直接找到更新目的表項P，不用再重新更新，這樣可以大大降低更新計算量。進一步的，通過分析發現，在更新當前層查找結構時，無論前一層查找結構更新後ET表表項數目多還是少，都要循環遍歷前一層查找結構的兩個ET表，即當前層查找結構中每個查找結構的更新複雜度為前一層查找結構兩個ET表表長的乘積，但實際上由於前一層查找結構的兩個ET表中大部分ET表表項未更新，對應的本層查找結構的IT表表項和ET表表項不需要更新，因此本發明實施例引入分塊標記比特位的方式進行標記，在更新前一層查找結構時，提前確定本層查找結構需要更新的IT表表項和ET表表項。對於前一層查找結構中進行按位與操作的第一ET表和第二ET表，第一ET表對應第一組標記比特位，第二ET表對應第二組標記比特位，每組標記比特位的長度為第一ET表表長和第二ET表表長的乘積。參照圖16中所示，在更新階段，當更新前一層查找結構時，如果第一ET表表項g被更新，則在第一組比特位標記的比特位[LEN2*g,LEN2*(g+1)]上置1來標記，其中，LEN2為第二ET表表長；如果第二ET表表項h被更新，則在第二組比特位標記的比特位h、h+LEN2*1、h+LEN2*2、h+LEN2*3、……、h+LEN2*(LEN1-1)上置1來標記，其中，LEN1為第一ET表表長；當完成對前一層查找結構的更新後，將第一組標記比特位和第二組標記比特位按比特位相與，結果為1的標記位對應的本層查找結構的IT表索引即為本層查找結構需要更新的IT表索引(圖中陰影部分)。本發明實施例提供的更新過程還可以包括刪除規則，與新增加規則類似，唯一不同的是由置1操作變成了復位即清0操作，更新過程及步驟與新增加規則並無差別，在此不再贅述。本發明實施例提供的報文分類方法，在初始化過程中，生成多層查找結構，每層查找結構均包括IT表和ET表，第一層查找結構的IT表的表項a索引與規則的匹配域a相對應，IT表中存儲ET表表項索引，ET表表項中存儲比特位圖，比特位圖的取值標識在規則集合中對應位置的規則的匹配域是否包含取值a；對於其他層查找結構來說，本層查找結構的IT表和ET表均由前一層的ET表表項生成，其中，本層查找結構的IT表索引由前一層查找結構ET表索引增加更新裕量後計算得到，本層查找結構的ET表由前一層查找結構ET表中比特位圖按位與得到，支持在更新裕量範圍內動態更新規則集合。在查找過程中，根據報文的匹配域對應第一層查找結構的IT表表項索引，得到IT表表項中存儲的ET表表項索引，然後逐層根據前一層查找結構的ET表表項索引值計算得到當前層查找結構的IT表表項的索引值，如果當前層查找結構為最後一層查找結構，則可得到該IT表表項中存儲的ET表表項索引值對應的ET表表項，該ET表表項中存儲的比特位圖的生效比特位所對應的規則為目標規則，通過對報文的匹配域按照索引值逐層查找匹配規則，不斷縮小查找範圍，可以實現對報文快速分類。本發明實施例提供了一種報文分類裝置10，參照圖17中所示，包括：生成單元101，用於在初始化階段，根據規則集合中各個規則的匹配域生成第一層查找結構，其中，每個匹配域對應第一層查找結構中的至少一個查找結構，每個查找結構包括索引表IT表和擴展比特向量表ET表，當匹配域取值為a時，與匹配域對應的第一層查找結構的IT表表項a中存儲第一層查找結構的ET表表項b的索引，ET表表項b中的比特位圖的取值用於標識在規則集合中對應位置的規則的匹配域是否包含取值a，a≥0，b≥0；生成單元101，還用於根據前一層查找結構的ET表表項生成當前層查找結構，直到當前層查找結構中的查找結構數目為1，其中，當前層查找結構的IT表表項k的索引與前一層查找結構的T個ET表表項的索引增加更新裕量後計算得到，T個ET表表項分別屬於前一層查找結構的T個查找結構之一，當前層查找結構的IT表表項k中存儲當前層查找結構的ET表表項f的索引，當前層查找結構的ET表表項f中的比特位圖為T個ET表表項中的比特位圖按位與的結果，k≥0，f≥0，T≥2；查找單元102，用於根據報文的匹配域查找得到對應的第一層查找結構的IT表表項，並得到所述對應的第一層查找結構的IT表表項中存儲的ET表表項索引值；查找單元102，還用於根據得到的前一層查找結構的ET表表項索引值計算得到當前層查找結構的IT表表項的索引值，並得到對應的當前層查找結構的IT表表項中存儲的ET表表項索引值，如果當前層查找結構為最後一層查找結構，則根據得到的當前層查找結構的IT表表項中存儲的ET表表項索引值得到當前層查找結構的ET表表項，其中，得到的當前層查找結構的ET表表項中存儲的比特位圖的生效比特位所對應的規則為報文所屬類型的目標規則；更新單元103，用於在更新階段，根據新增匹配域與已有匹配域具有的公共匹配域的範圍，確定對第一層查找結構的ET表中比特位圖的更新策略；根據前一層查找結構中更新的比特位圖對當前層查找結構的IT表和ET表進行更新。在一種可能的設計中，生成單元101，具體用於：創建臨時比特位圖，其中，臨時比特位圖的存儲形式與第一層查找結構的ET表的存儲形式相同；判斷規則集合中各個規則的匹配域中是否包含取值a，如果包含，則將臨時比特位圖中與各個規則在規則集合中的位置相對應的比特位置1，否則置0；判斷第一層查找結構的ET表的各個表項中是否已經存在與臨時比特位圖相同的比特位圖，如果存在，則將對應表項的索引填入第一層查找結構的IT表表項a中，如果不存在，則將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入第一層查找結構的IT表表項a中。在一種可能的設計中，生成單元101，具體用於：根據前一層查找結構中第2i-1個查找結構的ET表表項c以及第2i個查找結構的ET表表項d，確定當前層查找結構中第i個查找結構的IT表中的一個表項索引為c*(D+ΔD)+d，其中，i≥1，0≤c≤C+ΔC，0≤d≤D+ΔD，C為前一層查找結構中第2i-1個查找結構的ET表表長，D為前一層查找結構中第2i個查找結構的ET表表長，ΔC≥0，ΔD≥0；將前一層查找結構中第2i-1個查找結構的ET表表項c的比特位圖以及第2i個查找結構的ET表表項d的比特位圖進行與操作，得到第二臨時比特位圖；判斷當前層查找結構的ET表的各個表項中是否已經存在與第二臨時比特位圖相同的比特位圖，如果存在，則將對應表項的索引填入當前層查找結構的IT表表項c*(D+ΔD)+d中，如果不存在，則將第二臨時比特位圖存儲至當前層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入當前層查找結構的IT表表項c*(D+ΔD)+d中。在一種可能的設計中，查找單元102，具體用於：根據c*(D+ΔD)+d得到當前層查找結構的IT表表項的索引值。在一種可能的設計中，更新單元103，具體用於：如果新增匹配域包含已有匹配域，將公共匹配域對應的IT表表項所引用的ET表表項中的比特位圖的更新比特位置1，新建全0臨時比特位圖，將臨時比特位圖的更新比特位置1，並將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入第一層查找結構的IT表的非公共匹配域對應的表項中，非公共匹配域為新增匹配域減去已有匹配域後剩餘的匹配域；如果新增匹配域被包含於已有匹配域，複製已有匹配域對應的IT表表項所引用的ET表表項中的比特位圖作為臨時比特位圖，將臨時比特位圖的更新比特位置1，並將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入第一層查找結構的IT表的與公共匹配域對應的表項中如果新增匹配域與已有匹配域部分重疊，複製已有匹配域的比特位圖作為第一臨時比特位圖，將第一臨時比特位圖的更新比特位置1，並將第一臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入第一層查找結構的IT表的與公共匹配域對應的表項中；新建全0第二臨時比特位圖，將第二臨時比特位圖的更新比特位置1，並將第二臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入第一層查找結構的IT表與非公共匹配域對應的表項中如果新增匹配域與已有匹配域不具有公共匹配域，新建全0臨時比特位圖，將臨時比特位圖的更新比特位置1，並將臨時比特位圖存儲至第一層查找結構的ET表中第一個空閒表項，並將第一個空閒表項的索引填入第一層查找結構的IT表的與非公共匹配域對應的表項中。在一種可能的設計中，對於前一層查找結構中進行按位與操作的第一ET表和第二ET表，第一ET表對應第一組標記比特位，第二ET表對應第二組標記比特位，每組標記比特位的長度為第一ET表表長和第二ET表表長的乘積，所述更新單元103還用於：在更新階段，當更新前一層查找結構時，如果第一ET表表項g被更新，則在第一組比特位標記的比特位[LEN2*g,LEN2*(g+1)]上置1來標記，其中，LEN2為第二ET表表長；如果第二ET表表項h被更新，則在第二組比特位標記的比特位h、h+LEN2*1、h+LEN2*2、h+LEN2*3、……、h+LEN2*(LEN1-1)上置1來標記，其中，LEN1為第一ET表表長；當完成對前一層查找結構的更新後，將第一組標記比特位和第二組標記比特位按比特位相與，結果為1的標記位對應的本層查找結構的IT表索引即為本層查找結構需要更新的IT表索引。在一種可能的設計中，比特位圖為比特串或分層塊壓縮結構，所述分層塊壓縮結構包含S層的比特串，第s層比特串的每一位對應於第s+1層的一個比特串，當第s層中一個比特串全為0時，所述全為0比特串及對應的s+1層的比特串均不存儲，其中，0<s<S。由於本發明實施例中的報文分類裝置可以應用於上述報文分類方法，因此，其所能獲得的技術效果也可參考上述方法實施例，本發明實施例在此不再贅述。需要說明的是，生成單元、查找單元、更新單元可以為單獨設立的處理器，也可以集成在控制器的某一個處理器中實現，此外，也可以以程序代碼的形式存儲於控制器的存儲器中，由控制器的某一個處理器調用並執行以上生成單元、查找單元、更新單元的功能。這裡所述的處理器可以是一個中央處理器(英文全稱：centralprocessingunit，英文簡稱：CPU)，或者是特定集成電路(英文全稱：applicationspecificintegratedcircuit，英文簡稱：ASIC)，或者是被配置成實施本發明實施例的一個或多個集成電路。應理解，在本發明的各種實施例中，上述各過程的序號的大小並不意味著執行順序的先後，各過程的執行順序應以其功能和內在邏輯確定，而不應對本發明實施例的實施過程構成任何限定。本領域普通技術人員可以意識到，結合本文中所公開的實施例描述的各示例的單元及算法步驟，能夠以電子硬體、或者計算機軟體和電子硬體的結合來實現。這些功能究竟以硬體還是軟體方式來執行，取決於技術方案的特定應用和設計約束條件。專業技術人員可以對每個特定的應用來使用不同方法來實現所描述的功能，但是這種實現不應認為超出本發明的範圍。所屬領域的技術人員可以清楚地了解到，為描述的方便和簡潔，上述描述的系統、裝置和單元的具體工作過程，可以參考前述方法實施例中的對應過程，在此不再贅述。在本申請所提供的幾個實施例中，應該理解到，所揭露的系統、設備和方法，可以通過其它的方式實現。例如，以上所描述的設備實施例僅僅是示意性的，例如，所述單元的劃分，僅僅為一種邏輯功能劃分，實際實現時可以有另外的劃分方式，例如多個單元或組件可以結合或者可以集成到另一個系統，或一些特徵可以忽略，或不執行。另一點，所顯示或討論的相互之間的耦合或直接耦合或通信連接可以是通過一些接口，設備或單元的間接耦合或通信連接，可以是電性，機械或其它的形式。所述作為分離部件說明的單元可以是或者也可以不是物理上分開的，作為單元顯示的部件可以是或者也可以不是物理單元，即可以位於一個地方，或者也可以分布到多個網絡單元上。可以根據實際的需要選擇其中的部分或者全部單元來實現本實施例方案的目的。另外，在本發明各個實施例中的各功能單元可以集成在一個處理單元中，也可以是各個單元單獨物理存在，也可以兩個或兩個以上單元集成在一個單元中。所述功能如果以軟體功能單元的形式實現並作為獨立的產品銷售或使用時，可以存儲在一個計算機可讀取存儲介質中。基於這樣的理解，本發明的技術方案本質上或者說對現有技術做出貢獻的部分或者該技術方案的部分可以以軟體產品的形式體現出來，該計算機軟體產品存儲在一個存儲介質中，包括若干指令用以使得一臺計算機設備(可以是個人計算機，伺服器，或者網絡設備等)執行本發明各個實施例所述方法的全部或部分步驟。而前述的存儲介質包括：U盤、移動硬碟、只讀存儲器(英文全稱:read-onlymemory，英文簡稱：ROM)、隨機存取存儲器(英文全稱：randomaccessmemory，英文簡稱：RAM)、磁碟或者光碟等各種可以存儲程序代碼的介質。以上所述，僅為本發明的具體實施方式，但本發明的保護範圍並不局限於此，任何熟悉本
技術領域：
：的技術人員在本發明揭露的技術範圍內，可輕易想到變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應以所述權利要求的保護範圍為準。當前第1頁1 2 3 當前第1頁1 2 3