基于Trie的流水式IP查找結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、網(wǎng)絡(luò)速度的飛速發(fā)展對(duì)網(wǎng)絡(luò)搜索引擎提出了新的要求。應(yīng)運(yùn)而生的是各種硬件搜索引擎，最為常用的是基于TCAM（三態(tài)按內(nèi)容可尋址存儲(chǔ)器）的硬件搜索結(jié)構(gòu)，它是一種并行搜索的硬件結(jié)構(gòu)，具有較高的搜索速度，因此被廣泛應(yīng)用于各種高速網(wǎng)絡(luò)搜索引擎中。然而TCAM的并行性導(dǎo)致其功耗特別高。而且TCAM結(jié)構(gòu)較為復(fù)雜，一個(gè)典型的TCAM單元由14個(gè)晶體管組成，由它組成的搜索引擎面積很大，不利于擴(kuò)展。因此它不適用于下一代高速網(wǎng)絡(luò)應(yīng)用。人們著眼于新的高速搜索解決方

2、案。一種很好的解決方案是算法與硬件結(jié)合的解決方式。比較熱門(mén)的主要有基于hash的硬件結(jié)構(gòu)和基于 Trie的硬件實(shí)現(xiàn)。而基于 Trie的硬件實(shí)現(xiàn)方案被認(rèn)為是下一代搜索引擎的最佳選擇。為了進(jìn)一步提高吞吐量，需要采用流水線的設(shè)計(jì)方案。但傳統(tǒng)的基于Trie的硬件實(shí)現(xiàn)方式存在流水線內(nèi)存分配不均，負(fù)載不均衡等問(wèn)題?；趦?yōu)化的線性流水線（OLP）方案，能均勻的分配每級(jí)流水線的任務(wù)，能實(shí)現(xiàn)每周期一次查找，但是該方案流水線級(jí)數(shù)太長(zhǎng)，導(dǎo)致查找延時(shí)過(guò)長(zhǎng)，且該

3、方案存在節(jié)點(diǎn)布局不完整的問(wèn)題，因此，該方案值得進(jìn)一步研究。
　　本文研究了基于Trie的流水線實(shí)現(xiàn)方式，基于優(yōu)化的線性流水線（OLP）方案，提出了一種EOLP（Enhanced Optimized Linear Pipeline）方案。首先是前綴擴(kuò)展長(zhǎng)度確立算法，有效的確定了每級(jí)流水線 SRAM的大小，有利于減少流水線的級(jí)數(shù)；其次本文提出了新的節(jié)點(diǎn)布局算法，解決了原有 OLP算法可能無(wú)法布局完節(jié)點(diǎn)的不足。最后，本文提出編碼算法，能

4、將節(jié)點(diǎn)有效的編碼，使得其可在 SRAM進(jìn)行索引操作。為了驗(yàn)證EOLP方案的可行性，本文將方案在FPGA上進(jìn)行了實(shí)現(xiàn)和驗(yàn)證。FPGA實(shí)驗(yàn)結(jié)果表明，相對(duì)于OLP方案，EOLP方案的內(nèi)存占用和流水線延時(shí)至少減少了1/6，并克服了可能無(wú)法完全布局節(jié)點(diǎn)的問(wèn)題，同時(shí)達(dá)到了72Gbps的吞吐率，滿足高速網(wǎng)絡(luò)的需求。最后，在通過(guò)FPGA驗(yàn)證之后，針對(duì)典型路由表rrc（容量為50K條），本文做了專(zhuān)用集成電路（ASIC）的版圖實(shí)現(xiàn)。采用Global Fou