|
Abstract : |
Abstract In many Internet applications, requests for a certain object are routed bottom-up over a tree where the root of the tree is the node containing the object. When an object becomes popular, the root node of the tree may become a hot-spot. Therefore many applications allow intermediate nodes to acquire the ability to serve the requests, for example by caching the object. We call such distinguished nodes primed. We propose and analyze different algorithms where nodes decide when to become primed; these algorithms balance the maximum load on a node and the number of primed nodes. Many applications require both fully distributed decisions and smooth convergence to a stable set of primed nodes. We first present optimal algorithms which require communication across the tree. We then consider the natural previously proposed threshold algorithm, where a node becomes primed when the incoming flow of requests exceeds a threshold. We show examples where threshold exhibits undesirable behavior during convergence. Finally, we propose another fully distributed algorithm, gap, which converges gracefully. 1 Introduction The Internet provides a platform for decentralized applications where content or services are requested, stored, and provided by very large number of loosely coupled hosts. In these applications, there is no centralized support. Requests are forwarded from peer to peer, and each peer can become a server for each item., |
