面向IP流測量的哈希算法研究(

1、面向IP流測量的哈希算法研究*Supported by the National Natural Science Foundation of China under Grant No.90104031 (國家自然科學(xué)基金); the National Grand Fundamental Research 973 Program of China under Grant No.2003CB314803 (國家重點基礎(chǔ)研究發(fā)展規(guī)劃(973); the Foundation of Southeast University of China under Grant No.9209002157 (東南大

2、學(xué)基金)作者簡介: 程光(1973),男,安徽黃山人,博士,講師,主要研究領(lǐng)域為網(wǎng)絡(luò)行為學(xué);龔儉(1957),男,博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域為網(wǎng)絡(luò)行為學(xué),網(wǎng)絡(luò)安全;丁偉(1962),女,教授,博士生導(dǎo)師,主要研究領(lǐng)域為網(wǎng)絡(luò)行為學(xué);徐加羚(1979),男,助教,主要研究領(lǐng)域為網(wǎng)絡(luò)測量.程 光1,2+, 龔 儉1,2, 丁 偉1,2, 徐加羚1,21(東南大學(xué) 計算機科學(xué)與工程系,江蘇 南京 210096)2(江蘇省計算機網(wǎng)絡(luò)重點實驗室,江蘇 南京 210096)A Hash Algorithm for IP Flow MeasurementCHENG Guang1,2+, GONG J

3、ian1,2, DING Wei1,2, XU Jia-Ling1,21(Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China)2(Jiangsu Provincial Key Laboratory of Computer Network Technology, Nanjing 210096, China)+ Corresponding author: Phn: +86-25-83794000 ext 213, E-mail: gcheng, Received 20

4、04-04-14; Accepted 2004-11-22Cheng G, Gong J, Ding W, Xu JL. A hash algorithm for IP flow measurement. Journal of Software, 2005,16(5):652-658. DOI: 10.1360/jos160652Abstract:In order to solve the problems with computing resource and high-speed network traffic, it is necessary to deal with the netwo

5、rk traffic by some measuring technologies, such as sampling measurement and load balance, etc, while the hash algorithm is one of the key measuring technologies. In this paper, firstly, a random metric is provided to evaluate the performance of the hash algorithms. Secondly, the randomicity of XOR a

6、nd shift operations are analyzed, and it is proved that the two operations can improve the bit randomicity. Thirdly, this paper analyzes the four fields of IP packet, such as source IP, destination IP, source port, and destination port, and a hash algorithm named XOR_SHIFT is provided based on the a

7、nalysis. Finally, using the CERNET backbone traffic and PMA traffic, this paper analyzes the character of the XOR_SHIFT hash algorithm and compares with the performance among XOR_SHIFT, IPSX and CRC32 hash algorithms. This study shows that the XOR_SHIFT hash function provided in this paper has two a

8、dvantages: algorithm performance and hash randomicity, and it can be applied to measure the high-speed network traffic.Key words:hash algorithm; network traffic; XOR; shift; traffic measurement摘 要:為了解決計算資源和高速網(wǎng)絡(luò)流量之間的矛盾,需要對IP流進行抽樣或負載均衡等處理,而哈希算法是資源代價的核心.首先提出評價哈希算法性能的隨機測度;其次從理論上證明比特之間異或運算和位移運算能夠提高哈希值的隨機

9、特性,提出比特流之間哈希算法的原則;然后分析IP報文的4個字段:源IP、宿IP、源端口和宿端口的特性,由此提出相關(guān)的哈希算法;最后使用CERNET主干流量和PMA的數(shù)據(jù)驗證算法的性能,并與IPSX和CRC32算法進行比較.研究表明,基于異或、位移原則的比特流哈希算法的執(zhí)行效率和哈希值的均勻性兩方面具有較好的性質(zhì),能夠滿足高速網(wǎng)絡(luò)流量測量需求.關(guān)鍵詞:哈希算法;網(wǎng)絡(luò)流量;異或;位移;流量測量中圖法分類號:TP393文獻標識碼: AIP流測量是網(wǎng)絡(luò)管理和網(wǎng)絡(luò)流量工程技術(shù)研究和發(fā)展的重要依托,為此,IETF組織已建立了IP流信息輸出工作組IPFIX1.但是網(wǎng)絡(luò)主干流量增長迅速,1997年,MCI網(wǎng)絡(luò)

10、中的并發(fā)流數(shù)量大約為25萬條2,2003年CERNET OC48主干網(wǎng)絡(luò)流量并發(fā)流數(shù)達到300萬條.由此可見,互聯(lián)網(wǎng)發(fā)展“更大、更快”的趨勢將更進一步對網(wǎng)絡(luò)測量產(chǎn)生嚴重影響.“更大”是指互聯(lián)網(wǎng)絡(luò)將采用IPv6為基本網(wǎng)絡(luò)層協(xié)議,網(wǎng)絡(luò)用戶的增加和網(wǎng)絡(luò)服務(wù)的多樣化;“更快”是指互聯(lián)網(wǎng)主干帶寬達到OC48(2.5Gbit)甚至OC192(10Gbit),互聯(lián)網(wǎng)用戶的端到端帶寬將達到100Mbps以上.為了解決“更大、更快”網(wǎng)絡(luò)IP流測量,Cisco路由器提供NetFlow3測量IP流,并建議網(wǎng)絡(luò)速度超過OC-3時使用抽樣測量技術(shù):即在路由器內(nèi)存中維護抽樣報文的流記錄.哈希值的隨機性是基于流的抽樣技術(shù)的

11、關(guān)鍵,文獻4,5分析了5種基于IP流字段的哈希算法,可以分為兩類方法:一類6是直接使用報文中的標識字段,這種方法效率高,但是難以確保足夠的哈希值隨機性;另一類7是使用哈希函數(shù)計算哈希值,哈希函數(shù)選擇是保證哈希值隨機性和算法高效性的關(guān)鍵因素,文獻4,5的實驗結(jié)果表明,異或運算具有較高的哈希性能,但是沒有從理論上證明.本文首先提出評價哈希算法性能的隨機測度;其次從理論上證明比特之間異或運算和位移運算能夠提高哈希值的隨機特性,提出比特流之間哈希算法的原則;然后分析IP報文的4個字段:源IP、宿IP、源端口和宿端口的特性,由此提出相關(guān)的哈希算法;最后使用CERNET主干流量數(shù)據(jù)驗證算法的性能,并與IP

12、SX和CRC32算法進行比較.文中使用的數(shù)據(jù)來自于CERNET主干網(wǎng)絡(luò)流量數(shù)據(jù)和NLNAR PMA的網(wǎng)絡(luò)流量數(shù)據(jù).文章研究表明,基于異或、位移原則的比特流哈希算法的執(zhí)行效率和哈希值的均勻性兩方面具有較好的性質(zhì),能夠滿足高速網(wǎng)絡(luò)流量測量需求.1 隨機測度定義傳統(tǒng)上采用五元組定義流:協(xié)議、源IP(32bit)(SIP)、宿IP(32bit)(DIP)、源端口(16bit)(SPORT)、宿端口(16bit)(DPORT),由于網(wǎng)絡(luò)中90以上的流量為TCP流量,協(xié)議字段中信息量很小,因此本文不考慮將協(xié)議字段作為哈希算法的輸入?yún)?shù).兩個IP字段分成前16bit源IP(bsip)、后16bit源IP(a

13、sip)、前16bit宿IP(bdip)和后16bit宿IP(adip),研究一個哈希算法H,哈希算法以16bit串的六元組為輸入,一個16bit串的哈希值(hashID)為輸出,16bit的偽隨機哈希值可以保證抽樣精度達到1/216.我們首先定義比特隨機性的測度,以評價流字段各個比特的隨機性;其次定義評價比特流的隨機測度.定義1(比特隨機測度E). 定義為位熵和最大位熵Hmax(b)=1的比值,表示比特隨機程度的測度,.由定義可知,E表示隨機程度,E越接近1,表示隨機性越強,即位熵越大;E接近0,表示確定性信息越大,位熵越小.定義2(位流隨機測度E). 定義位流熵和最大位流熵Hmax(s)的

