基于TCAM的报文分类算法研究

论文摘要

互联网多元化、多媒体化的承载业务对网络设备的报文转发能力和安全防护能力提出了更高的需求。网络安全设备中,由于报文分类算法的复杂性,报文分类机制普遍基于软件实现,难以适应高速报文处理。基于TCAM高速报文分类算法是近年来的研究热点,而网络通信设备与安全设备的融合对基于TCAM实现的高速报文处理提出了新要求。论文结合江苏省科技成果转化专项资金支持项目‘’IPv4/IPv6融合网络芯片研究与产业化”中一体化安全网关（Integrated Security Gateway, ISG）的研制,深入研究了基于TCAM的高速报文分类算法,提出一种基于TCAM范围匹配分类算法和一种基于TCAM多重匹配分类算法。通过将上述两种算法有机结合,设计了一种高效的一体化安全网关报文分类方案,并予以工程实现。一体化安全网关报文分类方案不仅支持非字段和范围字段匹配,同时有效地解决了TCAM的多重匹配问题。论文的主要工作如下：■对现有基于TCAM的报文分类技术进行综述,给出基于TCAM报文分类的性能衡量指标,并主要讨论了一体化安全网关所需的基于TCAM报文分类算法,重点从算法的时间复杂度、TCAM利用率、工程实现难度等方面进行了分析和比较,指出现有基于TCAM报文分类算法存在的问题,为一体化安全网关报文分类方案的设计打下了基础。■提出了一种混合范围编码机制一HYBRID-RES （Hybrid range encoding scheme）,通过扩展系数和出现频率综合选择纵向或横向扩展编码策略对范围规则进行编码。纵向扩展编码策略利用GRAY码的对称映射特征设计一种格雷范围编码算法,而对纵向扩展出TCAM表项数目较多的范围规则采用横向扩展编码策略。理论分析和实验结果表明,HYBRID-RES能获得较好的TCAM利用率和更新性能。■提出了一种基于规则几何分割的多重匹配算法一MWSS（Multi-match With Set Splitting）。算法通过规则重建以及合理的表项管理实现规则的多重匹配,并在保证系统线速处理的前提下,对规则集进行拆分,从而寻求查询速度和TCAM利用率之间的平衡。MWSS算法虽然需要多个时钟周期分别匹配各规则子集,但较大地提高了TCAM利用率,同时具有较好的扩展性。■基于一体化安全网关的研制需求,综合考虑实际应用环境,对HYBRID-RES和MWSS算法进行应用上的扩展,为一体化安全网关设计了一种高效的基于TCAM报文分类方案,实现了非规则和范围规则的匹配,并通过对TCAM芯片的分区查询,完成了线速多重匹配。理论分析和测试表明,本方案能完全满足了一体化安全网关项目研发的需要。目前,该方案已经在一体化安全网关的实际系统中得到成功应用。

论文目录

• 表目录
• 图目录
• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 应用现状
• 1.3 主要工作
• 1.4 结构安排
• 第二章 基于TCAM的报文分类技术综述
• 2.1 引言
• 2.2 基于TCAM的报文分类定义
• 2.3 基于TCAM的报文分类算法性能衡量指标
• 2.4 基于TCAM的报文分类算法介绍
• 2.4.1 支持非规则匹配算法
• 2.4.2 支持范围规则匹配算法
• 2.4.3 支持多重匹配算法
• 2.5 本章小结
• 第三章 一种基于TCAM的范围匹配分类算法
• 3.1 引言
• 3.2 HYBRID-RES机制设计
• 3.3 HYBRID-RES机制描述
• 3.3.1 GBRE算法
• 3.3.2 比特向量映射编码
• 3.3.3 判决策略
• 3.3.4 报文处理流程
• 3.4 HYBRID-RES机制性能分析及比较
• 3.4.1 TCAM利用率
• 3.4.2 更新性能
• 3.4.3 综合比较
• 3.5 本章小结
• 第四章 一种基于TCAM的多重匹配分类算法
• 4.1 引言
• 4.2 MWSS算法思想
• 4.3 MWSS算法描述
• 4.3.1 规则几何分割
• 4.3.2 规则集拆分算法
• 4.3.3 TCAM表项管理
• 4.4 MWSS算法性能分析及比较
• 4.5 本章小结
• 第五章 基于TCAM的一体化安全网关报文分类方案
• 5.1 系统概述
• 5.2 一体化安全网关报文分类方案设计
• 5.3 一体化安全网关报文分类方案实现
• 5.3.1 TCAM映像表结构及组织方式
• 5.3.2 TCAM表项分配算法
• 5.4 方案性能分析及测试
• 5.4.1 方案性能分析
• 5.4.2 方案性能测试
• 5.5 本章小结
• 结束语
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