使用前綴特性的IPv6尋址算法

黃 萍，劉昕林，孫鳳杰

1.深圳供電局有限公司 信息中心，廣東 深圳 518000

2.華北電力大學 電氣與電子工程學院，北京 102206

網絡承載的全球IP流量持續增長[1]。為了應對日益增長的互聯網流量，目前正在研究400 GB以太網標準。因此，網絡節點必須以這些線速率處理數據包，這就需要IP地址尋址引擎在小于6 ns的時間內處理IPv6數據包[2]。

IP尋址任務包括識別數據包應該轉發到的下一跳信息（NHI）。尋址過程包括將從包報頭提取的目標IP地址與存儲在稱為轉發信息庫（FIB）的尋址表中的條目列表相匹配。FIB中的每個條目（前綴）表示由其前綴地址和前綴長度定義的網絡，前綴長度表示有效前綴位的數量。雖然目的IP地址可能與FIB中的多個條目匹配，但只返回與匹配的最長前綴相關聯的NHI[3]。

由于為IPv4技術的IP尋址算法和體系結構在IPv6[4-6]中的性能不佳，因此，需要專用的IPv6尋址方法來支持即將到來的IPv6流量。所以需要針對高帶寬、低延遲，可伸縮性，大體量進行優化。但目前現有的方法并沒有共同解決這些性能要求[7-8]。

并且，現有的為軟件實現優化的解決方案在完整系統中不支持高查找率。此外，以硬件實現為目標的解決方案通常受到低吞吐量或低內存效率的影響。

因此，在這里提出了一種滿足當前IPv6性能要求的可擴展的IPv6尋址算法（SHSL），其創新點如下：（1）提出了兩級前綴分組，將IPv6前綴聚集在具有共同特征的組中。前綴根據它們的23個最高有效位被劃分為存儲單元，而這些單元存儲在哈希表中。在每個bin中，前綴根據FIB前綴長度分布分組排序。（2）提出一種混合字典樹（HTT），每組前綴都在HTT中編碼。HTT重新考慮了多位字典樹（Trie）的概念，但是根據前綴密度調整了每個級別上構建的節點數。（3）基于FPGA實現對SHSL數據結構的流水遍歷，并利用片上內存來支持高查找率，同時平衡了查找延遲。

1 算法概述

SHSL包括建立有效數據結構的過程和遍歷該結構的過程，即尋址算法。

SHSL將前綴聚類方法與內存高效的數據結構相結合。一種基于兩級前綴分組的聚類方法，根據前綴的23個最有效位（MSBs）將前綴分為地址塊bin（ABB），并根據FIB前綴長度分布將前綴分為前綴長度排序（PLS）組。ABB記錄在哈希表中，而每個前綴長度排序組中的前綴則編碼在HTT中。

SHSL數據結構如圖1所示。N項哈希表包含M個有效地址塊bin（ABB），這些地址塊bin（ABB）是在對MSB上的前綴進行分割后獲得的。每個有效的ABB都有一個指針指向一組K前綴長度排序（PLS）組，編碼在HTTs中。

圖1 數據結構示意圖Fig.1 Data structure

尋址算法識別與匹配的最長前綴相關聯的NHI。首先，對目標IP地址的MSB進行哈希運算，以選擇ABB指針。在本例中，在哈希表中選擇第m個ABB。選定的ABB指向一組由虛線矩形表示的K個HTT。其次，使用目的地IP地址的最低有效位，并行地遍歷所選htt。因為每個HTT都可以保存一個與IP地址匹配的前綴，所以使用優先級解析模塊來選擇與最長前綴相關聯的NHI。

2 兩級前綴分組

兩級前綴分組是一種在ABBs中對前綴進行劃分，并進一步對前綴進行長度分組的聚類方法。這種聚類方法是將前綴表分組，每個組保存一部分前綴。然后HTT利用組內的前綴分布。

2.1 地址塊分塊

前綴在ABB中基于它們的23個最高有效位（MSB）進行分塊，ABB被記錄在哈希表中。

在23個MSB上前綴分塊的目的與已知的IPv6地址空間分配有關。IPv6前綴是從由互聯網分配號碼管理局（IANA）管理的前綴塊池中分配的，范圍從/12到/23[9]。因為分配的前綴塊很少[9]，所以當前綴在23個MSB上進行分塊時，會創建一些的bin。因此，在原始前綴表大小的基礎上，前綴中bin的數量最多改變了兩個數量級。