14、比值,表示比特流隨機性程度,.定義3(流標記FlowID). 每個報文具有一個四元組源IP、宿IP、源端口、宿端口,將IP字段分成前16bit串和后16bit串,因此流標記定義為FlowID=源IP前16bit(bsip)、源IP后16bit(asip)、宿IP前16bit(bdip)、宿IP后16bit(adip)、源端口(sport)、宿端口(dport).我們重點探討和研究這6個16bit串為輸入的哈希算法.2 比特隨機運算的分析哈希算法需滿足的兩點要求:(1) 生成的哈希序列隨機性盡可能大;(2) 算法簡單、高效.本節(jié)將首先分析兩個比特隨機運算的隨機性質(zhì),然后分析異或運算的性質(zhì)并證明相

15、關(guān)的定理.2.1 二元比特運算分析首先分析所有可能的二元比特運算,兩個比特之間可能的運算有種,見表1.對于比特運算而言,運算結(jié)果受制于真值表,實際上運算的種類因此是有限的.可以通過分析兩個比特之間的二元運算,歸納獲得對多比特運算有參考意義的結(jié)論.Table 1 Truth table of binary bit-wise operation表1 二元比特運算真值表000000000011111111010000111100001111100011001100110011110101010101010101AB0&AB|1顯然,對于恒0運算和恒1運算生成比特的位熵為0,無法保持良好的隨機

