基于TCAM的并行路由查找方案綜述

王　輝　李曉歌　張　賓　秦董洪

1(河南牧業(yè)經(jīng)濟學(xué)院自動化與控制系　河南 鄭州 450000)2(中國解放軍理工大學(xué)總參第63所　江蘇 南京 210007)3(廣西民族大學(xué)信息科學(xué)與工程學(xué)院　廣西 南寧 530006)

?

基于TCAM的并行路由查找方案綜述

王輝1李曉歌1張賓2秦董洪3

1(河南牧業(yè)經(jīng)濟學(xué)院自動化與控制系河南 鄭州 450000)2(中國解放軍理工大學(xué)總參第63所江蘇 南京 210007)3(廣西民族大學(xué)信息科學(xué)與工程學(xué)院廣西 南寧 530006)

摘要基于三態(tài)內(nèi)容尋址存儲器TCAM(Ternary Content-Addressable Memory)的路由查找方案是目前高性能路由器進行路由查找時普遍使用的方案，但這種方案仍存在查找速度、功耗和更新效率方面的挑戰(zhàn)。因此，學(xué)者們提出了各種并行TCAM的解決方案以提高查找速度、降低功耗和增強更新效率。歸類總結(jié)目前的并行TCAM路由查找方案，剖析它們的優(yōu)缺點，指出目前這些方案仍存在的不足，并探索相應(yīng)的解決方案。

關(guān)鍵詞并行TCAM路由查找功耗地址劃分

0引言

網(wǎng)絡(luò)組織認為在一般的處理器上達到G數(shù)量級的路由查找不太可能。由于路由查找需要進行地址最長前綴匹配，所以一般認為要達到G數(shù)量級的查找速度需要硬件的支持。另外既然路由查找是一種慢和復(fù)雜的操作過程，人們自然就想到一些技術(shù)來避開這些操作，其中一個想法是在IP層下實現(xiàn)各種鏈路層的交換技術(shù)，如基于虛電路技術(shù)的ATM技術(shù)，基于標(biāo)簽技術(shù)的MPLS等。它們都想避開或減少路由查找，但這反而增加了網(wǎng)絡(luò)的復(fù)雜性和冗余度，給網(wǎng)絡(luò)帶來不必要的負擔(dān)，降低了網(wǎng)絡(luò)的效率。既然鏈路層交換和IP層路由完成相同的功能，所以只用它們中的一種來處理將會更加簡單。另一種思路使用緩存技術(shù)，這種技術(shù)緩存的命中率比較高，然而隨著因特網(wǎng)的快速增長，增加了緩存所需要的空間，這種方法所要求的硬件緩存可能很不經(jīng)濟。

現(xiàn)在我們重新回到路由查找的思路上，目前高性能路由器中的路由查找方案大致分兩類：一類是基于Trie樹的軟件方案，另一類是基于TCAM的硬件解決方案[1]。傳統(tǒng)的路由表實現(xiàn)使用Trie樹，有很多優(yōu)化能減少Trie樹的存儲空間并且加快查找速度，然而這種數(shù)據(jù)結(jié)構(gòu)仍然太大而不能滿足要求，以致路由表不能裝入芯片緩存中而支持不了G級路由查找速度。另外，基于Trie樹的方案在進行路由查找時經(jīng)常需要幾次的存儲器訪問，雖然有很多方法來減少訪問次數(shù)[2-4]，但這類使用DRAM或SRAM的軟件方案由于其本身的特點很難更快地提高路由查找速度。

相比之下，TCAM由于其自身的并行訪問特性使其能在一次訪問完成路由查找，而且基于TCAM的硬件方案在更新上要比基于Trie樹的軟件方案簡單，所以TCAM方案在高性能路由器的發(fā)展中取得越來越多的應(yīng)用。TCAM是一種三態(tài)內(nèi)容尋址存儲器，主要用于快速查找ACL、路由等表項，它是從CAM的基礎(chǔ)上發(fā)展而來的。一般的CAM存儲器中每個bit位的狀態(tài)只有兩個，“0”或“1”，而TCAM中每個bit位有三種狀態(tài)，除掉“0”和“1”外，還有一個“don’t care”狀態(tài)，所以稱為“三態(tài)”，它是通過掩碼來實現(xiàn)的，正是TCAM的這個第三種狀態(tài)特征使其既能進行精確匹配查找，又能進行模糊匹配查找，而CAM沒有第三種狀態(tài)，所以只能進行精確匹配查找。