ABB方法利用一個完美的哈希表[8]來存儲bin值，原因有兩個。首先，bin值幾乎是靜態的，因為它們表示分配給區域互聯網注冊中心的地址空間，這些地址空間不太可能在短時間內更新。其次，完美的散列函數保證了O(1)時間復雜度，因為不會產生沖突。

雖然在IPv4[10-13]中，使用哈希表或直接索引表在MSB上進行尋址的想法并不新鮮，但ABB方法針對IPv6進行了優化，并通過利用已知的IPv6地址空間分配與以前的工作有所不同。

由于與ABB相關聯的前綴可以重疊，因此引入前綴長度排序方法來減少重疊前綴的數量。

2.2 前綴長度排序

基于ABB前綴的PLS將IPv6分發組劃分為前綴。使用此方法將前綴從/24到/64排序到K個組中。每個組包含一個連續的前綴長度范圍。

根據兩個原則選擇每組覆蓋的前綴長度范圍。首先，當前綴長度占前綴總數的很大比例時，前綴長度被用作所考慮組的上限。其次，必須選擇前綴長度范圍，使得K組在前綴數量方面盡可能平衡。

為了說明這兩個原理，圖2中給出了使用實前綴表[14]對前綴長度分布的分析。圖2中省略了前23個前綴長度，因為ABB方法已經基于它們的23個MSB來存儲前綴。在圖2中可以觀察到，對于該示例，具有最大基數的前綴長度是/32和/48。將前綴長度排序的兩個原則應用到這個例子中，第一組覆蓋從/24到/32的前綴長度，第二組覆蓋從/33到/48的第二個峰值。最后，從/49到/64的所有剩余前綴長度都保留在第三個前綴長度排序組中。

圖2 3組PLS的前綴分布Fig.2 Prefix distribution of 3 PLS

第一個原則是通過將大量的前綴從可以重疊的較長前綴中分離出來，從而最小化前綴組中前綴重疊的數量。第二個原則是盡可能平衡PLS組之間前綴重疊的數量，以獲得具有相對相似特性的HTT。

3 混合TRIE-TREE數據結構

提出的HTT對每個非空PLS組中的前綴進行編碼。HTT數據結構經過定制，以使其形狀適應所用前綴的特性。HTT結合了一個密度自適應Trie（DAT）、一個內存高效的多位Trie和一個從字典樹的節點派生的leafbucket（LB）。

3.1 密度自適應Trie

提出的密度自適應Trie重新定義了多位Trie的概念。它通過調整基于前綴密度創建的節點數量來實現，前綴密度指的是Trie級別內非空節點的稀疏性，以及Trie級別內相鄰節點上的前綴復制因子。

與k位Trie類似，DAT迭代地應用于從保存前綴集的二進制Trie中提取的sub-Tries。DAT在將前綴推送到葉之后對sub-Trie的葉進行編碼，如圖3中的虛線箭頭所示。后面章節會具體介紹從二進制Trie中提取sub-Tries的方法。

DAT背后的主要思想是合并相鄰的空葉或記錄相同前綴的葉，如圖3（a）所示，并在單個合并節點中對它們進行編碼，如圖3（b）所示。相比之下，k位Trie將每個sub-Trie葉編碼成節點，如圖3（a）所示。

為了確定是否可以合并兩個相鄰的葉，將計算每個葉所覆蓋的前綴數，其中包括保留在葉中的前綴和保留在葉下分支中的前綴數。當合并節點覆蓋的前綴數量小于某個固定閾值，即leafbucket的大小或不高于兩個葉子覆蓋的最大前綴數時，兩個葉子被合并。

合并方法從sub-Trie的兩個邊緣的葉子向中心應用。例如，在圖3（a）中，合并方法從與節點N0和N7相關聯的葉開始。對于兩個方向，此方法評估一個葉是否可以與下一個相鄰葉合并。合并過程會重復，直到某個葉不能再與其相鄰的下一個葉合并。否則，將從最后一個未合并的葉中重復該方法。

合并方法對合并的葉的個數有兩個限制。首先，合并節點只對2的冪次的連續葉進行編碼，因為合并節點覆蓋的空間使用前綴表示法表示。其次，合并節點的總數受自適應Trie節點大小的限制。

