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

2、學基金)作者簡介: 程光(1973),男,安徽黃山人,博士,講師,主要研究領域為網絡行為學;龔儉(1957),男,博士,教授,博士生導師,主要研究領域為網絡行為學,網絡安全;丁偉(1962),女,教授,博士生導師,主要研究領域為網絡行為學;徐加羚(1979),男,助教,主要研究領域為網絡測量.程 光1,2+, 龔 儉1,2, 丁 偉1,2, 徐加羚1,21(東南大學 計算機科學與工程系,江蘇 南京 210096)2(江蘇省計算機網絡重點實驗室,江蘇 南京 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摘 要:為了解決計算資源和高速網絡流量之間的矛盾,需要對IP流進行抽樣或負載均衡等處理,而哈希算法是資源代價的核心.首先提出評價哈希算法性能的隨機測度;其次從理論上證明比特之間異或運算和位移運算能夠提高哈希值的隨機

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

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

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

12、SX和CRC32算法進行比較.文中使用的數據來自于CERNET主干網絡流量數據和NLNAR PMA的網絡流量數據.文章研究表明,基于異或、位移原則的比特流哈希算法的執行效率和哈希值的均勻性兩方面具有較好的性質,能夠滿足高速網絡流量測量需求.1 隨機測度定義傳統上采用五元組定義流:協議、源IP(32bit)(SIP)、宿IP(32bit)(DIP)、源端口(16bit)(SPORT)、宿端口(16bit)(DPORT),由于網絡中90以上的流量為TCP流量,協議字段中信息量很小,因此本文不考慮將協議字段作為哈希算法的輸入參數.兩個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) 算法簡單、高效.本節將首先分析兩個比特隨機運算的隨機性質,然后分析異或運算的性質并證明相

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

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

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

18、(0<=p,q<=1)即,因此,同理可以證得.故定理1成立.定理1表明,相互獨立的兩個比特隨機事件之間異或可以增加結果的隨機性.如果網絡流量各比特之間存在聯系,對于兩個比特隨機變量x和h之間在某種程度上也是相互聯系的,即它們之間存在統計依賴關系.因此得知隨機變量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之間相關性很大,則獲得的位熵特性將無法保證.若

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.因此兩個隨機變量由于相關性為1,其異或運算以后位熵小于計算之前的位熵.下面需要研究兩個隨機變量相關性達到多少以后,異或運算的位熵開始減少.定義4. 隨機變量x和h之間的相關系數定義為(1)相關系數r是刻畫隨機變量x和h之間相依性的數字特征,相關系數等于0時表示不相關,而接近1時表示線性相關.定理2. 對于服從0,1分布的比特隨機變量x和h,隨機變量x中1事件出現的概率為p,h中1事件出現的概率為q,

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

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

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

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比特的相關系數3 位移運算分析本文第2節從理論上分析的異或運算可以增加偽隨機序列的隨機測度值,下面將研究比特位移對偽隨機序列隨機測度值的影響.繼續使用前文介紹的CERNET主干流量數據asipÙadip,bdipÙdport和bsipÙsport這3種組合的

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

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

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

27、循環位移3bit的平均隨機測度值最大,因此下面給出循環位移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串,但是該算法的執行性能很低,對于高速網絡主干IP流選擇,這種算法不是很合適.4.4 3種算法比較Fig. 4 Comparison among three algorithms圖4 3種算法隨機性比較Rnadomicity0.96460.96500.96540.96580.9662135791113151719shift3ipsxcrcMeasuring numbersIP流四元組隨機性分析采用兩組數據:CERNET主干和美國NLANR的PMA數據8.CERNET數據是2004年4月17日從0:00至24:00,在我國東北地區

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

31、位移哈希算法、IPSX和CRC32這3種算法哈希得到偽隨機序列的測度值如圖4所示.另一組數據來源于PMA,表3為AIX和TXS節點測量數據表,其中AIX有4組數據,AIX1,AIX2,AIX3,AIX4分別表示其中的每組數據,AIX表示這4組數據的總和;TXS共有5組數據,TXS1,TXS2,TXS3,TXS4,TXS5分別表示其中的每組數據,TXS表示這5組數據的總和.Table 2 Comparison among three algorithms using AIX and TXS dataset表2 AIX和TXS數據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異或循環哈希算法(XOR_SHIFT),IPSX,CRC這3種算法本質上都是位移和異或操作的組合,都具有時間復雜度為O(1)的運算.對于每個報文,XOR_SHIFT哈希算法要進行3次與操作、6次位移操作、5次異或操作;IPSX對于每個報文需要進行8次異或操作、8次位移操作.假設異或操作和與操作消耗硬件資源相等,則XOR_SHIFT哈希算法比IPSX算法對于每個報文少2次位移操作.而每個報文CR

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

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

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