TCAM具有查找速度快、操作簡單的優(yōu)點。然而,這類基于TCAM的路由查找方案面臨如下挑戰(zhàn)：

? IP 前綴是變長的而到來的數(shù)據(jù)包并不攜帶前綴長度信息，所以在進行路由查找時會匹配到多個地址前綴而應(yīng)該選擇最長的那個地址前綴 (LMP)。

? 光纖技術(shù)的發(fā)展使核心路由器要處理 40 Gbps或更高的線速，而最新的18 MB TCAM只能達到266 MHz的處理速度，每秒只能完成 133 millions次的查找, 遠遠跟不上40 Gbps的線速[5]。

? 路由表表項以大約每年10～50 k的速度在增長[6]，特別是當(dāng)IPv6廣泛部署后，需要TCAM要有更大的存儲空間。

? TCAM在進行路由查找時需要消耗大的功耗和散發(fā)大的熱量，如何降低功耗減少熱量也是查找引擎需要考慮的重要問題。

? 頻繁的更新要消耗查找引擎大量的計算而降低了查找的效率，所以如何進行高效的更新也是要考慮的重要問題。

歸納起來，這些挑戰(zhàn)需要基于TCAM的查找引擎解決如下三方面的問題：

? 查找速度

? 功耗

? 更新效率

基于這三個問題，人們提出了并行的TCAM解決方案。但目前據(jù)我們所知,并沒有一篇文章對這些工作進行歸類、梳理和分析。為了填補這個空白，調(diào)研了各種不同的并行TCAM解決方案并分析它們各自的優(yōu)缺點。并針對目前仍存在的問題提出了可能的改進方案，為進一步對基于TCAM進行并行路由查找算法的研究奠定了一定基礎(chǔ)。

1基于端口的并行方案

基本思想是將路由表項按輸出端口進行劃分，具有相同輸出端口的路由表項放在一個表中，每個表都用一個獨立的TCAM進行存儲，所以并行的TCAM數(shù)和輸出端口數(shù)相同。其體系結(jié)構(gòu)如圖1所示[7]。

圖1　基于端口的并行TCAM體系結(jié)構(gòu)

當(dāng)包到來時，所有并行的TCAM都要進行一次查找并輸出所有匹配的表項，然后送入選擇邏輯中，由選擇邏輯選定最長的匹配前綴并輸出其輸出端口。

由于每個TCAM中的路由表項有相同的輸出端口，所以每個TCAM內(nèi)部的路由表項不需要進行排序。進行路由表項的插入操作時，只需要查看路由表項的輸出端口號，然后插入相應(yīng)表的空余的表項中即可，刪除時直接刪除即可,都不需要移動表項，所以更新時間復(fù)雜度可以達到O(1)。這種方案提高了TCAM的更新效率。

這種方案雖然提高了更新效率，卻為此付出很大代價。首先由于所有TCAM都需要為一次路由查找進行并行查找，效率低功耗大。其次每個端口需要的路由表項數(shù)目可能相差很大而且不可預(yù)知，所以會造成很大的空間浪費。再者若端口很多則會需要很多的TCAM，不實際且擴展性差。最后它增加了選擇邏輯的復(fù)雜性。

2基于無子孫關(guān)系前綴集合的并行方案

基本思想:若一個集合中的所有地址前綴無子孫關(guān)系或不為互為前綴關(guān)系(我們稱這種關(guān)系為disjoint)，則集合中所有前綴所包含的地址范圍映射到一維地址空間上無地址重疊關(guān)系，所以在進行地址查找時這個集合至多只有一個匹配項。經(jīng)過調(diào)研目前路由表的前綴Trie樹一般不超過7層(包括*),如果把轉(zhuǎn)發(fā)表分到不同的TCAM中，使每個TCAM中的地址前綴為disjoint關(guān)系，則這些TCAM在查找時至多只有一項匹配，所以這些TCAM就不需要優(yōu)先編碼邏輯。圖2表示了這種方案的體系結(jié)構(gòu)[8]。

圖2　基于無子孫關(guān)系前綴集合的并行TCAM體系機構(gòu)

TCAM0 到 TCAM6 包含了disjoint集合的地址前綴, 不需要priority encoder logic(PE)。TCAM7仍用了一個普通的帶PE的TCAM，原因是在更新時有可能到來的地址前綴和前6個TCAM中的任一個前綴集合都無disjoint關(guān)系，則插入TCAM7中。由于TCAM7中的PE邏輯，它里面的地址前綴無限定條件，TCAM7輸出最長前綴匹配。

