用於大量樣本之快速定時平行自動機比對之深層封包比對加速器

Abstract

小型家用與公司用網路閘道器，常使低成本的嵌入式網路處理器去處理網路功能服務，而最近這樣的網路閘道器有更進一步的需求去提供深層封包比對(Deep Packet Inspection, DPI)功能。因此我們有動機去提出一適當的平行自動機比對(Parallel Automaton Matching, PAM)硬體去加速嵌入式網路處理器的效能。因自動機比對(Automaton Matching, AM)是彈性及定時反應的演算法，所以適用DPI應用。但AM仍有很大空間改善平均效能，所以PAM使用新的pre-hash, root-index及root-hash 方法加速AM的平均時間。PAM在非根點(non-root states)時pre-hash的方法使用雜湊函式預先快速比對，而在根(root state)時，可在一次比對中使用root-index或root-hash方法進行多位元組比對。至於有關PAM的實現，我們將PAM實現在一種盛行的自動機比對演算法 Aho-Corasick(AC)上。在FPGA方面的模擬，PAM在樣本集32,634位元組下可以達到最大效能12.6 Gbps，結果展現PAM可以以很小的電路，達到支援大樣本集及有競爭性的效能。而且PAM 樣本及並不受限於內部電路及記憶體，如果使用高速外部記憶體去儲存樣本，PAM可以支援超過21,302樣本數，並維持原有類似的效能。

Home and office network gateways often employ a cost-effective embedded network processor to handle their network services. Such network gateways have received a strong demand for applications dealing with deep packet inspection. This motivated us to propose an appropriate parallel automaton matching (PAM) hardware to accelerate the embedded network processors. Although automaton matching algorithms are robust with deterministic matching time, there is still plenty of room for improving their average-case performance. PAM employs novel pre-hash, root-index and root-hash techniques to accelerate the matching in automation-based hardware. The pre-hash approach uses some hash functions to pre-test the input substring for the non-root states, while the root-index and root-hash approaches handle multiple bytes in a single matching for the root state. PAM is also applied in a prevalent automaton algorithm, Aho-Corasick (AC), which is often used in many deep packet inspection applications. When implemented in the FPGA, PAM can perform at the rate of 12.6 Gbps with the pattern set of 32,634 bytes, demonstrating that our proposed approach can use a small logic circuit to achieve a competitive performance, although a larger memory is used. Furthermore, the amount of patterns in the PAM is not limited by the amount of internal circuits and memories. If high-speed external memories are employed, PAM can support up to 21,302 patterns while maintaining a similar high performance.