隨著經(jīng)濟社會的發(fā)展,網(wǎng)絡變得越來越普及,互聯(lián)網(wǎng)已經(jīng)成為這個社會不可缺少的一部分。而隨著網(wǎng)絡的普及與發(fā)展,也凸顯出一系列的問題和矛盾。主要有網(wǎng)絡流量的快速增長與現(xiàn)有網(wǎng)絡設(shè)備的轉(zhuǎn)發(fā)處理速度之間的矛盾,還有人們?nèi)找嬖鲩L的對一個安全的網(wǎng)絡環(huán)境的需求與現(xiàn)有網(wǎng)絡環(huán)境存在諸多安全隱患之間的矛盾。不管是數(shù)據(jù)轉(zhuǎn)發(fā)的現(xiàn)實需求,還是網(wǎng)絡安全的現(xiàn)實需求,對于數(shù)據(jù)流量關(guān)鍵字段的精確查找都是實現(xiàn)其功能的基礎(chǔ),所以快速的、準確的、低成本的精確查找的實現(xiàn)就顯得尤為重要�；诖�,本文設(shè)計了一種基于可編程邏輯門陣列的精確查找結(jié)構(gòu)。通過借鑒學習基于布隆過濾器的匹配查找,基于正則表達式的匹配查找,和基于已有內(nèi)容可尋址芯片的查找匹配方法。通過對以上三種實現(xiàn)方式進行理論分析,比較這三種方法實現(xiàn)的難易程度、復雜程度、開發(fā)成本、價格成本以及實現(xiàn)效果分析,并通過模擬仿真比較,最終提出了基于布隆過濾器的查找匹配方法。在布隆過濾器的基礎(chǔ)上,改造了原先的普通的布隆過濾器,設(shè)計了一種適用于硬件維護的并且可刪除元素的布隆過濾器,使布隆過濾器經(jīng)過改造可以適用于查找表設(shè)計,并理論計算和實驗仿真分析其可刪除率;并且設(shè)計了一種兩級流水的布隆過濾器的實現(xiàn)... 

【文章來源】：中國電子科技集團公司電子科學研究院北京市

【文章頁數(shù)】：79 頁

【學位級別】：碩士

【部分圖文】：

正則表達式仿真結(jié)果

圖 2.6 布隆過濾器誤檢率分析通過公式(2.1)和(2.2)能得出結(jié)論，在最好的狀況時，可以由 1<來表示誤檢率的最小值，那么就可以得出有如下的公式：In2nmk （2.3）這時的誤檢率如下公式： kf 12（2.4）由此得出結(jié)論，若誤檢率的值一定的時候，所需要的 m（二進制向量的長度）與 n（元素的數(shù)量）互為比例的增加或減少。工程實現(xiàn)時，在誤撿率小至一定的值時，可以近似的認為布隆過濾器可以準確的判定一個元素是否屬于某個集合。2.2.2.3 布隆過濾器仿真分析由于布隆過濾器需要進行哈希計算，對于純軟件平臺來說，這會大大降低其實現(xiàn)的性能，由于純軟件平臺本身的性能相對較低，所以這里對于純軟件實現(xiàn)布隆過濾器不做討論。

的字段按同樣的方法進行計算，然后依次和這個布隆過濾器的比特位進行比較，由此來判斷該字段是否屬于該集合。并維持一個 hit 信號，當其為 1 時代表其匹配成功，反之則匹配失敗。datain 緩存fifo dataout關(guān)鍵字提取64bitCRC（1）CRC（5）..Bloom Filter hit 丟棄圖 2.7 一個簡單布隆過濾器的實現(xiàn)布隆過濾器查找匹配字段的時序圖如下所示，布隆過濾器完成待匹配字段的“編程”寫入。對于一個輸入的數(shù)據(jù) datain（在 datain_val 有效），在等待一定的延時后可以看到，hit 值變?yōu)?1，則說明該 datain 匹配于該布隆過濾器，那么則將該數(shù)據(jù)包放行，而第二個輸入 datain 則沒有出現(xiàn) hit 信號為 1 的情況，則說明該datain 不匹配于該布隆過濾器，那么則將該數(shù)據(jù)包丟棄。

【參考文獻】：
期刊論文
[1]一種基于FPGA壓縮DFA的高速正則表達式匹配算法[J]. 譚用秋,唐球,譚建龍.  電子技術(shù). 2014(08)
[2]基于FPGA的高速低資源消耗字符串匹配算法[J]. 黃建,徐晶.  微電子學與計算機. 2007(11)
[3]一種將NFA到最小化DFA的方法[J]. 毛紅梅,聶承啟.  計算機與現(xiàn)代化. 2004(10)
[4]構(gòu)造正則表達式的簡化 DFA 算法[J]. 檀鳳琴.  北京航空航天大學學報. 1998(04)

博士論文
[1]下一代互聯(lián)網(wǎng)的報文標識與查找技術(shù)的研究[D]. 孫瓊.北京郵電大學 2010

碩士論文
[1]基于FPGA的正則表達式匹配引擎的設(shè)計[D]. 溫源.哈爾濱工程大學 2009
[2]正則表達式在電信業(yè)務處理中的應用研究[D]. 李哲夫.暨南大學 2008
[3]基于正則表達式的深度包檢測研究[D]. 張娜.華東師范大學 2007
[4]基于正則表達式技術(shù)的信息搜集引擎應用研究[D]. 馬俊.電子科技大學 2006
[5]集成化防火墻防護系統(tǒng)[D]. 王皎.電子科技大學 2003



本文編號：3463729