论文部分内容阅读
随着网络技术的快速发展，各种新型网络应用的不断出现，像网络入侵检测系统(Network Intrusion Detection System，NIDS)、质量服务(Quality of Service，QoS)、负载均衡(Load Balance)等都需要报告出所有的匹配规则—多匹配包分类。传统的基于软件的包分类技术远远不能达到其线速要求，而基于硬件的技术能够很好的解决这一问题，如TCAM(Ternary Content Addressable Memory，三态内容可寻址存储器)。 TCAM能够用于解决包分类问题不仅是因为其具有快速的、确定的查找速度和可以并行查找的特性;此外还因为TCAM可以存储三种逻辑状态，即“0”、“1”和“dontcare”三种状态，所以它非常适用于前缀匹配。但是TCAM只能返回最优匹配条目的索引，所以在多维包的多匹配包分类中，它不能直接实现多匹配包分类的查找，因此需要采用一些技术来解决这一问题;另外，在多维包分类中，如源端口和目的端口中都含有范围的情况，而TCAM不能直接存储范围，这也需要采用某种技术来解决这一问题。 本文中，我们针对上段中指出的两个问题，分别提出了一种解决方法。为了解决基于TCAM的多匹配包分类问题，我们提出了一种HTS(hybrid TCAM+SRAM)算法，此算法结合了顺序分解法和局部交叉乘积法。首先将规则集按域层层分解，然后将最后两个域相关联的信息通过局部交叉乘积存储到相应的SRAM中。此算法不仅解决了基于TCAM的多匹配包分类问题，而且还大大的降低了TCAM的查找功耗，在TCAM的存储空间和查找功耗间做了一个非常好的权衡。另外，为了解决基于TCAM的范围匹配问题，我们又提出了一种2级分层查找方法。此方法通过对范围集进行预处理，将原范围集分成许多新的范围集，然后再通过判断选择对某一个新范围集进行查找，从而通过两次查找得到所有的匹配结果。此方法能够很好的降低TCAM的查找空间，并且消耗的内存也较少一只需要3个小的TCAM，即它在TCAM的存储空间和查找功耗上同样做了一个很好的权衡。