三种包分类算法的实现 SX1116090

1、简单实现包分类算法概要包分类是VPNs、下一代路由器、防火墙等设备的关键技术。包 分类算法研究具有十分重要的意义，是目前的热点之一。本文介绍了 常用的包分类算法，分析了它们的优缺点，并简单实现线性、Hicuts 和Hypercut三种基本算法，对这三种算法进行性能对比。、包分类算法背景路由器的主要功能是将一个网络的IP数据报(包)Packet转发到另一个网 络。传统路由器仅根据数据包的目的地址对数据包进行转发，提供未加区分的尽 力服务(Best Effort Service)，这是一维报文分类的典型形式：对所有的用户报文 一视同仁的处理。但是，随着因特网规模的不断扩大和应用技术的进步，越来越

2、多的业务需要对数据包进行快速有效的分类以便区别处理提供不同级别的服务， 因此路由器还需要对数据包进行进一步的处理。最常见的是根据安全性需要，对 包进行过滤，阻止有安全隐患的数据包通过。因此，研究高速包分类算法具有十 分重要的意义。因特网是由许许多多的主机及连接这些主机的网络组成，主机间通过TCP /IP协议交换数据包。数据包从一个主机穿过网络到达另一个主机，其中就需 要路由器提供数据包转发服务。近年来，因特网己经从主要连接教育机构的低速 网络迅速成为重要的商业基础设施。现在，因特网正呈现两方面的新变化：一方 面，因特网上的用户正在呈现爆炸性增长，Web站点正在迅速增加，需要宽带 网络的多媒体应

3、用正在日益普及，因特网的通信量也正在呈现爆炸性增长，因特 网正日益变得拥挤：另一方面，因特网上的用户正呈现许多不同的种类，从以浏 览和下载资料为主的普通家庭用户到经营电子商务的大型企业等等，这些用户从 安全、性能、可靠性方面对因特网的期望是不同的。人们希望路由器能够具有诸 如数据包过滤、区分服务、QoS、多播、流量计费等额外功能。所有这些处理都 需要路由器按某些规则将数据包进行分类，分类后的数据构成许多“流，再对 每一个流分别进行处理。对于网络流量的不断增长问题，由于光纤技术和DWDM 技术的发展使得链路的速率不再成为瓶颈，已经满足了大流量传输的需求，这就 使得路由器的处理速度成为网络整体速度

4、的一个瓶颈。这主要由于路由器需要对 每个输入包执行许多操作，包括十分复杂的分类操作。例如，它们需要对每个输 入包执行最长前缀匹配以发现其下一跳地址：需要对每个输入包执行多维包分类 以便在执行缓冲器管理、QoS调度、防火墙、网络地址翻译、多播服务、虚拟专 用网、速率限制、流量计费等任务时区别对待不同的包。因此，为了满足服务快 速性和服务多样性这两方面的需要，就必须研究相应的快速包分类算法应用到实 际路由中。二、包分类原理包分类是QoS的基础，只有区分了不同的报文业务，才能进行分别处理及保 障相关业务的服务质量。分类是定义传输类别并判断报文所属传输类别的过程。 TCP/IP报文有两种基本的分类模式

5、，行为聚合（BA）或多字段（MF）。BA类 是区分服务编码点（DSCP）处理的基础，具有较好的扩展性，适用于核心网络。 MF类基于TCP/IP报头一个或多个域（字段），原则上讲所有的字段都可以用于 分类。比如经典的五元组形式（源端口，目的端口，源地址，目的地址，协议类 型）。MF类一般在网络边界实现，是一种广泛使用的灵活的报文分类方法。高 性能的路由器应该支持灵活的分类策略，实现高效的分类算法。动作通常数据包分类就是根据网络上传输的数据包的包头信息，将数据包按照一定规则进行分类。在网络分层模型中，要传输的数据被各层协议的包头依次封装， 每层的包头都包含若干个域（字段），它们分别表示该层协议的特

