HashNAT: a distributed packet rewriting system using adaptive hash functions

As traffic on the World Wide Web increases, more power is needed to serve Web pages. But large, powerful servers are expensive and proprietary. An alternative is to split up the task of serving Web pages between multiple, smaller servers. Various ways of doing this have been proposed, such as round-robin DNS, hierarchical redirection, and the use of load-balancing routers. In this paper, we propose a distributed packet rewriting system. In this system, not only is the task of serving Web pages split between the servers, but so is the task of routing packets. Incoming requests are initially distributed between servers using round-robin DNS; then the Web servers themselves route connections as necessary to balance the load more equally. We use an adaptive non-uniform hashing function in routing connections. The use of this function guarantees even load distribution, and allows for both new servers entering the system and server capacities changing due to load or outage, with no downtime.