BGP協(xié)議中正則表達(dá)式匹配系統(tǒng)的研究與軟硬件實(shí)現(xiàn).pdf

1、正則表達(dá)式是一種熱門的字符匹配技術(shù)，在BGP路由協(xié)議中得到了重要的應(yīng)用，本文的研究內(nèi)容的是如何提高正則表達(dá)式的匹配速度。在BGP路由協(xié)議中，正則表達(dá)式通過軟件實(shí)現(xiàn)的方式用于路由信息過濾，但大量的過濾事務(wù)和自身效率問題在一定程度上影響了BGP的性能，如何提高正則表達(dá)式的匹配速度是解決問題的關(guān)鍵。在這樣的項(xiàng)目需求下，本研究課題應(yīng)運(yùn)而生。經(jīng)過對國內(nèi)外關(guān)于正則表達(dá)式的實(shí)現(xiàn)技術(shù)進(jìn)行了調(diào)研，本文提出了一種新的正則表達(dá)式實(shí)現(xiàn)技術(shù)，它以BGP網(wǎng)絡(luò)路由協(xié)

2、議的應(yīng)用為背景，以嵌入式平臺為運(yùn)行環(huán)境，采用了POSIX正則表達(dá)式庫的軟件算法，結(jié)合軟件平臺的靈活和硬件平臺的高效，使得嵌入式Linux軟件系統(tǒng)和FPGA硬件協(xié)同工作，通過硬件加速的方式完成了對正則表達(dá)式的匹配。具體實(shí)施中，系統(tǒng)被劃分成了軟件系統(tǒng)模塊、硬件系統(tǒng)模塊和負(fù)責(zé)軟硬件通信的接口等三個組成部分。輸入的正則表達(dá)式和字符串首先進(jìn)入軟件系統(tǒng)模塊，它基于嵌入式Linux軟件系統(tǒng)實(shí)現(xiàn)，結(jié)合堆棧技術(shù)，把正則表達(dá)式編譯成為機(jī)器能識別并執(zhí)行的執(zhí)行

3、碼指令，并生成fastmap數(shù)據(jù)。因?yàn)檐浖到y(tǒng)模塊和硬件系統(tǒng)模塊的實(shí)現(xiàn)平臺不同，運(yùn)行速度級別也有差異，故通信接口負(fù)責(zé)它們之間的數(shù)據(jù)傳輸。硬件系統(tǒng)模塊基于FPGA實(shí)現(xiàn)，結(jié)合堆棧技術(shù)，根據(jù)得到的執(zhí)行碼、字符串和fastmap數(shù)據(jù)來完成正則表達(dá)式的匹配計(jì)算，得到最終是否匹配的結(jié)果。在整體設(shè)計(jì)中，系統(tǒng)具有“硬件加速”、“默認(rèn)使用最短匹配原則”和“放棄計(jì)算匹配細(xì)節(jié)”等獨(dú)到的設(shè)計(jì)特點(diǎn)，系統(tǒng)內(nèi)部高效運(yùn)作，很好地完成了設(shè)計(jì)任務(wù)。文章在最后給出的邏輯測試