用於分組分類的方法和設備的製作方法

2023-06-15 02:22:16 3

用於分組分類的方法和設備的製作方法
【專利摘要】一方面，本發明通過以壓縮形式表示分組分類規則資料庫來減少基於規則的分組分類所需的低等待時間存儲器的量。對諸如包括多個ACE的ACL資料庫的分組處理規則資料庫進行預處理以獲得對應的規則指紋。這些規則指紋比規則小得多，並且易於以有限的量容納在一般對於分類引擎可用的晶片上或其它低等待時間存儲器中。然後，可以將規則資料庫存儲在晶片外或其它較高等待時間存儲器中，因為初始匹配操作只涉及對象分組的分組密鑰和指紋資料庫。只有當在分組密鑰與指紋資料庫中的條目之間找到初步匹配時，才存取規則資料庫以進行完整分組分類。因此，本發明還有利地將對規則資料庫的存取減至最少。
【專利說明】用於分組分類的方法和設備

【技術領域】
[0001] 一般來說，本發明涉及數據網絡，具體來說，涉及數據網絡中的分組分類。

【背景技術】
[0002] 存取控制列表(ACL)是用於過濾IP業務的常用方法。ACL包括稱為存取控制條目 (ACE)的規則的列表。在一個示例情形中，ACE按照源地址和目的地址的函數將流入分組映 射到流出埠，並指示應當允許(路由）還是拒絕(丟棄)給定的流入分組。當然，ACL也可以 用於其它目的，包括網絡地址轉譯（NAT)處理、基於策略的路由等。
[0003] 隨著IP網絡(例如，在最新電信網絡中實現的IP網絡）的"智能性"的增加，越來 越需要更精密的分組分類、安全過濾、策略路由、分組重定向以進行服務鏈處理、OpenFlow 處理交換等。"OpenFlow"是對網絡路由器、交換機和接入點中的轉發表提供遠程控制並且 因此允許動態控制網絡行為、策略等的開放接口。
[0004] 可以想像，ACL中所需的ACE的數量會是相當大的。ACL包括多於一千個ACE (例 如，多達四千個或更多個ACE)並不罕見。而且，對於不同活動以及對於不同協議族，可存在 不同ACL，例如，數據平面中的每個ACL "綁定點"對應於不同的協議族類型，如IPv4、IPv6、 虛擬LAN (VLAN)、多協議標籤交換（MPLS)等。跨越在網絡交換機或路由器中所實現的所有 ACL的規則的總數會相當大，例如超過十萬。
[0005] 基於ACL的搜索類型包括最長前綴匹配（LPM)(例如，用於源IP - IPv4/IPv6、目 的IP - IPv4/IPv6的LPM)、用於協議或標誌的精確匹配搜索以及用於TCP/UDP源埠和目 的埠的範圍匹配。在這方面，三重CAM (TCAM)是基於經過交換機或路由器的分組設計用 於快速表查找的內容可尋址存儲器（CAM)的專門類型。但是，一般存在決定可用於快速搜 索大型ACL和/或大量ACL的TCAM的量的顯著的功率、成本和空間約束。
[0006] 其它方法包括諸如改進型遞歸流分類（MRFC)的算術解決方案。但是，特有地，基 於MRFC的解決方案需要許多外部存儲器存取，這是因為MRFC處理中所需的大量存儲器通 常不適合用作路由引擎的數字處理器的晶片上存儲器。另一個問題是，MRFC似乎也不能對 更廣泛的分組"密鑰"行得通，更廣泛的分組"密鑰"正隨著IPv6使用的增加而變得越來越 普及。


【發明內容】

[0007] -方面，本發明通過以壓縮形式表示分組分類規則資料庫來減少基於規則的分組 分類所需的低等待時間存儲器的量。對諸如包括多個ACE的ACL資料庫的分組處理規則數 據庫進行預處理以獲得對應的規則指紋。這些規則指紋比規則小得多，並且易於以有限的 量容納在一般對於分類引擎可用的晶片上或其它低等待時間存儲器中。而規則資料庫可以 存儲在晶片外或其它較高等待時間存儲器中，因為初始匹配操作只涉及對象分組的分組密 鑰和指紋資料庫。只有當在分組密鑰與指紋資料庫中的條目之間找到初步匹配時，才存取 規則資料庫以進行完整分組分類。因此，本發明還有利地將對規則資料庫的存取減至最少。
[0008] 在一個實施例中，一種在網絡節點中的分組分類的方法包括：獲得對應於由網絡 節點所接收的數據分組的分組密鑰；以及通過將分組密鑰的"特徵位"與指紋資料庫中的規 則指紋進行比較來標識是分組密鑰的可能匹配的一個或多個分組處理規則。指紋資料庫用 作包括分組處理規則的集合的規則資料庫的壓縮表示。規則指紋包括與分組處理規則中作 為區分它們的規則或子集的搜索切割點操作的位位置對應的"切割點位"。因此，任何給定 分組密鑰的特徵位是佔據對應於切割點位的位位置的位。
[0009] 該方法還包括：從規則資料庫獲取所標識的一個或多個分組處理規則；將分組密 鑰與所獲取的一個或多個規則進行比較；以及取決於分組密鑰是否與所獲取的一個或多個 規則中的任何規則匹配來指示規則命中或未命中。當然，如果沒有從指紋資料庫為分組密 鑰標識任何可能匹配的規則，那麼指示規則未命中。這種處理有利地允許處理引擎只有在 它首先從指紋資料庫確定存在一個或多個可能匹配的規則之後才對整個分組處理規則數 據庫進行存取。
[0010] 這種布置有利地在配置成基於分組分類在分組網絡中路由或交換分組的網絡節 點中實現。在一個示例實施例中，網絡節點包括一個或多個通信接口，其配置成接收輸入分 組以進行路由或交換處理，並依據根據由網絡節點所執行的分組分類處理關於輸入分組所 做的交換或路由決定而發送輸出分組。
[0011] 為了支持分組分類處理，網絡節點包括一個或多個處理電路，其基於配置成執行 以下動作而配置成執行所述分組分類處理：獲得對應於由網絡節點所接收的數據分組的分 組密鑰；以及通過將分組密鑰的特徵位與用作包括分組處理規則的集合的規則資料庫的壓 縮表示的指紋資料庫中的規則指紋進行比較來標識是分組密鑰的可能匹配的一個或多個 分組處理規則。
[0012] 規則指紋在其存儲器"佔用"方面比規則本身小得多，它們包括與分組處理規則中 作為區分它們的各個規則或子集的搜索切割點操作的位位置對應的切割點位。此外，如之 前所解釋，分組密鑰的特徵位佔據對應於切割點位的位位置。因此，通過將特徵位與切割點 位進行比較，例如通過按照特徵位值的函數遍歷表示切割點位的搜索結構，這一個或多個 處理電路可以確定是否存在是分組密鑰的可能匹配的任何分組處理規則，而無需存取規則 資料庫。
[0013] 假設標識了一個或多個可能匹配，那麼可以視為是"分類引擎"的這一個或多個處 理電路還配置成從規則資料庫獲取所標識的一個或多個分組處理規則，將分組密鑰與所獲 取的一個或多個規則進行比較，並取決於分組密鑰是否與所獲取的一個或多個規則中的任 何規則匹配來指示規則命中或未命中。在這方面，將明白，指紋資料庫處理還可導致確定規 則資料庫中沒有一個分組處理規則是分組密鑰的可能匹配。即，指紋資料庫處理可導致沒 有標識任何可能匹配的規則。在這種情況下，有利地，這一個或多個處理電路避免存取規則 資料庫，而是返回"未命中"指示，由此可以觸發分組丟棄或其它基於"未命中"的處理。
[0014] 當然，本發明不限於以上特徵和優點。實際上，在閱讀以下詳細描述和查看附圖 後，本領域技術人員將認識到額外的特徵和優點。

