TW201445921A - 用於在網路交換機中利用集中式記憶體池的表搜索的裝置和方法 - Google Patents

Abstract

一種網路交換機包括：在第一處理器核中的多個分組處理單元。介面模組被連接到分組處理單元。介面模組支援統一的表搜索請求以及統一的表搜索回應介面。公共記憶體池被連接到介面模組。公共記憶體池包括能被配置以支援多個並行表搜索請求的、各種記憶體類型。

Description

用於在網路交換機中利用集中式記憶體池的表搜索的裝置和方法 【相關申請的交叉引用】

本申請要求2013年4月30日提交的美國臨時申請案第61/817,810號的優先權，通過引用將其全文引用於此。

本申請涉及網路環境中的通信。更具體地，本發明涉及在高速網路處理單元中執行表搜索。

在網路交換單元中的表搜索的示例包括：用於媒體接入控制(MAC)位址查找的雜湊操作，用於網際網路協定(IP)路由的最長首碼匹配(LPM)，用於接入控制列表(ACL)的萬用字元匹配(wild-card matching)以及用於控制資料的直接存儲訪問。

在市場上已經出現軟體定義網路(SDN)。SDN允許通過對低層功能性進行抽象來管理網路。這是通過將執行關於業務發往何處的判決的系統(控制平面)從將業務轉發到選定的目的地的低層系統(資料平面)去耦合來實現的。

表搜索如軟體所見是處於靈活控制路徑的核心。交換機執行對每個進入分組的查找，並且執行由搜索命中結果指示的動作或者由表搜索失敗指示的默認動作。

由於表搜索對於SDN是至關重要的，將期望提供用於執行這類搜索的技術。

網路交換機包括在第一處理器核中的分組處理單元。介面模組被連接到分組處理單元。介面模組支援統一的表搜索請求介面以及統一的表搜索回應介面。公共記憶體池被連接到介面模組。公共記憶體池包括可被配置為支援多個並行表搜索請求的各種記憶體類型。

100‧‧‧網路交換機

101‧‧‧業務管理器

102_1‧‧‧分組處理單元

102_N‧‧‧分組處理單元

104‧‧‧分組修改器

106_1‧‧‧核

106_N‧‧‧核

108‧‧‧介面模組

110‧‧‧公共記憶體池

200_1‧‧‧記憶體搜索邏輯介面

200_N‧‧‧記憶體搜索邏輯介面

202_1‧‧‧記憶體類型1

202_N‧‧‧記憶體類型N

300‧‧‧介面單元

302‧‧‧LPM引擎

304‧‧‧哈希引擎

306‧‧‧直接引擎

308‧‧‧TCAM引擎

310‧‧‧片上網路

312_0‧‧‧SRAM池_0

312_N‧‧‧SRAM池_N

314‧‧‧TCAM

316‧‧‧片上網路

500‧‧‧通用搜尋引擎表

502‧‧‧搜索鍵值部分

504‧‧‧控制資料部分

506_1‧‧‧搜索鍵值參數_1

506_N‧‧‧搜索鍵值參數_N

508_1‧‧‧資料參數_1

508_N‧‧‧資料參數_N

600‧‧‧直接表存取的表

700‧‧‧雜湊搜索的表

800‧‧‧TCAM搜索的表

900‧‧‧解碼器

如在附圖中所示，前述內容將從以下對於本發明的示例性實施方式的更具體的描述中更明顯，在附圖中類似的參考標號在不同的視圖中指代相同的部件。

第一圖圖示根據本發明實施方式所配置的網路交換機。

第二圖圖示根據本發明實施方式所利用介面模組和公共記憶體池。

第三圖圖示根據本發明實施方式所利用的示例性介面模組和公共記憶體池。

第四圖圖示根據本發明的實施方式所利用的表搜索配置資訊。

第五圖圖示與本發明的實施方式關聯的通用表搜索參數。

第六圖圖示與本發明的實施方式關聯的直接表訪問搜索參數。

第七圖圖示與本發明的實施方式關聯的雜湊搜索參數。

第八圖圖示與本發明的實施方式關聯的TCAM搜索參數。

