A new task scheduling mechanism in grid computing using trust model

Abstract

Most of current research in grid computing is still focused on the improvement of the performance of grid schedulers. However, unlike traditional scheduling, in grid systems there are other important requirements to be taken into account. One such a requirement is the secure scheduling, namely achieving an efficient allocation of tasks to reasonable trustful resources. Trust brings a novel means to improve the security and enable interoperability of current heterogeneous independent grid platforms. In this paper, we present a new task scheduling mechanism based on trust model named TSTM (Task Scheduling mechanism based on Trust Model) in grid environment according to success and failure transaction between grid nodes based on the properties and semantics of trust so that, first the direct trust relation is calculated based on direct experiences between trustor and trustee also, trustor can builds an indirect trust relation with trustee through his acquaintances and then the tasks are assigned to the resources with higher trust values according to our new scheduling method. Theoretical analysis and experimental results prove that the heuristic TSTM algorithm can efficiently meet the requirement of grid computing in trust, and assuring the execution of tasks in a security way and it can obtain higher quality solutions when compared with other ones.

Keywords

Grid computing task scheduling direct trust recommendation trust scheduling framework

1. Introduction

In the recent years, grid computing is rising as a viable paradigm to convince the continuous growth of computation power requirement, which frequently cannot be fulfilled exploiting the internal resources of a single organization [1]. Grid computing is a collection of autonomous and distributed resources available over virtual organizations, and collaborate works with effective, efficient, and reliable way.

Grid computing systems have become popular for the resolution of large-scale complex problems from science, engineering, finance, etc. As large-scale infrastructures for parallel and distributed computing systems, grids enable the virtualization of a whole range of resources, despite their high degree of heterogeneity. Thus, different types of grid systems have been defined. Such systems are currently comprising computational grids, desktop grids, enterprise grids, scavenging grids, data grids, etc. [2]. As a unified computing platform grid tries to connect and share all resources in the Internet, including computation resource, storage resource, information resource, knowledge resource and equipment for scientific research, and then solves the problems of large-scale scientific engineering computing [3, 4].

However, with the characteristics of dynamic, heterogeneity, distribution, openness, voluntariness, uncertainty and deception, how to obtain trustworthy grid resource becomes a key issue in grid research. The traditional method to solve the security problem of these application tasks is to encrypt the data of execution and analysis, or isolate them from the Internet, and then schedule them to local resources to compute and analyze. In grid environment with uncountable numeric nodes, resource is inevitably unreliable, which has a great effect on task execution and scheduling. As grid becomes the next generation of computation and information platform, novel algorithms are needed to schedule the tasks on the trusty nodes to execute, assure the high speed of communication, reduce the tasks execution time, lower the ratio of failure execution, and improve the security of execution environment of important data.

In heterogeneous computing, grid computing, distributed computing and cluster computing environments, many static, dynamic, and even hybrid algorithms have been proposed [5, 6, 7, 8, 9, 10]. At the same time, some issues related to distributed scheduling, center scheduling, autonomy scheduling, intelligent scheduling and Agent negotiation scheduling are also in exploration. However, little of these algorithms takes the characteristics of nodes into account, such as uncertainty, unreliability and deception, and the scheduling length and trustworthiness of nodes cannot be considered synchronously.

Resources and security guarantee are the two fundamental requirements in grid applications [11, 12]. On the other hand, significant challenges also arise. The computational grid exhibits dynamic and unpredictable behavior, namely; the computational performances of each node vary significantly from time to time; the network connections may become unreliable; nodes may join or leave the grid system at any time; nodes may become unavailable without any notifications. As a result, a computational task running on different nodes on the grid will lead to a wide range of completion times. In some extreme cases, a task may never be able to complete. Therefore, how to effectively schedule the grid resources to minimize the task execution time is an issue of prime importance.

One of the important aspects of a grid is task scheduling. Since there exists high heterogeneity of resources such as PCs, workstations, clusters in grid which are not only distributed geographically but also have different time zone, scheduling policies, application requirements and design patterns. A major issue is how to distribute tasks among nodes. In traditional scheduling, tasks are assigned to any of the available nodes. Grid applications that require faster task execution do not perform well since tasks are assigned according to node availability and not according to the computing capability of any node.

With the characteristics of dynamic, uncertainty and deception, how to select trustworthy compute resources and data hosts for applications becomes an urgent problem. The trust mechanism should be used in grid environment [13]. Unfortunately, trust metrics which includes security and reliability is considered rarely in existing scheduling algorithms. Without verifying the justification of the trust, the user is compelled to trust the provider [14]. Users are able to submit tasks to remote resources and typically have no explicit control over the resources themselves. Therefore, mutually users and resources can be viewed as independent agents, having control of their own behavior. Since an individual cannot forecast the response of another to changing situations, this autonomy provides rise to inherent insecurity [15]. The grid service providers must guarantee the users with definite security, privacy protection, and dependable accessibility of all grid enabling platforms. Most grid computing environments spotlight their security concerns in properly authenticating users and hosts and in the communications between them.

To automatically and clearly ensure the fulfillment, the effective and efficient exploitation of grid computing facilities requires advanced and secured resource management systems [16]. The wide range of selection and the high degree of strangeness leads to the problem in secured selection of the resources in grid. Without the assurance of a higher degree of trust relationship, competent resource allocation and utilization cannot be attained. In recent times, with larger applications in ecommerce and on-line communities, trust models have become one of the most important techniques underpinning the distributed application and system safety for its better scalability and flexibility [2]. Recently, a great interest of researchers in grid computing domain has been focused on the secure scheduling, which aims to achieve an efficient assignment of tasks to reasonable trustful machines. Resource management and scheduling in grid is a complex undertaking, lots researches have been developed on the scheduling algorithm. However, existing scheduling algorithms largely ignore the security induced risks involved in dispatching tasks to remote sites.

