Webwave: Large scale load balanced content distribution

The Internet's primary function has been to universally connect clients to servers, using an interconnection network (IN) of packet routers. Implicitly, the traditional IN architecture ties each logical server to one physical server, placed at one network location. As a result, when large fractions of the client population converge simultaneously on a small subset of servers, they create hot spots of demand for server resources. Another consequence of the IN model is that the physical distance between a server and its client is so large that packet propagation delay is prohibitively slow for most interactive applications, and the probability of network congestion is increased.; This dissertation pursue an alternative model of the Internet, that of a computing network (CN), that solves the IN's problems. A CN consists of a set of intermediate servers that can acquire some of the functionality of origin servers. The CN directs client requests to a nearby intermediate server that acts on behalf of the origin. Hot-spot load is diffused across shared intermediate servers. The network distance between clients and intermediate servers is much shorter than between clients and origin servers, thus reducing packet propagation delay and network congestion.; The main difficulties in designing a CN are: (a) each logical origin server is tied to a rapidly changing set of intermediate servers, complicating resource discovery, and (b) large scale replication of origin server functionality must be controlled. We solve these problems under the additional constraint of smoothly evolving the current IN architecture into a CN.; Our solution starts with a new architecture and formal model of a CN, in which intermediate servers are attached to packet routers to form a forest of trees, each rooted at an origin server. Clients represent leaf nodes. We present a novel distributed algorithm (WebWave) for large-scale replication control that provably satisfies a new algorithmic definition of global load-balance. A simulation study provides evidence for fast convergence, consistent with known properties of similar algorithms, and suggests that WebWave consumes reasonable amounts of storage. We conclude with a practical design for implementing our CN architecture and WebWave within the context of the current Internet.