Performance of hashing-based schemes for Internet load balancing

Load balancing is a key technique for improving Internet performance. Effective use of load balancing requires good traffic distribution schemes. We study the performance of several hashing schemes for distributing traffic over multiple links while preserving the order of packets within a flow. Although hashing-based load balancing schemes have been proposed in the past, this is the first comprehensive study of their performance using real traffic traces. We evaluate five direct hashing methods and one table-based hashing method. We find that hashing using a 16-bit CRC over the five-tuple gives excellent load balancing performance. Further, load-adaptive table-based hashing using the exclusive OR of the source and destination IP addresses achieves comparable performance to the 16-bit CRC. Table-based hashing can also distribute traffic load according to unequal weights. We also report on four other schemes with poor to moderate performance.