Research Repository

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

Xiong, B and Yang, K and Li, F and Chen, X and Zhang, J and Tang, Q and Luo, Y (2014) 'The impact of bitwise operators on hash uniformity in network packet processing.' International Journal of Communication Systems, 27 (11). 3158 - 3184. ISSN 1074-5351

Full text not available from this repository.


© John Wiley & Sons, Ltd. 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 bitstreams before their XOR operation. Lastly, we provide guidelines to design uniform hash functions with circular shift and XOR.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Jim Jamieson
Date Deposited: 11 May 2015 14:26
Last Modified: 17 Aug 2017 17:36

Actions (login required)

View Item View Item