支持快速增量更新的包分类算法分析

《支持快速增量更新的包分类算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、表目录表1．1表2．1表2．2表2．3表2．4表2．5表3．1表3．2表4．1表4．2表4．3表4．4表4．5表4．6表4．7表4．8表4．9表4．10表4．1l表4．12典型包分类算法的性能比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯6～个3维示例规则集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯9参』．i包分类的5个典型IP包头域⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·21分类规贝U的5个典型域⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯”2l不同源／目的端口号类型分布统计⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·21Pthreads常用编程接口简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

2、⋯⋯24一个5维示例规则集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯··293种删叉决策树的路径长度和查找结点个数统计⋯⋯⋯⋯⋯⋯⋯⋯⋯39DellPowerEdge2900服务器硬件参数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46IntelXeonE54l0处理器参数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯”46LlCache、L2Cache和主存的访问延迟⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯463个版本TICS算法的分类速度对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·473个版本TICS算法的存储消耗对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯··48TIC与TICS算法的存储消耗和预处理时间对比⋯⋯⋯

3、⋯⋯⋯⋯⋯⋯·49TICS算法全速更新而无查找时的更新性能⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·49BRPS算法的更新性能⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯49TICS与BRPS的分类速度对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·50TICS与TIC算法的分类速度对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯”5lTICS算法全速更新和查找同时进行时的查找和更新性能⋯⋯⋯⋯⋯53TICS算法不同更新频率下的查找和更新性能⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯53VllI中国科学技术大学学位论文原创性声明作者签名：一签字日期：剖中国科学技术大学学位论文授权使用声明作为巾请学位的条件之一，学位论文著作权

4、拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。／叼公开作者签名：口保密(——年)导师签名：经益签字Lj期：≥!社签字日期：—』!竺址第1章绪论1．1引言随着通信及计算机技术的迅猛发展，因特网上的应用越来越丰富。这些应用要求㈧特网提供安全和多样化的服务，例如基于策略的路由【2】、流量计费【3

5、】、防火墙包过滤[4】、虚拟专用网【5】、网络地址转换【6】、区分服务[7】等。传统的网络路由器采用“尽力而为”的工作模式，按照先来先服务的顺序处理到达的数据包，不对数据包加以区分，从而无法提供有差别的多样化服务。新掣网络应用要求首先将到达的数据包进行分类，然后根据数据包所属的类进行相应的处理，因此包分类技术成为新型网络应用的基础。图1．1是一个具有包分类功能的路由器模型。图1．1具有包分类功能的路由器模型分类器根据预没的分类规则集将到达的数据包指派给不同的流。分类规则集是一系列规则(Rule)的集合，每条规则对应～个流(Flow)，规则中包含与包头巾卡【

6、1关域对J照的匹配条件、一个流标识(Flow．ID)和相应的处理方式(Action)。当数据包头中的相关域满足某条规则的所有匹配条件时，称数据包匹配该规则。包分类技术在边缘路由器和核心路由器中正发挥着越来越重要的作用。随着链路速度以及网络流蕈的不断攀升，路由器必须不断提高数据包的转发速度以避免成为嘲络瓶颈，因此高速包分类算法成为实现高性能路由器的关键。除了速度要求以外，部分实时应用还要求能够动态更新规则集，即动态分类[8】[9】(DynamicClassification)的要求。目前大多数包分类算法主要关注提高分类速第1章绪论度和减小存储空间需求，添加或

7、删除规则的操作很复杂，有的甚至需要重建整个数捌结构，更新规则集的代价仍非常高。这使得这些算法不适合那些要求动态分类的应用。目前，实现高速数据包分类主要采用硬件的方法，但硬件方法成本高，灵活性差。软件方法灵活性好，但是分类速度相对较低。随着多核处理器的广泛应用，在多核处理器上利用软件实现高速包分类成为可能。本文研究能够支持快速增量史新的包分类算法，并在多核平台上高效实现。1．2包分类问题的定义从数学_L石4，包分类问题与计算几何中的一些问题很相似。在计算几何中存在一个多维空间的点定位问题：给定多维空间中的一些互不相交的区域，找出包含指定点的区域。对应到包分类

8、问题，每条规则对应了多维空间中的一个区域，数据包头中域的组合对应多