A new TCAM Design For Longest Prefix Matching

三元內容定址記憶體(TCAM)是一種硬體的儲存元件，因為它能平行比對所有的資料，所以可以加速搜尋的效能。在這篇論文中，我們提出了一個高效能TCAM設計，來解決最長字首比對(LPM)的問題。與傳統最長字首比對(LPM)解決方法的比較，我們所提出的三元內容定址記憶體(TCAM)不需要把字首(prefix)按照長度的順序儲存，而且不需要優先權編碼器就可以解決最長字首比對(LPM)的問題。我們的設計可以使用管線化的技術，大幅提升路由器效能且快速簡單的更新資料。使用台積電0.18微米製程和1.8V的供應電壓來實做並驗証我們的設計，可在100MHz的操作頻率下，正常工作。Ternary Content Addressable Memory is a kind of hardware storage component that can speed up search performance. This paper proposes a high performance TCAM design to solve the longest prefix matching (LPM) problem. Compared to the traditional LPM solution, the proposed TCAM does not need to store prefix information based on descending prefix length, and can remove the priority encoder. By using pipeline technique, our design can perform one IP lookup per cycle. This study uses the TSMC 0.18 μm CMOS process with 1.8V supply voltage to verify the accuracy of the proposed design. The maximum frequency of the proposed structure is 100 MHz.摘要 i Abstract iii 目錄 v 圖目錄 vi 1、 簡介 1 2、 傳統TCAM架構和LPM架構簡介 4 2.1、傳統TCAM架構 4 2.2、最長字首比對(Longest Prefix Matching,LPM) 12 3、 相關研究 23 3.1、VLMP 23 3.2、HLMP 25 3.3、PCAM 27 3.4、Ripple-Precharge TCAM 29 4、 高效能TCAM應用在最長字首比對 32 4.1、架構和流程說明 33 4.2、Step1.搜尋所有相符的字首(Search prefix) 37 4.3、Step2.尋找最長字首長度(Find longest prefix) 40 4.4、Step3.尋找最長字首比對(Find longest prefix match) 43 5、 晶片製作 49 5.1、晶片製作流程 50 5.2、晶片佈局圖 51 6、 模擬結果 55 7、 結論 62 8、 未來展望 63 9、 參考文獻 6