此方案TCAM更新的時間復(fù)雜度為O(1),提高了TCAM的更新效率，而且需要的并行TCAM數(shù)量固定。但這種方案也存在類似前一個方案中一些較大的缺陷。首先由于所有TCAM都需要為一次路由查找進行并行查找，效率低功耗大。其次每個TCAM中路由表項數(shù)目可能相差很大，所以會造成很大的空間浪費。最后增加了選擇邏輯的復(fù)雜性。

3基于CoolCAMs技術(shù)的并行方案

為了減少TCAM的功耗，有一種機制可以只訪問整個TCAM的一小部分，這些被劃分的區(qū)域稱為blocks，CoolCAMs的思想就是把轉(zhuǎn)發(fā)表劃分成多個子表稱之為buckets，每個bucket部署在一個或多個TCAM的block上，在進行路由查找時只觸發(fā)相應(yīng)bucket對應(yīng)的blocks即可。目前有三種bucket劃分方案：

? 基于Trie樹劃分

? 基于地址位劃分

? 基于地址范圍劃分

基于這三種劃分方案并使用CoolCAMs技術(shù)有三種并行的TCAM方案，下面分別對它們進行介紹。

3.1基于Trie樹劃分的并行TCAM方案

首先由轉(zhuǎn)發(fā)表構(gòu)造二進制Trie樹，然后進行劃分，存在兩種劃分方法：1) Subtree splitting；2) Post-order splitting。具體如何劃分不再詳述。此方案在第一階段的查找過程中需要用一個小的index TCAM來保存前綴Trie樹，當(dāng)一個包到來時，先通過它找到bucket ID的索引，這個索引指向的SRAM包含真正的ID號，由ID號觸發(fā)相應(yīng)的TCAM對應(yīng)的blocks進行第二階段的查找。第一階段相當(dāng)于邏輯判斷。其體系結(jié)構(gòu)如圖3所示[9]。

圖3　基于Trie樹劃分的并行TCAM體系機構(gòu)

這種方案相比于前兩種可以使一次路由查找只在一個并行的TCAM中進行，這樣就有可能為到來的包進行并行查找，而且由于使用CoolCAMs技術(shù)可以只觸發(fā)TCAM中相應(yīng)的blocks進行查找，查找效率高功耗小。不足之處是首先進行劃分的時間復(fù)雜度是O(N + NW/b)。其中W是最大的前綴長度，O(N/b)是被砍掉的子樹數(shù)目。再者劃分的最大和最小bucket size相差兩倍，另外還需要一個index TCAM存儲Trie樹并且每次查找都要訪問此TCAM，會增加一些功耗。最后此方案的更新效率較低O(N + NW/b)，除了進行data TCAM的更新，還要進行index TCAM的更新。

3.2基于地址位劃分的并行TCAM方案

這種方案[10,11]面臨的一個很大的挑戰(zhàn)是如何選擇地址前綴中的位使得劃分得到的分區(qū)中的地址前綴數(shù)盡量平均，以及如何將這些分區(qū)放入TCAM使每個TCAM中的Traffic Load盡量平均，使查找效率盡量高功耗盡量小的問題。下面介紹Zheng 等提出的方案[10]。

他們分析了IPMA提供的路由表發(fā)現(xiàn)地址前綴的某些特定位可使它們比較平均的分布，他們用地址前綴的10～13位作為ID號，把路由表劃分成16組，但如何把這16個分區(qū)放入TCAM中又是一個待解決的難題。一種思路是每個TCAM多放一個冗余的分區(qū)，當(dāng)包到來時如果這個包匹配的分區(qū)在兩個TCAM中都有，選擇邏輯會選擇輸入隊列較少的那個TCAM。另一種相輔相成的思路是分析Traffic分布情況，使放入TCAM中的分區(qū)讓每個TCAM的流量盡量均衡。

當(dāng)一個包到來時，選擇邏輯會根據(jù)目的地址的10～13位判斷匹配哪個分區(qū)，此分區(qū)在哪些TCAM中，然后由哪個TCAM的輸入隊列較短就把包送到哪個TCAM的輸入隊列中。而相應(yīng)的TCAM在進行查找時，只觸發(fā)分區(qū)所在的blocks以減小功耗。