16、性,因此不能使用.對于產(chǎn)生結(jié)果中0和1的比例為3:1或1:3的8種運算(),如果A和B的位熵均較高,那么在A和B的相關(guān)性低(或無相關(guān)性)的情況下,生成出的結(jié)果中0和1的比例必然差異很大,所以位熵不會很高.當然,可以通過選擇兩個位熵很低的比特A和B以期獲得好的結(jié)果位熵.例如A和B都是非?？赡艹霈F(xiàn)1的,那么與(&)操作后的位熵反而可能得到很大改善.但由于選擇這樣位熵特性的比特并不直觀,所以難以確定這兩個比特所應(yīng)該具備的特性.因此,一般可以選擇的操作為0和1的比例為2:2的6種()運算,對于A,操作,其位熵等于A的位熵.同理,B和操作的位熵等于B的位熵.因此僅需分析異或運算和同或運算,且發(fā)現(xiàn)

17、這兩種運算的位熵相同.2.2 異或運算分析2.2.1 異或運算的隨機性分析定理1. 兩個獨立不相關(guān)的離散比特隨機變量x和h之間的異或運算所得的比特隨機變量x,其位熵.證明:設(shè)隨機變量x出現(xiàn)0的概率為p,出現(xiàn)1的概率為1-p;隨機變量x出現(xiàn)0的概率為q,出現(xiàn)1的概率為1-q.因此隨機變量x出現(xiàn)0的概率為,出現(xiàn)1的概率為.位熵的大小可以由0,1概率和最大位熵概率0.5之間的距離決定,如果距離0.5越近,則隨機變量x的位熵越大,反之越小.因此在證明定理1時,使用最大位熵概率0.5之間的距離為比較位熵大小測度.隨機變量x距離概率中心的距離為,隨機變量z距離概率中心的距離為,因此證明就等同于證明,即證明

18、(0<=p,q<=1)即,因此,同理可以證得.故定理1成立.定理1表明,相互獨立的兩個比特隨機事件之間異或可以增加結(jié)果的隨機性.如果網(wǎng)絡(luò)流量各比特之間存在聯(lián)系,對于兩個比特隨機變量x和h之間在某種程度上也是相互聯(lián)系的,即它們之間存在統(tǒng)計依賴關(guān)系.因此得知隨機變量x取值條件下的條件位熵H(h|x)總是不大于另一個隨機變量h的無條件位熵H(h).因此,H(h|x)表示了已知x后h殘留的不確定度,如果已知x,h的不確定度的減少量為H(h)-H(h|x).同樣,如果已知h,x的隨機程度的減少量為H(x)-H(x|h).如果兩個比特隨機變量x和h之間相關(guān)性很大,則獲得的位熵特性將無法保證.若

19、隨機變量x=0,1,0,1,0,1,而隨機變量h=0,1,0,1,0,1,雖然隨機變量x和h的位熵H(x)=1,H(h)=1,但是兩者之間的異或=0,0,0,0,0,0,0,0,其位熵H(z)=0.因此兩個隨機變量由于相關(guān)性為1,其異或運算以后位熵小于計算之前的位熵.下面需要研究兩個隨機變量相關(guān)性達到多少以后,異或運算的位熵開始減少.定義4. 隨機變量x和h之間的相關(guān)系數(shù)定義為(1)相關(guān)系數(shù)r是刻畫隨機變量x和h之間相依性的數(shù)字特征,相關(guān)系數(shù)等于0時表示不相關(guān),而接近1時表示線性相關(guān).定理2. 對于服從0,1分布的比特隨機變量x和h,隨機變量x中1事件出現(xiàn)的概率為p,h中1事件出現(xiàn)的概率為q,

