王 敏,邰 铭
(1.信息工程大学 网络空间安全学院,河南 郑州450001;2.信息工程大学数学工程与先进计算国家重点实验室,河南 郑州450001)
随着快速增长的网络链路速率与分类规则的增多,多维报文分类问题成为设计高速路由器的一个基本挑战。例如,当主干网链路速率达到80Gbps时,在报文长度为40字节时,需要每4ns内处理一个数据报,这个速度用现在的软件算法不可能实现。
为了满足以上网络速率的需要,研究人员寻求硬件上的解决方 案,三 态 内 容 存 储 器[1](ternary content addressable memory-TCAM)是一个不错的选择,它能够对输入的关键字进行并行查找,最大的优点是分类速度快,但也有如下一些缺点,如存储面积大、价格高,特别是TCAM不支持直接的范围匹配等。另一方面,由于FPGA具有可重构性和并行性,结合了软件的灵活性与硬件的高效性,使它成为实现实时网络处理引擎一个很好的选择。现在,研究人员已经开始在FPGA上实现一些现有分类算法[2-4],可以达到很高的吞吐量,由于存储需求过多,这些算法很少有能够支持大的规则集 (超过10K)。本文主要针对基于决策树类的分类算法在FPGA中的实现做了深入研究,解决了在规则集较大的情况下对报文进行快速分类的问题。
报文分类问题有许多定义,它们基本上是等价的,描述如下:报文头部H包含K个域,分别表示成H[1]、H[2]…H[K],一条过滤规则F相应地也具有K个域,其中F[i](F的第i部分)是H[i]的正则表达式,如果对任意的H [i]满足正则表达式F[i],则称报文P与规则F相匹配。
对具有N条过滤规则的分类器R来说,为了解决同一个报文与分类器R中多条规则相匹配的问题,在定义过滤规则F时,对每条规则指定了一个优先级,当有多条规则与报文头部匹配时,选择一个优先级最高的作为最终匹配规则。与每条规则相关联还有一个动作,它指出了当报文与此规则相匹配时,下一步所执行的操作,一个包含10规则的简单分类器见表1。
表1 10个规则的分类器例子 (IP地址8位;端口号4位;协议域2位)
也可以从计算机几何中的点定位问题来看待多维报文分类问题,一个D维的分类规则相当于D维空间中的一个超矩形,D维空间中的N个规则至多可构成 (2N-1)D个互不重叠的超矩形,而一个报文则相当于D维空间中的一个点,所以,多维报文分类转化为找到包含这个点的超矩形。由此可得到,多维报文分类的时间复杂度为O(logN),空间复杂度为O(ND),或是在时间度为O(logD-1N)的情况下,空间复杂度为O(N)。从上面的分析可以看到,多维报文分类问题是一个非常复杂的问题,幸运的是,现实情况要比这好,真实的分类器没这么复杂,它们有一些自身特点,我们可以在实际中加以利用,可以使分类算法得到简化。
由于IP分类问题可以抽象成一个查找表项巨大的多关键字查找问题,因此衡量一个算法好坏的关键是查询速度快,再就是用分类规则来构建查找表数据结构时所占内存要少。考虑到分类算法自身的特点,其它评估方法还有过滤规则的插入与删除速度快,维数 (查找中关键字个数)易扩展以及能够根据规则中各个域的不同表现形式,支持多种查询 (匹配)方式等。总的来说,算法的关键是怎么找到时间与空间的平衡点。
现有的分类算法很多,文献 [5]对各类算法进行了总结,并对每种类型的算法,列举出了相关的例子;文献[6]根据分类算法对规则进行预处理情况,把它们分为基于分解、基于分割和基于决策树3种情况。
基于分解算法的主要思想是对报文头部的每个域进行独立的搜索,最后把每个域查询结果结合起,就可得到最终匹配规则,该类型的算法适合于硬件实现,典型代表是平行位向量 (parallel bit vector)(BV)算法。
基于分割算法的主要思想是把原来的规则集划分为若干个子集,每个子集中的规则在单个或多个域之间是没有重叠的,独立集合算法 (independent sets algorithm))就属于这类。我们知道,对于有N条分类规则的D维分类器,算法所需要的空间复杂度为O(ND),现假设把规则集R均匀地划分为K组,每组有N/K个规则,划分后的空间复杂度为O(K*(N/K)D),所以通过规则集划分后,空间复杂度减少为原来的1/KD-1。算法面临的主要挑战是独立规则集划分个数的不确定性和过多。
决策树类的代表算法是HiCuts,它通过对分类器的预处理,建立决策树这种数据结构,树的根点代表整个搜索空间,它 “包含”了规则集中的所有规则,对决策树中的每个内部点,都递归地进行如下操作,根据预先定义的某种标准,选择在某一维方向上,相等地切割多少份,直到该结点所 “包含”的规则数少于预先定义的某个定值为止,不再进行切割,该结点为叶子结点。每当有报文达到时,对决策树进行遍历,找到叶子结点,由于叶子结点中的规则数较少,可以进行线性搜索,找到最佳匹配规则。Hi-Cuts算法的主要缺点是由于对搜索空间进行了切割,带来了规则的复制,增加了存储空间。HyperCuts算法是Hi-Cuts的改进版本,HiCuts是通过局部优化的方法在每个结点选择哪一维和 “切割”多少份来建立决策树,而Hyper-Cuts算法允许每一步选择多个维度进行 “切割”,其结果是树的宽度变大,深度减少。例如对表1中前5个规则所建立的决策树如图1所示 (只选择源/目的端口),可以看到对规则集端口域采用HyperCuts算法 “切割”后,决策树的深度从3变成2了。
图1 HiCuts与HyperCuts算法建立决策树的例子。((a)X轴与Y轴分别表示表1中规则R1至R5所代表的源端口域与目的端口域,(b)(c)圆矩形框表示树的内部结点,长方形框表示树的叶子结点)
现在,这几类算法都能在FPGA中实现,文献 [6]是基于分割算法在FPGA中的实现,为了避免分割的子集过多,该文献对Independent Sets algorithm进行改进,提出了coarse-grained独立集合算法,该算法把原始规则集划分为若干个coarse-grained独立集合,进行并行搜索,剩下的规则建立cross-producting表进行查询。由于对独立集合算法进行了改进,可以在coarse-grained中存放更多的规则,这样规则子集数就减少了,在Xilinx Virtex-5FPGA上实现结果表明,在消耗较少片内资源情况下,在单个FPGA芯片中能够存储10K的实时规则,在最小报文长度为40字节时,可以维持80Gbps的吞吐量。
文献 [7]把基于分割算法与决策树算法结合起来,即先把规则集分割成若干个子集,再对各个子集分别建立决策树,当报文达到时,可以对各个决策树进行并行搜索。为了使对规则的划分达到最优,作者采用范围到点转换(range-point conversion)的思想,也就是F维空间中的一个超矩形能够在2F空间中转换成一个点。从计算几何的角度来看,每个D维分类规则可以看作是D维空间中的一个超矩形,也就是2D空间中的一个点,再用组合优化的方法把这些 “点”划分成不同的集合,为了使划分达到近似最优,使用模拟退伙的方法,在各个集合之间进行相应的规则调整。当近似优化划分完成后,对每个子集用Hyper-Split[8]算法分别建立决策树,再把每棵决策树映射到专有的流水线上,由于这个设计消耗的资源较少,多个这样的机制能够在单个FPGA中实现,达到更高的吞吐量。
虽然HyperCuts算法对HiCuts有很多改进,但是在建立决策树时,虽然能减少树的深度,但并没有消除规则复制,从图2中我们可以看到,在两棵决策树中,规则R1、R2和R4都得复制到它们多个孩子结点中。通过观察可以发现,规则复制有两个来源,一是不同的规则之间相互重叠,上例中R1与R3、R5都重叠,无论怎么切割,R1都要复制到包含R3与R5的结点中去;二是在每个维度上进行均匀切割,如R2与R4都要复制一次,虽然它们没有与任何规则相重叠。需要说明的是第二点对用前缀表示的IP地址来说并不存在,因为IP地址查找是从最高有效位到最低有效位,等同于均匀切割。针对上面的问题,我们提出了两个优化的方法 (图2),一是把需要复制到多个孩子结点的规则,存储到附加在内部结点的一条链中,这个链叫做内部规则链,例如上面的R1,就可以把它选出来放在附加在根结点中的规则链中;第二种方法叫做精确范围切割,当我们对端口域进行切割时,选择能导致最小复制的切割点,如图2所示,重新选择切割点后,R2与R4就不用复制了。
图2 改进后的切割方法
结合上面两种优化思想,用以下步骤来建立决策树,首先,从根结点开始,根结点 “包含”了规则集中的所有规则,对决策树结点进行递归地切割,直到叶子,叶子结点 “包含”规则小于等于预先定义的参数binth。在每个内部结点,需要计算出对哪些维进行切割,每一维切割多少份,规则切割次数的上限为64,所以每个内部结点有2、4、8、16、32或64个孩子。对于端口域需要寻找精确的切割点,而不是切割多少份,可以限定端口域最大的切割数为2。因此没有对协议域进行切割,因为在实时规则集中,前四维就可以满足分类要求了。当选择哪些维进行切割和在源、目的IP地址上切割多少份时,标准与HiCuts和Hyper-Cuts算法一样,不同之处在于,当选择端口域进行切割时,选择的切割点能导致最少规则复制;当切割方法决定下来后,把在当前结点中复制次数最多的规则挑选出来,加到当前结点的内部规则链中,直到链中规则数达到上界binth为止。按上述方法对表1建立的决策树如图3所示。
图3 对表1中规则所建立决策树(SA/DA表示源/目的IP地址,DP表示源端口号,圆括号中的数字表示对端口号的切割点)
为了把决策树映射到流水线去,流水线每一阶段需要的存储大小都需要在FPGA实现之前确定,一般采用的方法是,把决策树相同层次上的结点映射到单独的阶段中去,由于存储分布在每个阶段变化很大,如果在每个阶段分配最大的存储量,将造成浪费。可以考虑把决策树映射到线性流水线中去,达到在每个阶段平衡存储分布的目的,同时还可以维持每个时钟周期处理一个报文的吞吐量。由于在这种体系中存在着两种流水线组织,因此,不仅在树流水线中,而且也要规则流水线中考虑各个阶段的存储分布情况,规则流水线中每个阶段需要的存储量取决于树的结点数,所以树到流水线映射的方式中,既要平衡存储分配情况,也要平衡各个阶段的结点分布情况。在把决策树映射到线性流水线的过程中,可以考虑把同一层的结点映射到流水线的不同阶段上去,这就为树结点映射提供了更多的灵活性,这样在每个阶段中能平衡存储和结点分布,需要的一个约束是,如果在决策树中结点A是结点B的祖先,则A映射到的阶段要先于B的映射。其具体映射模式如图4所示。
图4 决策树的流水线映射
当报文达到树流水线的某个阶段进行存储访问时,它同时也得到了与当前树结点相联系的规则链指针,报文利用这个指针与该规则链中的所有规则进行匹配,由于FP-GA提供了足够的字宽,每条规则作为一个字存储在规则流水线的某个阶段上。在规则流水线的某个阶段上,报文利用指针找到一个规则,并用报文头部与该规则进行比较,对不同的域,可采用不同的比较方法,如范围、前缀、定值比较。当它在当前规则流水线阶段找到匹配的规则后,遍历过程并没有结束,它需要记下当前规则优先级,以便与下一个匹配规则相比较。
当有规则需要添加或删除时,也就是规则更新,一般采用增量更新的方法,这种方法消耗存储空间较少,但是频繁的添加与删除操作将导致决策树的不稳定,最终得对决策树进行重建。这里用文献 [9]中的write-bubbles方法,即通过插入write-bubbles到各自的流水线上,可以在硬件中实现即时更新 (即在更新过程中,分类操作并没有停止)。然而,大规模的改变数据结构需要更有效方法,即缓存备份,这个方法需要建立额外的流水线来存放需要更新的数据,当这个流水线准备好了以后,与需要更新的流水线进行交换,这种方法牺牲了FPGA中的逻辑与RAM,但是带来了更有效的即时更新。
实验所用分类规则是访问控制链规则 (acl_num),规则 个 数 从 100 到 50000, 可 以 从 网 站:http://www.arl.wustl.edu/~hs1/PClassEval.html中 下 载 得 到。例如,acl_10K表示是由classbench[10]在acl种子文件下产生的10000条件规则,实验中用到了num数为100、1K、5K、10K的4种规则集。由于这个算法主要是在Hyper-Cuts算法中做了相应的改进,所以对这两种算法在两个参数上进行了比较,一是每个规则消耗的存储大小,主要用来说明算法的可扩展性;二是决策树的高度,用来指出树流水线的阶段数。比较结果见表2,从表中可以看到,随着规则数的增加,每个规则所需要的存储空间基本上保持不变,这说明了整个存储空间需求与存储规则数呈线性增长关系,易于扩展;同时,由于优化了切割方法,决策树的深度也降低了,减少了报文遍历决策树的延迟。
表2 不同规则集下算法性能比较
FPGA器件采用当前比较先进的Xilinx Virtex-6,型号是XC6VSX475T,它包含7640Kb分布式RAM和38304Kb的块RAM,时钟频率可达到115.4MHZ,其资源消耗见表3,两种算法实现结果见表4,其中效率这一项表示为吞吐量除以每个规则消耗的存储空间,主要用来说明时间与空间的平衡度问题。
表3 FPGA资源消耗情况 (acl_10K)
表4 实验结果对比
随着网络带宽的快速发展,线速多维报文分类问题成为了设计下一代网络处理设备的主要挑战,传统的软件算法已经无法满足需要。本文针对HyperCuts算法中规则复制的两个来源进行了相应改进,解决了该算法存储需求过多的缺点,基于FPGA的实验结果表明,改进后的算法能够在单个芯片上能够支持10K的规则,同时在报文长度为40字节的情况下能维持100Gbps的吞吐量。
[1]TIAN Le.Research on storage and power efficiency packet classification algorithm based on TCAM [D].Zhengzhou:Information Engineering University,2013 (in Chinese).[田乐.面向存储和功耗优化的TCAM报文分类算法研究 [D].郑州:信息工程大学,2013.]
[2]Ahmed O,Areibi S,Grewal G.Hardware accelerators targeting a novel group based packet classification algorithm [J].International Journal of Reconfigurable Computing,2013:1-30.
[3]Ahmed O,Chattha K,Areibi S,et al.PCIU:Hardware implementation of an efficient packet classification algorithm with incremental update capability [J].Intl Journal of Reconfigurable Computing,2011:1-21.
[4]Jiang W,Prasanna V K.Scalable packet classi_cation on FPGA [J].IEEE Trans VLSI Syst,2012,20 (9):1668-1680.
[5]QI Yahuan,LI Jun.The theory of high performance packet classification and algorithm summarizing [J].Journal of Computer,2013,36 (2):408-421 (in Chinese). [亓亚烜,李军.高性能网包分类理论与算法综述 [J].计算机学报,2013,36 (2):408-421.]
[6]Jiang W,Prasanna V K.A FPGA-based parallel architecture for scalable high-speed packet classification [C]//20th IEEE International Conference on Application-specific Systems,Architectures and Processors.IEEE,2009:24-31.
[7]Fong J,Wang X,Qi Y,et al.ParaSplit:A scalable architecture on FPGA for terabit packet classification [C]//IEEE 20th Annual Symposium on High-Performance Interconnects.IEEE,2012:1-8.
[8]Qi Y,Xu L,Yang B,et al.Packet classification algorithms:From theory to practice [C]//INFOCOM IEEE,2009:648-656.
[9]Qu Y R,Zhou S,Prasanna V K.High-performance architecture for dynamically updatable packet classification on FPGA[C]//Proceedings of the Ninth ACM/IEEE Symposium on Architectures for Networking and Communications Systems.IEEE Press,2013:125-136.
[10]Taylor D E,Turner J S.Classbench:A packet classification benchmark [J].IEEE/ACM Trans Netw,2007,15 (3):499-511.