孟旭東，許強凱

(1.南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003；2.南京郵電大學 江蘇省電信網絡融合實驗室，江蘇 南京 210003)

應用于Web服務器匹配算法的FPGA實現

孟旭東1,2，許強凱1,2

(1.南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003；2.南京郵電大學 江蘇省電信網絡融合實驗室，江蘇 南京 210003)

Web服務已經成為現代人網絡生活的一部分，人們需要通過Web迅速地獲取信息，需要在Web上快速地搜索關鍵字。在Web服務器端實現快速搜索，需要Web服務器能夠快速地對流經服務器的數據流進行字符串匹配。對字符串匹配算法進行了系統介紹，其中重點分析了利用位并行計算的Shift-Or算法。之所以利用FPGA來實現，是因為FPGA的實現方式在速率上高于軟件實現方式，在靈活性上高于專用集成電路的實現方式。在FPGA上實現了Shift-Or字符串匹配算法，并在千兆以太網的環境下進行了實驗測試。實驗結果表明，該方法能夠滿足在高速網絡環境下對數據包內容的深度檢測。

Web服務器；字符串匹配；Shift-Or；FPGA

0 引 言

在網絡這個數據的海洋里，數據流量正不斷增長，人們迫切需要對數據進行搜索，需要在Web服務器[1]上實現字符串匹配,工作量巨大。這一要求對數據搜索查找技術提出了巨大挑戰。字符串匹配是其核心技術。在網絡服務器[2]端，數據匹配的需求幾乎無處不在，尤其是在網絡安全領域。網絡安全領域中的一系列應用，例如防火墻、入侵檢測防護、垃圾郵件過濾、深度內容檢測等，都與字符串匹配緊密相關[3]。字符串匹配在上述安全領域的應用中都處于核心位置，并且占用著大量的計算資源。舉個例子，在檢測入侵的網絡安全應用中，字符串匹配是系統能否成功發現包含安全威脅信息的關鍵。入侵檢測系統先把部分已知具有安全威脅特征的模式串保存下來，定義成一系列的規則。當有數據流入內部網絡時，系統按照這些預先定義的規則和預先存下來的模式對流入數據進行對比，檢查出數據包內容中可能存在安全威脅的信息。據統計，在這樣的安全系統里，字符串匹配所消耗的計算資源占到了系統所有計算資源的50%以上[4]。字符串匹配本身需要消耗大量的計算資源，這一點對在網絡服務器端實現字符串匹配提出了較高要求。

在目前已有的字符串匹配算法中，最直接的方法是BF算法，俗稱蠻力算法。也就是不涉及任何技巧，逐個字符進行比較判斷，從而得到兩個字符串是否相同的結論。除了BF算法之外，研究人員提出了各種各樣的字符串匹配算法。這些算法中，有非常經典的Knuth-Morris-Pratt(KMP)算法[5]、Boyer-Moore(BM)算法[6]；也有一些新式算法采用較新技術思想(例如位并行)，其中的代表是Shift-And/Shift-Or算法，它通過同時完成多個位的計算達到同時處理多個字符串位置的目的，從而大幅提高了匹配效率[7]。

在網絡服務器這樣的對信息處理速度要求非常高的地方，傳統的利用通用處理器CPU，通過軟件實現字符串匹配存在運行速率不足的問題。軟件實現方式不能保證線速處理，從而造成網絡時延較大或信息檢索不充分。由于通用處理器性能的提升跟不上網絡速率的提升，一般在通用處理器上以軟件方式實現字符串匹配只能用于低于100 Mbps的低速網絡中。所以利用硬件來實現字符串匹配算法。

1 Shift-Or算法的FPGA實現設計概要

Shift-Or算法[8]利用位并行的方法提高了字符串匹配速率，通過一個位掩碼D，表示模式串前綴和文本串后綴的匹配情況。它同樣是先根據模式字符串構造一個表B，用來記錄字母表中每個字符的位掩碼bm…b1。如果pj=c，掩碼B[c]的第j位被置0，其余為1。這里的位掩碼D初始為全1。若模式串前綴p1…pj是文本串t1…ti的后綴，就把位掩碼D=dm…d1的第j位置0，并稱D的第j位是活動的。