這種方案最好情況下的查找速度能達到單個TCAM的k倍，k是并行TCAM的個數(shù)，假如每個TCAM的功率消耗為M，每個分區(qū)所占的blocks數(shù)是TCAM中所有blocks數(shù)的1/n，則最大功耗為kM/n，是一種查找效率高而功耗低的查找方案。最壞情況下是出現(xiàn)在突發(fā)的流量，所有的包都在某個特定分區(qū)中，而且這個分區(qū)只在一個TCAM中。這時相當(dāng)于一個TCAM在處理所有任務(wù)，查找速度相當(dāng)于單個TCAM的速度，如果線速很高，則會出現(xiàn)大量丟包，所以這種方案應(yīng)付因特網(wǎng)上經(jīng)常出現(xiàn)的突發(fā)流量比較差。另外在劃分分區(qū)時依賴某些特定位的統(tǒng)計數(shù)據(jù)，對不同站點情況不同，擴展性差，而且各分區(qū)的路由表項數(shù)目不平均。更新效率為O(N/k)，其中N為路由表項，k為并行TCAM數(shù)，更新時需注意對于跨多個TCAM的路由表項需要同時更新。

3.3基于地址范圍劃分的并行TCAM方案

基于前兩種劃分方案bucket中的地址前綴數(shù)都不平均，自然想到是否存在一種劃分方案使每個bucket中的地址前綴數(shù)基本相等。Anigrahy[12]給出了地址范圍劃分的方案，如圖4所示。

圖4　基于地址范圍劃分的方案

圖4中劃分了4組，可以讓每組前綴數(shù)目基本相等，把每個組都放到一個不同的TCAM中，每個TCAM最多有64個處于邊界即落在線上的前綴(現(xiàn)實中很少會超過12個)。

Anigrahy[12]給出了這種方案的基本框架，但并沒有做具體實現(xiàn)，Dong等[13]給出了這種劃分方案的具體算法，并依此劃分方案提出了一種高效的并行TCAM方案， Bin等在文獻[14-16]對林冬等提出的方案進行了進一步改進。下面主要介紹基于地址范圍劃分的并行TCAM的主要思想。

文獻[13]提出了用Preorder-Split算法劃分buckets。這個算法分兩步：首先根據(jù)路由表建立一個Trie樹，然后根據(jù)Trie樹進行劃分分組。具體算法如圖5所示。參數(shù)b代表將要劃分的bucket數(shù)目，輸出結(jié)果是b個子表和b-1個reference nodes，算法用前序遍歷搜索前綴節(jié)點，每遇到一個前綴節(jié)點就存入bucket中并同時壓棧，當(dāng)bucket中的前綴節(jié)點數(shù)達到平均數(shù)時，一個字表就完成了，這時開始出棧并刪除Trie樹對應(yīng)的中無孩子節(jié)點的前綴節(jié)點，直到?？諡橹埂Ｗ钔鈱觲hile循環(huán)結(jié)束時，就形成了b-1個具有相同前綴數(shù)的子表，剩余的前綴放入最后一個子表中。用reference node來計算bucket間的地址邊界，如P*是一個bucket u 的reference node，則bucket[u]的上界是(P0…0 - 1)，bucket [u+1]下界是(P0…0)。這樣就可以得到b個TCAM buckets，并且每個都有一對地址邊界。

圖5　基于地址范圍劃分的算法

圖6展示了如何用Preorder-Split算法劃分了4個buckets。在查找地址a時，只有a落在地址范圍中的bucket[u]所在的blocks被觸發(fā)，處于邊界上的地址前綴會被復(fù)制到兩個毗鄰的buckets中，(0.0.0.0)初始時會被放入到每個bucket中，由于Trie數(shù)層數(shù)一般小于6，所以冗余度一般小于6×buckets數(shù)。

圖6　用Preorder-Split算法劃分舉例

圖7表示了選擇觸發(fā)TCAM block的索引邏輯。它包括并行的比較邏輯和一個索引表，每個比較邏輯對應(yīng)一個TCAM bucket，并且有兩個寄存器來存儲每個bucket的邊界值，索引表中存儲bucket的分布信息，輸出一個用于指示哪個bucket含有與目標(biāo)地址匹配的地址前綴。此索引邏輯方案只有簡單的比較操作所以速度快。

圖7　索引邏輯方案

分配完成后另一個需要考慮的問題是如何動態(tài)的負載均衡，以更好的應(yīng)付突發(fā)流量和提高查找效率。核心路由器中由于流聚集的影響使得流的temporal locality特性較強，所以容易考慮到使用cache的方案。由于TCAM使用block機制，可以選擇TCAM的一些block作為TCAM的邏輯cache。這種機制的具體實施方案如圖8所示。

