王　輝　李曉歌　張　賓　秦董洪

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

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

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

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

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

? 查找速度

? 功耗

? 更新效率

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

1基于端口的并行方案

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

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

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

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

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

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

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

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

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

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

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

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

? 基于Trie樹(shù)劃分

? 基于地址位劃分

? 基于地址范圍劃分

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

3.1基于Trie樹(shù)劃分的并行TCAM方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖7　索引邏輯方案

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

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

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

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

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

4方案比較

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

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

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

5目前方案不足及改進(jìn)

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

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

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

? 對(duì)并行處理中的報(bào)文亂序問(wèn)題沒(méi)有足夠重視，沒(méi)有一套專門(mén)處理報(bào)文亂序問(wèn)題的機(jī)制。

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

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

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

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

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

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

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

6結(jié)語(yǔ)

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

參考文獻(xiàn)

[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é)報(bào),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。國(guó)家自然科學(xué)基金項(xiàng)目(61462009)；江蘇省博士后科研項(xiàng)目(1402138C)；河南省教育廳科技計(jì)劃項(xiàng)目(13B52 0337)。王輝，講師，主研領(lǐng)域：信息系統(tǒng)。李曉歌，講師。張賓，工程師。秦董洪，副教授。

中圖分類號(hào)TP393

文獻(xiàn)標(biāo)識(shí)碼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