Dynamic replication strategies in data grid systems: a survey
---
paper_title: Data Management in an International Data Grid Project

paper_content:

In this paper we report on preliminary work and architectural design carried out in the "Data Management" work package in the International Data Grid project. Our aim within a time scale of three years is to provide Grid middleware services supporting the I/O-intensive world-wide distributed next generation experiments in High-Energy Physics, Earth Observation and Bioinformatics. The goal is to specify, develop, integrate and test tools and middleware infrastructure to coherently manage and share Petabyte-range information volumes in high-throughput production-quality Grid environments. The middleware will allow secure access to massive amounts of data in a universal name-space, to move and replicate data at high speed from one geographical site to another, and to manage synchronisation of remote copies. We put much attention on clearly specifying and categorising existing work on the Grid, especially in data management in Grid related projects. Challenging use cases are described and how they map to architectural decisions concerning data access, replication, meta data management, security and query optimisation.
---
paper_title: A classification of file placement and replication methods on grids

paper_content:

This paper presents a classification of file placement and replication methods on grids. The study is motivated by file transfer issues encountered in the Virtual Imaging Platform deployed on the European Grid Infrastructure. Approaches proposed in the last 6 years are classified using taxonomies of replication process, replication optimization, file models, resource models and replication validation. Most existing approaches implement file replication as a middleware service, using dynamic strategies. Production approaches are slightly different than works evaluated in simulation or in controlled conditions which (i) mostly assumes simplistic file models (undistinguished read-only files), (ii) rely on elaborated access patterns, (iii) assume clairvoyance of the infrastructure parameters and (iv) study file availability less than other metrics but insist on cost.
---
paper_title: QoS-aware replica placement for content distribution

paper_content:

The rapid growth of new information services and business-oriented applications entails the consideration of quality of service (QoS) in content distribution. This paper investigates the QoS-aware replica placement problems for responsiveness QoS requirements. We consider two classes of service models: replica-aware services and replica-blind services. In replica-aware services, the servers are aware of the locations of replicas and can therefore optimize request routing to improve responsiveness. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for fast computation of good solutions are proposed and experimentally evaluated. In replica-blind services, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.
---
paper_title: Grid Datafarm Architecture for Petascale Data Intensive Computing

paper_content:

The Grid Datafarm (Gfarm) architecture is designed for global petascale data-intensive computing. It provides a global parallel filesystem with online petascale storage, scalable I/O bandwidth, and scalable parallel processing, and it can exploit local I/O in a grid of clusters with tens of thousands of nodes. Gfarm parallel I/O APIs and commands provide a single filesystem image and manipulate filesystem metadata consistently. Fault tolerance and load balancing are automatically managed by file duplication or recomputation using a command history log. Preliminary performance evaluation has shown scalable disk I/O and network bandwidth on 64 nodes of the Presto III Athlon cluster. The Gfarm parallel I/O write and read operations has achieved data transfer rates of 1.74 GB/s and 1.97 GB/s, respectively, using 64 cluster nodes. The Gfarm parallel file copy reached 443 MB/s with 23 parallel streams on the Myrinet 2000. The Gfarm architecture is expected to enable petascale data-intensive Grid computing with an I/O bandwidth scales to the TB/s range and scalable computational power.
---
paper_title: The complexity of static data replication in data grids

paper_content:

Data replication is a well-known technique used in distributed computing to improve access to data and/or system fault-tolerance. Recently, studies of its applications to grid computing have also been initiated. In this article we describe data replication on data grids as a static optimization problem. We show that this problem is NP-hard and non-approximable. We discuss two approaches to solving it, i.e. integer programming and simplifications.
---
paper_title: PUMA2—grid-based high-throughput analysis of genomes and metabolic pathways

paper_content:

The PUMA2 system (available at http://compbio.mcs. 10 anl.gov/puma2) is an interactive, integrated bioinformatics environment for high-throughput genetic sequence analysis and metabolic reconstructions from sequence data. PUMA2 provides a framework for comparative and evolutionary analysis of geno15 mic data and metabolic networks in the context of taxonomic and phenotypic information. Grid infrastructure is used to perform computationally intensive tasks. PUMA2 currently contains precomputed analysis of 213 prokaryotic, 22 eukaryotic, 650 mito20 chondrial and 1493 viral genomes and automated metabolic reconstructions for .200 organisms. Genomic data is annotated with information integrated from .20 sequence, structural and metabolic databases and ontologies. PUMA2 supports both 25 automated and interactive expert-driven annotation of genomes, using a variety of publicly available bioinformatics tools. It also contains a suite of unique PUMA2 tools for automated assignment of gene function, evolutionary analysis of protein families 30 and comparative analysis of metabolic pathways. PUMA2 allows users to submit batch sequence data for automated functional analysis and construction of metabolic models. The results of these analyses are made available to the users in the PUMA2 envir35 onment for further interactive sequence analysis and annotation.
---
paper_title: Static and adaptive distributed data replication using genetic algorithms

paper_content:

Fast dissemination and access of information in large distributed systems, such as the Internet, has become a norm of our daily life. However, undesired long delays experienced by end-users, especially during the peak hours, continue to be a common problem. Replicating some of the objects at multiple sites is one possible solution in decreasing network traffic. The decision of what to replicate where, requires solving a constraint optimization problem which is NP-complete in general. Such problems are known to stretch the capacity of a Genetic Algorithm (GA) to its limits. Nevertheless, we propose a GA to solve the problem when the read/write demands remain static and experimentally prove the superior solution quality obtained compared to an intuitive greedy method. Unfortunately, the static GA approach involves high running time and may not be useful when read/write demands continuously change, as is the case with breaking news. To tackle such case we propose a hybrid GA that takes as input the current replica distribution and computes a new one using knowledge about the network attributes and the changes occurred. Keeping in view more pragmatic scenarios in today's distributed information environments, we evaluate these algorithms with respect to the storage capacity constraint of each site as well as variations in the popularity of objects, and also examine the trade-off between running time and solution quality.
---
paper_title: A study on performance of dynamic file replication algorithms for real-time file access in Data Grids

paper_content:

Real-time Grid applications are emerging in many disciplines of science and engineering. In order to run these applications while meeting the associated real-time constraints with them, the Grid infrastructure should be designed to respect these constraints and allocate its computing, networking, storage, and the other resources accordingly. Furthermore, these applications involve a large number of data intensive jobs and require to access terabytes of data in real-time. On the other hand, a variety of dynamic file replication algorithms were proposed for the best-effort Data Grid environments in an attempt to decrease job completion times and save network bandwidth. Until now, there is no study in the literature which tries to elaborate on the real-time performance of these dynamic file replication algorithms. Based on this motivation, in this study, the performance of eight dynamic replication algorithms are evaluated under various Data Grid settings. For this evaluation, a process oriented and discrete-event driven simulator called DGridSim is developed. A detailed set of simulation studies are conducted using DGridSim and the results obtained are presented to reveal the real-time performance of the dynamic file replication algorithms.
---
paper_title: Giggle: A Framework for Constructing Scalable Replica Location Services

paper_content:

In wide area computing systems, it is often desirable to create remote read-only copies (replicas) of files. Replication can be used to reduce access latency, improve data locality, and/or increase robustness, scalability and performance for distributed applications. We define a replica location service (RLS) as a system that maintains and provides access to information about the physical locations of copies. An RLS typically functions as one component of a data grid architecture. This paper makes the following contributions. First, we characterize RLS requirements. Next, we describe a parameterized architectural framework, which we name Giggle (for GIGa-scale Global Location Engine), within which a wide range of RLSs can be defined. We define several concrete instantiations of this framework with different performance characteristics. Finally, we present initial performance results for an RLS prototype, demonstrating that RLS systems can be constructed that meet performance goals.
---
paper_title: Dynamic replica placement and selection strategies in data grids- A comprehensive survey

paper_content:

Data replication techniques are used in data grid to reduce makespan, storage consumption, access latency and network bandwidth. Data replication enhances data availability and thereby increases the system reliability. There are two steps involved in data replication, namely, replica placement and replica selection. Replica placement involves identifying the best possible node to duplicate data based on network latency and user request. Replica selection involves selecting the best replica location to access the data for job execution in the data grid. Various replica placement and selection algorithms are available in the literature. These algorithms measure and analyze different parameters such as bandwidth consumption, access cost, scalability, execution time, storage consumption and makespan. In this paper, various replica placement and selection strategies along with their merits and demerits are discussed. This paper also analyses the performance of various strategies with respect to the parameters mentioned above. In particular, this paper focuses on the dynamic replica placement and selection strategies in the data grid environment.
---
paper_title: Identifying Dynamic Replication Strategies for a High-Performance Data Grid

paper_content:

Dynamic replication can be used to reduce bandwidth consumption and access latency in high performance "data grids" where users require remote access to large files. Different replication strategies can be defined depending on when, where, and how replicas are created and destroyed. We describe a simulation framework that we have developed to enable comparative studies of alternative dynamic replication strategies. We present preliminary results obtained with this simulator, in which we evaluate the performance of five different replication strategies for three different kinds of access patterns. The data in ths scenario is read-only and so there are no consistency issues involved. The simulation results show that significant savings in latency and bandwidth can be obtained if the access patterns contain a small degree of geographical locality.
---
paper_title: Grid computing: the European Data Grid Project

paper_content:

The goal of this project is the development of a novel environment to support globally distributed scientific exploration involving multi-PetaByte datasets. The project will devise and develop middleware solutions and testbeds capable of scaling to handle many PetaBytes of distributed data, tens of thousands of resources (processors, disks, etc.), and thousands of simultaneous users. The scale of the problem and the distribution of the resources and user community preclude straightforward replication of the data at different sites, while the aim of providing a general purpose application environment precludes distributing the data using static policies. We will construct this environment by combining and extending newly emerging "Grid" technologies to manage large distributed datasets in addition to computational elements. A consequence of this project will be the emergence of fundamental new modes of scientific exploration, as access to fundamental scientific data is no longer constrained to the producer of that data. While the project focuses on scientific applications such as High Energy Physics, Earth Sciences and Bio-Informatics, issues of sharing data are germane to many applications and thus the project has a potential impact on future industrial and commercial activities.
---
paper_title: Data replication strategies with performance objective in data grid systems: a survey

paper_content:

Replicating for performance constitutes an important issue in large-scale data management systems. In this context, a significant number of replication strategies have been proposed for data grid systems. Some works classified these strategies into static vs. dynamic or centralised vs. decentralised or client vs. server initiated strategies. Very few works deal with a replication strategy classification based on the role of these strategies when building a replica management system. In this paper, we propose a new replication strategy classification based on objective functions of these strategies. Also, each replication strategy is designed according to the data grid topology for which it was proposed. We point out the impact of the topology on replication performance although most of these strategies have been proposed for a hierarchical grid topology. We also study the impact of some factors on performance of these strategies, e.g. access pattern, bandwidth consumption and storage capacity.
---
paper_title: A dynamic data replication strategy using access-weights in data grids

paper_content:

Data grids deal with a huge amount of data regularly. It is a fundamental challenge to ensure efficient accesses to such widely distributed data sets. Creating replicas to a suitable site by data replication strategy can increase the system performance. It shortens the data access time and reduces bandwidth consumption. In this paper, a dynamic data replication mechanism called Latest Access Largest Weight (LALW) is proposed. LALW selects a popular file for replication and calculates a suitable number of copies and grid sites for replication. By associating a different weight to each historical data access record, the importance of each record is differentiated. A more recent data access record has a larger weight. It indicates that the record is more pertinent to the current situation of data access. A Grid simulator, OptorSim, is used to evaluate the performance of this dynamic replication strategy. The simulation results show that LALW successfully increases the effective network usage. It means that the LALW replication strategy can find out a popular file and replicates it to a suitable site without increasing the network burden too much.
---
paper_title: QoS-aware replica placement for data intensive applications

paper_content:

Abstract In recent years, with the rapid development of data intensive applications, data replication has become an enabling technology for the data grid to improve data availability, and reduce file transfer time and bandwidth consumption. The placement of replicas has been proven to be the most difficult problem that must be solved to realize the process of data replication. This paper addresses the quality of service (QoS) aware replica placement problem in data grid, and proposes a dynamic programming based replica placement algorithm that not only has a QoS requirement guarantee, but also can minimize the overall replication cost, including storage cost and communication cost. By simulation, experiments show that the replica placement algorithm outperforms an existing popular replica placement technique in data grid.
---
paper_title: A survey of dynamic replication strategies for improving data availability in data grids

paper_content:

Data grid is a distributed collection of storage and computational resources that are not bounded within a geophysical location. It is a fast growing area of research and providing efficient data access and maximum data availability is a challenging task. To achieve this task, data is replicated to different sites. A number of data replication techniques have been presented for data grids. All replication techniques address some attributes like fault tolerance, scalability, improved bandwidth consumption, performance, storage consumption, data access time etc. In this paper, different issues involved in data replication are identified and different replication techniques are studied to find out which attributes are addressed in a given technique and which are ignored. A tabular representation of all those parameters is presented to facilitate the future comparison of dynamic replication techniques. The paper also includes some discussion about future work in this direction by identifying some open research problems.
---
paper_title: The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets

paper_content:

In an increasing number of scientific disciplines, large data collections are emerging as important community resources. In this paper, we introduce design principles for a data management architecture called the data grid. We describe two basic services that we believe are fundamental to the design of a data grid, namely, storage systems and metadata management. Next, we explain how these services can be used to develop higher-level services for replica management and replica selection. We conclude by describing our initial implementation of data grid functionality.
---
paper_title: GriPhyN and LIGO, building a virtual data Grid for gravitational wave scientists

paper_content:

Many Physics experiments today generate large volumes of data. That data is then processed in a variety of ways in order to achieve the understanding of fundamental physical phenomena. The goal of the NSF-funded GriPhyN project (Grid Physics Network) is to enable scientists to seamlessly access data whether it is raw experimental data or a data product which is a result of further processing. GriPhyN provides a new degree of transparency in how data-handling and processing capabilities are integrated to deliver data products to end-users or applications, so that requests for such products are easily mapped into computation and/or data access at multiple locations. GriPhyN refers to the set of all data products available to the user as virtual data. Among the physics applications participating in the project is the Laser Interferometer Gravitational-wave Observatory (LIGO), which is being built to observe the gravitational waves predicted by general relativity. We describe our initial design and prototype of a virtual data Grid for LIGO.
---
paper_title: Wide Area Data Replication for Scientific Collaborations

paper_content:

Scientific applications require sophisticated data management capabilities. We present the design and implementation of a data replication service (DRS), one of a planned set of higher-level data management services for Grids. The capabilities of the DRS are based on the publication capability of the lightweight data replicator (LDR) system developed for the LIGO Scientific Collaboration. We describe LIGO publication requirements and LDR functionality. We also describe the design and implementation of the DRS in the Globus Toolkit Version 4.0 environment and present performance results.
---
paper_title: The complexity of static data replication in data grids

paper_content:

Data replication is a well-known technique used in distributed computing to improve access to data and/or system fault-tolerance. Recently, studies of its applications to grid computing have also been initiated. In this article we describe data replication on data grids as a static optimization problem. We show that this problem is NP-hard and non-approximable. We discuss two approaches to solving it, i.e. integer programming and simplifications.
---
paper_title: Static and adaptive distributed data replication using genetic algorithms

paper_content:

Fast dissemination and access of information in large distributed systems, such as the Internet, has become a norm of our daily life. However, undesired long delays experienced by end-users, especially during the peak hours, continue to be a common problem. Replicating some of the objects at multiple sites is one possible solution in decreasing network traffic. The decision of what to replicate where, requires solving a constraint optimization problem which is NP-complete in general. Such problems are known to stretch the capacity of a Genetic Algorithm (GA) to its limits. Nevertheless, we propose a GA to solve the problem when the read/write demands remain static and experimentally prove the superior solution quality obtained compared to an intuitive greedy method. Unfortunately, the static GA approach involves high running time and may not be useful when read/write demands continuously change, as is the case with breaking news. To tackle such case we propose a hybrid GA that takes as input the current replica distribution and computes a new one using knowledge about the network attributes and the changes occurred. Keeping in view more pragmatic scenarios in today's distributed information environments, we evaluate these algorithms with respect to the storage capacity constraint of each site as well as variations in the popularity of objects, and also examine the trade-off between running time and solution quality.
---
paper_title: Giggle: A Framework for Constructing Scalable Replica Location Services

paper_content:

In wide area computing systems, it is often desirable to create remote read-only copies (replicas) of files. Replication can be used to reduce access latency, improve data locality, and/or increase robustness, scalability and performance for distributed applications. We define a replica location service (RLS) as a system that maintains and provides access to information about the physical locations of copies. An RLS typically functions as one component of a data grid architecture. This paper makes the following contributions. First, we characterize RLS requirements. Next, we describe a parameterized architectural framework, which we name Giggle (for GIGa-scale Global Location Engine), within which a wide range of RLSs can be defined. We define several concrete instantiations of this framework with different performance characteristics. Finally, we present initial performance results for an RLS prototype, demonstrating that RLS systems can be constructed that meet performance goals.
---
paper_title: A dynamic data replication strategy using access-weights in data grids

paper_content:

Data grids deal with a huge amount of data regularly. It is a fundamental challenge to ensure efficient accesses to such widely distributed data sets. Creating replicas to a suitable site by data replication strategy can increase the system performance. It shortens the data access time and reduces bandwidth consumption. In this paper, a dynamic data replication mechanism called Latest Access Largest Weight (LALW) is proposed. LALW selects a popular file for replication and calculates a suitable number of copies and grid sites for replication. By associating a different weight to each historical data access record, the importance of each record is differentiated. A more recent data access record has a larger weight. It indicates that the record is more pertinent to the current situation of data access. A Grid simulator, OptorSim, is used to evaluate the performance of this dynamic replication strategy. The simulation results show that LALW successfully increases the effective network usage. It means that the LALW replication strategy can find out a popular file and replicates it to a suitable site without increasing the network burden too much.
---
paper_title: QoS-aware replica placement for data intensive applications

paper_content:

Abstract In recent years, with the rapid development of data intensive applications, data replication has become an enabling technology for the data grid to improve data availability, and reduce file transfer time and bandwidth consumption. The placement of replicas has been proven to be the most difficult problem that must be solved to realize the process of data replication. This paper addresses the quality of service (QoS) aware replica placement problem in data grid, and proposes a dynamic programming based replica placement algorithm that not only has a QoS requirement guarantee, but also can minimize the overall replication cost, including storage cost and communication cost. By simulation, experiments show that the replica placement algorithm outperforms an existing popular replica placement technique in data grid.
---
paper_title: A classification of file placement and replication methods on grids

paper_content:

This paper presents a classification of file placement and replication methods on grids. The study is motivated by file transfer issues encountered in the Virtual Imaging Platform deployed on the European Grid Infrastructure. Approaches proposed in the last 6 years are classified using taxonomies of replication process, replication optimization, file models, resource models and replication validation. Most existing approaches implement file replication as a middleware service, using dynamic strategies. Production approaches are slightly different than works evaluated in simulation or in controlled conditions which (i) mostly assumes simplistic file models (undistinguished read-only files), (ii) rely on elaborated access patterns, (iii) assume clairvoyance of the infrastructure parameters and (iv) study file availability less than other metrics but insist on cost.
---
paper_title: A study on performance of dynamic file replication algorithms for real-time file access in Data Grids

paper_content:

Real-time Grid applications are emerging in many disciplines of science and engineering. In order to run these applications while meeting the associated real-time constraints with them, the Grid infrastructure should be designed to respect these constraints and allocate its computing, networking, storage, and the other resources accordingly. Furthermore, these applications involve a large number of data intensive jobs and require to access terabytes of data in real-time. On the other hand, a variety of dynamic file replication algorithms were proposed for the best-effort Data Grid environments in an attempt to decrease job completion times and save network bandwidth. Until now, there is no study in the literature which tries to elaborate on the real-time performance of these dynamic file replication algorithms. Based on this motivation, in this study, the performance of eight dynamic replication algorithms are evaluated under various Data Grid settings. For this evaluation, a process oriented and discrete-event driven simulator called DGridSim is developed. A detailed set of simulation studies are conducted using DGridSim and the results obtained are presented to reveal the real-time performance of the dynamic file replication algorithms.
---
paper_title: Improving Data Availability through Dynamic Model-Driven Replication in Large Peer-to-Peer Communities

paper_content:

Efficient data sharing in global peer-to-peer systems is complicated by erratic node failure, unreliable network connectivity and limited bandwidth. Replicating data on multiple nodes can improve availability and response time. Yet determining when and where to replicate data in order to meet performance goals in large-scale systems with many users and files, dynamic network characteristics, and changing user behavior is difficult. We propose an approach in which peers create replicas automatically in a decentralized fashion, as required to meet availability goals. The aim of our framework is to maintain a threshold level of availability at all times. We identify a set of factors that hinder data availability and propose a model that decides when more replication is necessary. We evaluate the accuracy and performance of the proposed model using simulations. Our preliminary results show that the model is effective in predicting the required number of replicas in the system.
---
paper_title: A survey of dynamic replication strategies for improving data availability in data grids

paper_content:

Data grid is a distributed collection of storage and computational resources that are not bounded within a geophysical location. It is a fast growing area of research and providing efficient data access and maximum data availability is a challenging task. To achieve this task, data is replicated to different sites. A number of data replication techniques have been presented for data grids. All replication techniques address some attributes like fault tolerance, scalability, improved bandwidth consumption, performance, storage consumption, data access time etc. In this paper, different issues involved in data replication are identified and different replication techniques are studied to find out which attributes are addressed in a given technique and which are ignored. A tabular representation of all those parameters is presented to facilitate the future comparison of dynamic replication techniques. The paper also includes some discussion about future work in this direction by identifying some open research problems.
---
paper_title: A study on performance of dynamic file replication algorithms for real-time file access in Data Grids

paper_content:

Real-time Grid applications are emerging in many disciplines of science and engineering. In order to run these applications while meeting the associated real-time constraints with them, the Grid infrastructure should be designed to respect these constraints and allocate its computing, networking, storage, and the other resources accordingly. Furthermore, these applications involve a large number of data intensive jobs and require to access terabytes of data in real-time. On the other hand, a variety of dynamic file replication algorithms were proposed for the best-effort Data Grid environments in an attempt to decrease job completion times and save network bandwidth. Until now, there is no study in the literature which tries to elaborate on the real-time performance of these dynamic file replication algorithms. Based on this motivation, in this study, the performance of eight dynamic replication algorithms are evaluated under various Data Grid settings. For this evaluation, a process oriented and discrete-event driven simulator called DGridSim is developed. A detailed set of simulation studies are conducted using DGridSim and the results obtained are presented to reveal the real-time performance of the dynamic file replication algorithms.
---
paper_title: Wide Area Data Replication for Scientific Collaborations

paper_content:

Scientific applications require sophisticated data management capabilities. We present the design and implementation of a data replication service (DRS), one of a planned set of higher-level data management services for Grids. The capabilities of the DRS are based on the publication capability of the lightweight data replicator (LDR) system developed for the LIGO Scientific Collaboration. We describe LIGO publication requirements and LDR functionality. We also describe the design and implementation of the DRS in the Globus Toolkit Version 4.0 environment and present performance results.
---
paper_title: Dynamic QoS-aware data replication in grid environments based on data importance

paper_content:

Data replication comprises a standard fault tolerance approach for systems-especially large-scale ones-that store and provide data over wide geographical and administrative areas. The major topics that the task of data replication covers include the replica creation, placement, relocation and retirement, replica consistency and replica access. In a business context a number of constraints exists which are set by the infrastructure, network and application capabilities in combination with the Quality of Service (QoS) requirements that hinder the effectiveness of data replication schemes. In this paper, we examine how this combination affects the replication lifecycle in Data Grids and we introduce a set of interoperable novel file replication algorithms that take into account the infrastructural constraints as well as the 'importance' of the data. The latter is approximated through a multi-parametric factor that encapsulates a set of data-specific parameters, such as popularity and content significance.
---
paper_title: Evaluation of an economy-based file replication strategy for a data grid

paper_content:

Optimising the use of Grid resources is critical for users to effectively exploit a Data Grid. Data replication is considered a major technique for reducing data access cost to Grid jobs. This paper evaluates a novel replication strategy, based on an economic model, that optimises both the selection of replicas for running jobs and the dynamic creation of replicas in Grid sites. In our model, optimisation agents are located on Grid sites and use an auction protocol for selecting the optimal replica of a data file and a prediction function to make informed decisions about local data replication. We evaluate our replication strategy with OptorSim, a Data Grid simulator developed by the authors. The experiments show that our proposed strategy results in a notable improvement over traditional replication strategies in a Grid environment.
---
paper_title: Enhanced Dynamic Hierarchical Replication and Weighted Scheduling Strategy in Data Grid

paper_content:

The Data Grid provides massive aggregated computing resources and distributed storage space to deal with data-intensive applications. Due to the limitation of available resources in the grid as well as production of large volumes of data, efficient use of the Grid resources becomes an important challenge. Data replication is a key optimization technique for reducing access latency and managing large data by storing data in a wise manner. Effective scheduling in the Grid can reduce the amount of data transferred among nodes by submitting a job to a node where most of the requested data files are available. In this paper two strategies are proposed, first a novel job scheduling strategy called Weighted Scheduling Strategy (WSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in a queue, the location of the required data for the job and the computing capacity of the sites Second, a dynamic data replication strategy, called Enhanced Dynamic Hierarchical Replication (EDHR) that improves file access time. This strategy is an enhanced version of the Dynamic Hierarchical Replication strategy. It uses an economic model for file deletion when there is not enough space for the replica. The economic model is based on the future value of a data file. Best replica placement plays an important role for obtaining maximum benefit from replication as well as reducing storage cost and mean job execution time. So, it is considered in this paper. The proposed strategies are implemented by OptorSim, the European Data Grid simulator. Experiment results show that the proposed strategies achieve better performance by minimizing the data access time and avoiding unnecessary replication.
---
paper_title: Identifying Dynamic Replication Strategies for a High-Performance Data Grid

paper_content:

Dynamic replication can be used to reduce bandwidth consumption and access latency in high performance "data grids" where users require remote access to large files. Different replication strategies can be defined depending on when, where, and how replicas are created and destroyed. We describe a simulation framework that we have developed to enable comparative studies of alternative dynamic replication strategies. We present preliminary results obtained with this simulator, in which we evaluate the performance of five different replication strategies for three different kinds of access patterns. The data in ths scenario is read-only and so there are no consistency issues involved. The simulation results show that significant savings in latency and bandwidth can be obtained if the access patterns contain a small degree of geographical locality.
---
paper_title: Data replication strategies with performance objective in data grid systems: a survey

paper_content:

Replicating for performance constitutes an important issue in large-scale data management systems. In this context, a significant number of replication strategies have been proposed for data grid systems. Some works classified these strategies into static vs. dynamic or centralised vs. decentralised or client vs. server initiated strategies. Very few works deal with a replication strategy classification based on the role of these strategies when building a replica management system. In this paper, we propose a new replication strategy classification based on objective functions of these strategies. Also, each replication strategy is designed according to the data grid topology for which it was proposed. We point out the impact of the topology on replication performance although most of these strategies have been proposed for a hierarchical grid topology. We also study the impact of some factors on performance of these strategies, e.g. access pattern, bandwidth consumption and storage capacity.
---
paper_title: Adaptive popularity-driven replica placement in hierarchical data grids

paper_content:

Data grids support access to widely distributed storage for large numbers of users accessing potentially many large files. Efficient access is hindered by the high latency of the Internet. To improve access time, replication at nearby sites may be used. Replication also provides high availability, decreased bandwidth use, enhanced fault tolerance, and improved scalability. Resource availability, network latency, and user requests in a grid environment may vary with time. Any replica placement strategy must be able to adapt to such dynamic behavior. In this paper, we describe a new dynamic replica placement algorithm, Popularity Based Replica Placement (PBRP), for hierarchical data grids which is guided by file "popularity". Our goal is to place replicas close to clients to reduce data access time while still using network and storage resources efficiently. The effectiveness of PBRP depends on the selection of a threshold value related to file popularity. We also present Adaptive-PBRP (APBRP) that determines this threshold dynamically based on data request arrival rates. We evaluate both algorithms using simulation. Results for a range of data access patterns show that our algorithms can shorten job execution time significantly and reduce bandwidth consumption compared to other dynamic replication methods.
---
paper_title: Replica placement in data grid: a multi-objective approach

paper_content:

One of the challenges in data replication is to select the candidate sites to place replicas. We use the p-median and p-center models to address the replica placement problem. In our problem, the p-median model finds the locations of p candidate sites to place a replica to optimize the total (or average) response time. The p-center model hosts replicas to p candidate sites by minimizing the maximum response time among sites. A Grid environment is highly dynamic so placing a replica by considering one objective, i.e., optimize average response time or optimize maximum response time, may not be always a good choice. We propose a multi-objective model that considers the objectives of p-median and p-center simultaneously to select the candidate sites that will host replicas. Simulation results demonstrate that the multi-objective model outperforms single objective models in dynamic environments such as Data Grids.
---
paper_title: FIRE: A File Reunion Based Data Replication Strategy for Data Grids

paper_content:

Data grids provide large-scale geographically distributed data resources for data intensive applications such as high energy physics and bioinformatics. Optimizing the use of data resources to maximize the performance is critical for data grids. In this paper, we propose a novel dynamic data replication strategy called FIRE (file reunion), which is motivated by the observations that a group of jobs in a site tend to demand a common set of files distributed in a data grid. The basic idea of FIRE is to reunite the file set through data replication so that it resides with the job group on the same site. Extensive experiments using a well-known data grid simulator OptorSim and synthetic benchmarks demonstrate that compared with two existing schemes, LRU (Least Recently Used) and LFU (Least Frequently Used), FIRE performs obviously better in most scenarios.
---
paper_title: PHFS: A dynamic replication method, to decrease access latency in the multi-tier data grid

paper_content:

Abstract Data replication is a method to improve the performance of data access in distributed systems. Dynamic replication is a kind of replication that adapts replication configuration with the change of users’ behavior during the time to ensure the benefits of replication. In this paper, we propose a new dynamic replication method in a multi-tier data grid called predictive hierarchical fast spread (PHFS) which is an extended version of fast spread (a dynamic replication method in the data grid). Considering spatial locality, PHFS tries to predict future needs and pre-replicates them in hierarchal manner to increase locality in accesses and consequently improves performance. In this paper, we compare PHFS and CFS (common fast spread) with an example from the perspective of access latency. The results show that PHFS causes lower latency and better performance in comparison with CFS.
---
paper_title: Identifying Dynamic Replication Strategies for a High-Performance Data Grid

paper_content:

Dynamic replication can be used to reduce bandwidth consumption and access latency in high performance "data grids" where users require remote access to large files. Different replication strategies can be defined depending on when, where, and how replicas are created and destroyed. We describe a simulation framework that we have developed to enable comparative studies of alternative dynamic replication strategies. We present preliminary results obtained with this simulator, in which we evaluate the performance of five different replication strategies for three different kinds of access patterns. The data in ths scenario is read-only and so there are no consistency issues involved. The simulation results show that significant savings in latency and bandwidth can be obtained if the access patterns contain a small degree of geographical locality.
---
paper_title: Adaptive popularity-driven replica placement in hierarchical data grids

paper_content:

Data grids support access to widely distributed storage for large numbers of users accessing potentially many large files. Efficient access is hindered by the high latency of the Internet. To improve access time, replication at nearby sites may be used. Replication also provides high availability, decreased bandwidth use, enhanced fault tolerance, and improved scalability. Resource availability, network latency, and user requests in a grid environment may vary with time. Any replica placement strategy must be able to adapt to such dynamic behavior. In this paper, we describe a new dynamic replica placement algorithm, Popularity Based Replica Placement (PBRP), for hierarchical data grids which is guided by file "popularity". Our goal is to place replicas close to clients to reduce data access time while still using network and storage resources efficiently. The effectiveness of PBRP depends on the selection of a threshold value related to file popularity. We also present Adaptive-PBRP (APBRP) that determines this threshold dynamically based on data request arrival rates. We evaluate both algorithms using simulation. Results for a range of data access patterns show that our algorithms can shorten job execution time significantly and reduce bandwidth consumption compared to other dynamic replication methods.
---
paper_title: Evaluating content management techniques for Web proxy caches

paper_content:

The continued growth of the World-Wide Web and the emergence of new end-user technologies such as cable modems necessitate the use of proxy caches to reduce latency, network traffic and Web server loads. Current Web proxy caches utilize simple replacement policies to determine which files to retain in the cache. We utilize a trace of client requests to a busy Web proxy in an ISP environment to evaluate the performance of several existing replacement policies and of two new, parameterless replacement policies that we introduce in this paper. Finally, we introduce Virtual Caches, an approach for improving the performance of the cache for multiple metrics simultaneously.
---
paper_title: Enhanced Dynamic Hierarchical Replication and Weighted Scheduling Strategy in Data Grid

paper_content:

The Data Grid provides massive aggregated computing resources and distributed storage space to deal with data-intensive applications. Due to the limitation of available resources in the grid as well as production of large volumes of data, efficient use of the Grid resources becomes an important challenge. Data replication is a key optimization technique for reducing access latency and managing large data by storing data in a wise manner. Effective scheduling in the Grid can reduce the amount of data transferred among nodes by submitting a job to a node where most of the requested data files are available. In this paper two strategies are proposed, first a novel job scheduling strategy called Weighted Scheduling Strategy (WSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in a queue, the location of the required data for the job and the computing capacity of the sites Second, a dynamic data replication strategy, called Enhanced Dynamic Hierarchical Replication (EDHR) that improves file access time. This strategy is an enhanced version of the Dynamic Hierarchical Replication strategy. It uses an economic model for file deletion when there is not enough space for the replica. The economic model is based on the future value of a data file. Best replica placement plays an important role for obtaining maximum benefit from replication as well as reducing storage cost and mean job execution time. So, it is considered in this paper. The proposed strategies are implemented by OptorSim, the European Data Grid simulator. Experiment results show that the proposed strategies achieve better performance by minimizing the data access time and avoiding unnecessary replication.
---
paper_title: Combination of data replication and scheduling algorithm for improving data availability in Data Grids

paper_content:

Data Grid is a geographically distributed environment that deals with large-scale data-intensive applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Data replication is another key optimization technique for reducing access latency and managing large data by storing data in a wisely manner. In this paper two algorithms are proposed, first a novel job scheduling algorithm called Combined Scheduling Strategy (CSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in queue, the location of required data for the job and the computing capacity of sites. Second a dynamic data replication strategy, called the Modified Dynamic Hierarchical Replication Algorithm (MDHRA) that improves file access time. This strategy is an enhanced version of Dynamic Hierarchical Replication (DHR) strategy. Data replication should be used wisely because the storage capacity of each Grid site is limited. Thus, it is important to design an effective strategy for the replication replacement. MDHRA replaces replicas based on the last time the replica was requested, number of access, and size of replica. It selects the best replica location from among the many replicas based on response time that can be determined by considering the data transfer time, the storage access latency, the replica requests that waiting in the storage queue and the distance between nodes. The simulation results demonstrate the proposed replication and scheduling strategies give better performance compared to the other algorithms.
---
paper_title: A dynamic replica management strategy in data grid

paper_content:

Data Grid provides scalable infrastructure for storage resource and data files management, which supports several large scale applications. Due to limitation of available resources in grid, efficient use of the grid resources becomes an important challenge. Replication is a technique used in data grid to improve fault tolerance and to reduce the bandwidth consumption. This paper proposes a Dynamic Hierarchical Replication (DHR) algorithm that places replicas in appropriate sites i.e. best site that has the highest number of access for that particular replica. It also minimizes access latency by selecting the best replica when various sites hold replicas. The proposed replica selection strategy selects the best replica location for the users' running jobs by considering the replica requests that waiting in the storage and data transfer time. The simulated results with OptorSim, i.e. European Data Grid simulator show that DHR strategy gives better performance compared to the other algorithms and prevents unnecessary creation of replica which leads to efficient storage usage.
---
paper_title: Dynamic replication in a data grid using a Modified BHR Region Based Algorithm

paper_content:

Grid computing is emerging as a key part of the infrastructure for a wide range of disciplines in science and engineering, including astronomy, high energy physics, molecular biology and earth sciences. These applications handle large data sets that need to be transferred and replicated among different grid sites. A data grid deals with data intensive applications in scientific and enterprise computing. Data grid technology is developed to permit data sharing across many organizations in geographically disperse locations. Replication of data to different sites will help researchers around the world analyse and initiate future experiments. The general idea of replication is to store copies of data in different locations so that data can be easily recovered if a copy at one location is lost or unavailable. In a large-scale data grid, replication provides a suitable solution for managing data files, which enhances data reliability and availability. In this paper, a Modified BHR algorithm is proposed to overcome the limitations of the standard BHR algorithm. The algorithm is simulated using a data grid simulator, OptorSim, developed by European Data Grid projects. The performance of the proposed algorithm is improved by minimizing the data access time and avoiding unnecessary replication.
---
paper_title: A Hierarchical Scheduling and Replication Strategy

paper_content:

Summary In data grids huge amount of data are generated and processed by users around the world. Objective of dynamic replica strategies is reducing file access time by reducing network traffic, which leads to reducing job runtime. In this paper a replication algorithm for a 3-level hierarchical structure and a scheduling algorithm are proposed. The simulation results with optorsim show better performance (over 13%) comparing to current algorithms.
---
paper_title: A Dynamic Optimal Replication Strategy in Data Grid Environment

paper_content:

The data grid technology, which uses the scale of the Internet to provide storage capability for the mass data, has become one of the hot research topics. The high latency of the network is the bottleneck in accessing the files in data grid systems. The replication strategy can shorten the time of fetching the files by creating many replicas stored in appropriate locations. Due to the limited storage capacity of each node, it is important to have an efficient replication strategy to make sure of the overall performance. In order to solve the problem, we propose a dynamic optimal replication strategy (DORS) in this paper. First, we empirically infer a threshold from some former work to decide whether one file is needed to be copied to other nodes. Then, a measure is devised to get the importance of each file, which relies on the inner and external features of the file. Finally, the algorithm can decide which replica to replace based on the importance value. Results from the simulation show the better performance of our algorithm than other former work.
---
paper_title: Managing Data Replication and Placement Based on Availability

paper_content:

The replication of data across multiple sites of data grid is an effective solution to achieve good performance in terms of load balancing, response time, and improving data availability. To get the maximum gain that can make the data replication, their placement strategy in the system is critical. This paper proposes a replication strategy based on availability. It proposes also a placement and replacement strategies of replicas that ensures the desired availability with the minimum replicas despite the presence of nodes failures and without overloading the system. The results of our experimentations confirm that the proposed approach reaches its objectives.
---
paper_title: PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids

paper_content:

In recent years, grid technology has had such a fast growth that it has been used in many scientific experiments and research centers. A large number of storage elements and computational resources are combined to generate a grid which gives us shared access to extra computing power. In particular, data grid deals with data intensive applications and provides intensive resources across widely distributed communities. Data replication is an efficient way for distributing replicas among the data grids, making it possible to access similar data in different locations of the data grid. Replication reduces data access time and improves the performance of the system. In this paper, we propose a new dynamic data replication algorithm named PDDRA that optimizes the traditional algorithms. Our proposed algorithm is based on an assumption: members in a VO (Virtual Organization) have similar interests in files. Based on this assumption and also file access history, PDDRA predicts future needs of grid sites and pre-fetches a sequence of files to the requester grid site, so the next time that this site needs a file, it will be locally available. This will considerably reduce access latency, response time and bandwidth consumption. PDDRA consists of three phases: storing file access patterns, requesting a file and performing replication and pre-fetching and replacement. The algorithm was tested using a grid simulator, OptorSim developed by European Data Grid projects. The simulation results show that our proposed algorithm has better performance in comparison with other algorithms in terms of job execution time, effective network usage, total number of replications, hit ratio and percentage of storage filled.
---
paper_title: PFRF: An adaptive data replication algorithm based on star-topology data grids

paper_content:

Recently, data replication algorithms have been widely employed in data grids to replicate frequently accessed data to appropriate sites. The purposes are shortening file transmission distance and delivering files from nearby sites to local sites so as to improve data access performance and reduce bandwidth consumption. Some of the algorithms were designed based on unlimited storage. However, they might not be practical in real-world data grids since currently no system has infinite storage. Others were implemented on limited storage environments, but none of them considers data access patterns which reflect the changes of users' interests, and these are important parameters affecting file retrieval efficiency and bandwidth consumption. In this paper, we propose an adaptive data replication algorithm, called the Popular File Replicate First algorithm (PFRF for short), which is developed on a star-topology data grid with limited storage space based on aggregated information on previous file accesses. The PFRF periodically calculates file access popularity to track the variation of users' access behaviors, and then replicates popular files to appropriate sites to adapt to the variation. We employ several types of file access behaviors, including Zipf-like, geometric, and uniform distributions, to evaluate PFRF. The simulation results show that PFRF can effectively improve average job turnaround time, bandwidth consumption for data delivery, and data availability as compared with those of the tested algorithms.
---
paper_title: Branch replication scheme: A new model for data replication in large scale data grids

paper_content:

Data replication is a practical and effective method to achieve efficient and fault-tolerant data access in grids. Traditionally, data replication schemes maintain an entire replica in each site where a file is replicated, providing a read-only model. These solutions require huge storage resources to store the whole set of replicas and do not allow efficient data modification to avoid the consistency problem. In this paper we propose a new replication method, called the Branch Replication Scheme (BRS), that provides three main advantages over traditional approaches: optimizing storage usage, by creating subreplicas; increasing data access performance, by applying parallel I/O techniques; and providing the possibility to modify the replicas, by maintaining consistency among updates in an efficient way. An analytical model of the replication scheme, naming system, and replica updating scheme are formally described in the paper. Using this model, operations such as reading, writing, or updating a replica are analyzed. Simulation results demonstrate the feasibility of BRS, as they show that the new replication algorithm increases data access performance, compared with popular replication schemes such as hierarchical and server-directed replication, which are commonly used in current data grids.
---
paper_title: A dynamic data replication strategy using access-weights in data grids

paper_content:

Data grids deal with a huge amount of data regularly. It is a fundamental challenge to ensure efficient accesses to such widely distributed data sets. Creating replicas to a suitable site by data replication strategy can increase the system performance. It shortens the data access time and reduces bandwidth consumption. In this paper, a dynamic data replication mechanism called Latest Access Largest Weight (LALW) is proposed. LALW selects a popular file for replication and calculates a suitable number of copies and grid sites for replication. By associating a different weight to each historical data access record, the importance of each record is differentiated. A more recent data access record has a larger weight. It indicates that the record is more pertinent to the current situation of data access. A Grid simulator, OptorSim, is used to evaluate the performance of this dynamic replication strategy. The simulation results show that LALW successfully increases the effective network usage. It means that the LALW replication strategy can find out a popular file and replicates it to a suitable site without increasing the network burden too much.
---
paper_title: A priori replica placement strategy in data grid

paper_content:

The use of grid computing is becoming increasingly important in the areas requiring large quantity of data and calculation. To provide better access time and fault tolerance in such systems, the replication is one of the main issues for this purpose. The effectiveness of a replication model depends on several factors, including the replicas placement strategy. In this paper, we propose an a priori replicas placement strategy optimizing distances between the data hosted on the grid.
---
paper_title: Evaluation of an economy-based file replication strategy for a data grid

paper_content:

Optimising the use of Grid resources is critical for users to effectively exploit a Data Grid. Data replication is considered a major technique for reducing data access cost to Grid jobs. This paper evaluates a novel replication strategy, based on an economic model, that optimises both the selection of replicas for running jobs and the dynamic creation of replicas in Grid sites. In our model, optimisation agents are located on Grid sites and use an auction protocol for selecting the optimal replica of a data file and a prediction function to make informed decisions about local data replication. We evaluate our replication strategy with OptorSim, a Data Grid simulator developed by the authors. The experiments show that our proposed strategy results in a notable improvement over traditional replication strategies in a Grid environment.
---
paper_title: Data Replication in P2P Collaborative Systems

paper_content:

Data replication techniques have been extensively used in distributed systems to achieve, among others, due to system nodes failures: (a) high data availability, (b) system's reliability and (c) scalability. Due to the various characteristics of distributed systems as well as system's and application's requirements, a variety of data replication techniques have been proposed in the distributed computing field. One important distributed computing paradigm is that of P2P systems, which distinguish for their large scale and unreliable nature. The study and application of replication techniques becomes a must in such systems. While it is well understood and easy to achieve replication of immutable information (typically files) in P2P systems, it becomes more challenging to implement data replication techniques of dynamic data under highly dynamic nature of large P2P systems. Indeed, replicating documents that could change over time requires addressing the consistency issues. In this paper we study some data replication techniques for P2P collaborative systems. We identify several contexts and use cases where data replication can greatly support collaboration. We then consider as a case study replication techniques for dynamic documents in the context of a peer-group based P2P system of super-peer architecture. P2P collaborative systems arise in many groupware applications, such as collaborative work in online teams, having requirements for high availability and system reliability (e.g. in disaster management scenarios). We propose a replication system for documents structured as XML files to address the dynamics of the documents at peers and use the super-peer to ensure a satisfactory level of document consistency among peers.
---
paper_title: A new decentralized periodic replication strategy for dynamic data grids

paper_content:

Data grids provide scalable infrastructure for storage resource and ::: data files management, which support data-intensive applications that need to access to huge amount of data stored at distributed ::: locations around the world. The size of these data can reach the scale of terabytes or even petabytes in many applications. These ::: applications require reaching several main goals, namely efficient accessing, storing, transferring and analyzing a large amount of data in geographically distributed locations. In this situation, replication is a general and simple technique used in data grids to achieve these goals. Indeed, it has as main purposes improving data access efficiency, providing high availability, decreasing bandwidth consumption, improving fault tolerance and enhancing scalability. In this paper, we propose a new classification of replication strategies through two complementary criteria as well as a survey of the induced categories of strategies. In addition, we introduce a new decentralized periodic replication strategy for dynamic data grids assuming limited storage for replicas, called \textsc{DPRSKP}, which stands for Decentralized Periodic Replication Strategy based on Knapsack Problem. This strategy takes into consideration the changing availability of sites. \textsc{DPRSKP} is based on two polynomial-time complexity algorithms. The first one starts by selecting the best candidate files for replication while the second places them in the best locations. The replication problem in \textsc{DPRSKP} is formulated according to the Knapsack problem. In addition, DPRSKP extends the well known LRU and LFU strategies. The simulation experiments ::: were carried out using OptorSim and a dynamic period rather than a static one. The obtained results show that \textsc{DPRSKP} can effectively improve response time, bandwidth consumption, remote file accesses number and local file accesses number as compared with other replication strategies.
---
paper_title: Improving Data Availability through Dynamic Model-Driven Replication in Large Peer-to-Peer Communities

paper_content:

Efficient data sharing in global peer-to-peer systems is complicated by erratic node failure, unreliable network connectivity and limited bandwidth. Replicating data on multiple nodes can improve availability and response time. Yet determining when and where to replicate data in order to meet performance goals in large-scale systems with many users and files, dynamic network characteristics, and changing user behavior is difficult. We propose an approach in which peers create replicas automatically in a decentralized fashion, as required to meet availability goals. The aim of our framework is to maintain a threshold level of availability at all times. We identify a set of factors that hinder data availability and propose a model that decides when more replication is necessary. We evaluate the accuracy and performance of the proposed model using simulations. Our preliminary results show that the model is effective in predicting the required number of replicas in the system.
---
paper_title: Decentralized replication strategies for P2P based Scientific Data Grid

paper_content:

Scientific Data Grid provides geographically distributed resources for large-scale data-intensive applications that generate large scientific data sets and it mostly deals with large computational problems. Research in the area of grid has given various ideas and solutions to address these requirements. However, since the number of participants (scientists and institutes) that involve in this kind of environment is increasing tremendously, scalability, availability and reliability have been the core problem for such system. Peer-to-peer (P2P) is one of the architecture that promising scale and dynamism environment. In this paper, we present a P2P model for Scientific Data Grid that utilizes the P2P services to address those problems. For the purpose of this study, we have developed and used our own data grid simulation written using PARSEC. In this paper, we illustrate our P2P Scientific Data Grid model, our data grid simulation and the design of proposed data replication strategies. We then analyze the performance of data discovery service with and without the existence of replication strategies relative to their success rates, response time, average number of hop and bandwidth consumption. The results from simulation study that show how the proposed replication strategies promote high data availability in the proposed Scientific Data Grid model and how these strategies improve the discovery process are presented.
---
paper_title: Replica Placement in Multi-tier Data Grid

paper_content:

Replication is used in distributed and pervasive computing systems to enhance availability by placing needed data close to the users so that user perceived response time is minimized. In multi-tier Data Grid environment, replicas are usually placed in either top-down or bottom-up way. We believe that availability of data can be greatly enhanced by using both methods in a coherent way. Our proposed scheme, Two-way Replication, identifies and places the popular data to the requesting sites in a bottom-up fashion. Using top-down way, it places the less popular data a tier below from the Data Grid root. In this system, requests for data can be serviced from the siblings as well as the parent sites of the requesting clients. Experiment results reveal that Two-way Replication fulfills the availability needs of users with less number of replicas and more economic storage utilization as compared to Fast Spread technique.
---
paper_title: Data replication strategies in grid environments

paper_content:

Data grids provide geographically distributed resources for large-scale data-intensive applications that generate large data sets. However, ensuring efficient and fast access to such huge and widely distributed data is hindered by the high latencies of the Internet. To address these problems we introduce a set of replication management services and protocols that offer high data availability, low bandwidth consumption, increased fault tolerance, and improved scalability of the overall system. Replication decisions are made based on a cost model that evaluates data access costs and performance gains of creating each replica. The estimation of costs and gains is based on factors such as run-time accumulated read/write statistics, response time, bandwidth, and replica size. To address scalability, replicas are organized in a combination of hierarchical and flat topologies that represent propagation graphs that minimize inter-replica communication costs. To evaluate our model we use the network simulator NS to study the impact of replication. Our results prove that replication improves the performance of data access on the data grid, and that the gain increases with the size of data used.
---
paper_title: An on-line replication strategy to increase availability in Data Grids

paper_content:

Data is typically replicated in a Data Grid to improve the job response time and data availability. Strategies for data replication in a Data Grid have previously been proposed, but they typically assume unlimited storage for replicas. In this paper, we address the system-wide data availability problem assuming limited replica storage. We describe two new metrics to evaluate the reliability of the system, and propose an on-line optimizer algorithm that can Minimize the Data Missing Rate (MinDmr) in order to maximize the data availability. Based on MinDmr, we develop four optimizers associated with four different file access prediction functions. Simulation results utilizing the OptorSim show our MinDmr strategies achieve better performance overall than other strategies in terms of the goal of data availability using the two new metrics.
---
paper_title: Dynamic QoS-aware data replication in grid environments based on data importance

paper_content:

Data replication comprises a standard fault tolerance approach for systems-especially large-scale ones-that store and provide data over wide geographical and administrative areas. The major topics that the task of data replication covers include the replica creation, placement, relocation and retirement, replica consistency and replica access. In a business context a number of constraints exists which are set by the infrastructure, network and application capabilities in combination with the Quality of Service (QoS) requirements that hinder the effectiveness of data replication schemes. In this paper, we examine how this combination affects the replication lifecycle in Data Grids and we introduce a set of interoperable novel file replication algorithms that take into account the infrastructural constraints as well as the 'importance' of the data. The latter is approximated through a multi-parametric factor that encapsulates a set of data-specific parameters, such as popularity and content significance.
---
paper_title: Enhanced Fast Spread Replication strategy for Data Grid

paper_content:

Data replication is used in Data Grid to enhance data availability and fault tolerance. However, replication should be used wisely because the storage size of each node reside on the Data Grid is limited. Thus, the node must accommodate only the important replicas. In this paper, a dynamic replication strategy that takes into account the number and frequency of requests, the size of the replica, and the last time the replica was requested is proposed. This strategy is an enhanced version of Fast Spread replication strategy. The simulation results show that the new proposed strategy attained better performance than Fast Spread with Least Recently Used (LRU) and Fast Spread with Least Frequently Used (LFU) in terms of total response time and total bandwidth consumption.
---
paper_title: Method for replica creation in data grids based on complex networks

paper_content:

Abstract In order to reduce makespan and storage consumption in data grids, a node selection model for replica creation is proposed. The model is based on the degree distribution of complex networks. We define two candidate replica nodes: a degree-based candidate pool and a frequency-based candidate pool, through which a degree-based candidate pool is defined in consideration of onsidering the access frequency; a candidate pool-based frequency is also defined. The data replica is copied to the node with the minimum local cost in the two pools. Further, this paper presents and proves a replica creation theorem. A dynamic multi-replicas creation algorithm (DMRC) is also provided. Simulation results show that the proposed method may simultaneously reduce makespan and data used in space storage consumption.
---
paper_title: Replica placement in data grid: a multi-objective approach

paper_content:

One of the challenges in data replication is to select the candidate sites to place replicas. We use the p-median and p-center models to address the replica placement problem. In our problem, the p-median model finds the locations of p candidate sites to place a replica to optimize the total (or average) response time. The p-center model hosts replicas to p candidate sites by minimizing the maximum response time among sites. A Grid environment is highly dynamic so placing a replica by considering one objective, i.e., optimize average response time or optimize maximum response time, may not be always a good choice. We propose a multi-objective model that considers the objectives of p-median and p-center simultaneously to select the candidate sites that will host replicas. Simulation results demonstrate that the multi-objective model outperforms single objective models in dynamic environments such as Data Grids.
---
paper_title: Zipf ’ s law and the Internet

paper_content:

Zipf's law governs many features of the Internet. Observations of Zipf distributions, while interesting in and of themselves, have strong implications for the design and function of the Internet. The connectivity of Internet routers influences the robustness of the network while the distribution in the number of email contacts affects the spread of email viruses. Even web caching strategies are formulated to account for a Zipf distribution in the number of requests for webpages.
---
paper_title: Simulation of Dynamic Grid Replication Strategies in OptorSim

paper_content:

Computational Grids normally deal with large computationally intensive problems on small data sets. In contrast, Data Grids mostly deal with large computational problems that in turn require evaluating and mining large amounts of data. Replication is regarded as one of the major optimisation techniques for providing fast data access.Within this paper, several replication algorithms are studied. This is achieved using the Grid simulator: OptorSim. OptorSim provides a modular framework within which optimisation strategies can be studied under different Grid configurations. The goal is to explore the stability and transient behaviour of selected optimisation techniques.
---
paper_title: Zipf ’ s law and the Internet

paper_content:

Zipf's law governs many features of the Internet. Observations of Zipf distributions, while interesting in and of themselves, have strong implications for the design and function of the Internet. The connectivity of Internet routers influences the robustness of the network while the distribution in the number of email contacts affects the spread of email viruses. Even web caching strategies are formulated to account for a Zipf distribution in the number of requests for webpages.
---
paper_title: A study on performance of dynamic file replication algorithms for real-time file access in Data Grids

paper_content:

Real-time Grid applications are emerging in many disciplines of science and engineering. In order to run these applications while meeting the associated real-time constraints with them, the Grid infrastructure should be designed to respect these constraints and allocate its computing, networking, storage, and the other resources accordingly. Furthermore, these applications involve a large number of data intensive jobs and require to access terabytes of data in real-time. On the other hand, a variety of dynamic file replication algorithms were proposed for the best-effort Data Grid environments in an attempt to decrease job completion times and save network bandwidth. Until now, there is no study in the literature which tries to elaborate on the real-time performance of these dynamic file replication algorithms. Based on this motivation, in this study, the performance of eight dynamic replication algorithms are evaluated under various Data Grid settings. For this evaluation, a process oriented and discrete-event driven simulator called DGridSim is developed. A detailed set of simulation studies are conducted using DGridSim and the results obtained are presented to reveal the real-time performance of the dynamic file replication algorithms.
---
paper_title: Identifying Dynamic Replication Strategies for a High-Performance Data Grid

paper_content:

Dynamic replication can be used to reduce bandwidth consumption and access latency in high performance "data grids" where users require remote access to large files. Different replication strategies can be defined depending on when, where, and how replicas are created and destroyed. We describe a simulation framework that we have developed to enable comparative studies of alternative dynamic replication strategies. We present preliminary results obtained with this simulator, in which we evaluate the performance of five different replication strategies for three different kinds of access patterns. The data in ths scenario is read-only and so there are no consistency issues involved. The simulation results show that significant savings in latency and bandwidth can be obtained if the access patterns contain a small degree of geographical locality.
---
paper_title: PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids

paper_content:

In recent years, grid technology has had such a fast growth that it has been used in many scientific experiments and research centers. A large number of storage elements and computational resources are combined to generate a grid which gives us shared access to extra computing power. In particular, data grid deals with data intensive applications and provides intensive resources across widely distributed communities. Data replication is an efficient way for distributing replicas among the data grids, making it possible to access similar data in different locations of the data grid. Replication reduces data access time and improves the performance of the system. In this paper, we propose a new dynamic data replication algorithm named PDDRA that optimizes the traditional algorithms. Our proposed algorithm is based on an assumption: members in a VO (Virtual Organization) have similar interests in files. Based on this assumption and also file access history, PDDRA predicts future needs of grid sites and pre-fetches a sequence of files to the requester grid site, so the next time that this site needs a file, it will be locally available. This will considerably reduce access latency, response time and bandwidth consumption. PDDRA consists of three phases: storing file access patterns, requesting a file and performing replication and pre-fetching and replacement. The algorithm was tested using a grid simulator, OptorSim developed by European Data Grid projects. The simulation results show that our proposed algorithm has better performance in comparison with other algorithms in terms of job execution time, effective network usage, total number of replications, hit ratio and percentage of storage filled.
---
paper_title: PFRF: An adaptive data replication algorithm based on star-topology data grids

paper_content:

Recently, data replication algorithms have been widely employed in data grids to replicate frequently accessed data to appropriate sites. The purposes are shortening file transmission distance and delivering files from nearby sites to local sites so as to improve data access performance and reduce bandwidth consumption. Some of the algorithms were designed based on unlimited storage. However, they might not be practical in real-world data grids since currently no system has infinite storage. Others were implemented on limited storage environments, but none of them considers data access patterns which reflect the changes of users' interests, and these are important parameters affecting file retrieval efficiency and bandwidth consumption. In this paper, we propose an adaptive data replication algorithm, called the Popular File Replicate First algorithm (PFRF for short), which is developed on a star-topology data grid with limited storage space based on aggregated information on previous file accesses. The PFRF periodically calculates file access popularity to track the variation of users' access behaviors, and then replicates popular files to appropriate sites to adapt to the variation. We employ several types of file access behaviors, including Zipf-like, geometric, and uniform distributions, to evaluate PFRF. The simulation results show that PFRF can effectively improve average job turnaround time, bandwidth consumption for data delivery, and data availability as compared with those of the tested algorithms.
---
paper_title: Adaptive popularity-driven replica placement in hierarchical data grids

paper_content:

Data grids support access to widely distributed storage for large numbers of users accessing potentially many large files. Efficient access is hindered by the high latency of the Internet. To improve access time, replication at nearby sites may be used. Replication also provides high availability, decreased bandwidth use, enhanced fault tolerance, and improved scalability. Resource availability, network latency, and user requests in a grid environment may vary with time. Any replica placement strategy must be able to adapt to such dynamic behavior. In this paper, we describe a new dynamic replica placement algorithm, Popularity Based Replica Placement (PBRP), for hierarchical data grids which is guided by file "popularity". Our goal is to place replicas close to clients to reduce data access time while still using network and storage resources efficiently. The effectiveness of PBRP depends on the selection of a threshold value related to file popularity. We also present Adaptive-PBRP (APBRP) that determines this threshold dynamically based on data request arrival rates. We evaluate both algorithms using simulation. Results for a range of data access patterns show that our algorithms can shorten job execution time significantly and reduce bandwidth consumption compared to other dynamic replication methods.
---
paper_title: A survey of dynamic replication strategies for improving data availability in data grids

paper_content:

Data grid is a distributed collection of storage and computational resources that are not bounded within a geophysical location. It is a fast growing area of research and providing efficient data access and maximum data availability is a challenging task. To achieve this task, data is replicated to different sites. A number of data replication techniques have been presented for data grids. All replication techniques address some attributes like fault tolerance, scalability, improved bandwidth consumption, performance, storage consumption, data access time etc. In this paper, different issues involved in data replication are identified and different replication techniques are studied to find out which attributes are addressed in a given technique and which are ignored. A tabular representation of all those parameters is presented to facilitate the future comparison of dynamic replication techniques. The paper also includes some discussion about future work in this direction by identifying some open research problems.
---
paper_title: Dynamic replication in a data grid using a Modified BHR Region Based Algorithm

paper_content:

Grid computing is emerging as a key part of the infrastructure for a wide range of disciplines in science and engineering, including astronomy, high energy physics, molecular biology and earth sciences. These applications handle large data sets that need to be transferred and replicated among different grid sites. A data grid deals with data intensive applications in scientific and enterprise computing. Data grid technology is developed to permit data sharing across many organizations in geographically disperse locations. Replication of data to different sites will help researchers around the world analyse and initiate future experiments. The general idea of replication is to store copies of data in different locations so that data can be easily recovered if a copy at one location is lost or unavailable. In a large-scale data grid, replication provides a suitable solution for managing data files, which enhances data reliability and availability. In this paper, a Modified BHR algorithm is proposed to overcome the limitations of the standard BHR algorithm. The algorithm is simulated using a data grid simulator, OptorSim, developed by European Data Grid projects. The performance of the proposed algorithm is improved by minimizing the data access time and avoiding unnecessary replication.
---
paper_title: A study on performance of dynamic file replication algorithms for real-time file access in Data Grids

paper_content:

Real-time Grid applications are emerging in many disciplines of science and engineering. In order to run these applications while meeting the associated real-time constraints with them, the Grid infrastructure should be designed to respect these constraints and allocate its computing, networking, storage, and the other resources accordingly. Furthermore, these applications involve a large number of data intensive jobs and require to access terabytes of data in real-time. On the other hand, a variety of dynamic file replication algorithms were proposed for the best-effort Data Grid environments in an attempt to decrease job completion times and save network bandwidth. Until now, there is no study in the literature which tries to elaborate on the real-time performance of these dynamic file replication algorithms. Based on this motivation, in this study, the performance of eight dynamic replication algorithms are evaluated under various Data Grid settings. For this evaluation, a process oriented and discrete-event driven simulator called DGridSim is developed. A detailed set of simulation studies are conducted using DGridSim and the results obtained are presented to reveal the real-time performance of the dynamic file replication algorithms.
---
paper_title: Identifying Dynamic Replication Strategies for a High-Performance Data Grid

paper_content:

Dynamic replication can be used to reduce bandwidth consumption and access latency in high performance "data grids" where users require remote access to large files. Different replication strategies can be defined depending on when, where, and how replicas are created and destroyed. We describe a simulation framework that we have developed to enable comparative studies of alternative dynamic replication strategies. We present preliminary results obtained with this simulator, in which we evaluate the performance of five different replication strategies for three different kinds of access patterns. The data in ths scenario is read-only and so there are no consistency issues involved. The simulation results show that significant savings in latency and bandwidth can be obtained if the access patterns contain a small degree of geographical locality.
---
paper_title: Cloud Computing and Grid Computing 360-Degree Compared

paper_content:

Cloud Computing has become another buzzword after Web 2.0. However, there are dozens of different definitions for Cloud Computing and there seems to be no consensus on what a Cloud is. On the other hand, Cloud Computing is not a completely new concept; it has intricate connection to the relatively new but thirteen-year established Grid Computing paradigm, and other relevant technologies such as utility computing, cluster computing, and distributed systems in general. This paper strives to compare and contrast Cloud Computing with Grid Computing from various angles and give insights into the essential characteristics of both.
---
paper_title: Minimizing Cost of K-Replica in Hierarchical Data Grid Environment

paper_content:

Replicating of objects at multi nodes has been considered a promising technique for decreasing access cost and network traffic for a large distributed systems like Data Grids. In this paper we propose Optimal Placement of Replicas (OPR) algorithm with the objective of minimizing the total replication cost including communication and storage cost, given that a maximum of k replicas are allowed in a tree data grid with n nodes and height h. OPR has time complexity of O(nhk), which is the lowest time complexity compared with the other algorithms with the same objective function in the past literature. In addition, two greedy algorithms, namely, Greedy Algorithm (GA) and Simple Greedy Algorithm (SGA) are proposed for near optimal placement of k replicas with the lower time complexity compared with that of OPR. We evaluate the proposed algorithms through an extensive simulation experiments in terms of access cost, network traffic and locality access to objects.
---
paper_title: Dynamic replication in a data grid using a Modified BHR Region Based Algorithm

paper_content:

Grid computing is emerging as a key part of the infrastructure for a wide range of disciplines in science and engineering, including astronomy, high energy physics, molecular biology and earth sciences. These applications handle large data sets that need to be transferred and replicated among different grid sites. A data grid deals with data intensive applications in scientific and enterprise computing. Data grid technology is developed to permit data sharing across many organizations in geographically disperse locations. Replication of data to different sites will help researchers around the world analyse and initiate future experiments. The general idea of replication is to store copies of data in different locations so that data can be easily recovered if a copy at one location is lost or unavailable. In a large-scale data grid, replication provides a suitable solution for managing data files, which enhances data reliability and availability. In this paper, a Modified BHR algorithm is proposed to overcome the limitations of the standard BHR algorithm. The algorithm is simulated using a data grid simulator, OptorSim, developed by European Data Grid projects. The performance of the proposed algorithm is improved by minimizing the data access time and avoiding unnecessary replication.
---

Title: Dynamic replication strategies in data grid systems: a survey

Section 1: Introduction
Description 1: Provide an introduction to the concept of data grids, their significance in computational applications, the challenges related to data replication, and the scope of the survey.

Section 2: Existing classifications
Description 2: Discuss existing classification schemes for dynamic replication, including static vs. dynamic, centralized vs. decentralized, push vs. pull-based, and objective function-based classification.

Section 3: Classification of dynamic replication strategies
Description 3: Introduce a new classification of dynamic replication strategies based on data grid architecture, and analyze recent works following this classification.

Section 4: Dynamic replication strategies for hierarchical architecture
Description 4: Review replication strategies designed for hierarchical architectures, including multi-tier and bandwidth hierarchy architectures, and others.

Section 5: Dynamic replication strategies for peer-to-peer architecture
Description 5: Describe replication strategies developed for peer-to-peer architectures, focusing on their decentralized and highly dynamic nature.

Section 6: Dynamic replication strategies for hybrid architecture
Description 6: Discuss strategies for hybrid architectures that combine features of two or more different architectures.

Section 7: Dynamic replication strategies for general graph architecture
Description 7: Examine replication strategies proposed for general graph architectures, emphasizing their scalability and flexibility.

Section 8: Performance evaluation
Description 8: Analyze the performance of different replication strategies on various architectures using a simulation study, focusing on metrics such as response time and effective network usage.

Section 9: Simulation environment
Description 9: Outline the simulation environment, explaining the tools and configurations used for conducting performance evaluations.

Section 10: Simulation results
Description 10: Present the results of the simulation study, comparing the performance of different architectures and summarizing key findings.

Section 11: Analysis
Description 11: Provide an in-depth analysis of the simulation results, discussing how data grid architecture impacts replication performance.

Section 12: Open problems in dynamic replication strategies
Description 12: Identify and discuss unresolved issues and research challenges in the field of dynamic replication strategies.

Section 13: Conclusion
Description 13: Summarize the survey, emphasizing the main findings, and suggest directions for future research.