Hashing-Based Traffic Splitting Algorithms for Internet Load Balancing

Abstract

Replication of resources is a key technique for improving Internet performance. Effective use of replicated resources requires good load distribution schemes. We study the performance of several hashing schemes for distributing traffic while preserving the order of packets within a flow. Traffic distribution with per-flow ordering has applications that include balancing traffic across multiple Internet access links and balancing HTTP request load in a web server farm. While hashing schemes for load balancing have been proposed in the past, this is the first comprehensive study of 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 TCP 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 load according to unequal weights. We also report on four other schemes with poor to moderate performance.