Deep Packet Inspection Using Cuckoo Filter论文总结

---

Abstract

内存消耗少，误报率低，插入性能更高，查找吞吐量更高，支持删除操作

---

INTRODUCTION

• 在 DPI 中使用 BF 的主要挑战是所需 (k) 散列函数的额外计算
• 尽管 QF 仅使用一个哈希函数，但 QF 的查询性质会带来额外的缓慢。
• 成员查询数据结构 Cuckoo 过滤器 [11] 已被用作 DPI 方法中的匹配检查工具，以克服同时使用 BF 和 QF 导致的限制

 Higher throughput and simpler to implement than using both Bloom and Quotient filters.
 More accurate because Cuckoo filter has less false positive rate than both Bloom and Quotient filters.
 Consuming less memory than using both Bloom and Quotient filters.
 Less memory accesses than using both BF and QF.
 Higher throughput and simpler to implement than using both Bloom and Quotient filters.
 More accurate because Cuckoo filter has less false positive rate than both Bloom and Quotient filters.
 Consuming less memory than using both Bloom and uotient filters.
 Less memory accesses than using both BF and QF.

---

REALATED WORKS

Consequently, in this paper a Cuckoo filter that support delete operation has been used and employed in a DPI approach to get better results than employing both BF and QF.

---

CUCKOO FILTER

详情见这篇文章: QCF for deep packet inspection论文总结

Insertion process

Lookup process

Deletion process

Mapping signatures into CF

Architecture of the proposed approach

1. 将所有预定义的签名映射到 CF
2. 将传入的数据包作为输入，指定搜索窗口的大小。
3. 遍历所有数据包的字节，该算法通过查询 CF 来检查所有字节，以寻找感兴趣(iinteresting)的字符串的任何外观
4. 有任何匹配，算法将采取适当的活动并立即停止搜索，等待下一个数据包，依此类推
5. 否则，如果已经到达数据包的末尾，但没有与 CF 匹配，则数据包将被转发到其原始目的地。

Proposed DPI approach

EVALUATION

Insertion throughput

False positive rate

Query throughput

Memory accesses

DPI time improvement

Deletion throughput

CONCLUSION

• 支持频繁的签名集更新
• 消耗更少的内存
• 更大的插入吞吐量
• 更高的查找性能
• 支持删除操作和更低的误报率