资源描述:
《面向ip流测量的哈希算法研究》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、1000-9825/2005/16(05)0652©2005JournalofSoftware软件学报Vol.16,No.5∗面向IP流测量的哈希算法研究1,2+1,21,21,2程光,龚俭,丁伟,徐加羚1(东南大学计算机科学与工程系,江苏南京210096)2(江苏省计算机网络重点实验室,江苏南京210096)AHashAlgorithmforIPFlowMeasurement1,2+1,21,21,2CHENGGuang,GONGJian,DINGWei,XUJia-Ling1(DepartmentofComputerScienceandEngineering,Southea
2、stUniversity,Nanjing210096,China)2(JiangsuProvincialKeyLaboratoryofComputerNetworkTechnology,Nanjing210096,China)+Correspondingauthor:Phn:+86-25-83794000ext213,E-mail:gcheng@njnet.edu.cn,http://www.njnet.edu.cnReceived2004-04-14;Accepted2004-11-22ChengG,GongJ,DingW,XuJL.AhashalgorithmforIPfl
3、owmeasurement.JournalofSoftware,2005,16(5):652−658.DOI:10.1360/jos160652Abstract:Inordertosolvetheproblemswithcomputingresourceandhigh-speednetworktraffic,itisnecessarytodealwiththenetworktrafficbysomemeasuringtechnologies,suchassamplingmeasurementandloadbalance,etc,whilethehashalgorithmison
4、eofthekeymeasuringtechnologies.Inthispaper,firstly,arandommetricisprovidedtoevaluatetheperformanceofthehashalgorithms.Secondly,therandomicityofXORandshiftoperationsareanalyzed,anditisprovedthatthetwooperationscanimprovethebitrandomicity.Thirdly,thispaperanalyzesthefourfieldsofIPpacket,suchas
5、sourceIP,destinationIP,sourceport,anddestinationport,andahashalgorithmnamedXOR_SHIFTisprovidedbasedontheanalysis.Finally,usingtheCERNETbackbonetrafficandPMAtraffic,thispaperanalyzesthecharacteroftheXOR_SHIFThashalgorithmandcompareswiththeperformanceamongXOR_SHIFT,IPSXandCRC32hashalgorithms.T
6、hisstudyshowsthattheXOR_SHIFThashfunctionprovidedinthispaperhastwoadvantages:algorithmperformanceandhashrandomicity,anditcanbeappliedtomeasurethehigh-speednetworktraffic.Keywords:hashalgorithm;networktraffic;XOR;shift;trafficmeasurement摘要:为了解决计算资源和高速网络流量之间的矛盾,需要对IP流进行抽样或负载均衡等处理,而哈希算法是资源代价的核心
7、.首先提出评价哈希算法性能的随机测度;其次从理论上证明比特之间异或运算和位移运算能够提高哈希值的随机特性,提出比特流之间哈希算法的原则;然后分析IP报文的4个字段:源IP、宿IP、源端∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.90104031(国家自然科学基金);theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.2003C