Data distribution algorithms for load balanced fault-tolerant Web access

Describes the design and analysis of RobustWeb, a scalable and fault-tolerant World Wide Web server cluster that is based on HTTP redirection. The system consists of a set of N back-end document servers and one or more redirection servers which receive the HTTP requests and redirect them to the document servers. A load distribution algorithm is used for initial distribution of the documents on the servers. Given a specific degree of replication k, the distribution algorithm guarantees that at least k replicas of each document are present after document distribution is complete. The redirection servers redirect requests to one of the replicas with a pre-computed redirection probability. When a server fails, the redirection probabilities are recomputed using a novel algorithm based on network flow. Theis enables the load to be approximately balanced among the remaining servers, allowing for graceful degradation of the service in the event of failures. A preliminary prototype of RobustWeb has been implemented