圖8　基于地址位劃分的并行TCAM體系機構(gòu)

一個包到來后，目的IP地址被取出送到Indexing Logic作比較，Indexing Logic將返回一個partition number指示可能含有匹配前綴的 “home” TCAM，Adaptive Load Balance Logic根據(jù)FIFO隊列的長度(短的優(yōu)先)把IP地址送到home TCAM或其他TCAM中處理。同時處理cache-missed包，這樣會使IP亂序，Re-ordering logic通過時間戳機制來處理亂序問題。所以到來的包會有三種路徑：1) 若被送到home TCAM, 就會匹配的bucket所在的blocks進行查找并輸出結(jié)果。 2) 若被送到一個non-home TCAM, 就會在cache進行查找，如果找到就輸出結(jié)果。3) 若被送到一個non-home TCAM, 如果沒找到就由Feedback邏輯把地址送回home TCAM對應(yīng)的FIFO中處理。

Cache問題：有兩種機制可供選擇。1)緩存目的IP地址。2)緩存地址前綴[17-19]。但緩存目的IP地址所需開銷太大，并且需要大量的緩存空間。所以邏輯緩存采用地址前綴緩存。但也有一個很重要的問題要考慮，比如有兩個地址前綴p和q，而q是p的子孫節(jié)點，若一個請求r的LMP是p，這時p被加入cache中，若另一個請求r’到來時，它的LMP是q，若它被送入cache中處理時，就會輸出錯誤的結(jié)果p。為解決這個問題，采用RRC-ME算法來管理cache。前綴p根據(jù)MEP(Minimal Expansion Prefix)[18]方法被擴展成一個長的前綴，假如路由表中只有兩個前綴1*和111*，對請求1111的MEP為111*,對請求1000的MEP 10*(與1*有相同的地址前綴), 對請求1100的MEP為110*(與1*有相同的地址前綴),由于擴展的前綴都不相交，所以對每個請求就只有一個可能的匹配。這種方法的另一個好處是使cache blocks的更新只需要一個TCAM周期，因為cache中的前綴不需要排序。

這種方案最好情況下的查找速度能達到單個TCAM的k倍，其中k是并行TCAM的個數(shù)。假如每個TCAM的功率消耗為M，每個bucket所占的blocks數(shù)是TCAM中所有blocks數(shù)的1/n，則最大功耗為kM/n，是一種查找效率高而功耗低的查找方案。并且在TCAM數(shù)N>2，平均cache的命中率大于等于(N-2)/(N-1)時，系統(tǒng)的查找速度能達到N-1的加速比。每個bucket中的前綴數(shù)分配平均，擴展性能好。最壞情況下是出現(xiàn)在緩存的命中率為0，這時相當(dāng)于一個TCAM在處理所有任務(wù)。另外還有一個可認為比較致命的問題是在緩存更新時，所有的TCAM不能進行查找，所以作者提出了慢速更新的思想，即每兩次更新間隔一個固定的時間，但這又影響了緩存的命中率，更新間隔和命中率之間需要取一個折中以獲得更好的效率，為此作者做了大量的實驗。更新效率為O(N/k)，其中N為路由表項，k為并行TCAM數(shù)，更新時需注意對于跨多個buckets的前綴項需要同時更新。

4方案比較

下面，我們從路由查找速度、功耗和更新效率三個方面簡要比較前述三類方案。表1列出了三類方案的比較，可以看到，基于端口和基于無子孫關(guān)系前綴集合的方法主要是提高更新效率，這兩種方案的更新效率可以達到O(1)。但是，這兩種方案和采用單個TCAM進行路由查找[20]的方案相比，在查找速度和功耗上并沒有改善。因為這兩種方案每進行一次路由查找，所有TCAM分片都需要為一次路由查找進行并行查找，效率低功耗大。基于CoolCAMs的方案可以將一次路由查找分配到不同的TCAM分片或block上，因此，如果有k個TCAM分片，可以達到查找速度上的將近k倍加速，大大提高了路由的查找效率，并且由于采用CoolCAM技術(shù)，大大降低了設(shè)備功耗。但在更新效率相比于前兩種方案相對較低，但相比于單個TCAM的查找方案其更新效率有所提高。對于N為路由表項，單個TCAM的查找方案的更新效率為O(N)[21]，并行方案的更新效率為O(N/k)，其中k為并行TCAM數(shù)。

表1　基于TCAM的并行路由查找方案對比

