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

文/陳欽樹(shù) 管自新 廖述京

1 引言

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

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

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

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

3 可編程多級(jí)動(dòng)態(tài)共享查找表

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

3.1 查表?xiàng)l件判決模塊

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

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

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

3.3 PPU查找表讀寫(xiě)控制模塊

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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