正則表達(dá)式是一種熱門的字符匹配技術(shù),在BGP路由協(xié)議中得到了重要的應(yīng)用,本文的研究內(nèi)容的是如何提高正則表達(dá)式的匹配速度。在BGP路由協(xié)議中,正則表達(dá)式通過軟件實現(xiàn)的方式用于路由信息過濾,但大量的過濾事務(wù)和自身效率問題在一定程度上影響了BGP的性能,如何提高正則表達(dá)式的匹配速度是解決問題的關(guān)鍵。在這樣的項目需求下,本研究課題應(yīng)運(yùn)而生。 經(jīng)過對國內(nèi)外關(guān)于正則表達(dá)式的實現(xiàn)技術(shù)進(jìn)行了調(diào)研,本文提出了一種新的正則表達(dá)式實現(xiàn)技術(shù),它以BGP網(wǎng)絡(luò)路由協(xié)議的應(yīng)用為背景,以嵌入式平臺為運(yùn)行環(huán)境,采用了POSIX正則表達(dá)式庫的軟件算法,結(jié)合軟件平臺的靈活和硬件平臺的高效,使得嵌入式Linux軟件系統(tǒng)和FPGA硬件協(xié)同工作,通過硬件加速的方式完成了對正則表達(dá)式的匹配。 具體實施中,系統(tǒng)被劃分成了軟件系統(tǒng)模塊、硬件系統(tǒng)模塊和負(fù)責(zé)軟硬件通信的接口等三個組成部分。輸入的正則表達(dá)式和字符串首先進(jìn)入軟件系統(tǒng)模塊,它基于嵌入式Linux軟件系統(tǒng)實現(xiàn),結(jié)合堆棧技術(shù),把正則表達(dá)式編譯成為機(jī)器能識別并執(zhí)行的執(zhí)行碼指令,并生成fastmap數(shù)據(jù)。因為軟件系統(tǒng)模塊和硬件系統(tǒng)模塊的實現(xiàn)平臺不同,運(yùn)行速度級別也有差異,故通信接口負(fù)責(zé)它們之間的數(shù)據(jù)傳輸。硬件系統(tǒng)模塊基于FPGA實現(xiàn),結(jié)合堆棧技術(shù),根據(jù)得到的執(zhí)行碼、字符串和fastmap數(shù)據(jù)來完成正則表達(dá)式的匹配計算,得到最終是否匹配的結(jié)果。 在整體設(shè)計中,系統(tǒng)具有“硬件加速”、“默認(rèn)使用最短匹配原則”和“放棄計算匹配細(xì)節(jié)”等獨(dú)到的設(shè)計特點(diǎn),系統(tǒng)內(nèi)部高效運(yùn)作,很好地完成了設(shè)計任務(wù)。文章在最后給出的邏輯測試和性能測試證明,系統(tǒng)不僅很好地完成了設(shè)計邏輯,并且擁有良好的加速效果,表明了本次科研設(shè)計是成功的。 本文的創(chuàng)新和貢獻(xiàn)在于:(1)總結(jié)了當(dāng)前各種正則表達(dá)式的實現(xiàn)技術(shù),結(jié)合了軟件解決方案和硬件解決方案的優(yōu)點(diǎn),創(chuàng)新出軟硬件協(xié)同工作的解決方案。(2)在嵌入式領(lǐng)域上提高了正則表達(dá)式的匹配速度,有力地支持了路由器等設(shè)備,拓展了正則表達(dá)式在嵌入式平臺上的應(yīng)用領(lǐng)域。
【學(xué)位單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2010
【中圖分類】：TP368.1
【部分圖文】：

圖 2-1 構(gòu)造自動機(jī)原理圖Fig. 2-1 principle graph of making automaton由正則表達(dá)式構(gòu)造出自動機(jī)的過程，如圖 2-1 所示。首先，正則表達(dá)式被解樹，然后再轉(zhuǎn)換成非確定有限自動機(jī)。目前，從解析樹構(gòu)造非確定有限自用方法有湯姆遜（Thompson）構(gòu)造法[9]和格拉施科夫（Glushkov）構(gòu)造法[9非確定有限自動機(jī)后，可以直接用它進(jìn)行文本匹配，也可以將它確定化和構(gòu)造出相應(yīng)的確定有限自動機(jī)，然后用確定有限自動機(jī)進(jìn)行文本匹配。3 正則表達(dá)式軟件實現(xiàn)的相關(guān)研究目前的軟件平臺上，C、C++、Java 等編程語言都有支持正則表達(dá)式的語法，各有優(yōu)缺點(diǎn)，在這些實現(xiàn)方法中，不少方法用到了自動機(jī)理論的知識，實現(xiàn)正則表達(dá)式的算法，都是可以值得借鑒的。以下是支持正則表達(dá)式的和軟件庫：

通大學(xué)工程碩士學(xué)位論文 第三章程中，只要發(fā)現(xiàn)有部分字符串符合正則表達(dá)式的規(guī)則，即宣告匹配成功，而不尋找符合要求的、長度更長的字符串；“放棄計算匹配細(xì)節(jié)”指的是放棄匹配細(xì)計算，諸如不計算出“字符串中共有多少部分的字符信息符合要求”等。以上設(shè)計特點(diǎn)，都是結(jié)合課題應(yīng)用背景需求，減少計算，為了更好地實現(xiàn)加速匹配。 系統(tǒng)設(shè)計與實現(xiàn)構(gòu)架在本次設(shè)計中，采用軟件和硬件相結(jié)合的方式來實現(xiàn)系統(tǒng)功能，軟件平臺采用嵌 Linux 系統(tǒng)，它能提供很好的軟件開發(fā)平臺，而硬件平臺采用 FPGA 芯片，它程的特點(diǎn)，提供了硬件開發(fā)過程中能不斷調(diào)試的機(jī)會，并且自身優(yōu)良的性能可速實現(xiàn)正則表達(dá)式的匹配計算。

工程碩士學(xué)位論文 第四章 軟件系統(tǒng)模塊設(shè)計系統(tǒng)模塊概述上一章節(jié)介紹，我們得知整體系統(tǒng)設(shè)計劃分為三個組成部分，本章節(jié)件系統(tǒng)模塊進(jìn)行介紹。系統(tǒng)模塊是基于 Linux 操作系統(tǒng)實現(xiàn)的，屬于 Linux 操作系統(tǒng)的應(yīng)用程其被封裝成 regcomp 函數(shù)模塊，所實現(xiàn)的功能是提供調(diào)用接口給用戶的編譯和 fastmap 數(shù)據(jù)生成、同硬件系統(tǒng)模塊通信。

【參考文獻(xiàn)】

相關(guān)期刊論文 前5條

1 葉梅;趙京偉;初元萍;;嵌入式Linux系統(tǒng)在PowerPC上的實現(xiàn)[J];核電子學(xué)與探測技術(shù);2006年05期

2 買培培;邵東暉;蘇濤;;Linux在Xilinx FPGA上的移植[J];火控雷達(dá)技術(shù);2009年04期

3 潘建,董金祥;基于GNU工具鏈的嵌入式操作系統(tǒng)開發(fā)[J];計算機(jī)工程與應(yīng)用;2004年26期

4 張宇;馮丹;;基于Xilinx SoPC的可重構(gòu)嵌入式計算系統(tǒng)的研究與設(shè)計[J];計算機(jī)科學(xué);2010年05期

5 夏軍波;車建國;楊建文;石磊;;基于硬件的快速正則表達(dá)式匹配方法[J];通信技術(shù);2010年01期

本文編號：2820003