一種可編程多級動態(tài)共享查找表裝置

文/陳欽樹 管自新 廖述京

1 引言

5G及后5G時代，各種新業(yè)務(wù)對網(wǎng)絡(luò)帶寬，網(wǎng)絡(luò)時延及網(wǎng)絡(luò)成本等需求千差萬別，所以各種新興業(yè)務(wù)可能會根據(jù)自己的特殊應(yīng)用有自己的通信協(xié)議，這樣要求網(wǎng)絡(luò)中的核心設(shè)備需要支持可編程性。但是現(xiàn)有的實現(xiàn)方案，要么采用網(wǎng)絡(luò)處理器方式來共享查找表要么采用固定流水轉(zhuǎn)發(fā)模式獨占查找表，都不能滿足5G及后5G新業(yè)務(wù)需求。本文提出了一種可編程多級動態(tài)共享的查找表方案，通過軟件編程可以根據(jù)業(yè)務(wù)的需要動態(tài)調(diào)整各個查找表的大小和查找方式，查找關(guān)鍵字等；根據(jù)查找表的規(guī)?？梢赃x擇使用PPU內(nèi)部查找表還是PPU外部查找表多級共享，滿足了5G及后5G新業(yè)務(wù)快速部署，大容量，低延遲，低能耗的需要。

2 可編程業(yè)務(wù)的處理流程

可編程交換機由可編程報文解析模塊，若干個報文處理單元和可編程報文編輯模塊構(gòu)成。報文先進入可編程報文解析模塊進行解析，獲取報文的結(jié)構(gòu)，并將解析結(jié)果放置到報文的描述符總線，送給后續(xù)模塊PPU（Packet Process Unit，報文處理單元）進行處理，每級PPU的結(jié)構(gòu)都是一樣的。每級PPU都是從報文的描述符總線取出對應(yīng)的關(guān)鍵字和查找表配置的關(guān)鍵字進行匹配，如果匹配中了將表格中對應(yīng)條目的內(nèi)容取出來放置到報文的描述符總線，然后交給下一級PPU處理，經(jīng)過n級PPU處理后將描述符和報文的內(nèi)容送給報文編輯模塊進行報文修改，最后根據(jù)描述符總線指示的輸出端口將報文從正確的目的端口轉(zhuǎn)發(fā)出去。

每級PPU內(nèi)部有m張查找表，這些查找表的容量比較小，可以存儲一些表項條目數(shù)比較少的查找表，例如端口屬性表。但是像MAC地址交換表、IP路由表等包含巨大條目數(shù)的查找表就需要存在PPU外部。一般每級PPU支持兩張外部查找表就可以滿足交換業(yè)務(wù)的需求了。不論是PPU內(nèi)部的查找表還是PPU外部的查找表，其查找表的深度和寬度都是可編程配置其大小的。對于在某種特定場景下沒有業(yè)務(wù)使用的查找表，可以配置分配0塊RAM資源，也就是不占用任何RAM的資源，其RAM的資源可以分配給其他的查找表使用。

3 可編程多級動態(tài)共享查找表

可編程多級動態(tài)共享查找表由查找條件判決模塊、查表關(guān)鍵字生成及哈希計算模塊、PPU查找表讀寫控制模塊和查表結(jié)果處理模塊構(gòu)成，各個模塊的功能如下所述。

3.1 查表條件判決模塊

查表條件判決模塊由m個查表判決器組成。每個判決器由i個j位比較器構(gòu)成，每個比較器都能夠執(zhí)行大于，小于，等于和不等于的判斷；每個比較器對應(yīng)一個控制寄存器，該寄存器存儲了比較數(shù)在報文描述符總線的位置，被比較數(shù)是否是立即數(shù)標(biāo)志，如果被比較數(shù)是立即數(shù)，則存放被比較數(shù)的數(shù)值；如果被比較數(shù)不是立即數(shù)，則存放著被比較數(shù)在報文描述符總線的位置。同時還包含了該比較數(shù)據(jù)對應(yīng)的掩碼，在進行比較操作前，被比較數(shù)和比較數(shù)都需要先和掩碼寄存器按比特位進行與操作，然后再執(zhí)行比較運算。最后將i個比較器的判斷結(jié)果和根據(jù)查表判決器指示的地址從描述符取出k個字段合并后查找對應(yīng)的TCAM條目，如果命中給出命中指示。根據(jù)命中指示在發(fā)起對應(yīng)查找表請求，給出所查表是哈希表還是直接表的標(biāo)志，是查PPU內(nèi)部查找表還是PPU外部查找表的指示，同時給查表的編號，用于指示查找哪個查找表。

3.2 查表關(guān)鍵字生成及哈希計算模塊

每個查找表都包含p個配置寄存器，用于指示如何生成查表需要的關(guān)鍵字。每個配置寄存器包含了對應(yīng)關(guān)鍵字一個字節(jié)在報文描述符總線的位置，該字節(jié)有效比特的比特長度。根據(jù)配置寄存器的配置值從報文的描述符總線取出對應(yīng)的關(guān)鍵字每個字節(jié)，然后根據(jù)配置寄存器的順序?qū)拿枋龇偩€提取的字節(jié)合并成一個臨時查表關(guān)鍵字，最后壓縮掉臨時查表關(guān)鍵字內(nèi)部無效的比特生成查表關(guān)鍵字。根據(jù)配置選取對應(yīng)的哈希函數(shù)計算查表關(guān)鍵字的哈希索引。本文支持雙哈希查找，所以對于每個查表關(guān)鍵字同時用兩個不同的哈希函數(shù)計算其對應(yīng)的哈希索引。