通過合并方法計算的葉索引被編碼在LtoH和HtoL數組中。LtoH和HtoL陣列分別保存了從低索引到高索引和從高索引到低索引的葉片索引。所有沒有用合并方法計算的葉子都被保留為未合并，并且被稱為編碼在未合并區域中。

DAT中使用的合并方法的優點如圖3所示，其中編碼后的sub-Trie存儲在存儲器中的節點數量從圖3（a）中的3位Trie減少到使用DAT的2位，如圖3（b）所示。使用DAT，存儲前綴P1的兩個相鄰葉被合并，但也合并相鄰的空葉。

DAT通過合并記錄相同信息的相鄰節點來定制內存效率。然而，在圖3（b）中，DAT需要另一個級別來將前綴P2與前綴P1分開。因此，為了減少DAT的深度，當一個節點覆蓋的前綴數量低于閾值b時，前綴被編碼在LB中。

圖3 不同情況下的減少內存中存儲的子節點N i的數量Fig.3 Reduceing number of child nodes Ni stored in memory under different conditions

3.2 Leaf Bucket（LB）

LB存儲一組多達b個不同的前綴及其NHI，由一個DAT節點覆蓋，并存儲在DAT節點下的分支中。例如，在圖3（b）中，DAT節點N0覆蓋前綴P1和P2。

提出的LB來自樹葉，但只存儲了未匹配的前綴位。每個前綴的不匹配位數都以LB編碼，以及存儲的前綴數。通過減少存儲的信息量，所提出的LB提高了樹葉的內存效率，并且需要較少的內存訪問被讀取。使用LB編碼前綴的興趣是兩倍。當sub-Trie在葉中保存最多b個稀疏分布前綴時，LB需要的節點存儲前綴的節點比DAT少。此外，由于大多數PLS組的前綴很少，LB可以在單個節點A PLS組中編碼。

在圖3（c）中，覆蓋兩個或更少前綴的DAT節點被編碼為LBs。因此，使用將DAT與LBs結合的HTT，表1所示的前綴集被編碼在具有兩個子節點LB0和LB1的DAT根節點中，如圖4所示。在圖4中還介紹了每個LB的內容。

表1 前綴示例Table 1 Prefix example

圖4 表1完整的HTTFig.4 HTT based on Table 1

3.3 HTT構建過程

HTT構建過程分為兩部分：主過程和sub-Trie的選擇。

（1）主過程：主過程在二進制Trie的根節點啟動。如果存儲在二進制Trie中的前綴數量低于固定的閾值b，則將前綴編碼在LB中。否則，算法從二進制sub-Tries中迭代選擇，即從主二進制Trie中分割出來的二進制Tries，這些Tries被編碼到HTT節點中。

對于選定的sub-Trie，DAT合并方法應用于葉。然后，當一個DAT節點覆蓋多達b個前綴時，前綴將被編碼到一個LB中。否則，將創建一個DAT節點，并在sub-Trie的每個非空分支上重復該過程。

圖3（c）和圖4給出了表1所示前綴集的圖示。前綴被插入到二進制Trie中，如圖3（a）所示。在圖3（a）和（c）中，所選的sub-Trie位于虛線紅線上方。sub-Trie葉在HTT節點中編碼。然后對紅色虛線下方的每個sub-Trie重復該過程。

（2）Sub-Trie的選擇：貪婪算法作為算法1，在每次迭代中提取一個子矩陣，從中構建一個內存高效的淺層HTT。

算法1啟發式選擇sub-Trie編碼到HTT節點的深度

貪婪算法從二進制Trie中提取關于存儲開銷約束的最深sub-Trie。因為每次迭代都會選擇一個深sub-Trie，所以構建了一個具有很少級別的數據結構，而這反過來又需要很少的內存訪問來遍歷。

從用作所選sub-Trie的根的二進制Trie節點開始，該算法迭代地增加sub-Trie的深度，直到違反存儲開銷約束。

作為存儲開銷約束的空間度量因子(Smpf)的計算方法是將選定的sub-Trie及其分支中包含的前綴數乘以一個常數，在這里設置為8。使用更高的常量值有利于選擇更深的sub-Trie，代價是更高的存儲開銷。這里使用的常數是實驗性地選擇的，以在亞深度和存儲開銷之間提供一個很好的折衷。

