流分類技術的研究和硬件實現(xiàn).pdf

1、本文首先對路由器的發(fā)展的現(xiàn)狀和將來的發(fā)展方向進行了一個概述，將來的路由器，會提供更大的容量和更高的端口速率、有QoS的保證、還將具有支持綜合業(yè)務迅速成長需求的能力。 然后本文從時間復雜度，空間復雜度等方面對比了多種分類算法，分析了各自的優(yōu)劣。還針對硬件的實現(xiàn)結(jié)構(gòu)進行了分析，并提出了一個好的分類算法要達到的要求。 接著，本文重點介紹了基于d-left算法和片內(nèi)CAM的硬件哈希表解決方案。此算法可以通過一次查表操作獲得結(jié)果，

2、解決了一般哈希表存在的最壞訪問時間的問題。利用片內(nèi)CAM使哈希表的加入失敗概率降到可以忽略的程度，同時提高了存儲器的利用率。在實現(xiàn)方面，Hash函數(shù)我們采用CRC,還可以按照設計需要折中考慮存儲器利用率、加入失敗概率、占用片內(nèi)CAM資源多少以及硬件實現(xiàn)復雜度等因素，具有很好的靈活性和可擴展性。將之應用到基于哈希表的硬件報文分類算法中，可以有效的提高其處理性能。仿真和應用證明其有很好的可行性和實用性。 最后，介紹了一下我在實驗室的