Research Repository

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

Xiong, Bing and Yang, Kun and Li, Feng and Chen, Xiaosu and Zhang, Jianming and Tang, Qiang and Luo, Yuansheng (2013) 'The impact of bitwise operators on hash uniformity in network packet processing.' International Journal of Communication Systems, 27 (11). n/a-n/a. ISSN 1074-5351

Full text not available from this repository.


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
Uncontrolled Keywords: network packet processing; hash uniformity; bitwise operators; connection identifier; deviation index
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 11 May 2015 14:26
Last Modified: 23 Sep 2022 18:41

Actions (login required)

View Item View Item