20、E(x)=p,E(h)=q.異或后的隨機變量位熵H(z)>=max(H(x),H(h)的條件是隨機變量x,h之間的相關(guān)系數(shù).(2)證明:對于服從0,1分布的比特隨機變量x和h,隨機變量x中1事件出現(xiàn)的概率為p,h中1事件出現(xiàn)的概率為q,E(x)=p,E(h)=q.其協(xié)方差:=E(xh)-pq,相應(yīng)地,.x和h的相關(guān)系數(shù)為 .隨機變量(x,h)出現(xiàn)的事件有4種(00,01,10,11),設(shè)每種事件出現(xiàn)的概率分別為p00,p01,p10,p11,這4個概率之間的關(guān)系是:,由于0´0=0´1=1´0=0, 1´1=1,因此E(xh)=p11.隨機變量的0

21、事件出現(xiàn)的概率, .設(shè)隨機變量x,h對應(yīng)的位熵分別為H(x),H(h),設(shè)H(x)>=H(h),比特事件0,1出現(xiàn)的概率距0.5中心的距離可以認為是位熵的大小,同時可知0,1出現(xiàn)的概率以0.5為中心左右對稱.因此0,1概率之間的距離反映位熵的大小,兩者之間的距離越近,則位熵越大,否則位熵越小.隨機變量x的0,1概率之間的間距為|2p-1|,隨機變量h的0,1概率之間的距離為|2q-1|,如果H(x)>=H(h),則|2p-1|<=|2q-1|.需要證明在相關(guān)系數(shù)r到達多少時,其位熵=max(H(x),H(z)=H(x),即證明|2p-1|=|p0-p1|=.,.因此相關(guān)系數(shù)滿

22、足下列條件.異或后的位熵會增加,證明完畢.對CERNET數(shù)據(jù)分析表明,FlowID 6個字段的比特之間均滿足定理2的條件.如圖1所示,是源宿IP第32bit之間的相關(guān)系數(shù)r,從圖1可以看出,|r|曲線在|r1|,|r2|下方,滿足定理2的條件,所以兩個比特之間進行異或計算會增加隨機性.6個流字段之間進行異或計算可以增加偽隨機序列的隨機測度值,因此在基于異或的哈希函數(shù)不變的情況下,將全部的6個流字段作為哈希函數(shù)的輸入,所得到的隨機序列的隨機測度值最大.根據(jù)異或運算的結(jié)合率和交換率兩個性質(zhì)可以容易得出,流字段之間以不同的順序進行異或運算不會改變偽隨機序列的隨機測度值.因此異或哈希算法可以不用考慮不

23、同字段之間的運算次序.00.050.100.150.200.2513579111315|r|r1|r2|Measuring numbersFig.1 Correlation coefficient of the 32th bit in source IP and destination IP圖1 源宿IP第32比特的相關(guān)系數(shù)3 位移運算分析本文第2節(jié)從理論上分析的異或運算可以增加偽隨機序列的隨機測度值,下面將研究比特位移對偽隨機序列隨機測度值的影響.繼續(xù)使用前文介紹的CERNET主干流量數(shù)據(jù)asipÙadip,bdipÙdport和bsipÙsport這3種組合的

24、隨機測度值進行分析.圖2是這3種組合位移和隨機測度之間的關(guān)系圖,從圖中可以明顯看出,流字段位移26bit異或生成的偽隨機序列的隨機測度值大于不位移或位移其他的值.圖3是asipÙadip,bdipÙdport和bsipÙsport三者之間異或后生成偽隨機序列的隨機測度值,其中shifti表示asip,bdip和bsip進行循環(huán)位移i個比特,其中shift0表示不進行循環(huán)位移,分不同的時間總共測量20次,每次連續(xù)測量200 000條流.從圖中可以看出,循環(huán)位移16bit的隨機測度值大于循環(huán)位移為0的隨機測度值,這6組平均值的差別最大不超過0.000 4,其中平均隨機

25、測度值最大的是shift3.Fig.2 Shift and randomicity圖2 位移和隨機測度之間的關(guān)系0.910.920.930.9413579111315bsipÙsportasipÙadipbdipÙdportRandomicityShift bit numbersFig.3 Shift and randomicity of FlowID圖3 FlowID的位移數(shù)和隨機測度值0.9400.9450.9500.9550.9600.9650.970135791113151719shift0shift1shift2shift3shift4shift5shi

26、ft6RandomicityShift bit numbers4 哈希算法及其性能分析根據(jù)前文對IP流字段異或、位移分析和設(shè)計原則,我們提出了一種基于異或、位移算法,同時給出IETF工作組PSAMP提出的IPSX和CRC32算法,然后對這3種算法的隨機特性進行比較.設(shè)bsip為源IP前16bit、asip為源IP后16bit、bdip為宿IP前16bit、adip為宿IP后16bit、sport為源端口、dport為宿端口;算法使用XOR(Ù),右移(>>)和左移(<<)操作;hash1,hash為16bit無符號整型.4.1 異或位移哈希算法從上文分析可知,

27、循環(huán)位移3bit的平均隨機測度值最大,因此下面給出循環(huán)位移3bit的異或、位移哈希算法(XOR_SHIFT).hash1=asip<<3|asip>>(16-3);hash1=hash1Ùadip;hash=hash1;hash1=bsip<<3|bsip>>(16-3);hash1=hash1Ùsport;hashÙ=hash1;hash1=bdip<<3|bdip>>(16-3);hash1=hash1Ùdport;hashÙ=hash1.其中hash是異或、位移算法返

28、回的哈希序列.4.2 IPSX哈希算法f1=IP源地址,f2=IP宿地址,f3=TCP或UDP報文的源端口和宿端口.中間變量h1,v1,v2均是32比特串.算法的輸出是h1的后16bit串.v1=f1Ùf2;v2=f3;h1=v1<<8; h1Ù=v1>>4;h1Ù=v1>>12;h1Ù=v1>>16;h1Ù=v2<<6;h1Ù=v2<<10;h1Ù=v2<<14;h1Ù=v2>>7.4.3 CRC32哈希算法CRC32

29、哈希算法具有較小的沖突性,它的輸出是一個具有足夠隨機化的32bit串,但是該算法的執(zhí)行性能很低,對于高速網(wǎng)絡(luò)主干IP流選擇,這種算法不是很合適.4.4 3種算法比較Fig. 4 Comparison among three algorithms圖4 3種算法隨機性比較Rnadomicity0.96460.96500.96540.96580.9662135791113151719shift3ipsxcrcMeasuring numbersIP流四元組隨機性分析采用兩組數(shù)據(jù):CERNET主干和美國NLANR的PMA數(shù)據(jù)8.CERNET數(shù)據(jù)是2004年4月17日從0:00至24:00,在我國東北地區(qū)

30、網(wǎng)絡(luò)中心對CERNET主干網(wǎng)絡(luò)主干測量流量,連續(xù)測量24小時數(shù)據(jù),每個報文截取報文頭44字節(jié)加上8字節(jié)的時戳,總共測量到18G報文,本文中使用的CERNET數(shù)據(jù)全部來自于這組數(shù)據(jù)源.第2組數(shù)據(jù)來源是美國應(yīng)用網(wǎng)絡(luò)研究國家實驗室(NLANR)的被動測量和分析工作組(PMA),PMA在HPC網(wǎng)絡(luò)中設(shè)置多個測量點被動測量Internet數(shù)據(jù),其中本文使用從節(jié)點AIX和TXS于2002年9月30日測量的報文,其數(shù)據(jù)格式為TSH,每個報文44字節(jié)長度,TSH數(shù)據(jù)格式包含整個IP報頭和TCP報頭的內(nèi)容.CERNET數(shù)據(jù)源中抽取20組,每個小時的數(shù)據(jù)中抽取一組,每組中的數(shù)據(jù)有200 000條流,分別使用異或、

31、位移哈希算法、IPSX和CRC32這3種算法哈希得到偽隨機序列的測度值如圖4所示.另一組數(shù)據(jù)來源于PMA,表3為AIX和TXS節(jié)點測量數(shù)據(jù)表,其中AIX有4組數(shù)據(jù),AIX1,AIX2,AIX3,AIX4分別表示其中的每組數(shù)據(jù),AIX表示這4組數(shù)據(jù)的總和;TXS共有5組數(shù)據(jù),TXS1,TXS2,TXS3,TXS4,TXS5分別表示其中的每組數(shù)據(jù),TXS表示這5組數(shù)據(jù)的總和.Table 2 Comparison among three algorithms using AIX and TXS dataset表2 AIX和TXS數(shù)據(jù)3種哈希算法隨機測度值比較AIXAIX1AIX2AIX3AIX4TX

32、SNumber of packets1 931 949621 103605 741393 969311 1362 049 940XOR_SHIFT0.995 180.990 90.989 60.988 70.985 60.993 6IPSX0.787 510.761 40.770 30.760 70.777 40.792 6CRC0.996 050.991 70.990 90.988 60.986 20.995 3TXS1TXS2TXS3TXS4TXS5Number of packets456 544363 157493 418374 960361 861XOR_SHIFT0.974 30.9

33、86 00.990 00.987 40.979 3IPSX0.780 30.745 30.746 40.748 10.781 4CRC0.978 00.987 90.991 00.987 60.981 2異或循環(huán)哈希算法(XOR_SHIFT),IPSX,CRC這3種算法本質(zhì)上都是位移和異或操作的組合,都具有時間復(fù)雜度為O(1)的運算.對于每個報文,XOR_SHIFT哈希算法要進行3次與操作、6次位移操作、5次異或操作;IPSX對于每個報文需要進行8次異或操作、8次位移操作.假設(shè)異或操作和與操作消耗硬件資源相等,則XOR_SHIFT哈希算法比IPSX算法對于每個報文少2次位移操作.而每個報文CR

34、C32運算需要異或運算至少1 536次操作,與操作3 072次操作,因此XOR_SHIFT運算效率遠高于CRC32運算.雖然提出CRC32簡化的BOB9哈希函數(shù),但BOB哈希函數(shù)的異或操作和與操作仍有300多次.從圖4和表2可以看出,XOR_SHIFT算法的隨機測度值和CRC32算法接近,但是高于IPSX算法,CERNET主干流量的XOR_SHIFT和CRC32算法的隨機測度值與TXS和AIX流量的隨機測度值接近,而CERNET流量的IPSX隨機測度值大于TXS和AIX流量的隨機測度值.其原因是CERNET主干比TXS和AIX覆蓋網(wǎng)絡(luò)范圍要大,因而CERNET的FlowID隨機測度值比TXS,

35、AIX要大.同時,由于IPSX算法沒有考慮IP流的本身特性,因此不能獲得較高的隨機測度值.5 結(jié) 論文獻4,5通過大量的實驗發(fā)現(xiàn),XOR和CRC16算法具有較好的隨機性,但是并沒有說明隨機性較好的原因,且給出的隨機測度不能統(tǒng)一描述不同的比特流序列,同時也沒有給出面向IP流的哈希算法.PSAMP提出的IPSX沒有考慮IP流的本身特性,沒有討論設(shè)計算法的理論依據(jù),其算法的隨機性不理想且難以滿足網(wǎng)絡(luò)測量的實際使用;而其建議的CRC32算法時間復(fù)雜度太大,不利于高速網(wǎng)絡(luò)流量測量.本文相對于前人的工作,貢獻主要體現(xiàn)在3個方面:(1) 提出了一個評價哈希算法隨機特性的測度,隨機測度為評價哈希算法的優(yōu)劣提供

36、了測度指標.(2) 從理論上分析了異或運算和位移運算的隨機特性,并提出了設(shè)計基于IP流哈希算法的基本原則.(3) 提出了基于IP流特性的哈希算法,循環(huán)位移和異或相結(jié)合的哈希算法(XOR_SHIFT),通過實驗表明,循環(huán)位移3,4,6個比特的哈希函數(shù)生成的偽隨機序列隨機測度值較大,并與PSAMP提出的CRC32和IPSX兩種哈希算法進行比較.研究表明,XOR_SHIFT哈希算法生成偽隨機序列的隨機測度值在統(tǒng)計上和CRC32哈希函數(shù)生成的偽隨機序列隨機測度值差別很小,但執(zhí)行效率高于CRC32算法.XOR_SHIFT算法執(zhí)行效率和IPSX接近,但是算法生成的偽隨機序列的均勻性高于IPSX.由于本文的XOR_SHIFT算法設(shè)計方法是基于IP流的特性,傳統(tǒng)的CRC32和IPSX算法是從通用性角度研究,因此本文的算法在執(zhí)行效率和隨機特性兩個方面優(yōu)于其他算法.References: