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

华中科技大学 硕士学位论文 高速分组查找规则匹配算法研究 姓名：朱国胜 申请学位级别：硕士 专业：计算机应用技术 指导教师：余少华 2010-01 I 华 中 科 技 大 学 博 士 学 位 论 文 摘 要 互联网流量增长和通信线路速率的提高，对路由交换网络设备数据平面的报文 处理提出了更高的要求，以 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） ， II 华 中 科 技 大 学 博 士 学 位 论 文 该方法结合了地址缓存和前缀缓存技术，克服了地址缓存技术缓存空间要求过大， 前缀缓存技术无法缓存内部前缀节点的问题，在缓存空间、缓存命中率、缓存公平 性以及路由增量更新方面具有优势仿真实验表明对于路由条目超过 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 检测的同时大大的降低功耗 关键词：关键词：规则匹配，三态内容寻址存储器，IP 路由查找，报文分类，范围匹配，深 度报文检测 III 华 中 科 技 大 学 博 士 学 位 论 文 Abstract With the increasement of network traffic and line speed, the datapath processing in the switching and routing devices faces great challenges. To get the wire speed forwarding for 100Gbps interface for the minumal ethernet packet, the processing time must be less than 6.72ns. L2-L7 rule matching is the key processing in packet processing for packet forwarding,QoS scheduling and traffic controlling. This thesis focus on the research of L3 Longest Prefix matching(LPM), L3-L4 Packet Classification(PC) and L7 Deep Packet Inspection(DPI). The researches are on TCAM(Ternary Content Addressable Memory) hardware. Some rule mathcig algorithms have been proposed, analysized and simulated. IP address lookup need to do two dimensions matching to find the longest matching prefix.Traditional schemes implement IP address lookup using linear or binary search on prefix lengths or prefix values at the cost of slow lookup speed,complex pre-computation or high power consumption. A novel binary search algorithm based on prefix covered levels called BSPCL is proposed in this paper.At each level we use TCAMs to determine whether there is a match.TCAM entries need not be sorted because prefixes at each level are disjoint. Pre-computation is no longer needed and incremental updates are supported. IP address lookup can be done in O(log2max_level+1) TCAM clock cycle at the worst case where max_level is the maximal number of overlapping prefixes.The current max_level is 7 for IPv4 and 2 for IPv6.We can reduce the power consumption about 50%.Complexity comparision and performance evaluation shows the proposed sheme has better performance over other schemes. A parallel IP address look scheme called LEAF-TCAM was proposed. The routing table is partitioned into subtable according to the leaf nodes which result in simple and even table partition. A greedy algorithm was proposed to distributed the subtables to the IV 华 中 科 技 大 学 博 士 学 位 论 文 K TCAM chips which could aassure load balance among the chips.With the proposed LEAF-TCAM scheme we can get K-1 speedup of IP address lookup and incremental updates are also supported. Simulation with backbone routing table shows with 0.1*(K-1) redundant factor, over 90% routing prefixes need not be sorted and the power dissipation is only 12% of single chip scheme. The current IP address cache or IP prefix cache technologies have limitations.We analysized the overlapping relationships among prefixes in the global routing tables and proposed a threshold-based routing cache method which combined IP address cache and prefix cache technologies without the need of prefix expa。