【專利附圖】

【附圖說明】
[0015] 圖1是具有至少一個節點的分組數據網絡的一個實施例的局部框圖，這至少一個 節點配置成結合分組處理規則的規則資料庫利用規則指紋的指紋資料庫來執行分組分類。
[0016] 圖2是分組、分組密鑰與規則資料庫中的規則之間的映射的一個實施例的圖。
[0017] 圖3是存取控制列表(ACL)數據結構的已知示例的圖。
[0018] 圖4是圖1中所介紹的這至少一個節點的一個實施例的框圖，它示出利用第一存 儲器中的指紋資料庫與第二存儲器中的對應規則資料庫的示例功能電路細節。
[0019] 圖5是來自分組的特徵位的示例圖，這些特徵位可以是例如在本文中用於搜索指 紋資料庫以便標識對應規則資料庫中的可能匹配的分組處理規則的特徵位。
[0020] 圖6是為分組處理規則的集合確定的切割點位的示例圖，切割點位可以是例如用 於形成對應於規則的規則指紋的切割點位。
[0021] 圖7是如在圖1中所介紹的這至少一個節點的一個示例中所實現的功能處理電路 和相關聯的資料庫結構的另一框圖。
[0022] 圖8是基於使用對應於分組處理規則的規則資料庫的規則指紋的指紋資料庫進 行分組分類處理的方法的一個實施例的邏輯流程圖。
[0023] 圖9是表示規則指紋的指紋資料庫的搜索結構40的一個實施例的局部框圖，搜索 結構可以是例如在指紋資料庫處理的一個或多個實施例中遍歷以便標識給定分組密鑰的 可能匹配的分組處理規則的搜索結構。
[0024] 圖10和圖11是提供圖9的示例搜索結構的進一步細節的框圖。
[0025] 圖12-16是表示或者以其它方式包含規則指紋的指紋資料庫的搜索結構的進一 步示例實施例。

