Hashing Functions Performance in Packet Classification

Abstract — Packet classification remains an important aspect of network processing as it encompasses increasingly more functionality due to newly introduced services. Essentially, it entails the matching of incoming packets against a database of rules performing the operation that is associated with the matching rule with the highest priority. Within the hashingbased packet classification algorithms, the tuple space search algorithm is gaining much interest. Using tuple spaces, the rules can now be subdivided into sets and in turn these sets can be searched in parallel. Within each set, the hashing functions determine the location of storing the rules. However, depending on the chosen collection of hashing functions, rules (within a set) can be mapped to the same location (containing multiple buckets to store the rules) resulting in a collision. A side-effect of such collisions is that more memory accesses are needed to resolve the collision resulting in degraded performance. In this paper, we compare and evaluate different hashing functions taking from the H3 class of hashing functions using which collisions can be reduced and in turn reduce the average bucket sizes. Our results show that when using the H3 class of hashing functions, we were able to reduce the number of collisions by at least 7 % and by at most 49 % when compared to other hashing functions