小规模TCAM实现快速正则表达式匹配

"这篇研究论文探讨了如何使用小型TCAM（Ternary Content Addressable Memory，ternary内容可寻址存储器）实现快速的正则表达式匹配。TCAM是一种现成的芯片，广泛用于现代网络设备中的深度包检测和安全设备任务，如包分类。文章提出了三种创新技术，包括转换共享、表合并和可变步进，以减少TCAM空间并提高正则表达式匹配速度。在实际测试中，这些技术能够将八个具有25000个状态的实际世界正则表达式集存储在0.59 Mb的TCAM芯片中，并实现高正则表达式匹配吞吐量。" 本文的焦点在于解决正则表达式匹配效率问题，特别是在现代网络和安全设备中。正则表达式匹配是深度包检测的重要组成部分，它允许设备识别和分析网络流量中的模式。然而，随着网络流量的增加和复杂性的提高，对快速且高效匹配的需求也相应增加。 TCAM作为一种特殊的内存类型，因其快速查找和匹配能力而被广泛应用于网络设备中。然而，大型TCAM的使用可能会导致成本和功耗的增加，因此，论文提出使用小型TCAM来实现高效的正则表达式匹配，这是对现有技术的一个重要补充。 首先，转换共享（Transition Sharing）技术旨在通过共享TCAM条目来减少存储需求。正则表达式转换可以有多个相同的前缀或后缀，这种共享可以减少存储这些重复部分所需的存储空间。 其次，表合并（Table Consolidation）是一种优化方法，它整合了多个相似或相关的正则表达式，将其合并到一个更大的表中，从而进一步节省TCAM空间。 最后，可变步进（Variable Striding）技术可能涉及到调整查询时的步进大小，以适应不同的正则表达式结构，从而提高匹配速度，尤其对于具有不同复杂度的正则表达式集合。 实验结果表明，这三项技术的有效结合使得小型TCAM可以存储大规模的确定有限自动机（DFA），并且仍然能够提供高的匹配性能。具体来说，八个具有25000个状态的DFA能够在0.59 Mb的TCAM中得到存储，这意味着在不牺牲性能的前提下，显著降低了硬件资源的需求。 该研究论文提出的策略为正则表达式匹配提供了新的解决方案，尤其是在资源有限的环境中，这对于优化现代网络设备的性能和效率具有重要意义。通过这些技术，可以实现更高效、更节省空间的正则表达式匹配，这对于网络监控、安全防护以及数据处理等领域都有重要的应用价值。