在每次迭代中，空間度量(Sm)函數通過計算保留在葉上和保存在分支中的前綴的數量(NumPrefixes(leaf j))來估計所選sub-Trie的存儲開銷，并在其中添加懲罰項。在將前綴推送到sub-Trie的葉之后，計算保留在葉上的前綴數。

啟發式算法選擇一個sub-Trie，包含分支的平均前綴長度。如果所選分支中的平均前綴長度大于子串覆蓋的前綴長度，則Sm將緩慢增長，并選擇更深的sub-Trie。為了避免Sm在多次迭代中保持不變時選擇非常深的sub-Trie，在Sm中添加一個懲罰項，并將該懲罰定義為Sm(i-1)和所選sub-Trie的葉數之和。

3.4 HTT尋址過程

HTT尋址算法從遍歷密度自適應Trie開始，直到到達LB為止。然后，將保存在LB中的前綴與目標IP地址進行匹配，并返回最長匹配前綴的NHI。

（1）密度自適應Trie遍歷：當從內存中讀取DAT節點時，必須對DAT節點中編碼的sub-Trie進行解碼，以計算下一次讀取的子節點的地址。使用DAT節點中存儲的LtoH和HtoL數組，可以識別sub-Trie合并的葉子。

在DAT中，由于圖3（b）和（c）所示的合并方法，sub-Trie的葉與圖3（a）中所示的k位Trie的節點之間的一對一映射不成立。因此，子節點的存儲器位置是所選子節點之前合并葉數的函數。算法2給出了計算子節點地址的步驟。

算法2匹配子節點地址的標識

接下來要訪問的子節點的地址分兩步計算。首先，確定包含子節點的區域（LtoH數組、HtoL數組或未合并的區域）以及所選區域中的子節點索引。其次，計算匹配節點索引之前合并的葉子數，以導出其地址。

首先提取IP地址段，選擇索引等于IP地址段的sub-Trie葉。LtoH和HtoL數組都用于標識所選葉索引是否被LtoH區域、HtoL區域或未合并區域中的合并節點覆蓋。此外，如果選擇了LtoH或HtoL區域，則將標識包含所選葉索引的合并節點的數組索引。LtoH或HtoL數組中的數組索引分別記為p LtoH和p HtoL。如果匹配的節點位于未合并區域中，則數組索引為IP地址段。

其次，使用子節點索引之前的合并葉數，導出子節點偏移量。如果子節點在LtoH區域中，偏移量由p LtoH直接給出。在未合并區域中，使用p LtoH數組計算的合并葉數從IP地址段中減去，以獲得子節點偏移量。在p H toL區域中，使用LtoH和HtoL數組計算的合并葉數從子節點索引p HtoL中減去。最后，偏移量被添加到子基地址。

在圖5中示出了L=3和IP seg=10情況下的算法2。IP地址段匹配HtoL區域中的節點，如IP seg≥HtoL[0]。當9≤IP seg≤10時，HtoL區域內匹配的節點存儲在數組索引p HtoL=1中。使用HtoL和LtoH數組計算到匹配節點的合并葉數。基于LtoH數組，合并的葉數為LtoH[L-1]-(L-1)=1。當p HtoL+HtoL[0]=IP seg時，匹配節點之前的HtoL區域中不會合并任何葉。因此，匹配子節點的偏移量為IP seg-1=9。

圖5 合并前和合并后的節點索引存儲在LtoH和HtoL數組中Fig.5 Node indexes before merging and after merging storing in LtoH and HtoL arrays

（2）LB匹配：遍歷DAT，直到到達LB為止。首先解析葉，然后讀取前綴。接下來，根據目標IP地址匹配所有前綴，如果匹配為正，則記錄它們的前綴長度。當所有前綴都匹配時，只有匹配的最長前綴與它的NHI一起返回。

4 更新支持

首先分析了更新的特點，然后評估了使用SHSL算法進行更新的代價。

與其他工作類似，離線過程在接收到前綴更新后識別要修改的SHSL數據結構的節點[15-16]。

4.1 前綴更新分析

共有三種類型的前綴更新可應用于FIB；NHI修改現有前綴、插入前綴、刪除前綴。從2020/12/1到2020/12/2，由RIS遠程路由收集器[14]（rrc）接收的更新如圖6所示。基于圖6，可以觀察到每秒2 000個NHI修飾的峰值，而峰值前綴插入和刪除速率在每秒550個更新時相對相似。

圖6 兩天的更新Fig.6 Update rates over two days

