Investigating dynamic data replication algorithms in grid networks and presenting a new algorithm based on parameters of file size, available bandwidth and geographical distance.

Computer Engineering Masters Thesis

Software Orientation

Abstract

The necessity of increasing use of distributed data in computer networks is clear to everyone. A large number of computing and storage resources are placed together and form the grid. In recent years, grid technology has grown significantly, so that it has been used in most researches and scientific experiments. The big challenges in the data grid are the need for high availability, efficiency and low bandwidth consumption. Data replication is a method that can be used to solve problems such as efficient data access or high availability. In an environment where replication is used, by increasing the number of replicated copies of files with better locality of data, the efficiency of the system will be improved.

In this thesis, different methods of dynamic data replication in data grid networks are investigated and a dynamic data replication algorithm is proposed in the grid, which by taking advantage of the effective factors on data replication, reduces the execution time of tasks and reduces bandwidth consumption and the cost of maintaining versions. This algorithm has been implemented in Optorsim simulator, and the simulation results show that parameters such as the average execution time, the number of replicas, and productivity have improved.

Key words: data grid, data replication, replacement, access pattern, geographical distance, access cost

Chapter One

Introduction

Introduction

Over time, various types of distributed systems [1] have been designed and implemented, one of the types of distributed systems is Grid systems [2]. This technology is characterized by its focus on large-scale resource sharing. Data replication is a data grid service that was created to facilitate and speed up data access. 

2-1. Statement of the problem

Today, in various fields, big data sets are becoming an important part of shared resources. In various fields, including physical energy, bioinformatics, earth observations, global climate changes, image processing and data mining, a huge amount of data is measured in terabytes and in some cases in betabytes. Such a huge amount of information can be accessed by researchers and scientists using sophisticated computing devices. These researchers and computing and storage devices are distributed all over the world.

The huge amount of information and calculations creates new problems regarding data access, processing and distribution, and with a large amount of data, different geographical locations and complex calculations are involved, which makes it difficult to face the challenge of management infrastructure. Data Grid is a suitable solution for all the mentioned problems. Grid is an architecture for distributed management and analysis of scientific data sets.

A large number of computing and storage resources are placed together and form Grid. The main topic and issue that caused the formation of Grid technology was to share resources in a coordinated manner and solve issues and problems in dynamic and multi-institutional virtual organizations. The purpose of sharing was not only the exchange of simple files, but the goal of direct access to computers, software, data and other available resources. Grid provides easy access to all these resources.

3-1. The importance of data grid

The main motivation for designing data grid was to respond to the needs of users with a large amount of data, cover users and distributed resources, and be responsive to analyzes with a high volume of calculations [1].

Effective access to such a large amount of data that is widely distributed is slow due to network delays and bandwidth problems. As the size of a grid grows, the complexity of this system increases. The big challenge that arises in the data grid is the need for high availability, efficiency and saving in network traffic. The data grid is designed to meet the needs of large data sets, geographical distribution of users and resources, and computational analysis. This architecture is also developed for complex operations in large areas and heterogeneous environments.Managing such a large amount of distributed data in a centralized method is not efficient because a large amount of load is imposed on the central server. In addition to the fact that the storage is done on the central server, it also has problems such as failure at one point and bottleneck. Therefore, this large amount of information must be repeated and distributed in different places of the distribution system in order to avoid such issues and problems. The grid retrieves data from the nearest site and replicates it to the requesting sites.

With the help of the data grid, large amounts of data can be stored and then retrieved at different points throughout the grid. In this case, the efficiency of the grid depends on the available bandwidth and network time delay, so that the low bandwidth between the data storage location and the processing location causes grid inefficiency.

4-1. Possible solutions

As we know, the data access time depends on the communication bandwidth in the data grid. In a communication environment, the main factor to ensure fast access to data is the absence of high latency. To reduce the access time, various solutions are used, among these solutions, the use of work scheduling can be mentioned. A good scheduler can reduce data transfer costs as much as possible for faster access by running the job in the right place. Another solution is to use the replication mechanism[3], which increases the access speed by creating copies[4] of a copy, in fact, to increase efficiency, multiple copies of files can be stored across the grid[2].

5-1. Proposed solution

In fact, the complexity of the structure increases with the growth of the grid size. High data availability is a major challenge in Grid. Users' computing applications contain enormous amounts of data. Local storage of a copy of the data is very expensive and impractical. Coping with network delays and storage capacity limitations[5] at different sites to provide high availability is a difficult challenge. To answer the access challenge, data replication is one of the major methods that promotes high availability, bandwidth consumption, increased fault tolerance, and improved scalability and response time [3-9]. When data is replicated, a copy of the data files is placed in different locations of the data grid, replication can save a large amount of bandwidth compared to having the data only reside at one site. Therefore, to ensure constant and fast access to data, data replication is a very good trade-off between available memory and available bandwidth [10]. Data replication is a common way to improve the efficiency of data access in distributed systems. Creating duplicates not only reduces bandwidth consumption, but also reduces access latency. In other words, increasing the efficiency of data reading from appropriate nodes [6] is the main goal of data replication algorithms.

In addition, it is possible to increase data access, reliability, system scalability, load balance by performing replication and queuing them among different sites [11].

The main benefits of replication are: [12]

1. Better availability: When one node fails, the system can access data from another node, which also improves availability.

2. Better performance: Because the data is replicated among multiple nodes, the user can obtain the data from the nearest node or the node with less workload. Data replication techniques can be classified into two main parts, static replication [7] and dynamic replication [8]. In static replication, the number of copies and the host node are statically selected at the beginning, and no more copies are created after that. On the other hand, the dynamic strategy can create the copy in a new node according to the storage capacity and bandwidth or adapt itself to the changes and delete the copies that are no longer needed according to the requests. In static data replication, a duplicate copy exists until it is deleted by the user or its lifetime expires. The defect of static replication is when the access pattern of nodes changes frequently and static algorithms are not able to adapt to new conditions. Once a copy is created on a site, it remains there until it is deleted by the user.