當模式串P=p1…pm長為m，dm是活動的時候，就說明有一個成功匹配。每次讀入下一個文本字符ti+1時，需要重新計算位掩碼D。同樣是利用了位并行的方式，使得D的計算可以在常數時間內完成。D的更新公式如下：

D=(D?1)|B[ti+1]

可以發現Shift-Or算法實際上是Shift-And算法的一種富技巧性的實現。它通過對位取反從而去掉0m-11，從而簡化了計算，提高了速度。Shift-Or算法的偽代碼如下[9]：

Shift-Or(p=p1…pm,T=t1…tn)

Preprocessing

Forc∈∑DoB[c]=1m

Forj∈1…mDoB[pj]=B[pj]&1m-j01j-1

Searching

D=1m

Fori∈1…nDoD=(D?1)|B[ti]

ifD|01m-1≠1mThenfindanoccurrenceati-m+1

EndofFor

假設在進行信息查找之前，FPGA內沒有事先存儲需要匹配的模式字符串。根據Shift-Or算法，FPGA需要在對文本字符串進行信息搜索之前完成對模式字符串的預處理，計算得到算法需要的表格B并存在RAM內。先向FPGA發送包含模式字符串的數據包，讓FPGA對模式串進行預處理。預處理完成后，FPGA開始等待接收包含文本字符串的數據包，對接收到的文本串計算字符串匹配結果。

2 利用該字符串匹配模塊工作的系統設計

該系統工作在網絡的數據鏈路層[10]，利用千兆以太網口收發以太網幀[11]。但它對數據的處理不局限于以太網數據幀的幀頭部信息。以太網幀中封裝了數據包，數據包的凈荷里存放著接下來所做的字符串匹配所需要的模式字符串和文本字符串。系統在接收到一個數據幀后，會傳給FPGA芯片，可以對幀內所有數據進行操作處理。

以太網幀中包括6字節的目標MAC地址，6字節的源MAC地址，2字節的數據類型，4字節的校驗和，以及幀中間的數據包部分。以太網協議規定數據包最少46字節，最長1 500字節。而這里除數據包以外都可以認為是幀的頭部信息，屬于數據鏈路層，不影響在應用層做字符串匹配。FPGA在接收了這樣一個數據幀后，首先是存到RAM[12]里，再進一步對數據進行處理。協議規定了以太網幀的固定結構，每一個以太網幀的頭部信息長度是固定的，可以利用這一點，準確找到在FPGA中的RAM里存下來的數據幀內部的數據。

以太網幀封裝的是網絡層的數據包，也就是通常所說的IP包。IP包里包含著用戶數據，但是和上述的幀結構類似，IP包存在一個20字節的頭部信息。IP報文里的頭部包括源IP地址、目標IP地址、頭校驗和等信息，屬于網絡層信息。IP數據包里接下來是TCP/UDP包，同樣也包含固定長度的頭部信息。對UDP包而言，UDP報頭包括2字節的源端口號，2字節的目的端口號，2字節的UDP長度和2字節的校驗和，一共8字節的頭部信息。上述所有的頭部信息，因為都是固定長度，所以在RAM中的存儲相對位置也是固定的。利用信息在RAM中相對位置固定的特點，可以方便地找到處理所需要的數據。

按照上述原理，把應用層的模式字符串和文本字符串分別封裝在不同的數據包中，從外部通過以太網幀的形式傳入系統，利用UDP的端口號來對其進行區分，以完成不同的處理。根據算法工作流程(見第三節)，如果判定為模式串，根據UDP報頭里的數據包長度確定模式串的長度，并在FPGA中對模式串進行Shift-Or算法預處理；如果判定為文本串，還是可以根據UDP報頭里的數據包長度確定文本串的長度，并在FPGA中對文本串進行Shift-Or算法匹配，這兩個過程可以分開并行執行。如果匹配成功，可以將匹配成功信息通過數據包的形式返回給外部接口。系統的結構如圖1所示，系統核心部分在字符串匹配模塊。

圖1 系統結構

2.1 字符串匹配模塊的具體實現

Shift-Or算法及其在FPGA上實現的思路已經在前面進行了詳細分析。字符串匹配模塊下還可以更細致地分為模式串預處理模塊和文本串匹配模塊。

