A practical design of hash functions for IPv6 using multi-objective genetic programming

摘要

Hash functions are widely used in high-speed network traffic measurement. A hash function of high quality is supposed to meet the requirements of collision free and fast execution. Existing works have already developed methods to generate hash functions for IPv4 data, while IPv6 data with much longer addresses and different data characteristics may decline the effectiveness of those methods. In this paper, we present a practical design of hash functions for IPv6 measurement, based on the entropy analysis of IPv6 network data and an automated method of multi-objective genetic programming (GP). Considering our specific application of hash functions, we use three fitness functions as the optimization objectives, including active flow estimation, uniformity and seed avalanche effect, among which the active flow estimation is the main objective as the specific measurement task. In implementation of multi-objective GP, we adopted a strategy to limit the hash functions to shorter execution time than other hash functions by advanced experimental investigation. Experiments were conducted to construct hash functions for WIDE IPv6 network data. The results show that our generated hash functions have high usability on different evaluation criteria. It indicates that our generated hash functions are superior in active flow estimation and execution time and could compete with state of art hash functions in terms of uniformity and generating independent hash values for data structures like Bloom Filter.