Abstract
Clusters of identical intermediate servers are often created to improve availability and robustness in many domains. The use of proxy servers for the World Wide Web (WWW) and of rendezvous points in multicast routing are two such situations. However, this approach can be inefficient if identical requests are received and processed by multiple servers. We present an analysis of this problem, and develop a method called the highest random weight (HRW) mapping that eliminates these difficulties. Given an object name and a set of servers, HRW maps a request to a server using the object name, rather than any a priori knowledge of server states. Since HRW always maps a given object name to the same server within a given cluster, it may be used locally at client sites to achieve consensus on object–server mappings. We present an analysis of HRW and validate it with simulation results showing that it gives faster service times than traditional request allocation schemes such as round-robin or least-loaded, and adapts well to changes in the set of servers. HRW is particularly applicable to domains in which there are a large number of requestable objects, there is a significant probability that a requested object will be requested again, and the CPU load due to any single object can be handled by a single server. HRW has now been adopted by the multicast routing protocols PIMv2 and CBTv2 as its mechanism for routers to identify rendezvous points/cores. Index Terms—Caching, client–server systems, computer networks, distributed agreement, multicast routing, proxies, World Wide Web.
I. INTRODUCTION
IN THE USUAL client–server model, clients access object data or services that are made available by servers. A single-server system is not robust, however, and often provides insufficient resources to handle a large number of requests. Thus, clusters of equivalent servers can be used to increase service availability and to lower the workload on individual servers. In this paper, we investigate how a client may map a request for a particular object to a server, so as to minimize response time. In particular, we will limit our scope to domains with the following characteristics. • All requests for the same class of objects are handled by a cluster of servers with equivalent functionality and capacity. • The set of servers in the cluster is known to clients prior to issuing requests, and all clients see the same Manuscript received November 26, 1996; revised June 20, 1997; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor D. Estrin. This work was supported in part by the National Science Foundation under Grant NCR- 9 417 032. The authors are with the Electrical Engineering and Computer Science Department, University of Michigan, Ann Arbor, MI 48109-2122 USA (email: thalerd[at]eecs.umich.edu; ravi[at]eecs.umich.edu). Publisher Item Identifier S 1063-6692(98)01075-9. set of servers. For example, this information may be statically configured, looked up at client startup time, or periodically distributed to clients.
• There is some notion of a “hit rate” at a server, so that a server responds more quickly to a duplicate request than to a first-time request. This is clearly true when the server functions as a cache. It is also true if clients need to locate the server which was assigned to do a particular task.
• The benefit of object replication across servers is negligible. That is, the CPU load due to any single object can be handled by a single server. The above characteristics cover a wide variety of domains. Some examples include: 1) Real-Time Producer–Consumer Systems: For example, in multicast routing protocols such as the core-based trees (CBT) [1] and protocol independent multicast (PIM) [2] protocols, receivers’ routers request data for a specific session by sending a join request toward the root of a distribution tree for that session, and sources send data to a session via the root of its tree. The root thus takes on the role of a server, with receivers and sources becoming clients. Sources and receivers must rendezvous at the root for effective data transfer. 2) Client-Side WWW Proxy Caches: In the World Wide Web (WWW), pages can be cached at proxy servers [3], [4]. All outbound client requests can then go through a local proxy server. If the proxy server has the page cached, the page is returned to the client without accessing the remote provider. Otherwise, the page is retrieved and cached for future use. Note that server-side proxy caches often do not fall within the relevant class of domains. When proxy caches are placed near servers to handle inbound requests, the number of requests for a single object may represent enough central processing unit (CPU) load to make object replication more effective. 3) Task Delegation: In task brokering systems, tasks may be delegated to various servers. Any clients which desire to interact with such a task must then contact the server running that task. For these domains, we will present an efficient algorithm which maps requests to servers such that requests for the same object are sent to the same server, while requests for different objects are split among multiple servers. We will refer to this concept as a “name-based” mapping. It is possible to view the case where all clients send requests for the same object to the same server as defining affinities between objects and servers in a cluster (Fig. 1). A number of studies (e.g., [5]–[7]) have examined the related notion of “cache-affinity” scheduling in the context of shared-memory multiprocessors, in which tasks are sent to processors which already have data cached. This achieves higher cache hit rates at the possible expense of load balancing.


Download full report
http://googleurl?sa=t&source=web&cd=1&ve....1.93.7624%26rep%3Drep1%26type%3Dpdf&ei=iiJTTpW3ENGyrAf9pKDfDg&usg=AFQjCNGBlnPFfIbOd5tVYBcCHZNUhNy0iw