字符串匹配所需的模式串和文本串分別由具有不同端口號的TCP/UDP包封裝起來。FPGA可以根據所收到的數據包中的TCP/UDP端口號來判斷已經存入RAM的數據包中的凈荷是模式串還是文本串。在verilog程序中，模式串預處理模塊和文本串匹配模塊分別用一段always語句塊實現。

2.1.1 模式串預處理實現

如果FPGA判定正在處理的數據包所含凈荷是模式字符串，Shift-Or算法要求對模式字符字符串進行預處理。在這個預處理中，算法會根據讀入的模式字符串制作一張模式特征表格。模式特征表B的每一行對應模式串中的一個字符。定義的表格B有27行，可以處理26個英文字母，其他的任意字符統一記為‘*’。

在ASCII編碼中，一個英文字符的長為1字節，即8位比特位，并且有大小寫之分，即大寫的字符‘A’和小寫的字符‘a’編碼不同。通過對字符編碼的判斷，實現了忽略英文字符大小寫的模式匹配。例如，字符串“CHINA”在該字符串匹配系統中和字符串“china”效果相同。

字符‘A’的ASCII編碼為65，即8'b0100_0001，字符‘a’的ASCII編碼為97，即8'b0110_0001，在計算模式特征表格B時，同時考慮了這兩種情況，字母‘A’或‘a’在模式串中的特征(在模式串中出現的位置)都在表格B的第一個行向量B[0]中表示出來。同理，字符‘B’的ASCII編碼為66，即8'b0100_0010，字符‘b’的ASCII編碼為98，即8'b0110_0010，在計算模式特征表B時，字母‘B’或‘b’在模式串中的特征都在表格B的第二個行向量B[1]中表示出來。對于非英文字母表的字符，一概認為是字符‘*’，相應的在表格B中對應的行向量B[26]就為全1。

在計算表B時，需要考慮兩個位置問題：

(1)目前正在計算模式串的第幾個字符位置;

(2)計算的位向量應該是表格B中的第幾行。

變量decoder就是為了描述第一個位置問題而設置的。當目前正在處理的字符在模式串的第一位時，對模式特征表B的計算結果只針對表的某一行向量的最低位(即最右邊的一位)，具體是哪一行，那是第二個位置問題。在順序讀入模式字符串時，應該一直明確當前讀入的字符在模式字符串中的位置。為了明確這一位置，就另行設定了這個decoder向量。當正在讀入的字符是模式串的第一個字符時，相應的decoder的最低一位(最右邊一位)就設置為0，其他位設置為1。同理，當正在讀入的字符是模式串的第二個字符時，相應的decoder從右往左的第二位就設置為0，其他位設置為1。其他情形以此類推。

如果模式串長為16，就可以把算法中的字符c對應的模式特征表B中行向量B[c]的長度設定為16，即為一個reg[15:0]的變量。在計算表B時，另外設定了一個長為16位的寄存器變量decoder，變量類型為reg[15:0]，用來記錄字符c在模式串從低到高(0到15位)16個可能的位置中出現的確切位置，從而方便計算B[c]。計算decoder的部分verilog代碼如下：

case(str_len)

5'd0:decoder[15:0]<=16'hfffe;

5'd1:decoder[15:0]<=16'hfffd;

5'd2:decoder[15:0]<=16'hfffb;

5'd3:decoder[15:0]<=16'hfff7;

//這里省略5'd4到5'd15的情形

endcase

如果讀入的字符是模式字符串的第一個字符，decoder的二進制表示就是16'b1111_1111_1111_1110，即為16'hfffe。同理，當處理到模式串的第二個字符時，變量decoder的二進制表示就是16'b1111_1111_1111_1101，即為16'hfffd。這樣，就通過設置一個類似位掩碼向量的decoder寄存器變量，解決了上述的第一個位置問題。

第二個位置問題需要由正在處理的模式串字符確定。事先規定模式特征表B的行數為27，前26行表示26個英文字母，而且不區分大小寫，最后一行表示其他任意字符。