然而，有效的刪除率和插入率可以大大降低。實際上，由于路由器可以與多個路由器交換網絡狀態信息，同一更新信息可以被一個路由器多次接收。此外，在網絡鏈路發生故障后的幾分鐘內，前綴可以被撤回和插入多次。事實上，先前的研究表明，在網絡鏈路故障后，觀察到的恢復時間平均為分鐘[16]。由于從相鄰路由器多次接收到信息，在網絡鏈路發生故障后的幾分鐘內，前綴可以被撤回并多次插入。總之，通過延遲刪除和每個時間戳對每個前綴進行一次更新，有效的前綴添加和刪除率將下降到每秒20次以下的更新。

4.2 開銷更新

現在通過計算修改SHSL數據結構的內存訪問次數來評估更新的開銷。讓CHTT和Chashtable分別代表HTTs和哈希表開銷更新。前綴的插入或刪除可以觸發哈希表更新和HTT的更新，與前綴長度無關。如果已更新前綴的23個MSB尚未與哈希表中的ABB關聯，則哈希表和HTT都必須更新。否則，只更新HTT。首先評估Chashtable。當ABB表中的一個條目被刪除時，需要一個與ABB表相關聯的詞條來更新。但是，必須重建整個哈希表以添加ABB。

為了降低更新的復雜性，需要構建一個哈希表，其中包含與當前IPv6單播地址空間相關聯的所有ABB[9]。因此，當添加前綴時，關聯的ABB條目通過單個存儲器訪問被啟用。此外，觀察到應用于哈希表的更新次數不到每秒一次。因此，Chashtable=insert ionrate×#memoryAccessperinsertion=1。保存所有ABB的哈希表使用54 KB，與SHSL上的數據結構大小相比可以忽略不計。此外，IPv6單播地址空間自2006年以來一直未被修改，其使用率仍然極低，因此該方法對于未來IPv6網絡的發展是有效的。

現在對HTT的更新成本進行了評估。當前綴NHI被更新時，更新HTT葉需要一次內存訪問。但是，前綴的插入或刪除需要重建HTT的一部分，或者一個完整的HTT。在所有使用的基準上，HTT中的節點數小于前綴的數量。結果，前綴更新后要修改的節點數最多等于n，即HTT中保留的前綴數。因為觀察到的大多數前綴更新都應用于HTT，CHTT=insertionrate×n+deletionrate×n+NHIupdaterate。

更新SHSL數據結構的成本為CHTT+Chashtable=20×n+20×n+2 000+1。因此，SHSL架構的更新復雜性為O(n)≈O(N)，其中N是FIB中前綴的數量。使用最大的前綴表，HTT中編碼的最大前綴數為n=7 000。因此，在最壞的情況下，每秒最多需要282 001個內存訪問來更新SHSL數據結構。

在最壞的情況下，每秒處理282 001次內存訪問對尋址速率的影響非常有限，而尋址速率大約是每秒數億次的尋址。

為了更新所提出的流水線硬件體系結構中的SHSL數據結構，使用了文獻[16]的技術，它是一種廣泛采用的技術，用于將更新推送到流水線硬件體系結構，該技術主要包含插入到管道中的三元組（管道階段、內存地址、值）。當到達三元組中指定的管道階段時，控制電路用三元組中保存的新值更新內存地址。

5 性能評估

5.1 實驗設置

SHSL的性能是用11個實前綴表來評估的，這些表保存著大約25 000個前綴，這些前綴是從RIS遠程路由收集器中提取的[14]。每一種情況下，rrc中的后兩位數的數字代表了所使用的遠程路由收集器在網絡中的位置。此外，還使用了合成前綴表。使用非隨機方法生成了一個合成的580k前綴表[17]。從580k前綴表中創建了四個較小的前綴表，前綴長度分布相似，分別保存290k、116k、58k和29k前綴。

由于SHSL使用兩級前綴分組對前綴進行聚類，因此在后面章節中評估了聚類后的前綴分布。使用一個小的實前綴表rrc00和最大的前綴表（580 000個前綴）來評估前綴分布。

SHSL性能的特征是遍歷數據結構的內存訪問次數及其內存占用。考慮了兩種情況：一種沒有聚類，即單個HTT對所有前綴進行編碼，另一種是使用兩級前綴分組對前綴進行聚類并在多個HTT中編碼。對于第二種情況，數字K的范圍是1到6。