3.3 PPU查找表讀寫控制模塊

PPU查找表讀寫控制模塊是整個可編程多查找表共享裝置的核心。其根據(jù)交換機的工作場景通過編程配置靈活改變各個查找表的大小，讓交換機在各種場景下都能夠滿足各類業(yè)務(wù)的需求而又最大限度的利用片內(nèi)RAM的資源。該模塊分為PPU內(nèi)部查找表的讀寫控制和PPU外部查找表的讀寫控制，但是這兩級查找表讀寫控制模塊基本相同。PPU內(nèi)部查找表讀寫控制模塊根據(jù)查找表的類型可以分為哈希表的讀寫控制和直接表的讀寫控制。

當(dāng)PPU內(nèi)部哈希表讀寫控制邏輯接收到的查表請求信號后，根據(jù)請求來源譯碼成哈希表的邏輯表號。PPU內(nèi)部查找表每塊RAM都根據(jù)查表的請求和查表地址查看自己的RAM屬性寄存器，確定查表請求信號和RAM屬性寄存器配置的查找表編號一致后，判斷查表請求對應(yīng)的地址是否落在該RAM所在的查找表的行塊內(nèi)，如果是則發(fā)起讀RAM的請求信號，同時驅(qū)動RAM的地址為查找表的地址，讀出RAM內(nèi)部的數(shù)據(jù)。然后根據(jù)RAM的屬性寄存器配置的邏輯表列塊號將讀出的數(shù)據(jù)放入到結(jié)果寄存器的對應(yīng)位置上。

將查表拼接后的數(shù)據(jù)hash_mux_result根據(jù)哈希表對應(yīng)屬性寄存器中的表字節(jié)寬度配置分割hash_mux_result，最后得到多個hash_result數(shù)據(jù)。根據(jù)哈希表屬性寄存器的配置查找關(guān)鍵字的比特寬度從分割出來的每個數(shù)據(jù)hash_result數(shù)據(jù)取出對應(yīng)的比特內(nèi)容和查表關(guān)鍵進行比較。如果配置的數(shù)據(jù)和查表關(guān)鍵字匹配上，則該條目為本次哈希查找的條目，根據(jù)哈希表的屬性寄存器配置的內(nèi)容取出查表的最終結(jié)果hash_final_result, 指令指針偏移值和統(tǒng)計計數(shù)偏移值。指令指針偏移值和該表屬性寄存器配置的指令指針基地址相加，作為指令指針最后和hash_final_result一并送給查表結(jié)果處理模塊。統(tǒng)計計數(shù)偏移值和查表屬性寄存器中的統(tǒng)計計數(shù)基地址相加得到統(tǒng)計計數(shù)指針，然后發(fā)起統(tǒng)計計數(shù)表查表請求。

PPU內(nèi)部直接表的查找過程和哈希表的查找過程非常類似，只是查找拼接后的數(shù)據(jù)dir_mux_result根據(jù)邏輯表屬性寄存器的字節(jié)寬度進行分割得到多個dir_result，然后用地址的最低幾位從分割后的數(shù)據(jù)dir_result中選擇出對應(yīng)的數(shù)據(jù)作為最終的查表結(jié)果dir_final_result，而不需要從分割的數(shù)據(jù)中取出關(guān)鍵字和查表關(guān)鍵字進行比較。

3.4 查表結(jié)果處理模塊

查表結(jié)果處理模塊主要是根據(jù)上一級PPU或報文解析模塊的處理結(jié)果和本次查表的結(jié)果進行合并生成新的描述符數(shù)據(jù)傳遞給下一級PPU或是可編程報文編輯模塊。查表處理模塊包含一個指令數(shù)據(jù)庫，該數(shù)據(jù)庫的每個條目包含u條ALU (Arithmetic Logical Unit, 算術(shù)邏輯部件運算器) 處理指令，每一條指令都可以執(zhí)行如下動作：

（1）將查表結(jié)果數(shù)據(jù)搬移到描述符總線上；

（2）將描述符總線上的數(shù)據(jù)搬移到描述符總線的其他位置；

（3）執(zhí)行邏輯運算，包括與，或，非和異或等操作；

（4）執(zhí)行算術(shù)運行，只執(zhí)行加法和減法運算，不執(zhí)行乘法和除法運算；

（5）執(zhí)行移位操作包括左移和右移；

（6）設(shè)置立即數(shù)，將立即數(shù)設(shè)置到描述符總線上。

4 總結(jié)

本文提出了一種可編程多級動態(tài)共享的查找表方案，解決基于現(xiàn)在網(wǎng)絡(luò)處理器架構(gòu)無法滿足低延遲，大容量交換的問題，也可以規(guī)避在基于固定流水轉(zhuǎn)發(fā)不可編程無法滿足新型業(yè)務(wù)快速部署的矛盾。通過軟件編程可以根據(jù)業(yè)務(wù)的需要動態(tài)調(diào)整各個查找表的大小和查找方式，查找關(guān)鍵字等；根據(jù)查找表的規(guī)模可以選擇使用PPU內(nèi)部查找表還是PPU外部查找表多級共享，滿足了5G及后5G新業(yè)務(wù)快速部署，大容量，低延遲，低能耗的需求。