還是在模式串長度不超過16個字符的假設下，進行模式串特征制表。按照Shift-Or算法，每讀入一個模式串字符c，都可能需要更新模式特征向量B[c]。在這里需要用到上述第一個位置問題里的寄存器變量reg[15:0]decoder，先把當前的decoder向量和與當前讀入的模式串字符c相應的特征向量B[c]作按位與運算，這樣就可以針對B[c]的某一位進行操作，繼而完成對B[c]的賦值。部分verilog代碼如下：

case(c)

8'b0100_0001:B[0]<=(B[0] &decoder[15:0]);//字符‘A’

8'b0110_0001:B[0]<=(B[0] &decoder[15:0]);//字符‘a’

8'b0100_0010:B[1]<=(B[1] &decoder[15:0]);//字符‘B’

8'b0110_0010:B[1]<=(B[1] &decoder[15:0]);//字符‘b’

//這里省略另外24個英文字母

default:B[26]<=(B[26] &decoder[15:0]);//其他字符

endcase

可以發現Shift-Or算法實際上利用了空間換時間[13]的算法思想，在開始對文本串進行字符串匹配前，需要對模式串進行分析計算，得出一張模式字符串特征表，也就是算法的預處理過程。構成這張二維數據表的元素為0和1，表格包括了字符串匹配系統所有可以識別的字符。這里將系統可以識別的字符集定義為所有英文字母，所以系統的模式特征表格有27行，前26行分別對應26個英文字母，最后一行代表可能在文本串出現的任意其他字符，比如空格或標點符號。每一行作為描述對應字符在模式串中的特征，反映了該字符在模式串中的出現位置信息。在接下來對文本串進行匹配時，就通過這樣一張模式字符串特征表來對每個讀入的文本串字符操作，用表格B里的行向量和字符串匹配狀態編碼，即位掩碼D進行位并行操作，節省了大量時間。在制表時考慮到字母大小寫的問題，從而實現了允許大小寫通用的字符串匹配，增加了系統的靈活性。

2.1.2 文本串匹配模塊的實現

字符串匹配模塊對從RAM取出的數據進行判別后分流，對模式字符串和文本字符串分別進行不同的處理。文本字符串實際上應該是在FPGA對模式字符串已經預處理過后才送入FPGA進行字符串匹配，所以在實現文本串匹配模塊時，假設模式字符串已經在之前的數據包中給入FPGA，并且算法對模式串的預處理部分已經完成，即模式串特征表已經計算得出。

Shift-Or算法在對文本串進行匹配時，借助一個由0、1組成的位掩碼D，判斷匹配是否成功。這個位掩碼D在之前介紹過，長度不少于模式字符串長，和預處理模塊計算得到的模式特征向量B[c]的長度相同。同時，D也可以理解為匹配狀態編碼。位掩碼D的初始值為全1，當模式字符串的第一個字符和最后讀入的文本串字符相匹配時，D的最低位由1改為0，其余位為1；當模式串的前兩個字符和最后讀入的文本串的兩個字符同時匹配時，D的第二位由1改為0，其余位為1，以此類推。這樣的狀態編碼清晰記錄和表現了字符串匹配過程。可以非常直觀地推斷，如果模式串長為m，那么每當位掩碼D的第m位(從右往左第m位)為0時，表明找到了一個成功匹配。

與之前一樣，這里還是先假設模式串的長度為16。那么，模式特征表B中字符c對應的B[c]特征向量長度就為16，字符串匹配過程中的狀態編碼D也為長度16的向量。在設計中，模式特征向量B[c]和字符串匹配狀態編碼D都定義為reg[15:0]的寄存器變量。負責更新匹配狀態編碼D的部分verilog代碼如下：

case(ch)

8'b0100_0001:D[15:0]<=(D[15:0]<<1|B[0]);//‘A’

8'b0110_0001:D[15:0]<=(D[15:0]<<1|B[0]);//‘a’

8'b0100_0010:D[15:0]<=(D[15:0]<<1|B[1]);//‘B’

8'b0110_0010:D[15:0]<=(D[15:0]<<1|B[1]);//‘b’

//這里省略讀入字符從‘C’/‘c’到‘Z’/‘z’的情況

default:D[15:0]<=(D[15:0]<<1|B[26]);//'*'

endcase