第九圖圖示根據本發明的實施方式所利用的TCAM架構。

第一圖示出了根據本發明實施方式所配置的網路交換機100。網路交換機100包括業務管理器101以及一個或多個分組處理單元102_1至102_N，其向分組修改器104分發處理的分組。這些組件形成核106_1。每個核可以存在多個實例，諸如106_1至106_N。介面模組108提供到公共記憶體池110的介面。正如從以下討論中將理解的，該架構支援用於多核網路交換機的集中式表搜尋引擎。每個核106可以利用相同的介面模組108和公共記憶體池110。

該架構通過統一的請求和結果介面支援多個平行表搜索。公共記憶體池110支援對於記憶體資源的有效使用。正如以下所討論的，該架構還靈活地生成搜索鍵值，以利用不同尺寸的搜索鍵值來執行不同類型的表搜索。還可以支援混合表搜索。

第二圖圖示了介面模組108包括一組記憶體搜索邏輯介面200_1至200_N。每個記憶體搜索邏輯介面200遵循統一的表請求介面格式和統一的表回應介面格式。每個記憶體搜索邏輯介面200進行獨立請求。因此，公共記憶體池110處理大量並行請求。

公共記憶體池110包括各種記憶體類型202_1至202_N。記憶體類型可以包括直接存取記憶體(例如，靜態隨機存取記憶體(SRAM)以及三態內容可定址記憶體(TCAM)。TCAM支援對於存儲的資料字中一個或多個比特的“不關注”或“X”態。這增加了靈活性，但是增加的靈活性是以超過兩態記憶體的附加成本而獲得的，因為TCAM編碼三個可能的狀態而不是兩個。TCAM經常被用於最長首碼匹配和存取控制清單搜索。TCAM是昂貴的交換組件。正如以下所討論的，本發明的實施方式靈活地利用了TCAM資源。

第三圖圖示介面模組108和公共記憶體池110的實施方式。介面模組108包括介面單元300以接收表搜索請求。表搜索請求指向包括邏輯以實施特定的表搜索請求的引擎。引擎可以包括最長首碼 匹配(LPM)引擎302，雜湊搜尋引擎304，直接記憶體搜尋引擎306以及TCAM引擎308。本發明的一個實施方式包括每個引擎的多個實例。每個引擎的輸出指向一個片上網路310。片上網路310被實施為用來提供如由表請求介面所指定的、對公共記憶體池110中的所有記憶體資源的訪問。

在該示例中，公共記憶體池110包括一組SRAM資源312_0至312_N以及TCAM 314。如下所討論的，在TCAM 314中命中引起對用於對應控制資訊的專用SRAM資源的訪問。在記憶體中表查找的結果被導向片上網路316，該片上網路316將結果路由到介面單元300。

第四圖圖示可以根據本發明的實施方式使用的配置表。配置表在介面單元300中建立一組配置文檔。配置表建立如何形成搜索鍵值，執行何種類型的搜索以及利用那個處理引擎。在該示例中，配置表具有四列以及八行。圖中圖示了用於一列的比特欄位。第一欄位是8比特的“table_id”(表標識)，其用於作為表的行中的索引。由於在該示例中存在八行，存在對於八個不同搜索配置文檔的訪問。每個配置文檔包含多至四個搜索命令；每次搜索可以是相同的或者不同的表。

下一欄位是48比特的“key_byte_mask”(鍵值位元組遮罩)欄位。該欄位指定搜索鍵值的構造。也即，遮罩說明來自輸入統一表請求介面的哪些比特需要被解釋為特定的搜索命令。例如，用於層2橋接器的目的地位址將設定與用於雜湊查找的目的地MAC位址和橋接器域的位置對應的位元組點陣圖。同時，在一個分別的搜索命令中，源位址查找可以利用被設定用於源MAC位址和相同的橋接器域的搜索鍵值位元組遮罩而被執行。形成具有位元組點陣圖的搜索鍵值的靈活性不僅簡化了控制路徑設計，而且還縮小了硬體，因為不需要額外的硬體來針對兩次查找來兩次提取相同的橋接器域。而且，軟體可以指定對於特定搜索請求的優先順序。例如， 在橋接環境中，用戶可以設置源位址查找作為較低優先順序，以便使得搜尋引擎僅在存在空閒頻寬時執行這種搜索，因為源位址通常能夠從將來的分組中匯出。這是示出搜尋引擎方案的應用以及優勢的一個示例。還應該理解，本發明提供協議獨立的搜索鍵值，這有利於靈活性。

“ecmp_en”和“ecmp_hash_byte_start”欄位是專用於LPM搜索的。“rslt_qw_start”欄位指定用於向其發送結果的邏輯通信通道的起點，而“rslt_qw_inc”欄位指定向其發送結果的通道遞增數目。例如，單個搜索命令的結果可以是256比特寬，被劃分為四個通道，每個通道是64比特寬。用於整個搜索配置文檔的結果能夠多至1024比特，因此其可以採用多個迴圈週期以返回所有結果。每個搜索命令在0-15之間配置“rslt_qw_start”並且在0-3之間配置“result_qw_inc”，以指定將結果佈置在16雙字中的何處。

“regret_table”欄位是服務品質參數；它指定當搜尋引擎被擁塞，哪個要求查詢的重新部署。“age_en”欄位是表條目逐出參數，它有助於用於調試的目的。“hash_way_cnt”欄位支持具體的雜湊搜索。“eng_id”欄位指定多個處理引擎中的一個處理引擎。

第五圖圖示根據本發明實施方式所配置的通用搜尋引擎表500。搜尋引擎表500指定根據第四圖的配置資訊處理的搜索請求。在一個實施方式中，搜尋引擎表500包括搜索鍵值部分502以及控制資料部分504。搜索鍵值部分502具有各自的搜索鍵值參數506_1至506_N。搜索鍵值參數可以從鍵值尺寸、雜湊函數配置、記憶體塊配置等等中選擇。因此，本發明支持不同的指定的鍵值尺寸。雜湊函數配置參數允許指定映射到記憶體的不同的方式。記憶體塊配置是物理記憶體資源的範圍。

類似地，控制資料部分504具有各自的資料參數508_1至508_N。資料參數可以從資料尺寸、資料記憶體塊配置等等中選擇。因此，本發明支援不同的資料尺寸結果。記憶體塊配置允許對記憶 體資源的抽象引用。

因此，鍵值尺寸和控制資料都能夠被配置以不同的尺寸；除了TCAM表格的所有表格均被配置為靈活地基於準確的應用用途被存儲在集中式SRAM池的某個部分中。

通用搜尋引擎表500支持各種搜索查詢。第六圖圖示被配置用於直接表存取的表600。搜索鍵值部分502是保留的。控制資料部分包括資料尺寸、池、row_blk_start和row_blk_cnt參數。這些參數可以與SRAM池結合使用，該SRAM池具有16MB的SRAM被劃分為8個相同的池。每個池具有2MB的記憶體。可以使用支援每個迴圈週期1讀取和1讀/寫操作的雙埠記憶體。物理上，池中的所有SRAM塊被組織為8塊，每個塊256比特寬並且8K行。行塊是在高級表位址和物理記憶體位址之間的中間表示。這允許將記憶體池的邏輯視圖從物理塊選擇中去耦合。每個行塊表示1K行。

SRAM可以被靈活配置以存儲不同的表類型和條目寬度。雜湊表和LPM表查找演算法要求多個記憶體訪問以具有最優的記憶體效率。將SRAM資源劃分為8個分離的池，這允許並行的記憶體訪問以及片上網路尺寸的縮減。

在行塊中分配與SRAM關聯的表，其中每個行塊是1024記憶體行。表條目可以是32比特、64比特、128比特、256比特或者512比特，而物理SRAM的是每個256比特寬。如果條目少於256比特，多個條目駐留在一個SRAM行，其中邏輯表位址的較低比特被用於選擇相同行中多個條目中的一個條目，而邏輯表位址的較高比特被用於選擇記憶體行以及記憶體塊。如果條目是512比特寬，其使用兩個SRAM塊。雙塊條目在其偶數塊中存儲其較低256比特，並且在緊鄰塊的相同行中存儲其較高256比特。儘管每個塊每個時鐘迴圈週期具有最大兩次訪問次數，但是多個表格可以駐留在相同塊，以允許以時域複用方式訪問每個表格。典型地，取決於分組解析結果，來自相同源的不同分組可以要求不同的查找；由此， 多個表被配置在相同記憶體塊中，但是如果通道提供大表容量，則針對不同分組來訪問該多個表。最小表尺寸是1024條目，而最大表可以佔據所有SRAM資源。通過每個具體網路應用的不同要求，搜索表的尺寸可以與搜索表的數目相權衡。

第七圖圖示被配置用於雜湊搜索的表700。控制資料部分504是保留的。搜索鍵值部分具有以下參數：key_size、data_size、dual_tile_entry、way_bmp、bucket_depth、hash_func以及row_blk_start。在該示例中，搜尋引擎雜湊函數能夠從七種不同尺寸中選擇；存在四種不同的雜湊函數以供選擇。每個方式被固定到一個對應的池；控制資料與一個鍵值相伴。

第八圖圖示被配置用於TCAM搜索的表800。控制資料部分504具有鍵值尺寸參數、資料庫起始參數以及資料庫結束參數。控制資料部分具有資料尺寸參數。在一個實施方式中，搜索鍵值部分已經允許64、128、192和384比特的尺寸。在一個實施方式中，資料尺寸可以是32、64、128或256比特。

所有TCAM查找都通過片上網路被路由到共用的TCAM池314，該共用的TCAM池314與用於存儲對應控制資料的片上SRAM相關聯。控制資料通過另一片上網路傳遞，並且路由回各自的表結果介面。

第九圖圖示了在本發明的實施方式中，TCAM引擎308包括16個引擎Engine_0至Engine_15。TCAM 314被劃分為16個資料庫DB_0至DB_15。每個資料庫具有一組塊。

每個TCAM資料庫能夠被配置為具有不同的鍵值尺寸，例如，64比特、128比特、192比特或者384比特。TCAM表能夠是一個或多個鄰接的TCAM資料庫。這樣，在一個實施方式中，存在16個不同的TCAM表，每個具有1個資料庫，或者存在具有全部16個資料庫的一個TCAM表。第九圖圖示TCAM 314包括16個資料庫DB_0至DB_15。取決於應用，可以配置多個小尺寸表或者少數 幾個大尺寸TCAM表，從而充分利用硬體上昂貴並且耗電的TCAM記憶體塊。

來自TCAM 314的輸出被施加到解碼器900，解碼器900訪問對應於TCAM命中的SRAM條目。在該實施方式中，SRAM池312包括SRAM組SRAM_0至SRAM_31。

搜尋引擎能夠執行多至16個並行TCAM查找。存在視配置而定的延遲的權衡。在一個極端情況，單個大表佔據所有記憶體空間，但是具有相對大的延遲。多個較小表可能構築於整個記憶體，在這種情況下較小的表具有較小的延遲。

對於每個TCAM資料庫使用專用的SRAM降低了對於TCAM表的存取延遲。該方案使得TCAM表由於其低延遲以及靈活性成為用於各種應用的有吸引力的備選方案。這些應用包括但不限於ACL以及LPM。

所有直接存取表、雜湊表以及LPM表共用集中式片上SRAM池，該片上SRAM池與處理引擎和結果介面通過分離的片上網路進行互連。如果表條目變得陳舊，並且在一段時間內沒有被任何分組命中，則搜尋引擎通過表老化機制通知CPU。

雜湊處理引擎中的每個引擎具有關聯的輸入緩衝器，以用於將多個進入的請求入佇列。當引擎變得被所有請求者過多訂購時，將一些較低優先順序請求丟棄。對進入請求進行優先順序排序的能力允許充分利用空閒頻寬，特別是在封包交換的背景下，其中分組的變化的長度要求對於處理頻寬的過度供給。

處於解釋的目的，前文的描述使用具體術語來提供對於本發明的透徹理解。但是，對於本領域的技術人員將清楚的是，為了實現本發明將不需要具體細節。因此，處於說明和描述的目的來給出前文對於本發明具體實施方式的描述。這些實施方式並不旨在窮盡本發明或者將本發明限制到所公開的精確形式；顯然，根據上述教導，許多修改和變形是可能的。選擇並且描述了實施方式，以便最 好地解釋本發明的原理以及其實際應用，因此它們使得本領域的技術人員能夠最好的利用本發明以及各種實施方式，並且利用適合於所設想的特定用途的各種修改。旨在由後續的權利要求和其等效物來定義本發明的範圍。

100‧‧‧網路交換機

101‧‧‧業務管理器

102_1‧‧‧分組處理單元

102_N‧‧‧分組處理單元

104‧‧‧分組修改器

106_1‧‧‧核

106_N‧‧‧核

108‧‧‧介面模組

110‧‧‧公共記憶體池

Claims (22)

1. 一種網路交換機，包括：在第一處理器核中的多個分組處理單元；連接到所述多個分組處理單元的介面模組，所述介面模組支援統一的表搜索請求介面以及統一的表搜索回應介面；公共記憶體池，連接到所述介面模組，所述公共記憶體池包括能被配置以支援多個並行表搜索請求的、各種記憶體類型。
2. 根據權利要求1所述的網路交換機，進一步包括在第二處理器核中的第二多個分組處理單元，所述第二多個分組處理單元被連接到所述介面模組。
3. 根據權利要求1所述的網路交換機，其中所述介面模組被配置為支援具有不同尺寸的搜索鍵值的不同類型的表搜索。
4. 根據權利要求1所述的網路交換機，其中所述各種記憶體類型包括靜態隨機存取記憶體以及三態內容可定址記憶體。
5. 根據權利要求1所述的網路交換機，其中所述介面模組包括各自的引擎，這些引擎具有用以協調不同的表搜索請求的邏輯。
6. 根據權利要求5所述的網路交換機，其中所述引擎包括最長首碼匹配引擎、雜湊搜尋引擎、直接記憶體搜尋引擎以及三態內容可定址記憶體(TCAM)引擎。
7. 根據權利要求5所述的網路交換機，其中所述介面模組包括根據配置表所配置的介面單元。
8. 根據權利要求7所述的網路交換機，其中所述配置表包括多個列和行，每個行指定搜索配置文檔並且每個列指定用於所述搜索配置文檔的搜索命令。
9. 根據權利要求7所述的網路交換機，其中所述配置表包括表標識欄位，能操作作為所述配置表的行中的索引。
10. 根據權利要求7所述的網路交換機，其中所述配置表包括鍵值位元組遮罩欄位，以指定搜索鍵值的構造。
11. 根據權利要求7所述的網路交換機，其中所述配置表包括最長首碼匹配搜索參數。
12. 根據權利要求7所述的網路交換機，其中所述配置表包括邏輯通信通路參數。
13. 根據權利要求7所述的網路交換機，其中所述配置表包括多個服務品質參數。
14. 根據權利要求7所述的網路交換機，其中所述配置表包括表條目逐出參數。
15. 根據權利要求7所述的網路交換機，其中所述介面模組處理表搜索請求，其中根據配置表的參數來處理所述表搜索請求。
16. 根據權利要求15所述的網路交換機，其中所述表搜索請求包括搜索鍵值部分以及控制資料部分。
17. 根據權利要求16所述的網路交換機，其中所述搜索鍵值部分包括從鍵值尺寸、雜湊函數配置以及記憶體塊配置中選擇的參數。
18. 根據權利要求16所述的網路交換機，其中所述控制資料部分包括從資料尺寸以及資料記憶體塊配置中選擇的參數。
19. 根據權利要求1所述的網路交換機，其中所述公共記憶體池包括多個被劃分為可定址資料庫分段的三態內容可定址記憶體(TCAM)資源。
20. 根據權利要求1所述的網路交換機，其中來自所述TCAM資源的輸出被編碼器處理以訪問對應於TCAM命中的靜態隨機存取記憶體資訊。
21. 根據權利要求1所述的網路交換機，其中所述公共記憶體池交替地被配置用於不同數目的表以及不同的搜索類型。
22. 根據權利要求1所述的網路交換機，其中所述公共記憶體池交替地被配置用於大容量長延遲表以及小容量短延遲表。