基于CoolCAM技術(shù)的三種方案路由查找速度、功耗和更新效率在具體闡述其方法時已作了詳細分析，這里不再贅述。總的來說基于Trie樹、基于地址位、基于地址范圍這三種方案的整體效率是逐步提升的，但仍然存在一些不足和有待改進的地方。

5目前方案不足及改進

總體來看，目前基于并行TCAM的路由查找方案在逐步進展和完善，但仍存在下列不足之處：

? 位劃分方案過于簡單，在進行基于位對路由表進行劃分時，缺少可信的調(diào)研數(shù)據(jù)[22]，只是簡單地用第15、16位進行劃分。另外對位劃分方案缺少足夠的闡述?；诘刂贩秶鷦澐值姆桨鸽m然有很大程度上的改進，但仍然缺乏考慮流量本身的特性造成不同地址范圍地址數(shù)量的巨大不均衡問題。

? 基于地址位的并行方案過于簡單，只是用第15、16位劃分劃分的四個分區(qū)放入4個并行的TCAM中，未考慮動態(tài)的負載均衡，未提出用冗余的部分來平衡流量以加快查找速度的思想；基于地址范圍劃分的方案雖然考慮了一定的動態(tài)負載均衡，但并未能充分利用TCAM的剩余空間進行負載均衡[23,24]；緩存機制的效率有待進一步研究[25,26]。

? 對并行處理中的報文亂序問題沒有足夠重視，沒有一套專門處理報文亂序問題的機制。

? 新的方案雖然極大地提高了路由的查找效率，而TCAM中路由條目的更新效率并沒有得到很好的提升。

? 未能充分考慮在IPV6網(wǎng)絡(luò)環(huán)境下部署的情況。

由于前兩個問題的改進需要設(shè)計一整套的改進方案和提出一個完整的體系結(jié)構(gòu)，不屬于本文的研究范圍，下面我們針對后面兩個具體的問題探索可能的改進措施。

首先我們探索一種保持包的查找次序的機制。由于在進行查找時包會去往不同的TCAM的輸入隊列，而每個TCAM的輸入隊列中的排隊的包的數(shù)目不同，如果順序到來的兩個包a和b，a到來后被送入一個比較長的輸入隊列中，b雖然后到，但到后有可能送入到一個很短的輸入隊列中，這時b就可能先于a進行處理，就出現(xiàn)了包亂序的情況。處理包亂序的問題一種常見的機制就是在包被送入不同的輸入隊列前加一個含有時間戳的標(biāo)記，在輸出隊列中根據(jù)時間戳排序后再進行輸出。也可以用序號生成器加一個含序號的標(biāo)簽，輸出時按序號進行排序，但序號生成器所生成序號的大小要能保證若最小序號的標(biāo)簽和最大序號的標(biāo)簽同時出現(xiàn)在輸出隊列中一定是含最小序號的標(biāo)簽在含最大序號標(biāo)簽的包之后。

下面，我們探索如何進一步改進TCAM的更新效率。前面我們談到方案的更新效率為O(N/k)，其中N為路由表項，k為并行TCAM數(shù)，是否有更好的方案達到更高的更新效率？由于這種方案的更新是在每個bucket中進行更新，下面我們探索一種可以在每個bucket中部署的快速更新方案?；舅枷虢⒂谌粢粋€集合中的所有地址前綴無子孫關(guān)系或不為互為前綴關(guān)系(我們稱這種關(guān)系為disjoint)，則集合中所有前綴所包含的地址范圍映射到一維地址空間上無地址重疊關(guān)系，如梁志勇等[27]就提出了一種基于這種非重疊前綴集合的并行路由查找算法，用軟件的方式對算法進行了描述，并且提出未來可以考慮用硬件實現(xiàn)。因此，在這種前綴關(guān)系下，在進行地址查找時這個集合至多只有一個匹配項，也就是說集合中所有項的順序沒有任何關(guān)系，進一步就相當(dāng)于只有具有子孫關(guān)系的前綴項在位置上要保持好前后順序，即在進行插入和刪除時只要保持好Trie數(shù)中的子孫關(guān)系就可以保證LMP。

經(jīng)過調(diào)研目前路由表的前綴Trie樹一般不超過7層(包括*),具體到bucket中某些位劃分成的子表，層數(shù)會更少，所以這時的更新效率會更高，一般小于O(7)，與路由表項無任何關(guān)系，不足之處是需要保存bucket中的Trie樹。