包含有文本串的數據包流進FPGA被順序讀取，FPGA每讀取一個文本字符，對字符進行判斷查表處理。如果該文本字符屬于英文字母字符集，則系統可以在模式特征表格B里找到相對應的模式特征向量，更新當前的字符串匹配狀態編碼；如果不屬于英文字母字符集，則可以肯定與模式串不匹配，所用的B[*]為全1，更新得到的匹配狀態編碼會直接回到初始全1狀態。字符串匹配是否成功可以從這個匹配狀態編碼得出結論。

2.2 匹配信息返回模塊實現

在Shift-Or算法中，字符串匹配是否成功是根據匹配狀態編碼，即文本串匹配模塊中的位掩碼D的最高位來判斷。如果D的最高位為1，則匹配不成功或還沒有完全匹配；如果D的最高位為0，則模式串在文本串中匹配成功。確定匹配成功后，系統需要以某種方式返回這個匹配成功信息，其中還應該包括在文本串中的成功匹配位置。

每讀入一個文本串字符c，Shift-Or算法會更新一次匹配狀態編碼D。延續之前的例子，在FPGA實現中，verilog代碼為：

D[15:0]<=(D[15:0]<<1|B[c])；

注意這里的賦值采用的是非阻塞賦值符，在一個語句塊內，首先計算該塊內所有非阻塞賦值符右邊的值，然后這些值再賦給左邊的寄存器，賦值過程分成了兩個小步驟。在這里對狀態編碼D的更新中，新的D要在下一時鐘周期內才穩定。在完成對新的匹配狀態編碼計算后的下一個時鐘周期內檢查這個新的狀態編碼D的最高位，為0則匹配成功。

在順序讀入文本串的過程中，設置一個計數器用來計算當前正在處理的字符在文本串的序數。當計數器值為i的時候，匹配狀態編碼D的最高位變成0，表明在搜索到文本串的第i個字符的時候，模式串和已經讀入的文本串后綴完全匹配。如果模式串長度為m,可推算出字符串匹配成功發生在文本串第i-m+1個字符的位置。這個匹配成功的位置信息作為數據凈荷封裝在一個數據幀里，通過以太網模塊返回。

3 硬件與系統測試

3.1 硬件開發平臺

實驗所使用的硬件開發平臺包括兩個主要模塊：千兆以太網模塊和FPGA開發板模塊。以太網模塊提供了一個千兆以太網口，用來收發數據幀。與以太網模塊相連的FPGA開發平臺是系統設計的重點，所要完成的字符串匹配算法在這里實現。

千兆以太網模塊使用了Marvell公司的88E1111芯片。88E1111是一個用于吉比特以太網的物理層收發器，它支持1000BASE-T、100BASE-T和10BASE-T類型的以太網。88E1111芯片使用標準數字CMOS工藝制造，包含所有必需的有源電路來實現物理層功能。

所選用的FPGA開發板型號是EP4CE40F23C8N，包括Altera公司的Cyclone IV可編程FPGA芯片。開發板可以提供高達3.125 Gbps的數據傳輸速率，支持千兆以太網協議，并且功耗低，非常適合于高速網絡數據處理的應用。

3.2 實驗環境搭建

如圖2所示，實驗包括兩臺電腦和千兆以太網FPGA平臺。

圖2 實驗設備

圖中左邊計算機和以太網模塊由網線連接，右邊計算機與FPGA模塊由USB blaster連接。通過左邊計算機上的科來數據包產生軟件產生以太網數據幀，與以太網模塊通信。在右邊計算機上的Quartus II軟件上使用verilog語言編程，然后通過USB blaster將程序下載進FPGA。FPGA開發板型號為EP4CE4DF 23CBN，包括Altera公司的Cyclone IV FPGA芯片。千兆以太網模塊使用Marvell公司的88E1111芯片。FPGA使用鎖相環PLL[14]產生頻率為125 MHz的時鐘，每時鐘處理一個字節，而每字節8 bit，與千兆以太網口速率匹配。

3.3 測試結果及分析

測試中使用科來數據包產生軟件產生包含模式串的數據，經過以太網模塊發送給FPGA模塊。通過網絡抓包軟件獲取UDP數據包。這個UDP數據包的目標端口號是0x1000，系統中表示凈荷中的數據為模式字符串。測試使用的模式字符串為“ABCABCABCABCABCA”，長度為16。