所述架構的存儲器總線允許每個時鐘周期讀取一個HTT節點。此外，在ABB中選擇的K個HTT被并行地遍歷。報告的內存訪問數是所有ABB中所有HTT之間的最大內存訪問數。

HTT存儲開銷以每字節前綴字節數表示，以捕獲數據結構開銷。這個度量的計算方法是數據結構的大小除以前綴表中每個前綴的大小之和。為了表征每層的HTT效率，評估了HTT節點分布、HTTs深度分布和前綴分布。最后兩個指標只考慮最大深度。這些度量結合起來，可以評估每個HTT節點編碼的前綴的平均數量，這直接反映了HTT的效率。這些指標使用K=2 PLS組進行評估，類似于用于聚類分析和FPGA實現的參數。

5.2 實驗結果

5.2.1 簇內的前綴分配

如前所述，在MSB上存儲前綴的動機在于IPv6地址結構[9]。在本小節中，通過實驗證明，前綴可以使用ABB寬度設置為23。

在圖7中，評估ABB寬度對前綴分布、單元數和前綴數的影響。在這個圖中，ABB和PLS兩種聚類方法被應用于前綴。ABB寬度設置為23位時，ABB的單元數和前綴的數量被規范化，因為所提出的聚類方法將其23個MSB作為前綴。

圖7 聚類后PLS組內前綴分布與ABB寬度Fig.7 Prefix distribution of PLS vs ABB width

使用ABB寬度等于或大于23位的實數前綴會使前綴沿著圖7（a）所示的PLS組分布得更均勻。使用ABB寬度大于23的前綴無助于減少PLS組中的最大前綴數量，如異常值方框圖所示。此外，使用大于23位的ABB寬度對前綴的總數幾乎沒有影響，但是bin的數量有一個超線性的增長。

使用合成前綴，觀察到ABB寬度大于或等于24位的分布更加均勻。雖然使用大于23位的ABB寬度對前綴的總數影響很小，但是bin的數量與ABB的寬度有超線性的增長。

總之，對真實前綴和合成前綴的實驗表明，使用23位是一個很好的折衷方案。

5.2.2 ABB哈希表

記錄ABB指針的哈希表的性能如表2所示。對于真正的前綴，ABB方法使用19 KB到24 KB之間的值。在所有測試的場景中，存儲開銷都是相似的，因為前綴共享23個MSB中的大部分。使用合成前綴，平均每個前綴字節2.7 Byte的內存用于評估的5個場景。哈希表顯示了線性存儲開銷比例。由于使用了一個完美的哈希函數，因此在所有場景中，內存訪問的數量都是常量2。

表2 ABB內存開銷和內存訪問數Table 2 ABB memory overhead and accesses

5.2.3 HTTs

實際前綴：HTTs的性能如圖8（a）和（b）所示。兩級前綴分組減少了存儲開銷并平滑了其可變性。對于兩級前綴分組的所有場景，HTTs的存儲開銷在每個前綴字節1.36到1.60 Byte之間。相比之下，在沒有集群的情況下，對于編碼整個前綴集的單個HTT，存儲開銷在每個前綴字節1.22到3.15 Byte之間。

圖8 實際前綴中K對HTT性能的影響Fig.8 Influence of K in actual prefix on performance of HTT

從圖8（a）可知，將K增加到3會降低存儲器消耗，盡管使用更多組會使存儲器開銷加大。事實上，當K增加時，大多數組包含很少的前綴，這導致分配給HTT的大部分內存未使用。

使用聚類方法，內存訪問次數平均減少2倍。雖然對于單個HTT，使用兩級前綴分組，在沒有聚類的情況下，存儲器訪問的數量在9到18之間，但是如圖8（b）中所觀察到的，它在6和9之間變化。然而，將K從1增加到6，在存儲器訪問數量上幾乎沒有增加。實際上，可以觀察到內存訪問的數量受到幾個只包含/48個前綴的PLS組的限制。因此，增加K并不能減少這些PLS組中的前綴數目，這會導致內存訪問次數的改善。

表3顯示PLS組1和2的平均HTT深度分別為1.4和2.1。大約75%的HTT的深度等于1，因為75%的PLS組包含少于2個前綴，如圖7所示。實際上，在HTT中，兩個前綴可以存儲在單個節點中。實驗上，對于PLS組1和2，每個HTT節點的平均前綴數分別為1.3和1.4。對于大于1的級別，PLS組1和2的每個HTT節點的平均前綴數分別為1.5和1.0。基于圖7，深度大于1的HTT編碼超過75%的前綴。

