高速分组查找规则匹配算法研究

摘要

互联网流量增长和通信线路速率的提高，对路由交换网络设备数据平面的报文处理提出了更高的要求，以100Gbps以太网接口为例，要实现最小包长线速转发，每报文处理时间要小于6.72ns,其中二到七层的分组查找规则匹配是分组转发、QoS调度、流量控制等处理的关键。本文在三层IP路由最长匹配（LPM：Longest Prefix matching）、三到四层的报文分类（PC：Packet Classification）和七层的深度报文检测（DPI：Deep Packet Inspection）等方面开展研究，基于硬件三态内容寻址存储器（TCAM：Ternary Content Addressable Memory）提出了相关的分组查找规则匹配算法，并对算法进行分析、仿真和实验验证。
　　 传统IP路由查找算法在前缀值或者前缀长度维度采用线性或者二分搜索，存在查找速率慢、预计算复杂和功耗高的缺点。为提高查找速率和降低功耗，提出了一种采用TCAM实现前缀覆盖级别的二分路由查找算法BSPCL（Binary Search on Prefix Covered Level），其特点是：前缀按照所在覆盖级别划分到不同的集合并放置在TCAM中，通过二分算法来实现路由查找。查找性能方面：路由查找可以在O(log2max_level+1)个TCAM时钟周期内完成，max_level为最大的前缀覆盖级别，目前对于IPv4和IPv6来说max_level分别为7和2；功耗方面：二分查找特性可以降低功耗约50％；路由更新方面：前缀在TCAM中的存放无需排序，支持随机更新。
　　 为加速IP路由查找，提出了一种并行IP路由查找方法LEAF-TCAM。路由表分区方面：LEAF-TCAM方法基于叶子节点（Leaf Node）进行路由表分区，分区算法实现简单且分区均匀；负载均衡方面：分区子表按照流量特征，基于贪心方法在K个TCAM芯片中进行均衡分布；查找性能方面：和其他并行方法一样具有K-1倍加速因子；路由更新方面：该方法无需进行前缀扩展，可以采用随机更新。针对骨干网路由表的分析表明在引入0.1*(K-1)冗余，90％以上的路由无需排序，功耗只有传统单片方案的12％。
　　 缓存技术也应用于IP路由查找，目前用于IP路由查找的地址缓存时间局部性和空间局部性有限，前缀缓存技术的存在不公平性以及不支持增量更新的问题。本文提出了一种基于阈值的IP路由缓存方法（TRC：Threshold-based Route Caching），该方法结合了地址缓存和前缀缓存技术，克服了地址缓存技术缓存空间要求过大，前缀缓存技术无法缓存内部前缀节点的问题，在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势。仿真实验表明对于路由条目超过260K的路由表，缓存空间大小为30K，选择阈值K=4时，缓存失效率为0.02，可以用小的缓存空间实现高速接口的线速转发。
　　 基于TCAM的报文分类在实现范围匹配时存在范围扩张问题，最坏情况下，基于前缀扩展方法（PE：Prefix Expansion）的范围扩张因子为2（W-1），基于格雷码表示方法（SRGE：Short Range Gray Encoding）的范围扩张因子为2（W-2），其中W为范围字段的长度。范围扩张一方面会导致TCAM空间利用率的降低，另一方面会导致查找匹配时功耗的升高。本文提出了一种基于TCAM的范围匹配方法：C-TCAM（Compressed TCAM）。空间方面，通过二级压缩存储，C-TCAM可以将2个扩展后的TCAM表项压缩成1个，最坏情况下范围扩张因子为W-1或者W-2，提高了空间利用率；功耗方面，通过一种新的TCAM查找算法来避免无效表项参与比较从而降低了功耗；扩展性方面，在性能允许的条件下，C-TCAM可以向多级扩展，从而进一步减少空间和降低功耗。分析和仿真显示C-TCAM方法在实现性能报文分类的同时在空间利用率、功耗等方面具有优势。
　　 基于报文内容扫描的深度报文检测技术广泛应用于网络入侵检测、业务识别和控制系统，传统基于三层、四层报文头部的安全访问控制需要扫描的三层、四层报头内容在报文中的位置固定，而DPI需要检测的特征字在报文中出现的位置不固定，因此需要对报文内容进行逐字节扫描。为实现低功耗高速DPI，提出一种基于布鲁姆过滤器（BF：Bloom Fliter）和TCAM的分级DPI方法BF-TCAM。第一级采用低功耗的并行布鲁姆过滤器排除无需检测的正常报文；第二级采用TCAM对真正需要检测的攻击报文和第一级的假阳性误判报文做进一步的检测。由于网络流量中大部分报文是正常报文，攻击报文在其中只占很少的部分，布鲁姆过滤器的假阴性（False Negative）概率为0，可以保证不会产生漏检，假阳性（False Positive）概率很低，可以保证高速DPI检测的同时大大的降低功耗。

目录

文摘

英文文摘

声明

1 绪 论

2 基于前缀覆盖级别的二分IP路由查找算法BSPCL

3 并行IP路由查找算法LEAF-TCAM

4 基于阈值的IP路由缓存算法TRC

5 基于TCAM的范围匹配算法C-TCAM

6 低功耗的高速DPI方法BF-TCAM

7 总结和展望

致 谢

参考文献

附录