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

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

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

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

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