Document publication service over such a large network as theInternet challenges us to harness available server and network resourcesto meet fast growing demand. We show that large scale dynamic cachingcan be employed to globally minimize server idle time, and hencemaximize the aggregate server throughput of the whole service. To beefficient, scalable and robust, a successful caching mechanism must havethree properties: (1) maximize the global throughput of the system; (2)find cache copies without recourse to a directory service, or to adiscovery protocol; and (3) be completely distributed in the sense ofoperating only on the basis of local information. We develop a precisedefinition, which we call tree load balance (TLB), of what it means fora mechanism to satisfy these three goals. We present an algorithm thatcomputes TLB offline, and a distributed protocol that induces a loaddistribution that converges quickly to a TLB one. Both algorithms placecache copies of immutable documents on the routing tree that connectsthe cached document's home server to its clients, thus enabling requeststo stumble on cache copies en route to the home server
展开▼