6、征数据。一个分 类器又称规则库f，含有条过滤规则，记为 R1,R2,.,Rn。R为其中任意一条规 则，由匹配条件filter、优先级priority和匹配处理action三部分构成，记为Rfilter， Rpriority和 R action:Rfilter:d元组（RF1,RF2,.,RFd），指示数据包匹配该规则的条件。Fi表 示规则R的第6匹配域，是该条规则对数据包头的第i个字段的约束条件。Rpriority:规则的优先级，优先级越高，代价越小。取值范围是1,+“），即 RpriorityE1,+s）。默认情况下规则编号表示优先级，编号较小的规则具有较高 的优先级。Raction:对满足

7、相应过滤规则的数据包的处理动作，其取值范围是 a1,a2,a3,.,ak，艮口RactionE a1, a2, a3,.,ak。一般来说k域报文分类匹配分类器设计到的技术也称k维报文分类问题。k维 报文分类问题是通用报文分类问题。一个数据包的包头经过解析以后得到一个关 键字P,P为d元（p1,p2，,p）,d维包分类问题就是在规则集中寻找和P匹配的具有 最高优先级的的规则Rbest （最佳匹配）。三、三种包分类算法包分类问题巨大的需求，众多的算法和体系结构已被提出，基本上可以划分 为5种类型的算法：穷举分类算法、基于Trie分割的分类算法、几何区域分割的 分类算法、元组空间分割分类算法、维度分

8、解分类算法，本文要实现的三种包 分类算法：线性包分类算法、Hucuts和Hypercut算法分别属于穷举分类算法和几 何区域划分算法。下文将就着两种类型的算法展开。穷举分类算法是查找问题最基本而简单的解决方法将待分类的数据包依次 和分类规则库内的所有规则进行比较。讨论这种方法的意义在于，假设规则集已 被分成许多子集，每个子集的独立查找往往可以选择该方法。穷尽查找法中具体 两个最常见的算法是线性查找和大规模并行查找。二者恰好代表穷尽查找法的两 种极端，线性查找对规则集不进行分割，其性能最低，WTCAM将规则集划分成 每个子集只有一条规则，其性能最高。线性查找算法按照按优先级降序排列分类规则链表，

9、一个数据包顺序地与每 个规则进行比较直到找到第一个匹配的规则。由于规则已经事先按照优先级降序 排列，所以第一个匹配的规则即为最佳匹配规则。包分类阶段的空间复杂度为 O(N)，时间复杂度为O(N)。包分类的时间随着规则数目的增加呈线性增加，适 用于规则数目比较少的情况。几何区域划分算法，主要思想根据规则代表的区域，对规则集进行分割储存 查找时，判断数据包代表的点落入的子空间范围，逐步收拢得到最佳匹配规则。 典型算法有：智能层次切割(Hierarchical IntelligentCuttings，Hicuts)算法和多决 策树HyperCuts算法。HiCuts(Hierarchical Int

10、elligent Cuttings)算法由学者 Gupta和 Mckeown提 出，切 割(Cutting)的概念来源于从几何学角度观察包分类问题。该算法适于范围类型的 规则，将其它字段统一转化成范围。卬。皿，采用了一棵决策树作为快速查找的 数据结构，其内部结点包含适当的分类导向信息，但不存储任何规则，其叶结点 (或外部结点)存储一个小型的规则子集。算法结合了决策树搜索和线性查找两种 分类方式，采用多级空间分解，每级分解在一个维度上进行，把规则库分为各个 叶子结点内的小规则集。当一个IP包进来时，沿着树的某一分支遍历到树的叶子， 将该IP包和叶子结点中少量的规则线性匹配。Hicuts算法的优点

11、是占用内存空间 小，规则集更新容易，直接支持范围匹配，缺点是预处理时间较长，分类速度比 一些快速包分类算法低。HyperCuts算法由Singh、Baboescu、Varghese和Wang等学者提出。HyperCut 以HiCuts算法为基础上，做了一些改进，通过多重切割多维空间，最小化决策树 的高度，同样也限制叶结点上规则最大数目。由于等分切割，HypcrCuts对子空 间的编码简单而有效，译码简单，这使得多重切割没有大幅增加数据结构所占用 内存。HyperCuts算法对Hicuts算法的改进，包括：HyperCuts通过增加一个参数， 使决策树中间结点可以同时基于多维进行分割。Hicut