表3 每層的HTT分析Table 3 HTT analysis for each layer

合成前綴：圖9展示了具有合成前綴的HTT的性能。在圖9（b）中可以觀察到兩種存儲開銷行為。對于包含290 000個或更多前綴的前綴表，使用K=2個組的兩級前綴分組稍微降低了單個情況下的存儲開銷HTT。另外，使用K＞2并不能提高內存效率。對于具有高達116 000個前綴的較小前綴表，僅使用單個HTT實現較低的存儲開銷。事實上，使用包含高達116 000個前綴的合成前綴表，大多數PLS組只包含一個前綴。因此，對于每個PLS組，分配給HTT的大部分內存未使用，這降低了內存效率。

HTT的存儲開銷比例如圖9（c）所示。這種存儲開銷，無論是否有兩級前綴分組，都隨著前綴的數量線性增長。注意橫坐標使用對數刻度。因此，HTT的存儲開銷縮放在有無兩級前綴分組的情況下是線性的。

基于圖9（a），使用兩級前綴分組減少了單個HTT上的存儲器訪問次數。平均來說，使用2個或更多組的單個HTT可以減少40%的內存訪問量。但是，使用K＞3并不能進一步減少內存訪問的次數。實際上，導致最大內存訪問次數的PLS組不能通過增加組的數量來減小其大小。最后，圖9（a）展示了用于搜索的存儲器訪問次數的增加最多與前綴的數量成對數關系，因為每條曲線近似線性且x軸是對數的。

圖9 合成前綴中K對HTT性能的影響Fig.9 Influence of K in synthetic prefix on HTT performance

就HTT效率而言，使用合成前綴也可以得出相同的結論。根據表4，PLS組1和2的平均HTT深度均為1.5。80%的HTT具有等于1的深度，這與圖2中所示的前綴分布一致。實驗上，對于PLS組1和2，平均每個HTT節點在一級分別編碼1.5和1.3個前綴。對于大于1的級別，PLS組1和2的每個HTT節點的平均前綴數分別為2.0和2.1。

表4 不同架構的性能Table 4 Performance of different architectures

最后，與兩級前綴分組一起使用的HTT具有線性存儲開銷比例和內存訪問次數的對數比例。ABB方法中使用的哈希表已經顯示出提供了線性存儲開銷縮放和固定數量的內存訪問。因此，SHSL使用所有考慮的基準對內存訪問的數量具有線性的存儲開銷縮放比例和對數縮放比例。

6 基于FPGA的實現

開發了兩種SHSL結構的FPGA硬件實現，并對其進行了特性分析。一個被優化以減少延遲，而另一個被優化以提高吞吐量。整個部署是基于C++進行的，并使用了Vivado HLS在Virtex7和UltraScale+上進行實現。

6.1 架構概述

這兩種架構實現了對SHSL數據結構的流水線遍歷。兩種體系結構的HTT遍歷模塊被劃分為K=2個并行管線。每條管線i∈[1,2,…,K]執行由第i個PLS組中的根指針地址選擇的HTT的遍歷。

對于低延遲架構，HTT遍歷模塊管線被劃分為d個階段，使得每個階段專用于單個HTT級別的遍歷。管線級j∈[1,2,…,d]由一個遍歷引擎（TE）和一個內存組成，存儲所有ABB（Bin從1到M）的j級HTT節點。第一個d-1級別的遍歷引擎僅用于處理DAT節點，而LB節點處理僅在d級完成。

為了提高低延遲架構上的尋址速率，高吞吐量架構將低延遲架構的每個管道階段分為多個階段。通過減少每個階段的邏輯電平數，可以獲得更短的時鐘周期，這也提高了尋址率。

6.2 結果

對于表4中給出的每個設計，有四個性能指標值得關注：尋址率、延遲、片上內存使用率（BRAM）和邏輯使用率。尋址延遲或掛鐘時間計算為時鐘周期乘以管道階段數。

在這里，首先討論高吞吐量體系結構的性能。然后，比較了高吞吐量體系結構與低延遲體系結構的開銷。

