黃 萍，劉昕林，孫鳳杰

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

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

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

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

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

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

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

1 算法概述

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

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

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

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

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

2 兩級(jí)前綴分組

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

2.1 地址塊分塊

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

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

ABB方法利用一個(gè)完美的哈希表[8]來存儲(chǔ)bin值，原因有兩個(gè)。首先，bin值幾乎是靜態(tài)的，因?yàn)樗鼈儽硎痉峙浣o區(qū)域互聯(lián)網(wǎng)注冊(cè)中心的地址空間，這些地址空間不太可能在短時(shí)間內(nèi)更新。其次，完美的散列函數(shù)保證了O(1)時(shí)間復(fù)雜度，因?yàn)椴粫?huì)產(chǎn)生沖突。

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

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

2.2 前綴長(zhǎng)度排序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Leaf Bucket（LB）

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

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

在圖3（c）中，覆蓋兩個(gè)或更少前綴的DAT節(jié)點(diǎn)被編碼為L(zhǎng)Bs。因此，使用將DAT與LBs結(jié)合的HTT，表1所示的前綴集被編碼在具有兩個(gè)子節(jié)點(diǎn)LB0和LB1的DAT根節(jié)點(diǎn)中，如圖4所示。在圖4中還介紹了每個(gè)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）主過程：主過程在二進(jìn)制Trie的根節(jié)點(diǎn)啟動(dòng)。如果存儲(chǔ)在二進(jìn)制Trie中的前綴數(shù)量低于固定的閾值b，則將前綴編碼在LB中。否則，算法從二進(jìn)制sub-Tries中迭代選擇，即從主二進(jìn)制Trie中分割出來的二進(jìn)制Tries，這些Tries被編碼到HTT節(jié)點(diǎn)中。

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

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

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

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

貪婪算法從二進(jìn)制Trie中提取關(guān)于存儲(chǔ)開銷約束的最深sub-Trie。因?yàn)槊看蔚紩?huì)選擇一個(gè)深sub-Trie，所以構(gòu)建了一個(gè)具有很少級(jí)別的數(shù)據(jù)結(jié)構(gòu)，而這反過來又需要很少的內(nèi)存訪問來遍歷。

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

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

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

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

3.4 HTT尋址過程

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

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

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

算法2匹配子節(jié)點(diǎn)地址的標(biāo)識(shí)

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

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

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

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

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

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

4 更新支持

首先分析了更新的特點(diǎn)，然后評(píng)估了使用SHSL算法進(jìn)行更新的代價(jià)。

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

4.1 前綴更新分析

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

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

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

4.2 開銷更新

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

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

現(xiàn)在對(duì)HTT的更新成本進(jìn)行了評(píng)估。當(dāng)前綴NHI被更新時(shí)，更新HTT葉需要一次內(nèi)存訪問。但是，前綴的插入或刪除需要重建HTT的一部分，或者一個(gè)完整的HTT。在所有使用的基準(zhǔn)上，HTT中的節(jié)點(diǎn)數(shù)小于前綴的數(shù)量。結(jié)果，前綴更新后要修改的節(jié)點(diǎn)數(shù)最多等于n，即HTT中保留的前綴數(shù)。因?yàn)橛^察到的大多數(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個(gè)內(nèi)存訪問來更新SHSL數(shù)據(jù)結(jié)構(gòu)。

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

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

5 性能評(píng)估

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果

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

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

在圖7中，評(píng)估ABB寬度對(duì)前綴分布、單元數(shù)和前綴數(shù)的影響。在這個(gè)圖中，ABB和PLS兩種聚類方法被應(yīng)用于前綴。ABB寬度設(shè)置為23位時(shí)，ABB的單元數(shù)和前綴的數(shù)量被規(guī)范化，因?yàn)樗岢龅木垲惙椒▽⑵?3個(gè)MSB作為前綴。

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

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

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

總之，對(duì)真實(shí)前綴和合成前綴的實(shí)驗(yàn)表明，使用23位是一個(gè)很好的折衷方案。

5.2.2 ABB哈希表

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

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

5.2.3 HTTs

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

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

從圖8（a）可知，將K增加到3會(huì)降低存儲(chǔ)器消耗，盡管使用更多組會(huì)使存儲(chǔ)器開銷加大。事實(shí)上，當(dāng)K增加時(shí)，大多數(shù)組包含很少的前綴，這導(dǎo)致分配給HTT的大部分內(nèi)存未使用。

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

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

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

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

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

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

圖9 合成前綴中K對(duì)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中所示的前綴分布一致。實(shí)驗(yàn)上，對(duì)于PLS組1和2，平均每個(gè)HTT節(jié)點(diǎn)在一級(jí)分別編碼1.5和1.3個(gè)前綴。對(duì)于大于1的級(jí)別，PLS組1和2的每個(gè)HTT節(jié)點(diǎn)的平均前綴數(shù)分別為2.0和2.1。

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

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

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

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

6.1 架構(gòu)概述

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

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

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

6.2 結(jié)果

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

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

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

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

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

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

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

由于Virtex7上的高吞吐量架構(gòu)性能受到路由延遲的限制，在UltraScale+上評(píng)估了該架構(gòu)，該FPGA具有更深的block RAM列和減少的路由延遲。在這個(gè)FPGA上，對(duì)于最大的情況，時(shí)鐘周期比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倍。

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

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

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

7 結(jié)束語

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

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

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