12、s形成的决策树叶子结点 上重复的规则较多，HyperCuts过把一些通用规则（比如通配规则，前缀较短的 规则）从分类规则库中独立出来，存放在根结点中。HyperCuts在叶结点所存储规 则列表中仍进行线性查找。理论上，该算法时间和空间复杂度与HiCuts算法属于 同一个数量级。HyperCutsa策树比HiCuts策树更低，然而内部结点信息更多， 需要位数也更多，这可能增加一个内部结点访问内存的次数，故一次多重切割的 维数和份数受存储器位宽限制。HyperCuts算法也支持增量更新，支持以中等速 度进行随机更新，最坏情况下，需要重构决策树.四、算法描述这里只做算法的描述，具体代码见附件包分类根

13、据IP数据的包头字段分类，小数据包为网络层信息传输的载体，拥 有固定长度20字节的首部。同时IP数据报还封装了上一层的TCP/UDP报文段得的 首部，包括源端口、目的端口等信息。规则库f中的每条规则规则Rule由分类器 (filter)、优先级(priority)、动作(action)组成。分类器可以用经典的五元组表示 (目的地址，源地址，协议，目的端口，源端口)即DA，SA，PR，DP，SP)。 当一条IP数据报进入路由器要经过路由器转发时，数据报会解析出一个关键字P， 若P也是由5个字段组成P(d1,d2,d3,d4,d5),那么数据包与规则的匹配问题就是P 的五元组每个分量d跟filte

14、r的分量匹配寻找路由器处理动作action的过程。typedef structunsigned long DA ;unsigned long SA ;int PR ;unsigned DP ;unsigned SP ;filter , *Filter;线性包分类算法：规则库中的规则用一条单链表的形式组织，按照优先Rule.priority将单链表 非升序排列。包头解析关键字P在链表中从头结点开始顺序匹配，第一个与之匹 配的规则就是最佳匹配。typedef struct rulefliter fliters;int priority ;int action ;struct rule *next

15、; Rule ;Hicuts算法Hicuts算法结合了决策树搜索和线性查找两种分类方式，采用多级空间分解， 每级分解在一个维度上进行，把规则库分为各个叶子结点内的小规则集。Hicuts 算法构建了一颗决策树，其内部结点包含适当的分类导向信息，但是不包含任何 规则，规则都是存储在叶子结点中。概括地描述d维HiCuts算法如下。每个内部 结点v，代表几何查找空间的一个分区。例如根结点代表完整的d维空间，根据其 中一维可将个结点空间分割成更小子空间，每个子空间为v结点的每个子结点所 表示。子空间被递归地分割直至每个空间包含的规则数目不大于参数binth，此时 给叶结点分派规则。公式化描述内部结点v如