FPGA在接收到包含模式字符串的數據之后，將凈荷數據取出按照Shift-Or算法對模式串進行預處理，主要任務就是計算模式特征表B。通過軟件Quartus II中的SignalTap可以觀察到算法運行情況。如圖3所示，可以看到定義的寄存器變量decoder和讀取的模式串字符q1的時序圖。變量clk為時鐘。str_len用來對模式串字符計數。字符串“A,B,C”的16進制表示就是“41h,42h,43h”，從圖中可以找到對應的位置。模式串預處理模塊中decoder計算完成后開始計算模式特征表B，在模式串預處理時序圖中最下一行的b變量可以觀察到。

模式串預處理完成后，向FPGA發送文本字符串，與之前發送模式字符串的方法相同。文本串數據包與模式串數據包不同的是UDP的目標端口號，包含文本串數據的UDP使用0x8000的目標端口號。用抓包軟件捕捉到UDP包。

FPGA接收到上述包含文本串的數據包后，對其展開深度內容檢測，即對UDP數據凈荷進行模式串匹配。在SignalTap中可以觀察到在時鐘信號clk的驅動下，文本串順序讀入字符q2和匹配狀態編碼D的時序圖。這里的字符串匹配用到了模式特征向量B[0],B[1],B[2]，它們分別為6DB6h，DB6Dh，B6DBh。

為了更細致地觀察匹配狀態編碼D，將字符串匹配成功的部分放大，如圖4所示。在編號35的時鐘周期內，16位狀態編碼D的最高位變位0，表示匹配成功。

注意到當D的最高位為0時，D=“01101101 10110110”，以“011”的形式重復，這正好符合測試使用的模式串“ABCABCABCABCABCA”以“ABC”的形式重復。通過手工計算，也可以驗證該算法在FPGA上正確運行。實際上在圖4中編號33的時鐘信號上升沿的地方，模式字符串就已經完整地在文本字符串中出現了，而此時的D還沒有更新，要到下一個時鐘周期內D才會更新，最高位改寫為0。

圖3 模式串預處理時序

圖4 字符串匹配結果時序

算法理論上，模式串“ABCABCABCABCABCA”對應的模式特征表項B[0]代表字符‘A’,B[0]應該為“0110110110110110”。實際測試中，計算得到B[0]是“6DB6”(十六進制表示)，換算成二進制為0110_1101_1011_0110，與理論值相同。同樣的方式可以驗證字符‘B’的模式特征向量B[1]和字符‘C’的模式特征向量B[2]，實際的模式特征表與理論相符。

當順序讀入文本串時，匹配狀態編碼D會相應更新，可以跟蹤D的更新過程來驗證系統的工作。初始時，16位的D為全1，實驗中，讀入不屬于英文字符集的字符時，D一直保持全1。當讀入字符‘A’，D在下一時鐘周期里更新為“1111_1111_1111_1110”，繼續讀入字符‘B’時，D更新為“1111_1111_1111_1101”；讀入文本串的后綴為“ABCA”時，D將在下一時鐘周期內更新為“1111_1111_1111_0110”。可以發現實驗中匹配狀態編碼D的更新與Shift-Or算法理論完全相符。

系統的字符串匹配處理速率與系統時鐘頻率有關。該系統FPGA通過鎖相環PLL產生頻率為125MHz的時鐘信號。系統每個時鐘周期處理一個字符，而一個字符長8bit，可以算出該系統可以支持千兆以太網上的字符串匹配應用。

4 結束語

網絡服務器承載了大量的用戶數據流量，在當今網絡數據的傳輸速率飛速發展，并且用戶越來越多的背景下，數據流量很容易達到千兆甚至萬兆比特每秒。數據傳輸速度的提高已經成為了用戶最基本、最重要的需求。然而隨著計算機通信技術的進步，如果只是簡單地傳輸數據，那么并不能實現更有意義的功能，需要對服務器中所承載的數據進行處理。文中在千兆以太網的測試環境中，實現了線速對數據包凈荷內容的字符串匹配。選擇FPGA作為字符串匹配算法實現平臺，針對FPGA在并行計算上的強大性能以及FPGA可編程的靈活性，選用以位并行計算為特點的Shift-Or算法。實驗在千兆以太網FPGA開發平臺上進行，在Altera生產的CycloneIVFPGA芯片里實現了Shift-Or字符串匹配算法。實驗中，通過一臺計算機產生數據幀，數據幀通過千兆以太網模塊傳給FPGA，在FPGA中完成字符串匹配。通過實驗驗證，結果與理論相符，達到了在千兆以太網下線速實現字符串匹配的目標。

