An overview of data replication on the Internet <s> O N <s> A model is developed for allocating information files required in common by several computers. The model considers storage cost, transmission cost, file lengths, and request rates, as well as updating rates of files, the maximum allowable expected access times to files at each computer, and the storage capacity of each computer. The criterion of optimality is minimal overall operating costs (storage and transmission). The model is formulated into a nonlinear integer zero-one programming problem, which may be reduced to a linear zero-one programming problem. A simple example is given to illustrate the model. <s> BIB001 </s> An overview of data replication on the Internet <s> O N <s> The problems of file allocation and capacity assignment in a fixed topology distributed computer network are examined. These two aspects of the design are tightly coupled by means of an average message delay constraint. The objective is to allocate copies of information files to network nodes and capacities to network links so that a minimum cost is achieved subject to network delay and file availability constraints. A model for solving the problem is formulated and the resulting optimization problem is shown to fall into a class of nonlinear integer programming problems. Deterministic techniques for solving this class of problems are computationally cumbersome, even for small size problems. A new heuristic algorithm is developed, which is based on a decomposition technique that greatly reduces the computational complexity of the problem. Numerical results for a variety of network configurations indicate that the heuristic algorithm, while not theoretically convergent, yields practicable low cost solutions with substantial savings in computer processing time and storage requirements. Moreover, it is shown that this algorithm is capable of solving realistic network problems whose solutions using deterministic techniques are computationally intractable. <s> BIB002 </s> An overview of data replication on the Internet <s> O N <s> The problem of allocating the data of a database to the sites of a communication network is investigated. This problem deviates from the well-known file allocation problem in several aspects. First, the objects to be allocated are not known a priori; second, these objects are accessed by schedules that contain transmissions between objects to produce the result. A model that makes it possible to compare the cost of allocations is presented; the cost can be computed for different cost functions and for processing schedules produced by arbitrary query processing algorithms. For minimizing the total transmission cost, a method is proposed to determine the fragments to be allocated from the relations in the conceptual schema and the queries and updates executed by the users. For the same cost function, the complexity of the data allocation problem is investigated. Methods for obtaining optimal and heuristic solutions under various ways of computing the cost of an allocation are presented and compared. Two different approaches to the allocation management problem are presented and their merits are discussed. <s> BIB003 </s> An overview of data replication on the Internet <s> O N <s> The resource allocation problem in distributed computing systems that have strict mutual consistency requirements is discussed. A model that incorporates the behavior of consistency control algorithms which ensure that mutual consistency of replicated data is preserved even when communication links of the computer network and/or computers on which the files reside fail is presented. The constrained resource allocation problem is formulated as a mixed nonlinear integer program. An efficient algorithm is proposed to solve this problem. The performance of the algorithm is evaluated in terms of its accuracy, efficiency and execution times, using a representative problem set. > <s> BIB004 </s> An overview of data replication on the Internet <s> O N <s> Examining multimedia program allocation in distributed multimedia-on-demand systems lets us consider how best to provide programs at will from geographically scattered servers. Each user is associated with a local server but can transparently access any program located at any server. The authors consider user demand for various programs, storage limitations of the multimedia servers, and costs of storing and transporting the programs. <s> BIB005 </s> An overview of data replication on the Internet <s> O N <s> Describes the design and analysis of RobustWeb, a scalable and fault-tolerant World Wide Web server cluster that is based on HTTP redirection. The system consists of a set of N back-end document servers and one or more redirection servers which receive the HTTP requests and redirect them to the document servers. A load distribution algorithm is used for initial distribution of the documents on the servers. Given a specific degree of replication k, the distribution algorithm guarantees that at least k replicas of each document are present after document distribution is complete. The redirection servers redirect requests to one of the replicas with a pre-computed redirection probability. When a server fails, the redirection probabilities are recomputed using a novel algorithm based on network flow. Theis enables the load to be approximately balanced among the remaining servers, allowing for graceful degradation of the service in the event of failures. A preliminary prototype of RobustWeb has been implemented. <s> BIB006 </s> An overview of data replication on the Internet <s> O N <s> This article addresses the performance of distributed database systems. Specifically, we present an algorithm for dynamic replication of an object in distributed systems. The algorithm is adaptive in the sence that it changes the replication scheme of the object i.e., the set of processors at which the object inreplicated) as changes occur in the read-write patern of the object (i.e., the number of reads and writes issued by each processor). The algorithm continuously moves the replication scheme towards an optimal one. We show that the algorithm can be combined with the concurrency control and recovery mechanisms of ta distributed database management system. The performance of the algorithm is analyzed theoretically and experimentally. On the way we provide a lower bound on the performance of any dynamic replication algorith. <s> BIB007 </s> An overview of data replication on the Internet <s> O N <s> Web caching or web proxy has been considered as the prime vehicle of coping with the ever-increasing demand for information retrieval over the Internet, the WWW being a typical example. Existing work on web proxy has primarily focused on content based caching; relatively less attention has been given to the development of proper placement strategies for the potential web proxies in the Internet. In this paper, we argue that the placement of web proxies is critical to the performance and further investigates the optimal placement policy of web proxies for a target web server in the Internet. The objective is to optimize a given performance measure for the target web server subject to system resources and traffic pattern. Specifically, we are interested in finding the optimal placement of multiple web proxies (M) among potential sites (N) under a given traffic pattern. We show this can be modeled a dynamic programming problem. We further obtain the optimal solution for the tree topology using O(N/sup 3/M/sup 2/) time. <s> BIB008 </s> An overview of data replication on the Internet <s> O N <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> O N <s> The paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm for distributing requests among currently available replicas. Our approach attempts to place replicas in the vicinity of a majority of requests, while ensuring at the same time that no servers are overloaded. The request distribution algorithm uses the same simple mechanism to take into account both server proximity and load, without actually knowing the latter. The replica placement algorithm executes autonomously on each node, without the knowledge of other object replicas in the system. The proposed algorithms rely on the information available in databases maintained by Internet routers. A simulation study using synthetic workloads and the network backbone of UUNET, one of the largest Internet service providers, shows that the proposed protocol is effective in eliminating hot spots and achieves a significant reduction in backbone traffic and server response time at the expense of creating only a small number of extra replicas. <s> BIB010 </s> An overview of data replication on the Internet <s> O N <s> The IDMaps project aims to provide a distance map of the Internet from which relative distances between hosts on the Internet can be gauged. Many distributed systems and applications can benefit from such a distance map service, for example, a common method to improve user-perceived performance of the Internet is to place data and server mirrors closer to clients. When a client tries to access a mirrored server, which mirror should it access? With IDMaps, the closest mirror can be determined based on distance estimates between the client and the mirrors. In this paper we investigate both graph theoretic methods and ad hoc heuristics for instrumenting the Internet to obtain distance maps. We evaluate the efficacy of the resulting distance maps by comparing the determinations of the closest replica using known topologies against those obtained using the distance maps. <s> BIB011 </s> An overview of data replication on the Internet <s> O N <s> Creating replicas of frequently accessed objects across a read-intensive network can result in large bandwidth savings which, in turn, can lead to reduction in user response time. On the contrary, data replication in the presence of writes incurs extra cost due to multiple updates. The set of sites at which an object is replicated constitutes its replication scheme. Finding an optimal replication scheme that minimizes the amount of network traffic given read and write frequencies for various objects, is NP-complete in general. We propose two heuristics to deal with this problem for static read and write patterns. The first is a simple and fast greedy heuristic that yields good solutions when the system is predominantly read-oriented. The second is a genetic algorithm that through an efficient exploration of the solution space provides better solutions for cases where the greedy heuristic does not perform well. We also propose an extended genetic algorithm that rapidly adapts to the dynamically changing characteristics such as the frequency of reads and writes for particular objects. <s> BIB012 </s> An overview of data replication on the Internet <s> O N <s> There has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. CDNs deploy a set of servers distributed throughout the Internet and replicate provider content across these servers for better performance and availability than centralized provider servers. Existing work on CDNs has primarily focused on techniques for efficiently redirecting user requests to appropriate CDN servers to reduce request latency and balance load. However, little attention has been given to the development of placement strategies for Web server replicas to further improve CDN performance. We explore the problem of Web server replica placement in detail. We develop several placement algorithms that use workload information, such as client latency and request rates, to make informed placement decisions. We then evaluate the placement algorithms using both synthetic and real network topologies, as well as Web server traces, and show that the placement of Web replicas is crucial to CDN performance. We also address a number of practical issues when using these algorithms, such as their sensitivity to imperfect knowledge about client workload and network topology, the stability of the input data, and methods for obtaining the input. <s> BIB013 </s> An overview of data replication on the Internet <s> O N <s> Internet service providers and infrastructural companies often employ mirrors of popular content to decrease client download time and server load. Due to the immense scale of the Internet and decentralized administration of the networks, companies have a limited number of sites (relative to the size of the Internet) where they can place mirrors. Mirrors of popular content are usually replicated on every site to maximize reachability to clients. We study the performance improvements as the number of mirrors increases under different placement algorithms subject to the constraint that mirrors can be placed only at certain locations. Although there are extensive theoretical studies on center placement and, analytical and empirical studies on Web cache placement, we are not aware of any published literature on mirror placement especially in the case of constrained mirror placement. Our results show that increasing the number of mirror sites under the constraint is effective in reducing client download time and reducing server load only for a surprisingly small range of values regardless of the mirror placement algorithm. <s> BIB014 </s> An overview of data replication on the Internet <s> O N <s> A video-on-demand server must satisfy a large customer base and a diverse archive of movies under changing movie popularity and daily load peaks. These requirements must be satisfied under the constraints imposed by storage device costs, capacities, I/O bandwidths, and geographic locations. In this paper we describe a partitioning of video data (movies) onto a video-on-demand storage hierarchy to achieve efficient storage and I/O bandwidth use. Our approach uses a probabilistic model of movie popularity in data distribution and replication to balance user requests with available disk I/O bandwidth. The results can be applied in the design of a general, distributed video-on-demand system. <s> BIB015
The work in BIB013 tackles the problem of replica placement in order to reduce network bandwidth consumption. They provide a greedy heuristic that outperforms the dynamic programming method of BIB008 in the non-tree network case. The study in BIB011 investigates the optimal placement of Internet distance measuring instrumentations under the IDMaps framework BIB009 . Both graph theoretic and heuristic algorithms are examined with results varying depending on the network topology. The performance metric considered is the expected accuracy of distance estimations, produced under the different instrumentation assignments. In a more recent work BIB014 , the same authors compared a 2-approximation algorithm for the k-Median, with a greedy approach, a random algorithm and a heuristic which favoured nodes of higher outdegree for replica placement. Bin packing  : An informal description of the bin packing problem is as follows: Given N objects, of various sizes, partition them to the minimum number of disjoint sets such as the cumulative storage at each set does not exceed a threshold S. Bin packing formulation is commonly used to model load balancing problems. The problem of distributing documents in a cluster of web servers in order to balance their load is discussed in BIB006 . The paper proposes a binning algorithm for the initial distribution and network flow  formulations in the case where either access patterns change or there is a server failure. In order to achieve graceful performance degradation dummy-replicas are also distributed (i.e., replicas that satisfy requests only in case the primary replica fails). File Allocation  : The basic form of the file allocation problem (FAP) is the following: Given a network of M sites with different storage capacities and N files exhibiting various read frequencies from each site, allocate the objects to the sites in order to optimize a performance parameter (e.g., total network traffic), with respect to the storage capacity available at each node  . The study in BIB001 expands the formulation to account for multiple object copies and updates, while  proves that FAP is NP-complete. In BIB002 the authors provide an iterative approach that achieves good solution quality when solving the FAP for infinite site capacities. A complete although old survey on the FAP can be found in  . FAP originated from the need to allocate programs and data to multiprocessor systems  and in its general formulation can be viewed as a case of the uncapacitated facility location (UFL) problem  which is studied in the business management sector. Subsequently FAP-like formulations were used to describe similar problems arising in distributed databases BIB003 ,  , multimedia databases  and video server systems BIB005 , BIB015 . Most of the papers included in  account for static centralized allocation (i.e., access patterns are assumed to be known and remain unchangeable). The Internet environment poses additional challenges with its dynamic nature. The work in BIB012 uses genetic algorithms to solve both the static version of the problem and an adaptive version whereby changes on object popularities make the current replica distribution obsolete and a fast way to determine a new allocation scheme is needed. Taking into account reliability and availability constraints is the focus of BIB004 where the authors combine allocation together with fault tolerance issues in a single formulation. The studies in  , BIB010 and BIB007 are concerned with the on-line version of FAP, i.e., they propose algorithms which given an input stream of requests, alter replica distribution so as to minimize the total answering cost. The problem can be viewed as an extension to the well studied paging problem (see  for a survey). In BIB007 the authors proposed a protocol called ADR that changes the replication scheme of an object so as to minimize the network traffic due to reads and updates. To do so, they impose a logical tree structure for the network. Authors in BIB010 propose a general protocol that creates, migrates and deletes replicas so as to improve the client-replica proximity without overloading any of the servers. The model does not account for updates. The work reported in  is of significant theoretical value providing an optimally competitive centralized algorithm as well as a decentralized one to solve the on-line FAP. .