Presenting an ant community algorithm to improve the time of doing tasks in the grid environment

Dissertation for M.Sc degree

Abstract

In this thesis, we have presented a new method in network processing with Ant Algorithm. The model we used in the network space is a continuous two-way auction. Due to their simplicity and dynamics, these models are used in many algorithms used to control resources and schedule tasks. Many of these models are weak in their response time when managing resources. In the auction model, the auctioneers announce the buyers' desired prices, and the buyer who announced the right price gets the resource. This problem itself causes the response time to increase due to buyers' requests. In this thesis, we presented a new method using the genetic algorithm in the two-way auction scenario. In this method, by intelligentizing the resources, we moved the proposed request packages[1] to a direction. Each of these network environments can be considered as a distributed system that does not interact with other networks and covers a large amount of data. One of the benefits of this method compared to the clustering method is that resources can be geographically dispersed and asymmetrically placed. According to the distribution of data sets, the selection of computing resources and data containing resources should be done appropriately so that the overhead caused by transferring these sets to the grid is minimized. In this research, the problem of scheduling programs that require data is considered. Given that optimal scheduling requires choosing the right set of resources. In network processes, the environments are dynamic in the sense that resources may be on at one time and the same resources may be off at another time

The implementations made in the simulation software GridSim were examined and the results showed that this new method improves the processing time and reduces the number of auction steps.

Key words: algorithm, network, software, call for proposal

Chapter One

1-1- Introduction

The main goal of this thesis is to improve efficiency in network processing by the Ant algorithm. This chapter starts with the main problem of network processing and its importance is explained. The use of Ant algorithm in many problems has improved efficiency and reduced processing time. This provides an opportunity to use this algorithm in batch processing.

1-2- Network processing

Network processing refers to a set of resources that work from several different points to achieve a goal. Each of these network environments can be considered as a distributed system that does not interact with other networks and covers a large amount of data. One of the benefits of this method compared to the clustering method is that resources can be geographically dispersed and asymmetrically placed. . According to the distribution of data sets, the selection of computing resources and data containing resources should be done appropriately so that the overhead caused by transferring these sets to the grid is minimized. In this research, the problem of scheduling programs that require data is considered. Given that optimal scheduling requires choosing the right set of resources. In network processes, environments are dynamic in the sense that resources may be on at one time and the same resources may be off at another time. Also, in these processes, they may differ in terms of hardware and software.

Network processing has different architectures, which can be mentioned as follows:

GT2

OGSA

GT3

1-3- Ant algorithm

Ant algorithm is a heuristic algorithm with an optimal local search that is used for combinatorial problems. This method is inspired by the natural behavior of ants. In nature, ants show the way to other ants with the substance they emit. In many researches, the ant colony method is used to solve NP-hard problems. This method is used to solve problems such as traveling salesman, graph coloring and routing.

A community of ants is a collection of intelligent ants that behave as a group.. This community searches the environment to find the optimal solution.

In the scheduling problem in network environments, each of these tasks is considered as an ant. Each of these ants moves in search of the resources they want.

The pseudo code of the ant community is shown below:

Procedure ACO

begin

Initialize the pheromone

while stopping criterion not satisfied do repeat for each ant do Chose next node by applying the state transition rate end for until every ant has build a solution Update the pheromone end while end

There are different methods for the ant community, which can be mentioned as follows:

Max-Min Ant System

Rank-based Ant System

Fast Ant System

Elitist Ant System

1-4- Challenges of network processing

One of the important challenges in network processing is how to prioritize and time Bandi referred to processes. The scheduling problem in network processing consists of three parts:

Finding resources that include resources that can be used

Collecting information about these resources and choosing the best set of resources

Works are done in this step

The step of finding the best set of resources is one of the NP-Complete problems. There are two main goals in scheduling jobs:

The system has the highest efficiency

Has the highest output

For the first goal, a method that reduces the processing time should be provided, and for the second goal, a method should be provided that divides the schedule into a set of independent tasks. This work increases the system's capacity to perform work per unit of time.

Different methods have been provided to solve this problem. One of these methods is to map this problem to the traveling salesman problem. In this method, the paths that the resources have in relation to each other are important. In network processing, due to the fact that the resources are located at different distances and are not symmetrical to each other, this method can be useful in some cases.

In the continuation of this research, the contents are presented as follows.

In the second chapter, we have discussed the relevant backgrounds and the generalities of the scheduling methods, ant, genetics, and auction have been discussed.

In the third chapter, the most important algorithms and methods implemented in the context of scheduling algorithms are presented.

In the fourth chapter, we present the proposed method and the simulation results of the proposed method (Acdanp) are evaluated and compared with the previous method.

In the fifth chapter, we present the suggestions and future works. In addition, the source code written in the Gridsim environment is given in Appendix A.

(images and formulas are available in the main file)

Chapter Two

Research Background

1-1- Overview of Algorithms and Methods

In this section, we review the work done in grid processing. First, we will explain the basic methods such as Dynamic level scheduling and then the recent methods used in this field.

2-2- Dynamic multilevel scheduling

In this method, the goal is to choose the best pair of subtasks and machines for scheduling [1]. A special model has been presented to perform the stated action. The general goal in this method is to reduce the program processing time. In networked processing environments, scheduling algorithms no longer emphasize the subtasks of a program that is executed in the computing host or virtual organization. The main goal is scheduling in such a way that all input programs can use the available power. In the article [2], by adding heuristics to the mentioned method, they have tried to increase the efficiency of the system. 2-3- Allocating the fastest processor to the biggest task. This method depends on two parameters of processor speed and resources and workload. In this method, the largest work is assigned to the fastest resource. If there are a large number of tasks with a large volume, then this method has very low efficiency.

The dynamic FPLTF method [4] is developed according to the static FPLTF method.