Premium
The impact of bitwise operators on hash uniformity in network packet processing
Author(s) -
Xiong Bing,
Yang Kun,
Li Feng,
Chen Xiaosu,
Zhang Jianming,
Tang Qiang,
Luo Yuansheng
Publication year - 2014
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.2532
Subject(s) - bitwise operation , hash function , computer science , unary operation , network packet , operator (biology) , identifier , bitstream , algorithm , mathematics , computer network , discrete mathematics , computer security , programming language , biochemistry , chemistry , decoding methods , repressor , transcription factor , gene
SUMMARY Hash functions are widely applied in network packet processing, and uniformity is one of their determinant attributes. This paper investigates into the impact of bitwise operators on the uniformity of such hash functions. To this end, we first define connection identifier as their input keyword, whose uniformity is quantized by deviation index. Then, we analyze the impact of all bitwise operators on the deviation indices of its operation results. As for binary bitwise operators, we give the conditions where AND, OR and XOR increase bit uniformity, respectively, and conclude that only XOR improves the uniformity of bits in the connection identifier effectively by verifying these conditions with real network traffic. Furthermore, we derive a positive linear relationship of the uniformity of a bit‐stream and that of its any bit under simple independence assumption. As for unary bitwise operators, we prove that NOT keeps bit‐stream uniformity as the same even combined with XOR. Nevertheless, we find that circular shift with XOR changes bit‐stream uniformity with a great probability. In particular, a way is proposed to determine the optimal staggered number of two bit‐streams before their XOR operation. Lastly, we provide guidelines to design uniform hash functions with circular shift and XOR. Copyright © 2013 John Wiley & Sons, Ltd.