Effect of Hash Collisions on the Performance of LAN Switching Devices and Networks

摘要

Hash tables are often used in LAN switching devices for MAC address lookup. The lookup is a central function, which significantly affects performance of such devices and their networks. Along with desirable reductions in cost and resource usage, hashing is accompanied by hash collisions, which result in decreased hash table capacity and inefficient bandwidth usage. This paper shows the effect of hash collisions on the performance of LAN switching devices, using calculations and empirical data for six devices from different vendors. Test results demonstrate that the ability to store addresses in a hash table greatly depends on address distribution and the hash function used. For all devices a significantly reduced table capacity was observed for random addresses, compared to sequential addresses. In some cases hash table performance in real networks can be improved by implementing hash functions optimized for the particular address distribution. Where it is possible address lookup can be performed using other technologies, such as content addressable memory or binary search.