The most important target of this research is to develop a solution that could afford trust aware security for resource selection in grid for scheduling large number of tasks. The proposed approach aims the schedule of incoming tasks to available resource sites based on the TSTM (Task Scheduling mechanism based on Trust Model). Our approach is meant to enforce security in grids with security-assured resource allocation, and presents a trust model of computation, which classifies compute nodes by their degree of trustworthiness based on their historical direct and recommendation transactions. The major contributions of this paper are as follows:

•
We develop a trust model to evaluate the trust value of the resource provider based on historical transactions so that we consider penalties to punish malicious nodes that have selfish or malicious behaviors and as well as the effect of time for both successful and failure transactions.
•
We present a trust based task scheduling mechanism by integrating the proposed task scheduling and trust model between the grid nodes so that nodes (resources, machines) with higher trust values have higher priority for receiving tasks.
•
We also propose the task scheduling and resource allocation framework based of our proposed trust based task scheduling mechanism.

The rest of the paper is organized as follows. Section 2 presents a brief review of related work. In Section 3, we first present the proposed trust model base on the historical transactions between nodes in grid environments. Also, we have described our task scheduling mechanism based on trust model named TSTM furthermore the trusted scheduling framework is presented in this section. In Section 4, experimental results are given. Finally, concluding remarks and future work are mentioned in Section 5.
2. Literature review

Security is one of the critical concerns in distributed computing environment. Security issues in grid computing have attracted a lot of attention of researchers in the literature. The integration of the security mechanism with the scheduling algorithms to be one of the most important issues in grid scheduling. Nevertheless, only few groups of researchers have investigated security-driven scheduling policy for applications.

Humphrey and Thompson [17] provided usage models for security-aware grid computing. However, they did not elaborate on how a scheduler should be designed to address the security concerns in collaborative computing over distributed cluster environment. Kashyap and Vidyarth [18] proposed a security-driven scheduling algorithm for Computational grid, which can achieve the dual objectives of minimizing the security overhead and maximizing the total security. Song et al. [18] modeled the risk and insecure conditions in grid job scheduling and developed three risk-resilient strategies to provide security assurance of grid job execution. Kołodzie and Xhafa [2] presented an approach combined game-theoretic and Genetic Algorithms for independent task scheduling with security requirements in Computational grids. Heuristic methods, due their robustness, have been successfully applied to solve the large-scale task scheduling problem in the dynamic grid environment [19, 20, 21]. Ge et al. [22] studied the problem of achieving a tradeoff between energy cost and service quality for Internet data centers and proposed a heuristic algorithm to select appropriate security services to guarantee the job security. Xie and Qin [23] built a security overhead model to reasonably measure security overheads incurred by the security-critical tasks and proposed a security-aware real-time heuristic strategy for clusters.

As pointed out by many researchers [24, 25, 26], trust and security are two different notions. Security is a notion associated with the assurance of secure computing services by a grid site or by a cluster node, whereas trust is reflected by the behavior of a resource node.

Wu and Sun [27] defined the risk relationship between jobs and nodes by the security demand and the trust level, and proposed a genetic algorithm to address the heterogeneity of fault-tolerance mechanisms problem in a computational grid. Wang et al. [28] introduced a model which incorporated trust to manage the life cycle of a scientific workflow to assure the execution of tasks in a security environment. Wang et al. [29] explored a kind of trust mechanism based trusted dynamic level scheduling algorithm, which could decrease the failure probability of the task assignments by evaluating the trustworthiness of machines in cloud environment. Tang et al. [30] designed a security-driven scheduling architecture for directed acyclic graph (DAG) applications, which can dynamically measure the trust level of each node in heterogeneous distributed systems by using differential equations. Lin [26] developed a trust management architecture for trust enhanced grid security, incorporating a novel trust model which is capable of capturing various types of trust relationships that exist in a grid system and providing mechanisms for trust evaluation, recommendations and update for trust decisions. Lohr et al. [14] proposed an approach to enhance the grid security using a combination of trusted computing and virtualization technologies. Azzedin and Maheswaran [31] suggested integrating the trust concept into grid resource management. They modified well-known ad hoc heuristics that incorporate the security implications into scheduling algorithms using a trust model for grid systems. Also in another work [32] they proposed a trust brokering system for grid environments that operates in a peer-to-peer manner. They have developed a security-aware model between resource providers and the consumers that separates the concepts of accuracy and honesty. Even though all the solutions mentioned above can improve the efficiency of the computing platform, they ignore the key factor which influences the performance of desktop grid platforms. Dyson et al. [15] described a trust framework model for grid computing, which enables users to execute their jobs on reliable and efficient resources, thereby satisfying clients’ quality-of-service (QoS) requirements.

3. Proposed trust-based task scheduling mechanism

The conceptual model of our proposed task scheduling mechanism based on trust model is presented in Fig. 1. As shown in Fig. 1, the users deliver requests (such as Information services, network services, security services, storage services, etc.) to the Task Management layer. After that, the Task Management layer communicates with the Trust Management middleware and obtains the trust value of resources based on their previous execution of tasks as historical transaction that will be fully explained in following.

Figure 1.

The conceptual model of our proposed task scheduling mechanism.

Accordingly, in this section, we first present the basic concepts of the trust model used in the proposed mechanism, which is in line with our previous work [33]. Then, the proposed task scheduling mechanism based on trust model (TSTM) is presented. After that, a trusted scheduling framework with respect to the proposed TSTM model is presented in the grid environments.

3.1 Trust computing model

