Optimal Grid Scheduling Using Improved Artificial Bee Colony Algorithm
Job Scheduling plays an important role for efficient
utilization of grid resources available across different domains and
geographical zones. Scheduling of jobs is challenging and NPcomplete.
Evolutionary / Swarm Intelligence algorithms have been
extensively used to address the NP problem in grid scheduling.
Artificial Bee Colony (ABC) has been proposed for optimization
problems based on foraging behaviour of bees. This work proposes a
modified ABC algorithm, Cluster Heterogeneous Earliest First Min-
Min Artificial Bee Colony (CHMM-ABC), to optimally schedule
jobs for the available resources. The proposed model utilizes a novel
Heterogeneous Earliest Finish Time (HEFT) Heuristic Algorithm
along with Min-Min algorithm to identify the initial food source.
Simulation results show the performance improvement of the
proposed algorithm over other swarm intelligence techniques.
MICOSim: A Simulator for Modelling Economic Scheduling in Grid Computing
This paper is concerned with the design and implementation of MICOSim, an event-driven simulator written in Java for evaluating the performance of Grid entities (users, brokers and resources) under different scenarios such as varying the numbers of users, resources and brokers and varying their specifications and employed strategies.
New Hybrid Algorithm for Task Scheduling in Grid Computing to Decrease missed Task
The purpose of Grid computing is to utilize
computational power of idle resources which are distributed in
different areas. Given the grid dynamism and its decentralize
resources, there is a need for an efficient scheduler for scheduling
applications. Since task scheduling includes in the NP-hard problems
various researches have focused on invented algorithms especially
the genetic ones. But since genetic is an inherent algorithm which
searches the problem space globally and does not have the efficiency
required for local searching, therefore, its combination with local
searching algorithms can compensate for this shortcomings. The aim
of this paper is to combine the genetic algorithm and GELS (GAGELS)
as a method to solve scheduling problem by which
simultaneously pay attention to two factors of time and number of
missed tasks. Results show that the proposed algorithm can decrease
makespan while minimizing the number of missed tasks compared
with the traditional methods.
Secure Resource Selection in Computational Grid Based on Quantitative Execution Trust
Grid computing provides a virtual framework for
controlled sharing of resources across institutional boundaries.
Recently, trust has been recognised as an important factor for
selection of optimal resources in a grid. We introduce a new method
that provides a quantitative trust value, based on the past interactions
and present environment characteristics. This quantitative trust value
is used to select a suitable resource for a job and eliminates run time
failures arising from incompatible user-resource pairs. The proposed
work will act as a tool to calculate the trust values of the various
components of the grid and there by improves the success rate of the
jobs submitted to the resource on the grid. The access to a resource
not only depend on the identity and behaviour of the resource but
also upon its context of transaction, time of transaction, connectivity
bandwidth, availability of the resource and load on the resource. The
quality of the recommender is also evaluated based on the accuracy
of the feedback provided about a resource. The jobs are submitted for
execution to the selected resource after finding the overall trust value
of the resource. The overall trust value is computed with respect to
the subjective and objective parameters.
Achieving High Availability by Implementing Beowulf Cluster
A computer cluster is a group of tightly coupled
computers that work together closely so that in many respects they
can be viewed as though they are a single computer. The components
of a cluster are commonly, but not always, connected to each other
through fast local area networks. Clusters are usually deployed to
improve performance and/or availability over that provided by a
single computer, while typically being much more cost-effective than
single computers of comparable speed or availability. This paper
proposed the way to implement the Beowulf Cluster in order to
achieve high performance as well as high availability.
Grouping-Based Job Scheduling Model In Grid Computing
Grid computing is a high performance computing
environment to solve larger scale computational applications. Grid
computing contains resource management, job scheduling, security
problems, information management and so on. Job scheduling is a
fundamental and important issue in achieving high performance in
grid computing systems. However, it is a big challenge to design an
efficient scheduler and its implementation. In Grid Computing, there
is a need of further improvement in Job Scheduling algorithm to
schedule the light-weight or small jobs into a coarse-grained or
group of jobs, which will reduce the communication time,
processing time and enhance resource utilization. This Grouping
strategy considers the processing power, memory-size and
bandwidth requirements of each job to realize the real grid system.
The experimental results demonstrate that the proposed scheduling
algorithm efficiently reduces the processing time of jobs in
comparison to others.
A Survey of Job Scheduling and Resource Management in Grid Computing
Grid computing is a form of distributed computing
that involves coordinating and sharing computational power, data
storage and network resources across dynamic and geographically
dispersed organizations. Scheduling onto the Grid is NP-complete,
so there is no best scheduling algorithm for all grid computing
systems. An alternative is to select an appropriate scheduling
algorithm to use in a given grid environment because of the
characteristics of the tasks, machines and network connectivity. Job
and resource scheduling is one of the key research area in grid
computing. The goal of scheduling is to achieve highest possible
system throughput and to match the application need with the
available computing resources. Motivation of the survey is to
encourage the amateur researcher in the field of grid computing, so
that they can understand easily the concept of scheduling and can
contribute in developing more efficient scheduling algorithm. This
will benefit interested researchers to carry out further work in this
thrust area of research.
Fortification for P2P Grid Computing Used for Resource Discovery
Grid computing provides an effective infrastructure for massive computation among flexible and dynamic collection of individual system for resource discovery. The major challenge for grid computing is to prevent breaches and secure the data from trespassers. To overcome such conflicts a semantic approach can be designed which will filter the access requests of peers by checking the resource description specifying the data and the metadata as factual statements. Between every node in the grid a semantic firewall as a middleware will be present The intruder will be required to present an application specifying there needs to the firewall and hence accordingly the system will grant or deny the application request.
An Agent Based Dynamic Resource Scheduling Model with FCFS-Job Grouping Strategy in Grid Computing
Grid computing is a group of clusters connected over
high-speed networks that involves coordinating and sharing
computational power, data storage and network resources operating
across dynamic and geographically dispersed locations. Resource
management and job scheduling are critical tasks in grid computing.
Resource selection becomes challenging due to heterogeneity and
dynamic availability of resources. Job scheduling is a NP-complete
problem and different heuristics may be used to reach an optimal or
near optimal solution. This paper proposes a model for resource and
job scheduling in dynamic grid environment. The main focus is to
maximize the resource utilization and minimize processing time of
jobs. Grid resource selection strategy is based on Max Heap Tree
(MHT) that best suits for large scale application and root node of
MHT is selected for job submission. Job grouping concept is used to
maximize resource utilization for scheduling of jobs in grid
computing. Proposed resource selection model and job grouping
concept are used to enhance scalability, robustness, efficiency and
load balancing ability of the grid.
Cloud Computing: Changing Cogitation about Computing
Cloud Computing is a new technology that helps us to
use the Cloud for compliance our computation needs. Cloud refers to a scalable network of computers that work together like Internet. An
important element in Cloud Computing is that we shift processing, managing, storing and implementing our data from, locality into the
Cloud; So it helps us to improve the efficiency. Because of it is new
technology, it has both advantages and disadvantages that are
scrutinized in this article. Then some vanguards of this technology
are studied. Afterwards we find out that Cloud Computing will have
important roles in our tomorrow life!
Developing a Sustainable Educational Portal for the D-Grid Community
Within the last years, several technologies have been developed to help building e-learning portals. Most of them follow approaches that deliver a vast amount of functionalities, suitable for class-like learning. The SuGI project, as part of the D-Grid (funded by the BMBF), targets on delivering a highly scalable and sustainable learning solution to provide materials (e.g. learning modules, training systems, webcasts, tutorials, etc.) containing knowledge about Grid computing to the D-Grid community. In this article, the process of the development of an e-learning portal focused on the requirements of this special user group is described. Furthermore, it deals with the conceptual and technical design of an e-learning portal, addressing the special needs of heterogeneous target groups. The main focus lies on the quality management of the software development process, Web templates for uploading new contents, the rich search and filter functionalities which will be described from a conceptual as well as a technical point of view. Specifically, it points out best practices as well as concepts to provide a sustainable solution to a relatively unknown and highly heterogeneous community.
SWARM: A Meta-Scheduler to Minimize Job Queuing Times on Computational Grids
Some meta-schedulers query the information system of individual supercomputers in order to submit jobs to the least busy supercomputer on a computational Grid. However, this information can become outdated by the time a job starts due to changes in scheduling priorities. The MSR scheme is based on Multiple Simultaneous Requests and can take advantage of opportunities resulting from these priorities changes. This paper presents the SWARM meta-scheduler, which can speed up the execution of large sets of tasks by minimizing the job queuing time through the submission of multiple requests. Performance tests have shown that this new meta-scheduler is faster than an implementation of the MSR scheme and the gLite meta-scheduler. SWARM has been used through the GridQTL project beta-testing portal during the past year. Statistics are provided for this usage and demonstrate its capacity to achieve reliably a substantial reduction of the execution time in production conditions.
Performance Evaluation of Data Transfer Protocol GridFTP for Grid Computing
In Grid computing, a data transfer protocol called
GridFTP has been widely used for efficiently transferring a large volume
of data. Currently, two versions of GridFTP protocols, GridFTP
version 1 (GridFTP v1) and GridFTP version 2 (GridFTP v2), have
been proposed in the GGF. GridFTP v2 supports several advanced
features such as data streaming, dynamic resource allocation, and
checksum transfer, by defining a transfer mode called X-block mode.
However, in the literature, effectiveness of GridFTP v2 has not been
fully investigated. In this paper, we therefore quantitatively evaluate
performance of GridFTP v1 and GridFTP v2 using mathematical
analysis and simulation experiments. We reveal the performance
limitation of GridFTP v1, and quantitatively show effectiveness of
GridFTP v2. Through several numerical examples, we show that by
utilizing the data streaming feature, the average file transfer time of
GridFTP v2 is significantly smaller than that of GridFTP v1.
Grid-HPA: Predicting Resource Requirements of a Job in the Grid Computing Environment
For complete support of Quality of Service, it is better that environment itself predicts resource requirements of a job by using special methods in the Grid computing. The exact and correct prediction causes exact matching of required resources with available resources. After the execution of each job, the used resources will be saved in the active database named "History". At first some of the attributes will be exploit from the main job and according to a defined similarity algorithm the most similar executed job will be exploited from "History" using statistic terms such as linear regression or average, resource requirements will be predicted. The new idea in this research is based on active database and centralized history maintenance. Implementation and testing of the proposed architecture results in accuracy percentage of 96.68% to predict CPU usage of jobs and 91.29% of memory usage and 89.80% of the band width usage.
An Off-the-Shelf Scheme for Dependable Grid Systems Using Virtualization
Recently, grid computing has been widely focused on
the science, industry, and business fields, which are required a vast
amount of computing. Grid computing is to provide the environment
that many nodes (i.e., many computers) are connected with each
other through a local/global network and it is available for many
users. In the environment, to achieve data processing among nodes
for any applications, each node executes mutual authentication by
using certificates which published from the Certificate Authority
(for short, CA). However, if a failure or fault has occurred in the
CA, any new certificates cannot be published from the CA. As
a result, a new node cannot participate in the gird environment.
In this paper, an off-the-shelf scheme for dependable grid systems
using virtualization techniques is proposed and its implementation is
verified. The proposed approach using the virtualization techniques
is to restart an application, e.g., the CA, if it has failed. The system
can tolerate a failure or fault if it has occurred in the CA. Since
the proposed scheme is implemented at the application level easily,
the cost of its implementation by the system builder hardly takes
compared it with other methods. Simulation results show that the
CA in the system can recover from its failure or fault.
Dynamic Load Balancing Strategy for Grid Computing
Workload and resource management are two essential functions provided at the service level of the grid software infrastructure. To improve the global throughput of these software environments, workloads have to be evenly scheduled among the available resources. To realize this goal several load balancing strategies and algorithms have been proposed. Most strategies were developed in mind, assuming homogeneous set of sites linked with homogeneous and fast networks. However for computational grids we must address main new issues, namely: heterogeneity, scalability and adaptability. In this paper, we propose a layered algorithm which achieve dynamic load balancing in grid computing. Based on a tree model, our algorithm presents the following main features: (i) it is layered; (ii) it supports heterogeneity and scalability; and, (iii) it is totally independent from any physical architecture of a grid.
Parallel and Distributed Mining of Association Rule on Knowledge Grid
In Virtual organization, Knowledge Discovery (KD)
service contains distributed data resources and computing grid nodes.
Computational grid is integrated with data grid to form Knowledge
Grid, which implements Apriori algorithm for mining association
rule on grid network. This paper describes development of parallel
and distributed version of Apriori algorithm on Globus Toolkit using
Message Passing Interface extended with Grid Services (MPICHG2).
The creation of Knowledge Grid on top of data and
computational grid is to support decision making in real time
applications. In this paper, the case study describes design and
implementation of local and global mining of frequent item sets. The
experiments were conducted on different configurations of grid
network and computation time was recorded for each operation. We
analyzed our result with various grid configurations and it shows
speedup of computation time is almost superlinear.
Grid Computing in Physics and Life Sciences
Certain sciences such as physics, chemistry or biology,
have a strong computational aspect and use computing infrastructures
to advance their scientific goals. Often, high performance and/or high
throughput computing infrastructures such as clusters and computational
Grids are applied to satisfy computational needs. In addition,
these sciences are sometimes characterised by scientific collaborations
requiring resource sharing which is typically provided by Grid
approaches. In this article, I discuss Grid computing approaches in
High Energy Physics as well as in bioinformatics and highlight some
of my experience in both scientific domains.
An Improved Resource Discovery Approach Using P2P Model for Condor: A Grid Middleware
Resource Discovery in Grids is critical for efficient
resource allocation and management. Heterogeneous nature and
dynamic availability of resources make resource discovery a
challenging task. As numbers of nodes are increasing from tens to
thousands, scalability is essentially desired. Peer-to-Peer (P2P)
techniques, on the other hand, provide effective implementation of
scalable services and applications. In this paper we propose a model
for resource discovery in Condor Middleware by using the four axis
framework defined in P2P approach. The proposed model enhances
Condor to incorporate functionality of a P2P system, thus aim to
make Condor more scalable, flexible, reliable and robust.
Towards Design of Context-Aware Sensor Grid Framework for Agriculture
This paper is to present context-aware sensor grid
framework for agriculture and its design challenges. Use of sensor
networks in the domain of agriculture is not new. However, due to
the unavailability of any common framework, solutions that are
developed in this domain are location, environment and problem
dependent. Keeping the need of common framework for agriculture,
Context-Aware Sensor Grid Framework is proposed. It will be
helpful in developing solutions for majority of the problems related
to irrigation, pesticides spray, use of fertilizers, regular monitoring of
plot and yield etc. due to the capability of adjusting according to
location and environment. The proposed framework is composed of
three layer architecture including context-aware application layer,
grid middleware layer and sensor network layer.
Implementation of Watch Dog Timer for Fault Tolerant Computing on Cluster Server
In today-s new technology era, cluster has become a
necessity for the modern computing and data applications since many
applications take more time (even days or months) for computation.
Although after parallelization, computation speeds up, still time
required for much application can be more. Thus, reliability of the
cluster becomes very important issue and implementation of fault
tolerant mechanism becomes essential. The difficulty in designing a
fault tolerant cluster system increases with the difficulties of various
failures. The most imperative obsession is that the algorithm, which
avoids a simple failure in a system, must tolerate the more severe
failures. In this paper, we implemented the theory of watchdog timer
in a parallel environment, to take care of failures. Implementation of
simple algorithm in our project helps us to take care of different
types of failures; consequently, we found that the reliability of this
A Graph-Based Approach for Placement of No-Replicated Databases in Grid
On a such wide-area environment as a Grid, data
placement is an important aspect of distributed database systems. In
this paper, we address the problem of initial placement of database
no-replicated fragments in Grid architecture. We propose a graph
based approach that considers resource restrictions. The goal is to
optimize the use of computing, storage and communication
resources. The proposed approach is developed in two phases: in the
first phase, we perform fragment grouping using knowledge about
fragments dependency and, in the second phase, we determine an
efficient placement of the fragment groups on the Grid. We also
show, via experimental analysis that our approach gives solutions
that are close to being optimal for different databases and Grid
Grid Coordination with Marketmaker Agents
Market based models are frequently used in the resource
allocation on the computational grid. However, as the size of
the grid grows, it becomes difficult for the customer to negotiate
directly with all the providers. Middle agents are introduced to
mediate between the providers and customers and facilitate the
resource allocation process. The most frequently deployed middle
agents are the matchmakers and the brokers. The matchmaking agent
finds possible candidate providers who can satisfy the requirements
of the consumers, after which the customer directly negotiates with
the candidates. The broker agents are mediating the negotiation with
the providers in real time.
In this paper we present a new type of middle agent, the marketmaker.
Its operation is based on two parallel operations - through
the investment process the marketmaker is acquiring resources and
resource reservations in large quantities, while through the resale process
it sells them to the customers. The operation of the marketmaker
is based on the fact that through its global view of the grid it can
perform a more efficient resource allocation than the one possible in
one-to-one negotiations between the customers and providers.
We present the operation and algorithms governing the operation
of the marketmaker agent, contrasting it with the matchmaker and
broker agents. Through a series of simulations in the task oriented
domain we compare the operation of the three agents types. We find
that the use of marketmaker agent leads to a better performance in the
allocation of large tasks and a significant reduction of the messaging
A Framework for Scalable Autonomous P2P Resource Discovery for the Grid Implementation
Recently, there have been considerable efforts towards the convergence between P2P and Grid computing in order to reach a solution that takes the best of both worlds by exploiting the advantages that each offers. Augmenting the peer-to-peer model to the services of the Grid promises to eliminate bottlenecks and ensure greater scalability, availability, and fault-tolerance. The Grid Information Service (GIS) directly influences quality of service for grid platforms. Most of the proposed solutions for decentralizing the GIS are based on completely flat overlays. The main contributions for this paper are: the investigation of a novel resource discovery framework for Grid implementations based on a hierarchy of structured peer-to-peer overlay networks, and introducing a discovery algorithm utilizing the proposed framework. Validation of the framework-s performance is done via simulation. Experimental results show that the proposed organization has the advantage of being scalable while providing fault-isolation, effective bandwidth utilization, and hierarchical access control. In addition, it will lead to a reliable, guaranteed sub-linear search which returns results within a bounded interval of time and with a smaller amount of generated traffic within each domain.
Resource Discovery in Web-Services Based Grids
A Web-services based grid infrastructure is evolving to be readily available in the near future. In this approach, the Web services are inherited (encapsulated or functioned) into the same existing Grid services class. In practice there is not much difference between the existing Web and grid infrastructure. Grid services emerged as stateful web services. In this paper, we present the key components of web-services based grid and also how the resource discovery is performed on web-services based grid considering resource discovery, as a critical service, to be provided by any type of grid.
Automatic Visualization Pipeline Formation for Medical Datasets on Grid Computing Environment
Distance visualization of large datasets often takes the direction of remote viewing and zooming techniques of stored static images. However, the continuous increase in the size of datasets and visualization operation causes insufficient performance with traditional desktop computers. Additionally, the visualization techniques such as Isosurface depend on the available resources of the running machine and the size of datasets. Moreover, the continuous demand for powerful computing powers and continuous increase in the size of datasets results an urgent need for a grid computing infrastructure. However, some issues arise in current grid such as resources availability at the client machines which are not sufficient enough to process large datasets. On top of that, different output devices and different network bandwidth between the visualization pipeline components often result output suitable for one machine and not suitable for another. In this paper we investigate how the grid services could be used to support remote visualization of large datasets and to break the constraint of physical co-location of the resources by applying the grid computing technologies. We show our grid enabled architecture to visualize large medical datasets (circa 5 million polygons) for remote interactive visualization on modest resources clients.
An Ant Colony Optimization for Dynamic JobScheduling in Grid Environment
Grid computing is growing rapidly in the distributed
heterogeneous systems for utilizing and sharing large-scale resources
to solve complex scientific problems. Scheduling is the most recent
topic used to achieve high performance in grid environments. It aims
to find a suitable allocation of resources for each job. A typical
problem which arises during this task is the decision of scheduling. It
is about an effective utilization of processor to minimize tardiness
time of a job, when it is being scheduled. This paper, therefore,
addresses the problem by developing a general framework of grid
scheduling using dynamic information and an ant colony
optimization algorithm to improve the decision of scheduling. The
performance of various dispatching rules such as First Come First
Served (FCFS), Earliest Due Date (EDD), Earliest Release Date
(ERD), and an Ant Colony Optimization (ACO) are compared.
Moreover, the benefit of using an Ant Colony Optimization for
performance improvement of the grid Scheduling is also discussed. It
is found that the scheduling system using an Ant Colony
Optimization algorithm can efficiently and effectively allocate jobs
to proper resources.
Mobile Ad-Hoc Service Grid – MASGRID
Mobile devices, which are progressively surrounded
in our everyday life, have created a new paradigm where they
interconnect, interact and collaborate with each other. This network
can be used for flexible and secure coordinated sharing. On the other
hand Grid computing provides dependable, consistent, pervasive, and
inexpensive access to high-end computational capabilities. In this
paper, efforts are made to map the concepts of Grid on Ad-Hoc
networks because both exhibit similar kind of characteristics like
Scalability, Dynamism and Heterogeneity. In this context we
propose “Mobile Ad-Hoc Services Grid – MASGRID".
Performance Prediction of Multi-Agent Based Simulation Applications on the Grid
A major requirement for Grid application developers is ensuring performance and scalability of their applications. Predicting the performance of an application demands understanding its specific features. This paper discusses performance modeling and prediction of multi-agent based simulation (MABS) applications on the Grid. An experiment conducted using a synthetic MABS workload explains the key features to be included in the performance model. The results obtained from the experiment show that the prediction model developed for the synthetic workload can be used as a guideline to understand to estimate the performance characteristics of real world simulation applications.