關(guān)于在IPv6網(wǎng)絡(luò)環(huán)境下如何部署目前提出的高速并向路由查找算法，當(dāng)前工作大部分都是簡單提到，沒有充分考慮真實部署時需要關(guān)注的各種因素。Tong Yang等[28]在他們最新的工作中提出一種分裂算法，并把算法部署到CPU,FPGA,GPU等硬件上進行了測試，驗證了算法的高效性。最后，提出了在IPv6上的部署問題，由于目前IPv6的FIB表的表項要遠遠小于IPv4中心路由器的表項，首先硬件的容量在實際部署時不成問題，一個主要考慮的問題是IPv6有128個地址位，而IPv4只有32位。但實際上IPv6的網(wǎng)絡(luò)地址只有64位，剩下64位為主機地址，作者建議將64位網(wǎng)絡(luò)地址按16，24，32，40，48，64劃分成6層適配到Trie樹節(jié)點中，而對于并行TCAM方案在IPv6實際環(huán)境中的部署，也主要是要考慮和IPv4地址位數(shù)的差別。不同的方案部署時考慮的因素不同，比如按位劃分的方案就需要對IPv6的FIB表進行實際分析，看看哪幾位的組合更能平均劃分FIB表項；基于TRIE樹和基于地址范圍的方案只需要將算法進行簡單擴展，用于IPv6的地址位即可。

6結(jié)語

由于TCAM自身的優(yōu)良特性，使得它在核心和高端路由器上得到越來越多的應(yīng)用，其應(yīng)用范圍也越來越廣。從路由查找到流分類和防火墻的應(yīng)用，其中對TCAM的要求也越來越高，如何高效節(jié)能地利用TCAM將會受到越來越多的關(guān)注和研究。我們分析了使用TCAM進行路由查找的背景和存在的挑戰(zhàn)，總結(jié)了在用TCAM進行路由查找時應(yīng)解決的三個主要問題：查找速度，功耗和更新效率。為了更好地解決面臨的問題，人們提出了不同的并行解決方案。文中調(diào)研了不同的并行方案，并分析了不同方案的優(yōu)缺點，總體來說是不斷改進的六種方案。針對目前提出的并行方案，分析了存在的不足，并提出了可能的改進。

參考文獻

[1] Ruiz-Sanchez M A,Biersack E W,Dabbous W.Survey and Taxonomy of IP Address Lookup Algorithms[J].IEEE Network 2001,15(2):8-23.

[2] Gupta P,Lin S,McKeown N.Routing lookups in hardware at memory access speed[C]//Proceedings of IEEE INFOCOM’98,San Francisco,April 1998:1240-1247.

[3] Nenfu Huang,Shiming Zhao,Jenyi Pan.A fast IP routing lookup scheme for gigabits switching routers[C]//Proceedings of IEEE INFOCOM,1999:1429-1436.

[4] Daxiao Yu,Smith B C,Wei B.Forwarding engine for fast routing lookups and updates[C]//Proceedings of IEEE GLOBECOM,1999:1556-1564.

[5] Huston G.Route Table Analysis Reports.http://bgp.potaroo.net/.

[6] CYRESS.http://www.cypress.com/.

[7] Ng E,Lee G.Eliminating Sorting in IP Lookup Devices using Partitioned Table[C]//Proceedings of 16th IEEE International Conf.on Application-Specific Systems,Architecture and Processors(ASAP),2005:119-126.IEEE Press, Greece.

[8] Jinsoo Kim,Junghwan Kim.An Efficient IP Lookup Architecture with Fast Update Using Single-Match TCAMs[C]//Proceedings of WWIC 2008:104-114.

[9] Zane F,Narlikar G,Basu A.CoolCAMs:Power-Efficient TCAMs for Forwarding Engines[C]//Proceedings of INFOCOM,2003:42-52.

[10] Kai Zheng,Chengchen Hu,Hongbin Liu,et al.An ultra-high throughput and power efficient TCAM-based IP lookup engine[C]//Proceedings of INFOCOM, March 2004:1984-1994.

[11] Xin Zhang,Bin Liu,Wei Li,et al.IPv6-oriented 4*OC768 Packet Classification with Deriving-Merging Partition and Field-Variable Encoding Algorithm[C]//Proceedings of INFOCOM,Spain,April 2006.

[12] Anigrahy R,Sharma S.Reducing TCAM Power Consumption and Increasing Throughput[C]//Proceedings of HotTI August 2002:107-112.

[13] Dong Lin,Yue Zhang,Chengchen Hu,et al.Smart Route Table Partitioning and Novel Load Balancing for Parallel Searching with TCAMs[C]//Proceedings of 21st IEEE International Parallel & Distributed Processing Symposium (IPDPS), Long Beach, California USA,2007.

