用于特定流匹配的随机矩阵映射Hash算法研究.doc

第2期唐红等：用于特定流匹配的随机矩阵映射Hash算法研究21用于特定流匹配的随机矩阵映射Hash算法研究唐红, 吴勇军, 赵国锋(重庆邮电大学，重庆 400065)摘 要：针对常规的Hash算法用于流匹配时冲突率高且不可控制的缺点，提出了一种随机矩阵映射Hash算法。该算法通过预先优选一个随机数矩阵，然后将大集合的元素分块映射成随机矩阵中的元素，从而把一个大集合映射到一个小集合。测试结果表明，该算法运算速度快、空间利用率高、冲突率低，用于流匹配时匹配速度可以达到2Mpacket/s，支持规则数达5万条以上。关键词：流匹配；随机矩阵映射；Hash算法；流量测量中图分类号：TN393.06 文献标识码：A 文章编号：1000-436X(2007)02-0017-06Research on stochastic matrix mapping Hash for specific flow matchingTANG Hong, WU Yong-jun, ZHAO Guo-feng(Chongqing University of Posts and Telecommunications, Chongqing 400065,China)Abstract: Because a general Hash algorithm had high collision rate and was not controlled while be used to flow matching, a stochastic matrix mapping Hash algorithm was presented, in which the elements of a large set were mapped into a small set through a pre-choosing stochastic number matrix. Tests show that the algorithm has high operation speed, high storage utilization rate and low collision rate, its flow matching speed is up to 2 million packets per second and it supports 50000 matching rules. Key words: flow matching; stochastic matrix mapping; Hash algorithm; traffic measurement1 引言收稿日期：2005-01-10；修回日期：2006-12-23基金项目：重庆市自然科学基金资助项目(CSTC，2003BB2195)；重庆市科技攻关项目(7220-13-20)；重庆市教委科技项目(001704) Fundation Items: The Natural Science Fundation of Chongqing(CSTC, 2003BB2195); Technology Project of Chongqing Science & Technology Commission(7220-13-20); Technology Project of Chongqing Education Commission(001704)对网络中的流量进行测量是进行网络管理、提供QoS保证的必要手段。然而在高速网络中要对所有流进行测量几乎是不可能的1，因此基于特定流的测量是流量测量发展的一个重要方向2。网络中的特定流指的是业务大客户或签订了SLA合同的用户产生的业务流，以及流量很大，容易对网络带宽和服务质量造成较大影响的业务流。如果能对这部分业务流进行测量和监视，就能很好地保证整个网络的QoS。而对网络中的特定流进行测量的关键是要快速对到达的数据包进行匹配以确定它属于哪一个流，因此流匹配算法性能的优劣是关系到能否对高速网络中特定流进行准确测量的关键。目前采用的流匹配算法主要有4类：1）BPF算法，该算法采用CFG(control flow graph)模式进行包过滤3，缺点是编制过滤规则复杂。2）利用SRL编写匹配规则集4，SRL(simple rule language)类似一种高级语言，它将匹配的规则用条件语句、转移语句的形式编制成匹配流程，采用的是线性匹配，匹配速度低。3）多域数据包分类算法，如RFC(recursive flow classification)是把包头的比特映射到classID的比特(,为规则数)5。这3种方法的共同缺点是不能支持大的匹配规则集，并且前2种方法匹配速度慢，而RFC算法对内存要求太大，因此这3种方法不能很好地满足高速网络中对大量流进行匹配的需要。4）Hash算法，一种常用的匹配算法，它通过一个Hash函数，将大集合的元素映射成一个小集合的有序元素，以便于快速查找。对于关键字和，若，有，则称为冲突(collision)。一个好的散列函数应具有下列特征6：避免冲突；均匀分配关键字；计算简单。常用的Hash算法有取模法(Mod Hash)、平方取中法(Middle-square Hash)6等。文献7提出了采用CRC(cyclic redundancy check)的Hash、采用Fletcher校验和的Hash以及采用XOR的Hash。文献8提出了一种无冲突Hash算法，它在大集合有限且已知的情况，可以实现无冲突。Tuple space search9利用规则前缀长度形成的元组空间作为一个Hash关键值。Modular10算法利用规则的某些bit位来形成一个Hash关键值。Hash算法用于流匹配的主要优点是运算简单、预处理时间短，内存消耗低，支持匹配规则数多。NeTraMet、NetFlow、Nprobe等工具主要采用Hash算法进行流匹配。但常规的Hash算法用于高速网络中特定流匹配还存在一些问题，主要有：由于每条规则的比特数较长，要将大集合值映射到一个小集合，冲突率非常高，运算速度慢，而且运算量大；由于每条规则的比特位可能有许多是相同的，采取常规Hash算法，其结果不具有均匀分布的特点；常规的Hash算法不能针对不同的规则集通过优化获得一个最低的冲突率。为了克服这些缺点，提出了一种称为随机矩阵映射(SMM, stochastic matrix mapping)Hash算法。2 SMM Hash定义1 设一个大集合的每个元素的比特长度为，小集合每个元素的比特长度为()，现将大集合每个元素的比特分成块，表示为，每块的比特数为，则。显然小集合的空间为，大集合的空间为，而。又设一随机矩阵，矩阵的每一个元素为之间的一个随机数，用二进制表示为，它满足条件 。SMM Hash的主要思想是通过预先优选一个随机矩阵，然后将大集合X的一个元素分成个块，每个块通过一个无冲突的散列函数映射成中的一个元素，再将个随机数进行异或，从而得到一个Hash关键值。以上过程表示为(1)其中，(2)(3)函数表示将输入变量()经过一次无冲突的Hash运算，映射到矩阵中的；函数表示将个经过函数变换的值进行异或运算。定理1 SMM Hash映射结果在间服从均匀分布。证明 1）对于任一集合的一个元素按比特分成块，每块比特数为，每块的值为()，第个块执行式(2)运算后，得到的值=，满足( )(4)2)设有任意2个由式(2)产生的值R= ，=;3) 令：=|(运算符|表示异或运算)，相应有;4) 根据异或运算的性质：若，则且或者且，所以有同理可以证明;5) 设，则 ()，则同理可以证明。所以有：对于2个满足式(4)的随机数进行异或运算后，其结果在空间的服从均匀分布。同理可以证明对于有限个满足式(4)的随机数进行异或运算后，其结果在空间的服从均匀分布。证毕。定义2 一个集合的每个元素分成 共块(,)，对个由的任意排列形成的元素的个块进行加法或者异或运算时，它们都具有相同的Hash关键值，这种现象称为自相关冲突。如常规的Mod Hash、Middle-square Hash和XOR Hash，当交换块与块之间的值形成一个新元素时，必然存在。定理2 SMM Hash自相关冲突率为。设集合的一个元素分成 (,)，这个值按式(2)计算得到。交换和的顺序得到，同时这个值按式(2)计算得到。如果，则，。根据式(3)，有，。由于,为同一空间的随机数，根据定理1，2个随机数异或的结果仍为同一空间的随机数，则，分别为空间内的2个随机数。根据均匀分布的特性， (表示排列)因此，当, =。同理，可以证明对的次排列，当组合形成的新元素时，概率为，即发生冲突的概率为。定理3 SMM Hash的冲突率在概率上具有确定性。对服从均匀分布，空间为的随机数集合，每个元素出现的概率为,从中随机抽取个元素，出现最多个冲突的概率可以表示为(表示排列，表示组合)(5)根据定理1，随机矩阵映射具有与均匀分布的随机数集合同样的分布，因此SMM Hash的冲突率同样满足式(5)，即它的冲突率在概率上具有确定性。3 SMM Hash用于流匹配3.1 预处理和匹配过程SMM Hash用于流匹配包括2个过程：一是预处理，二是匹配。预处理过程如下：1) for()/寻找K（K为优化次数）个随机矩阵；2) for() 3) for()4) =Random(m)；5) for() /从K个矩阵中选取冲突最小的矩阵；6) while(rules_set is not EOF) 7) ； /将每条规则的L比特分成n块8) =；=；=/每个值映射成一个随机数9) ； /将个块进行异或运算得到Hash关键 值，G为一数组10) Cicount_ collision_number(G)；11) if()12)； 13)；14) 执行步骤6） 9），将其中的Ri替换为。将相应匹配号写入Hash关键字所在的内存区域，同时将规则内容写入与匹配号对应的匹配规则存放区域，如存在冲突则以拉链的方式进行冲突处理。匹配过程如下：1) ； 2) =；=；=；3) ；4) 将包头相应的特征值与Hash关键值对应的规则存放区的的规则内容进行比较，如果匹配则返回相应的规则号，如不匹配则返回匹配失败；5) 当形成的Hash索引值对映的位置存在拉链时，则进行顺序查找比较。这种计算Hash值的方法有如下优点：由于随机矩阵可以针对不同的X集合随机产生，因此可以保证将X集合的元素映射到集合时有较低的冲突率；对于集合X，如果它的元素本身是由个块分别构成，那么通过这种随机矩阵映射运算获取Hash值时，不必将其联合成一个值；如果规则集中的规则特征值发生了变化，即的值改变了，只需要相应增加或减少R矩阵行的个数或对集合X进行重新分块，即可以同样的方法完成Hash关键值的计算。3.2 SMM Hash用于流匹配的性能由于SMM Hash用于匹配的时间耗费主要是对一条规则的个块进行比较，因此时间复杂度为，它在空间上主要是用于存储N条规则和个随机数，因此空间复杂度为(N为规则数)。Mod Hash和Middle-square Hash的时间复杂度为，空间复杂度为。由于SMM Hash的映射结果服从均匀分布，因此它的冲突率低，从而减少了比较次数。由于SMM Hash采用的是异或运算，而Mod Hash和Middle-square Hash采用的是加运算和乘运算，而在通用的运算器上，异或运算快于加运算和乘运算。4 SMM Hash用于流匹配的测试结果在P1.4GHz，内存128MB，Windows 2000环境下用VC+6.0对SMM Hash与Mod Hash，Middle-square Hash用于特定流匹配的过程进行了测试和比较。3种方法按式(1)计算Hash关键值，其中，SMM Hash的函数为式(2)，函数为式(3)。Mod Hash的函数为，函数为；Middle-square Hash的函数6为8，函数为。匹配规则包括源IP、目的IP、源端口、目的端口和协议共5个字段112bit(协议字段高8bit需补充0，扩展为16bit)，并将它分成7个块，每个块16bit。1) 冲突率和冲突率的波动。从图1可以看出SMM Hash的冲突率最低，它在规则数低于1 000条时冲突率为1%。通过对10个不同的有10 000条规则的规则库进行测试，SMM Hash冲突率的标准方差为0.104，Middle-square Hash的标准方差为0.327，Mod Hash的标准方差为0.216。即SMM Hash的冲突率对规则集的变化的敏感程度低于其他2种。图1 3种Hash算法的冲突率比较 2) 随机矩阵选取次数与冲突率的关系以及优选随机矩阵时间与规则数的关系。从图2看出，经过10次优选后，规则数分别为1 000条、5 000条和10 000条时冲突率基本上保持在1%、3%和7%。可见对于一个给定的规则库，经过有限次(小于10)的优选后可以找到一个较低冲突率的随机矩阵。图2 SMM Hash冲突率与随机矩阵优选次数的关系3) 匹配时间。图3是SMM Hash、Mod Hash和Middle-square Hash 3种Hash算法每个数据包的平均处理时间。从图中可以看出，SMM Hash的处理时间最少，它比Mod Hash快约4.3%，比Middle-square Hash快约13.5%。在10 000条规则时，SMM Hash每个数据包的平均处理时间为486ns，即每秒可处理200万个数据包。图3 3种Hash算法的匹配时间比较4) SMM Hash与Tupe Space的比较。文献9中的Tupe Space算法用于流匹配时的一个重要前提是：匹配规则分成多个小集合后，元组数量可大大减少。但当匹配规则不具备这一条件时，比如，用于骨干网上的流匹配规则集变化就相当大。在这种情况下，元组的数量会急剧增加，从而使该算法性能迅速恶化。采取随机生成匹配规则集，当规则数达到10 000条以上时，Tupe Space算法的匹配时间大大超过SMM Hash(如图4所示)。因此，SMM Hash与Tupe Space算法相比，最大的优点就是可支持更大数量的流匹配规则集。同时，SMM Hash算法用于流匹配时，只提取每个数据包的源IP、目的IP、源端口、目的端口和协议等字段，因此所需匹配时间、内存大小等与数据包大小无关。图4 Tupe Space与SMM Hash比较SMM Hash的缺点是必须在进行Hash计算前进行预处理来产生一个随机矩阵，同时，为达到较低冲突率的效果，必须对随机矩阵进行优化。为找到一个冲突率较低的随机矩阵映射一般需要约10次的优化，预处理时间为120s。由于基于特定流测量的流匹配规则库变化不频繁，对于给定的一组规则只需进行一次随机矩阵的优化，以后只需简单读入该优化的随机矩阵，这样可大大节省预处理时间。5 结束语本文针对特定流匹配的特点，提出了一种SMM Hash算法。由于采用了随机矩阵映射，使计算出的Hash关键值服从均匀分布且能减少自相关冲突，因此该算法在冲突率、匹配时间等方面都优于一般的Mod Hash和Middle-square Hash。这种算法的匹配速度可达2Mpacket/s，支持的匹配规则数可达5万条以上，而内存消耗不到2MB。但与一般的Hash算法相比，这种方法需要120s的预处理时间，同时与其它Hash算法一样不能支持掩码匹配和范围匹配。下一步还需要进一步研究随机矩阵的产生方法以减少预处理时间，同时还要研究如何支持掩码匹配和范围匹配。参考文献：1MILOUCHEVA I, NASSRI A, HOFMANN U. Traffic measu-rement and monitoring roadmapEB/OL. /pro-jects/ traffic_ngni. pdf, 2002.2ESTAN C, VARGHESE G. New directions in traffic measurement and accountingA. Proceedings of ACM SIGCOMM 2002C. Pittsburgh, Pennsylvania, 2002. 159-71.3MCCANNE S, JACOBSON V. The BSD packet filter: a new architecture for user-level packet captureA. Proceedings of the 1993 Winter USENIX Technical ConferenceC. San Diego, CA, 1993. 259-269.4BROWNLEE N. RFC2123: Traffic Flow Measurement Experiences with NeTraMetS. 1997.5GUPTA P, MCKEOWN N. Packet classification on multiple fieldsA. Proceedings of ACM Sigcomm99C.1999. 146-160. 6BRUNO R. Preiss数据结构与算法面向对象的C+设计模式M. 北京:电子工业出版社, 2000. 156-194.BRUNO R. Preiss Data Structure and AlgorithmObject-Oriented C+ Programming PatternM. Beijing:Publishing House of Electrionics Industry, 2000. 156-194.7JAIN R. Acomparison of hashing schemes for address lookup in computer networksJ. IEEE Transactions on Communications, 1992, 40(3): 1570-1573.8XU K, WU J P, YU Z C, et al. A non-collision hash trie-tree based fast IP c1assification a1gorithmJ. J Computer Sci &Technol, 2002, 17(2): 219-226.9SRINIVASAN V, SURI S, VARGHESE G. Pa