RADMA: A Mobile Agent-Based Resource Discovery Approach
For the Grid Environment
Ebrahim Bagheri, Mahmood Naghibzadeh
Department of computing,Ferdowsi University of Mashhad
,
1
Abstract
The Grid as a novel approach in the distributed computing field focuses on large-scale disperse resource and service sharing. Resources can be defined as a wide range of different storage devices, processing power, and online applications. One of the key services needed in the grid infrastructure is Resource Discovery (RD). In this article we focus on this topic and propose a new distributed methodology for resource discovery using mobile agents. Two models hierarchical/non-hierarchical RD in Virtual Organizations are introduced and evaluated minutely.The simulations show that the non- hierarchical approach has a much better discovery speed and creates lower system load compared with the hierarchical model.
Keywords: Grid, Resource Discovery, Virtual Organization, Mobile Agents
1. Introduction
Grid and software mobile agents are both pursuing the aim of creating a collaborative problem solving environment. While the ultimate goals followed in each technology differs from the conceptual view but they both share many ideas that can be mutually used. The Grid community has mainly focused on creating a distributed resource sharing environment which alleviates the lack of resource problem in the high performance computing area. Virtual organization (VO) is a new concept created in this field which allows a more controlled or market centric approach to Grid computing [1]. On the other hand, research on software mobile agents has been concentrating on different models to create suitable algorithms for problem solving in dynamic environments [2].
As the two fields advance they amusingly congregate. The convergence allows faster progress since many shared concepts have been to a great extent solved in the other field.
The Grid infrastructure provides a rich resources environment, however in many cases the distribution is unfair. The unjust resource distribution is mainly because the resources are shared on an availability basis. There might be an abundance of processing power in one virtual organization while other locations are faced with the lack [3].
This uncontrolled distribution of resources needs a careful resource allocation model to allow an optimized resource usage. This allocation model requires detailed resource description. There has been different resource description models proposed that mainly fall into two main categories: Schema and object model [4]. Both models can be extended to serve different purposes. The models are mainly described using XML. A simple schema is shown in figure 1.
Fig. 1- A resource schema
In our simulations, resources are modeled using the Globus Resource Specification Language [5].
Resource parameters can be seen as two different static and dynamic attributes. Parameters such as resource name, device type etc. fall into the static field where the value of these attributes never change throughout the resource availability time, but on the other hand we may face attributes which dynamically change like the length of the printer queue or the CPU load. These attributes need to be regularly checked for new values.
Static parameters can be announced once in the initial resource advertisement phase while dynamic parameter values should be updated and therefore increase message passing. The update models can use pull or push models. We propose a pull model using the mobile agents which is further introduced in the following parts of the article and decreases the amount of message passing required significantly.
To focus on exploiting the available resources in the Grid, a new model has been created for resource and service discovery in the Grid environment using mobile agents. Two different algorithms derived from the basic model have been implemented and compared. This article has been organized in 5 sections. In section two resource and job request models which follow the Zipf distribution have been explained. The rest of the sections are allocated to an in depth algorithm design and implementation explanation and performance evaluation.The article is then concluded in section five.
2. Resource and Job Request Model
In a Grid environment different requests for available resources or services are made through available interfaces. Resources are requested by the user processes based on their needs without any previous planned sequence therefore a devised resource allocation can't be designed.
It is proved that many events in the real world such as words in human or computer languages, operating system calls, colors in images and etc follow the Zipfian law.
The request model we devised follows the Zipf's law. The probability of a request arrival for any resource Ri is
P (Ri) = ; K =
The formula is then simplified by presuming the A and K constants to be 1 into:
P (Ri) =
The validity of this model is confirmed in similar research on video title request in [6, 7].
3. Resource Discovery Algorithm
We propose two different algorithms for resource discovery. The main idea for our resource discovery algorithm is to use mobile agents to discover the available resources.
Resources are located dispersedly on different virtual organizations which consist of multiple nodes that can be of any formation such as PCs or clusters. Resources are allocated to each node [8]. Therefore the Resource Table (RT) in each node consists of a list of resources available in the Grid environment.The idea to create a Resource Table has been adapted with many changes from the Agent Capability Table in [9]. Updating the RT is to some extent related to the advertisement protocol used.
The structure of the RT is designed in a way that allows the node to exactly locate resources available on the same virtual organization. On the other hand a node will only be able to approximately locate resources in other virtual organizations. In this way if a resource residing on a different virtual organization is requested the node will be able to find the related virtual organization but won't be able to specify the exact node to which the resource is attached to. The structure of a RT consists of the a unique node or VO identifier which is used to specify a particular node or virtual organization.The second field specifies if the record is showing that a resource is allocated on a VO or a node.A field to state the type of the resource has also been defined.We have also used many other fields that are not explained here for the sake of simplicity.Every record in this table corresponds to a resource available in the Grid environment.
Once a request for a resource or service arrives at a node in the grid the resource discovery algorithm consults the Resource Table residing on the node and one of the following strategies would be taken:
I. Non-Hierarchical Approach
In this approach, having consulted the RT, a number of mobile agents are created. The number of mobile agents created here is equal to the matching records available in the RT table. The mobile agents are then sent to the corresponding VOs.
An attorney which will be the representative of the destination VO is chosen (we assume the closest node to the originating VO to be the attorney to avoid bottlenecks created by choosing a permanent attorney. In this way the attorney changes frequently based on the originating request's VO and network conditions).The mobile agent will pass on the request to the attorney and will wait for the attorney to provide it with required information.
The attorney will then consult its RT which provides it with the exact location of the requested resource. The attorney will consequently create a number of mobile agents to move to the corresponding nodes and return the resource status.
Using the mobile agents in this way will allow us to query dynamic attributes of a resource without the need for a frequent message passing method when the attribute values change. On the other hand the mobile agent will be able to spot the traffic conditions of the connection and ultimately compute the effective time of discovery and also locate the best resource available.
The multiple mobile agents then summon in the attorney and the most suitable resource available is introduced to the waiting agent. The waiting agent will then return to its origination along with other mobile agents which had been sent to other VOs. A decision is then made based on all of the information gathered.
This method also benefits from a RT update model. When the agents probe for specific resources they might encounter missing resources which where stated as available in their originating node's RT. In this way they will not only inform and update their own RT but will also update the attorney's RT which will thus broadcast the change to all of the nodes in the VO and provide a global VO RT update.
The total exploration time in the non-hierarchical algorithm would be as follows:
Where
Texp: Total exploration time
Tac: Time to create one agent
K, K': number of agents
Tcvot: Time to jump to next VO
Tivot: Time to jump to next node
Tq: Time taken to query a resource
U is the Max operator
II. Hierarchical Approach
In this second approach, since there may exist enough suitable resources on the source VO, all VOs are not initially queried.In the first stage only records in the RT that have the same virtual organization identifier are queried for the desired resource, if the resource is found and the required specifications match the existing resource then the resource discovery process will end here. But if no suitable resource is found or the matching resource doesn’t satisfy the required QOS conditions then other VOs are also queried. Using this hierarchical method internal resources are queried for matches and only in the case of failure other virtual organizations are tried.
The total exploration time in the hierarchical algorithm would be:
Where
: is one if resource was not found in the first attempt and zero if it had been reached.
4. Performance Evaluation
The performance of the two algorithms described in the previous section where evaluated using an implemented simulation environment.
A total number of fifteen experiments using different resource distribution models were carried out. Resource distribution was done based on three different strategies.
In the first (SVSNDR) five experiments the number of virtual organization and the number of nodes had been kept constant (10 virtual organizations and 100 nodes), while the number of resources varied between 10 and 50. The distribution model is shown in figure 3.
In the next five experiments (SVDNSR) the number of virtual organization were again kept constant along with the constant number of resources (10 virtual organizations and 50 resources), but the number of nodes changed between 100 and 300.Figure 4 shows this distribution.
The last five experiments (DVSNSR) as shown in figure 5 dynamically changed the number of virtual organizations between 10 and 50 while the number of nodes and resources were kept constant.
1
Fig. 3 - Dynamic change in the number of resources
Fig. 4 - Dynamic change in the number of nodes
Fig. 4 - Dynamic change in the number of resources
1
The results as had been previously anticipated show a better performance for the hierarchical algorithm compared with the non-hierarchical algorithm. For the sake of comparison different performance evaluation factors where evaluated which are briefly introduced here:
· (Selected / Maximum) Path Ratio: This factor shows the extent to which the selected path to the resource has been successful in minimizing the overall path length.
· Mean Agent Life Time(MALT):
This factor calculates the average life time of an active agent working in a grid environment.
· Number of Active Agents in Discovery (NAAD):
The NAAD will count the average number of activated mobile agents for a resource discovery process.
· Number of Active Agents times by their Life Span(SL):
The lower the SL is for the discovery process the lower the burden created on the Grid will be. (Figure 6)
· Maximum Discovery Time(MXDT):
The slowest agent's discovery time is known as the maximum discovery time. This is usually equal to the resource discovery time. (Figure 7)
· Minimum Discovery Time(MNDT):
The discovery time of the fastest agent to locate the required resource is called the minimum discovery time. (Figure 8)
As the minimum discovery time in both approaches belongs to the discovery process within the same virtual organization, a similar diagram for both algorithms in MNDT was expected.This is clearly seen in figure 8. On the other hand the MNDT and MXDT diagrams for the hierarchical algorithm were anticipated to have similar behavior caused by the initial local originating virtual organization search done by the hierarchical algorithm.
The acquired results confirm the expectations and validate the simulations performed for both of the resource discovery algorithms proposed.
Although the hierarchical algorithm seems to create agents with longer activity life time but the overall load on the system is balanced by creating less mobile agents.
The experiments show that the hierarchical algorithm performs better with higher speed in resource discovery and lower overall system burden on the network traffic in the grid environment.
1
Fig. 6 – Number of Active Agents times by their Life Span (SL)
Fig. 7 - Maximum Discovery Time (effective discovery time)
Fig. 8 – Minimum Discovery Time
1
5. Conclusion
In this article, we described two new approaches towards resource discovery in the Grid environment. These algorithms exploit mobile agents for the discovery process. The algorithms sre effectively implemented and the results are compared. The simulation results show a more effective outcome for the hierarchical algorithm with higher speed of service discovery and lower system load. The simulation was validated and its results are approved to be correct.
References
[1]Foster, I. and Kesselman, C.,"The Grid: Blueprint for a New Computing Infrastructure " 2nd ed. Morgan Kaufmann, 2004.