Measures of the Potential for Load Sharing in Distributed Computing Systems.
In this paper we are concerned with the problem of determining the potential for load balancing in a distributed computing system. We define a precise measure, called the Number of Sharable Jobs, of this potential in terms of the number of jobs that can usefully be transferred across sites in the system. Properties of this measure are derived, including a general formula for its probability distribution, independent of any particular queuing discipline. A normalized version of the number of sharable jobs, called the Job Sharing Coefficient, is defined. From the general formula, the probability distribution of the number of sharable jobs is computed for three important queuing models and exact expressions are derived in two cases. For queuing models in which an exact expression for the probability distribution of the number of sharable jobs is difficult to obtain, two methods are presented for numerical computation of this distribution. The job sharing coefficient is plotted against traffic intensity for various values of system parameters. Both of these measures are shown to be useful analytic tools for understanding the characteristics of load sharing in distributed systems and can aid in the design of such systsems.
Introduction
In a distributed system, statistical fluctuations in arrival and service patterns across the various
sites cause imbalances in load where one or more sites may be operating much below capacity
and others may simultaneously be overloaded. Livny and Melman [4] showed that in a
distributed system consisting of homogeneous sites, there is a high probability that a site is idle
while jobs are queued up for service at another. Thus improvement in overall system
performance can be achieved by moving jobs from overloaded to underloaded sites, a process
called load-sharing or load-balancing. Over the last several years, a number of load balancing
algorithms has been proposed. Shivaratri, Krueger, and Singhal [8] provide a survey and
taxonomy of load sharing algorithms. Recently, Rommel [6] extended the Livny-Melman
result for a generalized definition of overloaded and underloaded sites and computed the
probability that at least one site is overloaded while at least one other site is underloaded, for
several service time distributions. This probability is called the Probability of Load Balancing
Success (PLBS).
However, these results do not quantify the potential to which load distribution is possible in a
distributed system because the PLBS does not give any indication of the amount of
simultaneous overload and underload present in the system. For example, Rommel's results are
concerned only with the probability of at least one site being overloaded while at least one
other is underloaded. They do not offer insight into the average number of jobs that can be
profitably transferred by a load sharing algorithm. Such information is clearly useful to
system designers, enabling them to predict accurately the potential number of jobs that can be
transferred to improve overall system performance.
In this paper, we quantify the potential for load distribution in distributed systems in terms of
the number of jobs that can potentially be transferred to balance the load across all sites. We
do this by deriving a general formula for the probability distribution of the number of jobs
which can be usefully transferred across sites in a distributed system. The mean of this
random variable is computed as a function of system load and plotted for a number of queuing
models. It is shown that Rommel's results constitute a special case of this general distribution.
A normalized measure for the potential for load sharing is defined and shown to provide useful
insights in determining the potential for load sharing.
2. Model
We consider a homogeneous distributed computing system consisting of N independent CPUs
each with local memory. Sites, denoted S i , 1  i  N, communicate with each other by
message passing over a communications network. Jobs arrive at each site from the outside
world in independent streams, are processed, and sent out. Each site can be modeled as a
queuing system, such as M/M/1, M/D/1, etc. For the moment, we do not assume any particular
queuing model. The job arrival rate is denoted as l and the rate at which each CPU processes
jobs is denoted as . The ratio l / is denoted r and is called the traffic intensity. The queue
size at each node is a continuous time stochastic process denoted as {Q i (t), t  0} where 1 i
N. For clarity, we shall drop the time variable and refer to the instantaneous random variable
in the following.
Due to statistical fluctuations in arrival and service times, Q i varies over time between 0 and
an arbitrarily large number. If Q i is large at a given time then the site S i clearly is faced with
a large backlog of work. On the other hand if Q i is small, or zero, then S i is lightly loaded.
These notions are quantified by selecting two integers L and H, 0 < L < H, and by the
following definitions. The integers L and H are system parameters set by system designers
based upon the speed of the CPUs comprising the distributed system, as well as anticipated job
arrival patterns.
2.1 Definitions
Definition 1: A site S i is underloaded , denoted as UL, if Q i < L.
Definition 2: A site S i is overloaded , denoted as OL, if
Definition 3: A site S i is normal , denoted as NL, if L  Q i  H.
Definition 4: The probability of underload , which is the same for all i, 1  i  N, (due to the
assumption of homogeneity of sites) is the probability that a site is underloaded
Definition 5: The probability of overload , which is the same for all i, 1  i  N, (due to the
assumption of homogeneity of sites) is the probability that a site is overloaded.
Definition the amount of underload at a site is the random variable defined
as
Definition 7: For 1  i  N the amount of overload at a site is the random variable defined as
A i and B i can be interpreted as the extent of underload and overload, respectively at the site
S i is the number of jobs that S i can receive before becoming normal, i.e., ineligible for
receiving transferred jobs. Similarly B i represents the number of jobs that must be transferred
from S i to make it attain normality. Clearly, the sum of A i over all i, 1  i  N, is the total
amount of underload in the system The sum of B i over all i, 1  i  N, represents the total
amount of overload in the system. These two sums are defined below.
Definition 8: The total underload in the system is the random variable
Definition 9: The total overload in the system is the random variable
Definition 10: The number of underloaded sites in the system, denoted as N UL , is defined as
Definition 11: The number of overloaded sites in the system, denoted as N OL , is defined as
2.2 A Measure of the Potential for Load Sharing
It is natural to attempt optimization of overall system performance by transferring jobs from
overloaded sites to underloaded ones. Normal and overloaded sites are not candidates to
receive transferred jobs. If site S i is overloaded, then to completely alleviate the overload, the
number of jobs that must be transferred out of S i is This is the number of jobs that
can potentially be transferred from S i to other sites in the system. However, only sites which
are currently underloaded can accept these jobs. If S k is an underloaded site, then it can accept
at most L - Q k jobs since accepting more would make it a normal (or overloaded) site. Thus, it
is quite possible that the total number of jobs that can feasibly be transferred from S i is not
the same as Q
Extrapolating the above reasoning from a single site to the entire system we see that the total
number of jobs that can be transferred, when the system has at least one overloaded site, is a
random variable whose value depends upon the number of underloaded sites at that time, as
well as the queue sizes at these sites. In the following, we shall give a rigorous definition of
this random variable, denoted G, and derive a number of its properties. It is worth noting that
our analysis is independent of any particular load sharing algorithm and the method below can
be extended to general definitions of overload, underload, and normality. The only major
assumption in our model, apart from homogeneity, is that a site can be in only one state -
underloaded, overloaded or Normal - at any one time.
Definition 12: The number of sharable jobs in the system is the random variable,
The expectation of the number of sharable jobs will be denoted EG
From Definitions 6 - 12 it is clear that the Number of Sharable Jobs is a function of N, L, H, r,
and the queuing model of each of the computing sites comprising the distributed system. A
related measure of the potential for job transfer is the following.
Definition 13: Let EQ denote the expectation of the queue size random variable at each of the
sites in the distributed system. The job sharing coefficient of the system, denoted J c , is the
constant:
The job sharing coefficient is a constant which measures the mean number of sharable jobs as a
fraction of the mean number of jobs in the system. Since the number of sharable jobs is always
less than the total number of jobs in the system it follows that 0  J c  1. J c is a function of N,
L, H, r, and the queuing model of a site in the system.
J c is computed as follows: First obtain EQ from the probability distribution of the queue size
in the queuing model at each site. Second, compute the distribution of G using methods
described in the following. Third, calculate EG from the distribution of G. Finally compute
the ratio in Definition 13. For most of the common queuing models, EQ is already available in
the literature. Thus, the hard part in calculating J c will usually be computing the distribution of
G and subsequently EG. Therefore, in the rest of this paper we study G in detail and derive its
important properties, including a general formula for its probability distribution.
2.3 Interpretations
Both EG and J c have useful interpretations. For systems designers, J c provides a normalized
basis for comparing one system to another, or for comparing the same system operating under
different values of parameters such as N, L, etc. Using the methods described in the rest of this
paper, systems designers can compute J c for different values of these parameters as well as for
different queuing models and select the most suitable configuration with respect to their needs.
Thus J c can be used as a design tool. Large values of J c indicate a large potential for load
sharing.
Once a set of systems parameters has been decided upon, the implementers of the system can
use EG to predict the mean number of jobs in the system due to load sharing. EG can also be
used to estimate the amount of message passing and data transfer that the communications
network would be called upon in order to handle the needs of load sharing.
We note also that G is an upper bound on the number of jobs that can be shared among the sites
in the system. This implies an upper bound on the improvement in system performance by
load sharing at any given time. EG is the mean of the maximum number of sharable jobs. On
the average, the best improvement in system performance due to load sharing is bounded by
functions of EG depending on the performance measure in question. These bounds are
currently being researched by the authors.
3. Analysis
We begin by stating a number of observations.
Observation 1: At any given time, a site can only be in one state, normal, underloaded, or
overloaded.
This follows from 0 < L < H and Definition 1 - Definition 3.
Observation 2: The tuple of random variables (N UL , NOL ) is distributed according to a
Trinomial distribution with parameters (N, P UL , P OL ).
This is obtained from Observation 1, Definitions 9 - 12, and the independence of the
sites.
Observation 3: For any i, 1  i  N, A i > 0 =>
Observation 4: For any i, 1  i  N,
Observations 4 and 5 follow from 0 < L < H, and Definitions 6 and 7 .
Observation 5: If all sites are normal or underloaded then
Observation are normal or overloaded then
If all sites are normal, then for all i, 1  i  N, A This means that TUL
9. Hence, from Definition 12 it follows that
are normal and the others are underloaded then T
Similarly, if some sites are normal and all the others are overloaded,
then
Observation 7: G > 0 if and only if there exists at least one underloaded site and one
overloaded site simultaneously, i.e., if and only if NUL > 0 and N OL > 0.
Observation 7 follows from Definition 12 which says that G > 0 if and only if both T UL
> 0 and TOL > 0. This can happen if and only if NUL > 0 and N OL > 0.
Observation 8: 0  G  (N-1)L.
To see this we note that from Definition 6, 0  A i  L, for all i, 1  i  N. From
N*L. The event T would occur if and only if Q
N. But from Observation 7 we must have H for at least one i to have G > 0.
Hence G attains its maximum when all sites except one have queue sizes equal to 0 and the
queue size at the single overloaded site is at least (N-1)L.
Observation 9:
This is clear from Observation 8 above.
From these observations, we see that if there are no underloaded sites then all sites are either
overloaded or normal and it is useless to attempt job transfer. In this case G = 0. On the other
hand, if there are no overloaded sites then all sites are either normal or underloaded so job
transfer is unnecessary. In this case also, we have represents the maximum
number of jobs that can be usefully transferred in the system. There is no point in trying to
transfer a greater number of jobs than G because there will not be any underloaded sites
available to accept these excess jobs.
In [6] Rommel computes the probability that G > 0, and calls it the Probability of Load
Balancing Success(PLBS). Here we shall derive a general expression for the distribution of
G. This expression gives much better insight into the potential for load balancing.
Theorem 1
The probability distribution of G is given by the following expression.
a)
For
N-I
I P OL
I
Where R i and S j are random variables defined as follows.
For all i, 1  i  N,
Proof:
From Observation 3.6 we see that
It follows that
0}- P{N UL
From Definitions 2.8 through Definition 2.10 we obtain
b) From Definition 12, for 1  k  (N-1)L, we obtain the following expression, using the total
probability law and Observation 7.
k and T OL
k}
N-I
k and (N
For fixed I and J, using Definition 6 and Definition 7, we can rewrite the summand above as
P{ A i
k, and (I sites are UL, J sites are OL)}
k and I sites are UL) and ( B i
k and J sites are OL)}
Now, there are N!
I! J! (N - I - J)!
ways, i.e., combinations of sites, in which the event that I
sites are underloaded while J are overloaded can happen. Because the sites are homogeneous,
these are equiprobable. In each such combination we have three subsets of the N sites: the
underloaded subset, the overloaded subset, and the normal subset. By Observation 1 these
three subsets are disjoint and form a partition of all the sites. The sum of A's in the first set is
over exactly I sites, while the sum of the B's in the second set is exactly over J sites. The
queues across sites are stochastically independent and identically distributed. Hence, using
Observation 2 we can write the above probability as the following.
I! J! (N - I - J)!
P{ A i
I
(2)
We can rewrite the first probability term in (2) as follows.
P{ A i
I
I
a i =0, for 1  i  I, and a  I*L - k
I
I
I
Because the Q i are independent the probability term here is a product of I terms. Each can be
combined with one of the P UL terms in the denominator. Then, because a i < L in the above
summation, and because P definition,we obtain the following expression.
I | Q I < L}
a i =0, for 1  i  I, and a i  I*L - k
I
I
}.P{R I
a I
a =0, for 1  i  I, and a  I*L - k
I
I
is the conditional random variable, R i
| { Q i
< L}. For 1  i  I, the R i
are
independent because the Q i are independent. Hence, by combining the product probability above
into one term and rewriting the multiple summation, we obtain the following formula.
P{ A i
I
I
I . (3)
Since for x < L, {Q { the distribution of R i is as follows.
P{
for
In a similar manner, we obtain
J . (4)
Here, S j is the conditional random variable S
its probability distribution is as follows.
, for x > H
Finally, substituting (3) and (4) back into (2) and the result back into (1), we obtain the
expression in Theorem 1(b).
The above theorem is completely general in the sense that it makes no assumptions about the
nature of the queues at each of the N sites, i.e., regarding arrival and service time distributions
and service disciplines. The distributions of the conditional random variables R i and S i are
readily obtained from that of Q N. The formula in Theorem 1(b) involves the
probability distributions of terms of the form R i
I
and S j
. Each of these are sums of
independent identically distributed random variables. Hence their distributions can, in
principle, be computed using a number of methods including the well known transform
methods [3]. If exact expressions prove hard to derive, numerical methods can be used to
compute and to invert these transforms.
From Theorem 1, we can obtain the expectation of the random variable G as a finite sum. This
quantity, henceforth denoted by EG, represents the mean number of jobs that can be usefully
transferred around the system. It is a measure of the potential for load sharing or
alternatively, a measure of the wasted capacity in the system. Clearly, its behavior as a
function of system parameters N, L, H, and r is of great interest.
Note that Theorem 1(b) gives the probability distribution of G in terms of P{G  k}, for 1  k
(N-1)L. This, of course, can easily be converted into the more standard form of P{G=k} using
the following formula:
4. Computing the Distribution of G
Theorem 1 gives a general formula for computing the distribution of G in terms of expressions
derived from the probability distribution of the queue size at each site. To apply Theorem 1 to
a particular case, i.e., for a given queue size distribution such as M/D/1, M/M/1, etc., the
procedure is as follows.
1: From the probability distribution of the queue size random variable, obtain the
overload and underload probabilities, P UL and P OL .
Step 2: Using P UL and P OL compute the probability distributions of the conditional overload
and conditional underload random variables, R i and S i for 1  i  N.
Step 3: For 1  I  N, compute the probability distributions of sums of I independent instances
of each of R i and S i .
Step 4: Compute the formulas of Theorem 1(a) and Theorem 1(b) using the results of Steps 1,
2, and 3.
Generally speaking, P UL and P OL can be obtained readily. Indeed, even closed form
expressions may be derivable for many of the common queuing models. Thus the expression in
Theorem 1(a) for P{G= 0} can usually be computed without great difficulty. On the other
hand, an exact expression for P{G  k}, k > 0, in Theorem 1(b) may not always be easy to
derive. This is usually because the distributions of the sums of the overload and the underload
terms may turn out to be exceedingly complex. We now present two computational methods
for dealing with such a situation.
4.1 Method 1
Consider the terms due to underloads in Eq (2) above. Each can be written as:
I
Applying the law of total probability on the random variable Q I and using the independence of
the queues, we obtain:
< L for 1  i  I -1)}P{Q I
Thus,we have a recursive relation for q(I, k).
This recursion terminates at
I
and Q 1 < L}
I
I * L - k - x i
I
} otherwise.
Likewise, we can obtain a recursive relation for the 'overload' term in Eq (2). P{G  k} can
therefore be computed using a recursive technique. However, this method is computationally
expensive for large N because the above recursions branch out at each step.
4.2 Method 2
In the second method, we make use of transforms to compute the probability distributions of
the sums of the conditional random variables S i and R i for 1  i  N. Three transform methods
are commonly available in the context of probability distributions. These are z-transform,
Laplace Transform, and Fourier Transform (also known as the characteristic function) [3].
Here, we shall describe the use of z-transforms. The other transforms can also be used
likewise.
Given a function p n , defined on the non-negative integers, its z-transform [3] is the function
If p n is the probability distribution of a discrete non-negative random variable X, then the z-transform
of the sum of I independent instances of X is simply the Ith power of f[z]. If the
random variable X is finite, then f[z] is a polynomial of finite degree. Thus the z-transform of
the sum is also a polynomial of finite degree. The coefficients of this polynomial comprise of
the probability distribution of the sum of I independent instances of X.
From its definition (see statement of Theorem 1) we observe that each R i is a finite random
variables. The R i are independent and identically distributed. Hence, the distribution of finite
sums of the R i can be obtained exactly by computing the powers of the z-transform of R i .
The conditional random variable S i is not finite. In this case, to apply the above technique, we
are forced to make it finite by truncating S i at some integer M, such that P{S i  M} is small,
say 0.0001. The resulting probabilities for the sums of the S i are approximations, as are the
subsequent computations for P{G  k}. Since queue size distributions tend to be tail heavy for
large values of the traffic intensity, r , the approximation tends to be less accurate for large r.
On the other hand, this method is very fast and by increasing the truncation value, M, the
accuracy can be enhanced.
Other transform methods may yield better approximations. This is a subject for further study.
The point, however, is that Theorem 1(b) provides a basis for the computation of the
distribution of G, whether by analytical or numerical methods.
4.3 Boundary Values
Two independent and easily computable 'sanity checks' on numerical computation are
available. Theorem 1(a) provides an independent formula for P{G=0} which must equal
1- P{G  1} computed from Theorem 1(b). At the other extreme, the following Lemma
provides an independent check for P{G  (N -1)L}.
Let random variable Q denote the queue size . Then
Proof:
From the definition of G, it is clear that the event which from Observation 9 is
the same as {G  (N-1)L}, occurs when (N-1) sites have empty queues and one site has queue
size at least (N-1)L. There are N ways, i.e. combinations of sites, in which this event can
happen. Due to homogeneity and independence of the sites, each such combination has
probability Hence the lemma follows.
We now specialize Theorem 1 to a number of important queuing models. These cases illustrate
the computation of the distribution of G, EG, and J c .
5. Special Cases
5.1 M/M/1 Queue
In this case, each site is modeled as an M/M/1 queue in which arrivals to a site form a Markov
process and jobs are serviced according to a Markov process. The M/M/1 queue is a well
known model for queues.
Let random variable Q denote the M/M/1 queue size at a site and r denote the traffic intensity.
For clarity we shall omit subscripts (denoting sites) in the following analysis wherever there is
no confusion. We have [3],
Using this expression for the queue size distribution, we obtain the following expressions.
{
To compute the expression in Theorem 1(b), we need to compute the distributions of R, S,
and the distributions of finite independent sums of each of these.
5.1.1 Distribution of S
First consider the term in Theorem 1(b) due to overloads, i.e. the terms involving S. We have
r H+1
This means that for 1  j  N, S j has the same distribution as the random variable
1). Thus, S j
has the same distribution as Q j
. Hence, for k > H, and
Since the Q j above are independent Geometrically distributed random variables each with
parameter r, the sum of J of these is distributed as a Negative Binomial random variable with
parameters (J, r) [5]. Thus, the above probability is given by the following expression.
x
5.1.2 Distribution of R
Now consider the terms in Theorem 1(b) due to underloads, i.e., the terms involving R i . We
have
The z-transform of each R i can be obtained from the above expression. The z-transform of the
sum of I independent random variables, each distributed as R i , is the Ith power of the z-transform
of R i and is given by the following expression.
I
r z
The second term in the above expression is a polynomial of degree (L-1) in (r z). Thus, to
evaluate the above z-transform, we need to know the coefficients of the Ith power of this
polynomial. It is shown in the Appendix that these coefficients, denoted c k , 1  k  I(L-1), are
given by the following expression.
I
Putting all these pieces together and performing algebraic manipulation, we obtain the
following expression in the M/M/1 case.
For
N-I
IL-k
Here, f J is the cumulative distribution function of the Negative Binomial (J,r) density. i.e.,
x
for
Finally, to obtain the expectation of G, we observe that since G is a non-negative random
variable its expectation is given by P{G  k}
. Thus the above formula for P{G  k} can be
used to compute EG.
5.1.3 Computation of the Job Sharing Coefficient
To compute the Job Sharing Coefficient, J c, we recall [3] that the expectation of the queue size
distribution of the M/M/1 queue is r/(1 - r). For various combinations of values of N, L, and
H, EG was computed as described in Section 5.1.2. J c was then calculated from Definition 13
for each of these combinations and plotted as a function of r in Figures 7, 12, 17, and 22.
5.2 M/D/1 queue
When a site is modeled as an M/D/1 queue, the arrival process is Markovian while the service
time is constant across all jobs. In this case, the queue size distribution is given by the
following expressions [2].
n- k
n- k-1
The complex form of causes the computation of the expression in Theorem
1(b) to be intractable. It turns out that for large values of r and n, difficult to
compute accurately since it involves summing up a large number of very small quantities of
alternating sign. Method 2 described in Section 4.2 was used to compute approximations to EG
for various parameter values.
5.2.1 Computation of Job Sharing Coefficient
From [7], we obtain that the average waiting time in M/D/1 queue is given by
, where  is the service rate. Using Little's Law [3], we obtain
Using this expression and EG values as computed in Section 5.2, J c can be calculated from
Definition 13. In Figures 8, 13, 18, and 23, J c is plotted against r for various combinations of
values of system parameters.
5.3 M X /M/1 Queue
The M X /M/1 queue models bulk arrivals, in which jobs arrive according to a Markovian
process, not one by one but in bulk. The number of jobs arriving at a particular time, called the
bulk-size random variable, is a discrete non-negative random variable. A common model for
bulk-size distribution is the Geometric distribution [2]. In addition to arrival rate, l, and
service rate, , an M X /M/1 queue requires a third parameter, a, to describe the Geometric
distribution of bulk size. The first two are usually replaced by their ratio l / , denoted by r,
as in the case of the M/M/1 queue. The queue size distribution for an M X /M/1 queue is given
by the following[2].
In this case, we were able to obtain an exact expression for the distribution of G, as follows.
Let us define a)r. For n > 0, we can rewrite the distribution of Q as
It follows that the overload and underload probabilities are given by the following expressions.
From Theorem 1(a) and the above expressions, we obtain:
1- rb L-1
1- rb L-1
As in the M/M/1 case, we observe that the distribution of the overload term S, is the same as
that of the random variable X is a Geometric random variable with
parameter b . The sum of J independent instances of S is therefore distributed as Y
where Y is a Negative Binomial random variable with parameters (J, b).
To obtain the distribution of the sum of I independent instances of the underload term, R, we
use the z-transform method, as in the M/M/1 case. The z-transform of this distribution is the
I
The second term above is the Ith power of an (L-1) degree polynomial in (bz) whose first term
is not 1, but b(1- r)
. In Lemma 2 of the Appendix, we derive the following expression for
the coefficient of the kth power of (b z), denoted by d k, in this polynomial.
I
I
This yields the following formula.
I
IL-
IL-k
Putting all these pieces together, we obtain the following expression.
For
N-I
IL-k
Here, f J is the cumulative distribution function of the Negative Binomial (J, b ) density, i.e.,
x
for
5.3.1 Computation of Job Sharing Coefficient
In Sec 5.3, we observed that for n > 0, the queue size distribution in the M X /M/1 queue is given
by . Using this expression and the definition of  in Section 5.3, it
follows that
was calculated from Definition 13 for
various combinations of system parameters and plotted as a function of r in Figures 9, 10, 11,
14, 15, 16, 19, 20, 21, 24, 25, and 26.
6. Numerical Results and Discussion
Using the methods described above, EG and J c were computed as functions of the traffic
intensity for three queuing models: M/M/1, M/D/1, and M X /M/1. Two values, 5 and 20, were
chosen for N, the number of sites in the distributed system. For each value of N, L and H were
varied in two ways. First, L was varied from 1 to 3 while H was set at L + 2. Second, L was
kept fixed at 2, while H was varied from 4 to 6.

Figure

Figure 6 are plots of EG vs. r with various combinations of L
and H for the three queuing models mentioned above. Figure 7 through Figure 26 are plots of
the normalized form of EG, i.e., the Job Sharing Coefficient, J c , vs. r.
6.1 Remarks on plots of EG vs. r
The following are observations based upon inspection of Figure 1 through Figure 3 .
For low values of the traffic intensity r, the mean of G is small or zero because the job arrival
rate is much lower relative to the job processing rate. The queue size at each site is therefore
small and each site is either normal or underloaded so that there is seldom a need for load
sharing. When r is large, (i.e., close to 1), the job arrival rate approaches the job processing
rate and most sites are overloaded. Thus, there tend to be fewer underloaded sites to accept
transferred jobs, so EG is again small or zero. However, in the middle range, where r is
neither too small nor too large, job sharing is possible due to the simultaneous occurrence of
underloaded and overloaded sites. Therefore, as can be seen in the plots, EG is significantly
large in the middle range of values of the traffic intensity.
When the difference between H and L is a constant, the EG vs. r plots shift to the right as L
increases. In particular, EG attains its maximum at larger values of r. This is because H
increases with increasing L. Therefore, queue size has to be correspondingly greater for sites
to be overloaded. Hence, the traffic intensity must be higher to enable occurrence of
overloaded sites.
The value of the maximum of EG also increases when L is increased while keeping (H-L)
constant. This is because the total underload in the system (see Definition 10) increases as L
increases. The maximum number of sharable jobs is also an increasing function of L, as noted
in Observation 8.

Figure

Figure 6 are plots of EG vs. r, for the three queuing disciplines mentioned above, in
which the value of the lower threshold, L, is fixed at 2, while the upper threshold, H, is varied
from 4 to 6. In all cases the maximum of EG decreases as H increases. This is because for a
fixed value of r, the probability of overload is a decreasing function of H. Hence, as H
increases the need for load sharing tends to decrease. At the same time, since L is fixed, the
total underload in the system remains constant. Therefore, the mean number of sharable jobs
decreases as H increases while keeping L fixed.
EG tends to be smaller in M/D/1 case than in M/M/1 case. The reason is that there is a much
greater variation in service time in M/M/1 case as compared to M/D/1 case; so there is a
greater probability of the simultaneous existence of overloaded and underloaded sites in the
former case than the latter. On the other hand, in M X /M/1 queuing model with a = 0.75 , EG
vs. r plots are shifted to the left as compared to M/M/1 case. This is because in M X /M/1
case, there is a higher probability of bulk arrivals, which in turn increases the probability that a
site will become overloaded. Hence the need for load sharing will occur at smaller values of
the traffic intensity in M X /M/1 case than in M/M/1 case.
6.2 Remarks on plots of J c vs. r
Since the Job Sharing Coefficient is a normalized version of EG (see Definition 13), plots of J c
vs. r are similar to those of EG vs. r. However, due to the nonlinear relationship of both EG
and EQ with respect to the traffic intensity, some noteworthy observations can be made based
on

Figure

7 through Figure 26. These are described next.
Despite the fact that the number of sites, N, appears in the denominator of the definition of J c
we see that it tends to increase with increasing N for all queuing disciplines. For example, in
M/M/1 case with reaches a peak of 0.15 whereas for
5, the peak is 0.22. The reason is that P{G > 0} increases non linearly with respect to
increasing N. For M X /M/1 queue with a = 0.75, 20, the mean number of
sharable jobs is as high as 45% of the mean number of all jobs in the system. The potential
for load sharing, and hence the benefits from successful load sharing, appear to be high. This
is so especially for large N.
As can be seen in Figure 9 - Figure 11, and Figure 19 - Figure 21, M X /M/1 case shows
interesting behavior with respect to the parameter a. We note that as the parameter a
increases, the peak for J c occurs for smaller values of r. For example, with
the peak for J c occurs at queue as compared to r = 0.52 in M X /M/1 queue
with 0.5. For the same M X /M/1 case, J c is seen to be fairly high even for small values of
the traffic intensity. The same pattern is seen for M X /M/1 case with
We observe that as a increases, the curves for J c tend to shift towards the left. The reason is
that as a increases, the probability of large bulk size arrivals also increases. Hence, the
probability that all sites will be overloaded is high even for small values of r .
Another interesting observation on M X /M/1 queue for a = 0.75 and is that for
the plot for J c is bimodal even though Figure 3 shows that the plots of EG vs. traffic
intensity for the same parameter values are unimodal. Furthermore, although the peaks move
to the right as we increase L and H, the values of the peaks actually appear to decrease slightly.
These observations illustrate that the non-linearity of both EG and EQ results in somewhat
unexpected phenomena especially when the number of sharable jobs is potentially large.
6.3 Comparison with Previous Work
It is interesting to compare our numerical results with those of Rommel [6], especially for the
larger value of N. Since Rommel plots the Probability of Load Balancing Success(PLBS)
versus traffic intensity while we plot the mean number of jobs that can usefully be shared, these
two are not directly comparable. However, in terms of the information that they give to system
designers and analysts, we can contrast them. From Figure Figure 32, we see that across
all queuing disciplines considered in this paper, for similar values of L and H, the
PLBS is essentially flat and equal to 1 for a large range of values of r. On the other hand, for
the same set of parameter values, the curves for EG and J c are much sharper and more
sensitive to r. This striking contrast becomes more visible as N increases. In this sense, our
results are much more informative than Rommel's. This is natural because Rommel's PLBS is
essentially the same as Probability{G > 0} while our formulation takes into account the entire
probability distribution of G. EG and J c both provide detailed insights into the average
number of jobs that can usefully be transferred from site to site rather than merely providing
the information that load sharing is likely to succeed. In particular, EG is the average of the
maximum number of jobs that can be shared among processing sites in the system.
Improvement in overall system performance using load sharing is limited, on the average, by
some function of EG.
7. Conclusions
In this paper, we have precisely defined the notion of the number of jobs that can usefully be
transferred across sites in homogeneous distributed computing systems. This random variable,
called the number of sharable jobs and denoted as G, provides useful information to system
designers and analysts. A number of properties of G have been derived, including a general
expression for its probability distribution, independent of the particular queuing discipline at
each site of the distributed system. The computation of the distribution of G has been
illustrated for three important queuing models. In two of these, exact expressions have been
derived using the general formula. Two methods have been described to compute the
probability distribution of G in cases where exact expressions are not obtainable.
A quantity called the job sharing coefficient, denoted as J c , which expresses the potential for
load sharing normalized with respect to the mean number of jobs in the system, has been
defined. Interpretations and applications of this measure have been discussed. J c has been
computed for various values of key system parameters and plotted against the traffic intensity.
When compared to previous work in this area, our results provide finer and more detailed
insight about the number of jobs which can usefully be shared in a distributed computing
system. In particular, our work provides an upper bound on the number of jobs that can
usefully be shared across sites in the system and hence on the overall system performance
improvement that can be obtained by load sharing. Both the measures we have described can
play important roles in the analysis and design of distributed computing systems.

Acknowledgments

We are greatly indebted to Professor H. Nagaraja, Department of Statistics, The Ohio State
University, for many helpful discussions and suggestions, especially concerning the proof of
Theorem 1. The first author would like to express his gratefulness to Professor Jack W. Smith,
Jr., Director of the Division of Medical Informatics, College of Medicine, The Ohio State
University, for many years of staunch support and encouragement. And, in particular, for
providing a supportive environment for research and study.



--R

A First Course in Combinatorial Mathematics
Fundamentals of Queuing Theory
Queuing Systems
"Load Balancing in homogeneous broadcast distributed systems"
Introduction to the Theory of Statistics
"The Probability of load balancing success in a homogeneous network"
Elements of Queuing Theory with Applications.
"Load Distributing in Locally Distributed Systems"
--TR

--CTR
M. Sriram Iyengar , Mukesh Singhal, Effect of network latency on load sharing in distributed systems, Journal of Parallel and Distributed Computing, v.66 n.6, p.839-853, June 2006
distributed systems;load sharing;job sharing coefficient;sharable jobs