[14] Bin Zhang,Jianping Wu,Qi Li,et al.Efficient Parallel Searching with TCAMs IEEE 18th InternationalWorkshop on Quality of Service[C]//IWQoS, Beijing, China ,2010:1-2.

[15] Bin Zhang,Jiahai Yang,Jianping Wu,et al.An Efficient Parallel TCAM Scheme for the Forwarding Engine of the Next-generation Router[C]//IFIP/IEEE Int’l Symp. On Integrated Network Management, May 22-27, IM, Dublin, Ireland, 2011:454-461.

[16] Bin Zhang,Jiahai Yang,Jianping Wu,et al.Efficient Searching with Parallel TCAM Chips[C]//The 35th IEEE Conference on Local Computer Networks, LCN 2010, Denver, Colorado, U.S.A 11-14 Oct. 2010.

[17] WoeiLuen Shyu,ChengShong Wu,TingChao Hou.Efficiency Analyses on Routing Cache Replacement Algorithms[C]//Proceedings of ICC’2002, Vol.4, April/May 2002:2232-2236.

[18] Tzicker Chiueh,Prashant Pradhan.High-Performance IP Routing table Lookup Using CPU Caching[C]//Proceedings of INFOCOM’99, Vol.3, March 1999:1421-1428.

[19] Bryan Talbot,Timothy Sherwood,Bill Lin.IP Caching for Terabit Speed Routers[C]//Proceedings of GLOBECOM, Vol.2, DEC 1999:1565-1569.

[20] Huang N,Zhao M,Pan J.A fast ip routing lookup scheme for gigabits switching routers[C]//IEEE INFOCOM,1999.

[21] Yu D,Wei B S B.Forwarding engine for fast routing lookups and updates[C]//IEEE GLOBECOM,1999.

[22] Huston G.Route table analysis reports[EB/OL].http://bgp.potaroo.net/.

[23] Shyu W,Wu C,Hou T.Efficiency analyses on routing cache replacement algorithms[C]//IEEE International Conference on Communications,2002.

[24] Chiueh T,Pradhan P.High-performance ip routing table lookup using cpu caching[C]//IEEE INFOCOM,1999.

[25] Talbot B,Sherwood T,Lin B.Ip caching for terabit speed routers[C]//IEEE GLOBECOM,1999.

[26] Mohammad J,Akhbarizadeh M,Nourani M.Efficient prefix cache for network processors[C]//The 12th Annual IEEE Symposium on High Performance Interconnects,2004.

[27] 梁志勇,徐恪,吳建平,等.基于非重疊前綴集合的并行路由查找系統(tǒng)[J].電子學(xué)報,2004,32(8):1277-1281.

[28] Tong Yang,Gaogang Xie,YanBiao Li,et al.Guarantee IP Lookup Performance with FIB Explosion[C]//Proceedings of SIGCOMM,Chicago,USA,Aug.2014.

收稿日期：2014-12-26。國家自然科學(xué)基金項目(61462009)；江蘇省博士后科研項目(1402138C)；河南省教育廳科技計劃項目(13B52 0337)。王輝，講師，主研領(lǐng)域：信息系統(tǒng)。李曉歌，講師。張賓，工程師。秦董洪，副教授。

中圖分類號TP393

文獻標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.033

SURVEY ON TCAM-BASED PARALLEL IP ROUTE LOOKUP SCHEME

Wang Hui1Li Xiaoge1Zhang Bin2Qin Donghong3

1(DepartmentofAutomationandControl,HenanUniversityofAnimalHusbandryandEconomy,Zhengzhou450000,Henan,China)2(The63rdResearchInstituteofPLAGeneralStaffHeadquarters,Nanjing210007,Jiangsu,China)3(SchoolofInformationScienceandEngineering,GuangxiUniversityforNationalities,Nanning530006,Guangxi,China)

AbstractThe IP route lookup scheme based on TCAM (ternary content-addressable memory) is the widely used scheme by high-performance routes in route lookup at present. However the scheme still faces challenges in lookup performance, power consumption and update efficiency. Therefore, scholars proposed various parallel TCAM solutions to improve lookup performance, reduce power consumption and enhance update efficiency. This paper gives the classified summarisation on current parallel TCAM IP route lookup schemes, analyses the pros and cons of them, and points out the drawbacks of these schemes as well as explores some corresponding solutions.

KeywordsParallel TCAMIP route lookupPower consumptionAddress division