【具體實施方式】
[0026] 圖1是包括一個或多個網絡節點12和14的分組數據網絡10的局部框圖。至少 節點12是根據本文所呈現的分組分類教導進行配置的，包括有利地使用指紋資料庫，這將 在以下論述中舉例詳述。當然，也可以是類似地配置節點14中的一個或多個節點。作為非 限制性示例，網絡10是例如用於在根據第三代合作夥伴計劃（3GPP)協議標準配置的移動 通信網絡中遞送網際網路協議（IP)多媒體服務的IP多媒體子系統（MS)。
[0027] 參考圖2,節點12、14接收流入分組16。已知，每個流入分組16包括分組密鑰18， 分組密鑰18可以例如嵌入在其報頭信息中，或者通過節點12、14從分組報頭為分組16導 出分組密鑰18。節點12、14根據分組處理規則22 (例如，規則22-1、22-2、"·、22-Λ〇的規 則資料庫20處理每個流入分組16。實際上，可能存在對應於不同協議類型和/或不同分組 處理功能(例如，服務質量過濾等）的多個規則資料庫20,每個這樣的資料庫20包含分組處 理規則22的集合。但是，為了易於論述，參考一個規則資料庫20,要理解，本文所描述的處 理直接延伸到多個規則資料庫20和/或延伸到其中可以將所示的規則資料庫20理解為是 多個規則資料庫20的超集或集成的情況。
[0028] 此外，圖3示出存取控制列表（ACL)的一個已知示例，ACL是由稱為存取控制條目 (ACE)的規則組成的一種規則資料庫類型，但是如本文所使用的規則資料庫20可以用有利 的方式加以構造。對於在其上接收流入分組16的一個或多個節點接口激活ACL，並且ACL 基於流入分組16的源和/或目的IP位址將流入分組16映射到流出（目的)埠。因此，取 決於流入分組16的源/目的IP位址激活不同ACE，並且根據匹配到分組16的特定ACE，流 入分組16變成對應的流出分組16 (或被丟棄)。
[0029] 至少節點12偏離常規方法，常規方法基於將流入分組16的分組密鑰18與規則數 據庫20進行直接比較以標識任何匹配的分組處理規則22來執行上述分組分類處理。而節 點12卻是利用基於"指紋"的方法，該方法大大減少了執行高速分組分類所需的低等待時 間存儲器的量。在這方面，圖4呈現了節點12的示例布置。
[0030] 在圖4中示出的示例實施例中，網絡節點12配置成基於分組分類在分組網絡10 中路由或交換分組16。示例節點12包括一個或多個通信接口 30、一個或多個處理電路32、 用於存儲規則指紋38的指紋資料庫36和/或表示或以其它方式包含指紋資料庫36的對 應搜索結構40的第一存儲器34 (它可以是一個或多個存儲器裝置或電路)。這一個或多個 處理電路32包括到第二存儲器44 (它可以是一個或多個存儲器裝置或電路)的直接或間接 鏈路42,第二存儲器44用於存儲規則資料庫20,規則資料庫20同樣包含分組處理規則22 的一個(或多個）集合。
[0031] 參考圖5,給定流入分組16的分組密鑰18包括多個"特徵位"50。更詳細地，每個 分組密鑰18將理解為包含佔據從最高有效位（MSB)位置到最低有效位（LSB)位置排序的 相應位位置的一族位。如本文稍後將詳細解釋，如圖6中所介紹，根據本文的教導處理分組 處理規則22,以便找到區分分組處理規則22中的各個分組處理規則、或至少區分規則數據 庫20中的分組處理規則22的子集的"切割點位"52。對應地，每個分組密鑰18中的特徵 位50是佔據與分組處理規則22的切割點位52的位位置對應的位位置的那些位。
[0032] 記著這些示例細節，節點12配置成接收輸入分組16以便進行路由或交換處理，並 依據根據由網絡節點12所執行的分組分類處理關於輸入分組16所做的交換或路由決定而 發送(對應的)輸出分組16。這裡，將明白，節點12所做的交換或路由決定確定如何以及何 時將流入分組16映射到節點12的特定埠以作為流出分組16。當然，這些決定還涵蓋分 組丟棄，其中不將給定流入分組16作為流出分組16從節點12發送，而是將其丟棄，因為其 分組密鑰18沒有與在節點12處所定義的任何分組處理規則22匹配。
[0033] 節點12包括一個或多個處理電路32,這一個或多個處理電路32基於配置成獲得 對應於由網絡節點12所接收的數據分組16的分組密鑰18而配置成執行分組分類處理。分 組密鑰18可以包含在分組報頭信息中，或者可以通過這一個或多個處理電路32或通過節 點12中的另一個處理電路來從分組報頭信息中導出分組密鑰18。不管如何，這一個或多個 處理電路32結合指紋資料庫36利用分組密鑰18來標識是分組密鑰18的可能匹配的一個 或多個分組處理規則22。
[0034] 可能匹配的分組處理規則22的標識是通過將分組密鑰18的特徵位50與用作規 則資料庫20的壓縮表示的指紋資料庫36中的規則指紋38進行比較來進行的。當然，規則 資料庫20包括用於控制流入分組16的分類和處理的實際分組處理規則22。規則指紋38 小於分組處理規則22,因為它們包含對應於分組處理規則22中作為區分它們的各個規則 22或子集的搜索切割點操作的位位置的切割點位52。
[0035] 如上所述，分組密鑰18的特徵位50佔據對應於切割點位52的位位置，並且這允 許這一個或多個處理電路32僅僅通過存取指紋資料庫36或等效地評估實施或以其它方式 表示指紋資料庫36的搜索結構40來確定規則資料庫20中的任何分組處理規則22是否是 給定分組密鑰18的可能匹配。例如，搜索結構40包括對應於切割點位52的節點，並按照 所評估的分組密鑰18中的特徵位50的二進位值的函數遍歷搜索結構40。
[0036] 假設這種處理導致標識是分組密鑰18的可能匹配的一個或多個分組處理規則 22,那麼這一個或多個處理電路32配置成從規則資料庫20獲取所標識的一個或多個分組 處理規則22,並將分組密鑰18與所獲取的一個或多個規則22進行比較。對應地，這一個或 多個處理電路32配置成取決於分組密鑰18是否與所獲取的這一個或多個規則22中的任 何規則匹配來指示規則命中或未命中。將明白，該指示促使對討論中的分組16運用處理一 例如，在規則命中的情況下，節點12內的分組處理電路根據匹配的分組處理規則22處理分 組16,並且在規則未命中的情況下，分組處理電路丟棄分組16或採取其它基於未命中的措 施。
[0037] 記著上文，將明白，在至少一個實施例中，這一個或多個處理電路32配置成基於 根據與給定接收分組16的分組密鑰18匹配的獲取的分組規則22處理給定接收分組16而 將給定接收分組16分類以便作為對應的輸出分組16進行交換或路由。在相同或在其它實 施例中，這一個或多個處理電路32包括數字處理電路，該數字處理電路配置成執行可能與 分組密鑰18匹配的一個或多個分組處理規則22的標識，並執行所獲取的一個或多個規則 22與分組密鑰18的比較。數字處理電路可以包括一個或多個微處理器或其它固定或可編 程處理電路。在至少一個實施例中，這一個或多個處理電路32包括基於微處理器的電路， 該電路根據本文的教導至少部分地基於存儲在第一存儲器34、第二存儲器44、或對於這一 個或多個處理電路32可存取的另一存儲器或計算機可讀介質中的電腦程式指令的執行 而進行配置。
[0038] 在至少一個實施例中，第一存儲器34是晶片上存儲器、或能夠支持討論中的高速 路由處理的另一類型的低等待時間存儲器。在一個示例實施例中，第一存儲器34位於包括 這一個或多個處理電路32的數字處理電路的內部，或者第一存儲器34以其它方式對於數 字處理電路可以第一等待時間存取。相反地，第二存儲器44位於數字處理電路的外部，或 者以其它方式對於數字處理電路可以與第一等待時間相比較高的第二等待時間存取。數字 處理電路配置成從第二存儲器44獲取所標識的一個或多個分組處理規則22,但是在處理 給定分組密鑰18期間可以有利地避免這樣做，除非指紋資料庫處理首先指示，在規則數據 庫20中存在是分組密鑰18的可能匹配的至少一個分組處理規則22。
[0039] 圖7示出與圖4中所介紹的節點體系結構一致的示例布置。這裡，節點12包括分 組處理引擎60和可選的硬體邏輯或數據平面代碼62。實際規則資料庫20存儲在第二存儲 器44中，第二存儲器44可以是低成本外部存儲器，例如DDR3 (第三代雙倍數據速率同步動 態隨機存取存儲器)。這裡，將了解，分組處理引擎60表示之前公開的這一個或多個處理電 路32的實現，並且分組處理引擎60可以包括作為晶片上存儲器或如RLDRAM (縮短等待時 間動態隨機存取存儲器）的另一類型的低等待時間存儲器的第一存儲器34。這裡，以第一 存儲器34必須快速以支持指紋資料庫處理(搜索可能匹配的規則22)、而第二存儲器44可 能較為緩慢的相對意義來定義術語"低"和"高"的使用，第二存儲器44之所以可以較為緩 慢是因為，與它的事務的數量變得低得多，因為利用指紋資料庫36進行對於可能匹配的搜 索，並且只是為了檢索可能匹配的規則22才需要存取規則資料庫20。
[0040] 注意，圖7指示，第一存儲器34提供搜索結構存儲，以便導航搜索結構40,從而預 測可能匹配的規則22。在這方面，分組處理引擎60或更一般地是之前所介紹的這一個(或 多個）處理電路32配置成按照指紋資料庫36的切割點位52的函數定義搜索結構40並按 照分組密鑰18的特徵位50的函數遍歷搜索結構40,以便標識是分組密鑰18的可能匹配的 這一個或多個分組處理規則22。
[0041] 在一個或多個實施例中，這一個或多個處理電路32配置成將單個分組處理規則 22標識為分組密鑰18的唯一的可能匹配，或者標識規則資料庫20中表示分組密鑰18的可 能匹配的分組處理規則22的子集或範圍。在任一情況下，在分組分類處理的有利配置中， 這一個或多個處理電路32不會為了給定分組密鑰18的分類處理存取第二存儲器44,除非 指紋資料庫處理指示在規則資料庫20中存在至少一個可能匹配的分組處理規則22。
[0042] 在至少一個實施例中，指紋資料庫36配置成在分組密鑰18與規則資料庫20中的 相應的各個規則22之間提供精確匹配。這裡，這一個或多個處理電路32基於配置成執行 以下動作而配置成預處理規則資料庫20以便隨後在現場分組分類處理中使用：在邏輯上 按照二進位順序將規則資料庫20中的分組處理規則22排序；獲得通過對按照所述二進位 順序採取的分組處理規則22的配對運用異或("X0R")操作而產生的最高有效位（MSB)的位 位置，其中這些位位置是切割點位52。
[0043] 對應地，在一個或多個實施例中，這一個或多個分組處理電路32另外配置成基於 根據按照降序或升序順序採取的切割點位52對分組處理規則22的集合進行劃分和進一步 細分而形成與切割點位52的列表相對應的搜索結構40。在至少一個這樣的布置中，指紋數 據庫處理允許從規則資料庫20標識單個可能匹配的規則22,並且這一個或多個處理電路 32配置成從規則資料庫20檢索這單個標識的規則22,以便與正在分類的分組16的分組密 鑰18進行比較匹配。
[0044] 在一個或多個實施例中，指紋資料庫36或等效地指紋資料庫36的搜索結構表示 配置成提供分組密鑰18與規則資料庫20中的各個規則22的相應範圍之間的範圍匹配。這 種布置基於將這一個或多個處理電路32配置成基於以下動作預處理規則資料庫20以獲得 指紋資料庫36 :將分組處理規則22按序排到非重疊範圍中；生成對應於每個非重疊範圍的 下端的規則指紋38 ;以及形成對應於規則指紋38的搜索結構40。對應地，這一個或多個處 理電路32基於配置成從非重疊範圍中的相應非重疊範圍檢索多個規則22而配置成從規則 資料庫20中獲取所標識的一個或多個分組處理規則22,以便對於分組密鑰18進行所檢索 的多個規則22中的各個規則的比較匹配。
[0045] 在一個或多個其它實施例中，指紋資料庫36基於具有重疊前綴的規則22的範圍。 這一個或多個處理電路32配置成：預處理規則資料庫20以便結合對應於與重疊前綴相關 聯的這一個或多個規則22的索引值來存儲規則22,並標識是給定分組密鑰18的可能匹配 的這一個或多個分組處理規則22。具體來說，這裡，這一個或多個處理電路32配置成執行 最長前綴匹配，並通過對包含規則資料庫20的第二存儲器44進行一次存取來檢索所標識 的一個或多個分組處理規則22,從而檢索與最長前綴匹配相關聯的規則22以及對應於與 重疊前綴相關聯的這一個或多個規則22的這一個或多個索引值。
[0046] 此外，在其中指紋資料庫36基於具有重疊前綴的規則22的範圍的至少一個實施 例中，這一個或多個處理電路32配置成將對應於與重疊前綴相關聯的這一個或多個規則 22的那些索引值存儲在表示指紋資料庫36的搜索結構40中。關於這點，這一個或多個處 理電路32配置成通過關於搜索結構40執行最長前綴匹配來標識是給定分組密鑰18的可 能匹配的這一個或多個分組處理規則22,包括：響應於在搜索結構40中遍歷超過存在可能 匹配的規則的子節點，利用索引值來從子節點回溯到表示可能匹配的規則22的對應母節 點。
[0047] 此外，在至少一個實施例中，這一個或多個處理電路32在一個或多個實施例中配 置成將對應於與重疊規則前綴相關聯的這一個或多個規則22的那些索引值存儲在表示指 紋資料庫36的搜索結構40中。這一個或多個處理電路32通過以下方法來標識是分組密 鑰18的可能匹配的這一個或多個分組處理規則22 :關於搜索結構40執行最長前綴匹配， 以便標識將從規則資料庫20獲取以關於分組密鑰18進行比較匹配的規則22的範圍。
[0048] 記著以上分組分類處理配置，圖8示出在節點12處實現的分組分類處理的方法 800的一個實施例。將了解，給定流入分組16的"現場"處理包括處理它的分組密鑰18以 便進行分類處理，它不包括方框802中所介紹的處理，而是包括方框804-812 (偶數)。方框 802中的"預處理"操作應理解為是在按需基礎上執行，例如響應於新規則資料庫20的增加 和/或響應於現有規則資料庫20的修改而執行。
[0049] 預處理操作包括基於根據之前所描述的教導（即，切割點位確定等）處理規則數據 庫20的分組處理規則22而生成構成指紋資料庫36的規則指紋38。此外，在一個或多個實 施例中，預處理包括：以排序方式存儲規則22以反映指紋資料庫36的組織，和/或存儲反 映之前所描述的規則22的重疊範圍的索引值。
[0050] 在任一情況下，在現場路由/交換操作期間關於任何給定分組密鑰18的專利分類 方法800包括獲得(方框804)對應於由節點12所接收的數據分組16-流入分組的分組密 鑰18。方法800還包括通過將分組密鑰18的特徵位50與指紋資料庫36中的規則指紋38 進行比較來標識(方框806)是分組密鑰18的可能匹配的一個或多個分組處理規則22。如 上所述，指紋資料庫36在預處理(方框802)期間獲得，並且它用作規則資料庫20的壓縮表 示。具體來說，規則指紋38包括與分組處理規則22中作為區分它們的規則或子集的搜索 切割點操作的位位置對應的切割點位52,其中分組密鑰18的特徵位50佔據對應於切割點 位52的位位置。
[0051] 方法800繼續從規則資料庫20獲取（方框808)所標識的一個或多個分組處理規 則22,然後將分組密鑰18與所獲取的一個或多個規則22進行比較(方框810)。對應地，方 框800包括取決於分組密鑰18是否與所獲取的一個或多個規則22中的任何規則匹配來指 示(方框812)規則命中或未命中。
[0052] 因此，將明白，預處理用於確定將用作構成指紋資料庫36的規則指紋38的切割點 位52,並且切割點位52將需要比原始規則資料庫20小得多的空間。這種布置允許實際分 組處理規則22駐留在低成本外部存儲器中。當然，這種允許並不是意味著，強制將規則數 據庫20存儲在分組處理引擎60的外部，或本發明在這類情形中不適用。實際上，也可以是， 一些設計允許指紋資料庫36和規則資料庫20均位於晶片上或甚至在相同存儲器中。
[0053] 甚至在這類情況下，通過指紋資料庫處理以確定是否存在給定分組密鑰18的任 何可能匹配的規則22而獲得的效率是顯著的，因為這種處理只需要涉及小得多的指紋位 串的處理(與處理整個長度的分組處理規則22的備選方案相比)。一種示例情形是多核"高 接觸"分組處理。一般來說，指紋資料庫36的使用提供緩存友好的查找處理，並且甚至可以 更廣泛地理解為優化查找過程以實現更好的性能。
[0054] 但是，如本文中所認識，有利的是至少將指紋資料庫36存儲在晶片上存儲器或其 它低等待時間存儲器中。可以在搜索結構40中布置或以其它方式表示指紋資料庫36,搜索 結構40可以是二元樹、N元樹、直接索引結構等。這種使用指紋資料庫36來進行初始可能 匹配搜索的方法將對潛在較大的規則資料庫20 (具有其潛在較長字長度的規則22)執行高 速搜索的難題轉換為小得多的指紋資料庫36的可管理的高性能結構化搜索，以便預測任 何實際規則22是否是任何給定分組密鑰18的可能匹配。
[0055] -旦從指紋資料庫處理標識這一個或多個可能匹配的規則22,便從實際規則存儲 引進所標識的這一個或多個規則22,並且這是唯一一次分組處理引擎60需要存取外部或 高等待時間存儲器(如DDR3)以進行現場分組分類。如果所獲取的這一個或多個規則22中 有任何一個規則與分組密鑰18匹配，那麼分組處理引擎60斷言規則命中，否則它斷言未命 中。
[0056] 在這種布置的許多優點中，有這些項：在存在任何存取實際規則資料庫20的需要 之前，生成並最初搜索壓縮搜索結構40 ;查找成本與規則資料庫20中的規則22的寬度(按 位）無關；壓縮搜索結構40形式的指紋資料庫36具有比規則資料庫20小得多的存儲器佔 用，並且比整個規則資料庫20更容易符合晶片上或其它(相對而言)稀有的低等待時間存儲 器；以及在一個或多個實施例中，基於指紋的分組分類的方法只需要一次存取外部或高等 待時間存儲器(用於獲取標識為給定分組密鑰18的可能匹配的規則22)。
[0057] 例如，預期，384個位的密鑰寬度足以覆蓋IPv6 ACL，並且在本文的教導下，對於對 應的指紋資料庫36,可以在晶片上存儲器的小於3兆位中容納64K個規則。在28nm矽工藝 中的該存儲器量小於2平方毫米管芯面積，即使假設百分之二十的實現開銷。表示指紋數 據庫36的搜索結構40可以利用二元搜索算法、樹形搜索算法和/或直接索引算法來有效 地搜索。在至少一個實施例中，搜索基於本文稍後將詳述的優化LPM查找。大體上，本文教 導的基於指紋的方法具有直接適用於精確匹配搜索、範圍匹配搜索、基於LPM的查找等的 優點。
[0058] 這裡，應注意，指紋處理不會導致假否定。即，如果指紋處理指示規則22中沒有一 個規則是分組密鑰18的可能匹配，那麼在不出錯的情況下，可以斷言未命中。另一方面，如 果指紋處理指示規則22中有一個或多個規則是分組密鑰18的可能匹配，那麼結果可以是， 所獲取的規則22中沒有一個規則是分組密鑰18的實際匹配。因此，指紋處理可能生成假 肯定，但是這種可能性不會降低通過使用指紋處理以確定是否應當從規則資料庫20獲取 任何一個或多個規則22以便對於分組密鑰18進行比較而獲得的效率。
[0059] 在一種方法中，規則22包括用作規則資料庫20的ACL中的ACE。在一個或多個實 施例中，預處理包括： -在不同欄位中分解ACL規則(一些欄位可以組合）： 〇一些欄位用於LPM匹配 〇一些欄位用於精確匹配 〇一些欄位用於範圍匹配 -處理引擎60創建叉積以便找到最終解答，就像MRFC中所做的那樣。
[0060] 在與ERICSSON SMART EDGE路由器中的MRFC相關的示例中，這種預處理可以包 括： -取ACL的所有欄位並確定它們的叉積； -嘗試進行查找操作。
[0061] 在精確匹配查找示例中，令"R1"表示第一分組處理規則22-1，"R2"表示規則 22-2,依此類推。此外，對於規則R1-R8的示例集合，假設規則位模式如下（LSB在最右邊）： R1- 00000000 00000000 00000000 00000000 R2- 00100000 00101000 00000000 00000000 R3- 00101000 00101100 00000000 00000000 R4- 01001000 00101101 11001100 01010100 R5- 01100000 00101110 11001100 00110010 R6- 01110000 00110110 00011001 00110011 R7- 10000000 11000000 00011010 00000000 R8- 10010000 11110000 00000000 00000000 規則R1-R8按升序順序排序。排序不需要是物理的，例如，排序可以在邏輯上進行，而 不一定在實際存儲中將規則重新排序。
[0062] 然後，對按照其連續順序所取的規則22的每個配對採取邏輯X0R。該操作標識這 兩個規則之間的最高有效區分位的位位置，並且X0R處理包括將所標識的位位置記錄為切 割點位52。參見R1-R8的以下示例： X0R_BIT1=在（R1 XOR R2)中所設置的最高有效位的位位置=29 X0R_BIT2=在（R2 XOR R3)中所設置的最高有效位的位位置=27 X0R_BIT3=在（R3 XOR R4)中所設置的最高有效位的位位置=30 X0R_BIT4=在（R4 XOR R5)中所設置的最高有效位的位位置=29 X0R_BIT5=在（R5 XOR R6)中所設置的最高有效位的位位置=28 X0R_BIT6=在（R6 XOR R7)中所設置的最高有效位的位位置=31 X0R_BIT7=在（R7 XOR R8)中所設置的最高有效位的位位置=28 以上處理得到表示上文示為R1-R8的規則22的示例集合的指紋38的X0R位列表。在 該示例中，X0R位列表是X〇R_BIT_LIST= {29,27,30,29,28,31，28}，並且它用作指紋資料庫 36。因此，在該示例中，實際規則R1-R8可以理解為是構成規則資料庫20的實際分組處理 規則22的集合，並且切割點位52的X0R列表可以理解為是構成指紋資料庫36的規則指紋 38 〇
[0063] 有利地，包括以上X0R位列表的成員的規則指紋38可以只利用五個位來編碼。即， 利用5位規則指紋38來表示32位規則22。即使規則22是例如IPv6地址掩碼，仍可將指 紋38編碼為7位值。因此，與規則資料庫20相比，用於指紋導出的基於X0R的切割點位方 法得到指紋資料庫36的顯著壓縮。
[0064] 在構造等效於由 X0R_BIT_LIST= {xor_bitl=29，xor_bit2=27，xor_bit 3=3〇， xor_bit4=29, xor_bit5=28, xor_bit6=31, xor_bit7=28}所表不的指紋資料庫 36 的表不 的搜索結構的示例方法中，處理如此開始： -找到X0R列表中的最大數字，並利用該數字作為第一切割點一這裡，最大數字=31， 並且它用作搜索樹結構中的第一切割點； -以上第一切割點的使用得到具有低於31的切割點節點的以下條目的樹的左邊： {29，27，30，29，28}; -相應地，樹的右邊具有條目：{28}。
[0065] 圖9中示出對應的示例搜索結構40,其中可見例如對應於xor_bit6=31的節點 70-1。現在，取決於該切割點位52的1或0二進位值，搜索將在所示樹結構中對於對應於 xor_bit7=28的節點70的右側子集合向右往下進行，或者對於對應於xor_bitl=29、xor_ bit2=27、xor_bit3=30、xor_bit4=29和xor_bit5=28的節點70的左側子集合向左往下進 行。
[0066] 為了選擇搜索結構40中的子節點70的切割點，選擇每個節點70的左邊和右邊的 最大X0R位，並利用這作為切割點。圖10示出根據該方法的搜索結構40的進一步發展。圖 11示出通過增加進一步子節點70而獲得的最終搜索結構40。
[0067] 所得搜索結構40用作指紋資料庫36的壓縮版本以便準備存儲在第一存儲器34 中。基於按照所評估的分組密鑰18的特徵位50的二進位值的函數在搜索結構40中從母 節點70遍歷到子節點70,分組處理引擎60標識可能匹配的規則22。在這種指紋資料庫處 理的一個示例中，假設利用如下分組密鑰18呈現分組處理引擎60 :分組密鑰=01001000 00101101 11001100 01010100。
[0068] 按照X0R列表-{29，27，30，29，28，31，28}，分組處理引擎60從分組密鑰18 提取以下位：BIT_29=0, BIT_27=1，BIT_30=1，BIT_29=0, BIT_28=0, BIT_31=0, BIT_28=0。分 組處理引擎60在如圖11所示的搜索結構40中從根節點70-1開始。如果分組密鑰18的 位31是1，那麼來自根節點70的處理將向右往下進行，並且如果分組密鑰18的位31是0， 那麼來自根節點70的處理將向左往下進行。因此，分組密鑰18的位31是將在遍歷搜索結 構40中使用的分組密鑰18的第一特徵位50。
[0069] 在該示例中，分組密鑰18的位31是0,所以分組處理引擎60在搜索結構40中向 左往下遍歷至子節點70-3,子節點70-3指示應當審查分組密鑰18的位30。因此，分組密 鑰18的位30表示將在遍歷搜索結構40中使用的它的下一個特徵位50。由於分組密鑰18 的位30是1，所以分組處理引擎60向下遍歷到右邊，從而到達子節點70-4,它對應於X0R_ BIT4。
[0070] 此時，應注意，分組處理引擎60記住在遍歷搜索結構40期間所訪問的每個節點 70,從而在支持查找處理中提供到上一個(或多個）節點70的退回。
[0071] 繼續該示例和節點70-4,分組處理引擎60評估分組處理密鑰18的位29是將審查 的下一個特徵位50。由於位29是0,並且也因為節點70-4沒有左子節點，所以節點70-4 是繼續到左邊的最終節點。該算法要求，當搜索到達終止節點時，目標規則的對應位(在搜 索結構40中的節點70上指定)必須是1 ;否則需要在搜索結構上回溯。回溯可以潛在地追 溯到搜索結構中的多個級，直到滿足所述要求。現在，搜索回溯到節點70-3。在審查目標規 則的第30個位(它是1)之後，指紋處理算法預測節點70-3 (規則R4)是唯一的可能匹配。
[0072] 因此，分組處理引擎60從第二存儲器44獲取R4,並將它與分組密鑰18進行比較， 從而基於該比較斷言規則命中。
[0073] 現在，考慮"範圍匹配"問題的示例解決方案，其中利用給定分組密鑰18的指 紋資料庫處理來標識規則資料庫20中包括一個或多個可能匹配的規則22的分組處理 規則22的子集。考慮IPv4地址作為一個示例。諸如192. 168. 1. 0/32的地址要求精確 匹配。將前綴長度變為較小值(如28)，那麼192. 168. 1. 0/28表示從192. 168. 1. 0/32到 192. 168. 1. 255/32的範圍。考慮若干個地址或地址範圍（它們可能不能在像這樣的真實世 界中使用）：〇·〇·〇· 80/32，[0·0·0· 80 -0·0·0· 84]，[0·0·0· 82 -0·0·0· 86]，[0·0·0· ΙΟ. 0.3. 255]， [0.0. 0.1 - 0.0. 255. 255]。 這裡為 了簡化標記， 通過並置到單個數字中來轉 化這些四個八位組的地址。例如，0. 0. 255. 255是0x00. 00. FF. FF，並且OxOOOOFFFF是十 進位數65535。這些示例範圍可編寫為數字對[80，80]、[80，84]、[82，90]、[1，1023]、 [1-65535]，並且在一個或多個實施例中，分組處理引擎60配置成確保這些範圍不具有任 何局部重疊。例如，在就在上文示出的範圍集合中，在[80，84]和[82，90]之間存在局部 重疊，但是兩者都沒有完全包含在另一個中。
[0074] 在該示例情形中，分組處理引擎60配置成通過創建不具有重疊範圍的等效範圍 集合來消除規則範圍中的局部重疊。對於該示例情形，這種處理將規則資料庫20中的規 則 22 的邏輯範圍創建為[1，79]、[80，80]、[81，81]、[82，84]、[85，90]、[91，1023]、 [1024，65535]。這些是非重疊範圍。其中，在該處理之前，一些範圍被原始範圍中的多個範 圍包含。例如，原始[1，1023]和[1，65535]包含[1，79]。該信息存儲在這些經過處理 的範圍的旁邊，以使得當預測匹配是[1，79]時，可以檢索原始[1，1023]和[1，65535]。 在需要排序的情況下，分組處理引擎60配置成在每個範圍的下端的基礎上將這些非重疊 範圍排序。剛剛上述範圍就已經按該順序排序。
[0075] 保留在第二存儲器44中的規則資料庫20的對應排列為例如： -Rl- 1, 79 -R2- 80, 80 -R3- 81, 81 -R4- 82, 84 -R5- 85, 90 -R6- 91, 1023 -R7- 1024, 65535 作為該預處理的一部分，分組處理引擎60基於以下關聯創建對應的規則指紋38 : -R0- 0 (這裡插入零虛擬規則以在指紋處理中包含R1) -Rl- 1 -R2- 80 -R3- 81 -R4- 82 -R5- 85 -R6- 91 -R7- 1024 在生成規則指紋38之後，分組處理引擎60形成對應的搜索結構40,例如如圖9-11的 示例中所示。在搜索結構40基於非重疊範圍的情況下，分組處理引擎60預測可能匹配的 規則22所在的範圍，並且分組處理引擎60獲取該範圍的對應規則22以便對照示例分組密 鑰18進行比較。
[0076] -個或多個其它實施例基於LPM查找。在一個示例情形中，利用0來延伸前綴。只 需考慮一個前綴被另一個前綴覆蓋(前者具有比後者短的前綴長度）的情形。注意，較短前 綴將具有比較長前綴小的數值，並且可以利用該屬性一即，如果分組處理引擎60預測較長 前綴為可能匹配的規則22,那麼它可以獲取被該較長前綴所覆蓋的所有規則22,以使得所 有這些規則22都可用於對照所評估的分組密鑰18進行比較匹配。
[0077] 在IPv4地址的示例情形中：

【權利要求】
1. 一種在網絡節點（12)中的分組分類的方法（800)，包括： 獲得對應於由所述網絡節點（12)所接收的數據分組（16)的分組密鑰（18); 通過將所述分組密鑰（18)的特徵位（50)與用作包括分組處理規則（22)的集合的規則 資料庫（20 )的壓縮表示的指紋資料庫（36 )中的規則指紋（38 )進行比較來標識（806 )是所 述分組密鑰（18)的可能匹配的一個或多個分組處理規則（22)，所述規則指紋（38)包括與 所述分組處理規則（22)中作為區分它們的所述規則或子集的搜索切割點操作的位位置對 應的切割點位（52)，並且其中所述分組密鑰（18)的所述特徵位（50)佔據對應於所述切割 點位（52)的位位置； 從所述規則資料庫獲取（808)所述標識的一個或多個分組處理規則（22); 將所述分組密鑰（18)與所述獲取的一個或多個規則（22)進行比較（810);以及 取決於所述分組密鑰（18)是否與所述獲取的一個或多個規則（22)中的任何規則匹配 來指示（812)規則命中或未命中。
2. 如權利要求1所述的方法（800)，還包括：在內部或其它低等待時間存儲器（34)中 存取所述指紋資料庫（36);以及在外部或其它高等待時間存儲器（44)中存取所述規則數據 庫（20 )，其中術語"低等待時間"和"高等待時間"是相對於彼此而言的。
3. 如權利要求2所述的方法（800)，其中標識（806)是所述分組密鑰（18)的可能匹配 的所述一個或多個分組處理規則（22 )包括數字處理器（32 )評估保留在所述內部或低等待 時間存儲器（34)中的所述指紋資料庫（36)，並且其中獲取（808)所述標識的一個或多個規 則（22)包括所述數字處理器（32)從保留在所述外部或高等待時間存儲器（44)中的所述規 則資料庫（20 )直接或間接地檢索所述標識的一個或多個規則（22 )。
4. 如前述任一權利要求所述的方法（800)，還包括：按照所述指紋資料庫（36)的所述 切割點位（52)的函數定義搜索結構（40)，並按照所述分組密鑰（18)的所述特徵位（50)的 函數遍歷所述搜索結構（40)，以便標識是所述分組密鑰（18)的可能匹配的所述一個或多 個分組處理規則（22)。
5. 如權利要求4所述的方法（800)，還包括將所述搜索結構（40)作為二元樹、N元樹 或作為直接索引結構來實現。
6. 如前述任一權利要求所述的方法（800)，其中標識（806)是所述分組密鑰（18)的可 能匹配的所述一個或多個分組處理規則（22)包括：將單個分組處理規則（22)標識為所述 分組密鑰（18)的唯一可能匹配，或者標識所述規則資料庫（20)中表示所述分組密鑰（18) 的可能匹配的所述分組處理規則（22)的子集或範圍。
7. 如前述任一權利要求所述的方法（800)，還包括：出於將給定分組（16)分類的目 的，只為了檢索所述標識的一個或多個分組處理規則（22)而存取所述規則資料庫（20)。
8. 如前述任一權利要求所述的方法（800)，其中所述指紋資料庫（36)基於所述方法 (800)提供分組密鑰（18)與所述規則資料庫（20)中的相應的各個規則（22)之間的精確匹 配，所述方法（800 )包括通過以下步驟預處理（802 )所述規則資料庫（20 )以獲得所述指紋 資料庫（36): 在邏輯上按照二進位順序將所述規則資料庫（20)中的所述分組處理規則（22)排序； 獲得通過對按照所述二進位順序採取的所述分組處理規則（22)的配對運用異或操作 而產生的最高有效位的位位置，其中這些位位置是所述切割點位（52);以及 基於根據按照降序或升序順序採取的所述切割點位（52)對所述分組處理規則（22)的 集合進行劃分和進一步細分，形成對應於所述切割點位（52)的列表的搜索結構（40)，所述 搜索結構（40 )包含所述指紋資料庫（36 )。
9. 如權利要求8所述的方法（800)，其中從所述規則資料庫（20)獲取（808)所述標識 的一個或多個分組處理規則（22 )包括從所述規則資料庫（20 )檢索單個規則（22 )以便對於 所述分組密鑰（18)進行比較匹配。
10. 如權利要求1-7中任一權利要求所述的方法（800)，其中所述指紋資料庫（36)基 於所述方法（800)提供分組密鑰（18)與所述規則資料庫（20)中的各個規則（22)的相應範 圍之間的範圍匹配，所述方法（800)包括通過以下步驟預處理（802)所述規則資料庫（20) 以獲得所述指紋資料庫（36): 將所述分組處理規則（22)按序排到非重疊範圍中，其中所述非重疊範圍的下端在邏輯 上按照升序順序排列； 通過在邏輯上對每個非重疊範圍的下端執行異或操作來生成規則指紋（38 );以及 形成對應於所述規則指紋（38)的搜索結構（40)，其中所述搜索結構中的每個節點對 應於所述非重疊範圍之一。
11. 如權利要求10所述的方法（800)，其中從所述規則資料庫（20)獲取所述標識的 一個或多個分組處理規則（22)包括從所述非重疊範圍中的相應非重疊範圍檢索多個規則 (22)，以便對於所述分組密鑰（18)進行所述檢索的多個規則（22)的各個規則的比較匹配。
12. 如權利要求1-7中任一權利要求所述的方法（800)，其中所述指紋資料庫（36)基 於具有重疊前綴的規則（22)的範圍，並且其中所述方法（800)還包括預處理（802)所述規 則資料庫（20)以便結合對應於與所述重疊前綴相關聯的所述一個或多個規則（22)的索引 值存儲規則（22)，並且其中標識是所述分組密鑰（18)的可能匹配的所述一個或多個分組 處理規則（22)包括執行最長前綴匹配，並且其中檢索所述標識的一個或多個分組處理規則 (22)包括對包含所述規則資料庫（20)的存儲器（44)進行一次存取，以便檢索與所述最長 前綴匹配相關聯的所述規則（22)以及對應於與所述重疊前綴相關聯的所述一個或多個規 則（22)的所述一個或多個索引值。
13. 如權利要求1-7中任一權利要求所述的方法（800)，其中所述指紋資料庫（36)基 於具有重疊前綴的規則（22)的範圍，並且其中所述方法（800)還包括將對應於與所述重疊 前綴相關聯的所述一個或多個規則（22)的那些索引值存儲在表示所述指紋資料庫（36)的 搜索結構（40)中，並且其中標識是所述分組密鑰（18)的可能匹配的所述一個或多個分組 處理規則（22)包括關於所述搜索結構（40)執行最長前綴匹配，這包括響應於在所述搜索 結構（40)中遍歷超過存在可能的匹配規則（22)的子節點（70)，利用所述索引值來從所述 子節點（70)回溯到表示可能匹配的規則（22)的對應母節點（70)。
14. 如權利要求1-7中任一權利要求所述的方法（800)，其中所述指紋資料庫（36)基 於具有重疊前綴的規則（22)的範圍，並且其中所述方法（800)還包括將對應於與所述重疊 前綴相關聯的所述一個或多個規則（22)的那些索引值存儲在表示所述指紋資料庫（36)的 搜索結構（40)中，並且其中標識是所述分組密鑰（18)的可能匹配的所述一個或多個分組 處理規則（22)包括關於所述搜索結構（40)執行最長前綴匹配，以標識將從所述規則數據 庫（20)獲取以便關於所述分組密鑰（18)進行比較匹配的規則（22)的範圍。
15. -種網絡節點（12)，配置成基於分組分類在分組網絡（10)中路由或交換分組 (16)，所述網絡節點（12)包括： 一個或多個通信接口（30)，配置成接收輸入分組（16)以進行路由或交換處理，並根據 依據由所述網絡節點（12)所執行的分組分類處理關於所述流入分組（16)所做的交換或路 由決定而發送輸出分組（16);以及 一個或多個處理電路（32)，基於配置成執行以下動作而配置成執行所述分組分類處 理： 獲得對應於由所述網絡節點（12)所接收的數據分組（16)的分組密鑰（18); 通過將所述分組密鑰（18)的特徵位（50)與用作包括分組處理規則（22)的集合的規則 資料庫（20 )的壓縮表示的指紋資料庫（36 )中的規則指紋（38 )進行比較來標識是所述分組 密鑰（18)的可能匹配的一個或多個分組處理規則（22)，所述規則指紋（38)包括與所述分 組處理規則（22)中作為區分它們的各個規則（22)或子集操作的搜索切割點操作的位位置 對應的切割點位（52)，並且其中所述分組密鑰（18)的所述特徵位（50)佔據對應於所述切 割點位（52)的位位置； 從所述規則資料庫（20)獲取所述標識的一個或多個分組處理規則（22); 將所述分組密鑰（18)與所述獲取的一個或多個規則（22)進行比較；以及 取決於所述分組密鑰（18)是否與所述獲取的一個或多個規則（22)中的任何規則匹配 來指示規則命中或未命中。
16. 如權利要求15所述的網絡節點（12)，其中所述一個或多個處理電路（32)配置成 基於根據與給定接收分組（16)的分組密鑰（18)匹配的所述獲取的分組規則（22)處理所述 給定接收分組（16)來對所述給定接收分組（16)進行分類以作為對應的輸出分組（16)進行 交換或路由。
17. 如權利要求15或16所述的網絡節點（12)，其中所述網絡節點（12)包括數字處理 電路（32)，其配置成執行可能與所述分組密鑰（18)匹配的所述一個或多個分組處理規則 (22)的所述標識，並執行所述獲取的一個或多個規則（22)與所述分組密鑰（18)的所述比 較，並且其中所述網絡節點（12)還包括 ： 用於存儲所述指紋資料庫（36)的第一存儲器（34)，所述第一存儲器（34)位於所述數 字處理電路（32)的內部或者以其它方式對於所述數字處理電路（32)可以第一等待時間進 行存取；以及 用於存儲所述規則資料庫（20)的第二存儲器（44)，所述第二存儲器（44)位於所述數 字處理電路（32 )的外部或者以其它方式對於所述數字處理電路（32 )可以與所述第一等待 時間相比較高的所述第二等待時間進行存取。
18. 如權利要求17所述的網絡節點（12)，其中所述數字處理電路（32)配置成從所述 第二存儲器（44)獲取所述標識的一個或多個分組處理規則（22)。
19. 如權利要求15-18中任一權利要求所述的網絡節點（12)，其中所述一個或多個處 理電路（32)配置成按照所述指紋資料庫（36)的所述切割點位（52)的函數定義搜索結構 (40)，並按照所述分組密鑰（18)的所述特徵位（50)的函數遍歷所述搜索結構（40)，以便標 識是所述分組密鑰（18)的可能匹配的所述一個或多個分組處理規則（22)。
20. 如權利要求15-19中任一權利要求所述的網絡節點（12)，其中所述一個或多個處 理電路（32)基於配置成執行以下動作而配置成標識是所述分組密鑰（18)的可能匹配的所 述一個或多個分組處理規則（22):將單個分組處理規則（22)標識為所述分組密鑰（18)的 唯一可能匹配，或者標識所述規則資料庫（20)中表示所述分組密鑰（18)的可能匹配的所 述分組處理規則（22)的子集或範圍。
21. 如權利要求15-20中任一權利要求所述的網絡節點（12)，其特徵進一步在於，出 於對給定接收分組（16)進行分類的目的，所述一個或多個處理電路（32)配置成只為了檢 索所述標識的一個或多個分組處理規則（22 )而存取所述規則資料庫（20 )。
22. 如權利要求15-21中任一權利要求所述的網絡節點（12)，其中所述指紋資料庫 (36 )配置成基於所述一個或多個處理電路（32 )提供分組密鑰（18 )與所述規則資料庫（20 ) 中的相應的各個規則（22)之間的精確匹配，所述一個或多個處理電路（32)基於配置成執 行以下步驟而配置成預處理用於隨後在分組分類處理中使用的所述規則資料庫（20)以獲 得所述指紋資料庫（36) : 在邏輯上按照二進位順序將所述規則資料庫（20)中的所述分組處理規則（22)排序； 獲得通過對按照所述二進位順序採取的所述分組處理規則（22)的配對運用異或操作 而產生的最高有效位的位位置，其中這些位位置是所述切割點位（52);以及 基於根據按照降序或升序順序採取的所述切割點位（52)對所述分組處理規則（22)的 集合進行劃分和進一步細分，形成對應於所述切割點位（52)的列表的搜索結構（40)。
23. 如權利要求22所述的網絡節點（12)，其中所述一個或多個處理電路（32)基於配 置成從所述規則資料庫（20 )檢索單個規則（22 )而配置成從所述規則資料庫（20 )獲取所述 標識的一個或多個分組處理規則（22)，以便對於所述分組密鑰（18)進行比較匹配。
24. 如權利要求15-21中任一權利要求所述的網絡節點（12)，其中所述指紋資料庫 (36)配置成基於所述一個或多個處理電路（32)提供分組密鑰（18)與所述規則資料庫（20) 中的各個規則（22)的相應範圍之間的範圍匹配，所述一個或多個處理電路（32)基於配置 成執行以下步驟而配置成預處理所述規則資料庫（20)以獲得所述指紋資料庫（36): 將所述分組處理規則（22)按序排到非重疊範圍中； 生成對應於每個非重疊範圍的下端的規則指紋（38);以及 形成對應於所述規則指紋（38)的搜索結構（40)。
25. 如權利要求24所述的網絡節點（12)，其中所述一個或多個處理電路（32)基於配 置成從所述非重疊範圍中的相應非重疊範圍檢索多個規則（22)而配置成從所述規則數據 庫（20)獲取所述標識的一個或多個分組處理規則（22)，以便對於所述分組密鑰（18)進行 所述檢索的多個規則（22 )中的各個規則的比較匹配。
26. 如權利要求15-21中任一權利要求所述的網絡節點（12)，其中所述指紋資料庫 (36)基於具有重疊前綴的規則（22)的範圍，並且其中所述一個或多個處理電路（32)配置 成：預處理所述規則資料庫（20)以便結合對應於與所述重疊前綴相關聯的所述一個或多 個規則（22)的索引值存儲規則（22);並基於配置成執行最長前綴匹配而標識是所述分組密 鑰（18)的可能匹配的所述一個或多個分組處理規則（22);並通過對包含所述規則資料庫 (20 )的存儲器（44)進行一次存取以檢索與所述最長前綴匹配相關聯的所述規則（22 )以及 對應於與所述重疊前綴相關聯的所述一個或多個規則（22)的所述一個或多個索引值來檢 索所述標識的一個或多個分組處理規則（22)。
27. 如權利要求15-21中任一權利要求所述的網絡節點（12)，其中所述指紋資料庫 (36)基於具有重疊前綴的規則（22)的範圍，並且其中所述一個或多個處理電路（32)配置 成：將對應於與所述重疊前綴相關聯的所述一個或多個規則（22)的那些索引值存儲在表 示所述指紋資料庫（36)的搜索結構（40)中；並通過關於所述搜索結構（40)執行最長前綴 匹配來標識是所述分組密鑰（18)的可能匹配的所述一個或多個分組處理規則（22)，這包 括響應於在所述搜索結構（40)中遍歷超過存在可能的匹配規則（22)的子節點（60)，利用 所述索引值來從所述子節點（60)回溯到表示可能匹配的規則（22)的對應母節點（60)。
28. 如權利要求15-21中任一權利要求所述的網絡節點（12)，所述指紋資料庫（36)基 於具有重疊前綴的規則（22)的範圍，並且其中所述一個或多個處理電路（32)配置成將對 應於與所述重疊前綴相關聯的所述一個或多個規則（22)的那些索引值存儲在表示所述指 紋資料庫（36)的搜索結構（40)中，並且其中標識是所述分組密鑰（18)的可能匹配的所述 一個或多個分組處理規則（22)包括關於所述搜索結構（40)執行最長前綴匹配，以標識將 從所述規則資料庫（20)獲取以便關於所述分組密鑰（18)進行比較匹配的規則（22)的範 圍。
【文檔編號】H04L29/06GK104303482SQ201380024104
【公開日】2015年1月21日 申請日期:2013年5月2日 優先權日:2012年5月8日
【發明者】P.阿南德, R.拉克什米肯桑, 陳孫登, 許寧 申請人:瑞典愛立信有限公司