The impact of bitwise operators on hash uniformity in network packet processing

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.