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

黃 萍，劉昕林，孫鳳杰

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

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

網(wǎng)絡(luò)承載的全球IP流量持續(xù)增長[1]。為了應(yīng)對日益增長的互聯(lián)網(wǎng)流量，目前正在研究400 GB以太網(wǎng)標準。因此，網(wǎng)絡(luò)節(jié)點必須以這些線速率處理數(shù)據(jù)包，這就需要IP地址尋址引擎在小于6 ns的時間內(nèi)處理IPv6數(shù)據(jù)包[2]。

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

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

并且，現(xiàn)有的為軟件實現(xiàn)優(yōu)化的解決方案在完整系統(tǒng)中不支持高查找率。此外，以硬件實現(xiàn)為目標的解決方案通常受到低吞吐量或低內(nèi)存效率的影響。

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

1 算法概述

SHSL包括建立有效數(shù)據(jù)結(jié)構(gòu)的過程和遍歷該結(jié)構(gòu)的過程，即尋址算法。

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

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

圖1 數(shù)據(jù)結(jié)構(gòu)示意圖Fig.1 Data structure

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

2 兩級前綴分組

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

2.1 地址塊分塊

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

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

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

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

由于與ABB相關(guān)聯(lián)的前綴可以重疊，因此引入前綴長度排序方法來減少重疊前綴的數(shù)量。

2.2 前綴長度排序

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

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

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

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

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

3 混合TRIE-TREE數(shù)據(jù)結(jié)構(gòu)

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

3.1 密度自適應(yīng)Trie

提出的密度自適應(yīng)Trie重新定義了多位Trie的概念。它通過調(diào)整基于前綴密度創(chuàng)建的節(jié)點數(shù)量來實現(xiàn)，前綴密度指的是Trie級別內(nèi)非空節(jié)點的稀疏性，以及Trie級別內(nèi)相鄰節(jié)點上的前綴復(fù)制因子。

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

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

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

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

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

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

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

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

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

3.2 Leaf Bucket（LB）

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

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

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

表1 前綴示例Table 1 Prefix example

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

3.3 HTT構(gòu)建過程

HTT構(gòu)建過程分為兩部分：主過程和sub-Trie的選擇。

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

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

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

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

算法1啟發(fā)式選擇sub-Trie編碼到HTT節(jié)點的深度

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

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

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

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

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

3.4 HTT尋址過程

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

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

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

算法2匹配子節(jié)點地址的標識

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

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

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

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

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

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

4 更新支持

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

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

4.1 前綴更新分析

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

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

然而，有效的刪除率和插入率可以大大降低。實際上，由于路由器可以與多個路由器交換網(wǎng)絡(luò)狀態(tài)信息，同一更新信息可以被一個路由器多次接收。此外，在網(wǎng)絡(luò)鏈路發(fā)生故障后的幾分鐘內(nèi)，前綴可以被撤回和插入多次。事實上，先前的研究表明，在網(wǎng)絡(luò)鏈路故障后，觀察到的恢復(fù)時間平均為分鐘[16]。由于從相鄰路由器多次接收到信息，在網(wǎng)絡(luò)鏈路發(fā)生故障后的幾分鐘內(nèi)，前綴可以被撤回并多次插入?？傊ㄟ^延遲刪除和每個時間戳對每個前綴進行一次更新，有效的前綴添加和刪除率將下降到每秒20次以下的更新。

4.2 開銷更新

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

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

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

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

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

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

5 性能評估

5.1 實驗設(shè)置

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

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

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

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

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

5.2 實驗結(jié)果

5.2.1 簇內(nèi)的前綴分配

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

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

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

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

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

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

5.2.2 ABB哈希表

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

表2 ABB內(nèi)存開銷和內(nèi)存訪問數(shù)Table 2 ABB memory overhead and accesses

5.2.3 HTTs

實際前綴：HTTs的性能如圖8（a）和（b）所示。兩級前綴分組減少了存儲開銷并平滑了其可變性。對于兩級前綴分組的所有場景，HTTs的存儲開銷在每個前綴字節(jié)1.36到1.60 Byte之間。相比之下，在沒有集群的情況下，對于編碼整個前綴集的單個HTT，存儲開銷在每個前綴字節(jié)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增加時，大多數(shù)組包含很少的前綴，這導(dǎo)致分配給HTT的大部分內(nèi)存未使用。

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

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

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

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

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

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

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

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

表4 不同架構(gòu)的性能Table 4 Performance of different architectures

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

6 基于FPGA的實現(xiàn)

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

6.1 架構(gòu)概述

這兩種架構(gòu)實現(xiàn)了對SHSL數(shù)據(jù)結(jié)構(gòu)的流水線遍歷。兩種體系結(jié)構(gòu)的HTT遍歷模塊被劃分為K=2個并行管線。每條管線i∈[1,2,…,K]執(zhí)行由第i個PLS組中的根指針地址選擇的HTT的遍歷。

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

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

6.2 結(jié)果

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

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

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