Trust is a level of subjective probability between a source node (trustor) and a target node (trustee), which is formed through the direct observation and/or recommendation from trusted nodes, to fulfilling a particular service within a specific time and context [34, 35, 36]. Trust is usually evaluated by trust degree [37]. Trust degree $Td_{ij}$ is used to evaluate the degree of trust from a domain set of possible trust values that trustor $n_{i}$ in views trustee $n_{j}$ and denotes node’s $n_{i}$ trust attitude towards node $n_{j}$ in time $t$ and context $c_{g}$ . The trust degree can be expressed as the following equation:

$\displaystyle Td_{ij}=\left\{\begin{array}[]{c}DT\left(n_{i},\ n_{j}\right),\\ RT\left(n_{i},\ n_{j}\right),\\ \textit{IDT}\left(n_{i},\ n_{j}\right)\\ \end{array}\right.$ (1)

where $Td_{ij}=DT\left(n_{i},\ n_{j}\right)$ , $Td_{ij}=RT\left(n_{i},\ n_{j}\right)$ and $Td_{ij}=\textit{IDT}\left(n_{i},\ n_{j}\right)$ are the direct trust degree, recommendation trust degree and indirect trust degree between trustor $n_{i}$ and trustee $n_{j}$ in context $c_{g}$ and time $t$ , respectively. From different points of views, trust can be categorized into different classes [38, 39]: direct trust and indirect trust. Each of these is explained in the rest of this section.

3.1.1 Direct trust degree

When there is a direct transactional relationship between node $n_{i}$ and node $n_{j}$ , this is called the direct trust relation between node $n_{i}$ and node $n_{j}$ . Figure 2 shows direct trust relation and direct trust degree between node $n_{i}$ and node $n_{j}$ at context $c_{g}$ and time $t$ .

Figure 2.

Direct trust between node $n_{i}$ and node $n_{j}$ .

To calculate trust degree we consider the transactions between trustor $n_{i}$ and trustee $n_{j}$ based on their historical transactions. Suppose node $n_{i}$ has $p$ times successful transactions and $q$ times failure transactions with node $n_{j}$ at a specific time $t$ and context $c_{g}$ . Therefore, we define the direct trust degree between trustor $n_{i}$ and trustee $n_{j}$ in a specific context $c_{g}$ and at time $t$ as follows:

$\displaystyle{Td}^{g}_{ij}(DT)=\frac{\alpha p^{g}+\beta q^{g}}{p^{g}+q^{g}}$ (2)

where $\alpha$ and $\beta$ are the weight of successful and failure or unsuccessful transactions that have a value of 1 and 0, respectively.

A node behavior is not always constant but often changes with time, therefore, the recent experience is more credible than the general historical experience. Therefore, we have considered the functions to determine the successful and unsuccessful experiences over time. These functions calculate the successful transaction rate based on historical successful transaction and failure transaction rate based on historical unsuccessful transaction between trustor $n_{i}$ and trustee $n_{j}$ in a specific context $c_{g}$ and at time $t$ . So, the value of successful transactions over time is calculated as follows:

$\displaystyle p\left(T_{i}\right)=\alpha p\left(\Delta T_{i}\right)+\left(1-% \alpha\right)p\left(T_{i-1}\right),$ $\displaystyle T_{i}=T_{p},$ (3) $\displaystyle p\left(t_{0}\right)=p\left(T_{s}\right)=1$

Similarly, for unsuccessful transactions:

$\displaystyle q\left(T_{i}\right)=\beta q\left(\Delta T_{i}\right)+\left(1-% \beta\right)q\left(T_{i-1}\right),$ $\displaystyle T_{i}=T_{q},$ (4) $\displaystyle q\left(t_{0}\right)=q\left(T_{s}\right)=1$

where $\alpha$ and $\beta$ are the adjustable parameters and present the weight of successful and unsuccessful transactions in different timescale $\Delta T_{i}=T_{i}-T_{i-1}$ respectively. $p\left(\Delta T_{i}\right)$ and $q\left(\Delta T_{i}\right)$ are recent successful and unsuccessful or failure transactions. Also, $p(T_{i-1})$ and $q(T_{i-1})$ are successful and unsuccessful transactions that have occurred in the past. Moreover $T_{p}$ and $T_{q}$ represent the current time, and $T_{s}$ denotes the initial time.

In order to punish the behavior of selfish and malicious nodes, we have considered amounts as penalty $\lambda$ which can be set by trustor for failure or unsuccessful transactions in different timescales as follows:

$\displaystyle\overline{q}\left(\Delta T_{i}\right)={\lambda}_{i}q({\Delta T}_{% i})$ (5)

Therefore, the value of failure or unsuccessful transactions over time is calculated as follows:

$\displaystyle\overline{q}\left(T_{i}\right)=\beta\overline{q}\left(\Delta T_{i% }\right)+\left(1-\beta\right)\overline{q}\left(T_{i-1}\right)$ (6)

According to the above, the direct trust value between trustor node $n_{i}$ and trustee node $n_{j}$ in context $c_{g}$ and at time $t$ is defined as follows:

$\displaystyle{Td}^{g}_{ij}(DT)=\frac{p^{g}\left(T_{i}\right)}{p^{g}\left(T_{i}% \right)+{\overline{q}}^{g}\left(T_{i}\right)}$ (7)

3.1.2 Indirect trust degree computing

If the trustor $n_{i}$ does not have any direct experience with trustee $n_{j}$ or it wants to calculate a more accurate trust degree, it can receive recommendations from its acquaintances based on their direct experiences with the target node. Figure 3 shows the recommendation trust relation between trustor $n_{i}$ and recommender $n_{k}$ .

Figure 3.

Recommendation trust between $n_{i}$ and $n_{k}$ .

The recommendation trust degree between node $n_{i}$ as trustor and node $n_{k}$ as recommender in a specific context $c_{g}$ and at time $t$ , which is calculated as follows:

$\displaystyle{Td}^{g}_{ij}(RT)=\frac{r^{g}\left(T_{i}\right)}{r^{g}\left(T_{i}% \right)+{\overline{s}}^{g}\left(T_{i}\right)}$ (8)

where $r$ represents the number of successful recommendation transactions and $s$ represents the number of failure recommendation transactions between node $n_{j}$ and node $n_{k}$ in a specific context $c_{g}$ and at time $t$ . To prevent the synergistic effect of malicious or selfish nodes, the similarity of recommendations among grid nodes, according to our previous work [33], can be calculated based on adjusted cosine similar function.

An indirect trust relation $\textit{IDT}_{ij}$ is built from recommendations. In other words, the indirect trust relation $\textit{IDT}_{ij}$ integrates the recommendation trust relation $RT_{ki}$ and direct trust relation $DT_{kj}$ which is shown in Fig. 4.

Figure 4.

Indirect trust between $n_{i}$ and $n_{j}$ .

In this paper, we have used min-max composition [42] to integrate direct trust value and recommendation value according to our previous work [33]. We provide a general overview of this composition for computational trust modeling. More detailed information about min-max composition can be found in [33, 44]. Therefore, the indirect trust relation for Fig. 4 is given by:

$\displaystyle Td^{g}_{ij}(\textit{IDT}^{1})=RT\ {}^{\circ}\ DT=RT\left(n_{k},n% _{i},c_{g},t\right)\ {}^{\circ}\ DT\left(n_{k},n_{j},c_{g},t\right)=\left\{% \text{Max}_{n_{k}}\text{Min}\left(RT\left(n_{k},n_{i},c_{g},t\right),DT\left(n% _{k},n_{j},c_{g},t\right)\right)\right\}={\bigvee}_{n_{k}\in N}\left(RT\left(n% _{k},n_{i},c_{g},t\right)\bigwedge DT\left(n_{k},n_{j},c_{g},t\right)\right)$ (9)

In the above equation, we calculated one-level indirect trust value which includes one level recommendation based on Fig. 4. If node $n_{i}$ continues in this manner, there have three, four…n-levels indirect trust relation and it can get more and more accurate trust degree with node $n_{j}$ in context $c_{g}$ . The multi-level composite indirect trust is calculated as:

$\displaystyle Td^{g}_{ij}(\textit{IDT}^{n})=RT\ {}^{\circ}\ RT\ {}^{\circ}\ RT% \ {}^{\circ}\dots{}^{\circ}\ DT$ (10)

3.2 Task scheduling mechanism based on trust model

According to the trust model presented in Sub-section 3.1, in this sub-section we propose a task scheduling mechanism based on trust model in the grid environment. We have extended the traditional dynamic level scheduling (DLS) algorithm [10] by considering trustworthiness of resource nodes. This algorithm meets the requirement of user tasks in trust, and makes tasks scheduling based on directed acyclic graph more reasonable. First, a directed acyclic graph is introduced for modeling the problem. Then, we introduce the task scheduling mechanism based on our proposed trust model named TSTM. Also, we assume that the resources are heterogeneous and the tasks have precedence order. Heterogeneity of resources refers to the different capability of resources that execute tasks. This helps us to model a realistic grid situation.

Tasks with precedence order in the grid environments can be modeled as a DAG, $TG=(V,E)$ , where the set of vertices $v\in V$ is tasks to be executed and $e\in E$ denotes the communication among tasks and representing the precedence constrains between them. A source machine or resource, which represents the location of the user, is also associated with the application. This resource supplies all initial data needed by the application. Furthermore, all results produced by the application must be transmitted to this resource. Thus, new vertices and edges are added to the task graph $T G$ to model these data dependencies.

Figure 5 depicts a sample of seven tasks with eight precedence relation among them. To start processing tasks $t_{1}$ and $t_{2}$ , first $t_{0}$ must be completed. Also, execution of $t_{3}$ and $t_{4}$ depends on completion of $t_{1}$ and execution of $t_{5}$ depends on completion of $t_{2}$ . At the end, $t_{6}$ cannot be started unless all $t_{3}$ , $t_{4}$ and $t_{5}$ are completely done.

Figure 5.

Sample of tasks with precedence relation.

Supposing that task $t_{i}\in T$ is assigned to machine $m_{j}\in M$ for execution with non-preemptive approach. The heuristic task scheduling ${Ts}_{i,j}$ is defined as the completion time or compile time of task $t_{i}$ , which has been developed to allocate a DAG-structure application to a set of heterogeneous machines to minimize the execution time of the application and is composed of three parts: first; determine the importance or priority of the task in the precedence hierarchy, second; identify the fastest idle machine for execution task $t_{i}$ and third; specify the starting time of task $t_{i}$ on machine $m_{j}$ . Therefore, ${Ts}_{ij}$ can be calculated as follows:

$\displaystyle{Ts}_{ij}={Sl}_{i}+\Delta\left({VM}_{i}\right)-\text{Max}\left\{{% TA}^{d}_{ij},{TA}^{m}_{ij}\right\}$ (11)

where ${Sl}_{i}$ is the static level of the task that indicates the priority by giving higher priority to tasks that the time spent to complete the execution of the application is expected to be larger. Also, $\text{Max}\left\{{TA}^{d}_{ij},{TA}^{m}_{ij}\right\}$ is the time when task $t_{i}$ can begin execution on machine $m_{j}$ so that ${TA}^{d}_{ij}$ denotes the time when the data will be available after scheduling task $t_{i}$ on machine $m_{j}$ , and ${TA}^{m}_{ij}$ is the time when machine $m_{j}$ will be available for the execution of task $t_{i}$ . Moreover, $\Delta\left({VM}_{i}\right)$ calculates the machines speed differences or in other words reflects the computing performance of the machine and is defined as follows:

$\displaystyle\Delta\left({VM}_{i}\right)={\overline{TE}}_{i,Im}-{TE}_{ij}=% \frac{L_{i}}{n}\left(\frac{1}{{Cp}_{1}}+\frac{1}{{Cp}_{2}}+\cdots+\frac{1}{{Cp% }_{n}}\right)-\frac{L_{i}}{{Cp}_{j}}=\frac{L_{i}}{n}\left(\sum^{n}_{Im=1}{% \frac{1}{{Cp}_{Im}}-\frac{n}{{Cp}_{j\in Im}}}\right)$ (12)

where ${\overline{TE}}_{i,Im}$ denotes the average execution time of the task $t_{i}$ on all the idle machines, and ${TE}_{ij}$ is the desired execution time of task $t_{i}$ on machine $m_{j}$ . Also, $L_{i}$ and ${Cp}_{j}$ denote the processing length of task $t_{i}$ and the computing capacity of machine $m_{j}$ , respectively.

It should be considered, in addition to the three factors mentioned in the scheduling algorithm, namely, priority of the task in executing, the earlier starting time, and identify the fastest idle machine, it is important to consider the trust value of resources (machines or nodes) providers. Actually when a task is scheduled to execute on a machine, the trustworthiness of the node reflects the reliability of the service it supplies. Therefore, we have developed the task scheduling mechanism based on trust model (TSTM) in grid environment and can be defined as follows:

$\displaystyle\textit{TSTM}_{ij}=Td_{ij}\times{Ts}_{ij}$ (13)

where $Td_{ij}=\sum^{n}_{g=1}{w_{g}\times Td^{g}_{ij}}$ represents the total trust value in all context between trustor $n_{i}$ as owner of task $t_{i}$ and trustee $n_{j}$ as provider of resource or machine $m_{j}$ . where $Td^{g}_{ij}$ represents the total trust value in each context $c_{g}$ between trustor $n i$ and trustee $n j$ and $w_{g}$ is the weight of the context $c_{g}$ so that the sum of weights is equal to one which is assigned by trustor $n i$ according to the importance of the context $c_{g}$ . Also, ${Ts}_{ij}$ denotes the heuristic task scheduling between task $t_{i}$ and machine $m_{j}$ .

3.3 Trusted scheduling framework

Trusted scheduling algorithm can be implemented as a middleware to plug into the gird environment, which the tasks can be executed on trust nodes efficiently. On one hand, the ratio of failure task execution is reduced and on the other hand, the security of data executive environment is improved. In this section, a basic integrated framework based on TSTM is presented.

In grid environment, the user nodes can enroll the grid at any time, deliver requests to the schedule center, and monitor the implementation of themselves’ tasks. The framework of task scheduling and resource allocation is shown in Fig. 6. In the trust scheduling based our TSTM framework, the whole process of the task submission and execution is in the following steps:

Figure 6.

Proposed task scheduling mechanism based on trust model (TSTM) framework.

Step 1.

The user delivers a request (such as Information services, network services, security services, storage services, etc.) to the Request Service as task pool.

Step 2.

Task Submission exploits and classifies the tasks according to the requested services and the execution time. Task Submission not only divides and classifies tasks but also manages them relating to their nature and required services. This component considers all aspects of a task, including its status, priority, requested time, and requested resource. Also, it is responsible for processing a task and submitting the created tasks to the task queues. After dividing and classifying the user request, Task Submission submits the task to the Task Scheduler.

Step 3.

Task Scheduler is the most important component of grid that allocates a set of tasks which are received from Task Submission to the appropriate resources based on our proposed task scheduling mechanism as mention in Sub-section 3.2 as well as communicates with the Schedule Advisor. The main purpose of Task Scheduler is to shorten the response time to users and enhance the resource utilization to increase organization efficiency.

Step 4.

The Schedule Advisor communicates with the trust management middleware and obtains the trust value of resources based on their previous execution of tasks as historical transaction, and transfers them to both Task Scheduler and Task Dispatcher.

Step 5.

Task Dispatcher delivers the task to the selected resource mapped task for execution, and gives transfer delay and actual task assignment result to the Resource Monitor. The Task Dispatcher maintains a scheduled task queue, when some task is finished or failed, the dispatcher delete the task in the queue or put the task back to unscheduled task queue, and notifies the resource monitor.

Step 6.

The Resource Monitor maintains the up to date state of every resource (all kinds of available resources such as computing, data, storage, network, software, etc.) and discovers the resources available and send resources status to Task Scheduler.

Step 7.

The task can be executed on the most trustworthy resource node in the gird.

4. Results and discussions

In this section, to demonstrate the benefits of task scheduling mechanism based on trust model (TSTM), we will present a couple of illustrative examples plus empirical evaluations of the model according to the parameters set them. Also we have tried to show the differences of the proposed model with the commonly used classical models and illustrate what the proposed model can bring to the computational grid domain. Hence, in the following section, we first discuss the effect of our proposed task scheduling mechanism based on trust model (TSTM), and then we compared the TSTM with other models.

4.1 Results for the proposed task scheduling mechanism (TSTM)

In this section, In order to evaluate the proposed algorithms, a simulation program that can be used to emulate the execution of randomly created or real application task graphs on a simulated computing system was developed. Hence, in the following section, we first consider a small-scale scheduling scenario to understand the simulation process more clearly, and then we have verified our proposed task scheduling mechanism (TSTM) by comparing our algorithm with others such as TDL (trusted dynamic level scheduling) model [43] and give systematic analysis on how our proposed model can enhance the task scheduling process.

Therefore, assume that the gathered data from information sources such as task user and grid services providers are as shown in Tables 1–3. In this scenario, we consider 5 task users and 3 machines so that 10 tasks are submitted to the machines and the length of each task is considered as a random number within the range of [1, 15] that shown in Table 1. Also, the initial trust value between task users and machines nodes are generated randomly that shown in Table 2. Moreover, Table 3 shows the execution time of each task of task graph.

Table 1
Configuration parameters

Task	Task user	Priority	Task length
1	1	1	10
2	1	1	13
3	1	2	5
4	2	3	6
5	2	4	8
6	3	1	11
7	4	2	15
8	5	2	4
9	5	3	5
10	5	5	9

Table 2

Initial trust value between task users and machines nodes

Task user	Machine 1	Machine 2	Machine 3
1	0.67	0.34	0.88
2	0.7	0.56	0.81
3	0.55	0.48	0.79
4	0.59	0.55	0.79
5	0.6	0.44	0.75

Table 3

Execution time of each task

Task	Machine 1	Machine 2	Machine 3
1	13.33	20	16.66
2	17.33	26	21.66
3	6.66	10	8.33
4	8	12	10
5	10.66	16	13.33
6	14.66	22	18.33
7	20	30	25
8	5.33	8	6.66
9	6.66	10	8.33
10	12	18	15

Figure 7.

Comparison of the amount of task scheduling.

Figure 8.

Comparison of task scheduling mechanism based on trust model (TSTM).

Figures 7 and 8 show the amount of task scheduling and task scheduling mechanism based on trust model according to equations 11 and 13, respectively. As shown in Figs 7 and 8, the TSTM values have been reduced compared with TS values due to the direct impact of trust value on scheduling. In other words, in TSTM, there is a direct relationship between the task scheduling and the value of trust between the task users and the machines. For example, as shown in Table 2, the machine 3 has a higher trust value between task users, hence the TSTM value for this machine is higher than others and therefore has a higher priority to execute the tasks.

In another experiment, we evaluated the makespan that is an important performance criterion of scheduling heuristics in grid computing systems. It is defined as the maximum completion time of application tasks executed on grid resources. Simulation result of this experiment is shown in Fig. 9. Also, Figs 10 and 11 show the starting time and the execution time of different tasks according Table 1.

Figure 9.

Comparison of final completion time (makespan) of different tasks based on Table 1.

Figure 10.

Comparison of starting time of different tasks based on Table 1.

Figure 11.

Comparison of execution time of different tasks based on Table 1.

4.2 Evaluation and comparison among trust models

An important application of the proposed task scheduling mechanism based on trust model (TSTM) is to facilitate comparison among different task scheduling mechanisms. There are some task scheduling mechanisms proposed for grid environment, so, it is difficult to list all task scheduling mechanisms to compare with each other. Therefore, we make a comparison with two task scheduling mechanisms, i.e., TDL (trusted dynamic level scheduling) [43] and proposed model without considering trust, i.e., TS (task scheduling without considering trust).

Figure 12.

Comparison of average scheduling length under varying number of tasks. TSTM: task scheduling mechanism based on trust model, TDL: trusted dynamic level scheduling, TS: task scheduling without considering trust.

Figure 13.

Comparison of average scheduling length under varying number of machines.

Figure 14.

Comparison of final completion time under varying number of tasks.

Figure 15.

Comparison of final completion time under varying number of machines.

The schedule length is one of important factor for evaluation of the task scheduling mechanisms. Therefore, we compare the average scheduling length of TSTM with TDL and TS under varying number of tasks and varying number of machines. Figures 12 and 13 show the average scheduling length under varying number of tasks and varying number of machines, respectively. In first simulation experiment, task graph with 10 to 100 tasks is generated, and the number of machine nodes set to 30. Also, in second simulation, we consider the number of machine nodes from 10 to 60, and the number of tasks is set to 100.

Experiment results as depicted in Fig. 12 show that with the increasing the number of tasks, the average scheduling length of the three algorithms also increases. The average scheduling length at the beginning of the simulation – when the number of tasks is low – in three algorithms is almost equal to each other, but with increasing the number of tasks, the average scheduling length of TSTM is little more than TS, due to the calculation of trust value, but it little less than TDL. Also, as shown in Fig. 13, the number of machines has an inverse relationship with the average scheduling length, so that with the increasing the number of machines, the average scheduling length decreases. The simulation results indicate that TSTM has a better status than TDL. However, because of calculating the trust value between task users and machine nodes, the average scheduling length is slightly more than TS.

As mention above, makespan is an important performance criterion of scheduling heuristics in grid computing systems. The comparison experiments’ result about final completion time is shown in Figs 14 and 15 under varying number of tasks and varying number of machines, respectively.

The result indicates that (TSTM shortes the final completion time compared to the model TS which does not load trust model and also TDL. TDL try to shorten the execution time of tasks on the path by assigning them to the shortest execution time resources. But it ignores resources’ integrity which possibly leads to the result that tasks are sent to resources that needed to re-scheduling. So the final completion time is postponed. While our model took into account the trust included comprehensive performance of the candidate resources in the tasks’ scheduling process and the probability of failure scheduling is low.

5. Conclusion and future work

In this paper, we model the problem of task scheduling to decrease the failure probability of the task assignments, and improve the trustworthiness of execution environment while minimizing both execution time and makespan. A new task scheduling mechanism based on Trust Model named (TSTM) is proposed in grid environments so that we first calculate the trust value between task users and resource providers according to success and failure transaction between them and then we compute task scheduling based on trust value. We also proposed the framework of task scheduling and resource allocation. Moreover we compared it with other two algorithms. The experimental results show that the TSTM algorithm can achieve better solutions than other ones and also can be effective in selecting secured resource for task execution from the available ones.

Future studies in this research can be performed in the following directions. First, considering other aspects of security in grid environment such as the probability failure of links and security software deployed in the nodes. Second, task scheduling algorithms with optimization objectives such as cost and minimizing energy consumption will be considered.

Footnotes

Author’s Bios

	Ali Mohsenzadeh received his B.S. degree in Computer Engineering and M.S. degree Information Technology from Mazandaran University of science and Technology in 2012 and 2014, respectively. Currently he is Ph.D. candidate in management information system (MIS). His research interests and papers are mostly in the areas of Evolution Algorithms, Distributed Computing, Software Security, DLT, Blockchain and Petri Net.
	Mohsen Nickray received the B.S. and M.S. degree in computer engineering from Iran University of Science and Technology and University of Tehran in 2004, 2007, and Ph.D. degree computer architecture at University of Tehran respectively in 2012. Currently, he is an assistant professor in Department of Computer Engineering and Information Technology University of Qom, Iran. His recent research interests include resource management and task scheduling in Cloud and Fog computing.
	Amir Jalaly Bidgoly is currently an Assistant Professor at the Department of Computer Engineering, University of Qom. He received M.S. degree in Computer Engineering from Iran University of science and Technology 2009. He received Ph.D. degrees in Computer Engineering from University of Isfahan 2015, respectively. He is the head of APA Cert/SOC research center of Qom province, Iran. His current research interests include Computer Security, Soft (social) Security, Modelling, Simulation and Verification.
	Yaghoub Farjami is an associate professor of computer science and information technology at University of Qom. He received B.Sc., M.Sc., and Ph.D. degrees in Mathematics from Sharif University of Technology in 1992, 1994 and 1998 respectively. Dr. Farjami’s current research interests include computational and nonlinear mathematical models in engineering, information security protocols, performance analysis of distributed systems, and the applications of Artificial Intelligence and big data to Engineering and Quality control. He is the co-author of serval books on BI, IoT, security, big data, and BI, all in Persian.

References

Ranaldo

and Zimeo

, A framework for qos-based resource brokering in grid computing, Emerging Web Services Technology 2 (2008), 159–170.

Kołodziej

and Xhafa

, Meeting security and user behavior requirements in grid scheduling, Simulation Modelling Practice and Theory 19 (2011), 213–226.

Foster

Kesselman

and Tuecke

, The anatomy of the grid: Enabling scalable virtual organizations, Internat J Supercomp Appl 15(3) (2001), 200–222.

Foster

and Kesselman

, Globus: A metacomputing infrastructure toolkit, Internat J Supercomp Appl 11(2) (1997), 115–128.

El-Rewini

Lewis

T.G.

and Ali

H.H.

, Task Scheduling in Parallel and Distributed System, Englewood Cliffs, New Jersey: Prentice Hall, 1994, 401–403.

Iverson

and Ozguner

, Dynamic competitive scheduling of multiple DAGs in a distributed heterogeneous environment, in: Proceedings of the Seventh Heterogeneous Computing Workshop, Orland: IEEE Computer Society Press, Mar 1998, pp. 70–78.

Iverson

and Ozguner

, Hierarchical, competitive scheduling of multiple DAGs in a dynamic heterogeneous environment, Distributed Systems Engineering 6(3) (1999), 112–120.

Boeres

Lima

and Rebello

V.E.

, Hybrid task scheduling: Integrating static and dynamic heuristics, in: Proceedings of the 15𝑡ℎ Symposium on Computer Architecture and High Performance Computing (SBAC-PAD’03), Brazil: IEEE Computer Society, 2003, pp. 199–206.

Dogan

and Ozguner

, Reliable matching and scheduling of precedence-constrained tasks in heterogeneous distributed computing, in: Proceedings of the 29𝑡ℎ International Conference on Parallel Processing, Toronto, Canada: IEEE Computer Society, 2000, pp. 307–314.

10.

Dogan

and Ozguner

, Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing, IEEE Trans Parallel Distrib Syst 13(3) (2002), 308–323.

11.

Berman

Wolski

Casanova

Cirne

Dail

Faerman

Figueira

Hayes

Obertelli

Schopf

Shao

Smallen

Spring

and Zagorodnov

, Adaptive computing on the grid using AppLeS, IEEE Trans. on Parallel and Distributed Systems 14(4) (2003), 369–382.

12.

Welch

Siebenlist

Foster

Bresnahan

Czajkowski

Gawor

Kesselman

Meder

Pearlman

and Tuecke

, Security for Grid Services, in: High Performance Distributed Computing, Proceedings, 12𝑡ℎ IEEE International Symposium on, Jun 2003, pp. 48–57.

13.

Foster

Zhao

Raicu

and Lu

, Cloud Computing and Grid Computing 360-Degree Compared, in: IEEE Grid Computing Environments Workshop, Nov 2008, pp. 1–10.

14.

Lohr

Ramasamy

H.V.

Sadeghi

A.R.

Schulz

Schunter

and Stuble

, Enhancing Grid Security Using Trusted Virtualization, Lecture Notes in Computer Science, Jul 2007, 372–384.

15.

Dyson

J.R.

Griffiths

N.E.

Keung

L.C.

Jarvis

S.A.

and Nudd

G.R.

, Trusting Agents for Grid Computing, in: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Vol. 4, 2004, pp. 3187–3192.

16.

Vijayakumar

and Banu

R.S.D.W.

, Security for resource selection in grid computing based on trust and reputation responsiveness, International Journal of Computer Science and Network Security 8(11) (2008), 107–115.

17.

Humphrey

and Thompson

M.R.

, Security implications of typical grid computing usage scenarios, Cluster Computing 5(3) (2002), 257–264.

18.

Kashyap

and Vidyarth

, Security driven scheduling model for computational grid using NSGA-II, Journal of Grid Computing 11 (2013), 721–734.

19.

Ali

Siegel

H.J.

Maheswaran

and Hensgen

, Task execution time modeling for heterogeneous computing systems, in: Proceedings 9𝑡ℎ Heterogeneous Computing Workshop, 2000, pp. 185–199.

20.

Braun

T.D.

Siegel

H.J.

Beck

Boloni

L.L.

Maheswaran

Reuther

A.I.

Robertson

J.P.

Theys

M.D.

Yao

Hensgen

and Freund

R.F.

, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing 61(6) (2001), 810–837.

21.

Xhafa

Carretero

and Abraham

, Genetic algorithm based schedulers for grid computing systems, International Journal of Innovative Computing, Information and Control 3(5) (2007), 1053–1071.

22.

Z.J.

J.D.

C.Y.

Yang

H.J.

H.Y.

Luo

and Chang

, Energy cost minimization with job security guarantee in internet data center, Future Generation Computer Systems 73 (2017), 63–78.

23.

Xie

and Qin

, Scheduling security-critical real-time applications on cluster, IEEE Transactions on Computers 55(7) (2006), 864–879.

24.

Ashtiani

and Abdollahi Azgomi

, A formulation of computational trust based on quantum decision theory, Information Systems Frontiers 18(4) (2016), 735–764.

25.

Mohsenzadeh

, Software security modeling based on petri nets, Journal of Mathematics and Computer Science 15(1) (2015), 70–77.

26.

Lin

Varadharajan

Wang

and Pruthi

, Enhancing Grid Security with Trust Management, in: IEEE International Conference on Services Computing, 2004, pp. 303–310.

27.

and Sun

, An integrated security-aware job scheduling strategy for large-scale computational grids, Future Generation Computer Systems 26(2) (2010), 198–206.

28.

Wang

Ramamohanarao

and Chen

, Trust-based robust scheduling and runtime adaptation of scientific workflow, Concurrency and Computation: Practice and Experience 21 (2009), 1982–1998.

29.

Wang

Zeng

Tang

and Yao

, Cloud-DLS: Dynamic trusted scheduling for cloud computing, Expert Systems with Applications 39(3) (2012), 2321–2329.

30.

Tang

Zeng

and Veeravalli

, A novel security-driven scheduling algorithm for precedence constrained tasks in heterogeneous distributed systems, IEEE Transactions on Computers 60(7) (2011), 1017–1029.

31.

Azzedin

and Maheswaran

, Integrating Trust into Grid Resource Management Systems, in: Proceedings International Conference on Parallel Processing, 2002, pp. 47–54.

32.

Azzedin

and Maheswaran

, A Trust Brokering System and Its Application to Resource Management in Public-Resource Grids, in: Proceedings 18𝑡ℎ IEEE International Parallel and Distributed Processing Symposium, 2004.

33.

Mohsenzadeh

and Motameni

, A trust model between cloud entities using fuzzy mathematics, Journal of Intelligent & Fuzzy Systems 29(5) (2015), 1795–1803.

34.

Mohsenzadeh

Motameni

and Meng

J.E.

, A new trust evaluation algorithm between cloud entities based on fuzzy mathematics, International Journal of Fuzzy Systems 18(4) (2016), 659–672.

35.

Sun

Chang

Sun

and Wang

, A dynamic multi-dimensional trust evaluation model to enhance security of cloud computing environments, International Journal of Innovative Computing and Applications 3(4) (2011), 200–212.

36.

Kovac

and Trcek

, Qualitative trust modeling in SOA, Journal of Systems Architecture 55(4) (2009), 255–263.

37.

Liao

Wang

and Li

, A Fuzzy Logic-based Trust Model in Grid, in: International Conference on Networks Security, Wireless Communications and Trusted Computing, 2009, pp. 608–614.

38.

Jøsang

and Ismail

, The Beta Reputation System, in: 15𝑡ℎ Bled Electronic Commerce Conference eReality: Constructing the eEconomy, Bled, Slovenia, 2002, pp. 324–337.

39.

Griffiths

Chao

K.M.

and Younas

, Fuzzy trust for peer-to-peer systems, in: 26𝑡ℎ IEEE International Conference on Distributed Computing Systems Workshops, July 2006, pp. 73–73.

40.

Luo

Liu

and Fan

, A trust model based on fuzzy recommendation for mobile adhoc networks, Journal of Computer Networks 53(14) (2009), 2396–2407.

41.

Sarwar

Karypis

Konstan

and Riedl

, Item-Based Collaborative Filtering Recommendation Algorithms, in: Proceedings of the ACM 10𝑡ℎ International Conference on World Wide Web, 2001, pp. 285–295.

42.

Zadeh

L.A.

, Fuzzy sets, Information and Control 8(3) (1965), 338–353.

43.

Wei

and GuoSun

, Trusted dynamic level scheduling based on bayes trust model, Science in China Series F: Information Sciences 50(3) (2007), 456–469.

44.

Kundu

, The min-max composition rule and its superiority over the usual max-min composition rule, Fuzzy Sets and Systems 93(3) (1998), 319–329.

A new task scheduling mechanism in grid computing using trust model

Abstract

Keywords

1. Introduction

3. Proposed trust-based task scheduling mechanism

4.1 Results for the proposed task scheduling mechanism (TSTM)

Table 1 Configuration parameters

Footnotes

Author’s Bios

References

Table 1
Configuration parameters