16、下：一个超矩形(Hyper-rectangle)B(v)，是一个范围类型的d元组(m1,h1,m2,h2,，mdOd该矩形定义了一个子空间，存储于v结点中。一次切割c(v)，包含两个实体。k=dim(c(v)，切割空间B(V)所依据的维 的编号。np(C(v)，空间B(v)被分成的份数，等于内部结点v的孩子结点个数。所包含的规则子集CRS(v)，如果是内部结点w的子结点， UCRS(v )是 CRS(w)的一个子集。每个CRS(w)中的规则，如果跨入(或被切入)空间B(v)，也即 成为CRS(v)中的一员。CRS(root)是包含所有规则的集合。CRS(v)的规则数目记 作 NumRules(

17、v)。为一个规则集构造一棵决策树有许多方法。在预处理阶段，HiCuts算法在几 个启发公式引导下，在限定可用内存的情况下最小化决策树的高度，从而能够构 造出一棵比较合理的决策树。Typedef enumLEAF,BRANCH NodeKind ; 结点种类typedef struct TREENODENodeKind kind ;unionstruct Filter ;Rule* infoptr lf ;叶子struct TREENODE*ptr31 ;int num bh; /分支TREENODE;*rootTREE ;规则划分 int PreCut (unsigned char dimTo

18、Cut, unsigned int currRange42,unsigned int numRules,unsigned int *currRuleList,struct CUTTING *tempCut,struct RULESET *ruleSet) unsigned int i, num, cut;unsigned int cuts = 1;/unsigned int numCuts = 1; / number of cuts is 2AnumCuts/ TODO:refer to HiCuts for alternative initialization of numCutsunsig

19、ned int spaceAvailable = numRules*SPFAC; / space availableunsigned int smC=0; / space measurementunsigned int rangeToSearch2; / search this range for the number of colliding rulesunsigned int interval = currRangedimToCut1-currRangedimToCut0; / interval is always 2Acutfloat costs4, worstCosts4;for(i=

20、0; i4; i+) worstCostsi = 0;/ decide if current search range really need to cutfor(num=0; numruleListcurrRuleListnum.ruleRangedimToCut0ruleListcurrRuleListnum.ruleRangedimToCut1=currRangedimToCut1)smC+;if(smC = numRules)return FALSE; / all rules cover the full search space, so is of no use to cut any

21、more/ cutting with the limit of spaceAvailablewhile(TRUE)smC = 0; / space measurementinterval = (interval1)+1;/ interval/2numCuts = (0 x1cuts);costs1 = 0;for(cut=0; cutnumCuts; cut+)划分出来的区间rangeToSearch0 = currRangedimToCut0+cut*interval;rangeToSearch1 = rangeToSearch0+interval-1;/ -1 为防止越界 costs0 =

22、 0;for(num=0; numruleListcurrRuleListnum.ruleRangedimToCut0=rangeToSearch0 &ruleSet-ruleListcurrRuleListnum.ruleRangedimToCut0ruleListcurrRuleListnum.ruleRangedimToCut1=rangeToSearch0&ruleSet-ruleListcurrRuleListnum.ruleRangedimToCut1ruleListcurrRuleListnum.ruleRangedimToCut0ruleListcurrRuleListnum.

23、ruleRangedimToCut1rangeToSearch1)smC+;costs0+;costs1+=costs0;if(worstCosts0costs0)worstCosts0 = costs0;costs1 = costs1/numCuts; / average number of rules falling in each child node if(worstCosts1costs1) worstCosts1 = costs1;smC+=numCuts;if(smCspaceAvailable)cuts+; / twice larger than current number

24、of cuttings interval-;for(i=0; idimToCut = dimToCut;tempCut-numCuts = cuts;for(i=0; icostsi = worstCostsi;return SUCCESS;HyperCuts 算法HyperCuts以HiCuts算法为基础上，做了一些改进，通过多重切割多维空间， 最小化决策树的高度，同样也限制叶结点上规则最大数目，降低决策树高度。由 于等分切割，HypcrCuts对子空间的编码简单而有效，译码简单，这使得多重切 割没有大幅增加数据结构所占用内存。五、算法性能分析对于包分类算法的软件仿真要满足四个原则：一、数据

25、流的产生：只有实际 的网络流才能对算法给出准确的评估。二、分类规则集的产生：网络设备对规则 数的容忍度要多达10K1M个，仿真软件可以根据参数设定自动产生规则集。三、 算法的实现和嵌入：实现上述多种算法，分别将它们嵌入到平台中测试。四、仿 真统计参数分析：主要包括时间性能测试和空间需求量测试。时间量的统计是将 同一个包经过多次重复处理后的平均值。空间需求量主要是算法的代码空间和数 据占用空间。基于上述这些原则可以使用PALAC模拟器为测试包分类算法提供了一个模 拟环境，也可以使使用Quartus II 6.0平台。它可以分析普通的ACL条（存取访问规 则），产生背景数据流，在其提供的离散事件模

26、拟框架中静态的存储算法的相关 数据，最后输出统计结果。算法性能对比（S：速度M：存储空间）线性算法几何空间分解S随规则数变化线性增长几乎无影响S随域数变化不敏感慢速线性增长M随规则数变化线性增长线性增长M随树数变化较敏感慢线性增长适用性适用于规则数很少的情况速度较快占用空间小，适合高速应用线性查找的空间复杂度是O (n)，时间复杂度也是O(n)。若把查找过程分为若 十小步，并采用流水线技术，可以将平均查找时间降低一个常数因子，令k代表 流水线的阶段个数，平均查找时间变为O(N /k)，但是计算所需资源也将增加k 倍。线性查找相对较慢，但是，当根据其它算法将所有可能与输入包相匹配的规 则数目已经缩小到一个常数后，往往将线性查找作为查找的最后阶段。HiCuts是一个表现杰出的动态软件算法。用depth表示决策树的高度，binth 为决策树叶子