An overview of data replication on the Internet <s> Server Selection <s> Abstract As distributed information services like the World Wide Web become increasingly popular on the Internet, problems of scale are clearly evident. A promising technique that addresses many of these problems is service (or document) replication. However, when a service is replicated, clients then need the additional ability to find a ``good'''' provider of that service. In this paper we report on techniques for finding good service providers without a priori knowledge of server location or network topology. We consider the use of two principal metrics for measuring distance in the Internet: hops, and round-trip latency. We show that these two metrics yield very different results in practice. Surprisingly, we show data indicating that the number of hops between two hosts in the Internet is {\em not\/} strongly correlated to round-trip latency. Thus, the distance in hops between two hosts is not necessarily a good predictor of the expected latency of a document transfer. Instead of using known or measured distances in hops, we show that the extra cost at runtime incurred by dynamic latency measurement is well justified based on the resulting improved performance. In addition we show that selection based on dynamic latency measurement performs much better in practice that any static selection scheme. Finally, the difference between the distribution of hops and latencies is fundamental enough to suggest differences in algorithms for server replication. We show that conclusions drawn about service replication based on the distribution of hops need to be revised when the distribution of latencies is considered instead. <s> BIB001 </s> An overview of data replication on the Internet <s> Server Selection <s> In this paper we consider the problem of choosing among a collection of replicated servers, focusing on the question of how to make choices that segregate client/server traffic according to network topology. We explore the cost and effectiveness of a variety of approaches, ranging from those requiring routing layer support (e.g., anycast) to those that build location databases using application-level probe tools like traceroute. We uncover a number of tradeoffs between effectiveness, network cost, ease of deployment, and portability across different types of networks. We performed our experiments using a simulation parameterized by a topology collected from 7 survey sites across the United States, exploring a global collection of Network Time Protocol servers. <s> BIB002 </s> An overview of data replication on the Internet <s> Server Selection <s> A distributed Web system, consisting of multiple servers for data retrieval and a Domain Name Server (DNS) for address resolution, can provide the scalability necessary to keep up with growing client demand at popular sites. However, balancing the requests among these atypical distributed servers opens interesting new challenges. Unlike traditional distributed systems in which a centralized scheduler has full control of the system, the DNS controls only a small fraction of the requests reaching the Web site. This makes it very difficult to avoid overloading situations among the multiple Web servers. We adapt traditional scheduling algorithms to the DNS, propose new policies, and examine their impact. Extensive simulation results show the advantage of using strategies that schedule requests on the basis of the origin of the clients and very limited state information, such as whether a server is overloaded or not. Conversely, algorithms that use detailed state information often exhibit the worst performance. <s> BIB003 </s> An overview of data replication on the Internet <s> Server Selection <s> The explosion of the web has led to a situation where a majority of the traffic on the Internet is web related. Today, practically all of the popular web sites arc served from single locations. This necessitates frequent long distance network transfers of data (potentially repeatedly) which results in a high response time for users, and is wasteful of the available network bandwidth. Moreover, it commonly creates a single point of failure between the web site and its Internet provider. This paper presents a new approach to web replication, where each of the replicas resides in a different part of the network, and the browser is automatically and transparently directed to the “best” server. Implementing this architecture for popular web sites will result in a better response-time and a higher availability of these sites. Equally important, this architecture will potentially cut down a significant fraction of the traffic on the Internet, freeing bandwidth for other uses. <s> BIB004 </s> An overview of data replication on the Internet <s> Server Selection <s> Replication of documents on geographically distributed servers can improve both performance and reliability of the Web service. Server selection algorithms allow Web clients to select one of the replicated servers which is "close" to them and thereby minimize the response time of the Web service. Using client proxy server traces, we compare the effectiveness of several "proximity" metrics including the number of hops between the client and server, the ping round trip time and the HTTP request latency. Based on this analysis, we design two new algorithms for selection of replicated servers and compare their performance against other existing algorithms. We show that the new server selection algorithms improve the performance of other existing algorithms on the average by 55%. In addition, the new algorithms improve the performance of the existing non-replicated Web servers on average by 69%. <s> BIB005 </s> An overview of data replication on the Internet <s> Server Selection <s> We examine the use of the anycasting communication paradigm to improve client performance when accessing replicated multimedia objects. Anycasting supports dynamic selection of a server amongst a group of servers that provide equivalent content. It the selection is done well, the client will experience improved performance. A key issue in anycasting is the method used to maintain performance information used in server selection. We explore using past performance or experience to predict future performance. We conduct our work in the context of a customized web prefetching application called WebSnatcher. We examine a variety of algorithms for selecting a server using past performance and find that the overall average and weighted average algorithms are closest to optimal performance. In addition to the WebSnatcher application, this work has implications for responsible network behavior by other applications that generate network traffic automatically. By using the techniques we present here, such applications can reduce network and server load, potentially improving performance for interactive applications. The results can also be used to reach conclusions about the performance that would be obtained if anycasting were used in an interactive application.© (1998) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only. <s> BIB006 </s> An overview of data replication on the Internet <s> Server Selection <s> One or more liquids may be applied to a running textile web in flat tubular or open width form by three different cooperative and integrated systems. A drying chamber is associated with the apparatus for recovering solvent which may be included in certain liquid chemicals. The chemical applicating apparatus includes spray nozzles spaced transversely adjacent the path of travel of the web for spraying chemicals on the moving web. Guiding means are provided for selectively positioning the web with respect to the nozzles for optimum spraying position. A padding tank is also provided for passing the web directly through a bath of the chemical and a metering system including an applicator roll and an adjustable blade in different configurations is provided for applying precisely controlled amounts of chemicals to the web. <s> BIB007 </s> An overview of data replication on the Internet <s> Server Selection <s> Server replication is an approach often used to improve the ability of a service to handle a large number of clients. One of the important factors in the efficient utilization of replicated servers is the ability to direct client requests to the best server, according to some optimality criteria. In this paper we target an environment in which servers are distributed across the Internet, and clients identify servers using our application-layer any-casting service. Our goal is to allocate servers to clients in a way that minimizes a client's response time. To that end, we develop an approach for estimating the performance that a client would experience when accessing particular servers. Such information is maintained in a resolver that clients can query to obtain the identity of the server with the best response time. Our performance collection technique combines server push with client probes to estimate the expected response time. A set of experiments is used to demonstrate the properties of our performance determination approach and to show its advantages when used within the application-layer anycasting architecture. <s> BIB008 </s> An overview of data replication on the Internet <s> Server Selection <s> There is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal content Web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggest an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast groups, in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We also presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area. <s> BIB009 </s> An overview of data replication on the Internet <s> Server Selection <s> Replication of information among multiple World Wide Web servers is necessary to support high request rates to popular Web sites. A clustered Web server organization is preferable to multiple independent mirrored servers because it maintains a single interface to the users and has the potential to be more scalable, fault-tolerant and better load-balanced. In this paper, we propose a Web cluster architecture in which the Domain Name System (DNS) server, which dispatches the user requests among the servers through the URL name to the IP address mapping mechanism, is integrated with a redirection request mechanism based on HTTP. This should alleviate the side-effect of caching the IP address mapping at intermediate name servers. We compare many alternative mechanisms, including synchronous vs. asynchronous activation and centralized vs. distributed decisions on redirection. Moreover, we analyze the reassignment of entire domains or individual client requests, different types of status information and different server selection policies for redirecting requests. Our results show that the combination of centralized and distributed dispatching policies allows the Web server cluster to handle high load skews in the WWW environment. <s> BIB010 </s> An overview of data replication on the Internet <s> Server Selection <s> Replication of information across a server cluster provides a promising way to support popular Web sites. However, a Web‐server cluster requires some mechanism for the scheduling of requests to the most available server. One common approach is to use the cluster Domain Name System (DNS) as a centralized dispatcher. The main problem is that WWW address caching mechanisms (although reducing network traffic) only let this DNS dispatcher control a very small fraction of the requests reaching the Web‐server cluster. The non‐uniformity of the load from different client domains, and the high variability of real Web workload introduce additional degrees of complexity to the load balancing issue. These characteristics make existing scheduling algorithms for traditional distributed systems not applicable to control the load of Web‐server clusters and motivate the research on entirely new DNS policies that require some system state information. We analyze various DNS dispatching policies under realistic situations where state information needs to be estimated with low computation and communication overhead so as to be applicable to a Web cluster architecture. In a model of realistic scenarios for the Web cluster, a large set of simulation experiments shows that, by incorporating the proposed state estimators into the dispatching policies, the effectiveness of the DNS scheduling algorithms can improve substantially, in particular if compared to the results of DNS algorithms not using adequate state information. <s> BIB011
Various methods for selecting among replicated servers are extensively discussed in the relevant literature, most of them attempting to provide better QoS by assigning a client to its "closest" server. The response time a user experiences depends on: i) server capabilities, ii) server load, iii) network path characteristics, e.g., propagation delay, iv) path load. The solutions proposed vary according to how many factors they consider. BIB004 and  provide an overview of some of the server selection alternatives proposed in the literature and discuss the expected benefits and drawbacks. In BIB001 the authors argue that hop distance is not a good metric. They examine the performance of a random algorithm, that selects servers uniformly, as well as one which selects the server with the minimum average response time. Experiments show that dynamic server selection in the form of the above algorithms outperforms static client-server allocation. Another study BIB005 examines the performance of different client-server distance metrics. The correlation between the number of hops and the response time, is found to be low (0.16), supporting the results of BIB001 . The use of ping utility as a metric is also deemed unsatisfactory (correlation of 0.51). The best metric is found to be the past request latency. Using past history as a metric, the authors propose a probabilistic and a refresh algorithm. The probabilistic selects a server with a probability inversely proportional to the latency exhibited in the past, thus not leading to starvation as a straightforward client allocation would. The refresh algorithm asynchronously updates latency information by sending periodically an HTTP HEAD request to the corresponding server, thus avoiding suboptimal clientserver allocations due to latency information being outdated. Both algorithms were marginally outperformed by a parallel strategy, where a client sends his request to all the available servers and selects the one who responds first. In BIB006 the authors experiment with an algorithm based on calculating a weighted average of past performance so as to place more importance on recent measurements. Their approach compares favorably to traditional schemes, such as round robin, but is dependent on careful parameter selection. The study in  also considers latency as the distance metric. It examines various methods for latency computation and compares different server selection algorithms, using their execution time as the primary performance criterion. The above techniques are useful primarily when redirection is client based. If this is not the case, distance estimation becomes more complicated and inaccurate. Let us consider server based redirection as an example. When a request arrives at a server it is possible to probe the client and measure the response time. The inter-server distances are also computable. Nevertheless, it is not always possible to determine with accuracy the closest server to the client due to the triangulation phenomenon. An early work in BIB002 describes how to derive client-server distance metrics and proposes techniques based on polling routing tables and network probing (i.e., placing measuring agents at key points in the Internet and calculate their distances). SONAR  and IDMaps BIB009 aim at building and maintaining an infrastructure on the Internet, capable of returning the distance between any pair of hosts. SONAR describes a DNS-like infrastructure to support client queries, while IDMaps tackles the problem of how to calculate and maintain the actual distance metrics. The method they propose is based on clustering of hosts and approximating distances using triangulation. The work in  is related to DNS based redirection. The authors propose extensions to routers and DNS servers in order to allow the later to communicate and take advantage of the reliable distance information kept in the routing tables BIB007 . A slightly different problem is addressed in BIB008 , i.e., how to maintain the metric information needed by the replicated servers. They consider three strategies: i) Server push. Upon the occurrence of significant metric changes a server notifies the other replica holders. It incurs minimum overhead, but is inaccurate since it does not measure path characteristics; ii) Client probing. Periodically probe agents issue queries to the servers and measure the response time; iii) A Hybrid server push/client probing approach, which was experimentally found to be the most promising. Server selection is also examined from the perspective of load balancing a cluster of web servers instead of minimizing end to end response time. The study in BIB003 provides a set of scheduling algorithms when redirection happens at the DNS level. It is observed that algorithms using asynchronous "server overloaded" warning messages, in combination with characteristics of client origin, perform significantly better compared to algorithms maintaining the accurate workload state of the servers. The same authors in BIB011 provide extensive simulation results and compare the most successful methods of BIB003 , with another alternative, namely Adaptive TTL. The new method, which is based on deriving optimal TTL values for DNS responses, was found to increase system's performance. Finally, BIB010 studies scheduling techniques that involve DNS -web server cooperation, with the redirection decisions occurring at the web servers using HTTP functionalities.