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

《用于特定流匹配的随机矩阵映射hash算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2期唐红等：用于特定流匹配的随机矩阵映射Hash算法研究·21·用于特定流匹配的随机矩阵映射Hash算法研究唐红,吴勇军,赵国锋(重庆邮电大学，重庆400065)摘要：针对常规的Hash算法用于流匹配时冲突率高且不可控制的缺点，提出了一种随机矩阵映射Hash算法。该算法通过预先优选一个随机数矩阵，然后将大集合的元素分块映射成随机矩阵中的元素，从而把一个大集合映射到一个小集合。测试结果表明，该算法运算速度快、空间利用率高、冲突率低，用于流匹配时匹配速度可以达到2Mpacket/s，支持规则数达5万条以上。关键词：流匹配；随机矩阵映射；Hash算法；流量测量中图分类号：TN393.06

2、文献标识码：A文章编号：1000-436X(2007)02-0017-06ResearchonstochasticmatrixmappingHashforspecificflowmatchingTANGHong,WUYong-jun,ZHAOGuo-feng(ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)Abstract:BecauseageneralHashalgorithmhadhighcollisionrateandwasnotcontrolledwhilebeusedtoflowma

3、tching,astochasticmatrixmappingHashalgorithmwaspresented,inwhichtheelementsofalargesetweremappedintoasmallsetthroughapre-choosingstochasticnumbermatrix.Testsshowthatthealgorithmhashighoperationspeed,highstorageutilizationrateandlowcollisionrate,itsflowmatchingspeedisupto2millionpacketspersecond

4、anditsupports50000matchingrules.Keywords:flowmatching;stochasticmatrixmapping;Hashalgorithm;trafficmeasurement第2期唐红等：用于特定流匹配的随机矩阵映射Hash算法研究·21·1引言收稿日期：2005-01-10；修回日期：2006-12-23基金项目：重庆市自然科学基金资助项目(CSTC，2003BB2195)；重庆市科技攻关项目(7220-13-20)；重庆市教委科技项目(001704)FundationItems:TheNaturalScienceFundationof

5、Chongqing(CSTC,2003BB2195);TechnologyProjectofChongqingScience&TechnologyCommission(7220-13-20);TechnologyProjectofChongqingEducationCommission(001704)对网络中的流量进行测量是进行网络管理、提供QoS保证的必要手段。然而在高速网络中要对所有流进行测量几乎是不可能的[1]，因此基于特定流的测量是流量测量发展的一个重要方向[2]。网络中的特定流指的是业务大客户或签订了SLA合同的用户产生的业务流，以及流量很大，容易对网络带宽和服务质量造成较

6、大影响的业务流。如果能对这部分业务流进行测量和监视，就能很好地保证整个网络的QoS。而对网络中的特定流进行测量的关键是要快速对到达的数据包进行匹配以确定它属于哪一个流，因此流匹配算法性能的优劣是关系到能否对高速网络中特定流进行准确测量的关键。目前采用的流匹配算法主要有4类：1）BPF算法，该算法采用CFG(controlflowgraph)模式进行包过滤[3]，缺点是编制过滤规则复杂。2）利用SRL编写匹配规则集[4]，SRL(simplerulelanguage)第2期唐红等：用于特定流匹配的随机矩阵映射Hash算法研究·21·类似一种高级语言，它将匹配的规则用条件语句、转移语句的

7、形式编制成匹配流程，采用的是线性匹配，匹配速度低。3）多域数据包分类算法，如RFC(recursiveflowclassification)是把包头的比特映射到classID的比特(,,为规则数)[5]。这3种方法的共同缺点是不能支持大的匹配规则集，并且前2种方法匹配速度慢，而RFC算法对内存要求太大，因此这3种方法不能很好地满足高速网络中对大量流进行匹配的需要。4）Hash算法，一种常用的匹配算法，它通过一个Hash函数，将大集合的元素映射成一个小集合的