[1] 于 靜.面向Web應用的安全服務器網卡的研究與設計[D].濟南：濟南大學，2010.

[2] 鄭慶良，張 翔,楊 瑩.網絡服務器模型分析與實現[J].杭州電子工業學院學報,2004,24(4):95-98.

[3] 黃 建.入侵檢測系統中字符串匹配算法與實現[D].武漢：華中科技大學,2008.

[4]FiskM,VargheseG.Ananalysisoffaststringmatchingappliedtocontent-basedforwardingandintrusiondetection[R].SanDiego:UniversityofCalifornia,2002.

[5]KnuthDE,MoorisJH,PrattJVR.Fastpatternmatchinginstrings[J].SIAMJournalonComupting,1977,6(2):323-350.

[6]BoyerRS,MooreJS.Afaststringsearchingalgorithm[J].CommunicationsoftheACM,1977,20(10):762-772.

[7] 邱慶哲.入侵檢測系統中檢測引擎的研究與實現[D].武漢：華中科技大學，2007.

[8] 王 誠，吳繼華.AlteraFPGA/CPLD設計[M].北京:人民郵電出版社,2005.

[9]NavarrG.柔性字符串匹配[M].中科院計算所網絡信息安全研究組,譯.北京:電子工業出版社,2007:15-20.

[10] 孫 鵬，董玉華，韓正之.基于數據鏈路層的局域網流量統計的實現[J].計算機工程與應用,2002,38(5):150-152.

[11] 王長清，張素娟,蔣景紅.基于以太網幀的嵌入式數據傳輸方案及實現[J].計算機工程與設計,2011,32(6):1952-1956.

[12]SalamonS,MaxmellWM.Storageoframsemen[J].AnimalReproductionScience,2000,62(1-3):77-111.

[13]KiltsS.高級FPGA設計:結構、實現和優化[M].孟憲元,譯.北京:機械工業出版社,2009.

[14] 李桂華，孫仲林，吉利久.CMOS鎖相環PLL的設計研究[J].半導體雜志,2000,25(3):30-37.

Implementation of FPGA Applied to Web Server Matching Algorithm

MENG Xu-dong1,2,XU Qiang-kai1,2

(1.Key Laboratory of Broadband Wireless Communication and Sensor Networkof Ministry of Education,Nanjing University of Posts and Telecommunications,Nanjing 210003,China；2.Telecommunications Network Integration Lab of Jiangsu,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Web services have become part of the modern life,and people need to get information through the Web quickly and require fast keyword search on the Web.To realize fast pattern matching on the Web server side,the Web server is needed to process the data stream through the server for string matching quickly.String matching algorithm is introduced systematically,in which the analysis is mainly focused on the use of a Shift-Or algorithm with parallel computing.Using FPGA to implement,because FPGA-based implementation can have a higher process rate than software implementations,and be more flexible than the ASIC implementation.The Shift-Or string matching algorithm is implemented in FPGA,and then tested in gigabit Ethernet.The results show that the design can meet the high speed packets rate under network environment of gigabit Ethernet.

Web server;string matching;Shift-Or;FPGA

2016-02-15

2016-06-09

時間：2016-11-21

國家“973”重點基礎研究發展計劃項目(2013CB329005)

孟旭東(1959-)，男，副研究員，研究方向為電信網絡和IP網絡的交換、異構網絡集成及業務融合、未來互聯網體系結構、網絡計算與分布式處理；許強凱(1991-)，男，碩士研究生，研究方向為下一代通信網絡。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1641.036.html

TP301.6

A

1673-629X(2016)12-0142-06

10.3969/j.issn.1673-629X.2016.12.031