论文部分内容阅读
TCAM由于其稳定又高效的查找性能，近年来被广泛应用于高速网络下的数据包分类系统中。TCAM中的规则表是动态的，当网络拓扑变化或者防火墙策略变更时，规则会被插入或者删除。插入和删除都通过TCAM写操作实现。与查询操作相比，写操作的效率较低，一次写操作需要消耗三个查询周期。进行规则表更新时，为了避免匹配到错误或者不一致的规则，TCAM查找接口不可用，等待查询的数据包需要被缓存起来。大量的写操作会使得更新效率过低，缓存的数据包过多，进而导致缓存占用过多的内存空间或者发生队头阻塞甚至丢包。减少写操作的次数即减少需要移动的规则数目，是提高TCAM更新效率的关键。常用减少移动规则数目的方法是使规则表稀疏排列，插入规则时只需插入空位或者移动少量规则。但是这种方法大大降低了空间利用率，对于价格昂贵的TCAM难以接受。 针对TCAM更新效率低的问题，本文首先分析了规则位置关系对TCAM并行查询的影响，总结出在规则紧密排列时减少移动规则数目的方法，设计并实现了全新的TCAM更新算法，偏序图更新算法，并对其做了进一步的优化。本文的主要工作包含以下两个方面。 1.偏序图更新算法的设计与实现。归纳了规则更新必须遵循的原则，在这个原则的基础上设计了减少规则移动的更新算法，偏序图更新算法。依次解决了算法实现中存在的问题，使用TCAM条目中多余的比特位解决了规则优先级存储问题，使用TCAM全局掩码器解决了返回所有相交规则和优先级比较问题，设计并实现了数据结构偏序图解决了偏序关系的记录和增量更新问题。然后对算法实现的各个阶段做了最坏情况下的性能分析。最后使用ClassBench工具分别生成Access Control List、Firewall、IP chain三种类型的规则集，进行规则更新实验。实验结果表明对于这三种规则集，算法每次移动的规则数量都远远小于规则集的大小，而且不随规则集大小线性增长。 2.优化偏序图更新算法。提出分割偏序图可以有效得提高偏序图更新算法的效率。分析了偏序图分割效果的影响因素，指出对于多维规则集，除了规则集大小外，分割算法也是其重要影响因素。进一步在偏序关系的理论框架下研究偏序图分割问题，证明了分割算法可以取到其理论上界，然后设计并实现了偏序图最优分割算法。加入偏序图最优分割算法之后，偏序图更新算法的更新效率有了大幅度的提升。最后与同类分割更新算法TreeCAM做性能对比，实验结果表明本算法在分割效果、更新效率和空间利用率上都优于TreeCAM。