路由查找算法的研究及其FPGA實現(xiàn).pdf

1、本論文在綜合了國內(nèi)外近年來在路由查找算法及其實現(xiàn)以及相關(guān)技術(shù)研究進展的基礎(chǔ)上，經(jīng)過系統(tǒng)深入的研究，采用RAM和TCAM結(jié)合的TreeBitmap結(jié)構(gòu)的算法進行路由查找的實現(xiàn)，并下載到Xilinx公司的VirtexⅡ系列xc2v1000器件中，經(jīng)驗證功能正確。 本文的特點和創(chuàng)新之處包括： 1.對現(xiàn)有的軟件和硬件實現(xiàn)的路由查找算法進行了空間和時間復(fù)雜度的分析和比較。 2.根據(jù)路由前綴分布的特點，特別是最近幾年路由前綴

2、長度大于24位的路由項大幅增加，所以把路由前綴項大于23位的路由項存儲在TCAM中，而把其他的路由前綴項使用BitmapTree結(jié)構(gòu)存儲在RAM中，這樣就可以同時進行在RAM和TCAM中進行路由查找，加快查找速度。 3.對于存儲在RAM中TreeBitmap結(jié)構(gòu)中的InternalPrefix和ExtendingPath同時進行處理，進行路由地址的查找。這樣就可以避免回溯訪問BitmapTree，減少了訪問RAM的次數(shù)，加快了路

3、由查找的速度。 4.完成了使用此路由查找算法的路由前驅(qū)引擎的設(shè)計，在前驅(qū)引擎中完成數(shù)據(jù)包的接收、修改TLL域、校驗域的計算和更新。 5.所有硬件實現(xiàn)模塊使用Top-Down的設(shè)計方法，用Verilog代碼進行代碼編寫，并在Xilinx公司的XST軟件中進行了綜合以及最后的下載驗證，下載至xc2v1000器件中，經(jīng)驗證功能正確。經(jīng)XST工具綜合，整個模塊的速度可達到88MHz，可以滿足0C-48高速路由查找的要求。