（1）高吞吐量架構：在Virtex7上實現的高吞吐量架構的尋址率隨著前綴表的大小而降低。使用25k前綴時，最多支持345 Mpacket/s，而當使用290k前綴時，尋址速率降低到264 Mpacket/s，并且使用最大前綴表進一步降低到167 Mpacket/s。

前綴表大小對尋址速率的影響與片上存儲器在FPGA中的分布有關。片上存儲器、block RAM被分成列。當SHSL數據結構的一個級別被映射到多個block RAM列時，由于訪問多個列的路由延遲，時鐘周期增加。作為路由延遲增加的直接結果，尋址率降低。

延遲也隨著前綴表的大小而增加，這是在較大場景下時鐘周期降低的結果。對于包含290 000個前綴的前綴表，尋址延遲在189.6到246.5 ns之間，而對于最大前綴表，尋址延遲增加到396.4。

block RAM的使用與前綴表大小幾乎成線性關系，這是圖9（c）中觀察到的線性存儲器消耗的結果。

由于在較大的場景中block RAM的消耗量較大，FPGA邏輯使用量隨著前綴表的大小而增加。在最小場景和最大場景之間，邏輯使用增加了61%。實際上，將單個block RAM組合成一個大內存所需的電路消耗FPGA邏輯。

由于Virtex7上的高吞吐量架構性能受到路由延遲的限制，在UltraScale+上評估了該架構，該FPGA具有更深的block RAM列和減少的路由延遲。在這個FPGA上，對于最大的情況，時鐘周期比Virtex7縮短了1.7倍。因此，尋址速率增加到295 Mpacket/s，并且尋址延遲減少到219.3 ns。此外，由于UltraScale+的內部結構經過修改，允許在block RAM列中構建大內存，而無需額外使用邏輯資源，因此邏輯消耗比Virtex 7減少了1.6倍。

為了進一步提高尋址速率，可以修改高吞吐量體系結構，使尋址速率加倍。所提出的技術包括使用兩個并行尋址引擎共享Virtex7和UltraScale+上的雙端口block RAM。單個雙端口內存塊可以同時為兩個尋址引擎提供服務。因此，帶有雙端口內存塊的高吞吐量體系結構在Virtex 7和UltraScale+上分別可以支持333 Mpacket/s和589 Mpacket/s。然而，由于實現了兩個并行尋址引擎，邏輯消耗幾乎增加了一倍。

（2）高吞吐量體系結構的開銷：在使用Virtex7時，高吞吐量體系結構比低延遲體系結構幾乎提高了三倍，使用UltraScale+時尋址率提高了3.3倍以上，如表4所示，高吞吐量架構使用的FPGA邏輯比低延遲架構多1.8倍，因為它的流水線更深，這就要求FPGA邏輯在每個流水線階段同步中間結果。盡管如此，與低延遲架構相比，高吞吐量架構增加的尋址速率超過了邏輯消耗開銷。此外，片上存儲器的使用不受管道深度的影響，因此，對于兩種架構，block RAM的消耗保持相似。

與低延遲體系結構相比，高吞吐量體系結構的缺點在于尋址延遲增加。由于流水線級的數量增加了5.4倍，而時鐘周期減少了不到3倍，與Virtex7上的低延遲架構相比，最大前綴表的尋址延遲增加了3倍，達到397 ns。使用UltraScale+，高吞吐量體系結構的尋址延遲僅比低延遲體系結構增加1.7倍，達到220 ns。

7 結束語

本文提出了一種可擴展的高性能IPv6尋址算法，以滿足當前和未來網絡應用的性能要求。SHSL利用前綴特性創建一個淺而高效的數據結構。首先，分配的IPv6地址空間用于有效地將前綴放入其MSB上。在每個bin中，前綴按FIB前綴長度分布分組排序。然后，將每個前綴組編碼在混合Trie樹（HTT）中。本文重新討論了多比特Trie的概念，但對基于前綴密度的節點數進行了調整，提高了內存效率。將Trie葉片轉化為LB，進一步提高了記憶效率。

提出的數據結構支持增量更新，并有效地映射到硬件上。提出了一種利用片上存儲器的流水線高吞吐量硬件體系結構。

使用實前綴表和合成前綴表對SHSL進行了評估，該表包含580 000個IPv6前綴，在內存訪問數量和線性存儲開銷比例方面，SHSL表現出對數比例因子。與其他著名的方法相比，SHSL將每個前綴所需的內存量減少了87%。