Distributed Dynamic Load Balancing in P2P Grid Systems - Cloud, Grid and High Performance Computing: Emerging Applications - page 294

Table 2. The status of grid sites

Local site's status Neighbor site's status

RL status AL status

High High Sendable Unreceivable

High Moderate Sendable Unreceivable

High Low Sendable Unreceivable

Moderate High Sendable Unreceivable

Moderate Moderate UnSendable Receivable

Moderate Low UnSendable Receivable

Low High Sendable Unreceivable

Low Moderate UnSendable Receivable

Low Low UnSendable Receivable

or “Unsendable”, and the status of its neighbor
sites to be “Receivable” or “Unreceivable”. In
order to further improve the load balancing per-
formance, we refine the definition of the status
set. As long as the status of one of RL or AL is
“High”, the grid site becomes “Sendable”. More-
over, when the status of only one of RL or AL is
“High”, the grid site becomes “Unreceivable”.
When a grid site becomes “Sendable”, it means
that the grid site is overloaded. Therefore, the
sendable site starts to pick out its neighbors which
are “Receivable”, and enables the job migration
phase. The statuses of different combinations in
gird sites are shown in table 2.

assume that the number of CPU in the site s is N CPU .
Then, the forecasted waiting time is defined as

T T
N CPU

+

(4)

r i

T w =

T e is the executing time of job J in the site s . T m
is the migration time of job J which is migrated
from the local site to the destination site. The
migration involves the job's program code and
some required data files. Thus,

The size of program code file and data file
The bandwidth between the local site and destination site
(5)

T m =

Job Migration Phase

Denoting the job turnaround time by T jt , then

In the job migration phase, the sendable site cal-
culates the possible job turnaround time for each
receivable neighbor site if this neighbor site is the
candidate site. And then, the job is migrated to the
neighbor site which has the minimal job turnaround
time. The job turnaround time is the sum of the
forecasted waiting time, the execution time and the
migration time which are respectively denoted by
T w , T e , and T m . T w is the forecasted waiting time of
the migrated job J in the destination site s . SALB
forecasts the total remaining execution time, T r ,
of the running jobs and the total execution time,
T i , of the idle jobs in the destination site s . Then,

T jt = T w + T e + T m . (6)

Figure 6 shows the algorithm of SALB. Each
grid site changes their neighbors periodically to
improve the global load balancing. In addition, due
to that SALB applies the sender-initiated strategy,
only when the grid site becomes “Sendable”, the
load balancing policy is enabled. The sendable site
picks out the neighbors which are “Receivable”
according to the statuses of RL and AL . Then, the
neighbor's job turnaround time ( T jt ) is calculated
and the neighbor which has the minimal job turn-