A Security Prioritized Computational Grid Scheduling Model - Cloud, Grid and High Performance Computing: Emerging Applications - page 94

networked system, has its own local jobs; i.e. it
cannot provide exclusive services to remote jobs.
Hence, scheduling algorithms need to address the
performance measures of the jobs on non-dedi-
cated network in the presence of multiple users.
Due to security heterogeneity, jobs that are
dispatched to a remote site can possibly experi-
ence security and reliability problems. Scheduled
grid tasks may have its security demand (SD) and
the grid site offers a certain security level (SL).
If security demand of the job (multiple tasks) is
not met by the resource on which it is made to
execute, the job may fail and is to be rescheduled
on some other resources.
A security-aware scheduling algorithm need
to satisfy the security constraints and at the same
time has to optimize the performance parameters
like site utilization (percentage of total task run-
ning time out of total available time on a given
site), makespan (completion time of the entire job
set), average response time (average value of all
tasks' response time), average slowdown ratio
(ratio of the task's response time to its service
time).Therefore, multi-objective criteria have to
be met. Some of the grids scheduling algorithms
are discussed below. All these algorithms need
prediction information on processor speed and
the task length.

processor speed. However RR does not
consider security requirements.
• MinMin: gives highest priority to the task
that can be completed first. In this, for each
task the grid site that offers the earliest
completion time is tagged and the task that
has the minimum earliest completion time
is allocated to the respective node. MinMin
executes shorter task in parallel whereas
longer task follows the shorter one (Freund
et al., 1998).
• MaxMin: here the grid site that offers ear-
liest completion time is tagged. Highest
priority is given to the task with maximum
earliest completion time. The idea behind
max-min is overlapping long running task
with short running ones. MaxMin executes
many shorter tasks in parallel with the lon-
ger one (Freund et al., 1998).

MinMin and MaxMin are used in real world
distributed resource management systems such as
SmartNet (Freund et al., 1998). Both have time
complexities of (mn 2 ) where m is the number of
machines at the site and n is the number of tasks
to schedule. They are suitable when the tasks to
schedule are independent and compute intensive.

• SATS , suggested by Xie and Qin (2007),
takes into account heterogeneities in secu-
rity and computation. It provides a means
of measuring overhead incurred by secu-
rity services and quantitatively measuring
quality of service (QoS) but it does not
assure the desired security rather try to
improve security and minimize computa-
tional overhead.
• MinMin (Secure, Risky) (Song, Kwok
and Hwang; 2005), are secured version
of MinMin. Secure mode allocates task to
those sites that can definitely satisfy the
security requirements. Risky mode allo-
cates tasks to any available grid site and
thus takes all possible risks at the resource

• DFPLTF: (Dynamic Fastest Processor to
Largest Task First) gives the highest pri-
ority to the largest task but is not a secu-
rity aware algorithm (Paranhos, Cirne and
Brasileiro; 2003).
• Suffer: (Casonova, Legrand, Zagorodnov
and Berman; 2000) allocates the processor
to the task that would suffer the most if that
processor is not assigned to it.
• Round Robin: (RR) proposed by Noriyuki
Fujimoto and Kenichi Hagihara (2003) grid
scheduling algorithm for parameter sweep
applications which does not require predic-
tion information regarding task length and